8.2 BitcoinPool: The great anomaly hunt.

0. Introduction

In the last BitcoinPool post I showed that every important parameter of the probability distribution of the number of Difficulty 1 shares per round were not included in the 95% confidence interval for the sample statistics. Further, the Anderson Darling test resulted in p < 0.0003 for the null hypothesis that BitcoinPool's shares per round / Difficulty were exponentially distributed. 

Since the statistics of the BitcoinPool data are anomalous, it is useful to attempt to identify the anomaly more clearly. Is the anomaly present:

• at all times, or only for a particular epoch of time?
• for all sized rounds, or for some particular sized rounds only?

There are other ways to hunt the anomaly - for example, are the anomalous data cyclical in nature? However I have not been able to find a simple to use and easy to explain method to do so.

The data on which this post is based is here.

2. The anomalous epoch: cumulative statistics
At the end of the last BitcoinPool post I included two charts - one of the rolling mean shares per round / Difficulty and one of the cumulative mean shares per round / Difficulty , both showing the start of a trend of the mean away from the expected and eventually exceeding the 95% confidence interval for the population mean.

Analysing the cumulative statistic quantities of a system is a method often used in industry to determine when in a timeline the statistic of interest exceeds a particular value, and has a formalised method in CUSUM. In hunting BitcoinPool shares per round anomalies, we will be looking for a point at which a change occurs leading to a statistic exceeding our predefined 95% confidence interval limit, at either the lower or upper bound. 

The population 95% confidence interval for the cumulative mean of shares per round / Difficulty is approximated by the quantile function of the gamma distribution where both the shape and rate parameter equal the number rounds over which a particular cumulative mean has occurred:

mean = quantile gamma distribution, k = n, theta = 1/n
where n = number solved rounds

 The 95% confidence interval for the cumulative median shares per round / Difficulty is also approximated by the quantile function of the gamma distribution, where the shape parameter = rounds * ln(2)^2 and the rate parameter = rounds * ln(2).

median = quantile gamma distribution, k = n*ln(2)^2, theta = 1/(n*ln(2))
where n = number solved rounds

The population 95% confidence interval for the cumulative variance was less amenable to analysis. The next few paragraphs discuss to my method of defining a probability distribution for the variance. If this does not interest you, you can safely skip the next few paragraphs.

If variance is approximately normally distributed, then chi-squared quantiles - or the gamma distribution - can be used. Mean shares per round / Difficulty is approximately an exponentially distributed variable , and cumulative  shares per round / Difficulty is approximately a gamma distributed variable as described above. These types of random variable are not normally distributed, and are not close to being normally distributed except for very large n.

The distribution of variance for shares per round / Difficulty for two rounds is a Weibull distribution; at fifty rounds the variance is distributed very close to a log-normal distribution, and as the number of rounds increases the distribution of variance approximates a log-normal distribution more closely. Further, I found no simple chi-squared or two parameter gamma distribution that adequately modelled the change in distribution of variance. The closest was a two variable gamma distribution:

variance = quantile gamma distribution, k = n*0.121, theta = 8.264/n
where n = number solved rounds 

A three parameter generalised gamma distribution can be much more flexible than the standard gamma distribution and can also approach a log-normal distribution. I used the generalised additive model for location scale and shape with the specific parameterisation as follows:

f(y|mu,sigma,nu)=theta^theta*z^theta*nu*e^(-theta*z)/(Gamma(theta)*y)

where z =(y/mu)^nu, theta = 1/(sigma^2*abs(nu)^2) for y>0, mu>0, sigma>0 and -Inf>nu>Inf. 

I chose this parameterisation since when nu=0 the distribution is log normal. I was not able to derive parameters for the distribution of the variance of an exponential distribution, however I could make some assumptions about how the parameters were likely to change (for example that nu should tend toward zero as the number of exponential variables increased) and could then optimise using generated variance quantile data as the target. I discovered that a very good match for variance quantile data by defining mu, sigma and nu as follows:

mu     = 1 - nu

sigma  = exp(1)/sqrt(number of rounds)

nu     = sigma/(number of rounds/16 + pi)

A generalised gamma distribution using these parameters is not an exact match for the generated data, it is the 0.025, 0.25, 0.5, 0.75, and 0.975 quantiles are all within 1% of the generated data for numbers of groups of variables greater than forty. Hence I have used this approximation only from BitcoinPool solved round 40 onward.

There may be a better or even an exact parametrisation for the distribution of the variance of an exponential distribution, however I could not find it. If any reader has more information on this subject please pm me on the bitcointalk.org forums or post a comment here.

Below are the cumulative statistics charts with 95% confidence intervals for the relevant population parameters as calculated above, from BitcoinPool solved round 40 and onward.

There are several points of note:

• A significant increase in the cumulative mean, median and variance of shares per round / Difficulty approximately begins at solved block 480.
• The cumulative mean of shares per round / Difficulty exceed the 95% confidence interval upper bound at approximately solved block 550.
• The cumulative median of shares per round / Difficulty exceed the 95% confidence interval upper bound at approximately solved block 800.
• The cumulative variance of shares per round / Difficulty exceed the 95% confidence interval upper bound at approximately solved block 600.
• The cumulative median and variance of shares per round / Difficulty do not vary as the cumulative mean does. This is not expected behaviour for exponentially distributed shares per round / Difficulty.

3. The anomalous epoch: moments

It appears that some significant change occurred at solved block 480. The BitcoinPool data used in this post is up to solved round 926, and includes 921 rounds (ignoring three outlier rounds and two rounds which had some missing data. Considering the first 479 and the last 447 rounds separately, I calculated the mean, median, standard deviation, skewness and kurtosis for each group:

The differences are startling. For the first 479 rounds all statistics are much closer to the expected population parameters, and all parameters are within the 95% confidence interval for the sample. Further, the standard deviation and mean are the same, as expected.

For rounds 480 to 926, none of the sample statistics are close to the population parameters, and the population parameters all exceed the 95% confidence interval for the sample. The CDF at 0.9999997 means that only three in ten million groups of 447 rounds would be expected to have the same or a greater average shares per round / Difficulty than BitcoinPool's shares per round / Difficulty for rounds 480 to 926.

4. The anomalous epoch: Quantiles and empirical cumulative distribution function
The two groups of data are clearly very different. I've repeated the QQ plot and eCDF charts below, considering the two groups separately and the results show the two groups are very different to each other.

The QQ plot for the first 479 rounds show an almost 1:1 relationship to the theoretical values, and the eCDF is very close to the CDF. The CDF is well within the 95% confidence interval for the eCDF.

The QQ plot for rounds 480 to 926 show several odd points of discontinuity. The middle 50% of rounds show a linear relationship with theoretical values; however the shares per round / D are much larger for a given quantile. The largest 25% of rounds do not have a linear relationship with the theoretically expected quantiles.

The eCDF for rounds 480 to 926 very different to the CDF; the CDF exceed the 95% confidence interval for the eCDF for the greater portion of the CDF.

Again, rounds 480 to 926 don't seem to be from the same probability distribution. Next we'll test that hypothesis and calculate a p value.

4. The anomalous epoch: The Anderson Darling K test

The Anderson Darling K test can be used here in two ways: to compare the two groups of rounds to generated exponential variables as in the last post, and then to compare the two groups to each other:

1.  Do the shares per round / Difficulty for the first 479 solved rounds belong to an exponential distribution?

Null hypothesis: BitcoinPool's shares per round / Difficulty for the first 479 solved rounds belong to an exponential distribution.

Alternative hypothesis: BitcoinPool's shares per round / Difficulty  for the first 479 solved rounds do not belong to an exponential distribution.

p = 0.47550

The null hypothesis cannot be rejected. The shares per round / Difficulty for the first 479 solved rounds appear to be exponentially distributed.

2.  Do the shares per round / Difficulty for solved rounds 480 to 926 belong to an exponential distribution?

Null hypothesis: BitcoinPool's shares per round / Difficulty for solved rounds 480 to 926 belong to an exponential distribution.

Alternative hypothesis: BitcoinPool's shares per round / Difficulty for solved rounds 480 to 926 do not belong to an exponential distribution.

p < 1e-10

The null hypothesis can be confidently rejected with greater than 99.9999999% confidence -  BitcoinPool's shares per round / Difficulty for solved rounds 480 to 926 do not appear to belong to an exponential distribution.

Do the shares per round / Difficulty for the first 479 solved rounds belong to the same probability distribution as shares per round / Difficulty for solved rounds 480 to 926?

Null hypothesis: BitcoinPool's shares per round / Difficulty the first 479 solved rounds belong to the same probability distribution as shares per round / Difficulty for solved rounds 480 to 926.

Alternative hypothesis: BitcoinPool's shares per round / Difficulty the first 479 solved rounds do not belong to the same probability distribution as shares per round / Difficulty for solved rounds 480 to 926.

p = 0.0028

The null hypothesis can be rejected at the 99.7% confidence level- BitcoinPool's shares per round / Difficulty the first 479 solved rounds do not belong to the same probability distribution as shares per round / Difficulty for solved rounds 480 to 926.

The anomalous epoch clearly starts at round 480 and does not appear to have finished. Whatever is causing BitcoinPool's shares per round / Difficulty to be anomalous began in July 2011 and has not ended.

5. The anomalous shares per round: comparison of equiprobable shares per round / D sizes

Whether all rounds are affected in a similar manner or not is an important question. So far, given that the size of BitcoinPool's rounds are extremely unlikely to be distributed as expected, some sized rounds must be affected more than other sized rounds. This could provide some indication about the possible mechanism that is causing the  anomalous statistics.

So which sized rounds are affected the most? The QQ plot and CDF-eCDF comparison show this visually, however not clearly. To gain a clearer appreciation of which number of shares per round / D are most affected, we can use a histogram. Instead of assigning them to bins determined by size, we can instead assign different lengths of shares per round / D to equi-probable bins. This means that each bin of shares are just as likely to occur as each other - the probability of shares per round / D from 0.43 to 0.8 is the same as from 0.8 to 1.39. 

SInce each bin is just as likely to occur as each other, confidence intervals can be estimated as a Poisson probability. If there are a total of 10 bins, for the number of rounds here the expected number of blocks in each bin 46, and the Poission probability quantiles the define the upper and lower limit of the 95% confidence interval are 60 and 33 blocks per bin respectively.

I've separated the blocks into approximately equal groups for each of charting: solved blocks 1 to 463 and solved blocks 464 onwards ( ignoring the outlier and "NA" rounds ), rather than the 1 to 479 and 480 onwards as used previously to allow a clearer comparison for this particular set of charts.

The histogram for the first 479 rounds is much as expected - the number of rounds in each bin are within the 95% confidence interval, and generally close to the expected 46 per bin. 

For rounds 480 to 926, the counts vary from  each other significantly. Rounds with total submitted shares / Difficulty greater than zero but less than or equal to 0.11 and those greater than 0.36 but less than or equal to 0.51 both have lower counts than the 95% confidence interval lower bound, and the bin of rounds with total submitted shares / Difficulty greater than 2.3 has a higher count than the 95% confidence interval.


The histogram counts and the lower tail Poisson probability mass function (probability of smaller count occurring) are tabulated below. 

6. Discussion and summary.
What has the great anomaly hunt revealed? Some strange and improbable anomalies, certainly. For a start, It is extremely improbable that the statistics of rounds 480 onward are distributed as they should be. 

To answer my initial questions:

Did the anomalous rounds occur equally at all times, or only for a particular epoch of time?

• Rounds 1 to 479 have very different statistics to those from 480 onward

Did the anomalous rounds occur equally for all sized rounds, or for some particular sized rounds only?

• For rounds 480, the number of rounds having shares per round between 0 to 0.11 x D, and 0.36 to 0.51 x D are improbably small, and the number of rounds having shares per round greater than 2.3 x D are improbably many.

These facts do not really help us explain what the cause of the anomalies are. I have not been able to determine the way this could occur - either accidentally or on purpose. For example:

• Block withholding attack (see Meni Rosenfeld's "Analysis of Bitcoin Pooled Mining Reward Systems" for details): A "sabotage" attack is unlikely - the anomaly has been occurred at BitcoinPool for nearly 18 months (at the time of writing), and I find it unlikely that anyone would be able to keep up this kind "no reward" of attack for so long. Also, to what end? If I'm the first analyst to find this, it's not an obvious problem for the pool. A "lie in wait" attack might be more likely, but I'm not sure how to calculate how profitable it would be for BitcoinPool's piecemeal reward function. Certainly possible though.
• From pool op Geebus:

"The efficiency of any given miner, if not returning a share that could have potentially have had the answer to that block due to not hashing it before another entity in the bitcoin network solves a block, and long polling triggers, could change the outcome. "

 Although this might seem intuitive to some, the efficiency of an arbitrary miner cannot affect the number of shares required for the pool to solve a block. Only valid shares received by the pool are recorded; non shares that are not sent by low efficiency miners are not recorded.

• Pool operator malfeasance (someone with access to the pool server and data base): I think this is unlikely. If, for example, round with few shares are not being recorded and simply being added to the next round, then we would expect to see a spike in the next largest sized round, then a slight dip for the next largest shares per round /D bin, and slightly more than expected for the remainder of larger shares per round /D bins. The histogram shows that this is not the case. Applying some sort of function to the result of the number of shares per round (as was almost certainly the case for bitclockers.com before they became a PPS pool) would not have had such an apparently discontinuous effect on the pools shares per round / D distribution.

The most likely of the explanations that I've been able to analyse (and some I couldn't) seems to be a "lie in wait" attack. Even this is quite unlikely though - the hashrate required to make such an attack usefully profitable is quite high, and the pool's total percentage of the network is less than 0.2%.

So I'm not sure what the mechanism behind the anomalies is, or whether it's an internal or external attack, or if perhaps the shares are not being recorded properly in some strange way that targets only specific sized rounds. I am however quite confident that this is not just a period of bad luck for BitcoinPool - there are just too many extremely improbable anomalies for that to have occurred.

Until Geebus and FairUser can investigate and solve this problem, I'd avoid mining at BitcoinPool.com - the last 18 months history of the pool suggest you'll earn an average of only 80% of your expected mining reward.

Thanks to BitcoinPool.com for use of their pool statistics.

Donations help give me the time to analyse bitcoin mining related issues and write these posts. If you enjoy or find them helpful, please consider a small bitcoin donation:

12QxPHEuxDrs7mCyGSx1iVSozTwtquDB3r