Author: Natanael 2018-01-24 12:51:45
Published on: 2018-01-24T12:51:45+00:00
On January 23, 2018, Gregory Maxwell responded to a discussion on bitcoin-dev about the security of Bitcoin addresses in light of quantum computing advances. In response to a comment regarding the use of taproot and hashing the key, Maxwell asked if there was a model of quantum computation that could solve the discrete log problem but take longer than fractions of a second to do so. Quantum computers perform calculations probabilistically by biasing the probabilities of their qubits to read out the correct answer more often than at random, and algorithms are composed of a fixed sequence of quantum logic gates. Quantum algorithms are often probabilistic, providing the correct solution only with a certain known probability. A non-programmed quantum computer is an RNG driven by quantum effects, while a programmed one needs to run the program over and over until the correct answer can be derived from one of its outputs. Grover's algorithm would crack a symmetric 256 bit key in approximately 2^128 QC cycles, which is completely impractical, while Shor's algorithm is dangerous for ECC since it cracks current keys at practical speeds. Resource estimates for quantum computers do not address implementation speed, but some estimates suggest around 2^40 cycles in practical implementations for 256 bit ECC, although this remains theoretical.Maxwell noted that read-out time for quantum computers is insignificant in terms of measuring the state of the qubits after a complete cycle, but programming time, time to prepare for readout, reset, reprogramming, etc., will all take a little longer, particularly with more qubits involved. Optimistic cycle speeds are in the GHz range, but this is still on the order of ~15 minutes for 2^40 cycles. While danger to Bitcoin's typical use of ECC is immediate if someone builds a fast QC that is nearly ideal, Maxwell's own wild guess is that for the next few decades none will be faster than a runtime measured in weeks for cracking keys.Maxwell suggested implementing early support for the Fawkes scheme mentioned previously, which could be patched on top of classical transactions. By committing to the signed transaction into the blockchain before publishing it and then afterwards publishing the transaction itself with a reference to the commitment, the transaction can be assumed legit simply because there was no room to crack the key before the commitment, and the transaction matches the commitment. Never reusing keys ensures safety against QC's. However, there is a risk with interception and insertion of a new commitment and getting the new transaction into the blockchain first, so Maxwell suggests a mining policy were two known conflicting transactions with commitments are resolved such that the one with the oldest commitment wins. Finally, Maxwell notes that HD wallets with hash-based hardened derivation should also be safe in various circumstances, near completely safe in the case where they're defined such that knowing an individual private key, which is not the root key, is not enough to derive any other in your wallet. HD schemes that only prevent derivation of parent keypairs in the tree would require that you never use a key derived from another already used or published public key.
Updated on: 2023-06-13T00:07:01.912863+00:00