Core Math for Verifiable Computing

\(k\)-variate polynomial \(f(x_1,...,x_k)\) over a finite field \(\mathbb F_p\)

\[ S = \sum_{b_1,...,b_k \in \{0,1\}}{f(b_1,...,b_k)} \] Where \(f\) is a multivariate polynomial, \(S\) is the sum of boolean hypercube evaluations of \(f\)

E.g., \(f(x_1, x_2) = 5 + 4x_1 + 3x_2 + 2x_1x_2 \to f(0, 0) = 5, f(0, 1) = 8, f(1, 0) = 9, f(1, 1) = 14 \to S = 36\)

• Number of evaluations in the sum: \(2^k\)
• Time to compute each evaluation: \(T\)
• Total time to compute the sum: \(2^k \times T\)

The sumcheck protocol is an interactive proof protocol to prove the correctness of a sumcheck problem.

For an n-variate multilinear polynomial, the classic "coefficients" view stores the \(2^n\) numbers \(c_b\) array. \[ g(x_1, \dots, x_n) = \sum_{b \in \{0,1\}^n} c_b \prod_{i=1}^n x_i^{b_i} \] Where \(b = (b_1,...,b_n)\) is an n-bit vector indexing the monomials of a multilinear polynomial (i.e., \((b_i \in \{0,1\})\) is the i-th bit of the vector \(b\)), and because each exponent is 0 or 1, every variable appears at most linearly in any term.

In cryptography, multilinear polynomials often operating in a large finite field, which cannot include real numbers. (Predictable, efficient to evaluate & manipulate and can apply random evaluation on Schwartz-Zippel Lemma).

In Arithmetic Circuits, which is a layered directed acyclic graph (DAG) where each gate computes an arithmetic operation (typically addition or multiplication) over a finite field, and where each gate in a layer depeneds only on gates from the previous layer). When we already know the circuits's wire-values on the boolean cube we can have the evaluation view of that circuit's multilinear polynomials. \[ (v_b \stackrel{\text{def}}{=} g(b_1,...,b_n))_{b \in \{0,1\}^n} \]

Unlike coefficients, the circuit's layer already spits these numbers \((v_b)\) out "for free", and these value is enough for us to use folding techniques to calculate its multilineal extensions (i.e., evaluating \(g(x)\) at \(x \in \{\mathbb F\}^n\))

Because \(g\) is linear in each coordinate we have, and since we want evaluate this polynomial at random points \(r \in \{\mathbb F\}\), for every fixed \(x_2,...,x_n\), let: \(g(t) = g(t, x_2, ..., x_n)\) the degree of \(t\) in \(h\) is \(\leq\) 1, so there are scalars \(a, b \in \mathbb F\) with \(h(t) = a \cdot t + b\). In other words, once we "zoom in" on a single axis, the graph is always a straight line.

Evaluating at the only two Boolean values of \(t\), which completes define that linear function, where \(h(0) = b, h(1) = a + b\), these give \(a = h(1) - h(0), b = h(0)\), plug them back into \(h(t)\): \[ h(t) = (h(1) - h(0)) \cdot t + h(0) = (1-t) \cdot h(0) + t \cdot h(1) \] So for \(g(t) \in \mathbb F\), we have: \[ g(t,x_2,...,x_n) = (1 - t) \cdot g(0,x_2,...,x_n) + t \cdot g(1,x_2,...,x_n) \]

The right-hand side needs only the two "slices" where \(x_1\) is fixed to 0 or 1, repeat for the next variable and we will shrink \(2^n \to 2^{n-1} \to ... \to 1\) - the desired evaluations of gate values in the circuit.

Because \(g\) is degree-1 in every coordinate, we can evaluate it by a sequence of 1-dimensional linear interpolations:

dimension   n:   size 2^n     -- fold along x1 -->
dimension n-1:   size 2^{n-1} -- fold along x2 -->
...
dimension   1:   size 2       -- fold along xn -->
dimension   0:   size 1       (the answer)

Cost: one addition and one multiplication per value per fold \(\to n \cdot 2^n\) operations, only combine all existing values of gates array.

Folding is just repeated affine interpolation, turning the vector \(v\) into a single weighted sum, for \(n = 3 \), let:

Step 1 (fold \(x_1\)) size 4:

Step 2 (fold \(x_2\)) size 2:

Step 3 (fold \(x_3\)) size 1: