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.