From Question to Transformation: How Deterministic Circuit Structure Unlocked 10x Faster Groth16 Proving

Introduction

In the course of a deep investigation into Filecoin's SUPRASEAL_C2 Groth16 proof generation pipeline, a single unanswered question catalyzed the most impactful optimization of the entire engagement. The user asked: "Any optimizations possible for known constraint shapes, e.g. lots of sha256 constraints? or even more is the knowledge of constraint structure usable in ways that with some pre-computation (compile or runtime) would allow for better performance/parallelism?" This question, posed at message 45, challenged the fundamental premise of four prior optimization proposals—that the proving pipeline should be optimized around the circuit rather than through it.

What followed was a methodical investigation spanning over twenty messages, three parallel exploration agents, multiple source-code verifications, and ultimately the design of a transformative optimization: the Pre-Compiled Constraint Evaluator (PCE). This article synthesizes the work of this chunk, tracing the arc from the unanswered question through the research phase, the critical verifications, the architectural design, and the comprehensive total impact assessment that showed a path from ~360s per proof on 256 GiB machines to ~35-45s per proof on 96 GiB machines—a roughly 10x throughput improvement and 20x cost reduction.

The Unanswered Question: A Challenge to the Optimization Paradigm

The investigation began with four optimization proposals that addressed the mechanics of proof generation: sequential partition synthesis to reduce peak memory from ~200 GiB to ~64 GiB (Proposal 1), a persistent prover daemon to eliminate the 30-90 second SRS deserialization overhead (Proposal 2), cross-sector proof batching for 2-3x throughput improvement (Proposal 3), and 18 compute-level micro-optimizations across GPU kernels, CPU synthesis, and memory transfers (Proposal 4) [1]. These proposals were comprehensive, touching every layer of the stack from Go orchestration through Rust FFI into CUDA kernels.

But they all accepted a common premise: that the circuit synthesis phase—the synthesize() method that constructs the R1CS constraint system—must run for every proof. The user's question challenged this premise directly. It asked whether the shape of the constraints—the fact that ~88% come from SHA-256 gadgets with simple 1-3 term linear combinations, and ~99% of witness values are boolean (0 or 1)—could be exploited for fundamentally different algorithms [2].

The assistant's initial response, at message 44, was a remarkable document of intellectual honesty. It acknowledged that this question had not been answered yet, provided a comprehensive summary of everything discovered so far, and framed a detailed research agenda for how to pursue it [1]. This message set the stage for what would become the most innovative optimization proposal of the entire investigation.

The Research Launch: Three Parallel Investigations

Rather than attempting an immediate answer, the assistant decomposed the problem into three independent investigations, launched simultaneously at message 46 [3]:

Investigation 1: Aggregate Proof Paths (SnarkPack). This traced the five-layer aggregation stack from Curio's Go orchestration through filecoin-ffi Rust FFI into the SnarkPack aggregation logic. The goal was to understand whether the aggregation protocol's structure—which combines multiple Groth16 proofs into a single aggregate via the GIPA/TIPP/MIPP inner product argument—could enable mathematical transpositions that restructure the per-proof proving computation.

Investigation 2: Circuit Synthesis Structure. This explored the StackedCircuit::synthesize() method to understand the exact constraint composition of the PoRep circuit. The findings confirmed that SHA-256 constraints dominate (~88%), that witnesses are overwhelmingly boolean (~99%), and—most critically—that the R1CS constraint matrices A, B, C are deterministic and identical for every 32 GiB PoRep proof. Only the witness vector changes.

Investigation 3: Groth16 Math for Precomputation. This examined the mathematical structure of Groth16 proving to evaluate whether pre-computation based on known circuit structure is feasible. It traced how the a_i, b_i, c_i vectors are computed from witness and constraint linear combinations, revealing that the computation is a sparse matrix-vector multiply—a textbook scenario for pre-computation.

These three investigations returned comprehensive findings that converged on a single insight: the most under-exploited property of the entire pipeline is the determinism of the constraint structure. The matrices are static; only the witnesses change. Yet the current pipeline rebuilds everything from scratch for every proof.

The Pivot Points: From Investigation to Synthesis

The transition from research to synthesis occurred through a series of pivot messages. At message 47, the assistant acknowledged that the SnarkPack PDF had not rendered as text but pivoted to web searches for the Protocol Labs research blog post summarizing the same paper [4]. This demonstrated a key methodological principle: triangulate across multiple sources rather than depending on any single one.

At message 48, the assistant fetched the SnarkPack blog post for mathematical details and read the existing optimization proposals to understand what had already been covered [5]. The blog post confirmed that SnarkPack operates on the proof triplets (A, B, C) after individual proofs are generated—it is a post-processing step that does not change the per-proof proving math. This finding was crucial: it told the assistant that the optimization opportunity must come from the circuit structure itself, not from the aggregation layer.

At message 49, the assistant read proposals 1, 2, and 3 to understand the numbering scheme and ensure Proposal 5 would fit coherently into the existing framework [6]. This orientation step—reading before writing—reflected a disciplined engineering approach.

At message 50, the assistant declared "Now I have the complete picture" and committed to a specific decomposition of the work into three parts: Part A (Pre-compiled Constraint Evaluation), Part B (Exploiting Boolean Witnesses), and Part C (SnarkPack-Aware Transpositions) [7]. This planning message transformed scattered research into a structured, actionable plan.

The Pre-Compiled Constraint Evaluator: The Centerpiece

The centerpiece of Proposal 5 is the Pre-Compiled Constraint Evaluator (PCE), designed in detail at message 51 [8]. The PCE introduces a two-phase proving architecture that separates witness generation from constraint evaluation:

Phase 1 (Witness Generation): Run a stripped-down synthesis using bellperson's existing WitnessCS constraint system, which implements enforce() as a no-op. This executes only the alloc() closures that compute witness values (SHA-256 bit operations, Poseidon hash intermediates), skipping the enforce() closures that define constraint relationships.

Phase 2 (Constraint Evaluation): Load a pre-compiled CSR (Compressed Sparse Row) representation of the A, B, C constraint matrices and compute a = A·w, b = B·w, c = C·w via optimized sparse matrix-vector multiplication.

The PCE eliminates the ~780M ephemeral heap allocations per partition (130M constraints × 3 matrices × ~2 terms per LC) that result from repeated enforce() calls. The message estimated a 3-5x speedup in the synthesis phase, reducing it from ~90-180s to ~20-40s per partition.

The design includes a compressed entry format that exploits the coefficient distribution (~70% of coefficients are ±1, eliminating the need for field multiplication). The compressed format uses an enum with variants for PlusOne, MinusOne, PowerOfTwo, and General coefficients, compressing each entry from 36 bytes to ~5 bytes on average—a 5x compression ratio that reduces per-partition storage from ~22.7 GiB to ~4.7 GiB [8].

Specialized MatVec: Exploiting Coefficient and Witness Distributions

Part B of the proposal drills into the MatVec kernel itself, exploiting two properties of the circuit [8]:

Coefficient Distribution: Analysis of the constraint matrices showed that ~70% of non-zero coefficients are ±1, ~20% are powers of 2, and only ~10% are general field elements requiring full Montgomery multiplication (~50 cycles). For ±1 coefficients, the field multiply can be skipped entirely—just add or subtract the witness value. For powers of 2, field addition (~5 cycles) suffices.

Boolean Witness Specialization: Since ~99% of auxiliary witness values are 0 or 1, the MatVec inner loop can check a pre-computed boolean bitmap. For zero witnesses, the product is zero—skip entirely. For one witnesses, the product is just the coefficient—no multiply needed. The combined speedup analysis showed a ~16x improvement on the inner loop, reducing MatVec time from ~9.2s single-threaded to ~34ms with 16 threads.

Pre-Computed Split MSM Topology

Part C extends the boolean witness exploitation to the GPU multi-scalar multiplication (MSM) phase [8]. The existing split-MSM optimization in groth16_cuda.cu already classifies scalars into zero/one/significant buckets at runtime, scanning ~130M × 32B values per MSM. But since the set of boolean variables is deterministic (defined by the circuit structure, not the witness values), this classification can be pre-computed.

The proposal introduces a static BooleanIndexSet—a bitmap of ~130M bits (16 MiB) that identifies which auxiliary variables are always boolean. The SRS points can be pre-sorted so that boolean-indexed points are contiguous, enabling a single batch_addition pass without indirection. Only ~1% of scalars (Poseidon intermediates, column values) need full Pippenger MSM. This eliminates the runtime classification scan entirely and reduces the Pippenger MSM input from ~130M to ~1.3M points.

The Critical Verifications

Before writing the proposal, the assistant conducted two critical verifications that validated the PCE architecture [10][11].

At message 53, the assistant launched a verification task to confirm three details: (1) that is_witness_generator() exists in bellpepper-core's ConstraintSystem trait, (2) that ProvingAssignment handles witness generation correctly, and (3) that enforce() is skipped during witness generation. The verification succeeded, confirming that the two-phase approach is implementable without framework forks.

At message 54, the assistant summarized three critical findings: (1) WitnessCS exists and no-ops enforce() perfectly, (2) SHA-256 labeling has NO is_witness_generator() fast path (unlike Poseidon), meaning the PCE will have massive impact specifically on the SHA-256-dominated circuit, and (3) KeypairAssembly stores matrices in CSC (column-major) format, which requires a transpose to CSR but provides the starting point for extraction [10].

These verifications transformed the PCE from a compelling hypothesis into a confirmed design. The assistant could now write the proposal with confidence.

The Total Impact Assessment

The culmination of this chunk was a comprehensive total impact assessment synthesizing across all five proposals [12]. The analysis showed a path from the current baseline to an optimized pipeline:

| Metric | Current | Optimized | Improvement | |--------|---------|-----------|-------------| | Per-proof time | ~360s | ~35-45s | ~10x | | Peak RAM | 256 GiB | 96 GiB | ~2.7x | | Cost per proof | ~$0.083 | ~$0.004 | ~20x | | GPU utilization | ~30% | ~70-90% | ~2-3x |

The assessment identified the PCE (Proposal 5A) as the single highest-impact optimization across the entire stack, with a 1.00x throughput multiplier per engineering-week—meaning every week invested in the PCE pays back in full.

The implementation roadmap was organized into four waves with clear dependency ordering:

Wave 1 (highest impact, enables later waves): Build RecordingCS and CSR extraction tool, implement two-phase proving (WitnessCS + CSR MatVec) in bellperson fork, validate correctness via bit-for-bit comparison.

Wave 2 (specialize the MatVec): Implement SpecializedRow with coefficient classes, add boolean witness bitmap fast-path, benchmark and profile.

Wave 3 (GPU-side improvements): Extract static boolean index set, pre-sort SRS points and implement reordered split MSM, eliminate runtime classification scan.

Wave 4 (architecture): SnarkPack pipeline integration with persistent daemon (Proposal 2).

The Approaches Ruled Out

One of the most valuable sections of the analysis was the documentation of approaches investigated and ruled out [8]. These included:

The Broader Significance

This chunk represents a fundamental shift in how the optimization problem was framed. The first four proposals optimized how the existing pipeline ran—reducing memory, eliminating I/O, batching work, tuning kernels. Proposal 5 asked a more fundamental question: what computation is truly necessary, and what is redundant?

The answer—that the constraint matrices are deterministic and need not be rebuilt for every proof—is broadly applicable beyond Filecoin. Any Groth16 proving system where the circuit structure is fixed across multiple proofs with different witnesses can benefit from the PCE concept. This includes zk-Rollups, zk-EVMs, and any application that repeatedly proves the same computation with different inputs.

The investigation also demonstrated a mature methodology for systems optimization: start with measurement, identify the bottleneck, understand its root cause, propose a structural fix, quantify the impact, validate assumptions against source code, document dead ends, and produce a prioritized implementation plan. This methodology is applicable far beyond zero-knowledge proof generation.

Conclusion

The work in this chunk transformed a single unanswered question into the most impactful optimization of the entire SUPRASEAL_C2 investigation. Through methodical research, parallel exploration, critical verification, and careful synthesis, the assistant designed the Pre-Compiled Constraint Evaluator—a two-phase proving architecture that eliminates redundant circuit synthesis by exploiting the deterministic structure of the R1CS constraint matrices.

The combined impact across all five proposals is transformative: from ~360s per proof on 256 GiB machines at ~$0.083/proof to ~35-45s per proof on 96 GiB machines at ~$0.004/proof. This represents a roughly 10x throughput improvement and 20x cost reduction—a step-function change in the economics of Filecoin proof generation.

But beyond the numbers, this chunk demonstrates something more fundamental: the deepest optimizations come not from tuning parameters but from recognizing structural properties that others have overlooked. The deterministic circuit was hiding in plain sight, and this investigation finally gave it the attention it deserved.## References

[1] "The Unanswered Question: How Deterministic Circuit Structure Unlocks the Next Frontier of Groth16 Optimization" — Message 44 analysis. Describes the initial framing of the constraint-shape question and the comprehensive context provided before the investigation.

[2] "The Turning Point: How a Single Question Unlocked Constraint-Shape-Aware Optimizations for Groth16 Proof Generation" — Message 45 analysis. Examines the user's question about exploiting known constraint shapes and its assumptions.

[3] "The Research Launch: Gathering Foundational Knowledge for Constraint-Shape-Aware Groth16 Optimization" — Message 46 analysis. Documents the three parallel exploration agents launched to investigate SnarkPack aggregation, circuit synthesis structure, and Groth16 math.

[4] "The Pivot Point: How a Single Transitional Message Unlocked the Most Powerful Optimization in the C2 Proof Pipeline" — Message 47 analysis. Describes the pivot from investigation to synthesis, including the PDF failure and the decision to explore one more critical angle.

[5] "The Research Phase: How a Single Message Orchestrated the Final Piece of a Multi-Proposal Optimization Puzzle" — Message 48 analysis. Documents the fetching of the SnarkPack blog post and reading of existing proposals.

[6] "The Pivot Point: How Reading Existing Proposals Unlocked the Most Impactful Optimization in Filecoin's C2 Pipeline" — Message 49 analysis. Examines the orientation step of reading proposals 1-3 before writing Proposal 5.

[7] "The Moment of Synthesis: How a Single Planning Message Unlocked the Deepest Optimization in a Groth16 Proving Pipeline" — Message 50 analysis. Describes the planning message that committed to the three-part decomposition of Proposal 5.

[8] "The Pre-Compiled Constraint Evaluator: How Deterministic Circuit Structure Unlocks 10x Faster Groth16 Proving" — Message 51 analysis. The detailed design document for the PCE, specialized MatVec, pre-computed split MSM, and SnarkPack transpositions.

[9] "The Art of Scope: How a Single Commitment Message Defined the Future of Groth16 Proof Optimization" — Message 52 analysis. Documents the scope decision to go deep on PCE while keeping SnarkPack at the architectural level.

[10] "The Verification Before the Breakthrough: A Methodical Pivot in Groth16 Optimization" — Message 53 analysis. Describes the verification of is_witness_generator() and related implementation details.

[11] "The Pivotal Confirmation: How Three Lines of Evidence Unlocked the Pre-Compiled Constraint Evaluator" — Message 54 analysis. Documents the three critical findings that confirmed the PCE architecture.

[12] "The Deterministic Circuit: How Constraint-Shape-Aware Optimization Transforms Groth16 Proving" — Message 55 analysis. The complete design document for Proposal 5 with total impact assessment and implementation roadmap.