Given an Input string of N bytes where some bytes positions in the string are fixed/immutable (F Bytes) and rest of the bytes positions can contain any value as we want or are configurable/variable (V = N-F Bytes).

SHA256(SHA256(N)) = H (256 bits).

Now, Given an Input string of N bytes, the values of N, F, V and the positions which can change and which can't:

How do we calculate the probability/formula that for at least 1 assignment of values in V, the calculated H has k leading bytes as 0?

For eg: For a random input string of size N, N=80, F=40, V=40 (assuming the position information is also given) how do we know/calculate the probability that for at least 1 assignment of values in V first k bytes of H are 0?

I tried searching for some analysis on this but couldn't find any answer. Can someone please help?


The analysis is provided by the Left Over Hash lemma.

Positions of F are irrelevant. That's just called a bit fixing entropy source, and the extractor function completely subsumes F. So $P(H_k=0)$ is as if the output was random, but biased:-

$$P(H_k=0) = \big(\frac{1}{2}- \epsilon \big)^k$$

where $\epsilon$ is the bias. Just plug the numbers into $ \epsilon = 2^{-(sn-k)/2}$, to get $P(H_k=0) =\big(\frac{1}{2}- 2^{-32} \big)^k$. NIST would not consider this source as perfectly random.

Is this a cryptocurrency question?

  • $\begingroup$ Thanks a lot. Firstly yes its a cryptocurrency question and I don't have much theoritical background in crypto. When you say $P(H_k=0)$ I interpret it as probability that first $k$ bytes are 0 in $H$. but in my humble opinion that isn't the question. If $V$ is 1 byte for $N$=80 the probability $P(H_k=0)$ w.r.t. $V=N$ bytes in input the probability $P(H_k=0)$ would be different since potential allowed input range changes dramatically. That probabilty depedence on $V$ for a input of size $N$ (very specifically V=40, N=80) and in general too is the value I was asking about? $\endgroup$
    – J.Doe
    Aug 21 at 15:13
  • $\begingroup$ Am I missing something? $\endgroup$
    – J.Doe
    Aug 21 at 15:27
  • $\begingroup$ No, you have it exactly :-) This concept isn't tied to crypt£. It's just statistics. Forget F. The probability of a 'run' of $n$ zeros is $\frac{1}{2^n}$. But since source N is not entirely random, a bias occurs. That's the $\epsilon$ in the lemma. Read the paper. $\endgroup$
    – Paul Uszak
    Aug 21 at 17:14
  • $\begingroup$ Apologies for testing your patience. I did try to read though the paper in last half an hour or so and I simply do not have that sort of background. i understand the concept of bias (but not in here). what i was wondering was if we could have a formula for probability $P(H_k=0)$ based on how many bytes we are allowed to manipulate in $N$ (denoted by $V$). i am failing to see the variable $V$ in the eqn. you have used $s$ which i am not sure of what it represents? $\endgroup$
    – J.Doe
    Aug 21 at 17:31
  • $\begingroup$ It's not my patience. It's my sobriety. Which is going down hill rapidly. $\endgroup$
    – Paul Uszak
    Aug 21 at 17:48

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.