liveBook · Manning

Hypertree

As explained in Real-World Cryptography

A hypertree is a hierarchy of Merkle trees in which trees at one level authenticate the roots of trees at another level.

A hypertree is a tree of Merkle trees: its upper-level leaves authenticate the root hashes of lower-level trees, each containing one-time-signature keys. section 14.2.3

In XMSSMT, the structure helps balance signature capacity against signing and key-generation work:

  • Use smaller trees whose leaves authenticate the roots of other Merkle trees. section 14.2.3
  • Regenerate only the trees along the path to the one-time-signature leaf used for a message. section 14.2.3
  • Track state carefully in XMSSMT: reusing a path can reuse a one-time-signature key and enable forgery. section 14.2.3
Figure 14.6 The XMSSMT stateful hash-based signature scheme uses multiple trees to increase the amount of signatures supported by the scheme while reducing the work at key generation and signing time. Each tree is deterministically generated only when they are used in the path to the final leaf that contains the OTS used to sign a message.

A layered diagram shows how XMSSMT increases supported signatures while generating only the trees needed along the selected path. section 14.2.3

How Real-World Cryptography covers it

How deep it goes
Explains the tree-of-trees construction and selective regeneration, but stops short of implementation details.
Examples
Uses XMSSMT’s layered trees and path-specific generation as the concrete example.
What it assumes
Assumes familiarity with Merkle trees and one-time signatures rather than developing either from zero.
What you can do after
Evaluate how layered Merkle trees reduce signing work while increasing supported signatures.
How it connects
Connects Merkle trees, one-time signatures, XMSS, XMSSMT, and SPHINCS+.
Cover of Real-World Cryptography
liveBookmanning.com
Read Real-World Cryptography on liveBook Get the book at manning.com

This explainer was generated by Manning's knowledge graph from the text of Real-World Cryptography. The section links point to the parts of the book it draws on.