# Post-Quantum Digital Signature: Verkle-Based HORST
## 9 Verkle Tree
### Verkle-Based Horst  
Verkle trees are a type of cryptographic data structure that generalizes Merkle trees by using vector commitments rather than simple hash functions, which enables Verkle trees to achieve much smaller proof sizes than Merkle trees, making them highly efficient for applications that require compact proofs. Verkle trees are essential for post-quantum cryptography because they reduce storage requirements, maintain high security, and eliminate redundant data for efficient verification processes that keep only the information that is needed, making them perfect for handling large datasets.  
Verkle and Merkle trees have quite different proving properties. Verkle trees employ vector commitments to \"batch\" many nodes together, lowering the amount of data needed, whereas Merkle trees demand that every sibling node be included in the proof. Verkle trees become more effective and scalable as a result, particularly for applications that need quick verification and compact proofs. Verkle trees, in contrast to conventional hash functions, accomplish these gains by utilizing polynomial commitments, such as Kate/KZG commitments.  
A Verkle tree is used in place of the Merkle tree for validating HORS public keys in the Verkle-based HORST (HORS with Trees) for authenticating public keys. This change greatly increases HORST's scalability and efficiency, especially when it comes to verification time  
Figure 2: Verkle tree, with branching factor 3.  
and signature size. Applications like blockchain systems, secure boot protocols, and IoT firmware upgrades that demand concise proofs and effective verification are especially well-suited for Verkle-based HORST.  
The secret key for Verkle-based HORST is made up of \(t\) random values \(\text{sk}=(\text{sk}_{1},\text{sk}_{2},\dots,\text{sk}_{t})\).  
The Verkle tree's leaf nodes are created by hashing each secret key value \(\text{leaf}_{i}=H(\text{sk}_{i})\) for \(i=1,2,\dots,t\).  
By iteratively applying vector commitments to collections of leaf nodes, we may create a Verkle tree that has a single root node \(pkVerkleHORST=root\).  
Figure 3 shows the structure of Verkle-based HORST.  
As illustrated in Figure 3, the following is a description of the Verkle-based HORST structure:  
1. Leaf Layer  
* Leaf nodes represent the hashed secret keys of the HORST scheme.
* Generate \(t\) secret keys and compute their leaves: \[\text{leaf}_{i}=H(\text{sk}_{i})\text{ for }i=1,2,\dots,t\] (23)
* These leaves form the lowest layer of the Verkle tree.
2. Intermediate Layers (Optional)
* Group leaves/nodes into vectors: Verkle trees use a branching factor \(m\) (e.g., \(m=256\)) to minimize tree depth. For example, if \(t=1024\), group leaves into 4 vectors of 256 leaves each: \[\text{node}_{1,k}=\text{ Commit }^{(\text{leaf }_{(k-1)n+1-\dots},\text{ leaf }_{k =n})}\text{ for }k=1,2,3,A\] (24)
* Intermediate layers are only required for large \(t\). If \(t\leq m\), the root can directly commit to all leaves.
3. Root Layer
* The root is the final commitment of the Verkle tree: \(\text{pkVerkleHORST}=\text{Commit }(\text{node}_{1},\text{node}_{2},\dots,\text{ node}_{n})\).
* \(n\) depends on the branching factor \(m\) and the number of leaves \(t\). Example: If \(t=1024\) and \(m=256\), the root commits to \(n=4\) intermediate nodes.  
Figure 3: Hierarchical diagram for Verkle-based HORST.