From Incremental Optimization to Architectural Transformation: Phase 5 of the Cuzk Proving Engine

Introduction

In the lifecycle of any ambitious engineering project, there comes a threshold moment when incremental optimization reaches its natural limit and the only path forward is architectural transformation. For the cuzk project — a pipelined SNARK proving engine for Filecoin's Proof-of-Replication (PoRep) circuits — that threshold was crossed in a single session that spanned from a Phase 4 post-mortem through the complete implementation of Wave 1 of the Pre-Compiled Constraint Evaluator (PCE). This chunk of the conversation captures the entire arc: from recognizing that micro-optimizations had hit a wall, to designing a fundamentally new approach, to building the core infrastructure, to wiring it into the existing pipeline.

The work in this chunk represents the transition from Phase 4 to Phase 5 of the cuzk roadmap. Phase 4 had delivered a respectable 13.4% improvement in total proof time (88.9s → 77.0s) through two validated wins — Boolean::add_to_lc and async deallocation — but had also disproven several promising hypotheses (SmallVec, cudaHostRegister, Vec pre-allocation) through rigorous empirical testing. The critical finding was that the synthesis bottleneck (~50.8 seconds) was now purely computational, dominated by field arithmetic and LinearCombination construction. There were no more easy wins left to harvest in the existing synthesis approach.

The PCE approach, described in the design document c2-optimization-proposal-5.md, offered a fundamentally different strategy: instead of rebuilding the circuit from scratch for every proof, capture the R1CS constraint matrices once and reuse them across proofs via sparse matrix-vector multiplication. This chunk documents the execution of that vision, from exploration through planning through implementation through integration.

The Phase 4 Post-Mortem: Why Incremental Optimization Hit a Wall

The session opens with the assistant's comprehensive Phase 4 status report ([msg 1352]), which serves as both a post-mortem and a strategic recommendation. The report is notable for its empirical rigor: every optimization was tested against real hardware using perf stat to track IPC, cache misses, and branch mispredicts. Two optimizations survived this gauntlet. The Boolean::add_to_lc optimization eliminated temporary LinearCombination allocations in circuit gadgets by adding add_to_lc and sub_from_lc methods to the Boolean type, reducing synthesis time by 8.3% (55.4s → 50.9s) and eliminating 91 billion instructions. The async deallocation fix addressed a mysterious 10-second gap between CUDA-internal timing and pipeline-reported GPU time, traced to synchronous destructor overhead when freeing ~167 GB of C++ and Rust vectors. Moving ownership to detached threads dropped GPU wrapper time from 36s to 26.2s.

Equally important were the hypotheses that Phase 4 disproven. SmallVec caused an 8.5% IPC regression on Zen4 — the simpler instruction stream of plain Vec yielded higher IPC that more than compensated for any cache misses. cudaHostRegister added 5.7 seconds of mlock overhead and was reverted. Vec pre-allocation using capacity hints showed zero measurable impact, confirming that Rust's geometric doubling strategy already amortizes allocation costs when growth is interleaved with parallel computation across 96 cores.

The net result was a 13.4% improvement (88.9s → 77.0s), falling far short of the projected 2-3x target. The perf record profile told the decisive story: synthesis time (~50.8s) was dominated by field arithmetic (16.98%), LC construction (23.52%), and memory allocation (17.44%). Critically, ~74% of this work was structurally redundant — the LC shapes are identical for every proof because the circuit topology is fixed. Only the witness values change. The report concluded with an explicit recommendation: "Further gains require Phase 5 (PCE) to eliminate synthesis entirely."

The Threshold: "Implement Phase 5"

The user's response ([msg 1353]) was characteristically concise: "Implement phase 5," accompanied by references to the project roadmap (cuzk-project.md) and the Phase 5 design document (c2-optimization-proposal-5.md). This eight-word command carried the full weight of the strategic decision: abandon the path of diminishing returns in Phase 4 and commit to the highest-risk, highest-reward item in the entire roadmap.

The assistant's response ([msg 1354]) demonstrated the methodological discipline that would define the phase. Rather than immediately writing code, it dispatched two parallel task tool calls to explore the existing codebase. One subagent explored the cuzk workspace structure — the Cargo.toml, the crate organization, the pipeline code in cuzk-core, the synthesis call sites. The other explored the bellperson fork's prover internals — ProvingAssignment, KeypairAssembly, WitnessCS, and the density tracking flow from constraint system to GPU MSM. This parallel exploration strategy reflected an understanding that the PCE must be designed to fit within the cuzk workspace while correctly interfacing with bellperson's prover internals.

The exploration spanned messages [msg 1354] through [msg 1358], covering the workspace Cargo.toml, the supraseal.rs prover, the pipeline.rs synthesis orchestration, the WitnessCS type, the KeypairAssembly generator, the density tracking mechanism, and the existing benchmark infrastructure. Each file read added to the shared understanding that would inform the implementation.

The Architecture of a Plan: Four Waves of PCE Implementation

With the codebase fully explored, the assistant produced a detailed task plan ([msg 1359]) decomposing Phase 5 into four implementation waves:

Wave 1: Core CSR Infrastructure — Create the cuzk-pce crate with CsrMatrix types, PreCompiledCircuit serializable container, RecordingCS constraint system, and a multi-threaded evaluate_csr function. This wave establishes the foundational data structures and algorithms.

Wave 2: Specialized MatVec — Implement coefficient-specialized evaluation kernels (exploiting the fact that ~90% of coefficients are ±1, ±2, or small powers of 2) and boolean witness fast-paths (exploiting that ~99% of witness values are 0 or 1).

Wave 3: Pre-Computed Split MSM Topology — Extract the static boolean index set from the circuit topology, pre-sort SRS points so boolean-indexed points are contiguous, and modify the GPU split MSM to use direct ranges instead of runtime classification.

Wave 4: SnarkPack Pipeline — Add proof accumulation buffer and aggregation worker thread for the SnarkPack aggregation pipeline.

The plan's structure reveals a deliberate risk-management strategy. Wave 1 is the foundation — without it, nothing else can be built. Wave 2 is an optimization of Wave 1's MatVec kernel. Wave 3 is a deeper integration with the GPU proving pipeline. Wave 4 is a pipeline-level architectural change. Each wave produces a testable artifact, and the dependency order ensures that validation can begin early.

Building the Foundation: The cuzk-pce Crate

The assistant executed Wave 1 across messages [msg 1360] through [msg 1369], creating the cuzk-pce crate from scratch. The crate's Cargo.toml ([msg 1363]) declared dependencies on ff and blstrs for BLS12-381 field types, bellpepper-core for the ConstraintSystem trait, bellperson for WitnessCS integration, bitvec for density bitmaps, serde and bincode for serialization, and rayon for parallel evaluation.

The core types defined in the crate include:

CsrMatrix — A Compressed Sparse Row matrix with row_ptrs: Vec<u32>, cols: Vec<u32>, and vals: Vec<Fr>. CSR was chosen over CSC (Compressed Sparse Column, used by bellperson's KeypairAssembly) because the evaluation phase needs row-wise access: each constraint corresponds to one row, and the MatVec must compute the dot product of that row with the witness vector. CSR provides O(1) access to any row's non-zero entries and enables cache-friendly sequential access during evaluation.

PreCompiledCircuit — A serializable container holding three CsrMatrix instances (for A, B, C) plus density bitmaps and dimension metadata. This is the output of the extraction process and the input to the MatVec evaluator. The density bitmaps (a_aux_density, b_input_density, b_aux_density) are pre-computed during extraction and used during GPU MSM classification.

RecordingCS — A custom ConstraintSystem implementation that captures R1CS constraints directly into CSR format during a single synthesis run. This is the key innovation: by recording directly into CSR during synthesis, the PCE avoids the CSC-to-CSR transpose that would be required if using KeypairAssembly. The RecordingCS implements the ConstraintSystem trait methods — alloc(), alloc_input(), enforce(), is_witness_generator() — with the enforce() method capturing the A, B, C closure structures rather than evaluating them against a witness.

evaluate_csr() — A multi-threaded function that computes the matrix-vector product y = M · x for a CSR matrix M and witness vector x. The function uses rayon's par_extend to partition rows across threads, with each thread computing a contiguous range of output values. This provides excellent scalability with zero contention, as each thread writes to disjoint regions of the output vector.

The assistant encountered and fixed a borrow bug in the RecordingCS implementation ([msg 1368]), demonstrating the iterative nature of the development process. The enforce() method's closure invocation required careful handling of mutable state, and the fix ensured that the recording correctly captured all constraint terms.

Wiring It In: Workspace Integration

With the crate's code complete, the assistant integrated it into the cuzk workspace across messages [msg 1370] through [msg 1376]. This involved three coordinated edits:

First, the workspace Cargo.toml was updated to add "cuzk-pce" to the members list and to declare cuzk-pce as a workspace dependency. Without this, the crate's code would exist on disk but be invisible to the build system — dead code unreachable from any other crate.

Second, cuzk-core/Cargo.toml was updated to add cuzk-pce as a dependency. This is the critical integration point: cuzk-core is the heart of the proving engine, containing the pipeline, scheduler, prover dispatch, and SRS manager. By making cuzk-core depend on cuzk-pce, the assistant ensured that every part of the proving pipeline that needs to evaluate constraints can call into the PCE's MatVec routines.

Third, workspace-level dependencies for ec-gpu-gen and bitvec were added to support the downstream integration work still to come — specifically, the construction of DensityTracker objects from the PCE's density bitmaps.

The decision to keep the PCE in its own crate rather than inlining it into cuzk-core reflects a deliberate architectural philosophy. The crate boundary enforces separation of concerns: the PCE has its own data structures, its own evaluation logic, and its own serialization format. Mixing these into cuzk-core would bloat the core library with concerns that are conceptually distinct. The crate boundary also provides a compilation firewall — changes to the PCE's internals do not force recompilation of the entire cuzk-core crate — and enables future substitution if a better evaluation strategy emerges.

The Milestone: Wave 1 Complete

Message [msg 1377] marks the completion of Wave 1. The assistant's todowrite call flips three high-priority tasks from "in_progress" to "completed":

The Broader Significance

The work in this chunk exemplifies several principles of effective engineering:

Know when to stop optimizing the wrong thing. Phase 4 demonstrated that micro-optimizations of the synthesis pipeline have diminishing returns. The perf profile showed that ~74% of synthesis time is structurally redundant work that doesn't need to be repeated. The right response was not to optimize this work further but to eliminate it.

Invest in architectural change when the payoff justifies the risk. Phase 5 is the highest-risk item in the entire cuzk roadmap, requiring new infrastructure, codebase modifications, and careful validation. But the potential payoff — 3-5x synthesis speedup, 5-10x total throughput — justified the risk.

Use data to drive decisions. Every Phase 4 optimization was tested empirically, and the data determined which ones survived. The decision to move to Phase 5 was based on the clear evidence that the synthesis bottleneck is structural, not parametric.

Build shared context for efficient communication. The eight-word command "Implement phase 5" was sufficient because months of collaboration had built up a deep shared understanding between user and assistant. This context is the foundation of effective AI-assisted development.

Separate concerns through crate boundaries. The decision to create a dedicated cuzk-pce crate rather than inlining PCE code into cuzk-core reflects a disciplined approach to software architecture that values modularity, testability, and clean dependency boundaries.

Conclusion

The chunk spanning messages [msg 1353] through [msg 1377] captures a pivotal transition in the cuzk project: from the diminishing returns of Phase 4's micro-optimizations to the architectural ambition of Phase 5's Pre-Compiled Constraint Evaluator. The work is characterized by methodological discipline — explore before building, plan before implementing, validate before integrating. The cuzk-pce crate, now a member of the cuzk workspace, represents the first concrete step toward replacing circuit synthesis with sparse matrix-vector multiplication. Whether the PCE delivers the projected 3-5x synthesis speedup remains to be validated empirically, but the foundation is solid: the types are sound, the algorithms are designed, and the integration points are established.

In the broader narrative of the cuzk project, this chunk marks the transition from optimization to transformation. Phase 4 asked: "How can we make the existing synthesis faster?" The answer was: "Not fast enough." Phase 5 asks: "How can we replace synthesis entirely?" The PCE is the answer, and this chunk documents the moment that answer became structurally embedded in the project.