Random generation for Bitcoin

[Anders]

The quality and speed of random number generation is surely important for Bitcoin such as in mining. I found a list of random generators: http://www.cacert.at/cgi-bin/rngresults

"This is a project to make statistics about all random number generators on the market." -- http://www.cacert.at/random/

[gmaxwell]

The quality and speed of random number generation is surely important for Bitcoin such as in mining. I found a list of random generators: http://www.cacert.at/cgi-bin/rngresults

"This is a project to make statistics about all random number generators on the market." -- http://www.cacert.at/random/

There is absolute no random number generation in mining. There is no performance sensitive random number generation anywhere in the bitcoin system.

[jonald_fyookball]

How do the miners choose which nonce to start with when trying to solve a block?
Surely they don't all start with "1" ?

[Anders]

The quality and speed of random number generation is surely important for Bitcoin such as in mining. I found a list of random generators: http://www.cacert.at/cgi-bin/rngresults

"This is a project to make statistics about all random number generators on the market." -- http://www.cacert.at/random/

There is absolute no random number generation in mining. There is no performance sensitive random number generation anywhere in the bitcoin system.

But isn't there usually a brute force approach to finding a hash with enough leading zeros? And that would require guessing randomly since the search space is so astronomically huge. Or are there algorithms for finding such leading zeros without using any random or pseudorandom generator?

[DannyHamilton]

How do the miners choose which nonce to start with when trying to solve a block?
Surely they don't all start with "1" ?

Why not?

[CIYAM]

My guess is that mining pools probably allocate a different starting *nonce* to each miner (but I haven't looked into it).

[gmaxwell]

My guess is that mining pools probably allocate a different starting *nonce* to each miner (but I haven't looked into it).

They all start at zero (or any other number) it doesn't matter as they're all working on work which is merkle root distinct.

[jonald_fyookball]

How do the miners choose which nonce to start with when trying to solve a block?
Surely they don't all start with "1" ?

Why not?

Because if your set of transactions chosen for the block is the same as another miner, you
will lose assuming they are bigger than you.

Oh I get what you're saying.... can be the same transactions but different sequencing
gives it different merkle root?  but then how do they choose the sequence?

[infested999]

The quality and speed of random number generation is surely important for Bitcoin such as in mining. I found a list of random generators: http://www.cacert.at/cgi-bin/rngresults

"This is a project to make statistics about all random number generators on the market." -- http://www.cacert.at/random/

There is absolute no random number generation in mining. There is no performance sensitive random number generation anywhere in the bitcoin system.

https://www.bitaddress.org/

Move your mouse around the screen.

[CIYAM]

They all start at zero (or any other number) it doesn't matter as they're all working on work which is merkle root distinct.

Wouldn't they be *repeating the same work* if they started with the same nonce?

[gmaxwell]

They all start at zero (or any other number) it doesn't matter as they're all working on work which is merkle root distinct.

Wouldn't they be *repeating the same work* if they started with the same nonce?

Absolutely not. They are working on block headers which have a different merkel root, always.  Existing mining protocols do not even have a facility to set the nonce position/range.

[DannyHamilton]

But isn't there usually a brute force approach to finding a hash with enough leading zeros?

Yes.

And that would require guessing randomly since the search space is so astronomically huge.

No.

Or are there algorithms for finding such leading zeros without using any random or pseudorandom generator?

Yes.

• Start with a nonce of 0.
• Compute sha256(sha256(header))
• Is the hash value lower than the target?
• If so, hurray, you're done.
• If not, is the nonce equal to the maximum nonce?
• If not, increment the nonce, and return to the "Compute sha256(sha256(header))" step.
• If so, modify some other part of the block (for example extranonce, or the transaction list), and return to the "Start with a nonce of 0." step

[CIYAM]

Absolutely not. They are working on block headers which have a different merkel root, always.  Existing mining protocols do not even have a facility to set the nonce position/range.

I guess I still don't understand the details of this part - is that due to them using different txs?

Perhaps you could explain that a little clearer for someone like me that doesn't quite understand it.

[gmaxwell]

I guess I still don't understand the details of this part - is that due to them using different txs?
Perhaps you could explain that a little clearer for someone like me that doesn't quite understand it.

Well one transaction in particular is always distinct: the coinbase.  Every miner will be paying their winnings to a different address.  In the case of pooling, pools usually put a worker-distinguisher in the coinbase field of coinbase transaction to keep the work of the hashers they are paying distinct.

[CIYAM]

Well one transaction in particular is always distinct: the coinbase.  Every miner will be paying their winnings to a different address.  In the case of pooling, pools usually put a worker-distinguisher in the coinbase field of coinbase transaction to keep the work of the hashers they are paying distinct.

Of course - silly that I didn't see that - 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).

[jonald_fyookball]

I guess I still don't understand the details of this part - is that due to them using different txs?
Perhaps you could explain that a little clearer for someone like me that doesn't quite understand it.

Well one transaction in particular is always distinct: the coinbase.  Every miner will be paying their winnings to a different address.  In the case of pooling, pools usually put a worker-distinguisher in the coinbase field of coinbase transaction to keep the work of the hashers they are paying distinct.

Ahh..makes sense.

And I suppose there's no reason to believe
a higher starting number than 0 would be
any more effective.

[DannyHamilton]

There are a variety of areas where data differs between different pools and/or different hashers even when they are using the same nonce.

Some of them are:

• block timestamp
• transaction inclusion
• transaction order

As gmaxwell has pointed out, even when all of these are the same, the coinbase transaction is modified to make the merkle root unique.

Think about how fast the fastest ASIC machines are, and it becomes obvious that they are running through all 4,294,967,296 (about 4 gigahash) nonce possibilities in less than a second.  Clearly the nonce isn't the main source of variation in block solving.

[DannyHamilton]

And I suppose there's no reason to believe
a higher starting number than 0 would be
any more effective.

Nope.  As a matter of fact, by skipping the lower numbers you could very well be missing a potential solution entirely (unless you rolled back around to 0 after you reached max nonce).

[Anders]

But isn't there usually a brute force approach to finding a hash with enough leading zeros?

Yes.

And that would require guessing randomly since the search space is so astronomically huge.

No.

Or are there algorithms for finding such leading zeros without using any random or pseudorandom generator?

Yes.

• Start with a nonce of 0.
• Compute sha256(sha256(header))
• Is the hash value lower than the target?
• If so, hurray, you're done.
• If not, is the nonce equal to the maximum nonce?
• If not, increment the nonce, and return to the "Compute sha256(sha256(header))" step.
• If so, modify some other part of the block (for example extranonce, or the transaction list), and return to the "Start with a nonce of 0." step

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.

[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