Original text: Quantum computing is coming. What does it mean for Starknet?

Translation and proofreading: Starknet Chinese Community

📑 Please indicate the source for reprinting🕹️

introduction

Quantum computing has been a hot topic of discussion since the 1980s. Since then, it has been seen as a disruptive technology that is expected to completely change the field of computing. Quantum computing has the ability to solve certain complex problems in minutes or seconds that would take today's most powerful computers hundreds or even thousands of years to solve.

On the one hand, quantum computing will help us solve the great challenges of civilization, such as discovering new drugs and combating climate change. On the other hand, it has the potential to endanger all existing computer networks, including blockchain.

Following Google’s recent breakthrough in quantum computing , we thought it was necessary and timely to explain the quantum resistance of STARK proofs, the core technology developed by StarkWare and the foundation of Starknet, the Ethereum Layer 2 validity rollup .

https://starkware.co/wp-content/uploads/2024/12/Quantum-Computing-Video.mp4?_=1

First, let’s take a quick look at what quantum computing actually is.

What is quantum computing?

Quantum computing uses quantum mechanical principles such as superposition, entanglement and quantum interference to process information. It can be thought of as a way to solve problems in an extremely intelligent way by using the rules of behavior of tiny particles (such as atoms).

It would be interesting to go into depth on this extremely complex topic, but that is not the purpose of this article. However, if we try to abstract it, we can come to the following conclusion: While traditional computers perform calculations using "yes" or "no" (1 and 0), quantum computers are able to process "yes", "no" and "maybe" at the same time. This allows quantum computers to perform well in solving certain problems, such as integer factorization and drug discovery, much faster than today's most powerful computers.

Some parts of the encryption technology used to secure online information or log into a bank account will be vulnerable. The main concern is that when quantum computers come into use, security methods that currently take hundreds of years to crack may become so easy that attackers can crack them in minutes.

Google's quantum computing breakthrough

Google's new quantum computing chip "Willow" can complete a complex computing challenge in less than five minutes. According to Google, the same task would take the world's fastest supercomputer 10 to the 27th power years. This number is 700 trillion times the age of the universe.

So why hasn’t quantum computing been widely adopted yet? The answer has to do with how well quantum computers can scale up.

Instead of using bits, which represent 1 or 0, quantum computing uses quantum bits (qubits). Qubits can be in multiple states at the same time, such as 1, 0, and states in between (remember: yes, no, maybe). Qubits are prone to errors because they tend to exchange information with their environment very quickly. In general, the more qubits you use, the greater the chance of errors. To break the encryption we use in online banking, you would need a system with millions of qubits.

Currently, quantum computers have a calculation error rate of one in a thousand, far from the long-term error rate of one in a trillion required for many practical applications (such as cracking a bank account).

Google claims its researchers, who published their findings in the journal Nature , have found a way to reverse this relationship, causing errors to drop exponentially as they introduce more qubits into the system.

The research doesn’t tell us when quantum computing is expected to arrive, but it means it’s getting closer. And we can be sure that quantum computing is coming.

So, what can we do?

How do STARK proofs achieve quantum resistance?

A STARK proof is a type of zero-knowledge proof that enables a prover to prove to a verifier that a specific computation has been performed correctly without revealing any sensitive input data consumed by that computation.

Unlike other types of zero-knowledge proofs (such as elliptic curve-based SNARKs), the widely used STARK proofs have several features that make them considered quantum-resistant today:

1. STARK uses post-quantum cryptography assumptions

STARKs rely on hash functions for their security rather than the number theory structures such as elliptic curves or discrete logarithms that many SNARKs rely on. It is generally believed that hash functions (such as SHA-256 or similar functions) are resistant to attacks by quantum computers because:

• Grover’s algorithm is the most relevant quantum algorithm for attacking hash functions, and it can only provide a quadratic speedup. This means that a hash function that is 𝑛-bit secure against classical attacks will be 𝑛/2 qubit secure against quantum attacks.

• STARKs can remain highly secure in a quantum world simply by increasing the output size of the hash function.

2. No reliance on number theory problems

Many other cryptographic protocols, including SNARKs based on elliptic curve pairings, have to assume that certain number theory problems are difficult to solve, such as the discrete logarithm problem or integer factorization. These problems are extremely vulnerable to quantum attacks using Shor's algorithm, which can be solved efficiently on a quantum computer. STARKs avoid these vulnerabilities entirely by not relying on these assumptions. Instead, STARKs use more pure mathematics — algebra, probability theory, and error-correcting code theory, and the theorems that underpin the security of STARKs have been mathematically proven to be resistant to attacks by quantum computers.

3. Transparency settings

Unlike SNARKs, STARKs are "transparent," meaning they do not need to rely on trusted setups involving number theory "toxic waste" that is supposed to be buried but is in fact easily exposed by quantum computing. Instead, STARKs use publicly verifiable randomness (e.g., randomness generated by hash functions) to build their proof system. This eliminates another possible vulnerability point for quantum attacks.

4. Scalable Proof Construction

The cryptographic techniques used in STARKs, such as low-degree polynomial checks and Reed-Solomon codes, are computationally efficient and have been mathematically proven to be resistant to quantum computers. These techniques ensure that proofs can be verified quickly without relying on assumptions that could be compromised by quantum computers.

So we have established that STARK itself is quantum-resistant. What does this mean for the networks it relies on (like Starknet) and other blockchains?

Is Starknet quantum-proof?

Starknet brings massive scalability to Ethereum by moving transaction computations from Ethereum to Layer 2 and using STARK proofs to verify that these transactions were executed correctly.

Does the quantum-resistant STARK proof driving Starknet mean that the Starknet network itself is also quantum-resistant?

The answer is that there is no definitive answer yet, but it has a unique advantage in quantum resistance.

How does Starknet achieve quantum resistance?

Currently, Starknet uses the Pedersen hash function, which relies on cryptography that is vulnerable to quantum attacks. However, this is about to change as Starknet is planning to replace Pedersen with the quantum-resistant Poseidon hash function.

What about the wallet?

In addition to the network itself, another element to be evaluated is the endpoint through which users interact on Starknet: the wallet. Here, Starknet offers a decisive advantage with its native Account Abstraction .

Traditional cryptocurrency wallets are called externally owned accounts (EOA) , which are managed by a pair of private and public keys and are not built into the network. This means that if Ethereum becomes a quantum-resistant network overnight, external wallets that transact through the network will not be able to inherit its security. Wallet developers on Ethereum will have to develop new quantum-resistant wallets.

Thanks to the native account abstraction, wallets on Starknet are essentially smart contracts. They are built into the protocol itself , in other words, they are managed by the protocol's code. When the Starknet protocol adopts the Poseidon hash function and achieves quantum resistance, the code of every smart wallet on the network will also be quantum resistant.

The only vulnerability is the signature method, which can be fixed if necessary. Wallet developers on Starknet do not need to develop new wallets from scratch, they can just switch to a quantum-resistant signature method.

Ethereum is not quantum resistant. How does Starknet overcome this?

Ethereum is a proof-of-stake (PoS) blockchain. The majority of the stake used to govern the network is controlled by the EOA, which, as we mentioned above, is not quantum-resistant. Since Starknet inherits the security of Ethereum, this presents a challenge that must be addressed in order for Starknet to be quantum-resistant.

EOAs on Ethereum must be transformed into quantum-resistant accounts (such as smart contract accounts) so that Ethereum and Starknet can remain secure in the post-quantum world.

This is not an easy task, but StarkWare is willing to work with the Ethereum Foundation and other stakeholders to advance related work when quantum resistance becomes a more pressing issue.

in conclusion

The risk of quantum computing is like an asteroid hurtling toward Earth: We don’t know when it will hit, but when it does, the consequences will be beyond our imagination.

The good news is that there are steps we can take to protect against this. Today, all blockchain networks are at risk of being attacked when quantum computing arrives, but STARK proofs offer a promising solution. Thanks to their unique properties, STARK proofs provide us with a blueprint to prepare for when an “asteroid” eventually hits STARK and other blockchains. We are committed to continuously evolving STARK technology to address current and future needs.

Please follow StarkWare's X account for the latest updates.