Random generation for Bitcoin

[CIYAM]

Why would it be any faster to search through nonce values in a different order?

Agreed - but if you as the hasher had say 10 threads that could hash simultaneously wouldn't it make more sense to divide up the "nonce range" into 10?

[jonald_fyookball]

Why would it be any faster to search through nonce values in a different order?

Agreed - but if you as the hasher had say 10 threads that could hash simultaneously wouldn't it make more sense to divide up the "nonce range" into 10?

Probably not, as he mentioned, there's only about 4 billion nonces... so a single thread can handle that.
You'd have to let each thread use a different variation of the coinbase transaction.

[DannyHamilton]

Why would it be any faster to search through nonce values in a different order?

Agreed - but if you as the hasher had say 10 threads that could hash simultaneously wouldn't it make more sense to divide up the "nonce range" into 10?

Why would that be any better than giving each thread its own unique block header to work on and letting all 10 threads run through all 2³² nonces of their own respective header?

Otherwise don't you just increase your overhead as you have to resplit up the nonce range 10 times as often?

[CIYAM]

Okay - but how does each thread have its own "unique block header"?

I don't know the ins and outs of the way that mining is done so maybe I am missing something obvious here.

[Anders]

Ok, but couldn't the use of a random generator produce a correct nonce faster than the above approach? Of course, the random generator would have to be very fast to be useful.

Why would it be any faster to search through nonce values in a different order?

If the correct nonce for a solution is 1 and you search in the order:
5,8,3,9,2,4,0,3,8,2,7,4,3,9,7,0,6,1

Why would that find the solution any faster than if you searched in the order:
0,1,2,3,4,5,6,7,8,9

I was thinking that the number of possible combinations to try is so astronomically large that solutions had to be tested randomly. But ok, if the possible solutions themselves are randomly distributed then just incrementing the test is enough I guess.

[DannyHamilton]

Okay - but how does each thread have its own "unique block header"?

Increment the timestamp by one second for each header?

Issue a separate work request for each thread?

[DannyHamilton]

Ok, but couldn't the use of a random generator produce a correct nonce faster than the above approach? Of course, the random generator would have to be very fast to be useful.

Why would it be any faster to search through nonce values in a different order?

If the correct nonce for a solution is 1 and you search in the order:
5,8,3,9,2,4,0,3,8,2,7,4,3,9,7,0,6,1

Why would that find the solution any faster than if you searched in the order:
0,1,2,3,4,5,6,7,8,9

I was thinking that the number of possible combinations to try is so astronomically large that solutions had to be tested randomly. But ok, if the possible solutions themselves are randomly distributed then just incrementing the test is enough I guess.

Bitcoin's proof of work is based on the assumption that the solutions to SHA256 are randomly distributed.

If there is a discernible pattern in the solutions to SHA256, then that can be used to an advantage and it is no longer a valid proof of work.  In that case it would become necessary to hard fork and implement a new proof of work algorithm.

[jonald_fyookball]

Ok, but couldn't the use of a random generator produce a correct nonce faster than the above approach? Of course, the random generator would have to be very fast to be useful.

Why would it be any faster to search through nonce values in a different order?

If the correct nonce for a solution is 1 and you search in the order:
5,8,3,9,2,4,0,3,8,2,7,4,3,9,7,0,6,1

Why would that find the solution any faster than if you searched in the order:
0,1,2,3,4,5,6,7,8,9

I was thinking that the number of possible combinations to try is so astronomically large that solutions had to be tested randomly. But ok, if the possible solutions themselves are randomly distributed then just incrementing the test is enough I guess.

That was my assumption too.  I thought the nonce could be anything or at least 256 bits.
Ya learn somethin new everyday round here.

[CIYAM]

Increment the timestamp by one second for each header?

Issue a separate work request for each thread?

Okay - got it now.

Nice to learn something new.

[DannyHamilton]

That was my assumption too.  I thought the nonce could be anything or at least 256 bits.
Ya learn somethin new everyday round here.

Nonce is a 32 bit Unsigned Integer.

Therefore, the nonce range is 0 to 2³²

[CIYAM]

Nonce is a 32 bit Unsigned Integer.

There is a "second nonce" though isn't there (I seem to recall that)?

[gmaxwell]

Ok, but couldn't the use of a random generator produce a correct nonce faster than the above approach?

No.  It might be helpful if you explain why you think it would, since that must be predicated on some misunderstanding which we can correct, but I can't guess what it would be.

[DannyHamilton]

Nonce is a 32 bit Unsigned Integer.

There is a "second nonce" though isn't there (I seem to recall that)?

I think the name you're looking for is "extraNonce".

That's a fancy name for using the input of the generation transaction (coinbase) to create a unique merkle root.

https://en.bitcoin.it/wiki/Transactions

Generations have a single input, and this input has a "coinbase" parameter instead of a scriptSig. The data in "coinbase" can be anything; it isn't used. Bitcoin puts the current compact-format target and the arbitrary-precision "extraNonce" number there . . . The extranonce contributes to enlarge the domain for the proof of work function. Miners can easily modify nonce (4byte), timestamp and extranonce (2 to 100bytes).

[Anders]

Ok, but couldn't the use of a random generator produce a correct nonce faster than the above approach?

No.  It might be helpful if you explain why you think it would, since that must be predicated on some misunderstanding which we can correct, but I can't guess what it would be.

Randomness is a tricky issue. Are the Bitcoin proof of work solutions truly randomly distributed in the search space? If not, then just incrementing the test may be a suboptimal solution and a random test more efficient. I'm unclear about how many possible combinations there are to test in Bitcoin. Surely there must be more than 2³²?

[DeathAndTaxes]

thanks for the clarification (now it makes sense why starting at 0 for the nonce is what you'd do - although I guess if you were running multiple threads as a hasher then you might have them each start with a different nonce).

Probably not.  Remember the nonce range is only 2^32.   A 1 GH/s chip will complete that in a matter of seconds.   A 10 GH/s chip in a matter of milliseconds.   If you have multiple chips they all are starting at a nonce of zero they are just working on different work.  In hindsight it would have been better if Satoshi had made the nonce range larger (at least 64 bit) but that is water under the bridge.   I did point out a way that the blockheader could be changed to support this.  It would require a hard fork but it could be done in a manner which is compatible with existing hardware.

Agreed - but if you as the hasher had say 10 threads that could hash simultaneously wouldn't it make more sense to divide up the "nonce range" into 10?

No.  If anything the small nonce range leads to all kinds of convoluted solutions to keep the hardware from going idle.  Most rigs cheat and increment the time value as needed to act as a pseudo nonce.  It would be better simpler if Bitcoin had a larger nonce range, splitting the nonce range would only mean hardware exhausts the nonce range faster (and thus you need more chip-controller communication to keep the chip hashing).  In the long run you are going to still need to generate the same amount of hashes.  Nothing is simpler than nonce = nonce +1 so you want to keep doing that as long as possible.

[gmaxwell]

Randomness is a tricky issue. Are the Bitcoin proof of work solutions truly randomly distributed in the search space? If not, then just incrementing the test may be a suboptimal solution and a random test more efficient.

If they are not in a meaningful sense and you determine how then you will have compromised SHA256— one of the best studied cryptographic pseudorandom functions.

I'm unclear about how many possible combinations there are to test in Bitcoin. Surely there must be more than 2³²?

Mining is not a search, it's effectively a lottery. Each attempt is independent of the others and trying one does not increase the probability of your next find being a solution because you do not enumerate a finite space. Once a miner has exhausted the nonce it changes the block content (usually by incrementing something in the coinbase field in the coinbase transaction) and continues.

[DeathAndTaxes]

Randomness is a tricky issue. Are the Bitcoin proof of work solutions truly randomly distributed in the search space? If not, then just incrementing the test may be a suboptimal solution and a random test more efficient. I'm unclear about how many possible combinations there are to test in Bitcoin. Surely there must be more than 2³²?

There is an infinite number of possible inputs.  Any inputs is equally as probable to produce the desired hash (unless SHA-256 is cryptographically weak which there is no indication it is at the current time).  Baring some cryptographic weakness it doesn't matter where you start.  The only reason to use a subset of the possible inputs would be if you know that certain some range of inputs have a higher than normal probability of producing a solution than other inputs.   If that is the case you may only hash certain inputs but even there picking randomly would be pointless.  The goal is to attempts as many solutions as possible in the shortest amount of time.   You can't think "nonce =rand.GetNext" is going to be faster than "nonce++".

[DannyHamilton]

Ok, but couldn't the use of a random generator produce a correct nonce faster than the above approach?

No.  It might be helpful if you explain why you think it would, since that must be predicated on some misunderstanding which we can correct, but I can't guess what it would be.

Randomness is a tricky issue. Are the Bitcoin proof of work solutions truly randomly distributed in the search space? If not, then just incrementing the test may be a suboptimal solution and a random test more efficient. I'm unclear about how many possible combinations there are to test in Bitcoin. Surely there must be more than 2³²?

For any given block header, there are exactly 2³² possible values to test.

If you don't find a solution withing those 2³² values, it is necessary to give up on the block you are working on and try a new block.  This can be done by modifying the timestamp or by modifying the merkle root.

There is no known mathematical analysis that indicates that using random nonce values would be any better than sequential.  If the proof of work solutions are not truly randomly distributed, then a random test would not be better.  Instead, it would be best to understand the nature of the pattern in the solutions and choose nonce values specifically based on that pattern.  Furthermore, using random values would require the additional work of checking to see if the randomly generated value has already been tried, which would increase overhead and slow down the attempts.

[jonald_fyookball]

Randomness is a tricky issue. Are the Bitcoin proof of work solutions truly randomly distributed in the search space? If not, then just incrementing the test may be a suboptimal solution and a random test more efficient. I'm unclear about how many possible combinations there are to test in Bitcoin. Surely there must be more than 2³²?

There is an infinite number of possible inputs. 

Literally infinite?  I would have thought the variables could be enumerated and each has a finite set of possible values.

[CIYAM]

This is much clearer to me now - thanks for the great input.