Sum-check design philosophy, why it works?

Using an example of 3 variants multilinear polynomial to explain the design idea of sum-check protocol.

A 3 variants multilinear polynomial can be generally represented as

$$g(X,Y,Z)=a_0+a_xX+a_yY+a_zZ+a_{xy}XY+a_{xz}XZ+a_{yz}YZ+a_{xyz}XYZ$$

Understanding Sum-check in reverse order

In the final round of sumcheck protocol, assuming the verifier gets a one degree polynomial

$$h(z)=g(r_1,r_2,\ldots,z )=\alpha_n z + \beta_n$$

the verifier chooses the last randomness \(r_n\) and verifies:

$$h(r_n)==g(r_1,r_2,\ldots,r_n)$$

expand the equation, observe that:

$$h_3(r_3)=\alpha_3 z + \beta_3$$

$$g(r_1,r_2,r_3)=a_0+a_xr_1+a_yr_2+a_zr_3+a_{xy}r_1r_2+a_{xz}r_1r_3+a_{yz}r_2r_3+a_{xyz}r_1r_2r_3$$

$$=(a_z+a_{xz}r_1+a_{yz}r_2+a_{xyz}r_1r_2)r_3+a_0+a_xr_1+a_yr_2+a_{xy}r_1r_2$$

As \(r_3\) is chosen randomly, to keep the equation holds with no matter what value \(r_3\) is, the values of \(\alpha_n\) and \(\beta_n\) are determined. That is

$$\alpha=a_z+a_{xz}r_1+a_{yz}r_2+a_{xyz}r_1r_2$$

$$\beta=a_0+a_xr_1+a_yr_2+a_{xy}r_1r_2$$

Now let’s go one more round back, the verifier receive the polynomial in round 2, claim the evaluation of this polynomial in point \(r_2\) to be \(v_2\) and verifies

$$v_2=g(r_1,r_2,0)+g(r_1,r_2,1)$$

assuming the polynomial sent by the prover in round 2 is \(h_3(Y)=\alpha_2Y+\beta_2\)

expand the verification check, then observe

$$v_2=h_3(r_2)=g(r_1,r_2,0)+g(r_1,r_2,1)$$

$$2a_0+2a_xr_1+2a_yr_2+2a_{xy}r_1r_2+a_z+a_{xz}r_1+a_{yz}r_2+a_{xyz}r_1r_2=\alpha_2r_2+\beta_2$$

The above equation holds for random \(r_2\), therefore, \(\alpha_2\) and \(\beta_2\) are also determined

The proof can go backward until the first round.

What if the attacker knows the randomness beforehand?

one can notice what if an attack knows the random that a verifier is going to choose before hand, the soundness then will be broken, as the prover is able to manipulates the polynomial he send to the verifier.

Notes:

I also try to understand sum-check protocol in a forward way. for every round, a prover send a polynomial to the verifier, it essentially creates 2 constraints for the coefficients (from the coefficient of the one degree polynomial) of the polynomial defined over binary hypercubes. At the end all the constraints will uniquely define one polynomial.

Leave a Reply

Your email address will not be published. Required fields are marked *