How can we be sure that a new block will be found?

Question

How do we know the HASH function will produce an output that fulfills the difficulty, i.e. is below 0000...xxxx...xxx?

Is it possible that no proof will be found so that the HASH will produce that output 000...xxx...?

Answer 1

The important thing here is, that every mining pool/solo miner is working on a different input: They have different coinbase transactions and are working on different sets of transactions. Further entropy can be added by changing the nonce and extra-nonce, by adding another transaction, or by changing the order of the transactions.

While there can be block inputs that won't succeed with any nonce, the complete network traverses over so many different inputs, that at some point a valid block will be discovered.

Finding a block is a Poisson process

Due to the hashing process being implemented as a Poisson process, if the network's hashing power matches the difficulty, the expected time to find the next block is exactly 10 minutes at every point of time.

The probability of a number of X blocks to be found in a time frame in which you would expect to find λ blocks can be calculated with the following formula:

So, in order to calculate the likelihood of an interval between blocks to be longer than the mean (10 minutes in an ideal world) by a factor λ we get p(0|λ) = exp(-λ)*(λ^0)/(0!) = exp(-λ)*1/1 = exp(-λ), e.g. the likelihood for a block interval to be

• more than 10 minutes is 36.8%
• more than 20 minutes is 13.5%
• more than 30 minutes is 5.0%
• more than 1 hour is 0.25%
• more than 2 hours is 0.0006%
• more than a day is 2.89*exp(-63)

While it is not impossible that longer times occur, it is extremely unlikely to happen.

Additional random bits I stumbled upon while researching for this question

In the last two years, the seven day average block confirmation time has never been over 15 minutes. See Bitcoin Average Transaction Confirmation Time

In the very early days of Bitcoin, bigger fluctuations were more common due to fluctuating mining power, see for example What is the longest time gap between blocks in 2010 - 2011?.

You can find a list of all block intervals up to Jan 2014 sorted by length here: Block intervals sorted.
The first column denominates the blocks forming the interval, the second column gives the block interval in seconds. Source: runeks on reddit: What is the longest time between blocks in the history of bitcoin?

Answer 2

We can't know for absolute certain that a block will be found. However, we can roughly compute probabilities.

The current block difficulty requires approximately 63 zero bits at the start of the hash. The probability of finding a block with one hash is approximately 2**(-63). The probability of not finding a block is (1 - 2**(-63)). The probably, therefore, of not finding a block after N hash attempts is (1 - 2**(-63))**N.

The current network hash rate is about 30,000,000 GH/s, or 3e16 H/s. In 10 minutes the network can do about 1.8e19 hashes. Using this value as N above and working out the result gives 0.14205174, which again is the probability of not finding a block after 10 minutes.

Given the above, you can extend the time and calculate some more probabilities:

No result in one hour => 0.00000821 = 8.21e-6
No result in one day => 8.96e-123

It is exceedingly unlikely that no result for a block would be found after one day.