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.