normalized Proportional Payout - Nearly identical to PP although hopper-proof!

[streblo]

EDIT: This is all wrong. Nevermind

Introduction
Proportional Payout (PP) pools can be easily cheated by only submitting shares early in the round (see section 1, below). Alternative schemes exist to address pool-hopping, but all come with disadvantages:
still exploitable by pool-hoppers (including PPLNS, slush's pool, see section 2)
increased BTC return variance for miners as compared to PP (PPLNS, slush's pool)
possible decreased returns (score-based systems)
increased risk for pools (PPS)
Pool complexity and obscurity - (all)

There is a miner-driven demand for PP pools, despite their ability to be exploited, likely due to distrust for pool complexity and obscurity. Many PP pools have resorted to delaying or falsifying statistics to fend off hoppers, although this does nothing to solve the crux of the situation. This game of cat-and-mouse will continue, perhaps with hoppers determining how to independently infer round_shares of pools (which is deserving of a discussion of its own). Fundamentally, there exists a demand for a pool payout scheme with identical payout to PP for honest miners while removing the ability to be exploited by hoppers. Here, I present a new payout scheme, dubbed normalized Proportional Payout (nPP), which is mathematically impossible to cheat with hopping, while offering identical payout to miners which have a constant share submission rate. nPP requires no complex coding and pays out 100% (minus fees) of the generated BTC with every block (in other words, no BTC buffers) while not subjecting pools to variance risk. This work is based on statistics first formulated by Raulo.  

1) Proportional Payout (PP) Pools
In a proportional pool the expectation value of a submitted share is dependent on one and only one variable: the number of shares submitted previously. Define the normalized shares submitted, x, as the number of shares submitted divided by the current difficulty. Then the expectation value of a submitted share is how much the share is worth (in BTC) on average. When normalized to solo mining, it is equal to exp(x)*E1(x). E1 is a nonanalytic integral, but wolfram alpha will compute it for you. The expectation value is shown in Figure 1. Notice the expectation value is is greater than one before x~0.428 and less than one after 0.428. This is where the magical 42.8% comes from: shares submitted to the pool when x<0.428 have an expectation value greater than one. This is the essence of pool-hopping. Any payout system with an expectation value of 1 for all x is hopping-proof; conversely, any other system is subject to hopping-based exploitation.


Figure 1. Speedup vs normalized shares submitted (see above text)

2) Other scoring methods[I misunderstood PPLNS as resetting shares after each new pool round]
Many scoring systems are not statistically analyzed and hence still offer opportunity for hopping. For example, Pay-Per-Last-N-Shares is still quite hoppable (with typical N), as follows. Let's renormalize N by dividing by the difficulty, to give us the normalized last N shares, M. Using the same analysis as above, the speedup can be computed as shown below in Figure 3. PPLNS strongly deviates from PP only during rounds which pay (per share) below the statistical average. Because the hopper "suffers" from PPLNS only during sub-par rounds, the absolute difference between proportional and PPLNS is small. One can calculated the expectation values of PPLNS shares (as a function of x and M), with the following formula (Wolfram link): exp(x) ( Gamma(0,x) - Gamma(0,M+x)) which is valid for x < M. As M is decreased, the ability to be exploited is slightly decreased, but BTC return variance is increased. As M is increased, PPLNS reduces variance although is more exploitable. In fact, M~0 corresponds to solo mining and M~Infinity corresponds to PP. Hence, PPLNS is an interpolation between two undesired schemes. Slush's pool uses a time-based (in lieu of shares-based, as previously) share decay which is also hoppable for identical reasons (one need only multiply by the shares/time to map one to the other).


Figure 3. Comparison of expectation value from share submission from proportional and PPNLS (M=0.5, see text) payout schemes. Notice the intersection with y=1, where share expectation value is equal to solo mining. These intersections are respectively equal to ~0.21 and ~0.428 for PPNLS and proportional.

3) A new pool-hopping countermeasure: normalized Proportional Payout(nPP)
normalized Proportional Payout, nPP, is identical to PP, with one change: each share is normalized by dividing its expectation value (from above, exp(x)*E1(x), see Figure 1) such that instead of expectation value varying with x, one expects a constant amount of BTC, independent of x. Normalized shares at the beginning of the round would be worth less, shares at x=.428 would be equal to one, and shares late in the round would be worth more than one. When a block is found, all BTC are sent out proportionally, according to the amount of "normalized shares" submitted. For non-hoppers, this works out, as stated, IDENTICALLY to PP, with only distinction that nPP is hopper-proof. The calculated normalized expectation value per share is as follows in Figure 4. As you can see, miners could join and leave the pool arbitrarily, without garnering an advantage.


Figure 4. nPP has constant expectation value per share, in contrast to PP. normalized_expectation_value(y) = Integrate exp(y-x)/(x * exp(y) * E1(y)) from x=y to x=Infinity

Normalizing algorithm
Def ExpVal(x):
    return exp(x) * E1(x)

On ShareSubmit:
    x = round_shares / difficulty
    your_normalized_shares += 1 / ExpVal(x)

Payout Algorithm
your_payment = your_normalized_shares / total_normalized_shares * (50 BTC - Fees)


4) Conclusion
nPP offers all the benefits of PP system, with none of the obscurity of other payment systems. Additionally, it is rigorously hopping-proof and easily implementable.


Appendix 1) Numerical approximation of the exponential integral, E1(x) (maximum error less than 0.07%)
u = input
y = 0.5772156649015328606
G = exp(-y)
b = sqrt( 2(1-G)/(G(2-G)) )
hi = (1-G)(G^2-6G+12)/(3G(2-G)^2b)
q = 20/47 * u ** sqrt( 31/(2b) )
h = 1/(1 + u * sqrt(u)) + hi*q/(1+q)
output = exp(-u) * ln(1 + G/u - (1-G)/(h+bu)^2)/( G + (1-G)exp(-u/(1-G)))


Cheers

[Luke-Jr]

Proportional Payout (PP) pools can be easily cheated by only submitting shares early in the round (see section 1, below).

First, Proportional is a reward system, not a payout system. It is usually abbreviated "Prop.", not "PP". More importantly, what you describle is not cheating, but rather common sense: why should a miner contribute to a pool that is currently offering to pay him less than what his shares are realistically worth, when there are other pools willing to pay him fairly (or in the case of just-starting proportional rounds, potentially more)? The problem is with the proportional system itself overpaying and underpaying in a predictable way.

Alternative schemes exist to address pool-hopping, but all come with disadvantages:
still exploitable by pool-hoppers (including PPLNS, slush's pool, see section 2)
increased BTC return variance for miners as compared to PP (PPLNS, slush's pool)
possible decreased returns (score-based systems)
increased risk for pools (PPS)
Pool complexity and obscurity - (all)

None of these apply to the various SMPPS systems.

Here, I present a new payout scheme, dubbed normalized Proportional Payout (nPP), which is mathematically impossible to cheat with hopping, while offering identical payout to miners which have a constant share submission rate. nPP requires no complex coding and pays out 100% (minus fees) of the generated BTC with every block (in other words, no BTC buffers) while not subjecting pools to variance risk. This work is based on statistics first formulated by Raulo.

I'll call it NProp... If it's rewarding identical to constant miners, that means it's still rewarding unfairly and the real problem still exists. Buffers are the only way to pay fairly without creating a liability on the pool operator. Also, I feel it should be noted that for consistent miners, neither Slush and PPLNS increase variation.

Your actual "NProp" system looks more or less identical to Slush's Score system, perhaps varying in some technical details. Unfortunately, it hurts part-time miners (such as pool hoppers) without really fixing the problems. These kinds of systems basically hold your earlier reward hostage if you don't keep mining when the pool offers to pay less than the value of your work.

[gentakin]

M~Infinity corresponds to PP.

I'm not sure if you understand PPLNS correctly, although I am sure I don't understand the maths you posted, so this might be wrong.

Still, if M (or N) is Infty, that means "pay per all shares ever submitted". If I'd submit a share to a pool with PPLNS with N=Infty and then stop mining, then I'd get a reward for every block they find. I don't see how this corresponds to proportional.

Maybe you didn't take into account that PPLNS pays for shares from previous rounds if current_round_shares < N.

[Artefact2]

Maybe you didn't take into account that PPLNS pays for shares from previous rounds if current_round_shares < N.

I think so too. PPLNS is hopper-proof (unless you do it wrong, obviously).

[Meni Rosenfeld]

This post is completely wrong. Virtually all of your premises and conclusions are incorrect.

1. PPLNS always pays out the last N shares, even if they are from previous rounds. It is hopping-proof.

2. The geometric method is hopping-proof without crossing round boundaries.

3. Your method is not hopping-proof. The speedup function is calculated based on the distribution of the number of shares on the round, and on the assumption that they all have a score of 1. Once you change the scoring function this assumption becomes invalid. Take the first share for example. If you score it based on your suggestion and keep the score of all other shares 1, it will indeed have expected payout 100%. But you also decrease the score of the next several shares, thus increasing its expected payout.

In fact it is fairly easy to prove that a hopping-proof scoring method can't be based entirely on distributing the block reward between the participants in the current round. You must do something like take into account previous rounds or give the operator a variable fee.

[streblo]

Hello gentlemen,

Sorry, I formulated my calculations with PPLNS -- I mistakenly thought shares reset after each pool round was over. I don't know how to analytically formulate the expectation value of PPLNS (because one share could, feasibly, be counted for thousands of rounds), but I can run Monte Carlo calculations (with source) to show it is still very hoppable (we can discuss this topic further when I have a a proper argument). Thank you for clarifying this error to me.

First, Proportional is a reward system, not a payout system. It is usually abbreviated "Prop.", not "PP". More importantly, what you describle is not cheating, but rather common sense: why should a miner contribute to a pool that is currently offering to pay him less than what his shares are realistically worth, when there are other pools willing to pay him fairly (or in the case of just-starting proportional rounds, potentially more)? The problem is with the proportional system itself overpaying and underpaying in a predictable way.

Luke-Jr, thank you for your reply. You're more certainly an expert in this area and I am happy to have your comments. I greatly enjoy the Eligius pool.

My apologies for my incorrect terminology, I'll use convention in the future. I must disagree with you: there is a still a strong (perhaps irrational) demand for Prop. pools. Look at deepbit, et al., for instance. I believe miners want pools to pay out all generated BTC right away during "times of luck" (several shorter-than-average rounds).  

Alternative schemes exist to address pool-hopping, but all come with disadvantages:
still exploitable by pool-hoppers (including PPLNS, slush's pool, see section 2)
increased BTC return variance for miners as compared to PP (PPLNS, slush's pool)
possible decreased returns (score-based systems)
increased risk for pools (PPS)
Pool complexity and obscurity - (all)

None of these apply to the various SMPPS systems.

Although I find your SMPPS system to be excellent in the long run, I beg to differ. I believe it suffers from "decreased returns" for finite time spans and pool complexity and obsurity. The decreased returns stem from the fact that the maximum possible payout is is the average payout (1), but there exists a significant probability of less than average payout. I realize your system pays out the expectation value over an infinite time span, although realize if one were to join a SMPPS pool for one round, the expected value of shares is less than solo mining. All me to demonstrate:
the chances SMPPS pays out the full amount is Integral exp(-x) from x=0 to 1, or 63% of the time
Now integrating over the remaining time (x=1 to infinity), times the payout (the same as proportional, 1/x), Integral exp(-x)/x from x=1 to Infinity, one gets .22.
Hence, the expectation value for a SMPPS pool with a buffer less than or equal to zero, is .63+.22 = .85. In other words, for SMPPS for ONE round, NOT infinity the expectation value is 15% less than solo mining.

My pool complexity and obscurity claim is subjective, although, from lack of pool adoption, we can infer the community sees barriers to its use.

Here, I present a new payout scheme, dubbed normalized Proportional Payout (nPP), which is mathematically impossible to cheat with hopping, while offering identical payout to miners which have a constant share submission rate. nPP requires no complex coding and pays out 100% (minus fees) of the generated BTC with every block (in other words, no BTC buffers) while not subjecting pools to variance risk. This work is based on statistics first formulated by Raulo.

I'll call it NProp... If it's rewarding identical to constant miners, that means it's still rewarding unfairly and the real problem still exists. Buffers are the only way to pay fairly without creating a liability on the pool operator. Also, I feel it should be noted that for consistent miners, neither Slush and PPLNS increase variation.

Your actual "NProp" system looks more or less identical to Slush's Score system, perhaps varying in some technical details. Unfortunately, it hurts part-time miners (such as pool hoppers) without really fixing the problems. These kinds of systems basically hold your earlier reward hostage if you don't keep mining when the pool offers to pay less than the value of your work.

Constant miners are rewarded identically, that's the beauty. Share value changes with pool round duration, such to normalize the expected BTC per share. In a Prop pool you could multiply the share value by the moon phase if you wanted, and constant miners would not be affected. The moon phase is silly though, my normalization standardizes shares in a rigorous statistical manor in order negate the effects of joining or leaving a pool early or later on.

I disagree one your claim that buffers are required for fair payment. Buffers not needed in nProp, create no pool owner liability, are hopping-proof, and still pay out fairly. (shown above)

I also disagree that Slush's method and PPLNS do not decrease variation (although the math is difficult to show rigorously). By decreasing the number of shares averaged over (be it by an exponential time-factor or a finite-sized share-window), variance in increased. Can we agree that for sufficiently fast exponential decay factor "C" or N=1, once only one share is considered during payout, that the variance is that of solo-mining? Hence for more typical values, the variance is increased as compared to Prop. SMPPS does have a decreased variance, even over proportional, although it comes at the cost of expectation value of ~15% (see above).

My NProp scheme is very different than Slush's, namely, shares are kept indefinitely and at constant value. For instance, a share submitted years ago will still have the same value now as it did when it was submitted. My system has no penalties for any contribution scheme: the expected BTC is constant per share submission, independent of shares submitted! This is the entire basis of the payout scheme! NProp. does not keep any BTC hostage as it has no buffers and normalized shares NEVER decay in value (either in time nor in shares submitted as in Slush's or PPLNS). It is friendly to intermittent miners and requires no buffers. Additionally, the variance is minimized while maintaining a normalized expectation value of 1 per share for any time horizon.

I look forward to your reply.

[streblo]

This post is completely wrong. Virtually all of your premises and conclusions are incorrect.

1. PPLNS always pays out the last N shares, even if they are from previous rounds. It is hopping-proof.

2. The geometric method is hopping-proof without crossing round boundaries.

3. Your method is not hopping-proof. The speedup function is calculated based on the distribution of the number of shares on the round, and on the assumption that they all have a score of 1. Once you change the scoring function this assumption becomes invalid. Take the first share for example. If you score it based on your suggestion and keep the score of all other shares 1, it will indeed have expected payout 100%. But you also decrease the score of the next several shares, thus increasing its expected payout.

In fact it is fairly easy to prove that a hopping-proof scoring method can't be based entirely on distributing the block reward between the participants in the current round. You must do something like take into account previous rounds or give the operator a variable fee.

1) I appologize for interpreting PPLNS incorrectly. I see my error. [Edit: I think it is hopping proof]

2) the geometric method, although excellent, has irrational factors which prevent it's adoption: viz., complexity and obscurity

3) This is interesting. I'll investigate further. Would you be kind enough to supply with such a proof?

[Meni Rosenfeld]

1) I appologize for interpreting PPLNS incorrectly. I see my error. I disagree that it is hopping-proof. Consider this (rigorous simulations coming later): A share submitted immediately after a pool finds a block has more opportunity to be counted for multiple blocks than one submitted late into a "pool round". When all possibilities are integrated over, the expectation value must be equal to one, hence, if the expectation value, per share, varies with time or round_shares, it is hoppable.

No, the number of shares per round follows the exponential distribution which is memoryless. The payout for a share depends only on the blocks found in the future, not in the past, which doesn't depend on the number of shares already submitted in the round.

3) This is interesting. I'll investigate further. Would you be kind enough to supply with such a proof?

Let B be the block reward minus fixed fees, and p=1/difficulty. Then every share must be paid on expectation pB. The first share has probability p to end the round, and in a naive scoring system this will means it earns the entire reward B. This contingency alone gives at an expectation pB, so it must receive 0 payout if it's not valid (otherwise the expectation would be more than pB). So if the second share is valid then it receives the entire reward, so the same argument applies, and by induction any share receives the entire block reward if it is a valid block, and 0 otherwise (so in fact the accurate statement is that the only naive hopping-proof scoring method is solo. Which is, by the way, the limit case of the geometric method when the variable fee is 0).

[streblo]

Let B be the block reward minus fixed fees, and p=1/difficulty. Then every share must be paid on expectation pB. The first share has probability p to end the round, and in a naive scoring system this will means it earns the entire reward B. This contingency alone gives at an expectation pB, so it must receive 0 payout if it's not valid (otherwise the expectation would be more than pB). So if the second share is valid then it receives the entire reward, so the same argument applies, and by induction any share receives the entire block reward if it is a valid block, and 0 otherwise (so in fact the accurate statement is that the only naive hopping-proof scoring method is solo. Which is, by the way, the limit case of the geometric method when the variable fee is 0).

You're completely right. Through a different means, I also figured this out by trying to derive the normalization function, call it norm(x):

[ Integrate exp(y-x)/x * norm(x) from x=y to x=Infinity ] == Constant

Solving integral equations isn't my strong suite, but I convinced myself norm(x) doesn't exist. I am curious if one would be able to make a norm(x) such that instead of the RHS being constant it is something constant until a very large number of shares (say 10x difficulty) are submitted. For example, something like erfc(x-10)/2. But that's besides the point, other systems have solved it.

Cheers