Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hashcash is a proof-of-work system in which the Sender needs to find $Y$ such as the first (let's say 20) bits of $H(X+Y)$ are zeros where $H$ is a one-way hash function, $X$ is a fixed value and $+$ means concatenation.

The Sender starts with an initial random number $Y$. It then computes the hash of $X+Y$. If the first 20 bits of the hash are zeros, then $Y$ is an acceptable number. If not, then the sender increments the random number and tries again. Since about $1$ in $2^{20}$ headers will have $20$ zeros as the beginning of the hash, the sender will on average have to try $2^{20}$ random numbers to find a valid number.

My question is: The average number of tries is $2^{20}$ but is there a number of tries after which Hashcash is guaranted to be solved?

share|improve this question
For a good hash function, the answer is no. Now, if instead you were interested in a probabilistic guarantee (say guaranteed with probably greater than P), I think you could come up with an answer. – mikeazo May 14 '14 at 16:59

The probability of finding an acceptable number is $$Pr(\mbox{accept})=2^{-20}.$$ Thus the probability not to find an acceptable number is $$Pr(\mbox{reject})=1-Pr(\mbox{accept})=1-2^{-20}.$$ Assuming independent events, the probability not to find an acceptable number in $k$ attempts is given by $$Pr(\mbox{$k$ rejects})=(1-2^{-20})^k.$$ Thus, the probability to find at least one acceptable number in $k$ attempts is given by $$Pr(\mbox{not $k$ rejects})=1-Pr(\mbox{$k$ rejects})=1-(1-2^{-20})^k.$$

This means that if you want to find an acceptable number with a probability $P$, you chose $k$ such that $$1-(1-2^{-20})^k>P$$

$$\Leftrightarrow k>\frac{\log (1-P)}{\log(1-2^{-20})}.$$


To find an acceptable number with a probability of P=99%, you have to make $$k>\frac{\log (1-P)}{\log(1-2^{-20})}=\frac{\log (0.01)}{\log(0.9999990463256836)}\approx 4828869$$ attempts.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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