Histograms of all valid nonces & hashes values

[Geremia]

I set out to test the claim: "Every nonce has an equal chance of winning."

TIME EVOLUTION

So, I plotted, with gnuplot, the nonce values vs. hashes for all the valid blocks in the blockchain:

(Also, in the last plot, you can really visualize the change in the difficulty and even see where the difficulty was decreased.)

HISTOGRAMS

It makes sense that the nonces found are skewed toward 0 because this is a selection effect: most everyone starts searching for nonces starting at 0, so the lower nonces are found first, even though there may be also higher nonces that could produce a winning block:

Why are the hashes distributed this way, though?:

2-D histogram of hashes and nonces (logarithmic color scale):

(originally posted on Bitcoin Stackexchange)

[1715327037]

1715327037

[1715327037]

1715327037

[Geremia]

It's not unevenly distributed. The reason it appears that way in the graphs above is because the x-axis is plotted in logarithmic units. Here's what it looks like in linear units:

[gmaxwell]

I set out to test the claim: "Every nonce has an equal chance of winning."

The test that you've performed is also not a test of that claim.

Consider, assume that every nonce were equally likely to be a solution. Now also assume everyone looking starts at zero and increments.

What distribution would you expect to see after the fact? How would that distribution change as the probability of a hit changes?

[Geremia]

assume that every nonce were equally likely to be a solution.

How can I assume that, when that's what I'm seeking to prove, isn't it?

[cr1776]

assume that every nonce were equally likely to be a solution.

How can I assume that, when that's what I'm seeking to prove, isn't it?

I think part of his point was that if everyone starts looking at zero for a "winning" nonce and working up, the distribution will be towards the low end of the range since every nonce has an equal chance of being a solution.  

Consequently, your test will only show that more people are starting from zero and working up, than starting from <limit> -1 and working down or checking randomly between 0 and <limit>.


Asking you to assume that, is for the purpose of his example/question - if it is true that every nonce has an equal chance of being a solution, the pattern will be skewed by where people start searching.

[Geremia]

assume that every nonce were equally likely to be a solution.

How can I assume that, when that's what I'm seeking to prove, isn't it?

I think part of his point was that if everyone starts looking at zero for a "winning" nonce and working up, the distribution will be towards the low end of the range since every nonce has an equal chance of being a solution.  

Consequently, your test will only show that more people are starting from zero and working up, than starting from <limit> -1 and working down or checking randomly between 0 and <limit>.

That makes sense.
thanks for the clarification

[cr1776]

assume that every nonce were equally likely to be a solution.

How can I assume that, when that's what I'm seeking to prove, isn't it?

I think part of his point was that if everyone starts looking at zero for a "winning" nonce and working up, the distribution will be towards the low end of the range since every nonce has an equal chance of being a solution.  

Consequently, your test will only show that more people are starting from zero and working up, than starting from <limit> -1 and working down or checking randomly between 0 and <limit>.

That makes sense.
thanks for the clarification

It is interesting to see the distributions though, as a curiosity factor. :-)

[Geremia]

It is interesting to see the distributions though, as a curiosity factor. :-)

yes, indeed

[spin]

It's not unevenly distributed. The reason it appears that way in the graphs above is because the x-axis is plotted in logarithmic units. Here's what it looks like in linear units:

Between 64 - 66 on the hash scale you can see that on the right you have a few blank spaces.  Perhaps an indication of the bias to the lower end that gmaxwell identified.

To get a better sence of the distribution though you need to plot differently.  Perhaps using colour to denote density of values rather than block height? Or make your points smaller so they don't overlap.

[laurentmt]

To get a better sence of the distribution though you need to plot differently.  Perhaps using colour to denote density of values rather than block height? Or make your points smaller so they don't overlap.

I was thinking to something similar. May be a chart with bins defined on the y axis and colors denoting the number of blocks for (nonce, bin(hash)) could do the trick. For example, a bin could be defined for each target value. If I'm correct, we should expect to see horizontal lines with points having a "same" color.
For example, we could define bins on ranges of target values. If I'm correct, we should expect to see horizontal lines with points having a "same" color.

[Geremia]

To get a better sence of the distribution though you need to plot differently.  Perhaps using colour to denote density of values rather than block height? Or make your points smaller so they don't overlap.

Yes, a density map would be much better.

[Geremia]

To get a better sence of the distribution though you need to plot differently.  Perhaps using colour to denote density of values rather than block height? Or make your points smaller so they don't overlap.

Yes, a density map would be much better.

See the OP for the new density map I made (plus histograms).

[Geremia]

I think part of his point was that if everyone starts looking at zero for a "winning" nonce and working up, the distribution will be towards the low end of the range since every nonce has an equal chance of being a solution.  

Consequently, your test will only show that more people are starting from zero and working up, than starting from <limit> -1 and working down or checking randomly between 0 and <limit>.


Asking you to assume that, is for the purpose of his example/question - if it is true that every nonce has an equal chance of being a solution, the pattern will be skewed by where people start searching.

What you say here is excellently illustrated in the nonce histogram I put in the OP.

[laurentmt]

Good work Geremia !

Why are the hashes distributed this way, though?:

As a first hypothesis, I would say that these 3 peaks may be related to the 3 plateau appearing in difficulty and hashrate charts. But I may be wrong.


EDIT

2-D histogram of hashes and nonces (logarithmic color scale):

I was puzzled by the anomaly appearing around log(hash)=65 with this incomplete blue line. Actually, I'm almost sure it's related to a large influx of new users in July 2010 after an article in slashdot. During 3 days, the number of mined blocks was multiplied by 3 (between 600 and 700 blocks/day). I've quickly checked with a block mined on 07/12 and hash values seem to correspond.

[Cryddit]

Bitcoin headers don't really even need nonces. 

You could just set the nonce in the block header to zero, or use that field for something completely else, and do your hashing on the basis of incrementing extranonce instead of on the basis of incrementing the nonce.

We 'extended' the nonce space by embedding an "extra nonce" in the coinbase transaction, but there's no reason why that's an 'extension' rather than a 'replacement' except that incrementing it requires recomputing the merkle tree so it would be slower. 

Think about it:  The coinbase transaction is part of the block - it changes the merkle root of the transaction tree.  And we have space in the coinbase transaction currently devoted to an 'extranonce'.  Extranonces of up to 100 bytes can be used. 

[2**256-2**32]

Bitcoin headers don't really even need nonces. 

They don't, but you'd be silly not to use them. There's a very basic optimization with Bitcoin mining where you only need to hash from the midpoint of the previous attempt. You hash the first 76 bytes of the header and then store that as the 'midstate', then continue the hash with the four byte nonce and do part of the second hash to find out of it is a possible winner or not. Rather than starting over for the next nonce, you take the midstate again and continue with ++nonce. You end up doing much less than two SHA256 hashes as a result, and need to only push new work (a fresh midstate) to the chip every 4.2B attempts.

Hashing without a nonce is completely possible, but you would be at a significant disadvantage for no reason.

[Geremia]

We 'extended' the nonce space by embedding an "extra nonce" in the coinbase transaction, but there's no reason why that's an 'extension' rather than a 'replacement' except that incrementing it requires recomputing the merkle tree so it would be slower.

It's an extension because extranonce is 8 bytes, and nonce is 4 bytes.

[Cryddit]

Bitcoin headers don't really even need nonces. 

They don't, but you'd be silly not to use them. There's a very basic optimization with Bitcoin mining where you only need to hash from the midpoint of the previous attempt. You hash the first 76 bytes of the header and then store that as the 'midstate', then continue the hash with the four byte nonce and do part of the second hash to find out of it is a possible winner or not. Rather than starting over for the next nonce, you take the midstate again and continue with ++nonce. You end up doing much less than two SHA256 hashes as a result, and need to only push new work (a fresh midstate) to the chip every 4.2B attempts.

Hashing without a nonce is completely possible, but you would be at a significant disadvantage for no reason.

Heh.  It only puts you at a disadvantage if you *don't* use it and others *do*.  If it weren't there in the first place, and nobody were using it - all the hashing would still be fair, still distributed according to computing power, etc.

And the optimization is even steeper then recomputing from the midstate.  Having a nonce field in the header also saves you from having to recompute the merkle tree for every hash. 

[DeathAndTaxes]

We 'extended' the nonce space by embedding an "extra nonce" in the coinbase transaction, but there's no reason why that's an 'extension' rather than a 'replacement' except that incrementing it requires recomputing the merkle tree so it would be slower.

It's an extension because extranonce is 8 bytes, and nonce is 4 bytes.

Extranonce isn't part of the protocol and has no defined size.  It is up to the client implementation.  At one time if you had a really slow miner an extranonce of 1 byte would be sufficient.  Today you could use a random 256 bit number if you didn't want to worry about incrementing and that would be just as valid.

[picolo]

I set out to test the claim: "Every nonce has an equal chance of winning."

TIME EVOLUTION

So, I plotted, with gnuplot, the nonce values vs. hashes for all the valid blocks in the blockchain:

(Also, in the last plot, you can really visualize the change in the difficulty and even see where the difficulty was decreased.)

HISTOGRAMS

It makes sense that the nonces found are skewed toward 0 because this is a selection effect: most everyone starts searching for nonces starting at 0, so the lower nonces are found first, even though there may be also higher nonces that could produce a winning block:

Why are the hashes distributed this way, though?:

2-D histogram of hashes and nonces (logarithmic color scale):

(originally posted on Bitcoin Stackexchange)

Could you give us a conclusion to all the graphs apart that :
It makes sense that the nonces found are skewed toward 0 because this is a selection effect: most everyone starts searching for nonces starting at 0, so the lower nonces are found first, even though there may be also higher nonces that could produce a winning  ?