Pairingbased polynomial commitments and Kate polynomial commitments posted June 2021
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:
$$ SRS = {[1], [s], [s^2], [s^3]} = {G, sG, s^2 G, s^3 G} $$
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$:
$$ [f(s)] := [s^2] + 3 [s] = s^2 G + 3 sG = (s^2 + 3s)G $$
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)$:
$$ f(x)  f(\zeta) = (x\zeta) \cdot h(x) $$
Due to this, $h(x) = \frac{f(x)f(\zeta)}{x\zeta}$ must be a valid polynomial.
At a highlevel:
 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 SchartzZippel lemma tells us that two polynomials that are different are different in most points.
The proof
Here's the protocol:
 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).
 the verifier constructs a similar $h(s)$ but with the expected value of $f(\zeta)$ instead: $[\frac{f(s)  a}{s\zeta}]$. The prover then checks if it's equal to $[h(s)]$.
Note:

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_1x + a_2x^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$
 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 lefthand 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)]) $$
Comments
leave a comment...