A Toy Example for Multivariate Polynomials (with three variables)
Let π(π1,π2, π3) = 2π1 3 + π1π3 + π2π3. The sum of πβs evaluations over the Boolean hypercube is β = 12.
When the Sumcheck protocol is applied to π, the honest proverβs first message in the protocol is the univariate polynomial π 1(π1) equal to: \
The verifier checks that π 1(0) + π 1(1) = 12, and then sends the prover π1. Suppose that π1 = 2.
The honest prover would then respond with the univariate polynomial π 2(π2) = π(2, π2, 0) + π(2, π2, 1) = 16 + (16 + 2 + π2) = 34 + π2.
The verifier checks that π 2(0) + π 2(1) = π 1(π1), which amounts in this example to confirming that 34 + (34 + 1) = 8 (2 3 ) + 4 + 1; indeed, both the left hand side and right hand side equal 69. The verifier then sends the prover π2. Suppose that π2 = 3.
The honest prover would respond with the univariate polynomial π 3 (π3 ) = π(2,3,π3 ) = 16 + 2π3 + 3π3 = 16 + 5π3, and the verifier confirms that π 3(0) + π 3(1) = π 2(π2), which amounts in this example to confirming that 16 + 21 = 37.
The verifier picks a random field element π3. Suppose that π3 = 6. The verifier confirms that π 3(6) = π(2,3,6) by making one oracle query to π (i.e., both sides are equal to 46).
Last updated
