# Post-Quantum Digital Signature: Verkle-Based HORST
## 11 Efficiency Comparison  
Compared to classic HORST, Verkle-based HORST offers notable efficiency improvements, especially when it comes to storage needs, verification time, and signature size. Table 2 contrasts Verkle-Based HORST, Traditional HORST, and other Hash-Based Schemes. In traditional HORST, the signature size grows logarithmically with the number of leaves \(t\), resulting in \(O(k\text{log}t)\). In Verkle-based HORST, the use of vector commitments reduces the signature size to a constant \(O(k)\), making it much more compact. Verkle-based HORST would require only a constant number of values, regardless of \(t\). In HORST, the verifier must compute \(O(\text{log}t)\) hash operations to reconstruct the Merkle root. In Verkle-based HORST, the verifier only needs to compute a constant number of operations \(O(1)\) to verify the vector commitments, resulting in faster verification. The verifier in Verkle-based HORST would only need to compute a single operation. This information provides system designers with a number of crucial insights. Verkle-based HORST's uniform 32-byte public key size allows for simple integration without requiring protocol modifications because it corresponds to the address formats utilized by popular blockchain systems like Ethereum (20 bytes) and bitcoin (32 bytes). On the other hand, Dilithium3's 1.3 KB public keys would necessitate considerable changes to current systems; for instance, TLS 1.3 certificates would have to grow by around 30% in order to support these bigger keys. Despite their theoretical promise, multivariate and code-based schemes have not been widely adopted. For example, Rainbow-III's 161 KB public keys \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Scheme** & **Public Key** & **Private Key** & **Signature** \\ \hline Verkle-based HORST & 32 B & 64 B & 3.2 KB \\ Dilithium3 & 1312 B & 2528 B & 2.7 KB \\ Rainbow-III & 161 KB & 103 KB & 160 KB \\ McEliece-348864 & 0.9 MB & 1.2 MB & 0.2 KB \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Key and signature size comparison (128-bit security level). are larger than the total amount of memory on many devices with limited resources, and McEliece's combination of massive keys and small signatures results in an asymmetric storage profile that is challenging to control in distributed systems. Verkle-based HORST uses less storage for authentication pathways, because proofs are smaller. This renders it more appropriate for settings with limited resources, such as blockchain apps or IoT devices. For instance, in a blockchain system, transactions with smaller signatures are smaller, which results in cheaper fees and quicker processing times. Since the efficiency advantages rise with the number of leaves t, Verkle-based HORST is more scalable than standard HORST. Because of this, it is a superior option for applications that need extensive key management. For instance, Verkle-based HORST can effectively manage thousands of firmware upgrades in a secure boot protocol without sacrificing speed. Verkle trees use vector commitments (such as polynomial commitments like Kate/KZG commitments) rather than simple hash functions to obtain \(O(1)\) proof sizes. Because the verifier must recreate the full route from the leaf to the root, each proof in a typical Merkle tree requires \(O(\log t)\) hash values. Verkle trees, on the other hand, use vector commitments to combine many leaf nodes into a single proof, which enables the verifier to validate the whole path with a proof of constant size. This is accomplished by making use of polynomial commitments' mathematical characteristics, which allow for the effective aggregation of several values into a single proof. Verkle-based HORST is hence very scalable for large-scale systems as it lowers the proof size from \(O(\log t)\) to \(O(1)\). This thorough analysis reveals several important trends.