# Cryptographic hash function question

Consider the following question:

Given a $$n$$-bit cryptographic hash function $$H$$, how many messages should we expect to hash before before finding a message $$x$$ such that $$H(x) < 2^{n-k}$$, for some integer $$k$$.

For me, this question does not make a lot of sense. A cryptographic hashing function has always a fixed size on the output, such as SHA1 with 160 bits. It does not really matter what $$x$$, the message to be hashed, is $$\operatorname{len}(\operatorname{SHA1}(x)) = 160\,$$bits. In this case $$\operatorname{len}(H(x)) = n$$. Because of this, it is sufficient to hash a unique, random message. Because the size of the hashed $$x$$ is always going to be $$n$$ bytes, and $$(n\text{ bytes }< 2^{n-k})$$ is always true for any positive integer $$k$$.

Please do not give the answer, if you do, hide it ! :) I just want to better understand the question.

• This is about the representation of H(x) as an integer. Take for example a 4-bit hash function. The 4 bits 1111 are the integer 15 while the 4 bits 0001 are the integer 1. Basically the k in the question is the minimal number of leading 0 in the bit representation. Commented Nov 16, 2020 at 19:54
• SHA-1 has output size of 160 bits, not 161. What is the origin of this question? Why do you need this? There is no guarantee that SHA1 output 11.......111 Commented Nov 16, 2020 at 19:54
• Model the output as unform random than it will be easy... Commented Nov 16, 2020 at 19:56
• I have the strong feeling that the question should read $2^{n-k}$ not $2^n-k$, i.e. the same as mining a block. In that case $k$ is just the number of starting zeros after all. Commented Nov 17, 2020 at 8:15

In cryptography, we often assimilate bitstrings to integers. Unless otherwise specified, that is per big-endian binary, where a bitstring $$S$$ of $$n$$ bits $$b_0,b_1,\ldots b_{n-2},b_{n-1}$$ is assimilated to integer $$s$$ with $$s=\sum_{i=0}^{n-1}b_i\,2^{n-1-i}$$

E.g. bitstring 00010001 (which is 8-bit) is assimilated to integer $$16+1=17$$. Bitstring 0000000000010001 (which is 16-bit) and bitstring 10001 (which is 5-bit) also are assimilated to integer $$17$$. Note that for some purposes like hashing, we can't assimilate these bitstrings, even though they are assimilated to the same integer.

$$H(x)<2^{n-k}$$ compares $$H(x)$$, which is a bitstring (or perhaps a bytestring for a programmer), to $$2^{n-k}$$, which is an integer (an element of $$\mathbb Z\,$$). Some kind of transformation is needed. This is a sure sign that in the question, $$H(x)<2^{n-k}$$ must be read as:

the integer assimilated to the bitsring $$H(x)$$ is less than the integer $$2^{n-k}$$.

Note: In the circumstance it's also OK to assume little-endian binary, which uses the simpler $$s=\displaystyle\sum_{i=0}^{n-1}b_i\,2^i$$, but one should first get convinced this won't change the result.

There are several things wrong with stating

the size of the hashed $$x$$ is always going to be $$n$$ bytes, and $$(n\text{ bytes }< 2^{n-k})$$ is always true for any positive integer $$k$$.

• If the question considered the size of "the size of the hashed $$x$$", it would be written $$|H(x)|<2^{n-k}$$, rather than $$H(x)<2^{n-k}$$.
• Even with the statement understood as $$|H(x)|<2^{n-k}$$, the argument given would be wrong, with a counterexample the choice of $$k=n$$.
• Cryptographers measure size of bitstrings and integers in bits (not bytes) unless otherwise stated. BTW, the bit size of non-negative integer $$s$$ is $$\bigl\lceil\log_2(s+1)\bigr\rceil$$, or equivalently the size of the smallest bitstring assimilated to $$s$$ (equivalently per big-endian or little-endian binary).
• While educative, this doesn't address the actual question of the OP. I believe, the OP wants to estimate the Bitcoin Mining probability that one can find the required hash < the current hash. Commented Nov 17, 2020 at 16:26
• @kelelaka: you are right about what the OP is trying to achieve. See the question's last line for why I don't touch this, but only what the problem means.
– fgrieu
Commented Nov 17, 2020 at 16:46
• You can help to model, at least without the modelling it is hard. Commented Nov 17, 2020 at 16:47