6
$\begingroup$

I know it's possible to find a hash value with multiple zeroes in it, I know of some BitCoin hashes with it, but how difficult is it to find/create a hash digest with 12 or more leading hex zeroes in it?

$\endgroup$
4
  • $\begingroup$ Very difficult.................... $\endgroup$
    – TofaQ3
    Apr 30 at 14:22
  • $\begingroup$ @TofaQ3 Not really. Brute forcing 48-bits takes some effort but is quite affordable. I'd estimate several months on a typical desktop CPU. $\endgroup$ Apr 30 at 16:07
  • $\begingroup$ @CodesInChaos Well, that may true if you have some GPU. The Summit with 27,648 Volta core can reach $2^{48}$ in a second. A home PC with one TeslaV100 can reach that in 18 hour. For GTX 1080 double the time.GTX 3080 is near to TeslaV100, $\endgroup$
    – kelalaka
    Apr 30 at 19:59
  • $\begingroup$ I am expecting to see this answer a lot next week. $\endgroup$
    – IanMc
    May 3 at 13:57
7
$\begingroup$

First, we need to model SHA-512 as uniform random.

Start hashing random values.

In hex we have 4-bits

  • We would expect about 1 in $2^4$ values to have a hash-value with 0x0 at the beginning.
  • We would expect about 1 in $2^8$ values to have a hash-value with 0x00 at the beginning.
  • We would expect about 1 in $2^{12}$ values to have a hash-value with 0x000 at the beginning.
  • We would expect about 1 in $2^{16}$ values to have a hash-value with 0x0000 at the beginning.
  • ...
  • We would expect about 1 in $2^{48}$ values to have a hash-value with 12 hex zeroes at the beginning.

So we can say that we expect $\dfrac{2^{512}}{2^{4\cdot k}}$ values will have leading $k$ hex zeroes.


Little experiments

For random inputs the SHA-512 hashes with leading zeroes in hex;

random sample none 1 2 3 4 5 6 7 8
1M 937670 58485 3604 225 16 0
10M 9375898 584890 36824 2231 149 8 0
100M 93752595 5856572 366283 23019 1446 75 9 1 0
1B 937501048 58591757 3663483 228262 14501 881 66 2 0

$1B \approx 2^{30.89}$ and to see 12 leading zeroes, the experiment must go to $2^{48}$ and that needs still $2^{18}$ more time. It is quite doable with a single CPU, though parallel processing is possible, too. Note that this is a Python experiment and took ~22 minutes for 1B.

For a CPU this may be hard to achieve since SHA-512, although a fast hash function, is still not a simple function to evaluate. If you have a GPU like GTX 1080 then you may reach $2^{48}$ SHA-512 hashing around 36 hours and if you have GTX 3080 then you may need 18 hours.

$\endgroup$
3
  • 1
    $\begingroup$ Nice explanation. The real bitcoin average time for miners was around 10 minutes or so... And I think this is because they are looking to hash a specific message and obtain twelve leading zeroes. So I think because they are hashing a specific message expecting 12 leading zeroes, that the probability is much lower than any hash with 12 leading zeros as you explained here. $\endgroup$ Apr 30 at 3:38
  • 1
    $\begingroup$ Just to add the probability of matching a given 48-bit string in 2^48 random permutations is 1-((2^48-1)/(2^48))^(2^48) or 63.21% $\endgroup$ Apr 30 at 8:14
  • 2
    $\begingroup$ @RomanGherta: the bitcopin mining criterion is that the hash of the block header is numerically less than a target value; this requires all leading 0 bits in the target be 0 in the hash, but constrains the remaining bits as well. The target value, and thus the number of 0 bits, varies automatically to keep the block times near 10 minutes, and today the target has leading 76 bits or 19 hexits. The last time 12 hexits or 48 bits was enough was in March 2011, just over a decade ago. $\endgroup$ Apr 30 at 23:30
4
$\begingroup$

For several years there was a competition to find the lowest possible sha512sum of some random input. The maximum number of preceding zeros was 12. Beyond the dates between the winners post of an 11 and 12 zero prefixed hash (~4 months) little is known about the actual runtime. If it helps the code is available here.

$\endgroup$

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.