Sumcheck

The sumcheck/ module runs the layered sumcheck protocol over a compiled Circuit<Field> from the Compiler. It reduces “this circuit evaluates to zero on this witness” to a short transcript of polynomial evaluations. You’ll rarely call it directly — zk/ composes it with Ligero for you — but this is the page you read to understand what the transcript contains and where cost scales with circuit shape.

When to reach for it

You’re sizing a proof: depth and layer widths of your compiled circuit drive sumcheck’s work.
You’re implementing a sumcheck-only flow without witness-hiding (rare, but supported).
You’re debugging a “wrong claim propagated” bug and want to inspect the per-layer transitions.

Design overview

Circuit shape. Circuit<Field> (from sumcheck/circuit.h) is the compiler’s output: a vector of Layer<Field> entries, each with nw input wires and $\text{logw} = \log_2 \text{nw}$ binding rounds for the wire dimension, plus the copy dimension nc with $\text{logc} = \log_2 \text{nc}$ representing batched instances that are proven in parallel. The 32-byte id[32] field is the canonical circuit hash — the prover and verifier must agree on it or the transcript will diverge (see Compiler).

Three representations of a quadratic form. Each layer carries a quadratic relation between its output wires and its input wires, and Longfellow keeps three representations of it so that compilation, evaluation, and reduction each use the shape that is cheapest for their step:

EQuad<Field> — fully-expanded during compilation, one entry per non-zero coefficient as $(g, h[0], h[1], v)$ tuples (two separate wire indices h[0] and h[1]). This is the only representation that can be canonicalized, so it’s the form the compiler deduplicates against.
Quad<Field> — delta-encoded and constant-pooled; produced by QuadBuilder<Field>::compress(). This is what the prover and verifier actually consume. Users don’t touch QuadBuilder directly; they receive compressed Circuit::l[i].quad from the compiler.
HQuad<Field> — intermediate form after the gate dimension g has been bound; used during per-layer sumcheck to collapse toward a single scalar as the hand (wire) variables are bound.

Layered structure. Sumcheck is run per layer, not once over the whole circuit. Each layer’s quadratic assertion — “wire value at this layer is the sum over pairs of input wires of coefficient times left-wire times right-wire” — becomes its own sumcheck claim. The two reduced scalars at the end of one layer (wc[0] and wc[1] in LayerProof<Field>, one per hand) become the input-binding claims of the next layer, and the verifier folds them with a random linear combination using alpha before recursing.

API surface

Prover

Prover<Field> wraps ProverLayers<Field>.

Constructor: Prover(const Field& F).
Entry point:
```
void prove(Proof<Field>* proof,
           const Proof<Field>* pad,
           const Circuit<Field>* circ,
           const inputs& in,
           Transcript& t);
```
pad is optional; pass nullptr unless you’re composing with zk/’s zero-knowledge pad (in which case zk/ fills it in for you). prove always returns; if the witness does not satisfy the circuit it simply produces a proof that will not verify.
Internally, ProverLayers::eval_circuit() materialises per-layer wire values and then layer() runs the per-layer sumcheck, writing polynomials into proof->l[i] and carrying wc[0], wc[1] forward.

Verifier

Verifier<Field> is stateless — construction is deleted and everything runs through the static entry point:


static bool verify(const char** why,
                   const Circuit<Field>* circ,
                   const Proof<Field>* proof,
                   std::unique_ptr<Dense<Field>> W,
                   Transcript& ts,
                   const Field& F);

Returns true iff the proof is valid. On failure, *why is set to a short human-readable reason (for example "got != cl.claim[hand]" when the final input binding doesn’t match). The verifier consumes W because the last step binds the copy variables into the witness wires and compares the bound scalars against the two hand-claims that fell out of the last layer’s sumcheck.

Transcript

TranscriptSumcheck<Field> wraps a shared Transcript (see Transcript & Randomness) and exposes the only three operations sumcheck performs against it:

begin_circuit(Q, G) — extract the initial copy challenge $Q$ (length kMaxBindings = 40) and output-gate challenge $G$ .
begin_layer(alpha, beta, i) — extract the per-layer fold coefficient alpha and the assert-zero coefficient beta.
round(poly) — append a sumcheck round polynomial (degree 3 for copy rounds, degree 2 for wire rounds) and return the next Fiat-Shamir challenge. The p(1) coefficient is omitted from the transcript because it is implied by the running claim.

What sumcheck proves

Sumcheck in one paragraph. The basic sumcheck protocol reduces the statement “sum over the boolean hypercube $\{0,1\}^n$ of a multivariate polynomial $f$ equals $S$ ” to a single random-point evaluation $f(r_1, \ldots, r_n)$ . Each round, the prover sends a univariate polynomial — the partial sum over the remaining variables — the verifier checks that its evaluation at $0$ plus its evaluation at $1$ equals the running claim, then picks a random challenge $r_i$ , and the protocol recurses on $n-1$ variables. After $n$ rounds the original sum is reduced to evaluating $f$ at one random point, which is either checked directly or handed off to another protocol.

Layered sumcheck in Longfellow. Each circuit layer $\ell$ carries a quadratic relation $W_{\ell+1}[g] = \sum_{h_0, h_1} \text{quad}_\ell[g, h_0, h_1] \cdot W_\ell[h_0] \cdot W_\ell[h_1]$ , with the nc copies dimension multiplexed in via an equality polynomial $\text{EQ}$ . Sumcheck runs on this relation per layer, consuming $\text{logc} + 2 \cdot \text{logw}$ rounds per layer — first binding the copy variables (degree-3 polynomials), then the two wire dimensions hand-by-hand (degree-2 polynomials). The reduction of the final (input) layer produces two wire claims, which Verifier::verify checks directly against the bound witness W, closing the recursion.

Example

Adapted from lib/sumcheck/testing.h:


Prover<Field> prover(F);
Transcript tsp((uint8_t*)"testing", 7);
prover.prove(&proof, /*pad=*/nullptr, circuit.get(), inputs, tsp);
 
// --- verifier side ---
Transcript tsv((uint8_t*)"testing", 7);
const char* why = "ok";
bool ok = Verifier<Field>::verify(&why, circuit.get(), &proof,
                                  std::move(W), tsv, F);

The "testing" domain separator must match on both sides; this is what Transcript uses as the Fiat-Shamir seed before either party writes a byte.

See it used

sumcheck_test.cc — end-to-end prover/verifier tests across several field backends.
testing.h — run_prover and run_verifier helpers, the smallest working examples of the flow above.

Compiler — produces Circuit<Field>
ZK (top-level) — composes sumcheck with Ligero
Ligero — downstream constraint-system consumer
Transcript & Randomness