The Milestone That Shifts Paradigms: Phase 5 Wave 1 Complete

In the long arc of optimizing a Filecoin SNARK proving engine, most messages are about doing: writing code, running benchmarks, fixing bugs. But some messages are about becoming — marking the transition from one phase of work to the next, acknowledging that a foundational layer has been laid and the project can now build atop it. Message [msg 1377] is precisely such a message. On its surface, it is a simple todowrite tool call that flips three task statuses from "in_progress" to "completed":

[assistant] [todowrite] {"todos":[{"content":"Phase 5 Wave 1: Create PCE crate (cuzk-pce) with RecordingCS and CSR matrix types","priority":"high","status":"completed"},{"content":"Phase 5 Wave 1: Implement RecordingCS that captures R1CS into CSR format directly","priority":"high","status":"completed"},{"content":"Phase 5 Wave 1: Implement CSR sparse MatVec evaluator (row-parallel, multi-threaded)","priority":"high","status":"completed"},{"content":"...

Beneath this deceptively simple status update lies a carefully reasoned architectural pivot, the culmination of dozens of prior messages spanning weeks of empirical investigation, and the materialization of an idea that was first proposed as a theoretical optimization in a background document many segments ago. This article unpacks the full significance of this single message.

The Long Road to Phase 5

To understand why message [msg 1377] matters, one must understand the journey that preceded it. The cuzk project is a pipelined SNARK proving engine for Filecoin's Proof-of-Replication (PoRep), designed to generate Groth16 proofs for 32 GiB sectors. The proving pipeline is enormous: it involves synthesizing circuits with millions of constraints, evaluating those constraints to produce witness assignments, and then running multi-scalar multiplications (MSMs) on GPU to produce the final proof.

Phase 4 of the project had been a grueling exercise in empirical optimization. Every promising idea was subjected to rigorous microbenchmarking and perf stat analysis before being accepted or rejected. The Boolean::add_to_lc optimization eliminated temporary allocations in circuit gadgets, reducing synthesis time by 8.3%. Async deallocation fixed a 10-second GPU wrapper delay caused by synchronous destructor overhead. But equally important were the hypotheses that were disproven: SmallVec caused an 8.5% IPC regression on Zen4 and was rejected; cudaHostRegister added 5.7 seconds of mlock overhead and was reverted; Vec pre-allocation showed zero measurable impact.

The net result of Phase 4 was a 13.4% improvement in total proof time — from 88.9 seconds to 77.0 seconds. This was respectable, but it fell far short of the 2–3× improvement that the project ultimately needed. More importantly, the Phase 4 post-mortem (documented in chunk 0 of segment 16) delivered a critical insight: the synthesis bottleneck (~50.8 seconds) was now purely computational, not memory-bound. The perf profile showed that the CPU was spending its time on field arithmetic and LinearCombination construction, not on waiting for memory. This meant that incremental tweaks to the existing synthesis approach had reached their limit. A fundamentally different strategy was required.

That strategy was the Pre-Compiled Constraint Evaluator (PCE) — the central innovation of Phase 5.

The PCE Concept: From Circuit Synthesis to Sparse Matrix-Vector Multiply

The insight behind the PCE is elegant. In the traditional bellperson proving pipeline, every proof generation runs the full circuit synthesis process: the Circuit::synthesize method is called, which invokes ConstraintSystem::enforce for each constraint, building up LinearCombination objects, allocating variables, and constructing the R1CS matrices A, B, and C from scratch. For Filecoin PoRep, this synthesis takes approximately 50 seconds per proof — and it produces the same circuit structure every time, because the circuit topology is determined by the sector size and proof parameters, not by the witness data.

The PCE approach exploits this invariance. Instead of re-synthesizing the circuit for every proof, the PCE records the R1CS matrix structure once (during a single synthesis run), serializes it to a PreCompiledCircuit containing the A, B, and C matrices in Compressed Sparse Row (CSR) format, and then evaluates new witnesses against these pre-compiled matrices using a fast, multi-threaded sparse matrix-vector (MatVec) multiply. The 50-second synthesis becomes a sub-second MatVec.

This was the vision. Message [msg 1377] marks the moment when the foundational infrastructure for this vision was completed.

What Wave 1 Actually Built

The work that culminated in message [msg 1377] spanned approximately a dozen tool calls across messages [msg 1360] through [msg 1376]. The assistant created an entirely new crate, cuzk-pce, from scratch, with four modules:

csr.rs — The CsrMatrix type, a Compressed Sparse Row matrix representation with row_offsets, col_indices, and values arrays. This is the data structure that will store the pre-compiled A, B, and C matrices. The CSR format was chosen deliberately: it enables cache-friendly sequential access during the MatVec multiply, and it avoids the costly CSC-to-CSR transpose that would be required if the matrices were captured in the traditional column-major format used by bellperson's KeypairAssembly.
density.rs — The DensityBitmap type, a compact bit-vector representation that tracks which columns of each matrix row are non-zero. This mirrors the DensityTracker concept from ec-gpu-gen (used downstream by the GPU MSM kernels) but adapted for the CSR storage format.
recording_cs.rs — The RecordingCS struct, which implements bellperson's ConstraintSystem trait. During a single synthesis run, RecordingCS captures every enforce call — each constraint's linear combinations for A, B, and C — directly into CSR format. This is the key innovation: by recording directly into CSR during synthesis, the PCE avoids an expensive matrix transposition step that would otherwise be required.
eval.rs — The evaluate_csr function, a row-parallel, multi-threaded sparse MatVec evaluator. It takes a PreCompiledCircuit (the recorded A, B, C matrices) and a witness vector w, and computes a = A·w, b = B·w, c = C·w using rayon parallel iteration over rows. The function is generic over the field type and uses explicit cache prefetching hints (std::arch::x86_64::_mm_prefetch) to optimize memory access patterns. The crate was then integrated into the cuzk workspace: the workspace Cargo.toml was updated to include cuzk-pce as a member, cuzk-core's Cargo.toml was updated to depend on it, and workspace-level dependencies for ec-gpu-gen and bitvec were added to support the downstream integration work still to come.

The Reasoning Behind Every Decision

The message [msg 1377] is not just a status update — it is a testament to a series of deliberate architectural decisions, each grounded in the empirical findings of Phase 4.

Decision 1: CSR format over CSC. Bellperson's KeypairAssembly stores matrices in Compressed Sparse Column (CSC) format because the generator needs column-wise access for MSM pre-computation. However, the evaluation phase needs row-wise access: each constraint corresponds to one row of A, B, and C, and the evaluator must compute the dot product of that row with the witness vector. CSR provides O(1) access to any row's non-zero entries, making it the natural choice for MatVec. The RecordingCS captures directly into CSR, avoiding a transpose that could cost several seconds for matrices with ~100 million non-zero entries.

Decision 2: Row-parallel, not column-parallel. The evaluate_csr function uses rayon's parallel iteration over rows. This is a deliberate choice: each row's computation is independent (it reads from the shared witness vector but writes to distinct output positions), so there is no synchronization overhead. Column-parallel evaluation would require atomic updates to output positions, introducing contention.

Decision 3: Multi-threaded, not GPU. One might ask: if the goal is speed, why not run the MatVec on GPU? The answer lies in the Phase 4 profiling data. The 50-second synthesis bottleneck is CPU-bound, but the GPU is already saturated with MSM work. Offloading MatVec to GPU would either compete with MSM for GPU cycles (reducing overall throughput) or require synchronization and transfer overhead that would eat into the gains. A multi-threaded CPU MatVec, using all available cores on a Zen4 workstation, is expected to be fast enough to reduce the 50-second synthesis to well under a second — and it keeps the GPU focused on what it does best.

Decision 4: Separate crate, not inlined. The PCE infrastructure was placed in its own cuzk-pce crate rather than being added directly to cuzk-core or bellperson. This isolates the complexity, keeps the dependency graph clean, and allows the PCE to be tested and benchmarked independently before full integration.

Assumptions and Their Risks

Every engineering decision rests on assumptions, and the PCE Wave 1 work is no exception. The most critical assumption is that the circuit structure is indeed invariant across proofs for the same sector size. If the circuit topology varies — for example, if different vanilla proofs produce different constraint structures — then the pre-compiled matrices would be invalid for some inputs, and the PCE would produce incorrect results. The assistant implicitly assumes this invariance based on the nature of Filecoin PoRep circuits, where the circuit is determined by the sector size and proof parameters, not by the data. This assumption is likely correct, but it has not yet been empirically validated — that validation is one of the purposes of the planned PceExtract benchmark command.

A second assumption is that the CSR MatVec will be fast enough to justify the complexity. The Phase 4 data suggests that synthesis is ~50 seconds of pure computation, and the MatVec for a circuit with ~100M non-zero entries should take well under a second on a 16-core Zen4. But this has not been measured yet. If the MatVec turns out to be slower than expected — for example, if memory bandwidth becomes a bottleneck — then the PCE approach may need refinement.

A third assumption is that the RecordingCS faithfully captures all constraints. The ConstraintSystem trait has multiple methods (enforce, push_namespace, pop_namespace, alloc, alloc_input, etc.), and the RecordingCS must handle all of them correctly. Any mismatch between the recording and the actual synthesis could produce incorrect proofs.

The Knowledge Created

Message [msg 1377] represents the creation of several forms of knowledge:

Output knowledge: The cuzk-pce crate itself — approximately 500 lines of Rust code spanning four modules, plus the workspace and dependency integration. This is tangible, compilable infrastructure that future messages will build upon.

Structural knowledge: The crate's architecture establishes a pattern for how the PCE will integrate with the rest of the pipeline. The PreCompiledCircuit type is the bridge between the recording phase and the evaluation phase. The RecordingCS is the bridge between bellperson's synthesis interface and the CSR storage format. These interfaces define the contract for the remaining waves of Phase 5.

Status knowledge: The todo list update communicates to the assistant (and to any observer) that Wave 1 is complete and Wave 2 is ready to begin. This is project management knowledge — it enables the assistant to context-switch from "building infrastructure" to "integrating and validating."

Confidence knowledge: By marking these tasks as completed, the assistant implicitly asserts that the code compiles, the types are coherent, and the design is sound enough to proceed. This confidence is earned through the careful exploration and planning that preceded the implementation (messages [msg 1354] through [msg 1359]).

The Thinking Process Visible in the Message

While message [msg 1377] itself contains only a todowrite call, the thinking process that led to it is visible in the surrounding messages. The assistant spent messages [msg 1354] through [msg 1358] conducting an exhaustive exploration of the codebase: reading the workspace structure, the bellperson prover pipeline, the WitnessCS and KeypairAssembly mechanisms, the generator internals, and the existing benchmark tool. This was not casual browsing — it was systematic knowledge acquisition, conducted through two parallel task tool calls that spawned subagents to explore different parts of the codebase simultaneously.

The planning message [msg 1359] then synthesized this knowledge into a four-wave roadmap for Phase 5, with Wave 1 focused on core CSR infrastructure. The assistant then executed Wave 1 methodically: create the crate, implement the types, implement the evaluator, integrate into the workspace, fix bugs (the enforce method had a borrowing issue that was caught and fixed in message [msg 1368]), and update dependencies.

The todowrite in message [msg 1377] is the capstone of this process — the moment when the assistant steps back, assesses that all Wave 1 tasks are complete, and signals readiness for the next wave. It is a small message with large implications.

What Comes Next

The TODOs that remain pending tell the story of what comes after this milestone. Wave 2 will implement specialized MatVec paths with fast-paths for coefficient and boolean witnesses. The integration with bellperson's prover will replace ProvingAssignment with the PCE-based evaluation. A cuzk-bench extract-pce command will validate the PCE against real circuits. And ultimately, Waves 3 and 4 will tackle pre-computed Split MSM topology and SnarkPack pipeline integration.

But for now, message [msg 1377] stands as a quiet but significant milestone: the foundation for a paradigm shift in how Filecoin SNARK proofs are generated, from circuit synthesis to sparse matrix-vector multiplication. The code compiles. The types are sound. Phase 5 has begun.