# Post-Quantum Digital Signature: Verkle-Based HORST
## 6 Merkle Signature Scheme (MSS)  
In order to improve the usability of one-time signature (OTS) systems, [PERSON] invented the Merkle Signature technique (MSS) in 1979. It is a digital signature technique based on stateful hashing. Strong security is offered by OTS schemes like Lamport-Diffie OTS and Winternitz OTS (WOTS), but they have a major drawback: each key pair can only be used once. By enabling many secure signatures with a single small public key, MSS solves this problem. This is accomplished by organizing many OTS key pairs into a binary Merkle tree structure, with the root of the tree acting as the scheme's main public key [18]. Since the Merkle signature technique only uses hash functions, it is resilient to attacks by quantum computers, making it one of the first and most significant post-quantum cryptography schemes. Because MSS combines the efficiency of Merkle trees with the security of one-time signatures, it stands out for its simple yet clear design. Many contemporary hash-based signature schemes, like XMSS and SPHINCS+, which are currently a part of the NIST Post-Quantum Cryptography Standardization Project, were influenced by it. The key generation process in the Merkle signature scheme consists of three main steps: generating one-time signature key pairs, computing a Merkle tree, and deriving the main public key. Figure 1 shows a Merkle tree, when tree height is three:  
In Figure 1, firstly, the signer generates a set of \(2^{h}\) OTS key pairs, \(\big{(}X_{j},Y_{j}\big{)}\), where \(h\) is the height of the Merkle tree. The first one, \(X_{j}\), is the signature key or secret key, the other is the verification key or public key. Each one-time signature key pair consists of a secret key and a corresponding public key \((X_{i},Y_{i})\) for \(i=0,1,\ldots,2^{h}-1\). Next, the public keys of the OTS key pairs are hashed using a cryptographic hash function, to form the leaf nodes of the Merkle tree:  
\[\text{leaf}\,_{i}=H(\text{y}\,_{i}) \tag{12}\]  
After forming the leaf nodes, the Merkle tree is built by hashing pairs of child nodes to create their parent nodes. The internal nodes of the tree are determined by the hash values of its left and right child nodes. The public key of the Merkle signature scheme is represented by the root of the tree, while the secret key of the Merkle signature scheme consists of one-time signature keys, each with a length of \(2^{H}\). Until a single root node is obtained, this procedure keeps going:  
\[\text{node}_{j,k}=H\Big{(}\text{node}_{j-1,2k}\|\text{node}_{j-1,2k+1}\Big{)} \tag{13}\]  
Here, \(\|\) denotes concatenation. The final root node at the top of the tree serves as the main public key for MSS:  
\[\text{pkMSS}\,=\text{node}_{h,0} \tag{14}\]  
The signer's private key consists of all the generated one-time signature secret keys, which are used for signing messages. The height h of the Merkle tree determines the total number of signatures that can be generated, which is \(2^{h}\). For example, a tree of height h = 2 can produce over one million signatures. The signer chooses an unused one-time signature key pair from the Merkle tree and supplies an authentication path to confirm the authenticity of the key pair in order to sign a message using MSS. Choosing an OTS key that has never been used before is the first step. Assume that the key is selected at leaf index \(i\) by the signer. The private key for the one-time signature is then used to sign the message:  
\[\text{sigOTS}=\text{SignOTS}\,(\text{message},\,X_{i}) \tag{15}\]  
Figure 1: Merkle tree: height—three. The signer must supply an authentication path since the verifier only knows the root of the Merkle tree. The sister nodes required for the verifier to reconstruct the root without being aware of the entire tree are present in this route.