Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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
1  
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 at 16:59

1 Answer 1

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})}.$$

Example

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

 
discard

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.