3

I noticed that the hash message for the tagged hash in BIP340 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).
Improve this question

1 Answer 1

Reset to default
5
  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.

  1. "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.

Improve this answer
3
  • 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
    Aug 15, 2021 at 12:27
  • 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
    Aug 15, 2021 at 12:29
  • 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
    Aug 15, 2021 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.