# Post-Quantum Digital Signature: Verkle-Based HORST
## 6 Merkle Signature Scheme (MSS)
The following is the construction of the authentication path:  
\[\text{authPath}\ =\left(\text{node}_{0,s_{0}},\ \text{node}_{1,s_{1}},\ldots,\ \text{node}_{h-1,s_{h-1}}\right) \tag{16}\]  
where \(s_{j}\) represents the sibling node required to compute the parent node at level \(j\). Finally, the full MSS signature consists of the OTS signature and the authentication path: signature \(\ =\ (\text{sigOTS},\ \text{authPath}\ )\). The verifier must first confirm that the MSS signature is legitimate before utilizing the authentication path to recreate the Merkle tree root. Verifying the OTS signature with the supplied OTS public key is the first step: VerifyOTS (message, \(\text{sigOTS},\ y_{i}\)). The verifier then gradually calculates the Merkle root if the OTS signature is legitimate. The verifier repeatedly calculates the parent nodes using the authentication route, beginning with the hash of the supplied OTS public key:  
\[\text{node}_{j+1}=H(\text{node}_{j}\|\ \text{authPath}_{j}) \tag{17}\]  
The signature is legitimate if the calculated root hash corresponds to the primary public key that is known. If not, the signature is not accepted. This procedure preserves the scheme's effectiveness while guaranteeing that the signature is genuine and unaltered. Unlike standard one-time signature (OTS) schemes that require a distinct public key for each signature, MSS permits numerous safe signatures with a single compact public key, which is one of its main benefits [19]. The Merkle tree structure, which effectively authenticates several one-time signature public keys, is used to do this. Despite its effectiveness, the Merkle tree structure has built-in drawbacks with regard to computational overhead and proof size. Verkle trees, a more sophisticated data structure, provide notable advantages in this regard. We can use Verkle trees instead of Merkle trees. Verkle trees provide substantially reduced proof sizes and lower the computational difficulty of validating huge datasets by using vector commitments rather than basic hash functions. Because of this, Verkle trees are a superior option for applications like blockchain systems that demand great efficiency and scalability. Furthermore, the Merkle signature scheme is resistant to quantum assaults because it is only dependent on hash functions. It does not rely on number-theoretic presumptions that are susceptible to quantum algorithms like [PERSON]'s algorithm, in contrast to RSA or ECC. When it comes to key storage and transmission, MSS is extremely efficient since the master public key is simply the root of the Merkle tree, which is a single hash value. A disadvantage in contexts with limited resources may be the need for numerous hash operations to compute the Merkle tree, which adds overhead to the signature and verification procedures. This restriction is addressed by Verkle trees, which are more suited for such contexts because of their more effective proof production and verification procedures, which minimize the amount of operations required. But MSS has its limits as well. The signer must maintain track of which OTS keys have already been used because it is a stateful signing structure. Security is compromised when an OTS key is reused since it makes it possible for an attacker to fake signatures. The maximum number of permitted signatures is \(2^{h}\), where h is the Merkle tree's height. A fresh key pair has to be created once every leaf has been utilized. The requirement for secure state management is an additional constraint. The scheme's security is jeopardized if the signer becomes disoriented about which OTS keys have been utilized. Because of this, MSS is less appropriate for some applications, such as distributed systems, where it might be difficult to maintain a consistent state. MSS continues to be one of the most researched and used post-quantum cryptographic signature systems in spite of its drawbacks. Modern variations like SPHINCS+ and XMSS (Extended Merkle Signature Scheme) are built on top of it.