Double geometric method: Hopping-proof, low-variance reward system

[Meni Rosenfeld]

This is a new reward system for mining pools, a hybrid between PPLNS and the geometric method which combines advantages of both. It starts with PPLNS-like low share-based variance without operator risk, and then allows the operator to absorb some variance to decrease pool-based variance (which the geometric method can do, but not PPLNS). It is of course hopping-proof - the expected payout per share is always the same no matter when it was submitted. The variance and the maturity time (the time it takes to receive the reward) are independent of the pool's history and almost completely independent of future difficulty changes.

The method is purely score-based, which means that all the information required to calculate payouts can be encoded with a single score value per participant. There is no fundamental need to keep a history of shares. However, because the scores grow exponentially, it is advised to use a logarithmic scale to store their values and do the calculations.

We will denote by B the block reward (assumed constant) and p = 1/Difficulty. In addition there are 3 parameters which can be adjusted to balance average fee, operator variance, share- and pool-based participant variance, and maturity time:
f - Fixed fee.
c - Average variable fee. The average total fee will be (c+f-cf)B per block. Increasing c reduces participants' variance but increases operator's variance.
o - Cross-round leakage. Increasing o reduces participants' share-based variance but increases maturity time. When o=0 this becomes the geometric method. When o->1 this becomes a variant of PPLNS, with exponential decay instead of 0-1 cutoff (note that "exponential" does not mean "rapid", the decay can be chosen to be slow). For o=1, c must be 0 and r (defined below) can be chosen freely instead of being given by a formula.

The method is as follows:
1. When the pool first starts running, initialize s=1. Initialize the scores of all workers to 0.
2. Set r = 1 + p(1-c)(1-o)/c. If at any point the difficulty changes, p and then r should be recalculated.
3. When a share is found, increase by p*s*B the score of the participant who found it. Set s=s*r.
4. If the share found happens to be a valid block, then after doing #3, also do the following for each participant: Letting S be his score, give him a payout of (S(r-1)(1-f))/(ps). Set S=S*o. The remaining reward is given to the operator. Or, if the total is higher than the block reward (only possible if f<0), the operator pays the difference out of his own funds.

The inutition is this: Instead of keeping the score unchanged when a block is found (as in PPLNS) or setting all scores to 0 and effectively transferring them to the operator (as in the geometric method), a part of the score is transferred to the operator. When rounds are long, participants get to keep most of their score between rounds and this is similar to PPLNS. However, if several blocks are found in rapid succession, the operator will collect a large portion of the score and thus be the primary beneficiary of the good fortune. The fees collected this way allow letting f be negative, sweetening the rewards of long rounds. Overall, this decreases the dependence of participants' rewards on the pool's luck, thus reducing the variance caused by it.

The variance of the payout for a single submitted share is

(1-c)^4(1-o)(1-p)p^2(1-f)^2B^2
------------------------------
   (2-c+co)c+(1-c)^2(1-o)p

Notably, the factor of (1-o) allows this to be much smaller than the variance of the geometric method, if o is chosen close to 1. This value is of relevance, though, only to small miners, and the potential advantage of this system is for large miners (which suffer from pool-based variance but not so much from share-based variance). It would be of interest to evaluate the total variance for a participant constituting a given portion of the pool, and the variance of the operator. So far I was unable to derive symbolic expressions for these, but they can be evaluated in simulation. For c = 0.5, o = 1-c = 0.5, f = (-c)/(1-c) = -1 I got that a miner constituting the entirety of the pool has about 30% of solo variance (instead of 100% as in PPLNS), and the operator's variance is about 25% of PPS variance.

The geometric method was so called because shares decay in a geometric sequence, and its analysis crucially depends on summation of geometric series and the fact that round length follows the geometric distribution. Because in this new method shares decay geometrically along two directions, both for every share found and for every block found, I call it the double geometric method.

The variables used in the calculations grow rapidly, so if the method is implemented naively, they will overflow the data types used. Thus the implementation should use one of the following:

a. Periodic rescaling: The only thing that matters is the values of the scores relative to the variable s. Thus, if the values grow to large, all that is needed is to rescale them. This means dividing the scores of all participants by s, and then setting s=1. This should be done once in a while, the exact times do not matter (it can even be done for every share).

b. Logarithmic scale: Instead of maintaining the variables themselves, their logarithms are stored and updated. The following is the method expressed in logarithmic scale, denoting by log the natural logarithm function and by exp the natural exponentiation function:
1. When the pool first starts running, initialize ls=0. For every worker define a variable lS and initialize it to negative infinity (or a negative number of very large magnitude, say -1000000), and do this also for every worker which later joins.
2. Set r = 1 + p(1-c)(1-o)/c, lr = log(r). If at any point the difficulty changes, p, r and lr should be recalculated.
3. When a share is found, let lS = ls + log(exp(lS-ls) + pB) for the participant who found it. Set ls = ls + lr.
4. If the share found happens to be a valid block, then after doing #3, also do the following for each participant: Give him a payout of (exp(lS-ls)*(r-1)*(1-f))/p. Set lS = lS + log(o).

For display purposes, the quantity that should be shown as the score of a worker is S/s (or exp(lS-ls) in logarithmic scale). This represents the expected payout the worker should receive in addition to any confirmed rewards (before fees). To display the expected payout after deducting fees, use (1-f)*(1-c)*S/s, or (1-f)*(1-c)*exp(lS-ls).

[kano]

How about just break the block down into 10 minute intervals and thus divide the block total (e.g. 50) by the number of intervals and that fraction divided up over the shares during that interval.
(or even use the network block times themselves)

Anyone want to do the math?

Does it solve the supposed 43.5% issue mathematically?

[sirky]

How about just break the block down into 10 minute intervals and thus divide the block total (e.g. 50) by the number of intervals and that fraction divided up over the shares during that interval.
(or even use the network block times themselves)

Anyone want to do the math?

Does it solve the supposed 43.5% issue mathematically?

I don't think so. It is an interesting proposition though and it made me think some.

The issue is still that it's always better to mine at a pool with fewer intervals, all things being equal, because your shares will still be worth more than they are at a pool with more intervals, but a lower hash rate (so you would get a higher per interval payout).

Not to mention that a 10 minute interval at a place like deepbit is basically an entire round. While at a small pool 10 minute intervals are very few shares.

[jkminkov]

How about just break the block down into 10 minute intervals and thus divide the block total (e.g. 50) by the number of intervals and that fraction divided up over the shares during that interval.
(or even use the network block times themselves)

Anyone want to do the math?

Does it solve the supposed 43.5% issue mathematically?

don't break rounds, merge 3 rounds and pay 150btc

[Meni Rosenfeld]

How about just break the block down into 10 minute intervals and thus divide the block total (e.g. 50) by the number of intervals and that fraction divided up over the shares during that interval.
(or even use the network block times themselves)

Anyone want to do the math?

Does it solve the supposed 43.5% issue mathematically?

Then it's more profitable to mine at the beginning of an interval.
Actually it will create interesting dynamics depending on the number of hoppers. But it's still more profitable to mine early in the round.

don't break rounds, merge 3 rounds and pay 150btc

It's more profitable to mine in the beginning of the 3-round batch, or after 1 or 2 blocks were found if there are relatively few shares.


Anyway, this is off-topic, hopping-proof methods have been known for months, no need to reinvent the square wheel. This post is about a breakthrough in low-variance reward systems.

[Sukrim]

How does this deal with variable or unknown block rewards? Already now block rewards are rarely 50 BTC and the endgame scenario is anyways random block rewards (which should just be profitable).

Some comparisons between Geometric, PPLNS and PPS:

Share decay (If I stop mining, how will my expected balance decay):
Geometric: Exponential
PPLNS: Linear
PPS: None

Maturity time (How long after I submit a share will I be able to claim the full reward for this share):
Geometric: after block was found + calculations for payout have finished (+120 confirmations eventually)
PPLNS: N more shares have been submitted after my share (+eventually some confirmations)
PPS: Instant (or until a block has been confirmed, though a PPS pool should already start with a buffer!)

Payout estimates:
Geometric: Only estimates, will only be correct if the next submitted share solves the block - otherwise decay
PPLNS: Can only give "baseline" + probabilities for additional earnings (first baseline = 0 BTC/share, after a block was found [blockreward/N] BTC/share etc.) - gets more exact over time the more shares are being submitted after my share
PPS: exact pre-known price per share

Pool can go in minus if there are some long rounds:
Geometric: As far as I understood it - yes
PPLNS: Never
PPS: Biggest threat to true PPS actually

Your system wants to be somewhere in between Geometric and PPLNS.
How is maturity time affected? How exact and how "stable" are payout estimates displayed on a pool website (if I stop mining, how fast do shares decay)? How far can the pool in theory go into minus to "absorb some variance"?

Oh, and it might be great to have a google spreadsheet with example calculations + chart porn!

[Meni Rosenfeld]

How does this deal with variable or unknown block rewards? Already now block rewards are rarely 50 BTC and the endgame scenario is anyways random block rewards (which should just be profitable).

It doesn't. For now I recommend (for all reward systems) that the operator keeps transaction fees, and take this into account in his business plan when he decides what pool fees to take. I'll investigate this more thoroughly as it becomes a bigger problem.

EDIT: As discussed below, this turns out not to be a serious problem. Though variability in block rewards does increase operator risk.

How is maturity time affected?

You should look not at the time until all the reward is obtained, but rather at the average time it is received. So if your reward is 2 BTC, and you receive 1 BTC a million shares from now and 1 BTC two million shares from now, I count it as a maturity time of 1.5M shares. If you consider time to be fully repaid important for reasons of making a clean break from the pool, I have a different suggestion to address this which I will post about later.

When o=1, you can choose r to have whatever tradeoff you want between maturity time and variance. It turns out you get the same tradeoff as with 0-1 cutoff. A good choice is r=1+p, resulting in decay by a factor of e every D (difficulty) shares, with maturity time of 1 (expressed in multiples of D) and variance of (pB)^2/2. This is the same as with PPLNS when N = 2D. Then you can decrease o (and change r accordingly), keeping maturity time constant while decreasing variance of participants (at the cost of increased operator variance).

How exact and how "stable" are payout estimates displayed on a pool website (if I stop mining, how fast do shares decay)?

The decay rate, and the accuracy of the estimates (which is basically the inverse variance), are tunable, and as discussed above, start as good as PPLNS and can then be improved.

How far can the pool in theory go into minus to "absorb some variance"?

The operator can only lose if f is negative, and in this case, can lose up to (-f)B per block found. Compare with PPS, which is equivalent to f -> -Inf and the operator's loss per round is unbounded.

Oh, and it might be great to have a google spreadsheet with example calculations + chart porn!

I'll think about it.

[organofcorti]

In order simulate efficiency and the variability of efficiency for this scoring method, what f c and o values would you suggest I use?

Edit: For use in the simulator I define 'efficiency' to be (reward for a hopping miner)/(reward for a fee-free pps miner).

[Meni Rosenfeld]

In order simulate efficiency and the variability of efficiency for this scoring method, what f c and o values would you suggest I use?

Edit: For use in the simulator I define 'efficiency' to be (reward for a hopping miner)/(reward for a fee-free pps miner).

Use f = -1, c = 0.5, o = 0.5. With these parameters this method is the most different from other methods, so if there are any problems they should show up there. Also, with this the average fee is 0, so efficiency will be exactly 1.

Remember that to simulate/implement this, you need to use either logarithmic scale, or periodic rescaling (once in a while (which could be every share if you're only keeping track of a few workers), divide all scores by s and set s to 1).

[organofcorti]

In order simulate efficiency and the variability of efficiency for this scoring method, what f c and o values would you suggest I use?

Edit: For use in the simulator I define 'efficiency' to be (reward for a hopping miner)/(reward for a fee-free pps miner).

Use f = -1, c = 0.5, o = 0.5. With these parameters this method is the most different from other methods, so if there are any problems they should show up there. Also, with this the average fee is 0, so efficiency will be exactly 1.

Remember that to simulate/implement this, you need to use either logarithmic scale, or periodic rescaling (once in a while (which could be every share if you're only keeping track of a few workers), divide all scores by s and set s to 1).

Thanks Meni, and thanks for the reminder about log scale.

As far as efficiency goes, it's the variation in efficiency I want to simulate, which I think would really be the stand out reason to use this method over other hopper proof methods.

[Meni Rosenfeld]

As far as efficiency goes, it's the variation in efficiency I want to simulate, which I think would really be the stand out reason to use this method over other hopper proof methods.

By this, do you mean simply the variance of the reward? In this case you need parameters that are realistic with respect to the risk operators are willing to take, but for an operator who is already seriously considering offering PPS, I think these parameters are entirely viable (perhaps with a slightly higher f if he wants to gain on average).

[organofcorti]

As far as efficiency goes, it's the variation in efficiency I want to simulate, which I think would really be the stand out reason to use this method over other hopper proof methods.

By this, do you mean simply the variance of the reward? In this case you need parameters that are realistic with respect to the risk operators are willing to take, but for an operator who is already seriously considering offering PPS, I think these parameters are entirely viable (perhaps with a slightly higher f if he wants to gain on average).

It wont really be the statistical parameter 'variance' I'm recording in simulation, just the variation in the reward for this system compared to baseline pps, run for a number of rounds equivalent to days or weeks. But yes, it would record something similar to variance, so I think the parameters you suggest will be useful. The plots generated would look similar to the graph below.

[Meni Rosenfeld]

How does this deal with variable or unknown block rewards? Already now block rewards are rarely 50 BTC and the endgame scenario is anyways random block rewards (which should just be profitable).

It doesn't. For now I recommend (for all reward systems) that the operator keeps transaction fees, and take this into account in his business plan when he decides what pool fees to take. I'll investigate this more thoroughly as it becomes a bigger problem.

On second thought, it is trivial to deal with variable block rewards - at least, in a framework such as this which allows operator variance, and as far as hopping-proofness and expectation is concerned. Analysis of things like variance is harder though. I've changed the wording to be more friendly to incorporating this - basically the score given to a share should be based on the block reward at the time of submitting it.


In other news, I've thought of a new framework which includes as special cases double geometric, 0-1 and linear PPLNS, and their extension to operator variance. Some parts of this I've known for months, others for weeks and a key part I've just thought about. I think in particular the extension of linear PPLNS will give the ultimate variance tradeoff (though it's not pure score-based). I'm so excited... And yet I really need to work on Bitcoil now. So much to do, so little time...

[kripz]

Is your geo method and this double geo method essentially PPLNS but N is the number of shares in the last x hours?

Can you please graph the decay rate?

[Meni Rosenfeld]

Is your geo method and this double geo method essentially PPLNS but N is the number of shares in the last x hours?

Absolutely not.

Time never plays a factor in a hopping-proof method.

To clarify the picture, all these methods fall into a spectrum with two axes:

1. Decay function: 0-1 (step function), exponential, linear etc.
2. Block finding effect: No effect, resetting the round completely, or something in between.

PPLNS is 0-1 with no effect for block finding. Geom is exponential with complete round reset. Double geom is exponential with a partial effect of block finding, the magnitude of which is controlled with a parameter.

Can you please graph the decay rate?

It's exponential decay, you can see a graph of how that looks like here. The exact decay rate depends on the parameters. With double geom it's more complicated because there is also decay when blocks are found, but that's also exponential in nature.

[DrHaribo]

This is a very interesting method. But there are two aspects I am unsure about:

1. The reward is assumed constant. After some time fewer and fewer coins will be minted and transaction fees will be a larger part of the income. Eventually the only income is transaction fees. At some point variable income will be a must.

Perhaps you can just take the payout from the formula today, divide it by 50 and multiple with the actual income.

2. Proofs of work must be handled sequentially. This could impede performance. It could also make it difficult to have multiple backend servers spread around the world for redundancy.

[Meni Rosenfeld]

This is a very interesting method. But there are two aspects I am unsure about:

1. The reward is assumed constant. After some time fewer and fewer coins will be minted and transaction fees will be a larger part of the income. Eventually the only income is transaction fees. At some point variable income will be a must.

Most of the analysis assumes constant block reward, but the method doesn't require it. When you calculate the score for a share, you use the block reward in this share (viewed as a potential block). This guarantees fair expected return, but adds some variance to the operator.

Perhaps you can just take the payout from the formula today, divide it by 50 and multiple with the actual income.

It needs to be the potential income when the share was submitted, not the received income when a block is found.

2. Proofs of work must be handled sequentially. This could impede performance. It could also make it difficult to have multiple backend servers spread around the world for redundancy.

I don't know much about the technicalities of this, but from an algorithmic standpoint, having shares go slightly out of sync only causes a negligible error in the payouts.

[Inaba]

2. Proofs of work must be handled sequentially. This could impede performance. It could also make it difficult to have multiple backend servers spread around the world for redundancy.

This was my conclusion as well when coding the backends for EMC.  However, there are ways to account for that by storing shares and calculating them according to time submitted.  Unless your hashrate is in the multiple TH/s range, accommodating multiple back ends is not too difficult.

[urstroyer]

Perhaps you can just take the payout from the formula today, divide it by 50 and multiple with the actual income.

It needs to be the potential income when the share was submitted, not the received income when a block is found.

I'am looking for a way to determine the estimated block reward B when a share (which is not solving the block) was submitted. Is that even possible?

A possible solution i have in mind: we increase the user score for every submitted share on block x as soon as block x was solved and we know exactly how much B was.

Is that's the way it should be done?

[Meni Rosenfeld]

Perhaps you can just take the payout from the formula today, divide it by 50 and multiple with the actual income.

It needs to be the potential income when the share was submitted, not the received income when a block is found.

I'am looking for a way to determine the estimated block reward B when a share (which is not solving the block) was submitted. Is that even possible?

A possible solution i have in mind: we increase the user score for every submitted share on block x as soon as block x was solved and we know exactly how much B was.

Is that's the way it should be done?

That's exactly the thing I said shouldn't be done. The correct way is much simpler, it's to use the block reward of the share itself. That is, the share is a hash of a block header you hand out for the getwork, which has a merkle root of a transaction list with a given total transaction fee, which together with generation is the total block reward. That's the value of B which should be used for this share.