aere-docs/AERE-XMSS-AGGREGATION-CIRCUIT.md

Aere Network Post-Quantum Finality: XMSS Aggregation Circuit Design

Research item #4, the off-chain half of the Aere Network Post-Quantum Finality Certificate.

Status header, read this first.

• IMPLEMENTED and TESTED: the per-validator VERIFICATION CORE. An RFC 8391 XMSS-SHA2_10_256 hash-based signature verifier (WOTS+ one-time signature plus the XMSS Merkle authentication-path check that recovers the root public key), written as a dependency-free, no_std, allocation-free, float-free, hash-only Rust crate at aerenew/pqc-fork/pq-finality-circuit/xmss-verify-core/. It is validated against the OFFICIAL github.com/XMSS/xmss-reference known-answer vector and passes (see Section 7 for the real, run test result).
• NOT IMPLEMENTED, [MEASURE], multi-week specialist work: the full zkVM aggregation guest that runs this core over N validators, the SP1 proving pipeline, and the end-to-end certificate. This document specifies that design. It does not claim it works.
• UNCHANGED and fail-closed: the on-chain half (contracts/contracts/pqfinality/AereFinalityCertificateVerifier.sol and AerePQAttestationKeyRegistry.sol). Nothing in this work touches it. See Section 8.

Scope boundary, unchanged from the certificate design. This is the ADDITIVE post-quantum finality-attestation READ path. Aere consensus is still classical ECDSA QBFT. Validators keep signing ECDSA committed seals for block production and ALSO sign a hash-based attestation over each finalized block. The certificate proves the second, additive quorum. It does not replace, gate, or flip consensus, it needs no re-genesis, and post-quantum finality is NOT live end to end. Aere consensus is not post-quantum, and nothing here claims it is.

---

1. Where this sits

AERE-PQ-FINALITY-CERTIFICATE.md describes the whole feature. The on-chain verifier consumes ONE succinct proof and binds its public values to the live attestation-key registry. The proof is produced by an off-chain aggregation circuit that, inside a zkVM, verifies that a quorum of validators hash-based-signed a finalized block.

That aggregation circuit has an inner obligation it discharges once PER VALIDATOR: take a validator's committed hash-based public key and one signature, and confirm the signature is a genuine hash-based signature under that key over the domain-bound block message. For the XMSS-SHA2_10_256 scheme (RFC 8391, registry SCHEME_XMSS), that inner obligation is exactly the code in xmss-verify-core: recover the XMSS root from the signature and compare it to the validator's committed root.

This document specifies how the aggregation circuit wraps N instances of that inner obligation into the single proof the on-chain verifier already accepts.

---

2. The inner obligation (IMPLEMENTED)

For one validator, XMSS-SHA2_10_256 verification (RFC 8391 sections 4.1.9 / 4.1.10, single tree, height h = 10, n = 32, Winternitz w = 16, len = 67 chains, SHA-256):

1. M' = H_msg( toByte(2,32) || R || root || toByte(idx,32) || M ), the randomized, root-bound message hash, where M is the domain-bound block message (Section 4.3).
2. pk_ots = WOTS_PKFromSig(sig_ots, M', SEED, OTS-address(idx)), completing each of the 67 Winternitz chains from the signature value to its chain end.
3. leaf = ltree(pk_ots, SEED, LTree-address(idx)), the L-tree compression of the 67 WOTS+ public values to one n-byte leaf.
4. node = compute_root(leaf, idx, auth, SEED, HashTree-address), folding the leaf with the h = 10 authentication path.
5. The signature is VALID for (root, SEED) iff node == root.

All hashing uses the RFC 8391 keyed, address-domain-separated toolbox with padding_len = n = 32: F, H, H_msg, and PRF, with per-address keys and bitmasks derived by PRF(SEED, ADRS) over the 32-byte hash address. The reference crate is a byte-for-byte model of the already-deployed on-chain AereXmssVerifier.sol and its independent JS oracle, both validated against the same official vector.

Why XMSS verification is zkVM-tractable, honestly. It is hash-only: no floating point, no FFT, no Gaussian sampling (the reason Falcon is hard in a circuit). Every step is a SHA-256 call over fixed-size inputs, and SHA-256 is an SP1 precompile. The cost is a LARGE but BOUNDED number of SHA-256 invocations (Section 6), not a novel arithmetic gadget. That is what makes this the tractable first target.

Honest limits of the core. It verifies that a signature is valid for a given (root, SEED). It does NOT and cannot enforce the signer's one-time-per-leaf state: XMSS is stateful, and reusing a leaf index breaks WOTS+ off-chain, not in the verifier. The registry models rotation (Section 5); state discipline is the signer's duty.

---

3. The aggregation circuit (NOT implemented, [MEASURE])

The guest program (SP1 zkVM in the reference design, matching the repo's existing guests under aerenew/zk-light-client/ and aerenew/zk-circuits/) takes a private witness and commits public values.

3.1 Private witness

• blockHash, blockHeight: the finalized Aere block the certificate is about.
• attestationDomain: the 32-byte domain the on-chain verifier binds (Section 4.3).
• The ordered validator set: for each of the N enrolled validators (in the registry's enrollment order, which fixes the root ordering): the validator address, its current keyEpoch, and its current attestation public key bytes (for XMSS: root || SEED, plus scheme id).
• For each validator that attested: its XMSS signature (idx, R, wots[67], auth[10]) over the domain-bound block message. Non-attesting validators carry a null marker.

3.2 What the circuit MUST enforce

1. RECOMPUTE the committee commitment. Rebuild validatorSetRoot from the witnessed set exactly as AerePQAttestationKeyRegistry.validatorSetRoot() defines it (Section 4.1), and ABORT unless it equals the committed root the circuit emits. This is the membership check: a signature only counts if it is under a key the registry committed. Because the flat commitment binds every validator's address, key-epoch, and current key material, the circuit that reproduces it has proven each counted key is a genuine member at the committed epoch.
2. VERIFY each counted attestation. For each attesting validator, run the Section 2 inner obligation against THAT validator's committed (root, SEED) over the message of Section 4.3, and count it only if it recovers the committed root.
3. NEVER double-count. The circuit iterates the committed validator list in order and admits at most one counted attestation per list position, so distinctness is structural, not a runtime set-membership test.
4. COUNT and THRESHOLD. Let quorumCount be the number of DISTINCT valid attestations. The circuit requires quorumCount >= ceil(2N/3) (the on-chain _quorumThreshold(n) = (2n + 2) / 3), and ABORTS otherwise, so a proof cannot exist below quorum.
5. EMIT the public values of Section 4.2.

The proof is succinct: its size and on-chain verification cost are fixed by the SP1 verifier, independent of N and of how many attestations were checked internally. That independence lives entirely in the SP1 proof system, not in this circuit.

---

4. Binding to the on-chain verifier (the exact contract)

The circuit exists to satisfy the ALREADY-BUILT, UNCHANGED on-chain verifier. The binding is exact and is the load-bearing honesty of the design.

4.1 The committee commitment (registry-defined)

AerePQAttestationKeyRegistry.validatorSetRoot() is a flat, ordered keccak commitment:

leaf_i = keccak256(abi.encode(validator_i, keyEpoch_i, keyHash_i))
root   = keccak256(abi.encode(leaf_0, leaf_1, ..., leaf_{N-1}))

where keyHash_i = keccak256(currentPubKey_i), or bytes32(0) if validator_i has no key yet, and the ordering is enrollment order. The circuit MUST reproduce this byte-for-byte, including the Solidity abi.encode framing.

[VERIFY] Two encoding details the guest implementation must match against the deployed registry when built: (a) abi.encode(validator_i, keyEpoch_i, keyHash_i) left-pads the 20-byte address and the uint32 epoch to 32 bytes each, giving a 96-byte pre-image; (b) abi.encode(bytes32[] leaves) prepends the ABI head for a single dynamic array (a 32-byte offset word then a 32-byte length word) before the N leaves, so root = keccak256( 0x20-word || N-word || leaf_0 || ... || leaf_{N-1} ). Both use keccak-256, an SP1 precompile, distinct from the SHA-256 inside XMSS.

A Merkle tree is a drop-in alternative if per-leaf inclusion proofs are ever wanted (the registry doc notes this). It is NOT needed here: because the circuit witnesses the WHOLE set, recomputing the flat commitment is both sufficient and cheaper than N logarithmic inclusion proofs. If N grows large enough that witnessing the whole set is undesirable, switch the registry to a Merkle root and have the circuit check per-member inclusion instead; the on-chain verifier is agnostic, it only compares roots.

4.2 The public values (fixed 192-byte layout)

The circuit MUST commit exactly the six-word layout AereFinalityCertificateVerifier._decode expects:

abi.encode(
  bytes32 blockHash,        // the finalized Aere block hash
  uint256 blockHeight,      // its height
  bytes32 validatorSetRoot, // recomputed IN the circuit per Section 4.1
  uint256 validatorSetSize, // N committed under the root
  uint256 quorumCount,      // number of DISTINCT valid attestations, >= ceil(2N/3)
  bytes32 attestationDomain // the domain tag of Section 4.3
)

The on-chain verifier then, in ONE call and independent of N, checks: the registry is non-empty; validatorSetRoot equals the live registry root (a rotation invalidates old certs); validatorSetSize equals the live N; attestationDomain equals its immutable bound domain; quorumCount >= ceil(2N/3); blockHash != 0; and the SP1 proof verifies against the pinned circuit vkey. The circuit is trusted for the facts behind those six words; the contract binds them to live state.

4.3 The attestation message (domain-bound)

Each validator signs M, the 32-byte value the on-chain verifier defines in attestationMessage:

attestationDomain = keccak256(abi.encode(DOMAIN_PREFIX, chainId, registry))
M                 = keccak256(abi.encode(attestationDomain, blockHash, blockHeight))

DOMAIN_PREFIX = keccak256("AerePQFinalityCertificate.v1"). M is a keccak output; the XMSS H_msg then hashes M (as its message bytes) with SHA-256 internally. Domain binding blocks replay of a certificate to another chain, registry, or purpose. The circuit computes M from the witnessed attestationDomain, blockHash, blockHeight and checks every counted XMSS signature over it, then emits attestationDomain so the contract can confirm it equals the domain it pinned at construction.

---

5. Choice of hash-based scheme, and the tradeoff

The registry already carries scheme labels: SCHEME_XMSS (RFC 8391 stateful few-time), SCHEME_WOTS (Winternitz OTS+ one-time), SCHEME_LEANSIG (lean hash-based), and SCHEME_SLHDSA128S (FIPS 205 stateless), plus SCHEME_XMSSMT. The circuit's inner verifier is scheme-specific, so the scheme choice is a real design axis.

5.1 WOTS+ / XMSS (the implemented target)

• WOTS+ alone is ONE-TIME: a key signs exactly one message safely. XMSS layers a Merkle tree of 2^h WOTS+ keys under one long-term root, giving 2^h safe signatures (here 2^10 = 1024) before the key is exhausted. Both are STATEFUL: the signer must never reuse a leaf index. This is why attestation keys ROTATE, which AerePQAttestationKeyRegistry already models with a monotonic per-validator keyEpoch and an append-only key history. A validator that spends its 2^h leaves registers a successor key; the root changes; old certificates stop matching; new ones bind to the new root. Rotation is expected, cheap, and fail-closed.
• Pro: standardized (RFC 8391, NIST SP 800-208), the most conservative post-quantum assumption (security from SHA-256 collision and preimage resistance alone), and it MATCHES the deployed on-chain AereXmssVerifier.sol, so the same bytes verify on-chain and in-circuit.
• Con: SHA-256 is bit-oriented and comparatively EXPENSIVE to prove. The per-validator cost is thousands of SHA-256 invocations (Section 6). With N small this is tractable; it does not scale gracefully to thousands of validators.

SCHEME_SLHDSA128S (SLH-DSA, FIPS 205) is the STATELESS hash-based alternative: no rotation discipline (a key signs many times safely), at the cost of larger signatures and even more hashing per verify, so a heavier circuit. It is the right choice if operators cannot be trusted to manage XMSS state; it trades circuit cost for removing the stateful footgun.

5.2 leanSig / Poseidon2 (the field-native alternative)

leanSig is the hash-based signature line behind Ethereum's Lean Consensus / beam-chain direction: a generalized-XMSS-style construction whose hash is Poseidon2 over a small STARK-native field, chosen precisely for signature aggregation in a proof system.

• Pro: Poseidon2 is arithmetization-friendly. It is DRAMATICALLY cheaper inside a FRI/STARK circuit than SHA-256 (which pays for bit operations the field does not model natively). A leanSig aggregation circuit proves far faster per validator and scales to much larger N, which is why Ethereum targets it for its very large validator set.
• Con: it is NEWER and less standardized than RFC 8391 XMSS, and it moves the hash off SHA-256. To keep the on-chain binding exact, the registry key material and the committee commitment would also need a consistent hashing story (either keep the keccak commitment over Poseidon2-based public keys, or move the commitment to Poseidon2 too); the on-chain AereXmssVerifier.sol SHA-256 path would not be the in-circuit hash. It is the better ENDGAME for cost and scale; XMSS-SHA2 is the better FIRST target for standards-alignment and for reusing the already-validated on-chain verifier.

The tradeoff in one line: XMSS-SHA2 buys standardization, conservatism, and on-chain reuse at a higher in-circuit hashing cost; leanSig/Poseidon2 buys a much cheaper, more scalable circuit at the cost of novelty and a hashing story that diverges from the deployed SHA-256 verifier. An ML-DSA-in-zkVM approach (FIPS 204, integer arithmetic) is a further alternative with an easier circuit than SHA-256-XMSS, but it is LATTICE-based, not hash-based, so it does NOT carry the hash-only quantum-safety argument and is out of scope for the hash-based certificate.

Aere Network's live-first advantage is honest and specific: with a small validator set (N = 7 today, N >= 9 planned) the XMSS-SHA2 aggregation verifies at most N hash-based signatures per certificate, a tractable proving workload NOW, whereas Ethereum's hundreds of thousands of validators force the leanSig research runway. The small set that makes Aere's honest-quorum premise an operator assumption is the same property that makes post-quantum finality aggregation buildable today.

---

6. Structural cost (derivable) and performance ([MEASURE])

The following op counts are STRUCTURAL: they follow from the XMSS-SHA2_10_256 parameters and the toolbox definitions, and are derivable without running anything. They are NOT a performance measurement.

Per SHA-256-toolbox primitive: PRF and F hash 96-byte inputs; H hashes a 128-byte input; each F step needs 2 PRF (key, mask) plus one F hash (3 SHA-256 calls); each H node needs 3 PRF (key, two masks) plus one H hash (4 SHA-256 calls).

Per-validator XMSS-SHA2_10_256 verify (worst case, chains completed from the low end):

Stage	Units	SHA-256 calls (worst case)
H_msg	1 hash over ~129 bytes	1
WOTS_PKFromSig	up to 67 chains x 15 F steps	up to ~3015
L-tree	66 H nodes	~264
Auth path (h=10)	10 H nodes	~40
Per validator		up to ~3320 SHA-256 calls

For N = 7 that is on the order of ~23,000 SHA-256 invocations across the aggregation, plus a handful of keccak-256 calls for the committee commitment and the message binding. Typical (not worst) WOTS cost is roughly half, since the average completed chain length is about w/2. These counts are exactly why SHA-256 is the cost driver and why leanSig/Poseidon2 is the cheaper long-run hash.

[MEASURE] and NOT run here (each depends on the actual SP1 guest build, the sha256/ keccak precompile configuration, the prover hardware, and the proof mode):

• RISC-V cycle count per validator and per certificate inside the SP1 zkVM.
• Proving latency and memory for N = 7 and N = 9, on a given prover or the Succinct prover network.
• On-chain verifyProof gas against the REAL Succinct gateway (the contract is currently tested against a mock gateway).
• Native STARK vs Groth16-wrap tradeoff. A Groth16 wrap over BN254 shrinks the on-chain proof but REINTRODUCES a Shor-breakable pairing leg, forfeiting the end-to-end quantum-safety of Section 4 of the certificate doc. A native hash-based STARK proof (verified by the AerePQStarkVerifier line) keeps the proof itself post-quantum. This choice is a [MEASURE] cost-vs-quantum-safety decision, not settled here. Scope caveat (2026-07-19 finding): the AerePQStarkVerifier skeleton (0x0AE8) built so far is a BabyBear + FRI verifier that targets Aere's OWN Plonky3 STARKs. It does NOT verify an SP1 6.1.0 proof, because the pinned SP1 6.1.0 is a Hypercube / BaseFold (KoalaBear multilinear) system, not BabyBear FRI. So the native-STARK option here means proving the aggregation as an Aere-native BabyBear/FRI STARK (or retargeting 0x0AE8 to the SP1 Hypercube stack, a separate ~22 to 32 person-week effort), not verifying an SP1 zkVM proof directly. See AERE-STARK-SP1-RECURSION-AIR-PORT-SPEC-SUMMARY.md.

---

7. What was actually built and the REAL test result

Built at aerenew/pqc-fork/pq-finality-circuit/xmss-verify-core/:

• src/sha256.rs: a dependency-free no_std SHA-256 (self-checked against FIPS 180-4 SHA256("abc") and SHA256("")). A production SP1 guest swaps this for the SP1-patched sha2 precompile crate; the bytes are identical.
• src/xmss.rs: the RFC 8391 XMSS-SHA2_10_256 verification core (chain_lengths, wots_pk_from_sig, l_tree, compute_root, xmss_recover_root, xmss_verify), no_std, allocation-free, float-free, hash-only.
• src/vectors.rs: the official vector, GENERATED by scripts/gen_vectors.mjs from the committed contracts/test/fixtures/xmss-sha2_10_256-kat.json (github.com/XMSS/xmss-reference, oid=1, idx=512, msg=0x25), so the Rust vector is provably derived from the official fixture with no hand transcription.
• tests/kat.rs: the known-answer validation.

Real result of cargo test --offline (run, not asserted from memory): 12 tests passed, 0 failed. The genuine official signature recovers the official root 0x9d898033e37af48e6a116f8b15651cc26773467007ad19375d38c23c690c3483 and verifies; and every tamper (a WOTS+ value, the checksum chain, an authentication-path node, the message, the leaf index, the claimed root, the R randomizer) fails to verify. The two SHA-256 self-checks match FIPS 180-4.

This validates the INNER obligation of Section 2 only. It is not a proof, not a zkVM run, and not an aggregation.

---

8. On-chain side is unchanged and fail-closed

This work adds an off-chain reference crate and this document. It does NOT modify AereFinalityCertificateVerifier.sol or AerePQAttestationKeyRegistry.sol, and does not touch their tests. The on-chain verifier remains fail-closed exactly as before: it rejects unless the registry is non-empty, the proven root and size match the live registry, the domain matches, quorumCount >= ceil(2N/3), the block hash is non-zero, AND the SP1 proof verifies against the pinned vkey through the immutable gateway. Until a real aggregation guest and a real proof exist, no certificate can pass the real gateway, which is the correct fail-closed behavior.

---

9. Effort estimate for the remaining [MEASURE] work

Honest, and a range, not a promise. The verification core (done) is the small part. The remaining full zkVM guest plus proving pipeline is multi-week specialist work:

• Guest program: port xmss-verify-core into an SP1 guest, add the keccak committee commitment and message binding, the N-validator loop, distinct-count, and the threshold, and wire the six-word public-values output. Roughly 1 to 2 weeks including matching the abi.encode framing of Section 4.1 against the deployed registry.
• Host and witness assembly: collect attestations, build the private witness, run the prover. Roughly 1 week.
• Proving, tuning, and MEASURE: cycle counts, latency, memory, real-gateway gas, and the native-STARK vs Groth16 decision. Roughly 1 to 3 weeks, hardware-dependent.
• Audit of the guest before any mainnet vkey is pinned. Separate, founder-gated.

Total on the order of several weeks of focused specialist work before an end-to-end certificate could be produced, plus audit. Do NOT describe the certificate as working end-to-end until that work is done and measured.

---

10. References

• On-chain half (unchanged): contracts/contracts/pqfinality/AereFinalityCertificateVerifier.sol, contracts/contracts/pqfinality/AerePQAttestationKeyRegistry.sol, and contracts/test/AerePQFinalityCertificate.test.js.
• Feature doc: aerenew/docs/AERE-PQ-FINALITY-CERTIFICATE.md.
• Deployed on-chain XMSS verifier and its official vector: contracts/contracts/pqc/AereXmssVerifier.sol, contracts/test/xmssVerifier.test.js, contracts/test/fixtures/xmss-sha2_10_256-kat.json.
• SP1 guest / core-crate pattern this crate mirrors: aerenew/zk-light-client/guest/, aerenew/zk-light-client/qbft-finality/, aerenew/zk-circuits/recursive-aggregation-scale/.
• Standards: RFC 8391 (XMSS), NIST SP 800-208 (stateful hash-based signatures), FIPS 205 (SLH-DSA), FIPS 180-4 (SHA-256).