I was reading a blog about blockchain and wanted to know on average hot many attempts it would take to generate a hash with two zero's as prefix.
Note: two zero prefix
Each character of the SHA-256 checksum has 16 possible values: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f.
Answer in the blog:
*In order to generate a hash with a valid two zero prefix the sender will need 256 (16*16) attempts on average.*
so how did this number get computed: the way I am thinking about this is: Best Case: 1 attempt Worst Case 256 attempt Average case : (Best Case + Worst Case )/2 = 128.5.
can someone please explain ?
Thanks!
Consider reading a random number from left to right. The first number has a $\frac{1}{16}$ chance of being a zero. Independently, the second number has $\frac{1}{16}$ chance of being a zero. So we multiply these to get a probability of $\frac{1}{256}$. Letting $X$ be the number of attempts until we see a hash with two zero's at the beginning of the number, this becomes a geometric random variable with expected value $$E(X)=\frac{1}{p}=\frac{1}{\frac{1}{256}}=256$$
To see what's wrong with your answer, there are two flaws:
The worst case is $not$ $256$. The worst case isn't a finite value. The probability it takes $X$ number of trials as $X\rightarrow\infty$ approaches $0$ so the number of trials it takes until we get a "success" can be arbitrarily large.
The probability that it takes $1$ attempt and $256$ attempts are not equal.
To get it in $1$ attempt, the probability is $\frac{1}{16}\cdot\frac{1}{16}$
To get it on exactly the $256th$ attempt is $$\left(1-\left(\frac{1}{16}\cdot\frac{1}{16}\right)\right)^{255}\cdot\left(\frac{1}{16}\cdot\frac{1}{16}\right)$$
where the probability that it does not happen on a given trial is $1-\left(\frac{1}{16}\cdot\frac{1}{16}\right)$ and this needs to happen $255$ consecutive times, followed by a success with probability $\frac{1}{16}\cdot\frac{1}{16}$.
An alternate way to calculate the expected value is as follows:
$$\begin{align} E(X) &= \sum_{k=1}^{\infty} k\cdot p \cdot (1-p)^{k-1}\\\\ &= \sum_{k=1}^{\infty} k\cdot \left(\frac{1}{16}\cdot\frac{1}{16}\right) \cdot \left(1-\left(\frac{1}{16}\cdot\frac{1}{16}\right)\right)^{k-1}\\\\ &= 256 \end{align} $$