Using Stats to Improve Mining Software

[esenminer]

It occurred to me that there might be a way to make mining software luckier. I was looking through the code of JMiner by pooler - one thing caught my attention, the search for the hash always begins at nonce 0 and goes up. I'm assuming this is true for all other miners i.e. cgminer, reaper etc...but i haven't confirmed. I thought about analysing previous nonce data in order to determine a better starting point for the nonce count. Since the blockchain is already in a database format and contains the nonce information it's pretty straightforward and quick.

For example, for the last 1000 LTC blocks, I broke the nonce into 10 groups and summed up the number of nonces in each group to get

A   102
B   115
C   89
D   99
E   98
F   87
G   113
H   99
I   107
J   91

The probability of a nonce ending up in each group is 1/10 and doesn't change but over time if the nonce were adjust so that it started near lower count groups - i.e. with the above data, the nonce could start in group F and move outwards - that over enough iterations the mining program would be more likely to find a nonce quicker?

My stats courses are a little hazy - on the one hand this seem akin to trying to guess red / black and roulette by examining the previous board - the probability is always 50/50 and independent of the previous colour. On the other hand this makes sense intuitively so maybe I've forgotten something from those courses

[kjj]

This is the gambler's fallacy.  It will approach a uniform distribution over an infinite number of trials, but not necessarily on the next trial.

[esenminer]

Agreed. Individually the next nonce has an equal chance of ending up in any of the 10 groups.

However, from the example data above, if we started the nonce in group F over the next 100 blocks wouldn't the expectation of finding the nonce be better than if we always started in group A. We don't know where the next nonce will show up but over the next 100 we know there will likely be more in Group F.

[kjj]

Agreed. Individually the next nonce has an equal chance of ending up in any of the 10 groups.

However, from the example data above, if we started the nonce in group F over the next 100 blocks wouldn't the expectation of finding the nonce be better than if we always started in group A. We don't know where the next nonce will show up but over the next 100 we know there will likely be more in Group F.

No, this is completely wrong.  That's why we call it a fallacy.    The expected distribution will be uniform, no matter what happened in the past.

[Sukrim]

That only holds if scrypt actually HAS the attributes you assume it has (e.g. uniformity). It might be that scrypt mining actually results in a skewed set of hashes/nonces, so in that case it might be smarter to start in group B, then do group G and so on.

A sample of 1000 nonces might be too small though, it would be interesting to see the distribution along the whole LTC chain so far.

[kjj]

That only holds if scrypt actually HAS the attributes you assume it has (e.g. uniformity). It might be that scrypt mining actually results in a skewed set of hashes/nonces, so in that case it might be smarter to start in group B, then do group G and so on.

A sample of 1000 nonces might be too small though, it would be interesting to see the distribution along the whole LTC chain so far.

If you find any serious deviation from uniformity in SHA or scrypt, we all have some big problems.  And I don't mean bitcoin, I mean the entire world.  See here for a little bit on testing non-cryptographic hash functions.  The crude tests described should be taken as "step 0" when looking at cryptographic hashes.  Anything that performs poorly on them isn't worth the effort of explaining to the author why you aren't going to do a serious analysis of his pet function.  Note that you've probably never heard of any of these algorithms, with the possible exception of spooky.

Also, this is the inverse of the idea in the original post.  If there is an actual bias in the hashing function (and we hope there is not), then you can use that bias to make your mining more efficient.  Of course, if everyone does it, then difficulty just ends up somewhat higher than it "should" be.

[esenminer]

That only holds if scrypt actually HAS the attributes you assume it has (e.g. uniformity). It might be that scrypt mining actually results in a skewed set of hashes/nonces, so in that case it might be smarter to start in group B, then do group G and so on.

A sample of 1000 nonces might be too small though, it would be interesting to see the distribution along the whole LTC chain so far.

If you find any serious deviation from uniformity in SHA or scrypt, we all have some big problems.  And I don't mean bitcoin, I mean the entire world.  See here for a little bit on testing non-cryptographic hash functions.  The crude tests described should be taken as "step 0" when looking at cryptographic hashes.  Anything that performs poorly on them isn't worth the effort of explaining to the author why you aren't going to do a serious analysis of his pet function.  Note that you've probably never heard of any of these algorithms, with the possible exception of spooky.

Also, this is the inverse of the idea in the original post.  If there is an actual bias in the hashing function (and we hope there is not), then you can use that bias to make your mining more efficient.  Of course, if everyone does it, then difficulty just ends up somewhat higher than it "should" be.

An analysis of the whole chain would probably require regularizing the data per difficulty since the range of nonces would shift as difficulty moves up an down - might be interesting unless it's very uniform....

The linked article is very interesting - maybe worthwhile to do a chi-squared test on scrypt - i don't think it's completely uniform since it uses HMAC SHA256 and SHA256 has been show to have collisions.

In any case probably time for me to dust of those stats books