Optimized FORS signing through caching

Where this comes from

In the context of the Ephemeral Keys Protocol, instead of ECDSA, the account uses a hash-based few-time signature scheme (FORS+C) and burns a brand-new key on every transaction while the user's address never changes.

That rotation is part of what makes the wallet quantum-safe, but it also creates a practical problem: Generating a FORS key means building a small forest of hash-trees and grinding a counter, on the order of a couple thousand Keccak operations for the current parameters (K = 26,A = 5). On a laptop or phone that finishes in a few milliseconds, but the protocol also has to run on constrained hardware: a hardware wallet's secure element, where Keccak runs in software on a processor clocked in the tens of megahertz. There building one fresh signer can stretch into seconds, and with more conservative parameter sets into minutes.

Those seconds take place during the confirmation screen, while the user waits to approve and sign a transaction. If the wallet only starts building the next key after the user taps confirm, every transaction carries a stall. The two-forest cache removes that stall by doing the slow work ahead of time, in the background, so the next key is already built when it is needed.

The onchain contract

Everything the device does serves one onchain rule. The smart account stores a single owner address, and every successful UserOp rotates that owner to the nextOwner carried in the tail of the transaction's calldata:

current FORS signer authorizes UserOp i
UserOp i calldata ends with nextOwner
account.validateUserOp verifies current owner, then owner = nextOwner

Each transaction therefore does two jobs: it proves the current key and commits to the next one, providing the next signer inside the hash being signed.

A FORS forest here means the full signer material for one FORS public key: the secret seed skSeed, the public seed pkSeed, all the per-tree nodes needed to extract authentication paths, the compressed public root pkRoot, and the Ethereum-style owner address derived from that public key. A forest is ready when the device holds all of that and can sign immediately.

The core optimization logic

Keep two forests ready at all times, and start growing a third after you sign a transaction and delete one of the two stored forests.

One forest is the current signer, the one that can authorize the next transaction, while the other is the next signer, whose address gets written into that transaction as nextOwner. As soon as a signature goes out, the device starts building the forest after next in the background, so that by the next confirmation screen there is again a built spare waiting.

current: full forest for the signer that can authorize the next UserOp
next:    full forest whose address will be appended as nextOwner

The cache is only an offchain convenience for the device. The contract neither knows nor cares that it exists, it checks that the current owner signed and that the appended nextOwner is nonzero.

The default pipeline

Take the device in steady state, partway through a long run of transactions. Call the current signer S_i and the next one S_{i+1}. Just before signing UserOp i, the state looks like this:

chain owner        = address(S_i)
cache current      = S_i, full forest ready
cache next         = S_{i+1}, at least address ready, ideally full forest ready

Signing UserOp i runs through a careful sequence:

1. Build callData = account call || bytes20(address(S_{i+1})).
2. Compute userOpHash.
3. Atomically burn S_i.
4. Produce the FORS signature from cached S_i tree nodes.
5. Return the signature to the host.
6. Mark S_i as PENDING_ONCHAIN.
7. Start building S_{i+2} in the background.

The order of steps 3 and 4 matters: the device commits to never reusing S_i for a fresh signature before it releases a single byte of it. That burn-before-sign rule has a cost, covered below.

Once UserOp i lands onchain, the device tidies up:

1. Mark S_i as RETIRED.
2. Promote S_{i+1} to current.
3. Promote S_{i+2} to next once its address and forest are ready.

The address of S_{i+1} must be known before UserOp i can be signed, because that address is part of the signed userOpHash, and a hash cannot be signed before it is complete. The full forest for S_{i+1} does not need to exist yet, it only has to be ready in time to sign UserOp i+1. The minimum the cache needs to keep moving is the current forest fully built plus the next signer's address. The full forest for S_{i+1} needs to be computed though to compute the address of S_{i+1}, so if the device has enough storage, keeping it would save duplicate computations.

Building the spare in the background

The device should start building S_{i+2} right after releasing the signature for UserOp i. That work is independent of the signature already sent, it touches none of the current key material and can run whenever the device has spare cycles.

If the user needs to sign another transaction too soon, the next confirmation screen arrives before S_{i+2} is built. In this case the device should first build the needed material, making the user wait the necessary time. This caching trick only saves time if time between transactions is long enough to build the forests.

When a transaction slips

Say the device burns S_i, releases the signature, and the UserOp never lands. Maybe the mempool drops it, or the bundler swaps it out. The chain still expects a signature from S_i, but the device has already marked S_i spent.

There are three possible responses:

rebroadcast same UserOp:
  Safe. No new signature is produced and no additional FORS material is leaked.

replacement UserOp with same signer:
  Counts as a reuse of S_i. Permit only inside an explicit small reuse budget,
  for example maxReuseCount = 2 or 3. With the FORS parameters mentioned the
  signature is usable up to 5 times with reasonable security. 

recovery/spare path:
  Use if the reuse budget is exhausted or local state is ambiguous.

Rebroadcasting is the mild case: the same signed bytes go out again, so nothing new is revealed and there is no real reuse. A replacement transaction counts as a second use of S_i, so it has to be metered: allowed only within a small explicit budget. If that budget is spent, or the device cannot tell what the chain has seen, it falls back to a dedicated recovery path instead of improvising.

What two forests cost in memory

For N = 16 (the hash truncation length), storing all the public tree nodes of one full FORS forest comes to:

K * (2^(A + 1) - 1) * N bytes

For the two parameter sets on the table:

Two full forests at K=26, A=5 is therefore about 51 KB.

A FORS+C variant that omits one whole tree subtracts one tree's worth of nodes:

(2^(A + 1) - 1) * N bytes

which is 1,008 B at K=26, A=5.

Leaf secrets are a separate, optional cost. Caching them adds:

K * 2^A * N bytes

That is another 13,312 B per forest at K=26, A=5. The default is to derive leaf secrets from skSeed while signing rather than store them: caching would enlarge each forest by about half again on top of its node cost and leave more secret material on disk.

Rules to keep it safe

The cache is a device-side optimization. A few invariants keep it from drifting into unsafe territory, and the implementation must enforce them:

1. Never release a signature before the current signer is atomically marked as BURNED.
2. Never sign a new digest with a BURNED signer unless the user enters an
   explicit retry/replacement flow.
3. Never exceed the configured reuse budget for a signer.
4. Always derive nextOwner from public FORS key material:
   address = last20(keccak256(pkSeed || pkRoot)).
5. Always include nextOwner in callData before computing userOpHash.

None of the five asks the contract to trust the cache, which lives entirely on the device and is meant to speed the signing operation up.

Lifecycle of a signer

Every forest moves through the same short lifecycle, recorded in the state field of its cache entry:

READY
  signer has address and forest cache available

BURNED
  device has committed to not using this signer for normal fresh signatures

PENDING_ONCHAIN
  signature was released, but inclusion is not confirmed yet

CONFIRMED
  chain owner has rotated away from this signer and local cache may delete 
  tree nodes and keep only audit metadata

A signer starts READY, becomes BURNED at the instant of signing, sits PENDING_ONCHAIN while its transaction works into a block, turns CONFIRMED once the chain has rotated past it, at which point the device can drop the bulky tree nodes and keep only a little audit metadata.