4

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?

  • the hashMerkleRoot is not static, as it is calculated from the set of transactions included in the block, which can vary. The miner is free to organize these however they like, with the only restriction being that the first transaction must be the coinbase. – Mark H Jun 11 at 17:24
  • The odds of any nonce producing a valid block are miniscule. The vast majority of blocks cannot be mined. Miners have to try to mine billions of blocks before they succeed in mining one. – David Schwartz Jun 12 at 17:34
  • 32 bits nonce + maybe a few bits in timestamp which you can change in hope to get a hash with 9.5 bytes of zeroes in front (19 hex-zeros) it is highly unlikely (as off June 2020 difficulty rate). Thus, you have to change your Merkle root. Just change the transactions inside the block (add, delete or rearrange or modify the coinbase tx ) – Cisco Mmu Jun 18 at 17:06
  • 1
    Part of the requirement of a secure cryptographic hash function is that the output should be unpredictable, and therefore it should not be possible to say much with certainty about what can and can't happen. It's overwhelmingly likely that every block can be mined, as explained in the answer. But if there were a mathematical proof that it's always possible, that would be an indication that SHA256 is too predictable and that we ought not to be using it. – Nate Eldredge Jun 23 at 20:24
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 272 bigger than the projection space. Meanwhile, a block is only restricted to the current difficulty which is significantly smaller than 2224 (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?.

| improve this answer | |
  • @ruben: I've added more links to my answer to address your follow-up questions. – Murch Jun 13 at 17:01
  • he is looking for math proof. Formula! I seldom seen mathematician in this group – Cisco Mmu Jun 18 at 17:11
  • I understand that, but given that the question was based on a few misunderstandings regarding the composition of block templates, it seemed more helpful to explain why the framing of the question did not necessarily fit than to provide a calculation that is not meaningful due to the odd assumptions. – Murch Jun 18 at 18:23
  • OIC! I missed that part! TQ for the clarification – Cisco Mmu Jun 19 at 3:28
  • Thank you all. Yes, @Murch, what you explained is clear, and thanks for the detailed explanation!. To sum up, we have more fields that miners can change to add more entropy. But yes, I'm still searching a clean mathematical proof, that miner can always mine a block. The last link gives some ideas, thanks. – Ruben Jun 22 at 3:53
0

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)

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.