<p>Before we get to the real question we need to clear up a couple of apparent misconceptions</p>
<h2>Bitcoin never considers number of leading zeroes</h2>
<blockquote>
<p>As I understand it, proof of work requires nodes to &quot;scanning for a value that when hashed, such as with SHA-256, the hash begins with a number of zero bits&quot; ([bitcoin paper]).</p>
</blockquote>
<p>It is understandable why, after reading the famous white paper, you would think that. It is not true though. No bitcoin node actually cares about the number of leading zero bits. <strong>The test in  Satoshi Nakamoto's source code is <code>if (hash &lt;= hashTarget)</code></strong> -- Nakamoto wrote one thing in the whitepaper but wrote something different in the actual Bitcoin software.</p>
<p>Therefore the situation is this:</p>
<div class="s-table-container"><table class="s-table">
<thead>
<tr>
<th>Item</th>
<th>Binary</th>
<th>Comments / Verdict</th>
</tr>
</thead>
<tbody>
<tr>
<td>Target</td>
<td>000000001100</td>
<td>8 leading zeroes in target</td>
</tr>
<tr>
<td>Block A hash</td>
<td>000000001101</td>
<td>8 leading zeroes but FAILURE because hash &gt; target</td>
</tr>
<tr>
<td>Block B hash</td>
<td>000000001011</td>
<td>8 leading zeroes but SUCCESS because hash &lt; target</td>
</tr>
</tbody>
</table></div>
<p>Even though the block hashes have the same number of leading zeroes, one is a failure and the other a success.</p>
<h2>The test is not &quot;has a specified number of zeroes&quot;</h2>
<blockquote>
<p>Specifically, based on the 3Blue1Brown video, nodes are scanning for number such that, when it is appended to the block of transactions, the hash of the block has a specified number of zeros.</p>
</blockquote>
<p>That is doubly wrong. Even in systems based on numbers of leading zeroes,  like hashcash, I believe it is acceptable to have <strong>more than</strong> the specified number of zeroes.</p>
<hr />
<p>However the core of your question is certainly an important one.</p>
<h2>Is SHA256(SHA256(n)) surjective?</h2>
<p>No it is not.</p>
<p>according to an answer in cryptography.stackexchange.com to <a href="https://crypto.stackexchange.com/q/48946/52982">Is there a guarantee that for each possible hash y there exists a number x such that with hash function H, H(x) = y?</a></p>
<blockquote>
<p>A notable exception is double-SHA-256 (SHA256d) used in Bitcoin mining, where overwhelmingly likely there are some unreachable outputs.</p>
</blockquote>
<p>Therfore it might be possible that, for exceedingly small targets, there might be no reachable values smaller than the target</p>

CC BY-SA 4.0
2024-02-19T16:41:45.477Z
2024-04-01T10:22:31.187Z
2024-04-01T10:22:31.187Z
RedGrittyBrick
<p>The core principle behind the hash function, like SHA-256, is that it generates a seemingly random output for any given input and the output is uniformly distributed across the possible range. This means that for any given input, the chance of a particular bit being 0 or 1 is approximately 50%. Therefore, the chance of the first bit being zero is 1/2, the chance of the first two bits being zero is 1/4, the first three bits being zero is 1/8, and so on.</p>
<p>Due to these characteristics, it is statistically almost certain that a valid input exists which will generate a hash with a specific number of leading zeros. It is just a matter of trying enough inputs (or &quot;nonces&quot; in the case of ₿ mining) until you find one. This is what ₿ miners do in the proof-of-work system - they try billions of different inputs every second until they find one that generates a hash with the required number of leading zeros.</p>
<blockquote>
<p>What would happen if there was no such number?</p>
</blockquote>
<p>The ₿ network would be unable to produce a new block for the current difficulty level.</p>

CC BY-SA 4.0
2024-02-18T19:58:22.170Z
Thanks for the explanation. Can you show me (or link to) the math? (I mean, expanding on the math you already showed me.) You show that the probability of getting say 30 0 bits is 1/(2^32). That is a very low probability, weighing against what you are trying to show.
Benjamin Grange
CC BY-SA 4.0
2024-02-18T21:03:55.027Z
What you're asking about is essentially the concept of probability. It's like flipping a coin: the probability of getting heads is 1/2, but if you flip the coin enough times, you are almost certain to get heads eventually. ₿ miners are doing something similar, except instead of flipping a coin they are generating hashes, and instead of getting heads they are looking for a hash with a certain number of leading zeros.
deyw
CC BY-SA 4.0
2024-02-18T21:38:50.313Z
Right but the analogy isn't perfect because the SHA-256 algorithm isn't a perfect random coinflipper. It's actually completely deterministic.
Benjamin Grange
CC BY-SA 4.0
2024-02-19T20:17:19.277Z
well, theres a good argument to be made that any coinflippers not based on quantum measurments are themselves completely deterministic too, so the analogy laregly holds: the point is that its *not predictable without expending (a uniform amount of) energy*, not that it is literally random
hedgedandlevered
CC BY-SA 4.0
2024-02-18T18:49:58.303Z
2024-02-18T19:02:20.270Z
2024-02-18T19:02:20.270Z
deyw
<p>As I understand it, proof of work requires nodes to &quot;scanning for a value that when hashed, such as with SHA-256, the hash begins with a number of zero bits&quot; ([bitcoin paper])<a href="https://bitcoin.org/bitcoin.pdf" rel="nofollow noreferrer">1</a>.</p>
<p>Specifically, based on the <a href="https://www.youtube.com/watch?v=bBC-nXj3Ng4" rel="nofollow noreferrer">3Blue1Brown</a> video, nodes are scanning for number such that, when it is appended to the block of transactions, the hash of the block has a specified number of zeros.</p>
<p>I understand that SHA-256 and other cryptographic hash functions are supposed to be uniformly distributed, but is there any <em>guarantee</em> that it's always possible to find the desired number such that the hash begins with a certain number of zeros? What would happen if there was no such number?</p>

CC BY-SA 4.0
2024-02-18T20:12:36.563Z
Does https://bitcoin.stackexchange.com/q/22978/5406 answer your question?
Murch
CC BY-SA 4.0
2024-02-18T22:48:45.057Z
It is unfortunate that Nakamoto's whitepaper and code [disagree on this point](https://bitcoin.stackexchange.com/q/102414/13866).
RedGrittyBrick
CC BY-SA 4.0
2024-02-19T16:03:42.313Z
@Murch yes that gets into it. Especially, because it says that each miner is potentially working on a different set of transactions, that assuages my doubt a lot. I'm curious for more about SHA-256 though
Benjamin Grange
<proof-of-work><sha256>
Is it always possible to find a number whose hash starts with a certain number of zeros?
Benjamin Grange
# Is it always possible to find a number whose hash starts with a certain number of zeros?

(Asked by: username_0 on 2024-02-18)

As I understand it, proof of work requires nodes to "scanning for a value that when hashed, such as with SHA-256, the hash begins with a number of zero bits" ([bitcoin paper])[1](https://bitcoin.org/bitcoin.pdf).

Specifically, based on the [3Blue1Brown](https://www.youtube.com/watch?v=bBC-nXj3Ng4) video, nodes are scanning for number such that, when it is appended to the block of transactions, the hash of the block has a specified number of zeros.

I understand that SHA-256 and other cryptographic hash functions are supposed to be uniformly distributed, but is there any *guarantee* that it's always possible to find the desired number such that the hash begins with a certain number of zeros? What would happen if there was no such number?

**Tags:** proof-of-work, sha256

> **Comments:**
> **username_1**: Does https://bitcoin.stackexchange.com/q/22978/5406 answer your question?  
> **username_2**: It is unfortunate that Nakamoto's whitepaper and code [disagree on this point](https://bitcoin.stackexchange.com/q/102414/13866).  
> **username_0**: @username_1 yes that gets into it. Especially, because it says that each miner is potentially working on a different set of transactions, that assuages my doubt a lot. I'm curious for more about SHA-256 though  

---

## 2 answers

### Answer by username_2 on 2024-02-19. Score: 2

Before we get to the real question we need to clear up a couple of apparent misconceptions

## Bitcoin never considers number of leading zeroes

> As I understand it, proof of work requires nodes to "scanning for a value that when hashed, such as with SHA-256, the hash begins with a number of zero bits" ([bitcoin paper]).

It is understandable why, after reading the famous white paper, you would think that. It is not true though. No bitcoin node actually cares about the number of leading zero bits. **The test in Satoshi Nakamoto's source code is `if (hash <= hashTarget)`** -- Nakamoto wrote one thing in the whitepaper but wrote something different in the actual Bitcoin software.

Therefore the situation is this:

| Item | Binary | Comments / Verdict |
| --- | --- | --- |
| Target | 000000001100 | 8 leading zeroes in target |
| Block A hash | 000000001101 | 8 leading zeroes but FAILURE because hash > target |
| Block B hash | 000000001011 | 8 leading zeroes but SUCCESS because hash < target |

Even though the block hashes have the same number of leading zeroes, one is a failure and the other a success.

## The test is not "has a specified number of zeroes"

> Specifically, based on the 3Blue1Brown video, nodes are scanning for number such that, when it is appended to the block of transactions, the hash of the block has a specified number of zeros.

That is doubly wrong. Even in systems based on numbers of leading zeroes, like hashcash, I believe it is acceptable to have **more than** the specified number of zeroes.

---

However the core of your question is certainly an important one.

## Is SHA256(SHA256(n)) surjective?

No it is not.

according to an answer in cryptography.stackexchange.com to [Is there a guarantee that for each possible hash y there exists a number x such that with hash function H, H(x) = y?](https://crypto.stackexchange.com/q/48946/52982)

> A notable exception is double-SHA-256 (SHA256d) used in Bitcoin mining, where overwhelmingly likely there are some unreachable outputs.

Therfore it might be possible that, for exceedingly small targets, there might be no reachable values smaller than the target


---

### Answer by username_3 on 2024-02-18. Score: 1

The core principle behind the hash function, like SHA-256, is that it generates a seemingly random output for any given input and the output is uniformly distributed across the possible range. This means that for any given input, the chance of a particular bit being 0 or 1 is approximately 50%. Therefore, the chance of the first bit being zero is 1/2, the chance of the first two bits being zero is 1/4, the first three bits being zero is 1/8, and so on.

Due to these characteristics, it is statistically almost certain that a valid input exists which will generate a hash with a specific number of leading zeros. It is just a matter of trying enough inputs (or "nonces" in the case of ₿ mining) until you find one. This is what ₿ miners do in the proof-of-work system - they try billions of different inputs every second until they find one that generates a hash with the required number of leading zeros.

> What would happen if there was no such number?

The ₿ network would be unable to produce a new block for the current difficulty level.

> **Comments:**
> **username_0**: Thanks for the explanation. Can you show me (or link to) the math? (I mean, expanding on the math you already showed me.) You show that the probability of getting say 30 0 bits is 1/(2^32). That is a very low probability, weighing against what you are trying to show.  
> **username_3**: What you're asking about is essentially the concept of probability. It's like flipping a coin: the probability of getting heads is 1/2, but if you flip the coin enough times, you are almost certain to get heads eventually. ₿ miners are doing something similar, except instead of flipping a coin they are generating hashes, and instead of getting heads they are looking for a hash with a certain number of leading zeros.  
> **username_0**: Right but the analogy isn't perfect because the SHA-256 algorithm isn't a perfect random coinflipper. It's actually completely deterministic.  
> **username_4**: well, theres a good argument to be made that any coinflippers not based on quantum measurments are themselves completely deterministic too, so the analogy laregly holds: the point is that its *not predictable without expending (a uniform amount of) energy*, not that it is literally random  

---

