On Monday, Google unveiled its state-of-the-art quantum chip, Willow, sparking some concerns within the Bitcoin and broader digital asset community. Although quantum computing (QC) has long been a peripheral fear for investors, its future distance has kept it from being a pressing issue for analysis. Advancements like Google’s are inevitable, and while their significant impact may still be decades away, we’re providing this as a reference for investors the next time QC-related concerns arise. Expert opinions on the timeline vary widely, but we believe informed investors are best equipped to make sound decisions.
How Bitcoin Uses Cryptographic Technology
To start, let's cover the basics of how Bitcoin utilizes cryptographic technologies. It relies on two key types: digital signatures and cryptographic hash functions.
Digital signatures, such as ECDSA (Elliptic Curve Digital Signature Algorithm with the secp256k1 parameter) and Schnorr, are fundamental to generating private/public key pairs and managing how users send and receive bitcoins. Users create a key pair and lock an output (bitcoins) to a public key. These bitcoins are secure because only the corresponding private key can produce a valid signature to unlock or spend them. The public key is derived from the private key using ECDSA or Schnorr algorithms.
Hashing, particularly through the Secure Hash Algorithm 256-bit (SHA-256) and RIPEMD-160, processes an input string to produce a fixed-length output, known as a digest. Bitcoin relies on hashing for several critical functions, including address security, transaction verification, time stamping, and mining.
- Public keys, derived from private keys using digital signature algorithms, are hashed twice—first with SHA-256 and then with RIPEMD-160—to generate a public address.
- The hash of all transactions in a block called the Merkle root, is included in the block header to enable transaction verification.
- Each block has a unique hash, created by double-hashing (SHA-256) its header, which contains the previous block’s hash and other details, forming a chain of blocks.
- In mining, hashing involves combining various pieces of information, processing them through SHA-256, and iteratively adjusting data, such as the nonce, until the resulting digest meets specific criteria.
Both digital signatures and hash functions could, in theory, be compromised by QCs. QCs could compromise existing digital signatures using Shor’s algorithm, which efficiently solves the Discrete Logarithm Problem, allowing QCs to reverse a private key from a public key. Similarly, QCs could threaten current hash algorithms using Grover’s algorithm, known for its quadratic speedup over classical search methods. This could affect mining.
Good In Theory, Hard in Practice
The issue, however, is the practicality of these theoretical vulnerabilities. Digital signatures are widely seen as the more vulnerable of the two technologies, with an estimated 8.56M physical qubits required to break ECDSA in 10.5 hours. Google’s Willow chip operates at 105 physical qubits, implying that an 81,523x improvement would be required for a similar attack. SHA-256 is much thornier for QCs, requiring 2.2M physical qubits (21,238x improvement over Willow) to break - in 18,000 years. Mining is not likely to be impacted significantly by QCs given what we know today.
What’s at Stake
While experts differ on the timing of when (or even if) QCs of sufficient strength will be available to break digital signatures, let’s pretend that QCs of sufficient power have arrived. There are two potential vulnerabilities: bitcoins at rest and bitcoins in transit. Bitcoins for whom their public key has been revealed, either through P2PK transactions, the earliest type of transaction types that is no longer in use, or through address reuse (of any signature type). These include Satoshi’s potentially 1M+ bitcoins, which are sitting in P2PK addresses. In total, this amounts to about 4M bitcoins (~$400B). A sufficiently strong QC could reverse the private keys for these bitcoins and move them to new addresses the attacker controls. For bitcoins in transit, whose public key has been revealed in a spending transaction, a QC would need to reverse a private key in 10 minutes to intercept these bitcoins and double spend them, again moving them to addresses the attacker controls.
Technologists Haven’t Been Sitting Down
What is to be done about these risks, however remote they may be? First, QCs pose a risk for all sorts of real-world applications that are far more important than Bitcoin – commerce, banking, government, and military, just to name a few. Second, the experts haven’t been sitting down. The NIST (National Institute of Standards and Technology) started a competition in 2016 for post quantum computing (PQC) digital signatures, and today we have 3 viable candidates. The agency is continuing the search for more candidates too, with 14 more algorithms moving on to the next phase of evaluation. For federal systems, the NIST has set a deadline of deprecating ECDSA by 2030 and disallowing it entirely after 2035, to give readers a sense of how it views the timing of transitioning to a PQC world.
Potential Solutions
Several things could be done for Bitcoin specifically to address QCs. PQC digital signature algorithms could be implemented on Bitcoin. Vulnerable bitcoins at rest could be moved to PQC addresses. Those that cannot be moved because of private key loss or because the individuals are no longer around (Satoshi) could have non-spending conditions put on them via a soft fork. These are some simple solutions, but given the inventiveness of the Bitcoin community, we are certain plenty of other options will come forth. Furthermore, this isn’t just a problem that the Bitcoin community faces, but all digital assets. General solutions may arise from other parts of the broader digital asset ecosystem as well.
Final Thoughts
QCs may conjure up bewildering visions of the future, but they also spark fears, particularly for technologies like Bitcoin. Fortunately, the risks posed by QCs are often overstated (in the case of hashing) or remain many years away (for digital signatures). Moreover, cryptographers have been preparing for a PQC world for years, and Bitcoin developers are actively addressing this challenge. Technology risks are one of the largest categories to consider when evaluating Bitcoin, and while QCs carry significant theoretical implications due to their novelty, investors can take comfort in the fact that these risks are manageable if the threat ever becomes more immediate.
