Quantum computers and Bitcoin are a heady combination.

Welcome,

We launched the QDay Prize last week. It’s the world’s first public quantum cryptanalysis challenge, with a 1 BTC prize. Participants must break an ECC key of any length - even just 3 bits - using a real quantum computer. As far as we’re aware, Shor’s algorithm for the ECDLP has not been run successfully on quantum hardware. Any winning entries would be a milestone in quantum algorithms and an important data point for cryptography and blockchains.

Learn more at qdayprize.org. If you’d like to work with us on this, or on future iterations of the prize, email us at [email protected]. We’re interested in speaking to folks across quantum computing, post-quantum cryptography and blockchain.

 

BTC Mailing List, Fujitsu, Martinis

Much of the work on Bitcoin takes place on a public Google Group: The Bitcoin Development Mailing List. Over the past few weeks, there’s been good discussions there on preparing Bitcoin for quantum computing. Topics include aggregating post-quantum signatures, what to do with non PQC wallets and hashed keys.

Separately, Fujitsu announced a 256-qubit superconducting computer, though performance details are not yet public. They claim it will be available sometime this year. Interestingly, the design is made up of 4 64-qubit subunits. Also, John Martinis’ new superconducting company, Qolab, came out of stealth.

 

10 Misconceptions

The future of cryptography, cryptocurrency and quantum computing are intertwined, but these three fields are complex enough that few people really understand how they intersect. There are also gulfs between the respective communities: Crypto is a semi-anarchic battleground where attention and narrative potency are more important than facts, while quantum computing progresses through a stilted combination of excited press releases and impenetrable Arxiv papers. And because anything including ‘quantum’ gets treated more like magic than science, the public rarely gets a good explanation of quantum computing.

Well, that’s a recipe for misconceptions. Here are 10 about Bitcoin and quantum computing.

  1. “Quantum computers will be too slow to damage Bitcoin.”
    False. A fundamental pillar of Bitcoin is reliable cryptography. Quantum computers compromise this, and even if the first real quantum computers are not capable of stealing large amounts of BTC, their existence alone may cause a severe loss of trust in Bitcoin, and a mass exodus from the network. It’s worth preparing ahead of time in order to avoid this.
  2. “Quantum computers will break proof of work.”
    This won’t happen for at least 10 years. Bitcoin mining is a pre-image search: You compute hashes until you find one that matches a required pattern. Grover’s algorithm gives quantum computers a quadratic speedup for this kind of problem, cutting the work from $2^{256}$ to $2^{128}$ searches. This is a relative speedup, true, but it’s not sufficient to help on an absolute scale. A viable quantum computer might cost ~$100M and be orders of magnitude slower than $100M worth of Bitcoin mining ASICs and GPUs.
  3. “Bitcoins are not vulnerable to quantum attacks.”
    Today this is true. When a 2000-qubit, error-corrected quantum computer exists, it will be false. At that point, any Bitcoin address with its public key exposed can be hacked. We published a blog post recently outlining which address types are vulnerable. Notably, Taproot addresses are vulnerable, as are any address that has spent BTC.
  4. “A quantum computer will instantly steal all Bitcoin.”
    False. The first quantum computers capable of stealing Bitcoin will be those that can run Shor’s algorithm on 256-bit keys. These machines will be slow, and will likely take hours, days or weeks to calculate a single key. If used to hack Bitcoin, these first machines will only be able to produce a small set of private keys - and only for wallets whose public key is exposed. SegWit and P2PKH addresses that have not spent any BTC will be safe from initial attacks.
  5. “A quantum computer is too slow to pose a threat to Bitcoin.”
    False. When suitably large, error-corrected quantum computers exist, they can damage Bitcoin and steal BTC without having fast clock cycles. Today, multiple BTC wallets holding over 100,000 BTC have their public key exposed, including a wallet owned by Binance. As long as such targets exist, a quantum computer can take weeks or months to run Shor’s algorithm, and then empty the target wallet of its BTC. Any such hack by a quantum computer would precipitate a major crisis for Bitcoin.
  6. “Enabling quantum-safe addresses requires a hard fork.”
    Not true. Quantum-safe addresses can be enabled with a soft fork. However, making Bitcoin fully quantum-resistant will be hugely complex and may require a subsequent hard fork. Initially, a soft fork will enable Bitcoiners to upgrade from ECDSA/Schnorr signatures to PQC signatures. After a grace period, extant non-upgraded wallets will need to be dealt with, and ECDSA transactions may have to be discontinued, requiring a hard fork, which would include things like banning transactions to ECDSA P2PK addresses. There are additional challenges due to signature sizes and key sizes for PQC signatures being much larger than ECDSA.
  7. “It’ll be obvious to Bitcoin when a quantum computer arrives.”
    Quantum computers might never be used to attack Bitcoin, but better safe than sorry. Adversarial quantum computers may not be detected for some time. They can run Shor’s algorithm in secrete, recover private keys, and transfer BTC out of the hacked wallets whenever they please. Since many BTC wallets with large balances have been dormant for years, and may be unmonitored, it could be some time before the network is alerted to any hacks.
  8. “There is no post-quantum cryptography that can protect Bitcoin.”
    There is plenty, it’s just not implemented in Bitcoin yet. NIST completed its seven-year standardization process in 2023 has drafted standards for lattice-based and hash-based digital signatures, as well as key encapsulation mechanisms. Multiple open-source libraries now exist for implementing PQC. Challenges lie ahead for Bitcoin, including reconciling signature sizes, transaction throughput and block size, but the core blocker is social consensus rather than math.
  9. “Quantum computers will protect Bitcoin from quantum computers.”
    This confuses quantum cryptography (i.e. quantum key distribution, QKD) with post-quantum cryptography (PQC). QKD is a novel method for distributing private keys, but it does not sign transactions or stop thieves from running Shor’s algorithm on existing Bitcoin wallets. PQC, on the other hand, is the set of encryption schemes that are resistant to quantum computing attacks, even if the encryption is performed using classical computers. The clearest route to quantum-proofing Bitcoin is using PQC.
  10. “Bitcoin can’t survive quantum computers.”
    Bitcoin can absolutely survive the advent of quantum computing, but it needs to enable post-quantum cryptography in a timely manner and resolve the issues that this transition will surface. As well as being a major technical effort, upgrading to PQC will require confronting difficult decisions around block size, network throughput, property rights and dormant wallets - and any wallet which fails to upgrade to a PQC signature. The best approach is not yet clear and may take years to be agreed upon - not least because post-quantum cryptography is a rapidly evolving field. If the network takes too long to upgrade, it will put itself at risk of collapse, but Bitcoin can upgrade well before the first cryptographically-relevant quantum computer boots up.

 

Bitcoin Dev: Post-Quantum Cryptography Threads

Other Links

 

Until next time,

The Project Eleven Team