Merkle signature scheme

The Merkle signature scheme is a digital signature method from hash-based cryptography. It combines a one-time signature scheme, such as the Lamport signature scheme, with a Merkle tree, also called a hash tree. The signer generates 2^n one-time key pairs, hashes each public key, and builds a binary tree over those hashes so that its root serves as the single public key. To sign a message the signer uses one unused key pair and attaches the authentication path of tree nodes, which lets a verifier recompute the root. Because each key pair signs only once, the scheme can sign a limited number of messages, and its private key grows linearly with that number. Ralph Merkle developed it in the late 1970s as an alternative to signatures such as RSA and the Digital Signature Algorithm. It depends only on secure hash functions, so it is believed to resist attacks by quantum computers, and NIST approved specific variants in 2020.