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?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Very difficult.................... $\endgroup$– TofaQ3Commented Apr 30, 2021 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$– CodesInChaosCommented Apr 30, 2021 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$– kelalakaCommented Apr 30, 2021 at 19:59
-
$\begingroup$ I am expecting to see this answer a lot next week. $\endgroup$– IanMcCommented May 3, 2021 at 13:57
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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
0x0at the beginning. - We would expect about 1 in $2^8$ values to have a hash-value with
0x00at the beginning. - We would expect about 1 in $2^{12}$ values to have a hash-value with
0x000at the beginning. - We would expect about 1 in $2^{16}$ values to have a hash-value with
0x0000at 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.
answered Apr 29, 2021 at 19:53
-
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$ Commented Apr 30, 2021 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$ Commented Apr 30, 2021 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$ Commented Apr 30, 2021 at 23:30
$\begingroup$
$\endgroup$
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.
