KZG Commitment

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.

Leave a Reply

Your email address will not be published. Required fields are marked *