Database of Theorems, Lemmas and Proofs
====

# 1. Univariate sumcheck theorem

The univariate sumcheck theorem for multiplicative subgroups (question arose during cq reading group)

This is to prove that for a multiplicative subgroup $G$ of size $n$, any polynomial $f(X)$ of degree $< n$ satisfies that $sum(f(x)) = n · f(0) = s$ for all $x \in G$. This is equivalent to saying that there exist quotient and remainder polynomials such that $f(X) = q(X)*Z(X) + X · r(X) + s/n.$

Let’s understand why this holds.

**First** ($\Rightarrow$): We can express any polynomial without loss of generality as $f(X) = q(X) · Z(X) + X · r(X) + c$ , where $Z$ is the vanishing polynomial over $G$. Remember we are performing the sum of f(X) over all x in G. Then, all Z(x) by definition will vanish to zero. Then the claim reduces to checking that s = sum(x·r(x)) + n · c for x in G. Then, define r'(X) = X · r(X) , this is a polynomial of degree < n and any sum over all x in G of such polynomials are 0 iff they evaluate to zero in 0. This means that sum(r'(x)) = 0 because 0 · r(0) = 0 and then s = n · c which implies that c = s / n. (edited)

**Second** ($\Leftarrow$): If p(X) can be expressed as q(X) Z(X) + Xr(X) + s/n then the sum of p(x) is sum[ q(x) Z(x) + xr(x) ] + n · s / n and then sum(p(x)) = s.

# 2. ZK-property proof for chunked polynomials

The proof (sketch):

Suppose we have some polynomial f formed of k chunks of size n. We write

f(x) = a_0 x^0 + a_1 x^1 + ... + a_{k*n-1} x^(k*n-1)

and for each chunk we define `f_i` representing that chunk

f_i(x) = a_{n*i+0} x^{n*i+0} + ... + a_{n*i+n-1} x^{n*i+n-1}

We call `eval_i = f(ω^i), eval_i_ζ = f_i(ζ), and eval_i_ζω = f_i(ζω)`, as well as defining ZK_ROWS as some constant, where the last `ZK_ROWS` rows of the polynomial are randomised (that is, `eval_i` is random for `kn-ZK_ROWS <= i < kn`.

A verifier who believes they may know the kn-ZK_ROWS witness values and the 2k evaluations can form the system of simultaneous equations

eval_i = a_0 ω^0 + a_1 ω^i + ... + a_{kn-1} ω^(kn-1), 0 <= i < kn-ZK_ROWS
eval_i_ζ = a_{i*n+0) ζ^0 + a_{i*n+1) ζ^1 + ... + a_{i*n+n-1} * ζ^{i*n+n-1), 0 <= i < k
eval_i_ζω = a_{i*n+0) (ζω)^0 + a_{i*n+1) (ζω)^1 + ... + a_{i*n+n-1} * (ζω)^{i*n+n-1), 0 <= i < k

i.e. they have a system of kn-ZK_ROWS + k + k = k*(n+2)-ZK_ROWS equations.
Note that any collection of up to kn of these equations is linearly independent. Thus, if k*(n+2)-ZK_ROWS >= kn then you can select kn rows and form an invertible matrix, allowing you to infer the coefficients of a unique polynomial corresponding to the given set of evaluations.
Rearranging the inequality, this gives us ZK_ROWS <= k*(n+2) - kn = 2*k. Thus, we can set ZK_ROWS = 2*k + 1 to violate this inequality, ensuring that there is at least 1 degree of freedom in the interpolation (that is, we have kn variables but the verifier can only form kn-1 equations). Since all of our padding values are chosen uniformly at random, the probability that a malicious verifier guesses any of them correctly is ~1/2^254, i.e. negligible, and likewise if they attempt to guess the evaluation at any other arbitrary point.
Hence, randomising the final 2k+1 rows for a column using k chunks is sufficient to achieve zero-knowledge.
Note: given the description above, it might appear that 2k randomised rows would be sufficient for zero-knowledge, since the verifier has 'used' all of their evaluations to generate the polynomial, and has no way to check them. However, if the verifier is able to correctly infer the polynomials for all of the columns in the proof, they will then be able to compute the combined polynomial and thus ft_eval1, giving them a final check to see whether their 'guesses' were correct, and thus violating zero knowledge. Thus, we use 2k+1 to ensure that the probability of inferring the underlying polynomial for any column is negligible.

**Fixes:**

eval_j_ζ = a_{j*n+0) ζ^0 + a_{j*n+1) ζ^1 + ... + a_{j*n+n-1} * ζ^{j*n+n-1), 0 <= j < k \\
eval_j_ζω = a_{j*n+0) (ζω)^0 + a_{j*n+1) (ζω)^1 + ... + a_{j*n+n-1} * (ζω)^{j*n+n-1), 0 <= j < k \\
eval_i = a_0 ω_i^0 + a_1 ω_i^1 + ... + a_{kn-1} ω_i^(kn-1), 0 <= i < kn-ZK_ROWS