Existing Research on Post-Quantum Blockchain Design

I reviewed in a previous post a new paper by Google research that suggests that quantum attacks on cryptographic schemes might be more feasible than previously thought. This state of affairs poses a major challenge to existing blockchains since it will be possible for attackers to crack private keys and retrieve funds that don’t belong to them. The development of a quantum computer poses an existential threat to public blockchains, so it’s worth looking into the research on how to design post-quantum blockchains.

The first paper, A Secure Cryptocurrency Scheme Based on Post-Quantum Blockchain. This paper proposes the use of a post-quantum signature scheme based on a lattice scheme. Most of the work focuses on the precise definition of the signature scheme and the blockchain aspect is mostly used as a motivating example rather than investigated in depth. In addition, the paper doesn’t provide any experiments or implementation results, so it’s hard to judge how the proposed signature scheme would behave in a real implementation.

The second paper Committing to Quantum Resistance: A Slow Defence for Bitcoin against a Fast Quantum Computing Attack doesn’t study the design of a post-quantum signature scheme, but rather asks how the Bitcoin community can transition to a chosen post-quantum signature scheme safely once ECDSA has been cracked. There are a number of interesting tidbits in this paper. For one, any Bitcoin user who has ever revealed their public key would be at risk to quantum attack. Since public keys are assumed to be safe to reveal, this reality places many (most?) current Bitcoin holders at risk. Another interesting tidbit is that proof-of-work becomes significantly easier once it’s feasible to use Grover’s search algorithm to search for hashes. This means that the possibility of 51% re-orgs increases significantly once quantum computers emerge since a small group with enough quantum machines could overpower existing ASICs.

It’s important to emphasize that the scheme in this paper doesn’t help you if your public key has been exposed, but can provide for a safe transition if your public key has been kept secret thus far. The modification proposed is the creation of a soft-fork that freezes all ECDSA signature authorized transactions. Only post-quantum signatures and special “transition” transactions that move funds from ECDSA to post-quantum keys would be accepted. If a user has not revealed their ECDSA public keys, they may safely transition funds by a commit-reveal scheme. Mechanically, the proposed soft-fork would function like the previous SegWit soft-fork in which the data for the new rules would be held in a special witnessing area.

Reading both these works, it strikes me that considerably more work will be needed before a real post-quantum blockchain can be designed. A suitable post-quantum public/private key and signature scheme will have to be chosen. Proof of work will have to be modified to account for Grover’s algorithm based attacks. Or Proof of stake will be have to be modified so as to not rely on BLS signature aggregation (which is quantum vulnerable). What are the steps to make this happen? First I think a suitable post-quantum scheme would have to be proposed, perhaps using some of the entrants in the current NIST post-quantum crypto challenge. Next, a post-quantum proof-of-work or proof-of-stake implementation would have to be proposed, and finally a prototype implementation of a blockchain (UTXO or Ledger based) would have to be designed and launched. There are major risks in this process since most post-quantum crypto schemes haven’t been hardened and are often vulnerable to simple (non-quantum) attacks. However, the experiment seems like it’s worth the effort.