<blockquote>
<ol>
<li>&quot;optimized implementations are possible&quot;: What specifically is the optimization being talked about here, is it caused by the prefix being the same size as the block size of SHA-256? If so, can this conclusion be generalised to all block hashing algorithms? i.e. the same size of the prefix and the block of the algorithm can lead to optimization.</li>
</ol>
</blockquote>
<p>Yes, it means that the SHA256 hashing state at <code>SHA256(SHA256(tag)||SHA256(tag)||</code> can be precomputed. If the tag was just 32 bytes this wouldn't work, as you'd need to know 32 bytes of data before being able to process the first block.</p>
<blockquote>
<ol start="2">
<li>&quot;Using SHA256 of the tag name itself is reasonably simple and efficient for implementations that don't choose to use the optimization.&quot;: Does this mean that if the implementation does not intend to adopt optimization, then it can not repeat the tag? i.e. the tagged hash would be SHA256( SHA256(tag) || msg).</li>
</ol>
</blockquote>
<p>No, that would give a different result. All this is saying is that it's a simple construction to concatenate the hashed tag twice. Obviously not doubling it would be even simpler, but that would forego the optimization from the previous point.</p>

CC BY-SA 4.0
2021-08-15T12:27:43.747Z
Thank you very much for your reply.

For Q1: So this optimization needs to cache the intermediate state of `SHA256(SHA256(tag) || SHA256(tag)||` locally? So in future each time the hash of the tag is computed starting from reading the cache state?

For Q2: I am very sorry for misunderstanding this statement before, now I understand that this is the reason why tagged picks SHA256 directly.
sphpmp
CC BY-SA 4.0
2021-08-15T12:29:54.897Z
Right, the state after processing the first 64 bytes can be preconputed, and thus the computation of a tagged hash can start at that point rather than needing to redo it every time.
Pieter Wuille
CC BY-SA 4.0
2021-08-15T13:34:50.823Z
So, if the length of the prefix is a multiple of the block size, the optimization still works? i.e., a direct padding to the tag and using it as a prefix. For example, prefix = (tag_size, tag, padding), I just need to make sure it is a multiple of block size. But the downside is that this would limit the length of the tag. Does it correct? I will appreciate your reply!
sphpmp
CC BY-SA 4.0
2024-09-28T20:22:47.820Z
one other thing to keep in mind in an optimized implementation of tagged hashes: SHA256 writes the number of bits into the final hashed block, this will be 512 more due to the tagging block
laanwj
CC BY-SA 4.0
2021-08-15T11:33:43.553Z
2021-08-15T11:33:43.553Z
Pieter Wuille
<p>I noticed that the hash message for the tagged hash in <a href="https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki" rel="nofollow noreferrer">BIP340</a> is prefixed with SHA256(tag) || SHA256(tag), which also describes the reason</p>
<blockquote>
<p>Because this is a 64-byte long context-specific constant and the SHA256 block size is also 64 bytes, optimized implementations are possible (identical to SHA256 itself, but with a modified initial state). Using SHA256 of the tag name itself is reasonably simple and efficient for implementations that don't choose to use the optimization.</p>
</blockquote>
<p>But I have some confusions</p>
<ol>
<li><strong>&quot;optimized implementations are possible&quot;:</strong> What specifically is the optimization being talked about here, is it caused by the prefix being the same size as the block size of SHA-256? If so, can this conclusion be generalised to all block hashing algorithms? i.e. the same size of the prefix and the block of the algorithm can lead to optimization.</li>
<li><strong>&quot;Using SHA256 of the tag name itself is reasonably simple and efficient for implementations that don't choose to use the optimization.&quot;</strong>: Does this mean that if the implementation does not intend to adopt optimization, then it can not repeat the tag? i.e. the tagged hash would be SHA256( SHA256(tag) || msg).</li>
</ol>

<hash><taproot><sha256><schnorr-signatures>
Why is the tag repeated twice in a tagged hash?
sphpmp
# Why is the tag repeated twice in a tagged hash?

(Asked by: username_0 on 2021-08-15)

I noticed that the hash message for the tagged hash in [BIP340](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki) is prefixed with SHA256(tag) || SHA256(tag), which also describes the reason

> Because this is a 64-byte long context-specific constant and the SHA256 block size is also 64 bytes, optimized implementations are possible (identical to SHA256 itself, but with a modified initial state). Using SHA256 of the tag name itself is reasonably simple and efficient for implementations that don't choose to use the optimization.

But I have some confusions

1. **"optimized implementations are possible":** What specifically is the optimization being talked about here, is it caused by the prefix being the same size as the block size of SHA-256? If so, can this conclusion be generalised to all block hashing algorithms? i.e. the same size of the prefix and the block of the algorithm can lead to optimization.
2. **"Using SHA256 of the tag name itself is reasonably simple and efficient for implementations that don't choose to use the optimization."**: Does this mean that if the implementation does not intend to adopt optimization, then it can not repeat the tag? i.e. the tagged hash would be SHA256( SHA256(tag) || msg).

**Tags:** hash, taproot, sha256, schnorr-signatures


---

## 1 answers

### Answer by username_1 on 2021-08-15. Score: 5 | Accepted answer

> 1. "optimized implementations are possible": What specifically is the optimization being talked about here, is it caused by the prefix being the same size as the block size of SHA-256? If so, can this conclusion be generalised to all block hashing algorithms? i.e. the same size of the prefix and the block of the algorithm can lead to optimization.

Yes, it means that the SHA256 hashing state at `SHA256(SHA256(tag)||SHA256(tag)||` can be precomputed. If the tag was just 32 bytes this wouldn't work, as you'd need to know 32 bytes of data before being able to process the first block.

> 2. "Using SHA256 of the tag name itself is reasonably simple and efficient for implementations that don't choose to use the optimization.": Does this mean that if the implementation does not intend to adopt optimization, then it can not repeat the tag? i.e. the tagged hash would be SHA256( SHA256(tag) || msg).

No, that would give a different result. All this is saying is that it's a simple construction to concatenate the hashed tag twice. Obviously not doubling it would be even simpler, but that would forego the optimization from the previous point.

> **Comments:**
> **username_0**: Thank you very much for your reply.  For Q1: So this optimization needs to cache the intermediate state of `SHA256(SHA256(tag) || SHA256(tag)||` locally? So in future each time the hash of the tag is computed starting from reading the cache state?  For Q2: I am very sorry for misunderstanding this statement before, now I understand that this is the reason why tagged picks SHA256 directly.  
> **username_1**: Right, the state after processing the first 64 bytes can be preconputed, and thus the computation of a tagged hash can start at that point rather than needing to redo it every time.  
> **username_0**: So, if the length of the prefix is a multiple of the block size, the optimization still works? i.e., a direct padding to the tag and using it as a prefix. For example, prefix = (tag_size, tag, padding), I just need to make sure it is a multiple of block size. But the downside is that this would limit the length of the tag. Does it correct? I will appreciate your reply!  
> **username_2**: one other thing to keep in mind in an optimized implementation of tagged hashes: SHA256 writes the number of bits into the final hashed block, this will be 512 more due to the tagging block  

---

