When a verifier asks whether data belongs to a committed set, a Merkle proof supplies the neighboring tree hashes needed to verify that the leaf reaches the known root hash. section 14.2.3
A Merkle proof is used as follows:
- Hash the relevant leaf, then combine it with the supplied neighboring hashes to reconstruct the path toward the root. section 14.2.3
- Compare the reconstructed root with the committed root hash; a match shows that the leaf belongs to the tree. section 14.2.3
- In Merkle signatures, attach the one-time signature to its Merkle proof so the verifier can connect that signature to the public root. section 14.2.3
A signature with a membership proof
A Merkle signature contains a one-time signature plus the neighboring hashes for its leaf. The root hash acts as the compact public key, while the proof establishes that the signed leaf belongs to the tree. section 14.2.3
Figure 14.5 The Merkle signature scheme is a stateful hash-based algorithm that makes use of a Merkle tree to compress many OTS public keys into a smaller public key (the root hash). The larger the tree, the more signatures it can produce. Note that signatures now have the overhead of a membership proof, which is a number of neighbor nodes that allow one to verify that a signature’s associated OTS is part of the tree.
The figure shows how neighboring nodes form the membership-proof overhead around a one-time signature and lead to the compact root-hash public key. section 14.2.3
