A SPHINCS- C13 spend authorized by a zero-knowledge proof, over frame transactions

2026-09-03. Companion artifacts: noir/sphincs-c13-verify/ (circuit + generate_prover.py), js-client/contracts/src/frames/\{Stealth8141ZkAccount, Stealth8141ZkFactory\}.sol + frames/zk/SphincsC13HonkVerifier.sol (bb-generated), js-client/contracts/test/ZkAccount.t.sol, ui/scripts/\{deploy-frames-zk.mjs, e2e-frames-zk.ts\}. Follows D-022 (prefix-deploy-native-keys.md) and D-018's open item "remove spend-time linkability by binding the SPHINCS- key through a ZK proof".

1. Question and the user's framing

Given that the direct ML-DSA verify costs 13.7–14.9 M gas and precompiles are not the way: prove the post-quantum verification inside a circuit and spend with the proof. The pairing-based backend (UltraHonk on BN254/KZG) is not quantum-sound, but the statement is fixed, so the backend can be swapped for a hash-based one later. The user's choice for the spike: SPHINCS- C13 verification in-circuit, pairing now / STARK later with the swap designed in, measured on the frames testnet.

2. What the circuit proves

Public inputs: message (the frame tx sig_hash, TXPARAM 0x08) and the D-018 commitment = keccak256("pq-stealth/sphincs-c13/commit/v0" ‖ pk ‖ opener), each as two 128-bit field elements (4 public inputs). Private: pkSeed, pkRoot, opener, the 3,688-B signature, and a chain-order hint. The circuit opens the commitment and runs the exact SPHINCs-C13Asm.sol verification (Verity-refined Yul, D-018): keccak-only tweakable hash over seed ‖ ADRS ‖ payload, FIPS 205 uncompressed ADRS, FORS+C forced-zero and WOTS+C constant-sum as assertions.

Because the key is a witness, a spend reveals nothing about which recipient key signed it: the spend-time linkability of the commit signer (every spent address of a recipient becomes linkable once the commitment is opened on chain) is gone. The account address is CREATE2(factory, 0, initcode(commitment, verifier, frameCtx)), sender-computable from the meta-address key and the KEM shared secret exactly as before.

Circuit-shape decision. WOTS+C makes the total chain length fixed (L·(w−1) − target_sum = 43·7 − 208 = 93 steps per layer) while each chain's length is data-dependent. A naive circuit hashes 7 steps for every chain (301 per layer, 2.3× the work). Instead the prover supplies chain_hint[layer][93], the chain each step belongs to; the circuit hashes the steps in that order with a per-chain running position and asserts every chain received exactly 7 − digit steps. The digit-sum assertion guarantees Σ(7 − digit) = 93, so all 93 steps must land in real chains. Result: the same 335 keccak calls as the Solidity verifier.

3. Measured

Toolchain: nargo 1.0.0-beta.19, bb 4.2.0 (aztec bundle), noir-lang/keccak256 v0.1.2, forge 1.4.1, Apple silicon laptop.

3b. Live run (frames testnet, chain 81410, 2026-09-03)

Deployed (ui/scripts/deploy-frames-zk.mjs, ui/public/frames-zk-deployment.json): ZKTranscriptLib 0x48b90e15…2b361 (6,577 B, 10.4 M gas — bb's verifier calls it as an external library, so it is a second contract to link), HonkVerifier 0xF01ecC1d…5BBfb (26,318 B, 40.9 M gas — accepted: the frames testnet does not enforce EIP-170's 24,576 B), Stealth8141ZkFactory 0x303CB317…9826.

ui/scripts/e2e-frames-zk.ts, fixture recipient, fresh ML-KEM-768 encapsulation:

Two lessons from the first attempt (0x946ad48e…c0afd, status 0): a 4 M execution-gas spend frame died at 3,938,060 = exactly 63/64 of its limit, i.e. out of gas inside the verifier staticcall — forge's 3.53 M undercounts what this chain charges for copying the 11 KB proof (SIGDATACOPY + ABI return), two cold contracts, and the EIP-8037 schedule; 9 M is comfortable and the total stays far under the 16.78 M cap. And the account deploy fits inside the spend transaction (3,099 B runtime, 37 k execution gas), unlike the ML-DSA route's 43 M type-2 deploy — the whole first spend is one frame transaction again.

Two consequences stand out before any testnet number:

• The proof is cheaper than ML-DSA and dearer than SPHINCS- itself. ~3 M for the Honk verify versus 13.7 M for ML-DSA on the EVM, but the direct C13 verify is 188 k. For SPHINCS- the ZK route is a privacy purchase (unlinkability), not a cost cut; for ML-DSA it would be a cost cut, but that is the MLWE-ownership statement of D-008, not this circuit.
• The bb verifier does not fit EIP-170. 26.3 kB runtime against the 24,576-B limit. Mainnet needs EIP-7907 (removed from Fusaka, candidate for Glamsterdam, not final). The frames testnet runs Glamsterdam+Bogota; whether it enforces 170 is exactly what the deploy step tests.

4. Backend question: pairing now, STARK later

The account holds the verifier as a rotatable pointer (setVerifier, callable only by the account itself, i.e. through an authorized executeFrame covered by sig_hash). The statement and its public-input layout are the contract; the backend is replaceable. What that does and does not buy:

• Soundness of KZG/BN254 rests on discrete log. A CRQC forges proofs, so a Honk account is exactly as quantum-safe at rest as an ECDSA account: not at all. The swap must happen before a CRQC; after one, the attacker can authorize the swap too. Same posture as EIP-7702 accounts today, stated plainly.
• A hash-based backend (FRI/STARK, or a binary-field system) is plausibly PQ-sound and transparent, but its EVM verifier is the cost: hash-heavy, typically 1–5 M+ gas with keccak Merkle paths and proofs of tens to hundreds of kB; with D-015's standard-hash policy there is no Poseidon shortcut. The verifier contract must also fit 170, which today means a wrapped/recursive proof.
• Wrapping does not transfer post-quantum soundness. A PQ inner proof folded into a pairing-based outer proof (the SP1/Groth16 "EVM wrapper" pattern) is only as PQ as the outer proof. The on-chain verifier is the trust root.

Flock (succinctlabs/flock, asked about 2026-09-03): "a prover and verifier for R1CS-over-GF(2) statements, built on a zerocheck + lincheck PIOP with a multilinear PCS (Ligerito) over the binary field F₂₁₂₈" — hash-based, transparent, plausibly PQ-sound, aimed at "batched hash statements (BLAKE3 and SHA-256 compressions)" with "a recursion tower that folds proofs into proofs"; 305 k SHA-256/s on a 32-core Threadripper; Rust API only; research stage; no keccak encoder and no EVM verifier. For this statement it would need a Keccak-f R1CS-over-GF(2) encoder (Keccak is Boolean-native: 38,400 ANDs per permutation, 358 permutations ≈ 14 M AND constraints, well inside its throughput) and, for on-chain use, either an EVM Ligerito verifier (none exists; proofs are large) or a wrapper — which brings back the paragraph above. Verdict: the right shape of prover for a hash-based migration target, not something that can be plugged into the account today; watch it alongside EIP-8288 (protocol-level STARK aggregation).

5. Where this leaves the routes

5b. Follow-up: prove the secret instead, in the browser (D-025)

The C13 statement is too large for browser proving (bb.js is wasm32, 4 GB cap; the circuit needs 8–11 GB). The user's redirection for the demo — prove the spending secret, not a signature — makes the statement two keccak calls: noir/preimage-ownership, 40,626 gates, same public-input layout, same account. Measured: witness ~50 ms, UltraHonk prove 0.65–1.3 s with bb.js in WASM, verifier 26,317 B, executeFrame 2,942,272 gas in forge; live on the frames testnet 0xa598ec41…1fe65 with frames [100, 37,001, 3,544,107]. The demo UI proves in a web worker with no server component. Everything in §4 about the backend still applies; the statement shrank, the trust root did not move.

6. Open

• EIP-170 on the frames testnet and on mainnet (EIP-7907).
• Prover on a phone/browser: 6.4 M gates, 2^23, ~7 GB proving key — laptop-class today. The no-ZK flavour and a recursion step are the obvious levers.
• Grindable R (upstream's own review note) is unchanged by proving; the circuit inherits the C13 security posture as is.
• Anonymity set: every ZK account shares one verifier and one commitment domain, so the set is "all ZK SPHINCS- stealth accounts", the same shape as D-022's "all 8164 accounts" remark.