The sumcheck protocol was a landmark development in the early 1990s. The protocol led to Shamir’s proof that the space of interactive protocols was the same as PSPACE (the set of problems that can be solved using a polynomial amount of space). The sumcheck protocol has been used in subroutine for a variety of protocols such as GKR [Delegating computation: Interactive proofs for muggles]. More recently, Scroll’s zkVM, Ceno, uses GKR (and thus sumcheck).
Sumcheck is an excellent protocol to learn, and understand.
The sumcheck protocol addresses the following question: can a Prover convince a \log-time Verifier that ~~~~~~~~~~~~\displaystyle\sum_{h_1,\dots,h_{v} \in H} f(h_1,\dots,h_v)
\stackrel{?}{=} c
for a known v-variate polynomial f, set H and constant c.
We note that the Verifier cannot simply compute the sum as the sum consists of H^v terms. Instead, the Prover and Verifier will interact in v rounds.
Briefly, each of these rounds can be summarized with the following steps:
The Prover sends the Verifier an univariate polynomial g that is a partial sum over a subset of variables over H and evaluation of other variables at random values.
The Verifier sums g over the set H to verify that g matches with the previous step.
See the Sumcheck slides from the ZK Meeting call for more details and an example.
In practice, the set H = \{0,1\}. This is often used as statements concerning arrays can be extended to multilinear extensions that have inputs that are binary strings.
The sumcheck protocol has the following properties:
Completeness (the probability that an honest Prover convinces a verifier): 1.
Soundness (the probability that a malicious Prover can convince a verifier): vd/|\mathbb{F}|*
Communication complexity: O(v(d+1)) where d is the maximum variable degree of f.
Verifier complexity: O(v(d+1)|H|)*.
\vskip .15in
*: dependent on the polynomial commitment used.
The sumcheck protocol assumes the use of a random oracle for a single evaluation of the polynomial f at a random point. Concretely, this can be done with polynomial commitments.
Visit the IFT ZK Meeting notes for additional resources on the Sumcheck protocol.
Hi. There’s two zero knowledge variants of the sumcheck protocol (that I am aware of…). The first version from 2016 was expanded upon by Chiesa, Forbes and Spooner in the “second version”. Since the second version is a modification of the first, I’ll answer in terms of this paper.
Sumcheck requires the following parameters:
degree d (public)
number of variables m (public)
subset H of our field (public)
polynomial f
value v that f sums to over H. (public)
Only the polynomial f is kept secret in the zero-knowledge variants of the sumcheck protocol. Additionally, all of the partial sums of the polynomial f are kept secret as well.
This is achieved by using a masking polynomial r (of low degree) and a random value \rho. Briefly, the zero-knowledge variant of sumcheck uses the regular sumcheck on the new polynomial g(X) = \rho f(X) + r(X). Even if the verifier is allowed to make many queries to the polynomial r, only a single evaluation of f is leaked.
If you were thinking of a different zero-knowledge variant of sumcheck, please let me know.
There’s also Libra.
This one has better complexity because they use a small polynomial as the masking polynomial r. Chiesa et al. uses a masking polynomial r, which is as big as f.
I have seen (zero-knowledge) sumcheck being applied in some applications but they tend to not focus on explaining how the (zero-knowledge) sumcheck works like.
If we have something of the following:
0 = ∑ f(x) * c + d * (1-2^x)
The polynomial f and some arithmetic operations performed on f and constants c,d which are publicly known. Is it possible to prove this to a verifier without revealing f(x), and proving that you have multiplied f with the publicly known known values (c + d * (1-2^x))?
I am not sure how one would prove the (2^x) though.
It is quite common for ‘zero-knowledge’ to be handwaved away with sumcheck. Which is quite annoying.
The expression 2^x is problematic as you point out. Over a finite field, 2^x can be interpolate as a polynomial (of unfortunate size |\mathbb{F}|). I suspect that $2^xs polynomial form’s degree would be problematic for multiple reasons:
Libra uses GKR which assumes the Prover is restricted to polynomial time, so there might be some subtle issues applying directly.
Chiesa’s version, 2^x would have too large of a degree.
Though, the real question is, what would the term d\cdot (1-2^x) contribute? This is a masking polynomial to conceal f. However, it’s polynomial form has a large degree which would make it a poor choice compared to Libra’s approach.
Is there a particular application you’re thinking of that would require 2^x?
Sorry maybe I confused you, I am relatively new to this so I might lack correct notations I wasn’t referring to the term c + d * (1-2^x) as the masking polynomial r. My question was more on how do you apply the (zero knowledge) version of the sumcheck on 0 = ∑ f(x) * c + d * (1-2^x) as a whole.
E.g in a scenario where the verifier gives you c and d and a prover needs to prove that he indeed used c and d in the computed sum (if thats even possible).
e.g search for Sumcheck for binary operation in this zkPoT. Equation 3 and 4 has something very similar. The equations have a fixed structure. And as far as I understood the verifier needs to know this structure to accept the proof, but I am not sure how this happens?
Confusing me is not a problem. As long as I eventually understand the question.
To clarify, the sumcheck protocol is for v-variate polynomials. There is an univariate version of sumcheck in Aurora; this relies on FRI and has a zero-knowledge variant. So, in general care should be applied when referring to the polynomials f(x) and 1-2^x.
At the risk of being overly detailed:
f({\mathbf{x}}) is a v-variate polynomial; v > 1.
g(x_0) = 1-2^{x_0}; we can relabel variables to ensure x_0 is the power on 2.
Now, you’re looking at applying the sumcheck protocol to “polynomial” c \cdot f(\mathbf{x}) + d \cdot g(x_0) where c,d are random values selected from the verifier. Now, \sum [c \cdot f(\mathbf{x}) + \cdot g(x_0)] = 0 for randomly selected c,d would imply that \sum f(\mathbf{x}) = 0 = \sum g(x_0) (with high probability-this is an application of Schwartz-Zippel Lemma).
So, I think the real objective is:
The Prover has a secret v-variate polynomial f(\mathbf{x}) that she commits to.
We can assume(?) that a commitment to g(x_0) exists as well.
Verifier selects c,d and shares with the Prover.
The Prover computes v = \sum c \cdot f(\mathbf{x}) + d \cdot g(x_0).
Prover proves this equality with sumcheck.
Now, in terms of zkPoT. Equation 3 and 4 appear to be obtained from computing the multi-linear extension of a matrix. In Equation 4, the 2^y is a constant value rather than varied which is a good thing since that avoids the polynomial degree problem mentioned earlier.
Roughly, speaking. There’s a vector z. Each component of z has a binary representation in the matrix Z and bit sign z_{sgn} that are claimed to be binary. To prove that they are binary.
A challenge \alpha is applied to ensure that the z_{sgn}(1-z_{sgn}) and Z(1-Z) terms do not cleverly cancel out.
r_y and r_x are used in \beta function (defined in the definition of MLE in the paper).
Equation 3 demonstrates that Z and z_{sgn} are binary.
Equation 4 is used to show that Z and z_{sgn} correlate to the vector z in the claimed manner. This is the very rough idea.
In general, the Verifier has to be informed (and knowledgeable) of the validity of the protocol used. So, if two parties agree to perform zkPoT, then the Verifier would be aware of the steps that they need to follow. Though, in reality, the verifier’s challenges would be replaced by hash evaluations (Fiat-Shamir heuristics). This allows any verifier to use the proof to validate the prover’s claim.
Thank you so much for sharing Aurora with me!! I wasn’t aware of it That makes so much sense.
So, regarding the zkPoT, the verifier is already aware on what the sumcheck is being applied on. And in a zero-knowledge variant, I assume it’s still the same, the verifier won’t know the input values (here the binary values), but still knows the structure.
If we say, parties run a zero-knowledge variant sumcheck on:
H = \sum \left( 2 \cdot f(x) \right), \quad \text{where } f(x) \text{ stays hidden, and } 2 \cdot f(x) \text{ structure is agreed upon}
Absolutely, the Verifier will know the structure of the proof but none of the private inputs. In the case of the non-interactive versions, the values c and d would be known (just to be clear).
But yes, for your example with 2\cdot f(x), the zero-knowledge variant of sumcheck would keep f(x) hidden.
With oracle access to \widetilde{f} and \widetilde{g}.
At a final challenge r_l, the verifier receives a claim h_P(r_l), then he requests \widetilde{f}(r_1..r_l) and \widetilde{g}(r_1..r_l) and is able to construct the h_V(r_l) (by following the polynomial structure the sumcheck was applied on, so using the public values e.g \widetilde{\beta}_x(r_x) \cdot \widetilde{\beta}_y(r_y)) and outputs h_P(r_l) == h_V(r_l)
Yes, \mathsf{Z}_{Bit} and \mathsf{z}_{sign} are completely hidden and committed to in the polynomials f(x,y) and g(x).
At the end of the sumcheck protocol for equation (1), h_P(r_l) = \tilde{f}(r_1, \dots, r_l). Similarly, \tilde{g}(r_1,\dots, r_l) = h'_P(r_l) where h'_P is the polynomial from the last round of the sumcheck protocol.
Asking for openings of the hidden committed polynomials \tilde{f}(r_1, \dots, r_\ell),\quad \tilde{g}(r_1, \dots, r_\ell)
Plugging them into the known structure of the full expression (with constants, etc.)
Recomputing \text{poly}(r_1, \dots, r_\ell)
and verifying that h_P(r_\ell) = \text{poly}(r_1, \dots, r_\ell)
So, h_P(r_\ell) = \text{f}(r_1, \dots, r_\ell) doesn’t exactly fit here, but I think you referred it this way because I didn’t write what exactly h_P(r_\ell) stands for. Sorry again
This would work provided that the Verifier knows the known structure of \mathsf{poly}. It is necessary that the constants that are used to combine \mathsf{poly} are not selected by the Prover if you intend to prove something about f and g individually rather than the combination of f and g.
