Implementing sumcheck and GKR from first principles in Rust

01 · Motivation

Start before the proof becomes bytes

A serialized proof, verification key, or public-input file looks like arbitrary binary because it is the final output of several layers: field elements, polynomial claims, transcript challenges, commitments, curve points, and a chosen encoding. Reading the bytes first hides the structure that makes the verifier believe them.

My study repository builds that structure upward. The modules cover finite-field polynomial arithmetic, interpolation, FFTs, multilinear extensions, sumcheck, GKR, and KZG experiments. Correctness and visibility take priority over performance; this is not presented as a production proving library.

The implementation uses arkworks field types over BN254 and a Keccak transcript. That makes the algebra concrete while keeping the code generic over PrimeField where possible.

02 · Sumcheck

The starting claim is a sum over the Boolean hypercube

Let f be an n-variable polynomial over a finite field. The prover claims that summing f over every Boolean assignment equals H. Enumerating all 2ⁿ points defeats the purpose for a verifier, so the protocol removes one variable per round.

In round one, the prover sends a univariate polynomial g₁(X) obtained by summing over every remaining Boolean variable. The verifier first checks g₁(0) + g₁(1) = H. It then samples a challenge r₁ and replaces the original claim with g₁(r₁). Round two repeats the process for the next variable.

03 · Representation

For a multilinear table, each round polynomial is determined by two values

The basic sumcheck module stores a multilinear polynomial as its evaluation table. split_and_sum divides that table into the xᵢ = 0 and xᵢ = 1 halves, then sums each half. Because the polynomial is multilinear in the active variable, those two values determine the entire round polynomial by linear interpolation.

The proof therefore stores each basic round as [gᵢ(0), gᵢ(1)]. After the transcript supplies rᵢ, partial evaluation folds the table and halves its length. This data movement is the protocol reduction made visible in code.

fn split_and_sum<F: PrimeField>(evals: &[F]) -> [F; 2] {
    let (left, right) = evals.split_at(evals.len() / 2);
    [left.iter().copied().sum(), right.iter().copied().sum()]
}

// g(r) from g(0), g(1)
let next_claim = g0 + challenge * (g1 - g0);

04 · Fiat–Shamir

The transcript replaces verifier messages - but ordering becomes security-critical

The interactive verifier would sample a fresh random challenge after seeing each round polynomial. The implementation makes the proof non-interactive with a Keccak transcript: absorb the original evaluation table and claimed sum, absorb each round polynomial, then squeeze a field element from the accumulated hash state.

Prover and verifier must absorb exactly the same bytes in exactly the same order. Any missing field, ambiguous serialization, or inconsistent domain separation can fork the transcript or allow messages from another protocol context to be replayed.

The current transcript is intentionally minimal. A hardened version should add protocol and version domain separators, length-prefix variable inputs, make squeeze mutate state explicitly, and include negative tests showing that reordered or omitted messages fail.

for round_poly in proof.round_polys {
    if claimed_sum != round_poly.iter().sum() {
        return false;
    }

    transcript.absorb(&serialize(round_poly));
    let r: F = transcript.squeeze();
    claimed_sum = round_poly[0] + r * (round_poly[1] - round_poly[0]);
    challenges.push(r);
}

claimed_sum == original_poly.evaluate(&challenges)

05 · GKR

GKR applies the same reduction to a layered circuit

A layered arithmetic circuit gives each layer a table of wire values. Its multilinear extension Wᵢ lets the verifier ask for a layer value at a random point rather than inspect every wire. Wiring predicates addᵢ and mulᵢ encode which previous-layer wires feed each addition or multiplication gate.

For one output index a and child indices b and c, the layer relation combines those objects: an addition gate contributes Wᵢ₊₁(b) + Wᵢ₊₁(c); a multiplication gate contributes their product. Sumcheck reduces the large sum over b and c to evaluations of the previous layer at two random points.

The implementation then absorbs those W(b) and W(c) evaluations, derives alpha and beta, and folds the two claims into one linear combination for the next layer. Repeating this process walks the verifier from the output claim back toward the public input layer.

06 · Concrete test

The test circuit makes the layer claims inspectable

The repository test begins with inputs [1,2,3,4,5,6,7,8]. The first computed layer contains one addition and three multiplications, producing [3,12,30,56]. The next produces [15,1680], and the final addition produces 1695.

That tiny circuit is useful because every wire value can be calculated by hand while the GKR code still constructs wiring polynomials, runs a sumcheck proof per layer, evaluates W(b) and W(c), and folds the next claim with transcript-derived alpha and beta.

inputs        [1, 2, 3, 4, 5, 6, 7, 8]
layer 2       [1+2, 3×4, 5×6, 7×8] = [3, 12, 30, 56]
layer 1       [3+12, 30×56]          = [15, 1680]
output        [15+1680]              = [1695]

07 · Engineering notes

What is implemented - and what still separates it from a proof system

The repository contains real prover and verifier reductions, but several pieces remain educational. The basic verifier receives the full polynomial. GKR and circuit representation use cloning and dense evaluation tables. Debug output lives on hot paths. Transcript framing needs hardening, and there is no commitment binding the verifier to a large private witness or oracle.

The next useful work is not to add a polished proof-byte serializer. It is to strengthen invariants: mutate every round polynomial and confirm rejection; vary circuit depth and non-power-of-two shapes; domain-separate every transcript; measure prover field operations; and place a polynomial commitment at the boundary where the verifier currently receives a full object.

That progression is why implementing protocols is valuable. It exposes exactly where algebra ends and cryptographic binding begins - and it makes the remaining gaps impossible to mistake for completed security.

• Add adversarial and property-based tests for proof mutation
• Harden transcript framing and domain separation
• Replace dense clones with clearer ownership and streaming folds
• Bind large polynomial claims with an explicit commitment layer
• Document complexity from measured field operations, not only asymptotics