The more keys have to be replaced, the bigger the future upgrade.
We made quantum resistant smart contract wallets at anchorwallet.ca using Lamport signature.
A new version built on ERC 4337 is coming.
2 Likes
If quantum computers are already in the hands of a bad actor and are able to crack Ethereum wallets (like using Shor’s algorithm) fast enough, it would be too late, since determining a bad-actor from the actual owner of the account wouldn’t be possible.
Do not use stateful post-quantum algorithms; rather use NIST standardized ones in hybrid mode (combiner) with a classical algorithm, like Dilithium + ed25519. Ethereum have to take a significant hit on block sizes though, due to the currently standardized post-quantum dsa scheme’s large signature and public key sizes.
2 Likes
If quantum computers are in bad hand, we need a ML monitor system in the node tree to detect large transactions of unsafe/abnormal human transfer first to trigger Stark fail-safe pre-built emergence fork. Dynamic on chain fuzzing/firewall intercept protocol could be a big leap for prior the enforced fork.
3 Likes
My startup, pQCee dot com, has been working on a quantum-safe ECDSA based on the pre-image proof which is similar in design to @vbuterin post. We called it Signature Pre-image proof (SPP) and is patent-pending. It was presented at decompute 2023 (a side event from Token2049)
We started with making ECDSA signatures in PDF documents quantum-safe and our next steps include making ECDSA in Ethereum and Bitcoin quantum-safe based on the same principle. Watch out for our EIP to be available soon.
3 Likes
Hi @vbuterin, thank you for the post.
About a year ago (almost to the day, actually!), my Ph.D advisor Or Sattath and I considered the same problem, and proposed a protocol employing similar ideas – in particular using the BIP-32 derivation process for post-quantum authentication.
A preprint is available on IACR /2023/362, and our work was also presented in the PQCSM2 workshop, slides available on their website (your policy does not allow me to post links).
We flesh out ideas very similar to yours and discuss how they can be composed. Our work also includes a careful analysis of the collision resistance of BIP-32 derivation paths, as well as a security analysis of the resulting signature scheme.
The greatest difference between our approaches, I think, is that we used Picnic signatures rather than STARKs. The advantage of our approach is that gas can be paid from the spent pre-quantum account itself, but of course, the disadvantage is that the signatures cannot be batched. We propose another approach to deal with signature sizes: a protocol where the signature must only be posted to the blockchain in case of fraud attempts.
We also describe a “quantum canary” mechanism for detecting quantum adversaries (inspired by Justin Drake’s cryptographic canaries) and provide some analysis of its game theory.
You might find that our work expands and complements the ideas presented in your post.
4 Likes
Is it possible to just do an EIP upgrade whereby users have a choice to generate a totally different address/private key that is quantum resistant anytime he wants and do the transition on his own?
In this situation, we would have 2 types of addresses/keys in use; the traditional non-quantum resistant one and the newer quantum resistant one. After the quantum attack, any user who has already transitioned to using the newer keys (before the attack) need not do anything, while users who are still using the traditional one can then transition to the newer keys.
This way, I think, will create the least disruption to the network.
We have a Cryptokitty stored in a Lamport wallet since last year, see nft/0x06012c8cf97bead5deae237070f9587f8e7a266d/1850 on etherscan, stored at address 0xE1C67B7Db6eA02125D4a2d4Ec91D382dbF98E3d9
It’s impossible to move this NFT without a Lamport signature verified by the network.
So it’s already possible with the smart contract wallets on anchorwallet.ca
We are testing a version built on ERC 4337 on Sepolia currently.
1 Like
5 years ago, My team has organized one small summit to talk about this topic. The conclusion is cannot use hard fork to help the real owner take back the coins after the fork. Because there is no way to separate the owner and Q-hacker.
Hope we find the right way now.
Unlike what you think, it is actually possible. That ‘impossibility’ was already proven incorrect (by us). You can show specific one-way hashing encoding in the way you create the secret key, which the malicious actor can’t…
Also, the point of this construction is not to specify what will be the post-quantum signature scheme. But how to rollover a regular ecdsa wallet to any type of post-quantum wallet securely
While I understand this is in the hypothetical scenario of a “zero-day” quantum attack, I really don’t like the idea of having to rollback a huge number of blocks, especially given that (i) it might not be so obvious where the large-scale theft began and (ii) the hard fork has to be implemented and coordinated, taking more time where new blocks are produced that will ultimately have to be rolled back (effectively a massive liveness failure)
more on (i), picture a single large exchange wallet being drained by a quantum computer. Everyone would naturally assume it was a security failure of some kind on the exchange’s end. Or if a smart wallet relying on discrete log assumption gets drained, a smart contract bug/exploit would be the first thing that comes to mind. Or the quantum-enabled attacker avoids high profile targets altogether and slowly steals funds from various large EOAs, and we never even know a quantum attack took place
I would rather see this EIP proactively implemented today with the addition that the mechanism stays inactive until a kill switch is linked to previous ideas around “Quantum Canary” is triggered – i.e. a large enough amount of ETH sitting in a contract, secured only by a discrete log problem weaker than the ECDSA used by EOAs, but still infeasible to crack through a classical computer. If/when the ETH gets claimed, then no need for a messy emergency hard fork, since the mechanism outlined in the original post would kick in in the very next block
2 Likes
How does the solution work with EOA-based keys that were generated pre-BIP, i.e. those generated without 12/24-word seed/passphrase?
1 Like
As far as I remember, the Ethereum Foundation has a dedicated team researching this (I remain optimistic about this), and I do not think that the progress of quantum computing will pose a crisis to Ethereum in the short term. I have not researched the impact of quantum computing on Ethereum, but I have studied about Bitcoin, so perhaps I can help clarify:
Currently, the most advanced superconducting processors have only hundreds of quantum bits (qubits), and the ultra-low temperature working environment limits the processor size and prevents physical manipulation. Room temperature superconductivity (not yet achieved) will address the existing hardware expansion issues in quantum computing.
Bitcoin’s public key is vulnerable and easily attacked within a time window of approximately 10-60 minutes after a transaction is initiated. Breaking encryption within an hour requires approximately 317 million physical qubits.
Citing “The impact of hardware specifications on reaching quantum advantage in the fault tolerant regime” it states:
"We quantify the number of physical qubits needed to break encryption as a function of code loop time and basic physical error rate. Using surface codes, with a code loop time of 1 microsecond, reaction time of 10 microseconds, and physical gate error rate of 10^-3, breaking encryption within an hour requires approximately 317 million physical qubits.
If the basic physical error rate is a more optimistic value of 10^-4, then breaking encryption within an hour would require 33 million physical qubits. This significant demand for physical qubits implies that the Bitcoin network will not be threatened by quantum computing attacks for many years to come (potentially over a decade)."
Do not let “Vitalik says” become an accomplice to fraud, quantum computing cannot harm Bitcoin, let alone harm the actively innovative Ethereum.
1 Like
I’m glad to see a plan is being formed. I have a few questions.
The proposal above deals with an emergency hard fork to undo an attack.
Q1: How would the transition to a post-quantum Ethereum be changed (if at all) in case we were to perform the change preemptively? That is, if instead of having to rush a change to fix we have time to plan an ideal post-quantum solution.
Q2: How would we morph the hotfix solution proposed above into this final solution (if at all)?
The idea of the above two questions is that it’s good to have a plan to hot fix. But hot fixes usually take shortcuts and trade-offs that may not necessarily be ideal. How would the ideal solution look like and how we could migrate the hotfix to it?
Q3: The above solution deals with the use of elliptic curves for public key derivation. But Ethereum uses elliptic curves also for BLS signature aggregation and the KZG commitments. How are these impacted and what plan is there to move them to quantum resistant algorithms if needed?
1 Like
Glad to see people of such caliber thinking / planning for this – I did some basic research on this topic years ago and think there are a few difficulties which are not completely addresses by this proposal:
-
It might not be obvious when the quantum attack started (if used in a targeted way, or if the goal is to discredit the security of Bitcoin / Ethereum rather than to steal the funds of any individual accounts), similar to concerns mentioned by @domothy above
-
The social and coordination aspects of such an emergency hard-fork / pause on transactions might be thornier than they appear, and may destroy a large part of the financial value stored in BTC and ETH even if the technical aspects of relevant hard-forks are sound. With such a highly technical matter, most users will not have any idea of the cryptographic details and trusted individuals / teams (such as Vitalik) will be crucial for advocating which path to take, and there are sure to be suspicious parties and contentious decisions.
I have previously worked with the Quantum Resistant Ledger project, which has had a post-quantum XMSS-secured mainnet live for 5+ years. They are a member of the Post-Quantum Cryptography Alliance and have funded grants for research by Geometry Labs to push the frontier of post-quantum signature aggregation techniques and turn their results into an open-source implementation to be evaluated by NIST.
QRL is working to incorporate smart-contracts / EVM compatibility in their next update, and if any talented cryptographers and/or blockchain developers want to contribute to a post-quantum life-raft, collaboration with QRL and Geometry Labs might be among the most immediate / direct / open-source ways.
I love Ethereum and am not trying to shill QRL too much, but I am concerned about a sudden quantum advance destroying the credibility of blockchain networks (and/or the financial value stored in them). It doesn’t seem like the Bitcoin ecosystem takes the quantum risk seriously at this point, and with BTC being introduced into the mainstream financial system it strikes me as somewhat of a time bomb.
It seems possible that public knowledge of the SOTA on quantum computers will be lacking right up until there is some plausible “y2q” event (such as Satoshi’s BTC and other pay-to-public-key mining reward coins being moved), due to the national security implications of such technology and the incentive for relevant governments to push for secrecy around advances (even though it seems the SOTA is in the private sector).
2 Likes
Here we go @vbuterin : ERC-4337 + Lamport on Ethereum Mainnet as a browser plugin wallet.
We are doing a few more tests and we will start distributing more widely.
2 Likes
The plugin wallet Anchor Vault is now available in the Chrome Web store. The wallet is built on ERC 4337 and implements quantum resistance by using Lamport signatures.
This way it’s possible to protect Ethereum assets now @vbuterin.
We would need to switch from Verkle trees to binary trees based on STARK-friendly hash functions. It would be very beneficial to start writing that code (including the prover) asap.
Ethereum relies on Digital Signing over Elliptic Curve Cryptography (ECDSA – to represent the entire ECC family, e.g. EdDSA, BLS, Schnorr) for transaction security, with wallets storing private keys for signature creation, and nodes verifying transactions using corresponding public keys. However, with the rise of quantum computing, quantum computers could potentially break ECDSA cryptography, enabling attackers to steal assets by deriving private keys from public keys without wallet access. Estimates suggest cryptographically-relevant quantum computers could appear between 2028 and 2040, necessitating proactive mitigation strategies to safeguard Ethereum’s decentralized ecosystem.
pQCee dot com has been working on a quantum-safe ECDSA based on the pre-image proof called Signature Pre-image Proof (SPP) and is patent-pending. SPP was presented at DeCompute 2023 (a side event from Token2049). Coincidentally, in March 2024, @vbuterin wrote this post titled “How to hard-fork to save most users’ funds in a quantum emergency” which suggested a design similar to SPP.
We are excited to share a draft of an EIP that we have been working on. The proposal aims to present a solution for integrating a post-quantum signature scheme into the Ethereum blockchain while maintaining backward compatibility with existing ECDSA. The PQC signature scheme, targets integration with a quantum-safe zero-knowledge proof system such as zkSTARK or MPC-in-the-Head, to ensure the long-term security of Ethereum transactions against quantum attacks without requiring immediate upgrades to existing infrastructure.
Looking forward to your thoughts on the proposal.
I am really interested in this. Great post and topic. As I understand it, there are already quantum computers and a variety of models thereof. For example, D-Wave has adiabatic quantum computers, IBM has gate-model quantum computers, and PsiQuantum has photonic circuit board quantum computers.
Among the industry there seems to be a lot of in-fighting and competition for funding. As a result, many claim certain models are not real quantum computers. I’m more optimistic and think time will tell. In my opinion, what is important is whether there is an existing hardware-software combination that can break all classical crytpography.
I agree with you that we are already well-positioned to make a pretty simple recovery fork to deal with such a situation. I think this is an extremely insightful point.
I’m curious what led you to the conclusion that hashes are still safe, even when elliptic curves can be broken?
Overall, really brilliant analysis here.