From Constraint Shape to 20x Cost Reduction: How Deterministic Circuit Structure Transformed Groth16 Proving

Introduction

In the course of an intensive investigation into Filecoin's SUPRASEAL_C2 Groth16 proof generation pipeline, a single question from the user catalyzed the most impactful optimization of the entire engagement. At message 45, 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?" [msg 45]

This question challenged the fundamental premise of four prior optimization proposals—that the proving pipeline should be optimized around the circuit rather than through it. The first four proposals had addressed memory reduction via sequential partition synthesis (Proposal 1), persistent prover daemon architecture (Proposal 2), cross-sector proof batching (Proposal 3), and 18 compute-level micro-optimizations across GPU kernels, CPU synthesis, and memory transfers (Proposal 4). Each was valuable, but all accepted a common assumption: that the circuit synthesis phase must run for every proof.

What followed was a methodical investigation spanning over a dozen 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 segment, 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. Proposal 1 introduced sequential partition synthesis to reduce peak memory from ~200 GiB to ~64 GiB. Proposal 2 designed a persistent prover daemon to eliminate the 30-90 second SRS deserialization overhead. Proposal 3 demonstrated cross-sector proof batching for 2-3x throughput improvement. Proposal 4 catalogued 18 compute-level micro-optimizations across GPU kernels, CPU synthesis, and memory transfers [msg 44].

But all four proposals 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.

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. 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 [msg 46]:

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 [msg 47]. 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 [msg 48]. 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 [msg 49]. 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) [msg 50]. 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 [msg 51]. 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 design 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.

Specialized MatVec: Exploiting Coefficient and Witness Distributions

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

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.

The implementation uses a SpecializedRow structure that pre-sorts each row's entries by coefficient class at extraction time. The MatVec kernel for each row iterates through four segments: plus-one columns (field add), minus-one columns (field subtract), small-coefficient entries (field add with shift), and general entries (full multiply). This pre-sorting eliminates all runtime classification within the inner loop.

Pre-Computed Split MSM Topology

Part C extends the boolean witness exploitation to the GPU multi-scalar multiplication (MSM) phase [msg 51]. 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 interaction with the Pre-Compiled CSR is seamless: the CSR matrix column indices use the same sorted variable ordering. When the PreCompiledCircuit is extracted, it applies the same permutation. The witness vector is generated in the sorted order (or reordered after generation), ensuring consistency across all components.

The Critical Verifications

Before writing the proposal, the assistant conducted two critical verifications that validated the PCE architecture [msg 53][msg 54].

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.

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 segment was a comprehensive total impact assessment synthesizing across all five proposals [msg 55]. 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 roadmap spans approximately 13 weeks of engineering effort, with each wave delivering measurable throughput improvements that compound as later waves are completed. The marginal return analysis shows that Wave 1 alone delivers ~60% of the total throughput gain, making it the clear first priority.

The Approaches Ruled Out

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

The Broader Significance

This segment 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.

The SnarkPack Dimension

A significant thread of the investigation examined whether SnarkPack aggregation could enable mathematical transpositions that reduce C2 proving work. The conclusion was nuanced but important: SnarkPack operates on the output proof triplets (A, B, C) ∈ G1 × G2 × G1, not on the internal C2 computation (NTT, H polynomial, witness). There is no mathematical transposition that allows SnarkPack knowledge to reduce C2 work [msg 51].

However, the architectural co-design opportunities are real. SnarkPack aggregation is CPU-dominated (pairings, G1/G2 MSMs, Fiat-Shamir hashing), while C2 proving is GPU-dominated (NTT, GPU MSM). This enables clean pipelining: GPU does C2 for sector N+1 while CPU does SnarkPack aggregation for sectors 1..N. For the proofshare marketplace, this suggests a two-tier architecture: expensive GPU machines focus purely on C2 throughput, while cheap CPU machines run SnarkPack aggregation at near-zero marginal cost.

Conclusion

The work in this segment 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 segment 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] Chunk article: "From Question to Transformation: How Deterministic Circuit Structure Unlocked 10x Faster Groth16 Proving" — The detailed analysis of how the unanswered question about constraint shapes led to the Pre-Compiled Constraint Evaluator design.

[2] Message 44 — Comprehensive context message documenting all prior discoveries and framing the research agenda for constraint-shape-aware optimization.

[3] Message 45 — The user's question about exploiting known constraint shapes (SHA-256 dominance, boolean witnesses) and SnarkPack transpositions.

[4] Message 46 — Launch of three parallel exploration agents investigating SnarkPack aggregation, circuit synthesis structure, and Groth16 math for precomputation.

[5] Message 47 — Pivot from failed PDF rendering to web search for SnarkPack blog post, demonstrating multi-source triangulation.

[6] Message 48 — Fetching SnarkPack blog post and reading existing optimization proposals to understand coverage.

[7] Message 49 — Reading proposals 1-3 to understand numbering scheme and ensure coherent integration of Proposal 5.

[8] Message 50 — Planning message committing to three-part decomposition of Proposal 5 (PCE, boolean witness exploitation, SnarkPack transpositions).

[9] Message 51 — Detailed design of Pre-Compiled Constraint Evaluator, specialized MatVec, pre-computed split MSM, and SnarkPack co-design.

[10] Message 52 — Scope decision to go deep on PCE while keeping SnarkPack at architectural level.

[11] Message 53 — Verification of is_witness_generator() and related implementation details confirming PCE feasibility.

[12] Message 54 — Three critical findings confirming PCE architecture: WitnessCS existence, SHA-256 missing fast path, KeypairAssembly CSC format.

[13] Message 55 — Complete design document for Proposal 5 with total impact assessment and implementation roadmap across all five proposals.

[14] Message 56 — Summary of key findings and confirmation that the plan is ready to write.

[15] Message 57 — User instruction to write up and assess total impact with implementation path.

[16] Message 58 — Writing of Proposal 5 document and total impact assessment.

[17] Message 59 — Successful write of c2-optimization-proposal-5.md.

[18] Message 60 — Writing of total impact assessment document.