Rust Guide: Sum-Check protocol
This is an unofficial & unaudited Rust implementation of algorithms in Dr. Thaler’s Proofs, Arguments, & ZK book.
This week we learned about the sum-check protocol. In cases when we want a sum of a polynomial g
over an exponential size domain, in this case 2^v
(a boolean hypercube), sum-check provides an interactive proof for Provers to claim such sums.
Rather than manually recomputing this sum, the Verifier can just check the Prover’s claim in O(v + cost-to-compute-g-only-once)
time with only a minor increase in overall Prover runtime.
The way I visualize this proof, is that in each round j
, the Prover sort of affixes one more face of the boolean hypercube with a random r
given by the Verifier. He then evaluates the sum over the remaining faces of the hypercube, leaving one last edge open for the Verifier to evaluate. This takes the form of a univariate polynomial, which the Verifier can evaluate against the previous round gj−1(rj−1) = gj(0) + gj(1)
.
Sum-check turns out to be a hammer for a lot of interesting problems.
Walkthrough
Lets’ walk through this interactive proof and implement it a step at a time using Arkworks ark-poly crate to assist with polynomial representations.
To follow the notation in the following tutorial, please reference starting lemma 4.1 in Dr. Thaler’s book linked here.
The full implementation with tests & benchmarking can be found here:
Necessary caveat: I’m neither a mathematician nor a Rust expert. Suggestions for improvement are always welcome! 🥰
Round 1
The Prover first sends the Verifier a claimed sum-check value C1
. Let’s use the following function to represent the Verifier:
pub fn verify(g: &MultiPoly, c_1: ScalarField) -> bool {TODO}
Where the type aliases just mean:
- ScalarField:
ark_bls12_381::Fr
- Multipoly:
SparsePolynomial<ScalarField, SparseTerm>
Then, the Prover sends the first univariate polynomial g1(X1) claimed to equal C1.
To do this, we know that the Prover will have to keep some memory from now on, so let’s define a Prover struct with the following attributes, where:
g
is the original polynomial gr_vec
is a growing vector of random elements in a large field provided by the Verifier in each round:
To simulate the Prover calculating g1
, we implement a function gen_uni_polynomial.
It computes g over all permutations, all points over the hypercube as follows:
Note: n_to_vec
transforms a number to its binary representation in a vector format, e.g. 5 => [1,0,1].
Specifically, the function fixes Xj
, in this case x1, and evaluates over the remaining “unfixed” points of the boolean hypercube. For each point, we compute a univariate polynomial “unipoly
”. Finally, we sum up all evaluations into a single univariate polynomial.
Stepping one level deeper, it computes each polynomial as follows:
It evaluates gj
over a vector of points, folding all evaluated terms together into one univariate polynomial at the end.
Stepping one level deeper again, it computes each term as follows, returning a tuple of (new coefficent, fixed term)
:
In future rounds for example, given a term x_1²x_2x_3
. If round j= 2, then we leave x_2
unevaluated (as it will be the variable left to construct the univariate polynomial). x_1
has been previously fixed by the Verifier, so we replace it with r_1
. And we evaluate x_3
over the point
variable provided by the invoking function.
The verifier invokes the Prover and checks the following:
- C1 = gi(0) +gi(1)
- The degree of
gi
is at most the degree deg_1(g), which is done by constructing a one time look up tablelookup_degree
.
Intermediate Rounds
For each intermediate round, Verifier chooses a random element r, in our large ScalarField, and sends it to the Prover.
Verifier continues to checks that gj−1(rj−1) = gj(0)+gj(1) holds and that the degrees are still with range.
Final Round
In the final round, the Verifier chooses a final random element r
and evaluates the original polynomial g with the r vector
given to the Prover in throughout the proof.
Benchmarking
In benchmarking, we isolate the Verifier steps and obtain the following results:
Where:
slow_sumcheck_test
tests a Verifier which recomputes the sumsumcheck_test
is our implementation above
Notice the Verifier is linear time. Yay
Acknowledgements
- Dr. Thaler’s book
- @GUJustin @cryptograthor @zeroknowledgefm for the group
- Join the group