Properties of KZG:
- Trusted setup
- Pairings
- constant sized Polynomial
Trusted Setup
To commit to degree \leq l polynomials, we need to construct Structured Reference Strings: (g, g^\tau, g^{\tau^2} , …, g^{\tau^l})=(g^{\tau^i})_{i\in [0,l]}
Note 1: The trapdoor \tau is generated by distributed protocols, for instance, ….
Note 2: The SRSs are updatable …
Commitments
A polynomial f(x)=\sum\limits_{i\in [0, d]}f_ix^i with degree d is committed to one group element, i.e., in most of the project, it is a point in elliptic curve:
c=\prod\limits_{i\in[0,d]}(g^{f_i\tau^i})
Evaluation Proofs
To prove the polynomial f(x)=\sum\limits_{i\in [0, d]}f_ix^i evaluated at x=a is y, prover compute a quotient polynomial as
q(x)=\frac{f(x)-y}{x-a}
This leverages the polynomial remainder theorem. You may also find it helpful to understand it in one more way:
The polynomial f in Lagrange basis form as:
f(x)=\sum\limits_{i\in[0,d],x_i\neq a}y_i\prod\limits_{j\in [0,d]j\neq i }\frac{x-x_j}{x_i-x_j} + y\prod\limits_{j\in [0,d], x_j\neq a}\frac{x-x_j}{a-x_j}
Suppose points (x_0,y_0), …,(a,y),…,(x_d,y_d) are on f
Rewrite the above polynomial as
f(x)-y=(x-a)\sum\limits_{i\in [o,d],x_i\neq a }y_i\cdot \frac{1}{x_i-a}\prod\limits_{j\in [0,d],j\neq i,x_j\neq a }\frac{x-x_j}{x_i-x_j}
+y(\frac{\prod\limits_{j\in [0,d], x_j\neq a}(x-x_j)-\prod\limits_{j\in [0,d], x_j\neq a}(a-x_j)}{\prod\limits_{j\in [0,d], x_j\neq a}a-x_j})
let \phi(x)=\prod\limits_{j\in [0,d], x_j\neq a}(x-x_j)-\prod\limits_{j\in [0,d], x_j\neq a}(a-x_j)
\phi(a)=0 thus \phi(x)=(x-a)\cdot …
Verifying an Evaluation Proof
Verfier at this point will have:
- SRSs: (g, g^\tau, g^{\tau^2} , …, g^{\tau^l})=(g^{\tau^i})_{i\in [0,l]}
- commitment: c=g^{f(x)}
- evaluation point (a,y),
- the proof \pi=g^{q(x)}
accept if the following equations hold.
e(c/g^y,g)==e(\pi,g^\tau/a)
so in a proof, there will be
2 G1 points, c and \pi
Batch proofs
I will use the notation in Plonk paper to describe the batch proof of KZG.