A reference recursive composition assigned one 66-layer Poseidon2b walk to each authentication family so its full-graph cost could be measured directly. Memory scaled with family count and exceeded a 30 GB machine. The implemented redesign localizes family patterns inside one shared slot domain and discharges all nine families through one global walk, one shared state transfer and one combined polynomial identity.
Reference composition and its scaling limit
Poseidon2b is the four-word cryptographic permutation used to hash and authenticate proof data. The recursive verifier had to replay several Poseidon2b-based authentication families. Each family is one repeated type of hash relation—such as source-tree nodes, source leaves, pairs of symbols opened together at a fold layer or Merkle-path nodes—together with the openings that bind it to committed data. The reference composition intentionally gave every family its own slot schedule, its own selection of the four state words passed between layers, and its own deep-chain walk: a constraint trace that replays all sixty-six Poseidon2b layers for every occupied slot. That direct construction provided a clear baseline for measuring the complete authentication graph.
Algebraically, every family remained easy to inspect. Operationally, the full-graph benchmark showed memory growing with family count because every independent walk materialized another large set of trace columns. The complete nine-family shape exceeded a 30 GB machine, establishing that independent walks were not a viable composition topology.
“One walk per family” is a useful reference construction, but its memory cost scales with the number of authentication families. Production composition therefore needed to share the expensive permutation walk.
Find the shared object
Every family was ultimately asking the same question: does this sequence of width-four states follow the Poseidon2b permutation? The family-specific difference was not the permutation. It was the source of the inputs, the fixed schedule and the relation that consumes the outputs.
The union construction uses one shared slot domain with a fixed period P. Each family occupies a disjoint range inside that period. The four committed state-transfer columns C0..C3 hold the four words of the Poseidon state passed from one layer to the next. Those columns, the walk input and the Poseidon2b walk are shared. Only family input columns and fixed patterns differ.
Localizing family equations
Combining domains creates a subtle problem. A fixed pattern originally defined over a family's own stride repeats periodically. If copied directly into the shared domain, its constants fire inside other families' slots. Ungated state-transfer equations may also read across a family boundary.
The union primitive rebuilds every pattern as a table of length P, places the family's values only in its assigned range and writes zero elsewhere. A family term therefore vanishes outside its region. Terms that have no fixed factor receive an explicit region selector. Clean-start families are arranged so their first active node never reads transferred state from the preceding region.
At an A slot, only A terms are live. At a B slot, only B terms are live. The right-hand side is family-agnostic because it describes the same permutation input relation in both cases.
Two-family adversarial test
The minimal end-to-end experiment combined two genuinely different deep-chain families: a source-leaf chain and a Merkle path. It drove one state-transfer selection, one deep-chain walk and one combined polynomial identity—the sum of the localized family equations—through the outer polynomial commitment scheme (PCS) and public input/output boundary. The Merkle direction bits kept a separate booleanity sumcheck, but not a second permutation walk.
The regression tests changed an input symbol or sibling while leaving a satisfiable trace. The altered committed column then failed at the opening boundary. This was important: the test demonstrated that the union was not merely capable of accepting its own assembled witness; it still bound each family back to its commitment.
Full nine-family composition
The full experiment composed the source-binding graph: the source-tree family, source-leaf queries and one family of paired-symbol openings for each fold layer—nine family types in the measured shape. All of them shared:
- one slot domain;
- one state-transfer selection;
- one Poseidon2b deep-chain walk;
- one combined polynomial identity;
- one real FRI low-degree-proof channel schedule.
The channel was driven once from absorption of the Merkle cap—the compact list of roots authenticating the commitment trees—through mixed-opening challenges, round roots, final codeword, source-binding roots and shared query indices. Those challenges fed both the algebra and the source-opening claims. Each family retained its own committed input columns, but did not instantiate its own verifier walk.
Orthogonal memory controls
The single global walk removed the dominant multiplicative factor. Separate experiments moved constraint matrices to compressed sparse row (CSR) storage, right-sized the two alternating work buffers used by the BaseFold polynomial-commitment verifier, bounded temporary storage for linear-constraint checks (lincheck), capped scratch space by bytes and dictionary-encoded repeated matrix coefficients.
Those changes solve different problems. CSR and dictionary encoding reduce static matrix representation. Bounded scratch controls transient allocation. The global walk changes the composition topology itself. Treating all three as “memory optimizations” would hide why the original approach failed.
Scope of the construction
The construction applies to heterogeneous trace families that share Poseidon2b and can be localized inside one fixed domain. It is not a compiler for arbitrary verifier subcomputations. Its useful scope is specific: one expensive shared walk, with family-specific algebra at its input and output boundaries.
When many recursive checks contain the same expensive subcomputation, batch the subcomputation before optimizing its implementation. A faster copy of every walk would still have left memory proportional to the family count.
Why the full-graph benchmark matters
Single-family tests established local correctness and per-family cost. The full authentication graph measured the multiplicative topology that those local tests intentionally omit. The 30 GB boundary is therefore a composition measurement, not a defect in Poseidon2b or in any individual family. It explains why the selected design shares topology before applying lower-level memory controls.