Bitcoin Forum

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.

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

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?

Why not?

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.

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?

https://www.bitaddress.org/

Move your mouse around the screen.

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.

Yes.


No.


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

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.

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).

Ahh..makes sense.

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

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.

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).

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

???

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.

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?

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.

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.

Increment the timestamp by one second for each header?

Issue a separate work request for each thread?

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.

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

Okay - got it now.

Nice to learn something new.

Nonce is a 32 bit Unsigned Integer.

Therefore, the nonce range is 0 to 2³²

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

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.

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

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³²?

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.

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.

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.

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.

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++".

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.

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

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

Yes, nonce++ would definitely be faster than any pseudorandom algorithm, except perhaps some clever hardware implementation. But as you say, using random numbers wouldn't improve the proof of work speed.

In theory could have an infinite number of merkle trees but given the hash is a finite value eventually you would have a hash collision as the merkle tree is compressed down to a 256 bit value (merkle root hash).  So you are right there is a finite number of possible inputs (baring a protocol change).  The header is 640 bits so there are 2^640 possible inputs although not all of them would be valid under current protocol at any given point in time (i.e. timestamps >2 hours from now or a version >2 would be invalid right now although they may be valid in the future).

Ah! That explains it. Several timestamps or modifications may have to be tried if no solution was found in the 2³² combinations.

Well all the txns are distilled down to a single merkle root hash which only has 256 bits.  Originally I was thinking an infinite number of merkle trees but that doesn't matter because there is still a finite number of merkle root hashes.  Still even with nothing else 256 bit for merkle root hash + 32 bit nonce + 32 bit timestamp = 320 bits.  Still infinite or finite as you pointed out unless you some subset of the values are more likely to produce a solution it doesn't matter where you start.

And with multiple processors (multiple ASIC threads), generally multiple timestamp/merkle-root variations are being tried simultaneously.

Essentially every thread in existence across the entire bitcoin mining network is each working on its own variation of timestamp&merkle-root.  As soon as they finish their 2³² attempts, they start on a new unique timestamp&merkle-root combination.  This continues until the block is solved, at which time there is a new "previous blockhash", and the process starts over.

Several indeed: On average the network tries 16,818,461,371 modifications (each allowing 2^32 hash attempts) per block solved these days.

2³²⁰ = 2.14 X 10⁹⁶

Lets round up and call it a googol.

I don't think there can be an infinite number of merkle trees with a 1MB block size limit.
While we are the topic, why does Bitcoin use a double hash for the Merkle root?

True.

It can't be any more than 2^8,000,000 possible merkle tree variations (8 bits per byte, 1 million bytes)

Want to convert that into base 10 for me?  My calculator won't do it.

Decimal approximation: 7.5612130194946271264814592984191480373499754082086168... × 10^8428839

http://www.wolframalpha.com/input/?i=2^28%2C000%2C000 (http://www.wolframalpha.com/input/?i=2^28%2C000%2C000)

 ;D

Given that there are an estimated 10⁸⁰ particles in the known universe, and the estimated number of grains of sand that the entire known universe could hold (given average size of a grain of sand) is estimated at 10⁹⁰, and the quantity of planck volumes that would fit in the known universe is approximately 10¹⁸³, I think we've reached the point where the number of possibilities are indistinguishable from infinite.

I get this:

9.23234126681814 × 10^2408239

from here:

http://mrob.com/pub/comp/hypercalc/hypercalc-javascript.html

A large number, although finite, theoretically speaking.

Yours doesn't make sense Anders, how can 2^y > 10^y?

I typed in the wrong number. Here is the correct number:

9.2323412683466475285638791370210766478370544416421428... × 10^2408239

http://www.wolframalpha.com/input/?i=2^8%2C000%2C000 (http://www.wolframalpha.com/input/?i=2^8%2C000%2C000)

Still beyond astronomical though, lol.

I did some sloppy typing and had one extra 2 in the exponent by mistake.

Still much smaller than a googolplex,...so
not very impressive as far as "large numbers" go. hehe.

Also still wondering why Satoshi decided we should
be using double hashes in the Merkle tree.

One idea I came to think of is that perhaps the Bitcoin proof of work solutions are non-randomly distributed. Complex and even chaotic distribution, sure, or else someone would have found certain patterns by now, yet still maybe not truly randomly distributed. In that case certain number generators could produce faster results than merely incrementing the nonce. And with statistical analysis good number generators could be discovered.

Good luck.

If you can figure it out, you'll be quite wealthy.

Some of the best minds in mathematics have studied SHA-256.  I'm not aware of anyone finding any discernible pattern in the output.

And also much much unfathomably smaller than Graham's Number (http://en.wikipedia.org/wiki/Graham%27s_number).

I was thinking of a brute force test where numerous number generators with different distributions are used for finding Bitcoin nonces. Even genetic algorithms can be used where mutations of the best generators are tested in a tree-like structure.

Will probably fail to find any serious weakness in SHA-256. Here is a comment similar to yours:

"Cryptographic experts have so far failed to crack SHA256 and only a small number of defects (possible collision scenarios) have been declared which although reducing the theoretical security (of a brute force attack) do not compromise SHA256 in practical use." -- http://bitcoin.stackexchange.com/questions/17132/is-bitcoin-mining-itself-compromising-the-security-of-sha256

Anyway it would be fun to try anyway. It seems that the experts have more mathematical approaches to finding collisions etc. My approach here is more of a brute force shoot-from-the-hip millions of bullets.

I see what you saying, that having a larger nonce space would make mining more efficient.  But since mining is proof of work, I don't see how making it more efficient for everyone would change anything at all.  In fact, if searching the SHA-256 space was too efficient, we would have to switch the proof of work to something harder.  It's highly doubtful we would ever face such a problem, but my point is proof of work need not be made easier.

What it does is removes a differential advantage you'd get from using more complex miner designs that queue and pipeline work better and have more communications bandwidth to minimize latency.