Histograms of all valid nonces & hashes values

Geremia

sr. member

Activity: 507

Merit: 253

Quote from: picolo on March 14, 2015, 08:05:22 PM

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 ?

They show nonces are evenly distributed (i.e., equally likely).

picolo

hero member

Activity: 1022

Merit: 500

Quote from: Geremia on March 11, 2015, 03:53:41 PM

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 ?

DeathAndTaxes

donator

Activity: 1218

Merit: 1079

Gerald Davis

Quote from: Geremia on March 14, 2015, 10:19:03 AM

Quote from: Cryddit on March 14, 2015, 01:02:19 AM

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.

Cryddit

legendary

Activity: 924

Merit: 1132

Quote from: 2**256-2**32 on March 14, 2015, 08:40:35 AM

Quote from: Cryddit on March 14, 2015, 01:02:19 AM

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.

Geremia

sr. member

Activity: 507

Merit: 253

Quote from: Cryddit on March 14, 2015, 01:02:19 AM

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.

2**256-2**32

newbie

Activity: 2

Merit: 0

Quote from: Cryddit on March 14, 2015, 01:02:19 AM

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.

Cryddit

legendary

Activity: 924

Merit: 1132

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.

laurentmt

sr. member

Activity: 384

Merit: 258

Good work Geremia !

Quote from: Geremia on March 11, 2015, 03:53:41 PM

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

Quote from: Geremia on March 11, 2015, 03:53:41 PM

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.

Geremia

sr. member

Activity: 507

Merit: 253

Quote from: cr1776 on March 11, 2015, 07:10:08 PM

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 -1 and working down or checking randomly between 0 and .

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.

Geremia

sr. member

Activity: 507

Merit: 253

Quote from: Geremia on March 13, 2015, 03:20:17 PM

Quote from: spin on March 13, 2015, 03:08:14 AM

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

sr. member

Activity: 507

Merit: 253

Quote from: spin on March 13, 2015, 03:08:14 AM

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.

laurentmt

sr. member

Activity: 384

Merit: 258

Quote from: spin on March 13, 2015, 03:08:14 AM

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.

spin

sr. member

Activity: 362

Merit: 262

Quote from: Geremia on March 11, 2015, 04:58:27 PM

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.

Geremia

sr. member

Activity: 507

Merit: 253

Quote from: cr1776 on March 11, 2015, 09:03:51 PM

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

yes, indeed

cr1776

legendary

Activity: 4228

Merit: 1313

Quote from: Geremia on March 11, 2015, 07:45:54 PM

Quote from: cr1776 on March 11, 2015, 07:10:08 PM

Quote from: Geremia on March 11, 2015, 06:56:38 PM

Quote from: gmaxwell on March 11, 2015, 06:32:09 PM

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 -1 and working down or checking randomly between 0 and .

That makes sense.
thanks for the clarification

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

Geremia

sr. member

Activity: 507

Merit: 253

Quote from: cr1776 on March 11, 2015, 07:10:08 PM

Quote from: Geremia on March 11, 2015, 06:56:38 PM

Quote from: gmaxwell on March 11, 2015, 06:32:09 PM

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 -1 and working down or checking randomly between 0 and .

That makes sense.
thanks for the clarification

cr1776

legendary

Activity: 4228

Merit: 1313

Quote from: Geremia on March 11, 2015, 06:56:38 PM

Quote from: gmaxwell on March 11, 2015, 06:32:09 PM

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 -1 and working down or checking randomly between 0 and .

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

sr. member

Activity: 507

Merit: 253

Quote from: gmaxwell on March 11, 2015, 06:32:09 PM

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?

gmaxwell

staff

Activity: 4284

Merit: 8808

Quote

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

sr. member

Activity: 507

Merit: 253

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:

Topic: Histograms of all valid nonces & hashes values (Read 2643 times)