Can someone explain what are the ways to get an output of SHA-1 with first 2-bits which are zeros?

  • 14
    $\begingroup$ Interestingly, your question is more or less is the bitcoin nonce problem $\endgroup$
    – Steve Cox
    Commented Aug 4, 2020 at 14:21
  • 1
    $\begingroup$ Just bruteforce it? Or are there assumptions made on the input for the hash function? $\endgroup$
    – Cadoiz
    Commented Aug 5, 2020 at 8:58

3 Answers 3


Hash random values until you get a hash with two leading zeroes. We would expect about 1 in 4 values to have a hash-value of that form.

So let's try this:

echo hello | sha1sum
f572d396fae9206628714fb2ce00f72e94f2258f  -


echo hello1 | sha1sum
0ef562ff2d0c21358f9d289f1c908436714fc923  -

There we are, 4 leading zeroes.

  • $\begingroup$ Isn't it 1/16, rather than 1/4? $\endgroup$
    – Woodstock
    Commented Aug 4, 2020 at 17:41
  • 9
    $\begingroup$ We're talking about two leading zeroes, so it's $1/2^2=1/4$. Maybe you're confused because my example has 4 leading zeroes? That just happened to be the first one I found. (After 2 tries.) $\endgroup$
    – Maeher
    Commented Aug 4, 2020 at 17:43
  • $\begingroup$ yep! that's exactly why. Sorry :) $\endgroup$
    – Woodstock
    Commented Aug 4, 2020 at 17:44
  • 2
    $\begingroup$ @hanshenrik I have no idea what your code is doing, but given that 0x0e is 00001110 in binary, it clearly has 4 leading zeroes. I think you are either checking for trailing zeroes and/or interpreting things as little endian instead of big endian. $\endgroup$
    – Maeher
    Commented Aug 5, 2020 at 12:55
  • $\begingroup$ The following python code agrees with my shell: from hashlib import sha1 hashvalue = sha1('hello1\n'.encode('utf-8')).digest() print(format(int.from_bytes(hashvalue,'big'),'0=160b')) $\endgroup$
    – Maeher
    Commented Aug 5, 2020 at 13:05

This is an extension of Maeher's answer and the full code of this answer is in Github.

Hash functions are expected to produce random output random in the sense that the value of the hash is basically unpredictable without actual computing. We, also, expect them to produce the hash result evenly, i.e. all possible hash values occur with the same probability. This means that we expect 1/2 of them to have a leading zero, 1/4 them has 2 leading zeroes, and so on. In a formal way; for $n$ trial we expect $n/2^i$ values have $i$-leading zero.

The below Python code experiment this (the below is optimized of the original. It is optimized on codereview at least 2x speed up )

import hashlib
import random

leading = [0] * 160

for i in range(100000):
    hashvalue = hashlib.sha1(random.getrandbits(128).to_bytes(16, 'big')).digest()
    zeroes = 160 - int.from_bytes(hashvalue, 'big').bit_length()
    leading[zeroes] = leading[zeroes] +1
for item in leading: 
    print(item, end =',')

Sample output is

1 2 3 4 5 6 7 8 9 10 49894,25040,12555,6251,3142,1523,787,392,202,111,49,21,10,10,6,2,3,0,1,0,0,1,0,0,0,0,0,...

the remaining all zero...

The graph of the event.

enter image description here

Note that it is possible to draw this together with $n/2^i$, however, they are so close to each other that one needs to zoom.

The below is the $\log_{1000}$ scaled $y$ axis with $10^{10} \approx 32$-bits random trials, 1K times more than above, took around 3 hours. With the result data


This time the with $n/2^i$, which is reddish. Since the event is so small compared to space, most of the values are 0 that is the reason for the drop of blue.

enter image description here

A zoom on the initial part is the below figure.

enter image description here

This tells us that how SHA-1 outputs are close to ideal. We already know that is necessary but not sufficient and the attacks on SHA-1 verifies this.

And, if you replace the SHA-1 with double SHA256 one will see the hardness of mining.

Below is the python code that searches and prints for given leading zero.

def searchAndPrint(numberOfTrials,leadingZero):
    for i in range(numberOfTrials): 
        rndValue = random.getrandbits(128).to_bytes(16, 'big')
        hashvalue = hashlib.sha1(rndValue).digest()
        if leadingZero == (160 - int.from_bytes(hashvalue, 'big').bit_length()):
            print(bin(int.from_bytes(rndValue, byteorder='big'))[2:].zfill(128), " ", bin(int.from_bytes(hashvalue, byteorder='big'))[2:].zfill(160))


Plotting part as per request;

def expectedGraphData(space,div2):    
    for idx,item in enumerate(div2) : 
        div2[idx] = space /pow(2,idx+1)

def plotTheGraph(a_list, leading,div2):
    plt.title('SHA-1 Leading Zeroes')
    plt.xlabel('Leading Zeroes')
    plt.ylabel('Count log_1000')

xAxislist = list(range(1, 161))
expectedValues   = [0] * 160


plotTheGraph(xAxislist,leadingZeros, expectedValues)

  • 6
    $\begingroup$ If ever a plot called for a log axis, it's this. $\endgroup$
    – Maeher
    Commented Aug 4, 2020 at 17:13
  • 1
    $\begingroup$ Should "9894" be "49894"? $\endgroup$
    – bmm6o
    Commented Aug 4, 2020 at 17:55
  • 1
    $\begingroup$ Your graphs say trailing zeros, but your code appears to be counting leading zeros. Did you actually count trailing for the grap, or is that a mistake? e.g. hex 7ab100 has 3 leading zero bits, 8 trailing 0 bits. $\endgroup$ Commented Aug 4, 2020 at 21:59
  • $\begingroup$ @PeterCordes thanks for the notification. A new was coming, but I need to break it now due to your notice. Anyway, faster code can run now. $\endgroup$
    – kelalaka
    Commented Aug 4, 2020 at 22:17
  • $\begingroup$ Hash functions are expected to produce random output. — better phrasing would be something like evenly/uniformly distributed. Random function would be a quite bad hash function. $\endgroup$
    – user28434
    Commented Aug 5, 2020 at 16:42

just bruteforce it; one possible way to do it in PHP would be:

... i'm not sure which way to count the bits, code to count them in both directions follows:

declare(strict_types = 1);

$bit1_flag = 1 << 7;
$bit2_flag = 1 << 6;
// (and i know the fugly for loop should be a do{}while() instead, anyone feel free to fix it, idc)
for ($i = 0; $i < PHP_INT_MAX; ++ $i) {
    $str = (string) $i;
    $hash = hash("sha1", $str, true);
    $ord = ord($hash[0]);
    if (($ord & $bit1_flag) || ($ord & $bit2_flag)) {

function strtobits(string $str): string
    $ret = "";
    for ($i = 0; $i < strlen($str); ++ $i) {
        $ord = ord($str[$i]);
        for ($bitnum = 7; $bitnum >= 0; -- $bitnum) {
            if ($ord & (1 << $bitnum)) {
                $ret .= "1";
            } else {
                $ret .= "0";
    return $ret;
var_dump($str, strtobits($hash), bin2hex($hash));

which prints

string(1) "1"
string(160) "0011010101101010000110010010101101111001000100111011000001001100010101000101011101001101000110001100001010001101010001101110011000111001010101000010100010101011"
string(40) "356a192b7913b04c54574d18c28d46e6395428ab"

it seems SHA1("1") starts with 2x zero bits

-OR- alternative code counting bits in the other direction...:


    $bit1_flag= 1 << 0;
    $bit2_flag= 1 << 1;
    // (and i know the fugly for loop should be a do{}while() instead, anyone feel free to fix it, idc)
        if(($ord & $bit1_flag) || ($ord & $bit2_flag)){

    function strtobits(string $str):string{
                if($ord & (1<<$bitnum)){
        return $ret;

which prints

string(1) "5"
string(160) "0011010100101100000111100110101101011001001111001000000101011111010001100110011111110000001110100110110001101001011010000101101001110010011110100101011000100011"
string(40) "ac3478d69a3c81fa62e60f5c3696165a4e5e6ac4"

it seems sha1("5") starts with 2x zero bits

  • $\begingroup$ The order of bits you're using is rather odd. You're using big-endian byte order, but little endian bit-order if I'm reading this correctly. With big-endian we have 0xac = b'10101100 with no leading zeroes. $\endgroup$
    – Maeher
    Commented Aug 5, 2020 at 13:02
  • $\begingroup$ @Maeher hmm interesting, what about 3v4l.org/uqPru ? $\endgroup$
    – hanshenrik
    Commented Aug 5, 2020 at 13:43
  • $\begingroup$ That seems to agree with my code. (At the end of the day it doesn't really matter which bits you interpret as "first" bits. If there were any significant bias in one of the bits, we would know about it.) $\endgroup$
    – Maeher
    Commented Aug 5, 2020 at 13:59
  • 2
    $\begingroup$ Python beats in the simplicity :) $\endgroup$
    – kelalaka
    Commented Aug 5, 2020 at 18:09

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.