# Post-Quantum Digital Signature: Verkle-Based HORST
## 9 Verkle Tree
### Algorithm for Verkle-Based HORST  
Key Generation:  
Create \(t\) random secret key elements using formula \(\text{sk}=(\text{sk}_{1},\text{sk}_{2},\dots,\text{sk}_{t})\). Hash each secret key element to determine the leaf nodes:  
\[\text{leaf}_{i}=H(\text{sk}_{i})\text{ for }i=1,2,\dots,t \tag{25}\]  
Apply vector commitments to groups of leaf nodes iteratively to create the Verkle tree:  
\[\text{node}_{ijk}=\text{Commit}_{(\text{node}_{j-1,2k},\text{node}_{j-1,2k+1})} \tag{26}\]  
The root of the Verkle tree is the main public key pkVerkleHORST \(=\) root. Signing Process:  
Determine the message digest \(\text{msgDigest}=H(\text{message})\). Split the digest into \(k\) indexes \((\text{index}_{1},\text{ index}_{2},\dots,\text{ index}_{k})=\text{msgDigest}\bmod t\). Make the matching private key components visible \(\text{sigHORS}=(\text{sk}_{\text{index}_{1}},\text{sk}_{\text{index}_{2}}, \dots,\text{sk}_{\text{index}_{k}})\). Generate a Verkle proof (In Merkle tree we had sibling-based paths):  
\[\text{leaf}_{i}=H(\text{sk}_{index,i})\text{ for }i=1,2,\dots,t \tag{27}\]  
This replaces the traditional Merkle sibling path with a constant-sized KZG or IPA proof. The final signature is signature \(=(\text{sigHORS},\text{ verkleProof})\). Verification Process:  
Compute the message digest \(\text{msgDigest}=H(\text{message})\). Split the digest into \(k\) indexes \((\text{index}_{1},\text{ index}_{2},\dots,\text{ index}_{k})=\text{msgDigest}\bmod t\). Hash each revealed private key element \(\text{leaf}_{i}=H(\text{sk}_{index,i})\) for \(i=1,2,\dots,t\). Verify the Verkle proof. Use verkleProof to confirm that all \(\text{leaf}_{i}\) values are correctly included in the tree. Reconstruct the root from the proof and check computedRoot \(==\) pkVerkleHORST. If the computed root matches, the signature is valid. Three factors essentially control the security-performance tradeoffs in Verkle-based HORST: the subset size \(k\), total key count \(t\), and branching factor \(m\). These variables show complex dependence. While increasing \(t\) improves security through greater key material (typically \(t=1024\) for 128-bit security), it imposes linear \(O(t)\) scaling on key generation time. The branching factor \(m\) creates a dual effect: while reducing tree depth from \(O(\text{log}_{2}t)\) to \(O(\text{log}_{m}t)\), it creates polynomial commitment overhead that increases as \(O(m\text{ log}_{m}t)\). According to experimental evidence, \(m=256\) achieves an optimal balance for \(t=1024\), delivering 1.4 ms verification times while maintaining compact proofs. This parametric framework enables precise adjustment for different deployment circumstances. Resource-constrained IoT devices may use \(m=64\) to decrease memory consumption despite wider trees; blockchain systems often prefer \(m=512\) to reduce proof sizes at the risk of modest verification slowness (see Table 1: 2.1 ms). The subset size \(k\) further mediates this balance; bigger values improve fault tolerance but increase signature size as \(O(\text{klog}t)\). Implementers may adapt the scheme to their unique security and performance requirements thanks to this parametric framework. System designers can strike the ideal balance between computational overhead, verification speed, and signature size by carefully choosing the values of \((k,t,m)\). Verkle-based HORST offers several advantages over traditional HORST. Applications that need short signatures can benefit greatly from the usage of Verkle trees, which reduce the signature size to a constant. In blockchain systems, where smaller signatures result in cheaper transaction fees and quicker processing times, this is especially advantageous. Verkle-based HORST is faster to verify than classic HORST, which needs logarithmic-time verification, because vector commitments are verified in constant time. This enhancement is important for applications where quick verification is essential, such as secure boot protocols.