12

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...?

10

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: Probability of a number of occurrences varying from the expected occurrences

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?

  • What do für and sonst mean in this context? – Nick ODell Feb 19 '17 at 19:03
  • 1
    @NickODell: für = for, sonst = else. I.e. for natural numbers it's the upper formula, for negative values it's always zero. – Murch Feb 19 '17 at 23:47
4

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.

  • 3
    @Zaph: It's easy to work out the probability of getting a successful hash for bitcoin mining for a single hash attempt. That's like throwing a die and getting 1 (probability 1/6). However, the interesting part is how many times you have to throw a die to get 1 to come up at some point. You can't say for sure that you can throw a die 6 times and get a 1. You can't even say that for 10 throws, or 100 throws, or a million. For a die, the probability of throwing N times and never getting a 1 is (5/6)**N. – Greg Hewgill Mar 3 '14 at 23:11
  • 1
    @GregHewgill: While my first attempt to calculate the probabilities was much along the lines of yours, I have learned by now, that block finding is a Poisson process, and my initial attempt was wrong. I have now provided what I think to be the correct probabilities and also the formula that can be used to calculate them. – Murch Mar 4 '14 at 8:51
  • 1
    @Murch: The Bernoulli process (which I have described) and the Poisson process (which you have described) are closely related. The Poisson process models continuous time; the Bernoulli process models discrete time. Both approaches can successfully model the Bitcoin mining process. – Greg Hewgill Mar 4 '14 at 19:30

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.