We want to commit to some polynomial , and be able to provably evaluate the committed polynomial at arbitrary points. The naive solution would be for the prover to simply send the polynomial's coefficients to the verifier: however, this requires communication. Our polynomial commitment scheme gets the job done using communication.
Given a parameter we generate the common reference string defining certain constants for this scheme:
- is a group of prime order
- is a vector of random group elements;
- is a random group element; and
- is the finite field of order
The Pedersen vector commitment is defined as
for some polynomial and some blinding factor Here, each element of the vector is the coefficient for the th degree term of and is of maximal degree
The modified inner product argument is an argument of knowledge for the relation
where is composed of increasing powers of the evaluation point This allows a prover to demonstrate to a verifier that the polynomial contained “inside” the commitment evaluates to at and moreover, that the committed polynomial has maximum degree
The inner product argument proceeds in rounds. For our purposes, it is sufficient to know about its final outputs, while merely providing intuition about the intermediate rounds. (Refer to Section 3 in the Halo paper for a full explanation.)
Before beginning the argument, the verifier selects a random group element and sends it to the prover. We initialize the argument at round with the vectors and In each round :
- the prover computes two values and by taking some inner product of with and . Note that are in some sense "cross-terms": the lower half of is used with the higher half of and , and vice versa:
- the verifier issues a random challenge ;
- the prover uses to compress the lower and higher halves of , thus producing a new vector of half the original length The vectors and are similarly compressed to give and (using instead of ).
- , and are input to the next round
Note that at the end of the last round we are left with , , each of length 1. The intuition is that these final scalars, together with the challenges and "cross-terms" from each round, encode the compression in each round. Since the prover did not know the challenges in advance, they would have been unable to manipulate the round compressions. Thus, checking a constraint on these final terms should enforce that the compression had been performed correctly, and that the original satisfied the relation before undergoing compression.
Note that are simply rearrangements of the publicly known with the round challenges mixed in: this means the verifier can compute independently and verify that the prover had provided those same values.