1
$\begingroup$

I have been attempting to find an answer to a self-study question:

If I have a hash algorithm that outputs 256 binary bits, on average, how many times would I have to call the hash function so that the output begins with 15 zeros?

I am absolutely lost, but bear with me here - each bit has two possible values and assuming an uniformly random output, there are $2^{256}$ (or 1.1579209e+77) possible outputs from the hash function.

So approximately, how many calls to the hash function ($H$) would be required to get an ouput value that begins with those 15 zeros? Note that I am not looking for the probability of finding such a value (although that could be useful to know as well).

$\endgroup$
4
  • $\begingroup$ Typically when I see "on average" in a question, it means "with probability > 50%". Is that what you are looking for? $\endgroup$
    – mikeazo
    Sep 26 '14 at 18:54
  • $\begingroup$ @e-sushi: I disagree that this is "opinion based"; it has a definite answer; and while the exact answer would depend on whether "on average" means the median (how long it takes to get to 50% probability), or the mean (or expected value, which is what people generally mean by 'average' in most contexts), it has a precise answer in either case. However, if you say "this is really something for the math stackexchange", well, I don't disagree with you there $\endgroup$
    – poncho
    Sep 26 '14 at 22:09
  • $\begingroup$ @poncho Fair point – agreed. Retracted the “opinion-based” close vote and flagged for migration instead. $\endgroup$
    – e-sushi
    Sep 26 '14 at 22:15
  • $\begingroup$ I mean average as in expected value - does that change the answers provided? $\endgroup$ Sep 27 '14 at 18:12
4
$\begingroup$

Assuming the output is uniformly random, the probability of any given bit being 0 is $\frac{1}{2}$. So the probability that $b_0,b_1,b_2...b_{14} = 0$ is ${(\frac{1}{2}})^{15}$.

On average, it will require $2^{15}$ calls to find a hash where the first 15 bits are 0.

$\endgroup$
0
1
$\begingroup$

The right way to approach this problem is to think of the inverse problem. I.e., given N outputs from the hash function, what is the probability that none of them have the desired number of 0's? One minus this probability is the probability that at least one will have the desired number of 0's. Once you know this, you can figure out how many outputs are needed for the desired level of certainty.

Let's simplify the problem some. Say we are interested in the first bit being 0. The remaining bits, we don't care about. Since we assume the hash function has random outputs, the probability that an output has a 1 bit in the first position is 0.5. So, the probability that out of N outputs, none have a 0 bit is the probability that all have a 1 bit, which is $0.5^N$. So, the probability that at least one has a 0 bit in the first position is $1-0.5^N$.

Your question is, what is $N$. The answer to that is, it depends. How likely do you want it that you have a $0$ bit in the first position? Increasing $N$ will never get you a probability of $1$, but you can get arbitrarily close to $1$.

Now, that was a simplified problem. We only cared about a single 0 bit. How does it extend to multiple? We know that for a random function, the probability that the first $k$ bits are all zero is $\frac{1}{2^k}$. This is because there are $2^k$ possibilities, but only one of them has all zeros. $1-\frac{1}{2^k}$ is the probability that a single output does not have all zeros.

You should now be able to plug things in and figure it out $N$ for whatever certainty level you want.

$\endgroup$
3
  • $\begingroup$ Better, but it still doesn't answer "what is the average (expected) time". Unfortunately, evaluating that precisely would appear involve evaluating an infinite sum, and while that's not that difficult with the right trick, evaluating infinite sums might not be what mcdoomington is really interested in (especially since when talking about infinite sums, you need to explain when these tricks are safe and when they are not...) $\endgroup$
    – poncho
    Sep 26 '14 at 18:20
  • $\begingroup$ I'm confused by your answer. Is the average of hash calls between 1-2^256 then? $\endgroup$ Sep 27 '14 at 18:11
  • 1
    $\begingroup$ @mcdoomington My answer shows how to set $N$ for a particular probability. I am not quite sure what you mean by expected value in this context. Could you explain? $\endgroup$
    – mikeazo
    Sep 27 '14 at 21:53

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.