3.2 The risks of SMPPS

-1. Addendum to "3.2 The rise and fall of Arsbitcoin.com"
While researching the last post  I missed this statement from Arsbitcoin pool operator Burning Toad. An excerpt:

"Once I figure out the details, I will be shutting the pool down.  But basically, once I announce it, it will be something like 30 days left to mine, 60 days left to claim bitcoins on the site that may be in your account, and then 90 days until I officially close accounts (can still claim coins.)  Once I officially announce, notices will be posted on the site, all members with balances and/or recent mining activity will be emailed, etc."

If the pool does close in this manner I think this says much in favour of the pool operator's integrity. Closing a pool down is a large task and needs to be done in a way that won't disadvantage miners. Some pool operators - for example Bitp.it - have simply walked away leaving miners scratching their heads and missing coins. The correct way to close a mine is a topic I'll hopefully get to at some point.

16/04/2012 Edit: After an in depth conversation with Meni Rosenfeld on the bitcointalk forums, I have removed  3. How likely is a large negative buffer? and replaced it with 3. What is the average maturity time? and 4. What does pool hashrate matter? I hope you find it interesting. I'm grateful to Meni for his patient help and any new errors are mine alone.

0. Introduction

The following post is not targeted at Arsbitcoin.com (although most of the comparison data will come from Arsbitcoin) as much as it is targeted at the SMPPS payout system. A large portion of my information comes from Meni Rosenfeld's excellent guide "Analysis of Bitcoin Pooled Mining Reward Systems". A read of the SMPPS section will make this post easier to follow. Don't worry if you don't completely follow the math. Meni's conclusions are clear and easy to follow. I'll be applying his insights to Arsbitcoin.com as well as my own.

1. How does SMPPS work?
SMPPS is a response to fee paying pay-per-share (PPS). Rather than summarise it, I'll quote directly from http://eligius.st/wiki/index.php/Shared_Maximum_PPS:

Miners accumulate Pay-Per-Share as usual. When a block is found, the pool counts the total unpaid PPS credits. If there are sufficient pool funds earned to pay them all in full PPS, that happens. If not, the miners are paid proportional to available funds. Remaining pool funds accumulate toward future payouts. The difference between a miner's actual (SMPPS) earnings and PPS earnings is retained as "extra credit", and considered in future blocks.

So all miners are credited 1/D (D=current bitcoin difficulty) for every submitted share. Whether that get's paid immediately depends on the total amount of credit the pool has after the block reward is added.

The "extra credit", the amount owed to miners for shares submitted but not paid, is by no means guaranteed to be paid:

....... Instead of paying you with just BCs (which it doesn't have enough to do), you are instead issued a fiat "extra credit" which has no value in itself, but the pool will count as earnings in future rounds.

And from  Luke-Jr, the major proponent of SMPPS, in response to a comment discussing the amount of outstanding coin "owed" to an Arsbitcoin miner (discussed here: https://bitcointalk.org/index.php?topic=18567.msg811992#msg811992)

I suspect you mean extra credit. That was never promised to become Bitcoins or retain any value.

The issue of extra credit is only likely to be a problem in the case of the failure of an SMPPS pool, or a changeover to a different payout method. However as we shall see SMPPS pools are prone to bankruptcy due to negative buffers (ie the pool has insufficient funds to pay miners) and it is in this situation that miners will not be paid. This makes it very likely that at some point miners on an SMPPS pool will lose funds and not be paid 1/D for shares submitted.

Below is a simulation of an SMPPS pool's buffer over time.

2. Maturity time and "pool hopping".
Ignoring the time it takes for a block to be confirmed (accepted as being part of the block chain) and assuming no changes in pool hashrate, the length of time it takes for a miner to receive an average payout is proportional to the number of rounds of negative buffer a pool has and can be shown to be:

-R/B

where R = the current pool debt (or -1 x negative buffer)
and B = the current bitcoin reward.

This is derived by Meni Rosenfeld in Appendix F2 of "Analysis of Bitcoin Pooled Mining Reward Systems" and  the proof won't be repeated here. So, to use Meni Rosenfeld's example, if a pool has a negative buffer of 500 btc and the current bitcoin reward is 50btc per block solved and added to the block chain, then the time it takes for a miner to receive the "extra credit" is:

500/50 = 10 rounds

The time it takes the pool to solve ten rounds is how long a miner will need to wait to receive the average payment of their "extra credit". A full payout may take longer. The lower the pool hashrate, the longer it will take for a miner to be paid.

Some miners will not want to wait a long time to be paid, and will instead leave the pool to mine somewhere they will get paid more quickly. This is "strategic mining" or "pool hopping" - trying to get the best possible value for any share submitted. 

The problem is that when strategic miners leave, the hashrate is reduced and the time to maturity is increased further since the time to solve blocks has increased. If the pool stays in a large negative buffer long enough, it is a likely that all miners will leave, and the pool will fail. In this case, many miners will have received much less than 1/D for their shares, especially if they started to mine at the pool while the buffer was negative.

The likelihood of an SMPPS pool failing is thus related to the likelihood of a significantly large negative buffer at some point in time.

3. What is the average maturity time?

We define maturity time in an SMPPS pool as the amount of amount of time it takes to be paid the average of the PPS payout owed for a given round. For example, a miner is owed 1 btc for a round and is paid 0.25 btc per round for the next four rounds, the maturity time is two rounds.

Recall maturity time when an SMPPS pool has a negative buffer is -R/B and the maturity time for a miners' payout is the maturity time for the round. When the pool has a positive buffer, the maturity time is 0. This means that the average maturity time is non-zero.

To estimate average maturity time, we can use the negative binomial distribution to estimate probability mass function (PMF) of the total number of shares submitted by a particular round. For those familiar with this probability distribution, skip ahead a few paragraphs. 

The number of shares it takes to solve a block is a random variable distributed according to a special subset of the negative binomial distribution, the geometric distribution. However, the number of shares it takes to solve n rounds is a random variable distributed according to a negative binomial distribution where x is the total number of shares submitted (the number of failures), n is the target number of successes and p=1/D is the probability of success. So the likelihood of any given buffer can be calculated using the negative binomial distribution cumulative probability distribution function (CDF), after normalising for D and the current bitcoin reward, B.

Since maturity time is determined only by how much a pool owes at a given time, mean maturity time is the expected or mean negative buffer at any round n. 

The mean maturity time for a sample of pools at round n would can be described as a weighted mean where positive buffers have a weight of zero and negative buffers have a weight of 1. 

If we sample a large number of pools, then the number of positive buffer rounds will equal the number of negative buffer rounds, normalised for D. So for 2*j SMPPS pools, all at the same round, the weighted mean is:

  (xneg1*1+xneg2*1+…+xnegj*1+xpos1*0+xpos2*0+…+xposj*0)/(2*j)
   = (xneg1*1+xneg2*1+…+xnegj*1)/j*(1/*2)

where xneg1 is the first negative buffer in the sample, and so on for xneg2,... xnegj
and xpos1 is the first positive buffer in the sample, and so on for xpos2,... xposj

This shows that the mean maturity time is 1/(D*2) multiplied by the negative buffer mean. 

Deriving the negative buffer mean from a CDF for part the negative binomial distribution is difficult. However the mean can be estimated using a half normal distribution:

Negative buffer mean = sqrt(variance * 2/pi)/D

The variance of the negative binomial distribution is:

(1 - 1/D)*n/D^2 ~ n/D^2 when D is large.

Using this variance:

Negative buffer mean = sqrt(n/D^2*2/pi) = sqrt(n*2/pi)*D/D

So the mean maturity time at a given round n will be given by:

Maturity time mean = sqrt(n*2/pi)*(1/2)   = sqrt(n/(2*pi))

This is quite a good approximation, and at current D is within 2% of the maturity time mean as calculated by Monte Carlo simulation.

We might also wish to determine the average maturity time a miner will have experienced from the start of the pool until round n, rather than just at round n as derived above. Rather than deriving this, it can be calculated by averaging the maturity times from 1 to n.

The graph below shows the mean maturity time at round n and the expected mean maturity time from round 1 to n

As can be seen, the expected maturity time increases quite rapidly. By only 100 rounds, the average maturity time is already approximately the time it takes to solve four blocks, and at 1000 rounds a miner will need to wait on average approximately twelve to thirteen blocks in order to receive his averaged payment.

Also, at 1000 rounds, a full time miner on an SMPPS pool since its start will have experienced an average maturity time of 8.4 over all rounds until round 1000.

4. What does pool hashrate matter?

Whether a miner considers waiting twelve blocks for payment to be 'long' will depend on how much variance the miner can bear and how large the pool hashrate is - how quickly blocks can be solved. 

If we define chronological maturity time as the length of time it takes to solve the number of blocks defined by the maturity time, then

CMT = MT/HR

where CMT = chronological maturity time

       MT = maturity time

       HR = pool hashrate

A faster pool hashrate though means a reduced chronological maturity time but also a more rapidly increasing mean maturity time. For two pools that start at the same time with the same hashrate since the start, the ratio in average chronological maturity time is given by:

CMT1/CMT2 = sqrt(H1/H2)/(H1/H2) = (H1/H2)^-0.5

where H = pool hashrate

             1 = larger hashrate pool

             2 = smaller hashrate pool

For two pools at the same round since the start, the ratio in average maturity time is given by:

CMT1/CMT2 =  H1/H2

In both cases, the higher the hashrate, the sooner a miner will be paid. There is no situation in a lower hashrate at an SMPPS pool is advantageous.  

5. How likely is a large negative buffer?

A large negative buffer will create a long wait for a miner to be paid. A very long wait and a miner might decide not to mine that pool any longer. So as well as knowing the average maturity time, a miner will want to know the probability of an arbitrary negative buffer at an arbitrary round.

This type of problem - limits of random variables - has been investigated many years ago by famous mathematicians Erdös and Kac, in particular the limits of series of sums of independent random variables with a mean of 0. The full paper is here, but we are only interested in the first limit theorem:

Without going into detail, this tells us that probability of a given maximum α (for α >=0) occurring for a series of sums of independent random variables with a mean of 0 and v=unit variance can be calculated by the given integral. Since a cumulative sum of independent random variables with mean of 0 is such a series, we can use this integral to determine the probability of certain maxima occurring.

On calculating the integral the result is:

2 * normal distribution CDF  for α (mean = 0, sd = 1) - 1

This can also be described in terms of the error function:

sqrt(pi/2) * erf(α/sqrt(2))

We can also check we have interpreted this correctly by comparing the probability density of this function (2 x normal distribution PDF from α = from 0 to infinity) to the density of maxima from a simulation. Instead of unit variance we use the summed variance for α number of geometric distributed variables:

n * (1-1/D)/(1/D)^2

The simulation runs a series of cumulative sums of geometrically distributed randoms for n rounds and collects the maximum negative pools buffers. The density of the result is plotted against the error function density for various n and α between 0 and 5000 btc. The correlation is quite clear.

Now we can chart the CDFs for the maxima, again for  n = 100, 1000, and 10000 rounds, and for α between 0 and 5000 btc, using 

sqrt(pi/2) * erf(α/sqrt(2))

with variance

n * (1-1/D)/(1/D)^2

As before, the more rounds the pool solves, the greater the probability of a large negative buffer occurs. However, in this case we also consider maxima occurring at any time before the series of rounds end and the probability of a maximum negative buffer occurring before this time is much higher. The grey vertical line shows where a 1000 btc negative pool buffer intersects the upper tail CDF.

The probability of a 1000 btc negative buffer occurring before the series of n rounds end:

• at n = 100 rounds, p = 0.05
• at n = 1000 rounds, p = 0.52
• at n = 10000 rounds, p = 0.84

Thus the more blocks a pool solves the more likely a very high negative pool buffer will occur. 

6. How likely is Arsbitcoin.com's negative buffer?

This is calculated as described above, using n = 1700 rounds and α = 1000 btc, variance averaged to be based on D=1.3*10^6 and converting for the upper tail:

1-(2 * normal distribution CDF for α = 1000 btc (mean = 0, sd = 1700*(1-1/D)/(1/D)^2) - 1)

gives:

> 1-(2*pnorm((1000)/50*D,0,sqrt((1-1/D)*1700/(1/D^2)))-1)
[1] 0.6276257

With a probability of ~ 0.63, Arsbitcoin's current state of buffer was quite likely to have occurred. Eligius, the other large SMPPS pool is not immune from this problem, although according to their stats they seem not to have had a negative buffer at all in the last 1545 blocks. This should not be seen as anything other than quite good luck, and it can be considered likely that at some point in the next few thousand rounds that Eligius will encounter a maximum negative buffer that will drive miners away.

7. Conclusions

• The amount of time it takes for a miner to be paid is affected by the pool buffer:
• A large negative buffer at will greatly increase the time it takes for a miner to be paid. 
• A buffer greater than zero minimises the time  it takes for a miner to be paid. 
• A strategic miner will only mine at an SMPPS pool when it has a positive buffer.
• Average maturity time is approximately sqrt(n/(2*pi)). Arsbitcoin.com's maturity time of approximately 1000 btc at 1700 rounds is not much more than the average at 1700 rounds, 822 btc.
• A reduction in pool hashrate is never of benefit to miners.
• The probability of large negative buffer (that occurs some time before a certain number of rounds) can be calculated and in the case of Arsbitcoin.com, a 1000 btc negative buffer before 1700 rounds is quite likely.
• The more blocks a pool solves, the more likely it is for a an SMPPS pool to encounter so large a negative buffer that it will fail, leaving miners with much less than a PPS payout per share.

Donations help give me the time to investigate pools and write these posts. If you enjoy or find them helpful, please consider a small bitcoin donation:
12QxPHEuxDrs7mCyGSx1iVSozTwtquDB3r