0
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 16 '20 at 19:54
  • 1
    $\begingroup$ 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 $\endgroup$
    – kelalaka
    Nov 16 '20 at 19:54
  • $\begingroup$ Model the output as unform random than it will be easy... $\endgroup$
    – kelalaka
    Nov 16 '20 at 19:56
  • 1
    $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Nov 17 '20 at 8:15
1
$\begingroup$

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).
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – kelalaka
    Nov 17 '20 at 16:26
  • $\begingroup$ @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. $\endgroup$
    – fgrieu
    Nov 17 '20 at 16:46
  • $\begingroup$ You can help to model, at least without the modelling it is hard. $\endgroup$
    – kelalaka
    Nov 17 '20 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy