Tidbits of post-quantum ETH

Background

Cryptographically relevant quantum computer, if built, could enable Shor’s algorithm and Grover’s algorithm. These completely break ECDSA / ECDH, and reduce hash function (& cipher) strength from 2^n2n to 2^\frac{n}{2}2n2

There are some non-obvious parts of ETH which would need to be upgraded.

What is still OK

• bip39 (pbkdf2-sha512) seems just fine

What is not OK

• bip32 hdkey derivation
  • Should be replaced by something post-quantum and better (no “non-hardened” keys)
  • New scheme could be based on HKDF (like EIP-2333), but not HKDF-SHA256
  • Alternative KDF is Blake3 in context mode (pq security is unclear)
  • The proposed scheme should support both ECC and new pq mode
• Transaction signing
  • Should be replaced by lattice-based Falcon (FN-DSA / FIPS-206),
    or hash-based Sphincs-plus (SLH-DSA / FIPS-205)
  • New keys and signatures will consume more space
  • Falcon-1024 has 1.75KB keys and 1.25KB sigs
  • SLH-DSA-256 has 128B keys and 17KB-50KB sigs
• Sender address recovery
  • It was feature of ECDSA (not available in Schnorr, for example)
  • Perhaps txs (and not sigs) should encode sender addresses
• Address format
  • Currently it’s 40 hex characters, keccak256(pubkey)
  • keccak256 should be replaced by keccak512 / sha3-512 / sha512 / blake3-512
  • How does Grover algo affect brute-forcing of addresses? Should 40 characters be upped to 80-128?
  • Longer address formats should probably use something like bech32 for checksumming & human-friendliness
  • How would new addresses interop with old addresses / EVM?
• Encrypted wallets
  • Should upgrade from AES-128 to AES-256 or chacha20
  • HMAC-SHA256 should upgrade to HMAC-SHA512 or KMAC / blake3-512 (keyed mode)
• KZG EIP-4844 verification
  • Should be replaced by a post-quantum scheme
  • Algorithms are unclear for now, any suggestions?
• EVM 0x20 opcode (KECCAK256)
  • Should be replaced by keccak512 / sha3-512 / sha512 / blake3-512
• EVM precompile for ECRECOVER
  • See address recovery above
• EVM precompiles for BN / BLS / KZG
  • Should be replaced by newer schemes (unclear which ones?)
• Consensus layer signature aggregation
  • Currently aggregates signatures of all validators once per epoch (6 mins)
  • More than 1M signatures right now?
  • Algorithms are unclear for now, any suggestions?
• Anything else?

Final thoughts

I’m confident all of these problems can be solved even in limited time. Let’s start solving them.

If such computer appears soon, it’s possible to do Vitalik’s trick (How to hard-fork to save most users’ funds in a quantum emergency): freeze all accounts and leverage BIP39 with ZK-proofs to recover funds into new pq scheme.