Welcome,
Submissions for the QDay Prize are now open! Visit qdayprize.org/submit to take part.
Our team will be at Bitcoin Vegas, May 27th - 29th. We’re eager to meet anybody who’s thinking about how to prepare Bitcoin for quantum computing. Let us know if you’ll be there. We’re [email protected].
We released two open-source packages this week. More info below.
The problem with post-quantum (PQ) cryptography is not that it does not exist, it’s that it’s new. That means it’s less trusted, more cumbersome and has received nowhere near as much investment as ECDSA and RSA.
For blockchains, the most pressing issue is to decide on and implement a suitable PQ signature. Encryption is vulnerable to quantum computers, but blockchains are explicitly designed not to depend on secure channels or encrypted communications, so it’s more of an issue for wallets, exchanges and internet providers to solve. Everything is public on the blockchain! Signatures are a different story, being an integral part of proving ownership and proof of work. Also, cracking ECC requires fewer qubits than cracking RSA, so ECDSA and Schnorr signatures, as well as ECC encryption, will be the first victims of quantum computers.
Obviously, when choosing a PQ signature, security against both classical and quantum attacks is the biggest concern. There are other issues though. They can be separated into the two categories of storage and compute. With regard to storage, the questions are: How big are the public and private keys associated with the signature? How big are the signatures themselves? The compute questions are: How many cycles does it take to produce a signature? How many cycles does it take to verify a signature?
On the whole, PQ signatures are generally less performant than ECC signatures like ECDSA & Schnorr's, except in one key area (Hint: ‘PQ’). For a blockchain like Bitcoin, the first thing to consider is signature size, as this determines how many transactions can fit in a block. Schnorr signatures, as are currently used, are at most 64 B. The NIST-approved PQ signatures range from 666 B to 17 kB, or 10x - 267x larger! If these are naively implemented, Bitcoin suffers an instant reduction in tps of at least 10x.
Credit to Cloudflare for the original figures in this table. Source + PQ signatures zoo.
The other issues are key size, verification time and signing time. After signature size, verification is probably the biggest issue for a blockchain network. Every miner and validating node checks a large volume of signatures, both on incoming transactions and on blocks, and they need to be able to keep up with the rest of the network. If verification time(s) increase substantially, it becomes more difficult for nodes and miners to keep up, which means fewer effective nodes and miners, and a less resourced, more centralized network. Larger verification times make everything on the network go slower. We can measure verification time as how many cycles it takes a processor to validate a signature. This is a less precise measure than key size and signature size, but SLH-DSA takes 31x - 85x more cycles to verify than ECDSA. On the other hand, FALCON 512 and ML-DSA 44 can be validated faster than ECDSA, but they have larger public keys and signatures than ECDSA. There’s no obvious winner.
It’s unlikely that all possible PQ signatures are worse than ECDSA, but we haven’t yet found a uniformly superior replacement for ECDSA, and it might take decades before that happens. In the meantime, Bitcoin (and other systems) must assume it will have to incorporate an ugly new signature scheme soon, and make it work. It’s not as simple as swapping out an isolated, modular piece of code, and will require engineering improvements across the whole breadth and depth of the network.
You can learn about some of the less known PQ signatures on our blog.
As mentioned, this week we released two open-source packages: PQ Addresses for Rust and Typescript.
PQ Addresses are a better and safer way to share PQ public keys. We think this can be useful every time somebody wants to validate PQ signatures, whether that’s for the next generation of TLS, identity verification… and as a format for PQ addresses and signatures on blockchains, including Bitcoin.
PQ public keys are big, cumbersome, and error-prone when manually shared. We built PQ Address to tackle these issues directly by creating a reliable and simple address format for PQ public keys. A PQ Address encodes the hash of a public key, ensuring it does not reveal the public key, and is strictly one-way. It’s based on the Bech32m encoding and is designed to be quantum-secure and usable for a wide range of settings - not just Bitcoin.
We’d love to see people trying them out, experimenting with how to apply and improve them, and getting involved with the repos.
- The QDay Prize
- P11 Blog: Are Emerging PQ Signatures Better for Blockchains?
- P11 Blog: Introducing PQ Addresses
- PQ Addresses - Rust
- PQ Addresses - Typescript
- PQ Signatures zoo
- PQC is too damn big
- Cloudflare Blog: Candidate PQ Signatures
- Cloudflare blog: Sizing up PQ signatures
- A lovely, short interview on quantum computing developments from 1999 - 2047.
Until next time,
The Project Eleven Team