Proposed PQ upgrade for ecrecover

Cryptography
,
1

Proposed PQ hotfix for ecrecover

Many EVM contracts deployed today use ecrecover to verify ECDSA signatures and are thus vulnerable to quantum attacks. Rather than completely disabling the ecrecover opcode, we can update ecrecover to read post-quantum signatures from EIP-8141 frame transactions. The 65-byte signature (v, r, s) can be used to encode lookup values. A sentinel value would trigger the new lookup path instead of the original ECDSA recovery. This would create a graceful migration path for immutable deployed contracts. This proposal does not aim to fix EOA accounts themselves.

Backwards compatibility constraints

  1. The EVM defines ecrecover as a pure function. Any lookup of public key, claimed account, signature, and verification function must not break deployed bytecode or the compiler.

  2. The EVM checks that bytes32 r < n; any value encoded in r should start with a 0x00 byte.

  3. OpenZeppelin’s ECDSA.tryRecover in version 4.7 or earlier also checks that v ∈ {27, 28} and s < n/2.

  4. EIP-7702 delegates can send transactions on behalf of an EOA, but they cannot sign gasless permits and authorizations such as EIP-3009. The update to ecrecover should not unexpectedly allow this.

Proposed solution

This post is a high-level proposal that leverages EIP-8141, with the understanding that EIP-8141 will undergo significant change. The final version of EIP-8141 will likely include a pure verification function with a canonical authenticator set.

Sentinel values. Propose v = 27, s = 0 as the sentinel value to trigger the new execution path. The combination v = 27, s = 0 respects early OpenZeppelin-based contracts that enforce v ∈ {27, 28} while clearly identifying a new execution path, since a valid ECDSA signature will never have s = 0.

Lookup. The lookup information can be encoded as:


r = 0x00 || signatureIndex (11-byte) || verificationFunctionId (20-byte)

The leading 0x00 byte ensures r < n. The bytes11 signatureIndex allows for 2^88 signatures — more than can possibly be included in a frame transaction due to the gas ceiling. The bytes20 verificationFunctionId can be either a fixed enum used to call a pure signature verification function, or a lookup into a hash table inside a fixed key-registration precompile (which is treated as pure).

Claimed address. The claimed address must authorize the public key. A few options:

  • EIP-8164 (where account code becomes 0xef0101 || pubkey).

  • EIP-7932 that defines valid EVM addresses as hash of public key.

  • EIP-8130, which creates a designated Keystore contract.

The challenge here is to preserve pure verification. The design would depend on the final form EIP-8141 takes and/or adoption of above EIPs.

Signature verification. The EIP-8141 tx.signature[] is an array, and each entry contains a scheme, signer, msg and signature (which may contain public key). The expected invariant is that each signature is valid on msg.


scheme = ARBITRARY

signer = (empty)

msg = h

signature = pk || signature

EIP-8141 expects that len(signer)=0 for ARBITRARY schemes. There is an expected invariant that signature is valid on msg, hence ecrecover(h,...) must check that msg==h and the that verifySignature(pk, msg)==true. Signature verification will also need to check that claimed authorizes pk (using a TBD mechanism above).

Output. The function ecrecover would return claimed on success or address(0) on failure.

Alternative approaches

  • Use a sentinel value such as v = 29 that is not a valid ECDSA value. This is cleaner than v = 27, s = 0, allows data to be encoded inside both r < n and s < n/2, and creates a path for future upgrades with different sentinel values of v. However, it breaks older OpenZeppelin-based smart contracts.

  • Encode a claimed address in (v, r, s) or tx.signature and leverage ERC-1271 to STATICCALL into claimed.isValidAuthorization(). This creates a way for an existing ECDSA address to authorize a public key. However, ERC-1271 isValidAuthorization() is a view function that may break the expected behavior of ecrecover. It would also allow an EIP-7702 delegate to sign EIP-3009 transferWithAuthorization requests. Finally, if isValidAuthorization calls APPROVE, it can result in approving the entire frame transaction when the intent was to check a specific signature.

  • Include the public key inside the frame-transaction signature and compute the claimed address as a hash of the post-quantum public key. This would create a pure mechanism for claimed to authorize the public key and pass the ecrecover check. However, any ETH or tokens accidentally sent to such an address may become unrecoverable since claimed would not be a valid ECDSA address.

4 Likes
2

The sentinel + EIP-8141 framing is a clean way to add a PQ verification path without disabling ecrecover, and keeping (v=27, s=0) as the trigger is a nice use of the fact that valid ECDSA never has s = 0. One thing I’d surface, because it’s orthogonal to verifying a PQ signature and I think it’s load-bearing for whether the upgrade actually protects a migrated account:

Adding a PQ path does not retire the classical one, and that’s the whole attack surface. If ecrecover still accepts classical (v, r, s) for an account that has bound a PQ key, which backward compatibility requires, and which “this proposal does not aim to fix EOA accounts themselves” seems to concede, then an adversary who recovers that account’s ECDSA key post-Q forges a classical signature and spends through the unchanged classical path. The PQ binding bought nothing for that account, because the classical key was never made non-authoritative.

Verifying a PQ signature and retiring the classical key are two different problems; this proposal (and, as far as I can see, the key-binding EIPs it defers to, 8164 / 7932 / 8130) solve the first and leave the second implicit.

So the missing primitive is a per-account temporal cutoff: as of the point account X’s PQ binding is established, X’s classical key is no longer authoritative, and, critically, a verifier that does not know about the binding must fail closed, not silently fall back to the classical path (otherwise the
downgrade is a lookup miss away). That requires the cutoff time to be independently witnessed, so it can’t be back-dated or omitted; “when was the binding anchored” has to be as recomputable as “is the PQ signature valid.”

There is prior application-layer work on exactly this half of the problem that may be useful as a reference, and is complementary rather than competing, it sits above the precompile, at the consumer/authorization policy layer, and needs no consensus change:

The point of raising it here isn’t to substitute for a precompile, a consensus-layer PQ verification path is clearly the right long-term home. It’s that whichever layer verifies the PQ signature, something has to own the statement “the classical key for this account is retired as of T, witnessed, fail-closed on omission,” or the migration is a downgrade waiting to happen. If it’s useful, I’m happy to share the cutoff / temporal-authority semantics and vectors, and to look at where that policy would naturally attach in the 8141 / 8164 / 7932 / 8130 stack.

1 Like
3

I think you got the threat model kind of backwards. CRQPs can solve d-logs and recover private ECC keys from the corresponding public keys, so the ECDSA signers are vulnerable, not the verifiers. Once the private key is discovered the CRQP operator can generate valid signatures for ecrecover to verify, so there’s no “vulnerability” in ecrecover itself – it’s just that the private keys will be discovered.

Messy. Just introduce a new opcode. ecrecover was intentionally named after elliptic curve cryptography because it would have to be specific to elliptic curve cryptography.

4

This does not solves the backward compatibility constraint.

5

That’s a self-referential argument, the constraint is self-stated. A new opcode requires a bunch of new EIPs and lots of smartcontract upgrades, but on the other hand:

  1. it doesn’t create technical debt,
  2. it respects the original philosophy.
6

Hi @mirabelenkiy-circle, thanks for sharing this idea. I have been wondering what number of contracts would be affected by EIP-8151: Account Code Restricted ecRecover, which is currently my preferred deprecation path for ecrecover.

I’m a bit apprehensive of this proposal, because ecrecover is a tricky and special operation. As you know, we have a collision of meaning: on one hand, ecrecover is a standard cryptographic operation where we recover the address from a signature. On the other, we often see it as an authenticator to determine if a certain operation is allowed (i.e. transfer a balance owned by the key). Using a sentinel value here recover a address that is expected to originate from an ECDSA key pair would require us to think about a lot about probability of the address derivation scheme for a different crypto system to collide with ECDSA. The gain here also feels minimal since ecrecover is often used to simply circumvent the fact that accounts today can’t easily batch operations together.

Are there specific contracts or widespread use cases that you think are broken by EIP-8151? That would help determine how critical it is we retain some functionality here. Your general idea seems workable. In the past, we had the idea that ecrecover could just call claimed with the signature to see if the account can verify the signature or not. I would probably lean in that direction so that the account code remains the defacto authority on the account.

2 Likes
7

I like the idea of EIP-8151 - using EIP-7702 code, but its approach to ecrecover seems to actually make things worse for an account that upgrades to post-quantum.

A typical ERC-2612 permit or ERC-3009 transferWithAuthorization would perform ecrecover and accept the returned address as the signer. Once this authentication step is done, it performs the requested transfer.

EIP-8151 ecrecover checks if the signer upgrades to add EIP-7702 code and returns the signer address without executing the verification code. This means the smart contract would assume the signature is valid and execute the requested transaction.

Please let me know if I misunderstood.

8

An account with a 7702 delegation is not PQ secure since the EOA key remains active for the account. That’s why ecrecover still works for it. With the use of SETCODEFROM a 7702 account can fully migrate to become a normal contract, which cannot use ecrecover.

9

I’m raising a concern here: in short, users cannot select a signature threshold higher than half, as this would lead to a DoS

That is incorrect. This opcode does not make the account completely immune to `ecrecover`. The account identity remains unchanged, so any `ecrecover` operation involving address `0x01` can bypass EIP-3541. In reality, no contract on the network is capable of rejecting `0x01` until EIP-8151 is implemented.

10

Losing control of the keys in a multisig seems like the real issue here, not EIP-8151.

Sorry this doesn’t make sense. If an 7702-delegated account uses SETCODEFROM(source) it changes its code from 0xef0100… directly into the code source, at which point it can no longer use ecrecover under the EIP-8151 rules. Obviously this requires both 8151 and 8298 to be active.

11

Coming back to this now that the thread’s settled onto the retirement question, which I think is the right place for it to be.

The move toward EIP-8151 (code-restricted ecrecover) + EIP-8298 (SETCODEFROM) is, for accounts that fully migrate, a stronger form of what I was pointing at in #2 than an application-layer cutoff: it makes the classical key non-authoritative by construction, the account is no longer an EOA, so ecrecover can’t return its address at all. If an account gets there, that’s the cleanest possible retirement, and I’d defer to it.

Where I’d push is that “did the account’s code change?” is a binary, local fact, and retirement in practice has a temporal and a consumer dimension that it doesn’t answer:

  1. The window. Until 8151+8298 are active, and until a given account actually runs SETCODEFROM, the classical path is authoritative. A consumer reading state at a different height, or off-chain, needs to know not just whether the key is retired but as of when, and needs that answer to be non-back-dateable. That’s an independently-witnessed cutoff, which the code-change fact alone doesn’t provide.

  2. Fail-closed-on-omission which is exactly the ERC-2612 / ERC-3009 bypass @mirabelenkiy-circle raised in #7. A verifier that doesn’t know an account has bound a PQ key, and honors a classical permit for it, is the silent downgrade. The property that closes it is: unknown binding → fail closed, never fall back to the classical path. That has to be stated somewhere explicit, or the downgrade is a lookup-miss away regardless of which consensus mechanism wins underneath.

Both of those sit at the consumer/authorization-policy layer, above the precompile, and need no consensus change, so they compose with 8151/8298 rather than competing with them. That’s the half ERC-8373 (Post-Quantum Anchored Key-Binding) specifies: the classical→PQ binding is anchored on-chain, the anchoring tx is itself the classical proof-of-possession, and consumers apply an anchor-time cutoff, anchor time over signature time, omission fails closed, verified by recomputation rather than a per-tx second signature. The temporal-authority model (which epoch a key is in-force for, and the fail-closed reconstruction rule) is specified separately with conformance vectors.
discussions-to: https://ethereum-magicians.org/t/post-quantum-migration-for-on-chain-identity-an-anchored-key-binding-a-cutoff-verified-by-recompute-not-a-second-signature/29225

Net: whichever layer ends up verifying the PQ signature and whichever mechanism (8151/8298 or otherwise) enforces retirement on-chain, something still has to own “classical key for X is retired as of T, witnessed, fail-closed on omission.” Happy to map where the anchor-time cutoff would naturally attach across the 8141 / 8151 / 8298 stack, and to share the temporal-authority vectors if useful.