WIN BITCOIN
I won’t pretend to deeply understand quantum physics, or quantum computing specifically, I don’t, but I grasp enough to know that the theory underlying it is sound.
For certain classes of parallelizeable computations, the physical properties of quantum computers’ qubits allow searching for correct answers in very large search spaces exponentially more efficiently than classical computers. We have proven mathematical algorithms for these faster computations for a number of different computational problems, and there are many more that don’t yet have proven algorithms.
The question is whether it is practical to achieve from an engineering perspective, i.e. can we actually build machines that are efficient, reliable, and powerful enough to actually take advantage of quantum theory in a way that is useful at solving real problems?
That’s why I went to the Quantum Bitcoin Summit at the Bitcoin Presidio in San Francisco.
The small day and a half summit was attended by experts in both the quantum computing industry as well as Bitcoin developers. There were presentations on the current state of quantum computing, the specific risks to Bitcoin we would have to deal with after the development of a practical quantum computer, potential solutions we have to post-quantum cryptography, as well as debates over how to handle different aspects of the problem.
The State Of Things
There are four different architectures being developed by the different companies working on quantum computing projects. Neutral atoms, trapped ions, superconducting circuits, and photonics. All of these different physical platforms present themselves with different trade offs in terms of computational speed, stability, and scalability of the underlying physical architecture.
Most of the research for these different platforms has chiefly focused on one issue up to this point: error correction. The entire concept of quantum computing is based on the qubit, the quantum version of a bit. In traditional computers, physical hardware maintains a single bit of information using an electrical charge to represent either a 1 or 0. Qubits can exist in a superposition of both states, which is what makes them useful for certain parallelizable problems.
The issue is the physical constructs designed to implement qubits are very prone to noise interfering with computation, hence the focus on error correction. Because of this, the implementation of physical qubits has been highly redundant, in some cases requiring up to a thousand physical qubits to implement a “logical qubit” that can remain stable and coherent during computation.
Recent improvements have been made lowering the physical to logical qubit ratio, but another massive challenge still remains on the horizon: connecting multiple logical qubits together in a manner that can physically scale to large numbers of logical qubits. Currently no major progress has been made publicly on this challenge.
Threat To Bitcoin
Shor’s Algorithm is a quantum algorithm capable of breaking elliptic curve cryptography (ECC), if a quantum computer performant enough to run it in reasonable time is developed, then Bitcoin has serious problems to worry about. Bitcoin has many different script templates and address types at this point, but there are two major “classes” of addresses to consider when concerning ourselves with quantum computing: those that reveal the raw public key prior to spending coins, and those that don’t.
Coins that haven’t revealed their public keys prior to spending are safe from quantum theft until their owner goes to spend them, which necessitates revealing the public key, if quantum computers are powerful enough to reverse a public key to a private key before a transaction is confirmed. This is because these addresses use public key hashes rather than raw public keys. These coins are vulnerable to “short range attacks.” Coins that have already revealed their public keys are vulnerable to theft at any time. These coins are vulnerable to “long range attacks.”
Coins vulnerable to long range attacks include pay-to-public-key (P2PK), pay-to-multisig (P2MS), taproot address (P2T2), and any kind of address scheme that has reused addresses. Everything else is only vulnerable to short range attacks.
This presents a problem with two needed solutions: new cryptographic schemes that are quantum safe for users to migrate to, and a method to migrate coins vulnerable to short range attacks to protect users in case the threat materializes unexpectedly or users still haven’t migrated by the time it manifests.
There is still one major issue presented to the users operating Bitcoin: what to do with coins vulnerable to long range attacks that haven’t migrated by the time the problem appears.
Confiscate Or Not
There are almost 2 million coins locked in P2PK addresses that are vulnerable to long range quantum attack. That is almost 10% of the entire supply of bitcoin. Many Bitcoiners are very concerned about the possible implications the theft of such a large amount of coins could have on the price of bitcoin if dumped onto the open market.
As such, many ecosystem participants have proposed the idea of burning these coins and rendering them forever unspendable in the event of a quantum computer capable of attacking Bitcoin is developed. This has turned into the core of an ethical conundrum: do we take a confiscatory action to protect the wider ecosystem, or do we allow quantum vulnerable coins that have not migrated to be swept and stolen by a quantum attacker?
There are also middle ground proposals, such as Hourglass by Hunter Beast and Michael Casey. This proposes rather than freezing quantum vulnerable coins, they simply be throttled or rate-limited. Hourglass would only allow 1 UTXO of quantum vulnerable coins to be mined per block after activation, thereby limiting the effect stolen coins could have on the market, and giving the actual owner a slim chance of recovering some of their coins if they still possess the private keys.
One way or another, if a quantum attacker does manifest with a powerful enough computer, this issue will need to be decided.
The Tools We Have
As far as quantum safe cryptography is concerned, we have two broad options to choose from, lattice based cryptographic schemes or hash based cryptographic schemes. Lattice based schemes introduce new cryptographic assumptions, but support features we have come to assume when building, such as key aggregation schemes. Hash based schemes do not support key aggregation schemes, or even deterministic public key generation without private key material, but introduce no new cryptographic assumptions. Hash functions are known to be generally quantum resistant, and the hardness of hash functions is the only assumption made regarding cryptographic security.
Hash based signature schemes produce much larger signatures than lattice based schemes, but both are significantly larger than ECC signatures. Regardless of what scheme was chosen, there would be a massive reduction in throughput of the blockchain with the adoption of post-quantum signature schemes. This would either need to be accepted, or a proportional increase in block weight with a large quantum witness discount would be needed, heavily increasing the cost of running a full node.
In terms of migration schemes, there are two major paths that could be taken: commit-reveal schemes, or a zero-knowledge proof scheme proving control of secrets related to your private keys. The latter would only work for coins stored on keys generated by hierarchical determinic wallets using mnemonic word seeds.
Commit-reveal schemes invalidate spending short range attack vulnerable coins without first committing to a hash of the spending transaction. Users could then use quantum safe coins to commit to their vulnerable coins being spent, and only after that was buried under a sufficient amount of proof-of-work could the actual transaction migrating to a quantum safe address be confirmed.
Zero knowledge schemes could be used to generate a zero knowledge proof that you control a related key or secret generated in a derivation path from your mnemonic seed that has never revealed the public key. All vulnerable coins could be restricted to require such a proof in order to be spent. Since the proof must be generated using a key that the attacker could never discover, because the public key is never revealed, this proof should be impossible for the attacker to generate. However, it would be unusable for coins that are stored in addresses made prior to the invention of determinstic wallets.
So What Do We Do?
The theory of quantum computing is legitimate, and Bitcoin is systemically vulnerable to a powerful quantum computer, so what should we do?
I am personally not confident that the massive fundamental breakthroughs are right around the corner, but I am also not confident that they are impossible to make. It’s frankly above my ability to truly independently assess. What I do know is that we have the bare minimum of tools necessary to take defensive action against the possibility of those breakthroughs occurring.
Not reusing addresses and not using vulnerable address types will keep your coins safe from long range attacks, and able to use migration protocols. It is especially important for large exchanges and economic actors to take such basic actions. If this is a concern for you, then take such action, or be prepared to migrate to such addresses if it does become a concern.
As far as proactive changes go, hash based signature schemes are known to be quantum safe with no new assumptions, both Hourglass v1 and outright coin confiscation are simple to make changes to deal with systemic market risks (and doing nothing regarding this issue is even easier), and commit-reveal and zero knowledge migration schemes give us a means to migrate coins after the threat has already become real.
We should get these simple proposals in a ready-to-deploy, or place where getting there is a minimized workload, and then simply keep an eye on the situation while the people who are concerned continue debating and researching the subject.
The sky is not falling today, and maybe it never does at all. This is not an issue that should be keeping people up at night, but it is also not something we should completely ignore. We are already capable of minimal viable solutions now, we should get those into a reasonable state and then continue monitoring the situation for signs that we should collectively allocate more resources to the issue.
The one thing we definitely shouldn’t do, however, is panic and start blindly pouring time and resources into this over all other problems.
If you want to learn more about these issues, keep an eye out for coming interviews with attendees of the Summit. You can also watch the recorded presentations here:
