Is that proved that for each block there is always nonce value which will make block hash to start by n count of 0

Question

Sorry for the obvious question, but I'm looking for a mathematical prove.

Block header is calculated as a concatenation of the following values.

• Version
• hashPrevBlock
• hashMerkleRoot
• timeStamp
• Bits
• Nonce (32-bit number)

First 5 parameters are static for each block. Miner only tries to find out Nonce value, such that Hash(Block_header) will start with a certain number of zeroes.

Is that proved that for each combination of Version, hashPrevBlock, hashMerkleRoot, timeStamp and Bits there is a Nonce value, that will make block hash to start with a certain number of zeroes?

If yes, can you please share any article that explains that prove?

Answer 1

Cryptographic hash functions are collision resistant and the digests produced by SHA-256 are approximately uniformly distributed. This suggests that if the input space to the hash function is magnitudes bigger than the projection space of a hash function, we would expect that every value of the projection space can be hit.

The block header is 80 bytes, and the digest space of SHA-256 is 32 byte (256 bit). Out of the 80 bytes of the block header, version is unrestricted on 29 of 32 bits, the nonce is a 4-byte arbitrary value, the Merkle root is a 256-bit digest derived from an enormous combination space, the timestamp is rather flexible—limited to a unix timestamp range of roughly 3h/10,800 seconds (~13 bits), only the previous block hash and difficulty statement are fixed. So, before counting the Merkle root, miners could generate up to 74 bits of entropy in the block header.

The Merkle root is derived from the set of transactions that a miner is choosing to include in their Bitcoin block. Not only can the miner arbitrarily pick content and order of the (valid) transactions, but also each miner is paying themselves in the coinbase transaction of their block candidate. Given that paying to different addresses results in different coinbase transactions, every miner is working on a unique transaction set whose Merkle roots making any overlap between block candidates of different miners astronomically unlikely. Further, parts of the coinbase transaction's input can be picked arbitrarily (the "extranonce" and most of the remaining 2–100 byte input script of the coinbase transaction) giving miners a way to easily add further entropy to the set of block candidates they're evaluating. Additionally, miners update their block candidate's transaction composition whenever more new transactions paying higher fee rates arrive. Even if there were no transactions to add in the block, miners could just generate a different address to pay themselves for use in the Coinbase after exhausting the nonce and extranonce space.

Given the power set of all possible transaction orders, the address space of Bitcoin, and the 100 byte input script in sum by far exceed the 32-byte digest size of SHA-256d, I'd argue that the Merkle root provides a full 32 bytes of entropy.

In sum that gives the miners ~41 bytes of arbitrary input data to produce a 32-byte digest i.e. an input space 2⁷² bigger than the projection space. Meanwhile, a block is only restricted to the current difficulty which is significantly smaller than 2²²⁴ (the difficulty of requiring a block hash 000…0).

While this doesn't meet the requirements of a rigorous mathematical proof, I'd surmise that miners do not have to worry about running out of possible block candidates. Therefore, it's just a matter of time until someone happens to succeed at creating a new valid block.

Also see this closely related question here: How can we be sure that a new block will be found?.

Answer 2

Version, hashPrevBlock, Bits (a representation of the current difficulty) are static for the current block, the timeStamp is a unix representation of the current time, the miner can change it to change the blockheader too (untill 2 hours in the future)