A Working Example for Multivariate Polynomials (with four variables)

Let's say we have an execution trace that is represented as a vector. To demonstrate how it works, we will use a vector of length 16 composed of the evaluations of a polynomial {𝑓𝑖 }𝑖=0,..,15 where 𝑓𝑖 is an element of a finite field 𝔽. We can interpolate these values using a multivariate polynomial 𝑓(𝑋4,𝑋3, 𝑋2,𝑋1).

𝑓0	𝐹(0,0,0,0)
𝑓1	𝐹(0,0,0,1)
𝑓2	𝐹(0,0,1,0)
𝑓3	𝐹(0,0,1,1)
𝑓4	𝐹(0,1,0,0)
𝑓5	𝐹(0,1,0,1)
𝑓6	𝐹(0,1,1,0)
𝑓7	𝐹(0,1,1,1)
𝑓8	𝐹(1,0,0,0)
𝑓9	𝐹(1,0,0,1)
𝑓10	𝐹(1,0,1,0)
𝑓11	𝐹(1,0,1,1)
𝑓12	𝐹(1,1,0,0)
𝑓13	𝐹(1,1,0,1)
𝑓14	𝐹(1,1,0,1)
𝑓15	𝐹(1,1,1,1)

We can think of the first column of the table as the finite field elements, and the second column as the interpolation process where we use the Lagrange interpolation to interpolate the values.

where the Lagrange base polynomials defined in a binary field are represented by 𝑋 and 1 − 𝑋. The Multi-Linear Extension of a vector is a special polynomial denoted as 𝐹(𝑋4𝑋₃, 𝑋₂, 𝑋₁), which is constructed using these polynomials. In this scenario, the Sumcheck problem is defined as follows:

where 𝐶 ∈ 𝔽 and the protocol advances through the subsequent stages. In every round, the prover generates and commits to a univariate polynomial (Linear), and then obtains a challenge from the verifier.

The calculation which is made at round 1 shows that the prover computes:

The verifier checks:

Let the verifier send the challenge 𝑏1 ∈ 𝔽. Then the polynomial at round 2 would be described as follows.

Let the verifier send the challenge 𝑏2 ∈ 𝔽. Then the polynomial at round 3 would be described as follows.

Let the verifier send the challenge 𝑏3 ∈ 𝔽. Then the polynomial at round 4 would be described as: