Is it possible for the network to stop finding valid blocks?

Question

The hashing problem is by design computationally hard, because SHA-256 hashes are for all intents and purposes random strings with no direct link to their inputs, and there's no (known) way to generate a block so that its hash computes to a given output (or, more exactly, satisfies the current difficult criteria). At any given difficulty level, there will only be a certain probability for miners to find a valid block.

Ok. But is there any proof that a valid block will actually exist at a given difficulty level? Is it possible that valid blocks just stop being found if difficulty increases too much? How could the network handle such a situation, if the difficulty level can only change every X blocks?

Answer 1

The simple answer: no.

The not to simple answer: extremely unlikely.

Miners hash an input block, in the hopes of getting a result that satisfies the difficulty requirement, i.e., has a certain number of zeroes in front. Now the possibilities for the miner to vary the input are quite large. There is the 4 byte nonce, there is the order transactions are put into the transaction (for simplicity let's just assume it allows all permutations of the merkle root, 2^256), there's the coinbase in the reward transaction (which also influences the merkle root), there's the timestamp (not that variable but let's say we can vary by two hours => 14 bit) and there's the transaction count (up to 4 byte, that are not independent from the merkle root, but let's assume they are indipendent). So in total we have something in the order of 2^256*2^32*2^32*2^14~=3.49E100 possible inputs to find a block and 2^256~=1.15E77 possible block hashes. (These are all back-of-the-envelope calculation, and probably wrong, but just to give an idea of the scale of this)

Hence we would find ~3.02E23 hash collisions for each hash, and would have to not find a single hash that matches the target. Notice that hash functions are built with the stated goal of making hash collisions really hard (researchers have used super computers for decades to find a single hash collision), and you'll see it is unlikely to ever occur in anyones lifetime.

Answer 2

Think of mining like the lottery where the difficulty rate is the amount of numbers in the pool and your mining rate is how many tickets you can buy. The difficulty rate is set with the idea that we want someone to win the lottery every 10 minutes. We add more numbers when they win too quickly and remove numbers when they win too slowly adjusted every 2016 blocks (approx two weeks).

To answer your question, no we will not run out of blocks. In the year 2140 give or take a few, we will have exhausted all the bitcoins, but miners will still make bitcoins via verifying transactions. If the bitcoin survives this long, then most mining will be done by large institutions tied to the bitcoin in some way who have an incentive for all transactions to be properly verified.