Designing Efficient Recursion in Transparent Proof Systems (PLONK-ish and STARK-ish)

Introduction: why recursion matters for transparent proofs

Recursion turns a proof system into a composable verification layer: one proof can attest to the validity of many other proofs, or to the validity of a computation that itself verifies proofs. In transparent systems (no trusted setup), recursion is attractive for rollups, light clients, bridging protocols, and multi-layer applications where you want a small verification footprint on-chain or on constrained devices, while keeping the heavy proving work off-chain.

The engineering goal is not merely “make it recursive,” but to do so with stable soundness and manageable costs. In practice, recursion introduces three primary sources of overhead: (1) verifying the inner proof’s commitment openings and query consistency, (2) reproducing the inner transcript challenges (Fiat–Shamir) without circular dependencies, and (3) arithmetizing cryptographic primitives (hashes, field operations, FRI-like steps, Merkle paths) in an outer constraint system. The dominant cost is often the arithmetization of the inner verifier, so the most effective optimizations reduce how much of the inner verifier must be checked inside the outer proof.

Two recursion patterns: inline nesting vs aggregation/commit-and-prove

There are two canonical ways to compose transparent proofs recursively. Both can be made to work without a trusted setup, but they target different bottlenecks and lead to different interfaces.

Pattern A: inline nesting (verifier-in-the-statement)

In inline nesting, the outer proof’s statement includes “there exists an inner proof π such that Verify(vk, public_inputs, π)=1,” and the outer prover supplies a witness that includes π and whatever auxiliary data the verifier needs (authentication paths, decommitments, intermediate transcript states). The outer circuit/constraint system implements the inner verifier logic.

This pattern is conceptually straightforward and gives strong modularity: any statement can be upgraded to “plus a proof of that statement,” and you can stack layers. The trade-off is prover cost: encoding a full verifier is expensive, especially for STARK-style verification (Merkle authentication, FRI queries, and hashing) or for any scheme that relies heavily on hash-based commitments.

Pattern B: aggregation (commit-and-prove)

In aggregation, the outer proof does not fully re-run each inner verifier. Instead, it proves a combined predicate that implies the validity of many inner proofs using shared randomness, batching, or a reduced set of checks. The outer proof commits to a set of inner proof artifacts (or their digests) and proves that enough consistency conditions hold that a verifier would accept each inner proof.

This pattern can reduce verifier work substantially and can reduce the outer circuit size if you avoid re-implementing the full verification logic per inner proof. The trade-off is complexity and subtlety: aggregation often relies on careful batching (e.g., random linear combinations of opening checks) and careful transcript derivation to ensure that “combined checks” are sound. It also introduces an “aggregator” role that must assemble or preprocess multiple proofs and expose a stable public-input interface (e.g., a root commitment to the batch and a final combined proof).

Choosing between A and B is usually driven by the target: inline nesting is a good fit when you need strict modular layering and a small number of inner proofs per outer proof; aggregation is a good fit when you must compress many proofs into one succinct artifact for a single on-chain verification step.

Transcript and Fiat–Shamir in transparent recursion: avoiding circularity

Transparent systems are typically interactive-oracle-proof (IOP) based and made non-interactive via Fiat–Shamir. Recursion forces you to model that non-interactivity inside another proof, which can create circular dependencies if not designed carefully.

Deterministic transcript serialization is non-negotiable

The inner verifier’s challenges are derived from a transcript that absorbs commitments, public inputs, and protocol messages in a specific order. In recursion, the outer circuit must reproduce those challenges exactly. Any ambiguity in encoding (variable-length fields, multiple equivalent serializations, endianness differences, omitted domain separators) becomes a soundness risk or an interoperability failure.

Practical pattern: define a transcript API with explicit tags and length-prefixing at the byte level, then define a canonical mapping from bytes to field elements (including rejection sampling rules if applicable). Make this part of your protocol spec and test it with cross-language vectors early, because recursion magnifies small inconsistencies.

Break the “self-referential” loop explicitly

A common pitfall is inadvertently hashing something that depends on challenges that depend on that hash. This can happen if the proof includes a commitment to data that is derived from transcript challenges, and the transcript absorbs that commitment before sampling those challenges. The fix is structural: order messages so that commitments absorbed by Fiat–Shamir do not depend on future challenges, or isolate challenge-dependent objects behind later transcript steps.

In aggregation settings, be cautious about deriving one global batching challenge from a transcript that already includes the aggregated result. A safer approach is to derive batching randomness from a transcript that binds all inner proof digests and public inputs, then compute the aggregated checks, then absorb the aggregated commitments and derive any later randomness.

Model the random oracle carefully inside the outer proof

In a recursive verifier circuit, “hash” becomes a constrained primitive. For STARK-ish systems, hashes are typically arithmetized as field-friendly constructions or as bitwise circuits, which can be expensive. For PLONK-ish systems without trusted setup, you still need a transparent commitment or hash inside the circuit if you are verifying an IOP transcript. Engineers often underestimate how much of the recursion budget is consumed by hashing and Merkle logic rather than by “field arithmetic.”

Arithmetization choices: encoding inner verification for PLONK-ish vs STARK-ish

Arithmetizing an inner verifier means expressing its acceptance predicate as constraints over an outer field. The right encoding depends on (1) the inner proof system’s operations (hashes, polynomial evaluations, low-degree tests), (2) the outer proof system’s native field and constraint model, and (3) the availability and cost of gadgets (hash, Merkle, FFT-like operations, field extension arithmetic).

PLONK-ish outer systems (transparent variants)

PLONK-style arithmetizations (custom gates, lookup arguments, permutation checks) can represent a verifier efficiently when the verifier is dominated by structured arithmetic and table lookups. If your inner verification involves many hashes or bit-decompositions, lookups can help, but you must account for the transparency constraint: you may not have a trusted SRS, and you may rely on hash-based or IPA-like commitments rather than pairing-based commitments.

Engineering pattern: isolate expensive boolean/byte operations into lookup-heavy subcircuits, keep the rest of the verifier in native field arithmetic, and minimize cross-domain conversions. Avoid repeatedly packing/unpacking bytes unless the transcript format forces it; instead, define transcript absorption in terms of field elements where possible, with an explicit, unambiguous encoding.

STARK-ish outer systems

STARK arithmetizations (AIR) are often well-suited to verification that is itself “trace-like”: repeated hashing steps, repeated Merkle path checks, and repeated sampling and evaluation can be modeled as state machines. If the inner verifier resembles an iterative computation, AIR can represent it naturally. The catch is that the verifier includes cryptographic hash functions and Merkle verification, which can dominate trace width and constraint degree.

Engineering pattern: express the verifier as a small number of tightly optimized state machines: (1) transcript sponge steps, (2) Merkle authentication stepper, (3) finite-field arithmetic for evaluation checks, and (4) any FRI-like folding logic. Keep the public interface small by committing to all inner proof artifacts via a single root/digest, and only open what the outer verifier must inspect.

Field and extension-field friction

Many transparent proof verifiers operate over extension fields (for evaluation domains or for FRI folding). Recursion becomes harder when the outer system’s native field differs from the inner system’s base or extension field. Constraining extension-field arithmetic over a mismatched base field is doable but expensive.

If you have freedom in system design, aligning fields (or choosing an outer system that naturally supports the inner field arithmetic) can materially simplify recursion. If you do not have that freedom, prioritize designs that reduce extension-field operations in-circuit, for example by minimizing the number of queried points or folding steps the outer circuit must reproduce.

Commitments and opening verification: where costs actually land

Transparent systems typically use hash-based commitments (Merkle trees over evaluations) or other transparent polynomial commitments. Recursion forces the outer proof to check that the inner prover’s claimed evaluations are consistent with those commitments and that the low-degree test is satisfied (often via FRI-like checks). The outer circuit must therefore verify a set of openings, which typically consists of: (1) Merkle branch verification for each queried leaf, (2) hash computations along the branch, and (3) arithmetic checks tying queried evaluations to the claimed polynomial relations.

Batched openings reduce verifier work but complicate the circuit

Batched opening strategies (random linear combinations of multiple polynomials or multiple points) can reduce the number of distinct opening verifications. This typically helps the outer verifier’s asymptotic work and can shrink the size of the “verification transcript” that must be arithmetized. The trade-off is that batching introduces extra randomness, additional scalar multiplications or field operations, and a more complex soundness argument that depends on correct Fiat–Shamir derivation and correct binding of all batched items to the transcript.

Practical pattern: batch aggressively at the protocol layer, but keep the in-circuit batching logic simple and explicit. Derive a single batching challenge from a transcript that absorbs (a) all commitments being opened, (b) all points, and (c) the statement/public inputs. Then compute the batched combination deterministically in-circuit.

Merkle paths are expensive; minimize how many you verify

Each Merkle path forces repeated hashing in the outer circuit. The most direct optimization is to reduce the number of queries that must be verified inside the outer proof. This can come from protocol parameters (fewer queries), from batching (fewer distinct leaves), or from aggregation (verifying only a reduced set of checks that implies correctness for many proofs). Parameter changes have soundness implications; if you adjust them, do so with careful analysis rather than intuition.

Reducing verifier work: extract succinct checks and keep public inputs clean

If arithmetizing the full verifier is too costly, focus on extracting the smallest set of checks that preserves security. This often means proving that certain predicates hold rather than replaying the entire interaction in-circuit.

• Commit to inner proof artifacts via a single digest: Expose one root/hash that binds the inner proof, public inputs, and key commitments. The outer proof then only needs to open what it uses, while the digest prevents substitution.
• Separate “state transition” from “proof verification” in public inputs: For rollups and light clients, the outer proof should bind old_state_root and new_state_root (and possibly data availability commitments) as explicit public inputs. Inner proof details should remain private and referenced by digest.
• Use succinct predicate checks where possible: Instead of verifying every internal step, prove that a smaller set of algebraic relations holds that implies verifier acceptance. This resembles aggregation and must be designed cautiously, but it can save substantial circuit work.
• Be explicit about domain separation: Treat every transcript absorption with a tag identifying protocol, layer, and message type to prevent cross-protocol replay and to avoid accidental equivalences across recursive layers.

A recurring pitfall is “accidentally public” data: making inner transcript elements public inputs to simplify debugging can permanently bloat the interface and leak unnecessary details. Prefer private witnesses plus a single binding digest, and only elevate data to public inputs when a downstream verifier needs to reason about it (e.g., state roots, block headers, or application outputs).

Randomness, batching, and consistency across layers

Recursive composition often chains multiple sources of randomness: inner proof challenges, outer proof challenges, and batching scalars used to combine multiple checks or multiple proofs. Soundness can degrade if randomness is reused across contexts or if challenges do not bind to the correct messages.

Entropy reuse and “same challenge across proofs” hazards

If you aggregate many inner proofs, it is tempting to use a single batching scalar for everything. This can be acceptable if the scalar is derived from a transcript that binds all items being batched, but it becomes risky if proofs can be rearranged, truncated, or adversarially chosen to exploit linear dependencies. A cautious pattern is to derive randomness from a transcript that includes a commitment to the full set (e.g., a Merkle root of proof digests) and to include the batch structure (counts, ordering, domain separators) explicitly in the transcript.

Consistency checks for public inputs and outputs

For rollups and multi-step protocol proofs, recursion is valuable because it can enforce that the output of one proof is the input to the next. Engineers should make these linkages explicit: the outer statement should assert that inner_public_output_i equals inner_public_input_{i+1}, and that the first and last link to the outer public inputs (e.g., old_state_root and new_state_root). When aggregation is used, ensure that each inner proof’s public inputs are bound into the aggregated transcript and that the outer proof checks the chaining constraints, not just the validity of each proof in isolation.

Conclusion: practical recursion design checklist

Recursion in transparent proof systems is feasible without trusted setup, but it is less about choosing a label (PLONK-ish or STARK-ish) and more about disciplined engineering around transcripts, commitments, and what you actually verify in-circuit. The main cost driver is arithmetizing the inner verifier; optimizing recursion usually means reducing the inner verifier surface area that the outer proof must check.

Practically: pick an explicit recursion pattern (inline nesting for modular layering, aggregation for compressing many proofs), lock down deterministic transcript serialization with strict domain separation, design your public-input interface around stable state commitments, and batch openings in a way that is clearly bound to the transcript. Finally, treat hashing, Merkle verification, and extension-field arithmetic as first-class budget items; most recursion projects succeed or fail on those details rather than on the high-level proof system choice.