Independent verifier walks made memory scale with the number of authentication families and exceeded a 30 GB machine. Production HistoryStep places three Link groups and six Block groups in one joint transcript and one ordered ragged Poseidon2b walk. Canonical region columns and endpoint claims preserve the meaning of each group while the expensive permutation trace is shared across all nine.
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 shares 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.
Production joint composition
Current HistoryStep composition places nine recursive regions in one joint transcript. Link contributes three groups and Block contributes six. All nine groups share:
- one ordered ragged slot schedule;
- one 66-layer Poseidon2b walk;
- one batching challenge schedule;
- one canonical set of terminal claims entering the outer PCS batch.
The outer post-commit channel derives the three Link prefixes and seeds the Block child channel. The child processes the ordered nine-group walk and completes the six Block suffixes. Its terminal digest returns to the outer channel before the three Link suffixes complete. Each region keeps its own canonical committed columns, but no region instantiates an independent permutation 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.