1
$\begingroup$

While reading about mining in crypto currency, I found that it requires some leading bits of a hash function output to be 0. This boils down to preimage resistance of the hash function, hence done with exhaustive search.

My question, say I have an ideal hash function that gives 128 bit output and I want leading 4 bits be 0. What is the expected number of time I have to run it (with randomly chosen messages) so that I get a desired outcome?

More specifically, I am looking for a function sort of, that will give the complexity, for setting $m$ bits of an ideal hash function that returns $n$ bits as output.

$\endgroup$
4
  • 4
    $\begingroup$ Does this answer your question? SHA-512 - How difficult is it to find a hash digest beginning with at least twelve zeros? $\endgroup$
    – kelalaka
    Jun 17 at 11:32
  • $\begingroup$ @kelalaka thanks 😊 for linking. That one is more empirical, but I want some theoretical calculation $\endgroup$
    – hola
    Jun 17 at 14:23
  • 1
    $\begingroup$ We already lost when we model is as uniform random. Apart from that, the answer is already theoretical. If you are looking for the expected value, that is easy; It is Bernoulli Trials and the expected value is $p$ and the result is 1/16. The expected value for the number of independent trials to get the first success is $1/p = 16$ $\endgroup$
    – kelalaka
    Jun 17 at 14:42
  • $\begingroup$ Also note that, when we say complexity, it should be depend on the input other than it is just quantification like a cryptographic hash function expected to have $\mathcal{O}(2^n)$ pre-image security and SHA-256 has 256-bit pre-image security not $\mathcal{O}(2^{256})$ since that is constant!. $\endgroup$
    – kelalaka
    Jun 17 at 21:56
3
$\begingroup$

For a random input. Each bit has probability $\frac{1}{2}$ to be zero. Then because we suppose independence (ideal hash function implies this assumption). For each input the probability to have $4$ zeros in the leading bits is $\frac{1}{2^4}=\frac{1}{16}$.

Then after $k$ computations, because we consider each output is independent (still because it's an ideal hash function). The probability to wait exactly $i$ steps is a good output is $\frac{1}{16}\left(15/16\right)^{i-1}$. (because you have a wrong output for $(i-1)$ hashes, and then a goof one).

And the expectation of the time of computation is $\sum^{\infty}_{i=1} i\frac{1}{16}\left(15/16\right)^{i-1}= \frac{1}{16}\sum^{\infty}_{j=1} \sum^{\infty}_{i=j}\left(15/16\right)^{i-1}= \frac{1}{16}\sum^{\infty}_{j=1} \sum^{\infty}_{i=0}\left(15/16\right)^{j+i-1}$

$$=\frac{1}{16}\sum^{\infty}_{j=1} \left(15/16\right)^{j-1}\sum^{\infty}_{i=0}\left(15/16\right)^{i} $$ $$= \frac{1}{16}\sum^{\infty}_{j=1} \left(15/16\right)^{j-1}\frac{1}{1/16}$$ $$=\sum^{\infty}_{j=0} \left(15/16\right)^{j} =16$$.

Then in average you have to compute $16$ hashes to find a good one.

You can easily generalize this proof by replacing $16$ by $2^m$, and you will deduce than in average you need to compute $2^m$ hashes.

Notice that because we choose by advance the coordinates where we want to have the zeros, the total output of the hash function doesn't matter if we look the number of hashes we should compute (but it could do in time of computation of $H$).

$\endgroup$
2
  • $\begingroup$ Hmm. So you need $2^m$ random trials to expect a hash output where $m$ locations are fixed. $\endgroup$
    – hola
    Jun 17 at 14:25
  • $\begingroup$ Yes, but it's an average. $\endgroup$
    – Ievgeni
    Jun 17 at 15:16

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.