Author: Matt Corallo
Source: https://groups.google.com/g/bitcoindev/c/8O857bRSVV8/m/4cM-7pf4AgAJ
The original post was published on December 16, 2024.
There have been some rough ideas over the past few years regarding quantum computing resistance in Bitcoin transaction signature schemes, but many of these ideas have several major flaws.
First, we establish several basic assumptions:
(a) Quantum computers capable of breaking elliptic curves are still a long way off (potentially ten or even twenty years, not just a few). This aligns with the recommendations of the NSA (National Security Agency) and other agencies. We have time to upgrade, but we can consider one option: designing a security layer for quantum computing in wallet software today.
(b) It is entirely possible that a fundamental expansion constraint could emerge, making it impossible for a quantum computer capable of breaking elliptic curves to ever appear. We may not want to gamble on this possibility, but it is possible.
(c) Before quantum computing, which breaks through elliptic curves, is ready, we will see some significant warnings—the development of quantum computers requires enormous resources, so much so that only a handful of organizations in the world can afford the personnel and laboratory costs. This type of development work has already been, and will likely be, announced as progress is made, so even as quantum computers get closer to reality, we will receive warnings years in advance.
(d) Current security assumptions of post-quantum cryptography (such as lattice cryptography and “Supersingular Elliptic Curve Isogeny”) are insufficient to protect today’s money and are poor candidates for Bitcoin’s consensus (given the potential of future cryptographic research). This means that, at present, the only candidate for Bitcoin’s post-quantum signature security is hash function-based signatures (basically SPHINCS/SPHINCS+).
(e) It's not worth waiting for OP_CAT or other more generic script opcodes, as these projects seem mired in problems, not to mention the numerous questions surrounding MEVil (value that malicious miners can extract) and the future of Bitcoin. Furthermore, using specialized opcodes simplifies the adoption process for wallet software—wallet developers are already putting in extra work for a feature that won't be immediately available to users, which is already cumbersome enough.
Given these assumptions, it seems illogical for wallet software to lock funds in special addresses, pay additional fees, and leave a blockchain footprint for post-quantum security starting today . However, at the same time, considering the time-consuming nature of Bitcoin's upgrade cycles, it also seems unwise not to provide wallet software with some "emergency access" options.
Fortunately, taproot provides a good way to develop such a scheme! Because the script-path spend of taproot is strictly constrained (the internal public key of the taproot address is promised in the hash value t of the taproot script path), future quantum computers can calculate the private key (of the internal public key) and know the Merkle root value of the script path, but cannot forge another Merkle root of the script path.
This provides an entry point for quantum-resistant security: by directly adding an OP_SPHINCS opcode to verify SPHINCS (or an equivalent quantum-resistant non-one-time signature, unlike Lamport/Winternitz signatures) (like today's OP_CHECKSIG ), the wallet only needs to always include an alternative script path cost condition to construct the taproot output to obtain emergency access. When quantum computers become available, the taproot key path cost can be disabled via a soft fork, forcing coins to use quantum-safe script paths for spending.
This scheme clearly has a major drawback: funds in unupgraded addresses will be "confiscated" when quantum computers become available, but:
(a) We could require an explicit choice of this scheme. The downside of this is that it would leave an additional on-chain trace and would require a new script public key format (the existing bech32m address encoding format could be retained, which is presumably already supported by most wallets, requiring no code changes). Of course, if we made such a requirement, much Bitcoin that would otherwise be unlikely to be spent would be transferred, potentially causing a liquidity shock and harming Bitcoin's utility in another way.
(b) Alternatively, we could allow key path spending, provided the wallet proves its script path is a NUMS point (a public key whose private key is unknown to anyone) (through some new key path + proof spending variant). I suspect many wallets today wouldn't bother committing a NUMS point for their taproot output public key, so this could break existing wallet software, but it could serve as an opt-out solution.
This approach has a very good property: it hardly affects existing usage (it only requires adding an extra taproot script cost branch, but this is not a difficult thing in general).
There are a few issues to discuss: First, should users be required to choose whether to enter, or should an option to exit be provided? Second, should all script paths that trigger ECDSA signature verification also fail? (It's quite possible.)
I suspect this idea has already been shared elsewhere, but I haven't found it. Most of these ideas come from not_nothingmuch; I'm just writing them down to claim credit.
This idea doesn't solve the question of how PoW will exist in a world with quantum computers, but it's likely unanswerable until we see more practical limitations of quantum computers (e.g., what is the minimum latency of a quantum computer's gate circuitry). If this latency is very low, could we increase the complexity of Bitcoin's PoW hash function, thereby delaying the time it takes for a quantum computer to compute the result, allowing traditional hardware to still mine blocks?
Luke Dashjr replied:
Just one more point: this quantum-resistant script path doesn't require a soft fork to add, as long as it's fully defined. In other words, once its specification is finalized, wallet software can immediately begin implementing this fallback path without waiting for any soft fork activation. This will require protecting this post-quantum script as if it were a private key itself, so it could be a problem for hardware signers, but I suspect there are ways to solve it…
