Changing N in a PPLNS scheme

[TierNolan]

The idea behind a PPLNS (pay per last N shares) scheme is that instead of getting 100% of your share value (which has a high probability of being worthless), you get 1/N of the next N shares.

This reduces variance and is the one of the benefits of pooled mining.

However, a problem occurs if N needs to be changed.

If N was increased from 5000 shares to 7500 shares, then it is not clear what is the fairest way to share out the reward.

Consider where a share 3000 shares after the switch hits a block.

Each share back to the switch over is entitled to 1/7500 of the block's value.  This costs the pool 3000/7500 = 0.4 of the block's value.

The 2000 shares before the switch over are all entitled to 1/5000 of the share's value (since it is within 5000 shares).  This costs the pool 2000/5000 = 0.4 of the share's value.

This leaves 0.2 of the block's value unassigned.

However, the reverse happens when the pool switches from 7500 to 5000.

Each share back to the switch over is entitled to 1/5000 of the share's value.  This costs the pool 3000/5000 = 0.6 of the block's value.

The 4500 shares before the switch over are all entitled to 1/7500 of the share's value (since it is within 7500 shares).  This costs the pool 4500/7500 = 0.6 of the share's value.

This is 1.2 times the block's value.  In effect, the pool would have to "give back" the excess profits from switching upwards.

I was thinking about p2pool and how it handles payouts (my understanding of the rules might be wrong here).

My understanding is that it saves 1 day's worth of shares.  The payout goes to the last 24 hours of shares or shares worth 3X the difficulty of the block.

N = min(1 day's shares, 3 X block difficulty worth of shares)

This is a PPLNS system but N changes. 

If the pool hash rate drops, then N is reduced, since it only stores 24 hours.

If it managed to get at least 3 blocks every day, then dropping shares older than 1 day wouldn't affect things, since those shares would have expired anyway.

You get D shares for solving a share of difficulty D and N would be equal to 3*B (where B is bitcoin's block difficulty).

As long as B doesn't change, N is constant.

However, during a re-target the effective N would change.  If bitcoin's difficulty increases, it would cause an increase in B and so an increase in N.

This suggests that miners on p2pool get a bonus if they mine just before an increasing in bitcoin's difficulty (since the pool doesn't actually take the excess).  Similarly, if the difficulty is likely to drop, then miners would be underpaid.

A potential solution would be to slowly change N.  This would spread the problem over a larger period of time.  Some slew rate would keep the payout within 0.1% of theory (both for rising and falling).

In addition the 24 hour rule means that if the hash rate drops, then that is a good time to join the pool (assuming you expect the hash rate to increase).

[jgarzik]

BTC Guild's switching seems to have worked out just fine.

They assign shares to rounds, and changed the "N" value between rounds, when they needed to change.

[TierNolan]

BTC Guild's switching seems to have worked out just fine.

They assign shares to rounds, and changed the "N" value between rounds, when they needed to change.

They say that each shift is around 55 million shares without giving how the calculation works.  I assume that it is basically the difficulty of 1 block?

That might accomplish the smoothing required to reduce the effect to negligible.

Now that I think about it, it isn't really pay per share anyway.  If difficulty drops, then a difficulty 1 share is actually worth more, in terms of BTC, so probably compensates.

N can just be set to 3 blocks and done.  There would be an issue when changing minting target and it ignores tx fees.

[teukon]

To solve this, I'd start by thinking about the simpler problem of how to start or end a PPLNS pool "fairly" (in a hop-proof manner).

Keep things simple to start with, assume the pool is central (so there is a pool owner that can hold reserves) and that the reward and difficulties are fixed.

If the Kth share submitted to a pool generates a block and K < N, how does the reward get distributed?  If the public plan is to give [reward]/K for each share then the expected value of the first N shares submitted to the pool is greater than normal.  If you give just 1/N what do you do with the rest of the block reward?

When you close the pool, how do you compensate people that hold the last N shares?

One simple solution to the above is to have the pool collect the extra reward if any when the pool is created (always pay out 1/N to each share, even if there are not yet N shares) and pay out K/N * [expected value of a share] to shares that have their potential cut off when the pool is closed.  Of course, there is risk to the pool operator but that risk is bounded (unlike 100% PPS).

Next, to change N, one could imagine closing one PPLNS pool and opening another.

I could go further but I think this covers the basic point of inquiry.  These reward systems (probability in general) can be tricky and unintuitive and I certainly welcome corrections to my thoughts.

If you want more detailed and heavily scrutinised information on pool reward methods I recommend Meni Rosenfeld's work.

[TierNolan]

Next, to change N, one could imagine closing one PPLNS pool and opening another.

Right, that is the fairest way.

I think for p2pool, it would have to be an accepted non-ideal thing.  The total lost is 75 BTC (assuming 3 blocks) and only to those who are around if it stops.

The only way around it would be to set up some kind of trusted fund.  For example, startup money could be paid into a 3 of 5 address where the 5 people are trusted.  This would then be used to fund the wind down.

Having said that, I think if the shares count in terms of minting reward then the problem goes away for p2pool (effectively N never changes).

If you hit a block you get (mint reward) * (share difficulty) / (block difficulty) * (some constant)