How would all of this be affected if EC-based Verkle tries are included in the picture? @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.