Separator-Based Participation Commitments for Post-Quantum Attestation Aggregation

[muellerberndt]

Thanks to Arnav Anirudha for review & feedback.

TL;DR

The public Post-quantum Ethereum roadmap points toward larger hash-based validator signatures such as leanXMSS together with proof-based aggregation via leanVM / leanMultisig because post-quantum signatures are too large to rely on BLS-style native aggregation. If I understand correctly, the current folding-based scheme works as follows: Aggregate and Merge, keep exact signer participation in the statement, and treat witness movement as partly a networking problem rather than only a proving problem. The roadmap is also moving toward separate aggregator roles, propagation protocols, and recursive coalescing into one final aggregate per message. (Post-Quantum Ethereum roadmap). My baseline is the recent folding post.

The change I suggest is: Instead of carrying one global participation object through every internal merge, let each leaf carry a local participation object for one patch of the validator set, together with exact commitments for the overlaps with neighboring patches. Internal merges check agreement on those overlaps and combine the children. The full signer set is reconstructed once at the root, and the quorum check also happens once at the root.

In other words, keep signer accounting local for as long as possible. Each small group of validators records who signed inside that patch and what happens on the shared boundary. If neighboring patches agree on the shared validators, then on a tree cover there is only one global signer set consistent with all the local views.

If implemented, the only thing this proposal changes is the shape of the accountability object inside the recursion.

Informal Overview

Think of the validator set as a very large attendance sheet. In the usual recursive algorithm, one global attendance object gets threaded through many internal merges. The validator set is broken into overlapping neighborhoods, each neighborhood keeps its own local attendance sheet, and neighboring patches compare only the shared strip.

The key intuition is: if every neighboring pair agrees on the shared strip, then the global attendance sheet is already determined. The separator is the only place where the two sides need to communicate; once the boundary is fixed, the interiors can stay local. This is the separator theorem in Observers Are All You Need (OAAYN, r1378), Theorem 2.3 (§2.3, para. 9; proof in §2.3, paras. 14-24).

Proposal

Fix a message m, a validator snapshot root R, and a validator universe V for the attestation or finality object under consideration.

Choose a deterministic cover

V = \bigcup_{i=1}^k P_i

with the following properties:

1. the patch adjacency graph is a tree;

2. the cover satisfies the running-intersection property;

3. patch identifiers and validator ordering inside each patch are canonical and derived from R and the protocol randomness for the slot or epoch.

On a tree, local overlap agreement is enough to pin down one global section. On a graph with loops, path dependence and cocycle-type obstructions show up much more easily. For a first protocol version, that is unnecessary complexity. Tree covers are the safe place to start. This is the tree-versus-loop split in OAAYN (r1378), Lemma 3.2b (§3.4.2, para. 4).

For each patch P_i, define a local aggregation object

L_i = (m, R, P_i, b_i, C_i, {\alpha_{ij}}_{j \sim i}, \pi_i),

where:

• b_i \in \{0,1\}^{P_i} is the local participation bitfield;

• C_i is a commitment to the local witness data for that patch;

• \alpha_{ij} is a separator commitment for the overlap S_{ij} = P_i \cap P_j;

• \pi_i proves local validity for the signatures and local commitments under m and R.

A separator commitment can be instantiated as

\alpha_{ij} = H\Big( m \,|\, R \,|\, \mathrm{id}(P_i) \,|\, \mathrm{id}(P_j) \,|\, \mathrm{id}(S_{ij}) \,|\, b_i|_{S_{ij}} \,|\, C_i|_{S_{ij}} \Big).

The witness commitment C_i needs a canonical serialization. Otherwise two honest aggregators could describe the same local data with different roots and fail to merge. So the serialization has to fix validator ordering, chunk layout, Merkle arity, domain tags, and the encoding of restricted openings on overlaps.

Merge rule

Given two child objects L_u and L_v, define MergeSep(u,v) as follows:

1. verify that both children use the same message m, validator snapshot root R, and compatible patch metadata;

2. verify both child proofs;

3. verify exact separator equality on S_{uv} = P_u \cap P_v;

4. combine the non-overlap participant sets;

5. keep one canonical copy of the overlap state;

6. fold or accumulate the witness commitments into the parent object.

The parent lives on P_t = P_u \cup P_v.

Note that the internal merge does not compute quorum or try to sum attesting weight. It only checks exact local consistency and combines local claims. The quorum or attesting-weight check happens once, at the root, after canonical reconstruction of the global signer set. This fixes the potential double-counting bug that appears as soon as one validator lives in two overlapping patches.

Exact gluing theorem

Here is the exact statement that carries the consensus path.

Proposition. Let \{P_i\} be a deterministic tree cover with the running-intersection property. For each patch P_i, let b_i be a local participation bitfield indexed by P_i. If for every edge (i,j),

b_i|_{P_i \cap P_j} = b_j|_{P_i \cap P_j},

then there exists a unique global bitfield b on V such that

b|_{P_i} = b_i \quad \text{for all } i.

The same statement applies to the underlying witness relation once the serialization and commitment scheme are fixed canonically. Neighboring patches agree on the shared validators, so there is only one global signer set they could all have come from.

The same shape appears in OAAYN (r1378): Theorem 3.1 (§3.4.1, para. 1) gives constructive gluing on tree covers, Theorem 2.3 (§2.3, para. 9; proof in §2.3, paras. 14-24) isolates the separator as the place where left and right communicate, and Lemma 3.2b (§3.4.2, para. 4) explains why trees are the easy case.

Why this helps

There are three different costs here:

First, there is the irreducible cost of exact signer recovery. That cost does not go away. The older Signature Merging post says: if you want exact extraction of the signer set, there is a linear-size component somewhere in the system. (Signature Merging for Large-Scale Consensus)

Second, there is the cost of carrying that information through every internal merge. That’s what separator commitments reduce. The exact signer set still exists and is still recoverable, but it is materialized once at the root rather than being dragged through the whole recursive tree as a global object.

Third, there is prover cost. That depends on the proving backend, whether leanMultisig, WHIR-style recursion, or something else, and is mostly orthogonal to the geometric change proposed here.

In this design, the accountability object lives locally in patch-level commitments during recursion and is reconstructed as one global signer set only at the root. The improvement is that internal merges carry only separator-local accountability data instead of a full global signer object.

Security conditions

For a first version, I believe the protocol needs the following conditions.

1. Exact separator equality on the consensus path

Fork choice, finality, and slashing should only depend on exact separator equality and exact root reconstruction. Approximate recovery should stay outside the consensus path.

The approximate recovery theorem is still useful, and it gives a real trace-distance bound when the conditional mutual information across a separator is small. In OAAYN (r1378), §2.2, para. 1, the paper states

I(A:C \mid B) \le \varepsilon \quad \Longrightarrow \quad | \rho_{ABC} - (\mathrm{id}_A \otimes \mathcal R)(\rho_{AB}) |_1 \le 2 \sqrt{\ln 2\, \varepsilon},

and then extends this to tree gluing with additive error across steps in Theorem 3.1 (§3.4.1, para. 5). That is interesting for local repair, but not as a validity rule for consensus. The current folding baseline already treats witness handling as a P2P issue, and that is exactly where approximate methods belong.

2. Root-only quorum check

Consider patches P_1 = \{v_1, v_2\} and P_2 = \{v_2, v_3\}. If v_1 and v_2 signed, then the local counts are 2 and 1, while the true unique signer set has size 2. Any protocol that lets internal nodes sum local counts without exact deduplication creates a direct double-counting attack.

The safe first version is root-only thresholding. Internal nodes merge exact local claims. The root reconstructs the canonical global bitfield and computes the attesting weight once.

An optimized later version could use a deterministic owner map h(v) that assigns each validator to one home patch. That may be useful eventually, but it is extra machinery, and the first version does not need it.

3. Canonical cover and canonical serialization

The cover used by aggregators has to be deterministic from the validator snapshot and protocol randomness. The merge tree has to be canonical. The serialization of witness commitments has to be canonical as well.

If honest aggregators can pick different covers or different encodings, then path dependence appears for no good reason. See the tree-versus-loop analysis from OAAYN (r1378), Lemma 3.2b (§3.4.2, para. 4). Once loops appear, path independence becomes an issue. Trees avoid that entire class of ambiguity in the first version.

4. Per-validator openings for slashings

Ethereum needs exact accountability. A final aggregate must support later proofs of the form “validator v signed message m” or “validator v signed conflicting messages m and m'.” Local commitments therefore need per-validator openings and retention long enough to cover slashing windows.

5. Multi-source fetch for separators

Separator withholding is an obvious liveness issue. A malicious aggregator could withhold one small overlap opening and stall a merge. The fold-based baseline already treats witnesses as a network problem. In this construction, separator data becomes an especially natural target for withholding, so it should be fetchable from multiple peers, and another aggregator should be able to rebuild the merge from leaves if one provider stalls. (Post Quantum Signature Aggregation: a Folding Approach)

Toy accounting result

A simple back-of-the-envelope model gives the scaling intuition. Take a toy tree cover with:

N = 131{,}072, \qquad k = 64, \qquad s = 256.

If the exact count relation is

N = km - (k-1)s,

then

m = \frac{N + (k-1)s}{k} = 2300.

Suppose the naive recursive instance carries a full N-bit global signer object at every internal merge. Then the internal accountability payload is

B_{\mathrm{naive,int}} = (k-1)N = 63 \cdot 131{,}072 = 8{,}257{,}536 \text{ bits} \approx 1008 \text{ KiB}.

In the separator scheme, internal merges only carry separator-facing accountability data:

B_{\mathrm{sep,int}} = (k-1)s = 63 \cdot 256 = 16{,}128 \text{ bits} \approx 1.97 \text{ KiB}.

That is a factor of

\frac{N}{s} = 512

in the internal recursive accountability payload.

If we include the leaf-local patch bitfields and a one-shot root materialization of the full bitfield, the toy total becomes

km + (k-1)s + N = 147{,}200 + 16{,}128 + 131{,}072 = 294{,}400 \text{ bits} \approx 35.9 \text{ KiB}.

Under this toy accounting model, the repeated accountability payload inside recursion drops sharply, while the full accountability object still exists exactly once at the root. The point is that if separator width stays much smaller than total validator count, then the recursive accountability payload scales with separator size rather than with the full validator set size. These numbers also cover only the accountability component; end-to-end prover time still depends on signature verification costs, witness fetch patterns, and the proving backend.

Relation to current work

Folding and leanMultisig

The recent folding post is the closest baseline, and I see this proposal as modifying that baseline rather than replacing it. Aggregate still handles raw signatures, Merge still combines aggregated objects, and exact participation still matters because rewards, penalties, and slashings depend on it. The only change is the public accountability object carried by internal merges. Instead of one global bitfield-shaped object at each step, the recursive statement carries local patch commitments and exact overlap commitments. (Post Quantum Signature Aggregation: a Folding Approach)

WHIR

WHIR targets the proving engine. Separator commitments sit one layer above that. They change the geometry of the object being folded or recursively verified, not the low-level proving primitive. So my expectation is that the two ideas compose fairly cleanly. (WHIR for Ethereum)

Dynamic availability and heartbeat plus trailing finality

Recent consensus posts argue for a fast heartbeat chain and a trailing finality layer. A sampled heartbeat with about 256 validators can use concatenated signatures and avoid large-scale PQ aggregation on the critical path. That leaves the full-set finality layer as the place where recursive aggregation still matters. Separator commitments are aimed directly at that layer. (LMD GHOST with ~256 validators and a fast-following finality gadget)

QC-style decentralized aggregation

The recent SSF aggregation post proposes a large hierarchical grouping process that can absorb many attestations in parallel. That is directionally similar. The separator view adds a more explicit rule for overlaps: duplicate signers live on separators, exact deduplication is part of the merge condition, and local mismatch proofs live on one overlap instead of forcing global recomputation. (Decentralized Attestation Aggregation with Quorum Certification based Single-Slot-Finality)

Signature merging

Signature Merging for Large-Scale Consensus is useful background because it states the exact requirement that still matters here: a merged object should allow extraction of the signer set, and that requirement creates a linear-size component in the data. Separator commitments respect that fact. The linear cost is paid once at the root rather than being carried globally through each internal merge. (Signature Merging for Large-Scale Consensus)

Recent PQ aggregation alternatives

Recent posts also explore execution-layer aggregation trade-offs and even more radical alternatives such as removing signature objects from the authorization path entirely. Those discussions are useful because they underline how context-dependent the right answer is. Consensus has a stricter accountability requirement than transaction aggregation, because the signer set feeds directly into attesting weight and slashability. So this proposal stays squarely in the validator-attestation setting and keeps explicit signatures and explicit signer identity. (Revisiting Falcon Signature Aggregation for PQ Mempools)

Approximate local repair, future work

One direction that seems genuinely useful, though definitely not consensus-critical, is repair after missing witness chunks. If a node has most of the local data for two child patches and is missing a small amount of interior witness data, the separator may still tell it enough to decide whether the merge is repairable, which chunks to fetch first, or which candidate parent is consistent with the local picture.

In the paper, this is the content of

I(A:C \mid B) \le \varepsilon \Longrightarrow \text{recoverability across } B,

together with the additive tree-gluing bound of Theorem 3.1 (§3.4.1, para. 5) in OAAYN (r1378). The same paper’s §2.3, paras. 37-38, together with §5.9, paras. 7-10, then suggest that separator defects can decay exponentially with separator width in the right regime.

That suggests a useful future-work program:

• witness prefetch based on separator state;

• local merge scheduling based on repairability estimates;

• partial recovery after packet loss or delayed openings.

Fork choice, finality, and slashing should continue to use exact separator equality and exact root reconstruction.

Prototype plan

A serious first prototype could be done in three steps.

Step 1: exact mode in leanSpec / leanMultisig

Use the current lean stack and replace the internal global-bitfield recursion object with a tree cover of local patch objects and exact separator commitments. The root emits the reconstructed full bitfield once, so the rest of the consensus machinery can stay close to the current baseline. This fits the current roadmap directly, because pq-devnet-3 and pq-devnet-4 are already about separate aggregator roles, propagation, recursive aggregation, and one final aggregate per message. (Lean Consensus Roadmap)

Step 2: conflict localization and liveness testing

Simulate delayed or missing separator openings, duplicate deliveries, and adversarial withholding of overlap chunks. The goal is to measure:

• failed-merge rejection cost;

• fallback reconstruction cost;

• size of local conflict witnesses;

• recovery time when separators are fetched from multiple peers.

Step 3: fit it into a heartbeat plus trailing-finality architecture

Use the scheme only on the full-set finality side. Let the heartbeat path stay simple and sampled, in the spirit of the recent consensus discussions. That gives the proposal a cleaner deployment surface and avoids forcing the same machinery onto parts of the protocol that do not need it. (LMD GHOST with ~256 validators and a fast-following finality gadget)

Open questions

The main open questions I see are:

1. What is the best deterministic cover: committee-based, subnet-based, latency-aware, or stake-balanced?

2. Should the root always materialize the full bitfield, or should future versions move toward a commitment-only root with explicit openings on demand?

3. What is the best separator commitment: restricted bitfield root, restricted witness root, or one joint root?

4. Can separator mismatch proofs become compact fraud proofs for aggregator misbehavior?

5. What is the best chunk placement rule so that separator-locality also improves witness fetching on the network side?

6. Does an owner-map variant beat root-only thresholding in practice once the system is benchmarked?

Conclusion

Ethereum’s post-quantum path is now concrete enough that the aggregation interface itself is worth optimizing. The Post-Quantum Ethereum roadmap already points toward leanXMSS plus proof-based aggregation, and Post Quantum Signature Aggregation: a Folding Approach already gives the right Aggregate plus Merge abstraction.

Separator-based participation commitments are one natural fit. They keep recursive accountability local, make duplicate handling explicit, and localize conflict proofs to overlaps. The exact consensus theorem is simple. OAAYN (r1378) contributes the separator-first viewpoint of Theorem 2.3 (§2.3, para. 9; proof in §2.3, paras. 14-24) and the tree-gluing / recovery toolkit from §2.2, para. 1 and Theorem 3.1 (§3.4.1, paras. 1 and 5); Reality as a Consensus Protocol (r1378) gives the dedicated consensus lane in Introduction paras. 1-3 and Theorem 3.5 (§3, para. 9).

Other directions suggested by OPH mechanisms

Observer-Patch Holography (OPH) models reality itself as consensus between overlapping, subjective observer perspectives. That makes it a rich source of ideas for real consensus engineering, stolen directly from nature.

1. Repair budget. Approximate recovery plus tree gluing gives a budget for local defect accumulation. Gain: better fetch/scheduling decisions and less wasted work on unrecoverable partial states. See OAAYN (r1378), §2.2, para. 1 and Theorem 3.1 (§3.4.1, para. 5).

2. Overlap sizing. The exponential defect bound suggests choosing separator width from a target defect budget instead of by heuristic. Gain: lower overlap payload, witness traffic, and prover work for the same reliability target. See OAAYN (r1378), §2.3, paras. 37-38, and §5.9, paras. 7-10.

3. Obstruction audit. The tree/loop and cocycle viewpoint suggests checking decentralized merge plans for loop obstructions and path dependence. Gain: better correctness and auditability, plus earlier failure detection and more compact inconsistency certificates. See OAAYN (r1378), Lemma 3.2b (§3.4.2, para. 4).

4. Topology tuning. The local Gibbs / MaxEnt viewpoint suggests choosing tree shape, overlap width, and aggregator placement from explicit local costs. Gain: lower latency, bandwidth, and proving cost for a fixed safety target. See OAAYN (r1378), §2.3, paras. 31-42.

5. Live obstruction monitor. The cycle-obstruction theorem suggests continuously auditing the live aggregation graph using separator commitments as the local input data. Gain: earlier warning when the network is drifting toward a fork-prone shape, before a fork actually forms. See Reality as a Consensus Protocol (r1378), Theorem 4.1 (§4, para. 2; proof in §4, paras. 3-4).