Using the following example to go through GKR protocol
this blogs follows the example in Spartan 预备知识：GKR with ZK Argument
zero knowledge version of GKR, Hyrax approach.
GKR Part 2 -example
…
Category: Fundamental Protocols
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 …
Sum-check Protocol
Multi-linear extension
Following the definition from Justin Thaler
Let \(\mathbb{F}\) be any finite field, and let \( f : \{0,1\}^v \rightarrow \mathbb{F} \) be any function mapping the \( v \)-dimensional Boolean hypercube to \(\mathbb{F}\). A \( v \)-variate polynomial \( g \) over \(\mathbb{F}\) is said to be an …