Can Google’s Willow Crack Bitcoin?

• Blockchain Council
• December 10, 2024

Google’s Willow chip is a big step forward in quantum computing. With 105 qubits and advanced error correction, it shows how powerful quantum computers can become. This progress has led to questions about whether Willow could break the encryption that protects Bitcoin.

Bitcoin uses cryptography, like ECDSA, to keep wallets and transactions secure. As quantum computing advances, some worry that these systems might become vulnerable. This article looks at whether Willow is a real threat to Bitcoin’s security.

What is Quantum Computing?

Quantum computing harnesses the principles of quantum mechanics, the branch of physics that describes how particles behave at extremely small scales. Unlike traditional computing, which relies on bits as the smallest units of information, quantum computing uses qubits.

Qubits can exist in multiple states simultaneously, a property called superposition. This means a qubit can represent a 0, a 1, or both at the same time. Another key principle is entanglement, which links qubits together in such a way that the state of one directly influences the state of another, regardless of distance. These principles enable quantum computers to process information in ways that classical systems cannot.

Difference Between Classical and Quantum Computing

Classical computers use bits, which are binary and represent either 0 or 1. They perform calculations sequentially, one step at a time. In contrast, quantum computers use qubits, which can process multiple possibilities simultaneously due to superposition.

For example, a classical computer solving a complex problem explores all possible solutions one by one. A quantum computer, however, evaluates many solutions at the same time, drastically speeding up computations for specific tasks. This ability makes quantum computing uniquely powerful for problems that involve vast combinations or require immense computational resources.

Despite their potential, quantum computers are not replacements for classical computers. They excel at tasks like optimization problems, cryptographic analysis, and simulating quantum systems but are not practical for general-purpose computing. Classical systems remain better for day-to-day tasks due to their stability and scalability.

Google’s Willow Chip

Google’s Willow chip represents the latest breakthrough in quantum computing. It features 105 high-quality qubits, making it one of the most advanced quantum processors today. Willow builds on Google’s earlier quantum chips, like the Sycamore processor, by improving not just the number of qubits but also their reliability and performance.

One of Willow’s standout features is its exponential error correction capability. Quantum systems are notoriously prone to errors because qubits are highly sensitive to external disturbances. Willow addresses this issue with advanced error correction algorithms. These algorithms detect and correct errors in real time, allowing the chip to perform computations more reliably as the number of qubits scales up.

Key Achievements of Willow

Exponential Error Correction

Willow achieved a long-standing goal in quantum computing: operating “below threshold.” This means its error correction mechanisms reduce errors faster than they accumulate. Researchers demonstrated this by arranging qubits in grids of increasing size—3×3, 5×5, and 7×7—and observing that error rates dropped by half with each step. This breakthrough has been pursued for nearly 30 years.

Record-Breaking Computation Speed

In one benchmark, Willow solved a computational problem in under five minutes. This task, designed as part of Random Circuit Sampling (RCS), would have taken one of the fastest classical supercomputers approximately 10 septillion years to complete. RCS serves as a benchmark to test whether a quantum computer can perform genuinely quantum tasks that classical systems cannot replicate.

These achievements demonstrate that Willow not only improves quantum computing’s theoretical foundation but also delivers tangible results. Its performance highlights the potential of quantum processors to solve problems that are impossible for classical systems.

Real-World Implications and Benchmarks

Willow’s advancements hold promise for several real-world applications, although the chip is still in an experimental stage. Key areas where quantum computing could make an impact include:

• Drug Discovery: Quantum computers can simulate molecular interactions more accurately than classical systems. This capability could accelerate the development of new medicines.
• Material Science: Willow’s ability to simulate quantum systems could lead to the discovery of more efficient materials for energy storage and electronics.
• Artificial Intelligence: Quantum processors can optimize machine learning algorithms, making AI systems faster and more efficient.

Despite these possibilities, it’s important to note that Willow has not yet demonstrated practical applications in these fields. The chip excels at benchmarks like RCS, but scaling quantum systems for real-world use remains a significant challenge. Achieving practical quantum applications will require further advancements in qubit count, stability, and error correction.

Bitcoin’s Cryptographic Security

How Bitcoin’s Security Works

Bitcoin’s security relies on robust cryptographic algorithms to ensure the integrity and authenticity of transactions. Two key components in this framework are the Elliptic Curve Digital Signature Algorithm (ECDSA) and the Secure Hash Algorithm 256 (SHA-256).

Role of ECDSA and SHA-256 in Bitcoin

ECDSA is crucial for generating digital signatures in Bitcoin transactions. When you initiate a transaction, your private key signs it, creating a unique signature. This signature can be verified using your public key, confirming that the transaction hasn’t been altered and is indeed authorized by you. This mechanism ensures that only the rightful owner can authorize the movement of their bitcoins.

SHA-256, on the other hand, functions as a cryptographic hash algorithm. It takes an input and produces a fixed-size string of bytes. In Bitcoin, SHA-256 serves multiple purposes:

• Mining: Miners compete to find a hash value below a certain target by varying a nonce in the block header. The first miner to achieve this adds the block to the blockchain and earns a reward.
• Address Generation: Bitcoin addresses are derived by hashing public keys using SHA-256 followed by RIPEMD-160, providing a shorter representation for ease of use.

This dual application of SHA-256 ensures both the security and efficiency of the Bitcoin network. To know more about Bitcoin and how it works, consider enrolling into the Certified Bitcoin Expert™ certification.

Difficulty of Breaking Bitcoin Encryption with Classical Computers

The security of ECDSA hinges on the complexity of the Elliptic Curve Discrete Logarithm Problem (ECDLP). Solving ECDLP involves determining the integer kkk in the equation P=kGP = kGP=kG, where PPP and GGG are points on an elliptic curve. For classical computers, this task is computationally infeasible, especially with the key sizes Bitcoin employs.

Similarly, SHA-256 is designed to be collision-resistant, meaning it’s extremely unlikely for two different inputs to produce the same hash output. Classical computers would require an impractical amount of time and resources to find such collisions or reverse-engineer the original input from a hash.

Theoretical Vulnerabilities to Quantum Computing

Quantum computing introduces potential vulnerabilities to cryptographic systems like Bitcoin’s. A notable quantum algorithm, Shor’s algorithm, can efficiently solve problems that are hard for classical computers, such as integer factorization and discrete logarithms.

Shor’s Algorithm and Its Implications for Breaking Cryptographic Systems

Shor’s algorithm can solve the discrete logarithm problem in polynomial time, effectively undermining the security of ECDSA. This means that a sufficiently powerful quantum computer could derive private keys from their corresponding public keys, compromising the authenticity of digital signatures.

Requirements for a Quantum Computer to Crack Bitcoin

To break Bitcoin’s encryption within a feasible timeframe, a quantum computer would need a substantial number of qubits. Estimates suggest that approximately 317 million physical qubits are necessary to crack a 256-bit ECDSA key within an hour, considering error correction and operational stability. Current quantum computers are far from achieving this scale, indicating that, for now, Bitcoin’s cryptographic defenses remain secure.

Can Willow Crack Bitcoin?

Current Capabilities of Willow

Google’s Willow chip has brought a new level of capability to quantum computing. It represents a significant advancement in terms of both hardware and software. To understand its impact, we’ll explore its qubit count, error correction breakthroughs, and specific benchmarks. 

Qubit Count and Its Limitations

Willow features 105 qubits, a modest number compared to what is needed to revolutionize quantum computing fully. While this may seem small, quality matters more than quantity in quantum computing. Each of Willow’s qubits is engineered for reliability, with longer coherence times and better stability than previous chips. Coherence time refers to how long a qubit can maintain its quantum state without interference. Willow’s qubits achieve nearly 100 microseconds of coherence, a significant improvement over earlier chips like Sycamore, which only reached about 20 microseconds.

However, this limited number of qubits also imposes restrictions. Complex computations, such as those needed to break advanced cryptographic algorithms, require millions of error-corrected logical qubits, which are formed by combining physical qubits. Since Willow uses 105 physical qubits, the gap to achieving this scale is still substantial. While Willow is groundbreaking, it is not large or stable enough for many real-world applications yet.

Error Correction Breakthroughs and What They Mean

Quantum computing has always faced the problem of errors. Qubits are highly sensitive and prone to losing their quantum state due to environmental interactions. This issue, known as “quantum decoherence,” leads to errors that disrupt calculations.

Google’s Willow addresses this challenge with a key achievement: exponential error suppression. This means that as the chip scales up with more qubits, the error rate decreases significantly. For instance, Google tested qubit grids of different sizes—3×3, 5×5, and 7×7—and found that each step reduced errors by half. This process has been a goal in quantum error correction for nearly three decades.

The team achieved this using innovative hardware and machine-learning algorithms. These algorithms detect errors in real time and correct them before they affect computations. This capability allows Willow to operate “below threshold,” a landmark in quantum computing. Operating below threshold means the system’s error correction works faster than errors can accumulate. As a result, larger arrays of qubits can perform better than individual qubits. For example, Willow’s 7×7 lattice doubled the lifetime of its best physical qubit.

These breakthroughs signify progress toward building scalable quantum computers. However, the error rates are still far from what is needed for practical applications. Current systems experience about one error in every thousand operations, but real-world problems require far lower error rates.

Specific Benchmarks: What Willow Can and Cannot Do

Willow has demonstrated its capabilities through specific benchmarks, showcasing both its potential and its current limitations. One notable example is its performance in Random Circuit Sampling (RCS). This benchmark tests whether a quantum system can solve computational problems far beyond the reach of classical supercomputers.

In one demonstration, Willow performed an RCS computation in under five minutes. This task would have taken one of the fastest classical supercomputers, such as Frontier, about 10 septillion years. To put this into perspective, 10 septillion years vastly exceeds the age of the universe, which is approximately 13.8 billion years. This achievement highlights Willow’s ability to perform tasks that classical computers cannot realistically handle.

However, RCS is a highly specialized test and does not represent practical, real-world applications. While Willow excels at demonstrating raw computational power, it has not yet been used to solve problems in areas like drug discovery or material science. Real-world applications require quantum systems to handle diverse and unpredictable scenarios, which Willow is not yet equipped to do.

Moreover, the chip’s small qubit count limits the complexity of problems it can tackle. Tasks like cracking Bitcoin’s encryption or running Shor’s algorithm, which would require millions of logical qubits, are far beyond Willow’s current capabilities. For now, Willow serves as a proof of concept, showing that scaling up quantum systems can lead to better performance.

Requirements to Break Bitcoin’s Security

Breaking Bitcoin’s encryption with a quantum computer is a challenge that lies far beyond the capabilities of current technology. It requires a highly advanced quantum system, much larger and more stable than what we have today.

Number of Qubits Needed for Shor’s Algorithm to Crack Bitcoin’s Encryption

Bitcoin’s security relies on Elliptic Curve Digital Signature Algorithm (ECDSA), which uses the elliptic curve discrete logarithm problem (ECDLP). This problem is incredibly difficult for classical computers to solve, but quantum computers could theoretically break it using Shor’s algorithm. Shor’s algorithm can factorize large numbers and solve discrete logarithm problems efficiently.

However, running Shor’s algorithm at the scale required for Bitcoin is not feasible with today’s quantum systems. Experts estimate that breaking a 256-bit ECDSA key, like the one Bitcoin uses, would require a quantum computer with millions of logical qubits. Logical qubits are error-corrected and stable, unlike physical qubits, which are prone to errors. Google’s Willow chip, with 105 physical qubits, is nowhere near this requirement.

For perspective, creating one logical qubit often requires hundreds or even thousands of physical qubits to compensate for errors. Therefore, achieving the millions of logical qubits needed would require scaling up to billions of physical qubits.

Logical Qubits vs. Physical Qubits

The distinction between logical and physical qubits is critical. Physical qubits are the raw building blocks of a quantum computer. They are fragile and prone to errors caused by environmental noise, interference, and instability. While Willow has 105 high-quality physical qubits, it does not yet have logical qubits that are fully error-corrected.

Logical qubits are formed by grouping many physical qubits together, using error correction algorithms to reduce instability. This process is resource-intensive. Current quantum computers, including Willow, focus on improving physical qubit quality and error correction techniques to eventually create reliable logical qubits. Google’s recent achievement of “below threshold” operation, where error correction outpaces error generation, is a step toward this goal. However, it is still far from creating the millions of logical qubits needed to break Bitcoin’s encryption.

Computational Stability and Scalability Challenges

Scaling up quantum systems introduces significant challenges. As the number of qubits increases, so does the potential for errors. Without robust error correction, computations become unreliable. Google’s Willow chip addresses this issue by achieving exponential error suppression, cutting error rates in half with each increase in qubit grid size. This breakthrough allows the system to perform better as it scales, a milestone researchers have pursued for decades.

Despite this progress, stability remains a challenge. Quantum computations for tasks like breaking Bitcoin’s encryption require extremely low error rates—much lower than what current systems can achieve. Today’s quantum systems experience errors in about 1 out of every 1,000 operations, but practical applications demand error rates closer to 1 in a billion or lower. Achieving this level of stability will take years of further development.

Comparison of Willow’s Capabilities and Bitcoin’s Encryption Needs

Willow’s Performance Versus Requirements for Bitcoin Decryption

Willow’s performance is impressive, but it falls far short of the requirements to break Bitcoin’s encryption. The chip’s 105 qubits and advances in error correction make it a leader in quantum computing, but this is still a small fraction of what is needed for tasks like running Shor’s algorithm on Bitcoin’s 256-bit ECDSA keys.

Experts estimate that running Shor’s algorithm to break Bitcoin’s encryption would require 13 million logical qubits to perform the necessary calculations within 24 hours. Willow’s qubits are physical, not logical, and achieving logical qubits would require orders of magnitude more resources. Additionally, the computational complexity of this task demands stability that Willow cannot yet provide.

While Willow excels in benchmarks like Random Circuit Sampling, these tests focus on specific computational tasks that showcase raw quantum power. They do not translate to practical applications like breaking cryptographic keys. Willow’s achievements are important steps forward, but they are not a direct threat to Bitcoin’s encryption.

Timeline Estimates for Achieving Necessary Quantum Computing Capabilities

The timeline for developing a quantum computer capable of breaking Bitcoin’s encryption remains uncertain, but experts agree it will take at least 10 to 20 years. Several factors contribute to this timeframe:

• Scaling Up Qubits: Building millions of error-corrected logical qubits requires breakthroughs in both hardware and software. Current systems are still in the experimental stage.
• Error Correction Advances: Willow’s error correction demonstrates exponential improvement, but error rates must drop far lower for practical applications. This process will require sustained innovation.
• Practical Stability: Quantum computers must handle long computations without failure. Current systems cannot maintain stability over the timescales required for large-scale cryptographic tasks.
• Research and Development Pace: Companies like Google, IBM, and Microsoft are making significant progress, but scaling quantum systems is a slow and resource-intensive process.

While Willow’s advancements are promising, they are a small step toward the large-scale quantum systems needed to threaten encryption algorithms. In the meantime, researchers are developing quantum-resistant cryptographic algorithms to protect systems like Bitcoin from future quantum threats.

Future Risks to Bitcoin

Quantum computers pose a broader threat to cryptographic systems beyond Bitcoin. One of the most widely used encryption protocols, RSA (Rivest-Shamir-Adleman), relies on the difficulty of factoring large numbers. Shor’s algorithm, a quantum computing method, can solve this problem efficiently, making RSA vulnerable to quantum attacks.

RSA encryption secures financial transactions, credit card data, and sensitive communications. A quantum computer capable of factoring RSA keys could undermine the security of global financial systems, leaving bank transactions, online payments, and other systems exposed. For example, RSA-2048 encryption, which protects many banking systems, could theoretically be broken by a quantum computer with millions of logical qubits.

Implications for Blockchain and Other Decentralized Technologies

Blockchain technology relies on cryptographic algorithms to ensure data integrity and secure transactions. In Bitcoin, for instance, the Elliptic Curve Digital Signature Algorithm (ECDSA) secures private and public keys. Quantum computers with sufficient power could reverse-engineer private keys from public ones, potentially allowing unauthorized access to wallets.

Ethereum and other decentralized platforms face similar risks. Smart contracts, decentralized applications, and other blockchain functionalities rely on secure cryptographic methods. Without adequate protection, these systems could become vulnerable to exploitation in a post-quantum world.

Post-Quantum Cryptography

Research into Quantum-Resistant Cryptographic Algorithms

To address these risks, researchers are actively developing post-quantum cryptography. These algorithms aim to secure data against both classical and quantum attacks. Unlike current cryptographic methods, post-quantum algorithms rely on problems that even quantum computers cannot easily solve, such as lattice-based cryptography and hash-based signatures.

Organizations like the National Institute of Standards and Technology (NIST) are leading efforts to standardize quantum-resistant algorithms. NIST is currently in the final stages of selecting algorithms that could replace vulnerable encryption protocols. These developments are critical for ensuring the long-term security of digital systems.

Actions Being Taken by the Bitcoin and Broader Crypto Community

The cryptocurrency community is aware of the potential threat quantum computing poses. Developers and researchers are working on solutions to protect Bitcoin and other blockchains. Some key initiatives include:

• Quantum-Resistant Forks: Proposals for hard forks that would replace vulnerable algorithms with quantum-resistant ones. For Bitcoin, this would involve updating ECDSA with post-quantum cryptography.
• Educational Awareness: Prominent figures like Vitalik Buterin, co-founder of Ethereum, have publicly discussed the importance of addressing quantum risks early. By raising awareness, the community is building momentum for proactive measures.
• Testing Post-Quantum Algorithms: Developers are experimenting with quantum-resistant cryptographic methods in blockchain environments. These tests aim to ensure that systems remain secure even as quantum technology evolves.

Mitigation Strategies for Bitcoin

As quantum computing advances, concerns about its potential to compromise Bitcoin’s security have intensified. Quantum computers could, in theory, break the cryptographic algorithms that protect Bitcoin transactions. To counter this threat, the development of quantum-resistant algorithms is crucial.

Developing Quantum-Resistant Algorithms

Quantum-resistant, or post-quantum, cryptographic algorithms are designed to withstand attacks from quantum computers. These algorithms rely on mathematical problems that remain difficult for quantum computers to solve. Notable examples include:

• Lattice-Based Cryptography: Utilizes complex geometric structures called lattices. Algorithms like CRYSTALS-Kyber and CRYSTALS-Dilithium fall into this category.
• Hash-Based Cryptography: Employs cryptographic hash functions to create secure signatures. The Merkle signature scheme is a prominent example.
• Code-Based Cryptography: Relies on error-correcting codes. Classic McEliece is a well-known algorithm in this group.

Implementing these algorithms in blockchain networks like Bitcoin presents challenges. Quantum-resistant algorithms often require larger key sizes and more computational resources, which can affect network performance and scalability.

Hard Forks and Network Upgrades

To integrate quantum-safe cryptography, Bitcoin would need a hard fork—a significant change to its protocol. This process involves:

• Updating the Core Protocol: Developers would replace the existing Elliptic Curve Digital Signature Algorithm (ECDSA) with a quantum-resistant alternative. For example, lattice-based or hash-based cryptography could become the new standard.
• Community Consensus: A hard fork requires agreement among miners, developers, and users. Without consensus, the network could split, creating two separate blockchains.
• Wallet and Node Updates: Users would need to update their wallets and nodes to support the new cryptographic methods. This ensures that transactions remain secure and compatible with the updated network.
• Migration Plan: The network would need a clear plan to migrate existing wallets and keys to the new system. This might involve generating new quantum-resistant keys for users and mapping them to their existing balances.

Potential Disruptions and User Responsibilities During Such Transitions

Implementing a hard fork to introduce quantum-safe cryptography could cause disruptions:

• Temporary Network Downtime: The network might pause operations during the upgrade to ensure a smooth transition.
• User Participation: Users would need to actively update their wallets and software to remain part of the upgraded network. Those who fail to upgrade could lose access to their funds or become vulnerable to attacks.
• Split Chain Risk: If the community does not reach consensus, a chain split could occur. This would result in two separate versions of Bitcoin, potentially confusing users and diluting the network’s value.

Community Preparedness and Adaptability

The Bitcoin community has historically shown resilience to technical challenges. Proactive measures are essential to secure the crypto ecosystem against emerging threats like quantum computing. For example:

• SegWit Upgrade: In 2017, the community implemented Segregated Witness (SegWit) to improve scalability and reduce transaction malleability. Despite initial resistance, the upgrade was successful due to strong community support.
• Taproot Activation: In 2021, Bitcoin introduced Taproot to enhance privacy and enable more complex smart contracts. The upgrade demonstrated the community’s ability to coordinate and adopt new features.

Ongoing research and development in post-quantum cryptography demonstrate the community’s commitment to maintaining Bitcoin’s security and trustworthiness

Conclusion

Google’s Willow chip is impressive, but it cannot crack Bitcoin’s encryption. To break Bitcoin, a quantum computer would need millions of logical qubits. Willow, with its 105 physical qubits, is far from this capability.

Experts believe it will take at least 10 to 20 years for quantum computers to reach the level needed to challenge Bitcoin’s cryptography. In the meantime, researchers and developers are creating quantum-resistant algorithms to keep Bitcoin safe. For now, Willow shows the potential of quantum computing, but Bitcoin’s security remains intact.