Hash-Based Signatures and the Quantum Resistant Ledger

In previous posts, I’ve reviewed credible medium-term threats to cryptography from quantum computing and existing research on methods to migrate to a post-quantum future. I previously missed that there are existing projects attempting to build a quantum-resistant blockchain today. One such project is the quantum-resistant ledger which is working on building a quantum resistant blockchain.

The QRL whitepaper proposes replaces ECDSA signatures with a quantum resistant signature scheme. ECDSA uses elliptic curve operations to construct the signature desired. The ECDSA algorithm has the powerful advantage of having shorter public keys than other alternatives. However, ECDSA is vulnerable to a quantum period finding attack which makes it undesirable as a signature scheme.

Hash-based signature use standard hash functions to construct secure signatures. Hash functions are still vulnerable to attack by Grover’s algorithm (which provides a quadratic speed up to any search algorithm), but this quantum attack isn’t as severe as that posed by Shor’s exponential attack on ECDSA. However, it will likely necessitate doubling key sizes compared with a classical threat model. The construction of hash-based signature schemes is a little complex, so let’s discuss the simpler problem of creating simple one-time-signatures (OTS) based on hash functions. To a rough first approximation, hash-based OTS signature schemes perform multiple rounds of hashing to produce a signature. In each round, the input is XOR’ed with some fixed value and then passed through a hash function. The final output is the signature for the scheme. This technique produces one signature per private-key/public-key keypair, but is not secure for producing multiple signatures.

To construct a more useful signature scheme, it’s common to combine hash-based signatures in a Merkle tree. Such Merkle Signature Schemes (MSS) work by pre-generating many OTS key-pairs and computing signatures via a Merkle tree (which computes a hash function at each node). The merkle-root is the public key for the scheme. The OTS key-pairs are leaf nodes for the Merkle tree. The advantage of this scheme over OTS schemes is that each many OTS key-pairs can be used with one public key (the Merkle root). The limitation of such MSS schemes is that each leaf node can only be used to generate one signature, so the usability of the scheme is limited by the number of OTS key-pairs that can be generated. It turns out to be expensive to create large trees in this fashion, so an alternative idea uses “hypertrees.” In this design, merkle trees are chained, so that the leaf of the original merkle signature tree leads to a second merkle signature tree. This type of chaining is called a “hypertree”. This nesting can go deeper to allow for more signatures. With a sufficiently deep chain of Merkle trees in the hypertree, you can gain a large number of signatures before the scheme is exhausted. Note that the OTS key-pairs for each Merkle tree have to be pre-generated though, which might consume some amount of storage.

It’s worth pausing to contrast hash-based signatures with ECDSA signatures. ECDSA signatures don’t get exhausted in the same way hash-based schemes do; a single ECDSA key-pair can generate an arbitrary number of signatures. Hash-based signatures schemes are in broadly speaking inferior to ECDSA signatures, with larger keys, and signature exhaustion, but have the killer feature of quantum resistance. The QRL project uses the XMSS signature scheme. XMSS is a type of MSS that has been written up as an IETF draft for future standardization. The QRL whitepaper reports experiments that create signatures of size 5.75 kB using XMSS and also reports on some innovations such as “asymmetric keys” to reduce the signature burden on the user.

The QRL cryptocurrency itself is designed as a bitcoin-esque UTXO blockchain with a few tweaks from Bitcoin’s original design. The whitepaper advocates against high transaction fees, and proposes the use of a minimal transaction fee. In addition, QRL has adaptive blocksizes which allow for blocks to grow or shrink dynamically based on usage in the last few blocks. Mining is done with Proof-of-Work using the cryptonight hash function, and with a planned transition to a Proof-of-stake algorithm in the future. QRL launched a mainnet last year and appears to be running at present.

It’s heartening to find that at least one project on main-net has succeeded in launching with a proposed post-quantum signature scheme. At the same time, it brings some sobering understanding of the challenges of post-quantum signature schemes. XMSS and similar schemes look like they will need considerable additional refinement before they become as convenient to use as existing ECDSA signatures.