# Is there a number of tries after which Hashcash is guaranted to be solved?

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?

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