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.

Figure 4.1 in Proofs, Arguments, and Zero-Knowledge

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).

gj provided by the Prover in each round. Fig 4.5 in Proofs, Arguments, and Zero-Knowledge

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:

thaler/sumcheck.rs at main · 0xSage/thaler

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.

g1, a univariate polynomial over X1

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 g
• r_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 table lookup_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 sum
• sumcheck_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