3
$\begingroup$

Basically the same question as this one, except in my case the value to be hashed doesn’t have to be a valid Bitcoin block, but is a bytearray of arbitrary length and content (and that my use case is completely unrelated to Bitcoin).

In details, I have to deal with a computation that does x^ ((Integer)sha256(y)&0x7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff000), and while I know it’s impossible to have a value of bytearray y that yield the smallest possible number in order to get a computable result, I’m nevertheless still curious in knowing the smallest value of sha256 ever found…
As it’s arbitrary data, I suppose the smallest value ever found is lower than the smallest hash value of a Bitcoin block ever found. Bitcoin hashes are sha256(sha256(80 Bytes)) but in my case even 0 bytes is acceptable.

$\endgroup$
5
  • 4
    $\begingroup$ I don't think this question and its answer are useful to any of us. Why do you need to know it? What is the aim here? Besides, the nonce of the Bitcoin is already makes it almost random input... $\endgroup$
    – kelalaka
    Mar 4 at 20:54
  • 5
    $\begingroup$ @kelalaka I'm interested. $\endgroup$
    – Paul Uszak
    Mar 4 at 21:25
  • 3
    $\begingroup$ I don't think this is a question that, in the general case, is answerable. It could have occurred, just by happenstance, that the SHA-256 value used in HKDF in one of my random TLS connections was the smallest ever, and nobody would ever have recorded that fact. (And, due to forward secrecy, we'd never be able to recompute it efficiently.) In order to know this, you'd have to have recorded every hash ever produced, and we haven't. $\endgroup$
    – bk2204
    Mar 4 at 23:34
  • 2
    $\begingroup$ IMO, This question is not well-formed, because you're presuming that every hash that's ever been produced has been logged somewhere or is somehow retrievable. I've produced many hashes down in my basement with the lights off --- and until now, I haven't told a soul! Just last week, I produced the lowest possible hash. No cheating, I swear! $\endgroup$
    – jpaugh
    Mar 5 at 6:02
  • $\begingroup$ I still don't get what this is actually asking for; the recent edits seem to rule out the existing, at least somewhat generally informative answers. Yet knowing that the "current lowest" sha256 hash is 42, 0, or 4335069948445692188679829484389622911617539336091310364 tells you nothing at all, but apparently that's what is being asked for, isn't it? $\endgroup$ Mar 5 at 14:00

2 Answers 2

10
$\begingroup$

We can almost certainly say the hash corresponding to the Bitcoin block 756951 (which was mined on 2022-10-04 01:28 UTC) is the smallest SHA-256 hash that has ever been produced:

0000000000000000000000005d6f06154c8685146aa7bc3dc9843876c9cefd0f

This hash starts with an incredible 97 binary zeros. If you would like to find another hash which starts with that many zeros - you would have to calculate about 1.5845632502852868e+29 (2^97) hashes to achieve a 50% probability of finding one. That's thousands of times more than the estimated number of drops of water on earth.

Bitcoin miners are calculating many orders of magnitude more hashes then anyone else who uses SHA-256 for any purpose combined - therefore, they are the most likely ones to produce a really small hash.
Currently, all Bitcoin miners combined are calculating about 67 times more hashes than there are grains of sand on Earth, every single second.

Note: I've found this hash by writing a Rust program which downloaded the data from https://gz.blockchair.com/bitcoin/blocks/ and searched the files for the lowest hash.

$\endgroup$
13
  • 11
    $\begingroup$ Imagine if all that compute power went to something like protein folding or understanding prime numbers better! $\endgroup$
    – qwr
    Mar 5 at 4:26
  • $\begingroup$ @qwr we re talking about asics. If ypu want produce an uupgrade of twirl that can be implemented on fpgas, I m all in. $\endgroup$ Mar 5 at 5:05
  • 1
    $\begingroup$ @qwr IIRC the economics of crypto mining mean that mining power must be wasted for it to work properly. If you'd use protein folding, then people who actually need proteins folded would have an unfair advantage because they could get free bitcoins in the course of their normal work. This angers crypto-anarchists, who strongly believe that only rich investors, not biologists, should get free money. $\endgroup$
    – user253751
    Mar 6 at 15:49
  • 2
    $\begingroup$ “This hash starts with an incredible 96 binary zeros” — if this string is in base 16 and the 25-th symbol is $5_{16}=0101_2$, then it starts with $24\times4+1=97$ binary zeros. $\endgroup$ Mar 8 at 13:46
  • 1
    $\begingroup$ This is a SHA256d hash, that is the SHA-256 of a SHA-256. I agree it's extremely likely this is the smallest SHA256d ever produced. But there's no reason to rule out that an even smaller intermediary hash was computed, and immediately forgotten. Thus I'd say this very likely is the smallest SHA-256 known, and there's a nearly 50% chances this is the smallest SHA-256 ever produced. $\endgroup$
    – fgrieu
    Mar 8 at 16:17
7
$\begingroup$

TL;DR

Let's try to estimate this, based on some purported data [if someone has better data they can make the estimate better as well].

There is a claim I read somewhere, that I can't find a link to, that there were 200 quintillion SHA256 hashes computed in Bitcoin mining per second, sometime in the recent past.

If this is reasonable, then the minimum is about $2^{159}$ which is a 256 bit number with 97 leading zeroes.

Details:

If you have data about how many in other applications, in case this is not negligible compared to Bitcoin computations, you can adjust.

We model the SHA256 output as being uniformly distributed on $$ \{0,1,\ldots,M-1\} $$ where $M=2^{256}.$ Assuming independence, if you have $n$ SHA outputs $X_1,\ldots,X_n$ then the minimum $$Y=\min\{X_k:1\leq k\leq n\}$$ satisfies $$ \textrm{Prob}\{Y > y\}=\left(\frac{M-y}{M}\right)^n. $$ This means that if you want this probability to be say $2^{-k},$ then it can be computed by plugging in $M$ but you'll need to take logs and be careful.

If you're lazy and only want the expected minimum, you can find the CDF ${Prob}\{Y \leq y\},$ differentiate to get the density, and compute the expectation. See this question where this is detailed. If the distribution of the $X_i$ and $Y$ is projected on to the interval $[0,1)$ by dividing the hash output by $2^{256},$ and treating it as a real valued random variable, then the expectation is simply $\frac{1}{n+1},$ which is pleasing. Lifting back to $\{0,\ldots,M-1\}$ gives an expectation of the minimum being $$ \frac{M}{n+1}. $$ For 300 quintillion hashes per second (check my computations) I get a hashrate of $2^{67}$ per second or $2^{92}$ per year. So using a year, we get the expected minimum $Y$ to be approximately $$ \frac{2^{256}}{2^{97}}=2^{159}, $$ with 97 leading zeroes in its binary expansion.

$\endgroup$
8
  • 2
    $\begingroup$ ycharts.com/indicators/bitcoin_network_hash_rate says currently it's about 500M terahashes/sec, so 500 quintillion. So your number is the right order of magnitude. $\endgroup$
    – qwr
    Mar 5 at 4:22
  • 2
    $\begingroup$ The first order statistic over the standard uniform distribution has distribution Beta(1,n) $\endgroup$
    – qwr
    Mar 5 at 4:40
  • 2
    $\begingroup$ @kodlu Bitcoin hashes are sha256(sha256(80 Bytes)) but in my case even 0 bytes is acceptable. So does the fact 130 times less effort is Ok doesn t change anything? $\endgroup$ Mar 5 at 5:10
  • 2
    $\begingroup$ @user2284570, the output of the hash is modelled as a uniformly distributed element of $\{0,1\}^{256},$ which is independent of exactly what the input is--so no change to the argument is needed. $\endgroup$
    – kodlu
    Mar 5 at 13:03
  • 2
    $\begingroup$ @user2284570 SHA256 rfc-editor.org/rfc/rfc4634 operates on 64-byte blocks. So the minimum effort is one block. $\endgroup$
    – pjc50
    Mar 5 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.