Appendix C: Field Equations Cheat Sheet

A quick reference for the core equations that power zero-knowledge proof systems.

Schwartz-Zippel Lemma

The most important bound in the book.

For a non-zero polynomial $p(X_1,\dots ,X_n)$ of total degree $d$ over a field $\mathbb{F}$:

$$\underset{r\leftarrow {\mathbb{F}}^n}{\mathrm{Pr}}[p(r)=0]\le \frac{d}{|\mathbb{F}|}$$

Consequence: Random evaluation catches cheating with probability $\ge 1-d/|\mathbb{F}|$.

Multilinear Extensions

Lagrange Basis Polynomial

For $w\in \{0,1{\}}^n$:

$$L_w(X)=\prod _{i=1}^n\left(w_i\cdot X_i+(1-w_i)(1-X_i)\right)$$

Property: $L_w(w)=1$ and $L_w(b)=0$ for $b\ne w$.

Multilinear Extension Formula

For $f:\{0,1{\}}^n\to \mathbb{F}$:

$$\tilde{f}(X)=\sum _{w\in \{0,1{\}}^n}f(w)\cdot L_w(X)$$

Equality Polynomial

$$\widetilde{\text{eq}}(X,Y)=\prod _{i=1}^n\left(X_i{Y}_i+(1-X_i)(1-Y_i)\right)$$

Property: $\widetilde{\text{eq}}(a,b)=1$ if $a=b$, else $0$ (on hypercube).

Sum-Check Protocol

Dimensions: Vector size $N=2^n$; protocol runs $n$ rounds.

The Claim

Prove: $$H=\sum _{b\in \{0,1{\}}^n}g(b_1,\dots ,b_n)$$

Round $i$ Polynomial

Prover sends: $$s_i(X_i)=\sum _{b_{i+1},\dots ,b_n\in \{0,1\}}g(r_1,\dots ,r_{i-1},X_i,b_{i+1},\dots ,b_n)$$

Verifier Checks

• Round 1: $s_1(0)+s_1(1)=H$
• Round $i>1$: $s_i(0)+s_i(1)=s_{i-1}(r_{i-1})$
• Final: query oracle at $(r_1,\dots ,r_n)$ to check $s_n(r_n)=g(r_1,\dots ,r_n)$

Soundness

$$ϵ\le \frac{n\cdot d}{|\mathbb{F}|}$$

where $n$ is the number of variables and $d$ is the maximum individual degree. (More precisely: ${\sum }_i{d}_i/|\mathbb{F}|$ where $d_i$ is the degree in variable $i$.)

Vanishing Polynomials

Over Roots of Unity

For domain $H=\{1,\omega ,{\omega }^2,\dots ,{\omega }^{n-1}\}$ where ${\omega }^n=1$:

$$Z_H(X)=X^n-1$$

Property: $Z_H({\omega }^i)=0$ for all $i$, and $Z_H(r)\ne 0$ for $r\notin H$.

Over Boolean Hypercube

For proving a polynomial vanishes on $\{0,1{\}}^n$, use the univariate identity:

$$Z_{\{0,1\}}(X)=X(X-1)$$

applied variable by variable in multilinear settings.

R1CS and QAP

R1CS Constraint

Dimensions: Matrices $A,B,C$ are $m\times n$; witness $z$ is $n\times 1$; result is $m\times 1$.

For witness vector $z=(1,x,w)$:

$$(A\cdot z)\circ (B\cdot z)=C\cdot z$$

where $\circ$ is entry-wise multiplication.

QAP Polynomial Identity

Define polynomials $A(X),B(X),C(X)$ by interpolating constraint matrices.

The constraint system is satisfied iff:

$$A(X)\cdot B(X)-C(X)=H(X)\cdot Z_H(X)$$

where $Z_H(X)={\prod }_{\alpha \in H}(X-\alpha )$ is the vanishing polynomial.

KZG Polynomial Commitments

Dimensions: Polynomial degree $<D$; SRS size $D+1$ elements.

Structured Reference String (SRS)

Secret $\tau$; public: $(g,g^{\tau },g^{{\tau }^2},\dots ,g^{{\tau }^D})$

Commitment

For $f(X)={\sum }_i{c}_i{X}^i$:

$$C=g^{f(\tau )}=\prod _i(g^{{\tau }^i}{)}^{c_i}$$

Evaluation Proof

To prove $f(z)=v$: (Prover knows $f(X)$; Verifier knows $C$, $z$, $v$)

1. Compute quotient: $w(X)=\frac{f(X)-v}{X-z}$
2. Proof: $\pi =g^{w(\tau )}$

Verification (Pairing Check)

$$e(\pi ,g^{\tau }\cdot g^{-z})=e(C\cdot g^{-v},g)$$

Equivalently:

$$e(g^{w(\tau )},g^{\tau -z})=e(g^{f(\tau )-v},g)$$

FRI Folding

Split Polynomial

For $f(X)=f_E(X^2)+X\cdot f_O(X^2)$:

• $f_E(Y)$: even coefficients
• $f_O(Y)$: odd coefficients

Folding with Challenge $\alpha$

$$f_1(Y)=f_E(Y)+\alpha \cdot f_O(Y)$$

Property: $\mathrm{deg}(f_1)<\mathrm{deg}(f)/2$

Consistency Check

At query point $x$ (where $-x$ is its conjugate on the same coset), verify:

$$f_1(x^2)=\frac{f(x)+f(-x)}{2}+\alpha \cdot \frac{f(x)-f(-x)}{2x}$$

This uses: $f_E(x^2)=\frac{f(x)+f(-x)}{2}$ and $f_O(x^2)=\frac{f(x)-f(-x)}{2x}$.

AIR (Algebraic Intermediate Representation)

Trace Polynomials

For a trace matrix with $w$ registers and $T$ timesteps, interpolate each column over domain $H=\{1,\omega ,\dots ,{\omega }^{T-1}\}$:

$$P_j({\omega }^i)=\text{trace}[i][j]$$

Transition Constraints

For a constraint "register 0 at next step equals $f$ of current registers":

$$P_0(\omega X)=f(P_0(X),P_1(X),\dots )$$

The shift $\omega X$ accesses "next row" values. Define constraint polynomial:

$$C(X)=P_0(\omega X)-f(P_0(X),P_1(X),\dots )$$

Quotient Check

Valid trace iff $C(X)$ vanishes on transition domain $H^{\prime }=\{1,\omega ,\dots ,{\omega }^{T-2}\}$:

$$Q(X)=\frac{C(X)}{Z_{H^{\prime }}(X)}$$

is a polynomial (not rational function).

Boundary Constraints

Pin inputs/outputs. For $P_j({\omega }^k)=v$:

$$\frac{P_j(X)-v}{X-{\omega }^k}$$

must be a polynomial.

PLONK

Gate Equation

$$Q_L(X)\cdot a(X)+Q_R(X)\cdot b(X)+Q_O(X)\cdot c(X)+Q_M(X)\cdot a(X)\cdot b(X)+Q_C(X)=0$$

on domain $H=\{1,\omega ,{\omega }^2,\dots ,{\omega }^{n-1}\}$.

Permutation Grand Product

Accumulator $Z(X)$ satisfies:

$$Z(1)=1$$

$$Z({\omega }^{i+1})=Z({\omega }^i)\cdot \frac{(a_i+\beta {\omega }^i+\gamma )(b_i+\beta k_1{\omega }^i+\gamma )(c_i+\beta k_2{\omega }^i+\gamma )}{(a_i+\beta {\sigma }_a({\omega }^i)+\gamma )(b_i+\beta {\sigma }_b({\omega }^i)+\gamma )(c_i+\beta {\sigma }_c({\omega }^i)+\gamma )}$$

Property: The product telescopes, so $Z({\omega }^n)=Z(1)=1$ iff all copy constraints hold.

Quotient Check

All constraints satisfied iff there exists $t(X)$ with:

$$\text{(gate)}+\alpha \cdot \text{(permutation)}=t(X)\cdot Z_H(X)$$

Groth16

Public Input Combination

Given public inputs $(z_0,z_1,\dots ,z_{\ell })$ where $z_0=1$:

$${\text{vk}}_x=\sum _{j=0}^{\ell }{z}_j\cdot ({\text{vk}}_{IC}{)}_j$$

where $({\text{vk}}_{IC}{)}_j=g_1^{\frac{\beta A_j(\tau )+\alpha B_j(\tau )+C_j(\tau )}{\gamma }}$ are verification key elements.

Verification Equation

Given proof $({\pi }_A,{\pi }_B,{\pi }_C)\in {\mathbb{G}}_1\times {\mathbb{G}}_2\times {\mathbb{G}}_1$:

$$e({\pi }_A,{\pi }_B)\stackrel{?}{=}e(g_1^{\alpha },g_2^{\beta })\cdot e({\text{vk}}_x,g_2^{\gamma })\cdot e({\pi }_C,g_2^{\delta })$$

Verification cost: One MSM (size $\ell$) + 3-4 pairings, independent of circuit size.

Proof Size

3 group elements: 128 bytes over BN254 (32 + 64 + 32 for ${\mathbb{G}}_1$, ${\mathbb{G}}_2$, ${\mathbb{G}}_1$).

Lookup Arguments

Plookup Identity

For lookups $f=\{f_1,\dots ,f_n\}$ and table $t=\{t_1,\dots ,t_d\}$, let $s=\text{sort}(f\cup t)$.

$$\prod _i(\gamma +f_i)\cdot \prod _i(\gamma (1+\beta )+t_i+\beta t_{i+1})\cdot (1+\beta {)}^n$$

$$=\prod _i(\gamma (1+\beta )+s_i+\beta s_{i+1})$$

Property: Equality holds iff $f\subseteq t$.

LogUp Identity

For lookups $f=\{f_1,\dots ,f_n\}$ into table $t=\{t_1,\dots ,t_d\}$ with multiplicities $m_j$:

$$\sum _{i=1}^n\frac{1}{\gamma +f_i}=\sum _{j=1}^d\frac{m_j}{\gamma +t_j}$$

Property: Equality holds iff each $f_i\in t$ and $m_j$ counts occurrences correctly.

Soundness: By Schwartz-Zippel, equality holds with probability $\ge 1-(n+d)/|\mathbb{F}|$ over random $\gamma$.

Advantage: No sorting required; additive structure enables multi-table batching.

GKR Protocol

Dimensions: Layer $i$ has $S_i$ gates; layer $i+1$ (inputs) has $S_{i+1}$ gates; $k={\log }_2{S}_i$.

Layer Reduction

For layered circuit with values $V^{(i)}$ at layer $i$:

$$V^{(i)}(r)=\sum _{p,q\in \{0,1{\}}^k}{\widetilde{\text{add}}}^{(i)}(r,p,q)\cdot (V^{(i+1)}(p)+V^{(i+1)}(q))$$ $$+{\widetilde{\text{mult}}}^{(i)}(r,p,q)\cdot V^{(i+1)}(p)\cdot {\tilde{V}}^{(i+1)}(q)$$

Sum-Check Reduction

A claim about $V^{(i)}(r)$ reduces via sum-check to claims about $V^{(i+1)}(p^{\ast })$ and ${\tilde{V}}^{(i+1)}(q^{\ast })$ for random $p^{\ast },q^{\ast }$.

Soundness: Compound over $d$ layers, each with $O(\log n)$ sum-check rounds.

Inner Product Argument (IPA)

The Claim

Prove $⟨\vec{a},\vec{b}⟩=c$ for committed $\vec{a}$.

Folding Step

Given challenge $\alpha$:

$${\vec{a}}^{\prime }=\alpha \cdot {\vec{a}}_L+{\alpha }^{-1}\cdot {\vec{a}}_R$$ $${\vec{b}}^{\prime }={\alpha }^{-1}\cdot {\vec{b}}_L+\alpha \cdot {\vec{b}}_R$$

Property: $⟨{\vec{a}}^{\prime },{\vec{b}}^{\prime }⟩=⟨\vec{a},\vec{b}⟩+{\alpha }^{2}L+{\alpha }^{-2}R$

where $L=⟨{\vec{a}}_L,{\vec{b}}_R⟩$ and $R=⟨{\vec{a}}_R,{\vec{b}}_L⟩$.

Proof Size

$O(\log n)$ group elements after $\log n$ rounds.

Nova Folding

Relaxed R1CS

Standard R1CS: $(A\cdot z)\circ (B\cdot z)=C\cdot z$

Relaxed R1CS with scalar $u$ and error $E$:

$$(A\cdot z)\circ (B\cdot z)=u\cdot (C\cdot z)+E$$

A satisfying instance has $u=1$ and $E=0$.

Folding Two Instances

Given instances $(u_1,E_1,z_1)$ and $(u_2,E_2,z_2)$, with challenge $r$:

$$u=u_1+r\cdot u_2$$ $$E=E_1+r\cdot T+r^2\cdot E_2$$ $$z=z_1+r\cdot z_2$$

where $T$ is the "cross-term" computed by the prover.

Property: If both inputs satisfy relaxed R1CS, so does the folded instance.

Fiat-Shamir Transform

Challenge Derivation

$$r_i=H(\text{transcript prefix including all previous messages})$$

Security Requirement

The hash must include:

• The public statement $x$
• All previous commitments $C_1,\dots ,C_{i-1}$
• All previous challenges $r_1,\dots ,r_{i-1}$

Complexity Summary

Field Sizes (Common Choices)

*Small fields require extension fields for cryptographic security; base field security refers to the overall system design.

Quick Reference: What to Use When

Proving a sum over hypercube: Sum-check protocol

Encoding data as polynomial: Multilinear extension (hypercube) or Lagrange interpolation (roots of unity)

Binding prover to polynomial: KZG (trusted setup, constant size), FRI (transparent, log² size), IPA (no pairings, log size)

Checking polynomial identity on a domain: Quotient by $Z_H(X)=X^n-1$ for roots of unity

Checking table membership: Lookup argument (Plookup with sorting, LogUp without)

Verifying circuit layer-by-layer: GKR protocol with sum-check at each layer

Incremental computation: Nova folding (amortize SNARK cost across steps)

Eliminating interaction: Fiat-Shamir with complete transcript hashing