aztecprotocol/aztec-packages/sumcheck

Sumcheck Protocol Implementation

Overview

Sumcheck is the core interactive proof protocol (made non-interactive via Fiat-Shamir) that reduces a multilinear polynomial identity over a boolean hypercube {0,1}^d to a single-point evaluation. It is the central component of the Honk proving system.

Claim: sum_{X in {0,1}^d} pow_beta(X) * F(P_1(X), ..., P_N(X)) = 0

where P_i are multilinear witness/selector polynomials, F is the batched relation polynomial, and pow_beta is the gate separator polynomial.

Code Layout

Core: barretenberg/cpp/src/barretenberg/sumcheck/

• sumcheck.hpp — Prover, Verifier, and compile-time handler structs
• sumcheck_round.hpp — Per-round logic for both prover and verifier
• sumcheck_output.hpp — Output struct (challenge vector, claimed evaluations, ZK data)
• zk_sumcheck_data.hpp — Libra masking polynomials and running sums
• Sumcheck.md — Detailed mathematical documentation

Supporting:

• polynomials/gate_separator.hpp — pow_beta polynomial
• polynomials/row_disabling_polynomial.hpp — ZK row masking
• flavor/partially_evaluated_multivariates.hpp — Book-keeping table for partial evaluation
• flavor/flavor_concepts.hpp — Flavor dispatch concepts
• relations/ — Relation types, utilities, parameters, nested containers

Tests:

• sumcheck/sumcheck.test.cpp — Prover/verifier correctness, ZK, Grumpkin, failure cases
• sumcheck/sumcheck_round.test.cpp — Round-level: univariates, batching, check_sum, padding
• ultra_honk/sumcheck.test.cpp — Integration test with real UltraFlavor circuit

Callers:

• ultra_honk/ultra_prover.cpp / ultra_verifier.cpp — Ultra/Mega/MegaZK flavors
• eccvm/eccvm_prover.cpp / eccvm_verifier.cpp — Grumpkin committed sumcheck
• hypernova/ — HyperNova folding
• chonk/batched_honk_translator/ — Batched Honk+Translator

Architecture

Proving Pipeline

OINK PHASE (pre-sumcheck)
  Commit to wires, lookup counts, log-deriv inverses, permutation product.
  Draw alpha (subrelation separator) and gate challenges (beta_0,...,beta_{d-1}).
 
SUMCHECK PHASE
  For round i = 0..d-1:
    Compute round univariate (extend edges, accumulate relations, batch with pow)
    [ZK] Add Libra masking contribution, subtract row disabling correction
    Send round univariate to transcript, draw challenge u_i
    Partially evaluate all polynomials at u_i
  [Padding] For round i = d..virtual_log_n-1:
    Send zero/virtual univariate, draw challenge
  Extract claimed evaluations from top of book-keeping table
 
PCS PHASE (post-sumcheck)
  [ZK] SmallSubgroupIPA proves Libra evaluation
  Shplemini reduces multivariate opening claims to univariate
  KZG/IPA proves the univariate opening

Key Design Patterns

Compile-time flavor dispatch: The Flavor template parameter bundles all configuration. Handler structs (RoundUnivariateHandler, VerifierZKCorrectionHandler) use if constexpr and specializations to select behavior at compile time based on flavor traits.

Prover round structure: Each round extends polynomial evaluations from {0,1} to {0,...,D}, accumulates relation contributions into univariate accumulators, then batches over relations using alpha powers and the gate separator factor.

Verifier round structure: Each round checks S(0) + S(1) == target_sum, then computes the next target as S(u_i). The final step evaluates the full batched relation at the challenge point and compares.

Committed sumcheck (Grumpkin/ECCVM path): Instead of sending round univariate evaluations in the clear, the prover commits to each round univariate and sends the commitment plus evaluations at {0, 1} only. The verifier does NOT perform the usual check_sum and compute_next_target_sum during sumcheck — it defers all consistency checks to the PCS phase, where Shplemini batch-verifies the round univariate commitments together with the polynomial opening claims. This is controlled by IsGrumpkinFlavor and handled via the RoundUnivariateHandler and SumcheckVerifierRound specializations.

Book-keeping table: Partial evaluation halves the polynomial table each round. After d rounds, a single row remains holding the claimed evaluations at the challenge point.

Flavor System

Each flavor provides a compile-time configuration bundle that parameterizes sumcheck.

Key Flavor Traits

Dispatch Points

Relations System

A relation is a polynomial constraint (or set of sub-constraints) that must hold across the execution trace. Each relation has:

• SUBRELATION_PARTIAL_LENGTHS — array of algebraic degrees per subrelation
• SUBRELATION_LINEARLY_INDEPENDENT — controls whether each subrelation is multiplied by pow_beta
• accumulate() — evaluates the relation given extended edges and parameters
• skip() (optional) — returns true when a row contributes nothing

Subrelation Independence

• Linearly independent (default): must hold at every row; multiplied by pow_beta
• Linearly dependent (e.g., lookup sum identity): must sum to zero globally; NOT multiplied by pow_beta

Alpha Batching

Powers of a single challenge alpha separate subrelations. During batching, each subrelation accumulator is scaled by its alpha power, extended to full degree, then combined with the appropriate pow factor (or without, for linearly dependent subrelations).

Gate Separator Polynomial (pow_beta)

pow_beta(X_0,...,X_{d-1}) = prod_{k=0}^{d-1} (1 - X_k + X_k * beta_k)

Precomputed on the full hypercube via parallel recurrence. Each round contributes one linear factor (1-X_i + X_i*beta_i). A partial evaluation result accumulates across rounds. When betas is empty (multilinear batching), degenerates to constant 1.

ZK Sumcheck

Three mechanisms provide zero-knowledge:

1. Libra Masking

Adds a structured random multivariate G(X) = a_0 + g_0(X_0) + ... + g_{d-1}(X_{d-1}) scaled by a Fiat-Shamir challenge. Each round's univariate gets a Libra correction. The concatenated Libra univariates are committed and their evaluation is proved via SmallSubgroupIPA.

2. Row Disabling + In-Place Masking (Top-of-Trace)

The first NUM_DISABLED_ROWS_IN_SUMCHECK=4 rows of the trace are reserved. For ZK flavors, NUM_MASKED_ROWS=3 random values are written directly into witness polynomials at rows 1, 2, 3 (row 0 is the zero row for shifts). The row disabling polynomial (1-L) vanishes at rows 0-3, so the relation sum is unaffected. This adds +1 to the round univariate degree for ZK flavors.

The layout is uniform across ZK and non-ZK — non-ZK flavors have zeros in these rows, so relations are trivially satisfied there without row disabling.

`excluded_head_size` invariant: Non-zero only when the flavor needs the offset-area path — currently this is Flavor::HasZK:

size_t excluded_head_size = Flavor::HasZK ? Flavor::TRACE_OFFSET : 0;

The main sumcheck loop skips the first excluded_head_size edge pairs; compute_offset_area_contribution handles them separately, applying per-relation row-disabling factors ((1-L) for main-domain rels, L for offset-only rels — see below), and adds the result to the main-loop contribution. Non-ZK flavors keep excluded_head_size = 0 in round 0 (head rows are all zeros, processed uniformly by the main loop); after round 0 it flips to 2 for the partially-evaluated head-edge pair (harmless for non-ZK since those rows remain zero).

3. Witness Masking in PCS

Masking values are written directly into the polynomials (in-place), so commit(poly) produces the correct masked commitment directly. A Gemini masking polynomial ensures PCS opening proofs remain zero-knowledge.

Offset-Only Relations (boundary constraints on rows 0..3)

A relation tagged static constexpr bool IS_OFFSET_ONLY = true (detected by the IsOffsetOnlyRelation concept) has its round-univariate contribution scaled by L(X) instead of (1 - L)(X), so it fires only on the offset area (rows 0..TRACE_OFFSET-1). The sumcheck dispatch (extend_and_batch_univariates and scale_and_batch_elements) picks the factor per relation at compile time.

Used by MegaEccOpBoundaryRelation (in ecc_op_queue_relation.hpp) to enforce ecc_op_wire_j = 0 on rows 0..3 for MegaZK, making the boundary verifier-visible. The has_any_offset_only_relation_v<Flavor> trait checks whether any relation in the flavor's Relations tuple opts in. Not compatible with ZK flavors whose masked rows overlap with the constrained entities.

Batched Honk Translator Integration

The batched translator combines MegaZK and Translator into a joint sumcheck/PCS. MegaZK uses += compute_offset_area_contribution(... rdp) for the head rows. Translator has no offset-area contribution (it uses tail masking independently). After round 0, excluded_head_size = 2 for the MegaZK round (the offset area collapses to 1 edge pair).

Virtual Rounds and Padding

For constant proof size (recursive verification):

• Real rounds (0 to multivariate_d - 1): standard sumcheck
• Virtual/padding rounds (multivariate_d to virtual_log_n - 1): polynomials treated as zero-extended

With top-of-trace masking, the row-disabling polynomial is circuit-size independent, so all sumcheck rounds are processed uniformly by the verifier — no padding indicator needed.

Transcript / Fiat-Shamir Protocol

Prover writes round univariates (or commitments + evals for Grumpkin), final multilinear evaluations, and ZK-related data (Libra sum, evaluation). Challenges drawn: gate challenges, alpha, round challenges u_i, and Libra challenge. Translator sends minicircuit evaluations mid-sumcheck after the relevant round.

Performance Optimizations

• Row skipping: Identifies contiguous blocks of non-zero rows; threads iterate only over non-zero blocks
• AVM chunking: Splits trace into chunks distributed among threads
• Effective round size: Avoids iterating trailing zeros by finding the actual end of witness polynomials
• Short monomials: Produces degree-1 univariates during edge extension, deferring full-degree extension to batching
• Subrelation skipping: Relations can define a skip() method to avoid accumulation when selectors are zero

Soundness & Completeness Principles

These principles are distilled from historical bugs. They represent recurring vulnerability patterns in sumcheck and its surrounding infrastructure.

Recursive Verification: Constraints vs Native Checks

In recursive (circuit-based) verifiers, the prover controls all witness values. Any check that doesn't produce a circuit constraint is useless for soundness.