KZG Commitment Scheme

One of the most widely used polynomial commitment schemes is the KZG commitment scheme. The scheme was originally published in 2010 by Kate, Zaverucha, and Goldberg.

KZG is used in Ethereum’s Proto-Danksharding, and is also used in Scroll’s proof system.

This article will give an overview of the KZG commitment scheme.

Preliminaries and notation

Recall the premise of polynomial commitment schemes. We have some polynomial P(x)P(x) that we would like to commit to. We’ll assume the polynomial has a degree less than ll.

KZG commitments rely on elliptic curve pairings. Let G1\mathbb{G}_1 and G2\mathbb{G}_2 be two elliptic curve groups of order pp, with a non-trivial bilinear mapping e:G1×G2GTe: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T. Let gg be a generator of G1\mathbb{G}_1, and hh a generator of G2\mathbb{G}_2. We will use the notation [x]1:=xg[x]_1 := x \cdot g and [x]2:=xh[x]_2 := x \cdot h, where xFpx \in \mathbb{F}_p.

1. Trusted setup

Before computing any KZG commitments, a one-time trusted setup must be performed. Once the trusted setup is completed, it can be reused to commit and reveal as many different polynomials as desired. The trusted setup works as follows:

  • Pick some random field element τFp\tau \in \mathbb{F}_p
  • Let lZl \in \mathbb{Z} be the maximum degree of the polynomials we want to commit to
    • The trusted setup will only enable commitments to polynomials of degree l\leq l
  • Compute ([τ0]1,[τ1]1,[τ2]1,[τl]1)([\tau^0]_1,[\tau^1]_1,[\tau^{2}]_1\ldots,[\tau^{l}]_1) and ([τ]2)([\tau]_2), and release these values publicly.

Note that τ\tau should not be revealed - it is a secret parameter of the setup, and should be discarded after the trusted setup ceremony is completed so that nobody can figure out its value.

There are established methods of conducting trusted setup ceremonies with weak trust assumptions (1-out-of-N trust assumption) using multi-party computation (MPC). For more on how trusted setups work, see this post by Vitalik.

2. Committing to a polynomial

  • Given a polynomial P(x)=i=0lpixiP(x) = \sum_{i=0}^{l} p_i x^i
  • Compute and output the commitment c=[P(τ)]1c = [P(\tau)]_1
    • Although the committer cannot compute P(τ)P(\tau) directly (since he doesn’t know τ\tau), he can compute it using the output of the trusted setup:
      • [P(τ)]1=[i=0lpiτi]1=i=0lpi[τi]1[P(\tau)]_1 = [\sum_{i=0}^{l} p_i \tau^i]_1 = \sum_{i=0}^{l} p_i [\tau^i]_1

3. Prove an evaluation

  • Given an evaluation P(a)=bP(a) = b
  • Compute and output the proof π=[Q(τ)]1\pi = [Q(\tau)]_1
    • Where Q(x):=P(x)bxaQ(x) := \frac{P(x)-b}{x-a}
      • This is called the “quotient polynomial.”Note that such a Q(x)Q(x) exists if and only if P(a)=bP(a) = b. The existence of this quotient polynomial therefore serves as a proof of the evaluation.

4. Verify an evaluation proof

  • Given a commitment c=[P(τ)]1c = [P(\tau)]_1, an evaluation P(a)=bP(a) = b, and a proof π=[Q(τ)]1\pi = [Q(\tau)]_1
  • Verify that e(π,[τa]2)=e(c[b]1,h)e(\pi, [\tau - a]_2) = e(c - [b]_1, h)
    • Some algebra shows that this is equivalent to checking that that the quotient polynomial is correctly formed at τ\tau: Q(τ)=P(τ)bτaQ(\tau) = \frac{P(\tau) -b}{\tau-a}
      e(π,[τa]2)=e(c[b]1,h)    e([Q(τ)]1,[τa]2)=e([P(τ)]1[b]1,h)    Q(τ)(τa)e(g,h)=(P(τ)b)e(g,h)    Q(τ)(τa)=P(τ)b\begin{align*} & e(\pi, [\tau - a]_2) = e(c - [b]_1, h) \\ \iff & e([Q(\tau)]_1, [\tau -a]_2) = e([P(\tau)]_1 - [b]_1, h) \\ \iff & Q(\tau) \cdot (\tau - a) \cdot e(g, h) = (P(\tau)-b) \cdot e(g,h) \\ \iff & Q(\tau) \cdot (\tau -a) = P(\tau) - b \end{align*}
    • The bilinear mapping ee enables us to check this property without knowing the secret setup parameter τ\tau
  • Once this verification is complete, we can conclude that (with overwhelmingly high probability) the quotient polynomial is correctly formed, and therefore that the evaluation is correct.

Learn more

What's Next

Stay up-to-date on the latest Scroll Developer news
Roadmap updates, virtual and live events, ecosystem opportunities and more
Thank you for subscribing!


Follow Us

© Version 1.0.0 Scroll Ltd 2023