What if a block can NEVER be found?

[crowning]

Disclaimer: I'm a complete crypto-currency noob, and besides doing some alt-coin mining for 3 months now I never had the slightest idea what's behind all this.

Not until I've read Satoshi's whitepaper last week.

After letting it settle for some days, and a closer look into the algorithm and source code, I think I might have found a problem which _could_ have serious implications.

I barely scrapped the surface of this all, so if you think I'm wrong either because I'm just dumb or lacking some knowledge feel free to say so, and preferably point me to additional information/papers for further reading.
Most probably someone else has already pointed this out years ago and I just could not find that information.


Anyway, from what I have read a block header is the hash of the version, previous block, Merkle root, time stamp, difficulty (short VPMTD+N because I don't want to write this again   ) and a variable nonce chosen in a way that the resulting hash has the needed number of leading zero bits to fulfill the difficulty criterion.

Since VPMTD is fixed for a given block and SHA256 is a deterministic function the number of possible hashes is finite because the number of nonces is finite (uint32_t possibilities), in other words not all _possible_ hashes exist, just a finite subset.

Therefore it _could_ be that for this given finite set of inputs there is no hash which has the required number of leading zero bits.

VERY improbable, but not impossible.

In this case there would be no next block and the complete block-chain would come to a halt.
So would Bitcoin and a multimillion crypto economy.

Or is (what I would do) there already some heuristic which detects an unusual long block-time (e.g. longer than the difficulty re-target time) and changes the input (if I remember correctly there are some padding bits which could be abused for this, or just change the difficulty which is also part of the hash) to prevent this?

Or am I just the next noob who asks this dumb question?

A curious mind....

[1715659716]

1715659716

[1715659716]

1715659716

[1715659716]

1715659716

[1715659716]

1715659716

[1715659716]

1715659716

[danneu]

There are more variable fields than just `nonce`.

timestamp, "extra"-nonces, and the selected combination of transactions in the block are also variable.

[telepatheic]

The Merkle root can be changed by changing which transactions are included in the block and by changing the coinbase transaction. There is enough variability to make it infinitesimally small that a block can't be found.

Some people are proposing to make the nonce 8 bytes (64 bits) long so that miners don't have to fiddle about with the transactions.

[DannyHamilton]

The Merkle root can be changed by changing which transactions are included in the block and by changing the coinbase transaction.
- snip -

This is the main reason that a block will always be found.  The miner (or mining pool) is allowed to choose which transactions the include in the block. By changing the choice of transactions in the block, or the order of those transactions, there will always be enough variation for a valid block to be found.

[jonald_fyookball]

What happens to the leftover transactions not included in the block?

[Evil-Knievel]

This message was too old and has been purged

[jonald_fyookball]

yes , but how?

Are they stored in a temporary bucket?

The reason I ask is because I'm interested
in understanding the possibilities to make
transaction inclusion more likely in case
the network was ever attacked.

[DannyHamilton]

yes , but how?

Are they stored in a temporary bucket?

The reason I ask is because I'm interested
in understanding the possibilities to make
transaction inclusion more likely in case
the network was ever attacked.

Each solo miner (or mining pool) keeps track of the transactions that have been relayed to them, and chooses which of those transactions they include in the block they are working on.  They can run the reference software which can automate much of tracking and decision making, or they can write their own software that implements any tracking, relaying, broadcasting, and selecting rules they like.  As long as they don't break any of the protocol rules, their blocks will be as valid as anyone else's.

[crowning]

The Merkle root can be changed by changing which transactions are included in the block and by changing the coinbase transaction.
- snip -

This is the main reason that a block will always be found.  The miner (or mining pool) is allowed to choose which transactions the include in the block. By changing the choice of transactions in the block, or the order of those transactions, there will always be enough variation for a valid block to be found.

Ah, I remember reading somewhere that pools prefer to pick transactions with fees, so this is possible.
Thanks for this information.

But is this actually done? Especially done when, for a too long time, no block was found?

Of course this reduces the possibility of such a block even more, but as long as the possibility is not zero I personally would still worry about this.

[DannyHamilton]

But is this actually done? Especially done when, for a too long time, no block was found?

As you stated:

- snip -
the number of nonces is finite (uint32_t possibilities)
- snip -

uint_32 can hold about 4.3 * 10⁹ possible values.

Meanwhile, the entire network is generating 57.6 * 10¹⁵ possible block solutions every second.  Clearly the transaction selection and transaction order is not the same for all those blocks.

Of course this reduces the possibility of such a block even more, but as long as the possibility is not zero I personally would still worry about this.

The number of variations that exist in coinbase transaction values multiplied by the number of transaction ordering possibilities results in plenty of possible blocks.  You don't need to worry about this.  If you feel a need to be worried about something, there are far more dangerous things that can happen that are far more likely to happen.

[crowning]

You don't need to worry about this.  If you feel a need to be worried about something, there are far more dangerous things that can happen that are far more likely to happen.

That's a very valid point.

Thanks a lot guys and girls for all the information. You rule 

[valiron]

Disclaimer: I'm a complete crypto-currency noob, and besides doing some alt-coin mining for 3 months now I never had the slightest idea what's behind all this.

Not until I've read Satoshi's whitepaper last week.

After letting it settle for some days, and a closer look into the algorithm and source code, I think I might have found a problem which _could_ have serious implications.

I barely scrapped the surface of this all, so if you think I'm wrong either because I'm just dumb or lacking some knowledge feel free to say so, and preferably point me to additional information/papers for further reading.
Most probably someone else has already pointed this out years ago and I just could not find that information.


Anyway, from what I have read a block header is the hash of the version, previous block, Merkle root, time stamp, difficulty (short VPMTD+N because I don't want to write this again   ) and a variable nonce chosen in a way that the resulting hash has the needed number of leading zero bits to fulfill the difficulty criterion.

Since VPMTD is fixed for a given block and SHA256 is a deterministic function the number of possible hashes is finite because the number of nonces is finite (uint32_t possibilities), in other words not all _possible_ hashes exist, just a finite subset.

Therefore it _could_ be that for this given finite set of inputs there is no hash which has the required number of leading zero bits.

VERY improbable, but not impossible.

In this case there would be no next block and the complete block-chain would come to a halt.
So would Bitcoin and a multimillion crypto economy.

Or is (what I would do) there already some heuristic which detects an unusual long block-time (e.g. longer than the difficulty re-target time) and changes the input (if I remember correctly there are some padding bits which could be abused for this, or just change the difficulty which is also part of the hash) to prevent this?

Or am I just the next noob who asks this dumb question?

A curious mind....

Your objection is legit.

As far as I know, no one has proved that some hash with many leading zeros are in the image of SHA256^2 (square in the sense of composition) (that is actually used for hashing).

For example, I don't think it is known that 0000....000  (all zeros) is in the image of  SHA256^2

Nevertheless, the hashes are at first approximation evenly distributed, so you can evaluate the microscopic probability that this happens for "normal" complexities.

[jonald_fyookball]

yes , but how?

Are they stored in a temporary bucket?

The reason I ask is because I'm interested
in understanding the possibilities to make
transaction inclusion more likely in case
the network was ever attacked.

Each solo miner (or mining pool) keeps track of the transactions that have been relayed to them, and chooses which of those transactions they include in the block they are working on.  They can run the reference software which can automate much of tracking and decision making, or they can write their own software that implements any tracking, relaying, broadcasting, and selecting rules they like.  As long as they don't break any of the protocol rules, their blocks will be as valid as anyone else's.

How does the transaction go back to the original sender if no miner picks it up and puts it in a block ?

[cp1]

How does the transaction go back to the original sender if no miner picks it up and puts it in a block ?

If it's not included in a block it's technically never been sent.  But miners will refuse to allow those coins to attempt to be spent again because they're in the queue for block inclusion.  Your best hope is that eventually the miners will flush your failed transaction after a few days that it hasn't been included in a block.