There’s this thing called a Kate polynomial commitment, which is a polynomial commitment primitive that makes use of pairings. There’s an excellent post from Dankrad which I would recommend reading instead of this post. I wrote this as a shorter summary of how you can commit to a polynomial, and then prove any evaluation $f(x)=y$.

Here’s how it works:

You have a polynomial $f(x)=x^2+3x$

and some public parameters:

where $[x]:=xG$ for some generator $G$ of an elliptic curve group.

and $s$ is a toxic waste (something that no one should know) hidden behind an elliptic curve point G (some people call that “hidden in the exponent”).

to commit to $f$

To commit to this polynomial, evaluate it at the unknown point $s$. You can do that by playing with the $SRS$:

to prove that $f(\zeta )=a$

One day, the verifier asks “what’s the evaluation at $\zeta$?” And the prover responds by sending the answer, $a$, and a proof ($h(s)$, see below).

The idea behind the proof

Notice that because $\zeta$ is a root of $f(x)-f(\zeta )$, then for some polynomial $h(x)$:

Due to this, $h(x)=\frac{f(x)-f(\zeta )}{x-\zeta }$ must be a valid polynomial.

At a high-level:

• the verifier will compute what they think $[h(x)]$ should be at some random point $s$
• the prover will send the actual value $[h(s)]$
• the verifier will check if they match

This works because the Schartz-Zippel lemma tells us that two polynomials that are different are different in most points.

The proof

Here’s the protocol:

1. the prover sends the verifier a commitment $[\frac{f(s)-f(\zeta )}{s-\zeta }]=[h(s)]$ evaluated at some random point $s$ (the toxic waste).
2. the verifier constructs a similar $h(s)$ but with the expected value of $f(\zeta )$ instead: $[\frac{f(s)-a}{s-\zeta }]$. The verifier then checks if it’s equal to $[h(s)]$.

Note:

1. The prover can compute $[h(s)]$ easily, because they can just compute the polynomial $h(x)$ first, and then reconstruct it at $s$ with the $SRS$. $$h(x)=\frac{f(x)-f(\zeta )}{x-\zeta }=a_0+a_{1}x+a_2{x}^2+\cdots$$ and then $$[h(s)]:=a_0[1]+a_1[s]+a_2[s^2]+\cdots$$

   for example with our previous $f(x)$ and $\zeta =3$

   

2. The verifier cannot compute their own $[h(s)]$ because they cannot divide by $s$ (remember, nobody knows $s$). They need a pairing. Remember, you want to check the following identity hidden in the exponent (using commitments): $$\frac{[f(s)-a]}{[s-\zeta ]}=[h(s)]$$ But since you can’t divide with commitments, you can’t compute what’s on the left-hand side. You can multiply thanks to pairings though. So instead, you could check the following equation: $$[f(s)-a]=[(s-\zeta )h(s)]$$ and with pairings, you can multiply $[s-\zeta ]$ with the proof $[h(s)]$: $$e([f(s)]-[a],[1])=e([s-\zeta ],[h(s)])$$

PS: Thanks to h for pointing out a mistake