The Spartan argument

This chapter describes the R1CS-specific reduction that sits above the generic sum-check protocol. Spartan turns satisfaction of an R1CS instance into an outer zero-check over constraint rows, an inner matrix-evaluation sum-check over columns, and one final polynomial commitment opening for the committed witness.

From R1CS rows to a zero-check

For R1CS matrices \(A,B,C\) and assignment \(\mathbf{z}\), satisfaction means \[ (A\mathbf{z}) \circ (B\mathbf{z}) = C\mathbf{z}. \] Equivalently, the row error \[ \mathbf{e} = (A\mathbf{z}) \circ (B\mathbf{z}) - C\mathbf{z} \] vanishes at every constraint row. The vectors \(A\mathbf{z}\), \(B\mathbf{z}\), and \(C\mathbf{z}\) are viewed as tables on the padded row hypercube. If \(\ell_x=\log_2 m\), the outer layer batches all row equations into one weighted sum: \[ \sum_{\mathbf{x} \in \{0,1\}^{\ell_x}} W_\tau(\mathbf{x})\bigl(\widetilde{Az}(\mathbf{x})\widetilde{Bz}(\mathbf{x}) - \widetilde{Cz}(\mathbf{x})\bigr) = 0. \] The sum-check reduces this claim to one random row point \(r_x\). The summand contains a multilinear weight multiplied by the product \(\widetilde{Az}\,\widetilde{Bz}\), so an outer round polynomial can have degree three. Vega therefore uses cubic-with-additive-term prover routines for this layer.

Row weights in the two Vega variants

\(\mathrm{Vega}_{\mathrm{SC}}\) uses the equality-polynomial weight \[ W_\tau(\mathbf{x}) = \widetilde{\mathrm{eq}}(\tau,\mathbf{x}). \] In the reference implementation, the outer zero-check routine prove_cubic_with_additive_term_zk returns \(r_x\). The verifier recomputes \(\widetilde{\mathrm{eq}}(\tau,r_x)\) as tau_at_rx and checks the public values \[ \bigl[\tau_{r_x},\,\widetilde{X}(r_y’),\,\widetilde{A}(r_x,r_y)+r\widetilde{B}(r_x,r_y)+r^2\widetilde{C}(r_x,r_y)\bigr]. \]

\(\mathrm{Vega}_{\mathrm{MC}}\), the focus of this book, uses a powers-polynomial weight derived from \(\tau\). The powers polynomial is the multilinear extension whose Boolean evaluations are \(1,\tau,\tau^2,\dots\), with the bit ordering fixed by Notation and conventions. The folded step branch and the core branch pass through one batched outer round schedule rather than two independent schedules.

For \(\mathrm{Vega}_{\mathrm{MC}}\), the verifier recomputes the powers weight at \(r_x\) as tau_at_rx. It also recomputes \(\widetilde{\mathrm{eq}}(r_b,\rho)\), written eq_rho_at_rb, from the NeutronNova fold. The six public values pinned by the verifier circuit are, in order, \[ \tau_{r_x},\quad \widetilde{X}_{\mathrm{step}}(r_y’),\quad \widetilde{X}_{\mathrm{core}}(r_y’),\quad \widetilde{\mathrm{eq}}(r_b,\rho),\quad Q_{\mathrm{step}},\quad Q_{\mathrm{core}}, \] where \[ Q_\star = \widetilde{A}_\star(r_x,r_y)+r\widetilde{B}_\star(r_x,r_y)+r^2\widetilde{C}_\star(r_x,r_y) \] for \(\star\in\{\mathrm{step},\mathrm{core}\}\). The public-input polynomials \(\widetilde{X}_\star\) are evaluated at \(r_y’ = r_y[1..]\) — the inner point with its leading selector coordinate \(r_{y,0}\) dropped — while the matrix evaluations \(Q_\star\) use the full \(r_y\).

The inner matrix-evaluation sum-check

After the outer layer fixes \(r_x\), the matrix row variables are bound and the three matrices are combined with a fresh challenge \(r\): \[ \widetilde{ABC}_{r_x,r}(\mathbf{y}) = \widetilde{A}(r_x,\mathbf{y}) + r\,\widetilde{B}(r_x,\mathbf{y}) + r^2\,\widetilde{C}(r_x,\mathbf{y}). \] The inner sum-check proves the column-side claim \[ \sum_{\mathbf{y}} \widetilde{ABC}_{r_x,r}(\mathbf{y})\,\widetilde{z}(\mathbf{y}) \] over the padded column hypercube and reduces it to one column point \(r_y\). The summand is a product of two multilinear tables, so each inner round polynomial is quadratic. The generic routines for this shape are prove_quad and the batched zero-knowledge variant prove_quad_batched_zk; \(\mathrm{Vega}_{\mathrm{MC}}\) uses the batched variant to carry the folded step and core branches through the same challenge schedule.

Hand-off to the witness opening

The terminal inner claim contains \(\widetilde{z}(r_y)\). The verifier recomputes the public-input contribution directly from the public vector and the equality weights induced by \(r_y\). The witness contribution is obtained from the polynomial-commitment opening at \(r_y[1..]\). In \(\mathrm{Vega}_{\mathrm{MC}}\), this opening is the zero-knowledge linear inner-product argument stored as eval_arg.

The verifier then compares the resulting value of \(\widetilde{z}(r_y)\), together with the terminal matrix evaluation, against the final inner sum-check claim. This is the boundary between Spartan and Polynomial commitments and the ZK opening.

Challenge ownership

The challenges \(\tau\), \(r_x\), and \(r_y\) belong to Spartan’s row batching and sum-check reductions. The challenges \(\rho\) and \(r_b\) belong to NeutronNova folding, which produces the folded step instance that Spartan proves.

For background, see Multilinear polynomials, the sum-check primer, R1CS and its variants, and the generic sum-check protocol. The surrounding \(\mathrm{Vega}_{\mathrm{MC}}\) proving flow is described in Proving, and byte-exact transcript ordering is fixed in the transcript schedule.