Post-Quantum Readiness for EdDSA Chains and a Possible Solution for Some ECDSA Wallets - Part 2

This is the second part of a 2 part series. Part 1 can be found here.

We want to authorize future transactions for the same address using a post‑quantum scheme, with one action. The paper proposes two patterns for EdDSA accounts:

You produce a non‑interactive, post‑quantum‑sound zero‑knowledge proof such as a STARK. The proof’s witness is your seed. The public inputs are your address and a post-quantum public key (call it pqpk). Inside the proof, you derive sk, derive pk, derive the address, and check it equals the public address. Then you bind pqpk to that identity.

The chain verifies the proof and stores address → pqpk (or a commitment). From then on, validators or verifiers accept post-quantum signatures under pqpk for that address.

Pseudocode

// Public data: address, pqpk
// Private: seed

h = SHA‑512(seed)
sk = HashToScalar(h[:32])
pk = sk · G
addr = AddressEncode(pk)
assert addr == address
// bind pqpk with a domain‑separated hash:
hx = Hash(“PQ‑certify” || address || pqpk || seed)
// Output, a NIZK that these checks hold. The verifier never sees seed or pk.

One implication of pattern 1, is that it is stateful. Somewhere, somehow there must be a quantum resistant mapping from address → pqpk in order to keep track of proof-of-ownership in a post-quantum world, see yellowpages.xyz for one such example of this mapping live today. The authors propose a stateless mechanism whereby rather than registering this mapping once, each transaction carries a single proof whose witness is your seed. Inside the proof, you derive the address exactly as the pseudocode above. Then you verify a STARK-style hash signature on the transaction message using material derived from the seed. From here, the verifier would check both the proof and transaction data.

The upside of this mechanism is that there is no state, single point of failure, or need for post-quantum keys. The biggest drawback is that miners and verifiers would need to verify this proof for each transaction on chain.

Both patterns are post‑quantum‑sound under hash assumptions. Pattern 1 is easy to reason about and requires one single migration. Pattern 2 is stateless. Both look the same to end users: same address forever with post-quantum authorization from now on.

Although not covered in the paper, before Q-Day, you can get most of Pattern 1’s benefit without a proof system by doing a one-time, bidirectional commitment and anchor it to time. This is exactly how the yellowpages works today.

The user creates 2 distinct signatures:

1. legacy → post-quantum. The user signs a commitment with their current ECDSA/EdDSA key that binds their address to a post-quantum public key.
2. Post-qauntum → legacy. Using the post-quantum key, the user signs a reciprocal statement that names the legacy address.

Both signatures plus metadata are stored in an append-only, tamper-evident log with a strong timestamp. After Q-Day, verifiers treat that record as a pre-existing certification: this address had chosen pqpk before a quantum break was possible and can now authorize with post-quantum signatures.

This gives you a simple, deploy-now way to bind identity to a post-quantum key without ZK. It works for both EdDSA and ECDSA accounts.

It’s important to note that this pattern is only as strong as its timestamp mechanism and how certain we are of when a quantum computer capable of breaking 256-bit ECC comes online. Like pattern 1, it’s also important to not reveal the ECDSA/EdDSA public key, this is one of the core design advantages of the yellowpages.

Even though ECDSA doesn’t have a canonical seed → scalar at the protocol level, many wallets still follow a reproducible BIP-39 → BIP-32 path. If we prove that exact derivation inside a post-quantum-sound zero-knowledge proof and bind a post-quantum key, we can develop a wallet specific solution that could help many users. Furthermore, we could do this for the top N wallets.

We can save addresses whose provenance is known and reproducible. Think popular wallet cohorts with documented paths and users who still hold the mnemonic (and passphrase). An example of this would be Ethereum accounts at m/44’/60’/0’/0/x. Mixed paths with some non-hardened steps are still provable, but scalar coupling remains a risk; the proof helps you migrate before anything breaks. We cannot help keys from random scalars, proprietary HSM flows, or truly lost mnemonics.

There exists a mnemonic (and optional BIP-39 passphrase) such that:

1. PBKDF2-HMAC-SHA-512 yields the 512-bit seed,
2. the wallet’s documented BIP-32 path applied to that seed yields sk on secp256k1,
3. pk = sk·G encodes to the given on-chain address, and either (Pattern 1) we bind a post-quantum public key pqpk to that identity, or (Pattern 2) we verify a proof inside the transaction inside the same proof. The mnemonic, passphrase, seed, scalars, and pk never leave the circuit.

This likely requires wallet specific circuits which implement PBKDF2-HMAC-SHA-512, BIP-32 HMAC-SHA-512, secp256k1 multiplication, and address encoding directly in a STARK-like circuit with parameters per wallet.

Ethereum

Pattern 1: an on-chain registry that accepts the proof and writes a mapping from address → pqpk. From then on, the account signs with pqpk and verifiers check a post-quantum signature. This means one single migration. Pattern 2 also works and means a stateless structure however it also would require proof verification per transaction.

Bitcoin

Given Bitcoin script cannot verify a STARK, Pattern 1 is the only viable option. Create an off-chain registry like yellowpages.  Publish the proof once to bind address → pqpk. Wallets and services enforce the mapping when validating signatures in a post-quantum world. If script primitives improve later, we could potentially move verification on-chain.

Provided there is some mechanism such as sk = some_hash_function(seed), even if your pk was exposed on chain and a future quantum computer can recover sk from it, the seed is still hidden behind a quantum-resistant hash e.g SHA-512. Recovering seed is a preimage attack on a hash function, which is impractical using Grover’s algorithm provided a large enough hash function. Legacy curve material can be compromised but the root witness, the seed, remains safe.

This scheme works just the same with hybrid signatures. You could include a classical/post-quantum hybrid such as EdDSA & ML-DSA or a post-quantum/post-quantum hybrid such as ML-DSA & SLH-DSA. It should be clear from the pseudocode above how adding a second post-quantum key pair can be done.

Largely speaking, a hard-fork where users must upgrade to post-quantum keys and migrate their funds before Q-Day is still a viable option today. However, the biggest benefit of this new scheme is that it can take place post Q-Day. This is helpful for users who fail to upgrade on time, users who do not want to take action today while some of the new post-quantum signature schemes are still being thoroughly tested and audited, and users who require the same address or cannot afford to move even in a post-quantum world (think cold storage, vaults, qualified custodians etc).

• The seed is the root identity. It can never be leaked and should be kept off-line.
• Use domain separation inside hash-based proofs. E.g Hash(“PQ-certify” || address || pqpk || seed) and Hash(“Tx-auth” || chainID || network || address || nonce || tx || seed) to secure against replay attacks.
• Keep elliptic‑curve computations inside the proof. Make the only public identity the existing address. Most importantly, do not re-expose the pk as this may render funds at risk from quantum theft.
• Performance of proof generation and verification with STARKs needs further research and optimizations before implementing at this scale.

Post-quantum migration doesn’t have to mean “new keys, new addresses, break everything”. EdDSA chains already have the right structure: prove knowledge of the seed once and switch future authorizations to a post-quantum scheme without moving funds. ECDSA doesn’t share that invariant, but we can still rescue large cohorts by proving wallet-specific BIP-39/32 derivations and, pre-Q-Day, by recording cross-signed, time-anchored commitments. None of this requires a base-chain upgrade. Define the statement, keep curve material inside the proof, publish a simple address → pqpk mapping, and start with the biggest wallets. Done early, this turns “don’t upgrade” into a safe, operational path to post-quantum readiness.