$$$$

PLONK PCS

Polynomial Commitment Scheme (PCS) - allows a prover to commit to a polynomial

$f(X)$ such that a verifer can check claimed evaluations

$(z,f(z))$ o the polynomial using its commitment.

Batched-PCS (BPCS) - allows a prover to commit to multiple polynomials.

Why Does PLONK Need a PCS?

Constant-Sized - a PLONK witness

$\mathit{u}=(u_1,\dots ,u_n)$ can be encoded into a polynomial

$f(X)=u_1{X}^0+\cdots +u_n{X}^{n-1}$ for which a single-value commitment can be generated using a PCS.

Non-Revealing - a PCS allows the verifer to query (and verify) additional information about

$\mathit{u}$ without learning any

$u_i\in \mathit{u}$; other commitment schemes (e.g. Pedersen [vector] commitments and Merkle trees) require the prover to reveal some/all of their committed data.

Homomorphic - a PCS verifier can perform (limited) polynomial arithmetic without having access to the committed polynomial.

Batchable - PLONK requires a prover to commit to multiple polynomials where some/all are evaluated at different inputs which can be accomplished using a BPCS.

Polynomial Remainder Theorem

If

$f(X)$ is a polynomial containing the point

$(a,f(a))$ then the polynomial

$f(X)-f(a)$ has a root at

$a$.

If

$f(X)-f(a)$ has a root at

$a$, then its linear factorization contains the degree-1 polynomial

$(X-a)$.

$$\begin{gathered} \begin{array}{rl}f(X)-f(a)& =c\prod _i(X-r_i)\\ & =(X-a)h(X)\end{array} \\ (X-a)|f(X)-f(a) \end{gathered}$$

The PRT can be used to prove that a polynomial

$f(X)$ contains the point

$(a,f(a))$ by showing that

$(X-a)|f(X)-f(a)$ without remainder.

Encryption

Here, encryption of an integer

$a\in \mathbb{Z}$ means computing

$g^a=g\ast \cdots \ast g$ where

$g$ is a generator of a prime order multiplicative cyclic group

$\mathbb{G}=⟨g⟩=\{g^1,\dots ,g^p\}$ (which has a hard discrete log).

$$\begin{gathered} (\mathbb{G},\times )=⟨g⟩=\{g^1,\dots ,g^p\} \\ {g}^a\in \mathbb{G} \\ Pr[\mathcal{A}(g,g^a)=a]=\mathsf{\text{negl}} \end{gathered}$$

Homomorphic Encryption

Allows arithmetic to be performed on plaintext values without leaving encrypted space.

$$\begin{array}{|cccc|}\hline & \mathbf{\text{Have}}& \mathbf{\text{Want}}& \mathbf{\text{How}}\\ \text{Add.}& g^a,g^b& g^{a+b}& g^a{g}^b\\ \text{Sub.}& g^a,g^b& g^{a-b}& g^a/g^b,g^a(g^b{)}^{-1}\\ \text{SMul.}& g^a,c\in \mathbb{Z}& g^{[c]a}& (g^a{)}^c\\ \text{Poly. Eval.}& f(X)=a_0{X}^0+\cdots +a_d{X}^d,g^{s^0},\dots ,g^{s^d}& g^{f(s)}& \prod _{i\in [0,d]}(g^{s^i}{)}^{a_i}\\ \text{Mul.}& g^a,g^b& g^{ab}& e(g_1^a,g_2^b)=g_t^{ab}\\ \hline\end{array}$$

Homomorphic Polynomial Evaluation

If we have homomorphic addition and scalar mulitplication we can homomorphically evaluate a polynomial

$f(X)$ at a point

$s$, i.e.

$g^{f(s)}$, given encrypted powers of

$s$, i.e.

$g^{s^0},\dots ,g^{s^d}$.

$$\begin{array}{rl}f(X)& =a_0{X}^0+a_1{X}^1+a_2{X}^2\\ g^{f(s)}& =g^{a_0{s}^0+a_1{s}^1+a_2{s}^2}\\ & =\left(g^{a_0{s}^0}\right)\left(g^{a_1{s}^1}\right)\left(g^{a_2{s}^2}\right)\\ & ={\left(g^{s^0}\right)}^{a_0}{\left(g^{s^1}\right)}^{a_1}{\left(g^{s^2}\right)}^{a_2}\\ & =\prod _{i\in [0,d]}{\left(g^{s^i}\right)}^{a_i}& .\phantom{}\end{array}$$

Pairings

We cannot perform homomorphic multiplication using cyclic group encryption alone:

$$(g^a,g^b)\mapsto /g^{ab}$$ but, we can do so using pairings.

A pairing

$e$ is a 2:1 function between groups

$({\mathbb{G}}_1,{\mathbb{G}}_2)$ and

${\mathbb{G}}_t$ such that exponents in the inputs (i.e. encrypted integers) are multiplied in the output.

$$\begin{gathered} e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_t \\ e(g_1^a,g_2^b)=g_t^{ab} \end{gathered}$$

Here,

${\mathbb{G}}_1$,

${\mathbb{G}}_2$, and

${\mathbb{G}}_t$ are multiplicative, cyclic, and cryptographic groups of equal prime order

$p$.

$$({\mathbb{G}}_1,\times )=⟨g_1⟩({\mathbb{G}}_2,\times )=⟨g_2⟩({\mathbb{G}}_t,\times )=⟨g_t⟩$$

We can homomorphically evaluate a product of polynomials

$f(X)h(X)$ at an input

$s$ given encrypted powers of

$s$ in

${\mathbb{G}}_1$ and

${\mathbb{G}}_2$.

$$\begin{gathered} \begin{array}{rlll}f(X)& =a_0{X}^0+\cdots +a_d{X}^d,& \text{deg}(f)=d,& (g_1^{s^0}=g_1,\underset{―}{g_1^{s^1},\dots ,g_1^{s^d}})\\ h(X)& =X+b,& \text{deg}(h)=1,& (g_2^{s^0}=g_2,\underset{―}{g_2^{s^1}})\end{array} \\ f(s)h(s)=\text{???} \\ \begin{array}{rl}{g}_1^{f(s)}& =\prod _{i\in [0,d]}{\left(g_1^{s^i}\right)}^{a_i}\\ g_2^{h(s)}& =g_2^{s^1}{g}_2^b\end{array} \\ e(g_1^{f(s)},g_2^{h(s)})=g_t^{f(s)h(s)} \end{gathered}$$

ZKG10 PCS

KZG is parameterized by

$(\kappa ,{\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_t,d)$:

• $\kappa$ - the security parameter (in bits) which gives the minimum group size, i.e.
  $p\ge 2^{\kappa }$.
• ${\mathbb{G}}_1$,
  ${\mathbb{G}}_2$, and
  ${\mathbb{G}}_t$ - cryptographic groups of equal prime order
  $p$ for which a pairing function is defined
  $e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_t$.
• $d$ - the largest polynomial degree that a prover can commit to.
  
  $$\mathsf{\text{new}}(\kappa )\to ({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_t,d)$$

KZG requires homomorphically evaluating a degree-

$d$ polynomial in

${\mathbb{G}}_1$ and a degree-1 polynomial in

${\mathbb{G}}_2$ at a random input

$s$ (Schwartz-Zippel). Homomorphic polynomial evaluation requires knowledge of encrypted powers of the polynomial input, thus a trusted-setup is run to generate the random input

$s$, known to no party, and outputs encrypted powers of

$s$ in

${\mathbb{G}}_1$ and

${\mathbb{G}}_2$, i.e. the structured reference string (SRS).

$$\mathsf{\text{setup}}()\to \mathsf{\text{SRS}}=\{g_1^{s^0},\dots ,g_1^{s^d},g_2^{s^0},g_2^{s^1}\}$$

The prover commits to a polynomial

$f(X)=a_0{X}^0+\cdots +a_d{X}^d$ by homomorphically evaluating it at

$s$.

$$\mathsf{\text{commit}}(f)\to \mathsf{\text{Com}}(f)=g_1^{f(s)}=\prod _{i\in [0,d]}{\left(g_1^{s^i}\right)}^{a_i}$$

The verifier asks the prover to evaluate

$f(X)$ at a chosen input

$z\in \mathbb{F}$. The prover calculates

$f(z)$, uses polynomial division to create the PRT cofactor polynomial

$h(X)$ for

$(z,f(z))$, and homomorphically evaluates

$h(s)$.

$$\begin{gathered} \mathsf{\text{eval}}(z)\to (f(z),g_1^{h(s)}) \\ \begin{array}{rl}f(X)& -f(z)=(X-z)h(X)\\ \Rightarrow h(X)& =\frac{f(X)-f(z)}{(X-z)}=b_0{X}^0+\cdots +b_{d-1}{X}^{d-1}\end{array} \\ {g}_1^{h(s)}=\prod _{i\in [0,d-1]}{\left(g_1^{s^i}\right)}^{b_i} \end{gathered}$$

$g_1^{h(s)}$ can be thought of as a commitment to

$h(X)$ in the same way that

$g_1^{f(s)}$ was a commitment to

$f(X)$.

The verifier checks the claimed evaluation

$f(z)$ using the PRT equality evaluated at a random input

$s$ (Schwartz-Zippel). The verification equation is the PRT equality written homomorphically so that the verifier can evaluate the equality at

$s$ without knowing

$s$.

$$\begin{gathered} \mathsf{\text{verify}}(\mathbf{\cdot })\to \{0,1\} \\ \begin{array}{rl}e(\mathsf{\text{Com}}(f)/g_1^{f(z)},g_2)& \stackrel{?}{=}e(g_1^{h(s)},g_2^{s^1}/g_2^z)\\ \Rightarrow e(g_1^{f(s)-f(z)},g_2)& \stackrel{?}{=}e(g_1^{h(s)},g_2^{s-z})\\ \Rightarrow g_t^{f(s)-f(z)}& \stackrel{?}{=}{g}_t^{h(s)(s-z)}\end{array} \end{gathered}$$ Which is equivalent to checking the PRT equality at a random input

$s$ (Schwartz-Zippel).

$$f(s)-f(z)\stackrel{?}{=}h(s)(s-z)$$

Why does this work?

The prover claims that

$(z,f(z))$ lies on

$f(X)$; the PRT equality must hold on all inputs if the claim is true.

$$f(X)-f(z)=(X-z)h(X)$$ Schwartz-Zippel says that we can evaluate the equality at a single random input. The SRS contains a random integer

$s$, known to no party, which we use for the random input.

$$Pr[f(s)-f(z)=h(s)(s-z)\mid (z,f(z))\notin f(X)]\le \frac{d}{|\mathbb{F}|}$$ Note that this is the exponents in the KZG verification equation.

$$f(s)-f(z)=h(s)(s-z)\text{v.s.}{g}_t^{f(s)-f(z)}=g_t^{h(s)(s-z)}$$ Rewriting the Schwartz-Zippel-ed PRT equality using homomorphic polynomial evaluation (allows

$s$ to be unknown) and pairings (allows the verifier to homomorphically multiply evaluated polynomials, i.e.,

$h(s)(s-z)$) yields an equality which can be checked by a verifier without knowledge of

$s$.

$$\begin{array}{rl}h(s)(s-z)& ⇝e(g_1^{h(s)},g_2^{s^1}/g_2^z)=g_t^{h(s)(s-z)}\\ f(s)-f(z)=h(s)(s-z)& ⇝e(g_1^{h(s)-f(z)},g_2)=e(g_1^{h(s)},g_2^{s-z})\end{array}$$

Random Linear Combinations

A linear combination is a sum of binary products. The linear combination of two vectors

$\mathit{a}$ and

$\mathit{b}$ is their dot product.

$$\mathit{a}\mathbf{\cdot }\mathit{b}=a_1{b}_1+\cdots +a_n{b}_n$$

A random linear combination (RLC) of a vector

$\mathit{a}$ is its dot product with a vector of random values

$\mathit{\gamma }=({\gamma }_1,\dots ,{\gamma }_n)\leftarrow {\mathbb{F}}^n$.

$$\mathit{a}\mathbf{\cdot }\mathit{\gamma }=a_1{\gamma }_1+\cdots +a_n{\gamma }_n$$

The modular powers of an integer form a psuedorandom sequence, thus for a random

$\gamma$ we consider

$\mathit{\gamma }=({\gamma }^1,\dots ,{\gamma }^d)$ to be random.

Schwartz-Zippel tells us that for a random

$\gamma$, the RLC of a vector

$\mathit{a}$ with powers of

$\gamma$ is (w.h.p.) unique.

$$\begin{gathered} f(X)=a_0{X}^0+\cdots +a_d{X}^d \\ g(X)=b_0{X}^0+\cdots +b_d{X}^d \\ \mathit{a}\ne \mathit{b} \\ \gamma \leftarrow \mathbb{F} \\ Pr[\mathit{a}\mathbf{\cdot }\mathit{\gamma }=\mathit{b}\mathbf{\cdot }\mathit{\gamma }]\le \frac{d}{|\mathbb{F}|} \end{gathered}$$

Combining Polynomials via RLC's

Multiple polynomials

$f_1(X),\dots ,f_t(X)$ can be compressed into a single polynomial

$F(X)$ by taking their random linear combination with randomness

$\gamma$.

$$\begin{gathered} \gamma \leftarrow \mathbb{F} \\ F(X)=f_1(X){\gamma }^0+\cdots +f_t(X){\gamma }^{t-1} \end{gathered}$$ We can compress multiple Schwartz-Zippel evaluations

$f_1(\beta ),\dots ,f_t(\beta )$ at a random input

$\beta$ into a single value

$F(\beta )$ using an RLC with randomness

$\gamma$ which is (w.h.p.) unique.

$$\begin{gathered} \beta \leftarrow \mathbb{F} \\ F(\beta )=f_1(\beta ){\gamma }^0+\cdots +f_t(\beta ){\gamma }^{t-1} \\ G(\beta )=g_1(\beta ){\gamma }^0+\cdots +g_t(\beta ){\gamma }^{t-1} \\ F(\beta )=G(\beta )\stackrel{\text{w.h.p.}}{⟹}F(X)=G(X),\text{i.e. }\mathrm{\forall }{f}_i(X)=g_i(X) \end{gathered}$$

Combining Polynomial Equalities via RLC's

Multiple polynomial equalites

$f_i(X)=g_i(X)$ can be compressed into a single polynomial equality by taking a RLC of the left-hand sides and a RLC of the right-hand sides using randomness

$\gamma$ and equating the two.

$$\begin{gathered} f_1(X)=g_1(X) \\ ⋮ \\ {f}_t(X)=g_t(X) \\ \gamma \leftarrow \mathbb{F} \\ F(X)=f_1(X){\gamma }^0+\cdots +f_t(X){\gamma }^{t-1} \\ G(X)=g_1(X){\gamma }^0+\cdots +g_t(X){\gamma }^{t-1} \\ F(X)=G(X) \\ \beta \leftarrow \mathbb{F} \\ F(\beta )=G(\beta )\stackrel{\text{w.h.p.}}{⟹}F(X)=G(X),\text{i.e. }\mathrm{\forall }{f}_i(X)=g_i(X) \end{gathered}$$

Batched-KZG Using RLC's

We can combine multiple polynomial equalities into a single equality using an RLC with randomness

$\gamma$, thus we can write a batched-PRT equality for proving multiple polynomial evaluations

$f_1(z)$ and

$f_2(z)$ at the same input

$z$.

$$\begin{gathered} f_1(X),f_2(X) \\ {f}_1(X)-f_1(z)=h_1(X)(X-z) \\ {f}_2(X)-f_2(z)=h_2(X)(X-z) \\ \gamma \leftarrow \mathbb{F} \\ \begin{array}{rl}(f_1(X)-f_1(z)){\gamma }^0+(f_2(X)-f_2(z)){\gamma }^1& =h_1(X)(X-z){\gamma }^0+h_2(X)(X-z){\gamma }^1\\ & =(h_1(X){\gamma }^0+h_2(X){\gamma }^1)(X-z)\end{array} \end{gathered}$$

Batched-KZG evaluates the batched-PRT equality at a random input

$s$ (Schwartz-Zippel) generated during a trusted-setup. Batched-ZKG allows us to commit to multiple polynomials and verify an evaluation for each using a single equality.

$$e(g_1^{f_1(s){\gamma }^0-f_1(z){\gamma }^0+f_2(s){\gamma }^1-f_1(z){\gamma }^1},g_2)=e(g_1^{h_1(s){\gamma }^0+h_2(s){\gamma }^1},g_2^{s-z})$$

Multivariate Schwartz-Zippel

Multivariate Schwartz-Zippel:

$$\begin{gathered} f(X_1,\dots ,X_n)\ne g(X_1,\dots ,X_n) \\ \mathit{\gamma }=({\gamma }_1,\dots ,{\gamma }_n)\leftarrow {\mathbb{F}}^n \\ Pr[f(\mathit{\gamma })=g(\mathit{\gamma })]\le \frac{d}{|\mathbb{F}|} \end{gathered}$$ tells us that a RLC of polynomials is (w.h.p.) unique.

TLDR: an

$n$-variate polynomial is a LC of

$(n-1)$-variate polynomials. A univariate polynomial evaluated at a random input is (w.h.p.) unique, thus a bivariate polynomial having a partially applied random input

$X=\beta$ results in a univariate polynomial which (w.h.p.) has unique coefficients. Partially applying a second random input

$Y=\gamma$ yields the standard univariate Schwart-Zippel probability. A RLC of

$n$-variate polynomials is equivalent to an

$(n+1)$-variate polynomial evaluated at a random input for the introduced indeterminate.

A degree-

$d$ bivariate polynomial

$g(X,Y)$ is a linear combination of powers of

$Y$ with univariate polynomials

$(f_0(X),\dots ,f_d(X))$.

$$\begin{gathered} g(X,Y)=f_0(X)Y^0+\cdots +f_d(X)Y^d \\ \text{deg}(f_i)=d-i \end{gathered}$$

Schwartz-Zippel says us that a univariate polynomial evaluated at a random input

$\beta \leftarrow \mathbb{F}$ is (w.h.p.) unique.

$$f_1(\beta )\ne f_2(\beta )$$ Thus, partially applying

$X=\beta$ to a bivariate polynomial

$g(X,Y)$ results in a unique coefficient vector

$(f_0(\beta ),\dots ,f_d(\beta ))$.

$$g(\beta ,Y)=f_0(\beta )Y^0+\cdots +f_d(\beta )Y^d$$ The probability that the coefficient vectors of two different bivariate polynomials

$g_1(X,Y)\ne g_2(X,Y)$ are equal after partially applying the random input

$X=\beta$ is zero.

$$\begin{array}{rl}{g}_1(X,Y)& =f_0(X)Y^0+\cdots +f_d(X)Y^d\\ g_2(X,Y)& =h_0(X)Y^0+\cdots +h_d(X)Y^d\\ Pr[g_1(\beta ,Y)=g_2(\beta ,Y)]& =Pr[f_0(\beta )=h_0(\beta )]\dots Pr[f_d(\beta )=h_d(\beta )]\\ & =\frac{d}{|\mathbb{F}|}\dots \frac{0}{|\mathbb{F}|}\\ & =0\end{array}$$ Thus, partial application of

$X=\beta$ yields a unique univariate polynomial, which Schwartz-Zippel tells us evaluates uniquely on random input

$Y=\gamma \leftarrow \mathbb{F}$.

$$\begin{gathered} g_1(X,Y)\ne g_2(X,Y) \\ \beta \leftarrow \mathbb{F} \\ {g}_1(\beta ,Y)\ne g_2(\beta ,Y) \\ \gamma \leftarrow \mathbb{F} \\ Pr[g_1(\beta ,\gamma )=g_2(\beta ,\gamma )]=\frac{d}{|F|} \end{gathered}$$

[Somewhat surprisingly] the bivariate and univariate Schwartz-Zippel probabilities are equal, which by induction can be generalized into the multivariate Schwartz-Zippel expression.

$$\begin{gathered} f(X_1,\dots ,X_n)=g_0(X_1,\dots ,X_{n-1})X_n^0+\cdots +g_d(X_1,\dots ,X_{n-1})X_n^d \\ ({\gamma }_1,\dots ,{\gamma }_n)\leftarrow {\mathbb{F}}^n \\ Pr[f_1({\gamma }_1,\dots ,{\gamma }_n)=f_2({\gamma }_1,\dots ,{\gamma }_n)]=\frac{d}{|F|}.\phantom{} \end{gathered}$$

Proof by Induction:

PLONK's BPCS

PLONK's BPCS is a batched-batched-ZKG which allows a prover to commit to mulitple polynomials where each may be evaluated at a distinct input. A prover has

$k$ sets of polynomials where each set is evaluated at the same input and each set's input is distinct. The prover runs batched-KZG for each set producing

$k$ batched-PRT equalities (one for each distinct input). The prover batches those batched-PRT equalities into a single equality which contains every polynomial's evaluation.

The BPCS is parameterized by

$(\kappa ,{\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_t,d,t)$ where

$t$ is the number of polynomials that the prover commits to; all other parameters are the same as those used in KZG10.

PLONK's BPCS uses the same trusted-setup and commitment procedures as KZG10 except that PLONK's BPCS makes

$t$ commitments, one for each polynomial

$f_i$.

$$\begin{gathered} \mathsf{\text{setup}}()\to \mathsf{\text{SRS}}=\{g_1^{s^0},\dots ,g_1^{s^d},g_2^{s^0},g_2^{s^1}\} \\ (f_1,\dots ,f_t) \\ \mathsf{\text{commit}}(f_i)\to \mathsf{\text{Com}}(f_i)=g_1^{f_i(s)} \\ (\mathsf{\text{Com}}(f_1),\dots ,\mathsf{\text{Com}}(f_t)) \end{gathered}$$

The verifier sends the prover each polynomial's evaluation input

$(z_1,\dots ,z_t)$ which may contain duplicated values. For each of the

$k\le t$ distinct inputs, the verifier samples a random value

$\gamma$ and sends it to the prover

$({\gamma }_1,\dots ,{\gamma }_k)\leftarrow {\mathbb{F}}^k$.

The prover partitions their polynomials according to like input, i.e. splits their polynomials

$(f_1,\dots ,f_t)$ into

$k$ subarrays where each subarray's polynomials are evaluated at the same input.

For each parition

$j\in [k]$, the prover performs a batched-PRT using randomness

${\gamma }_j$, i.e. homomorphically computes each

$h_i(s)$ then homomorphically computes the RLC

$H_j(s)$ of all

$h_i(s)$. Partition

$j\in [k]$ contains

$t_j$ polynomials denoted

$(f_{\mu },\dots ,f_{\nu })$.

$$\begin{gathered} \begin{array}{rll}\mathrm{\forall }i\in [t]:& h_i(X)& =\frac{f_i(X)-f(z_j)}{(X-z_j)}=b_0{X}^0+\cdots +b_{d-1}{X}^{d-1}\\ \mathrm{\forall }i\in [t]:& g_1^{h_i(s)}& =\prod _{i\in [0,d-1]}{\left(g_1^{s^i}\right)}^{b_i}\\ \mathrm{\forall }j\in [k]:& g_1^{H_j(s)}& =g_1^{h_{\mu }(s){\gamma }_j^0+\cdots +h_{\nu }(s){\gamma }_j^{t_j-1}}=\prod _{i\in [t_j]}{\left(g_1^{h_i(s)}\right)}^{{\gamma }_j^{i-1}}\end{array} \\ (f_1(z_1),\dots ,f_t(z_t),g_1^{H_1(s)},\dots ,g_1^{H_k(s)}) \end{gathered}$$

The prover sends the verifier each polynomial's evaluation

$f_i(z_i)$ and each partition's compressed PRT cofactors

$g_1^{H_j(s)}$.

The verifier compresses each partition's

$j\in [k]$ polynomial commitments and polynomial evaluations using randomness

${\gamma }_j$.

$$\begin{array}{rll}{g}_1^{F_j(s)}& =g_1^{f_1(s){\gamma }_j^0+\cdots +f_{t_j}(s){\gamma }_j^{t_j-1}}& =\prod _{i\in [t_j]}\mathsf{\text{Com}}(f_i{)}^{{\gamma }_j^{i-1}}\\ g_1^{F_j(z_j)}& =g_1^{f_1(z_j){\gamma }_j^0+\cdots +f_{t_j}(z_j){\gamma }_j^{t_j-1}}\end{array}$$

The verifier now has three values for each partition: the compressed polynomial commitments, the compressed polynomial evaluations, and the compressed PRT cofactor polynomials.

$$(g_1^{F_1(s)},g_1^{F_1(z_1)},g_1^{H_1(s)}),\dots ,(g_1^{F_k(s)},g_1^{F_k(z_k)},g_1^{H_k(s)})$$

The verifier samples a random

$\beta \leftarrow \mathbb{F}$ and computes the random linear combinations of all

$F_j(s)$,

$F_j(z_j)$,

$H_j(s)$ and

$H_j(s)z_j$:

$$\begin{array}{rll}A& =g_1^{F_1(s){\beta }^0+\cdots +F_k(s){\beta }^{k-1}}& =\prod _{j\in [k]}{\left(g_1^{F_j(s)}\right)}^{{\beta }^{j-1}}\\ B& =g_1^{F_1(z_1){\beta }^0+\cdots +F_k(z_k){\beta }^{k-1}}\\ C& =g_1^{H_1(s){\beta }^0+\cdots +H_k(s){\beta }^{k-1}}& =\prod _{j\in [k]}{\left(g_1^{H_j(s)}\right)}^{{\beta }^{j-1}}\\ D& =g_1^{H_1(s){\beta }^0{z}_1+\cdots +H_k(s){\beta }^{k-1}{z}_k}& =\prod _{j\in [k]}{\left(g_1^{H_j(s)}\right)}^{{\beta }^{j-1}{z}_j}\end{array}$$ then checks the verification equation:

$$e(AD/B,g_2)\stackrel{?}{=}e(C,g_2^{s^1})$$ which homomorphically checks the batched-batched-PRT equality:

$$\underset{―}{(F_1(s)-F_1(z_1)){\beta }^0}+\cdots +(F_k(s)-F_k(z_k)){\beta }^{k-1}=\underset{―}{H_1(s)(s-z_1){\beta }^0}+\cdots +H_k(s)(s-z_k){\beta }^{k-1}.\phantom{}$$

Why Use KZG Over Other Commitment Schemes?

Examples of other commitment schemes are CRHF's, Merkle trees, Pedersen [vector] commitments, accumulators, etc.

KZG10 has constant sized commitments, constant sized openings, opening does not reveal information about the committed polynomial

$f(X)$, i.e.

$(a_0,\dots ,a_d)$, and is a natural commitment choice for polynomial-based protocols.

Hiding - the function's output contains no information about its input, e.g.

$$\begin{gathered} M=\{m_1=\text{unicode}x201C\text{Yes"},m_2=\text{unicode}x201C\text{No"}\} \\ \begin{array}{rl}\text{Non-hiding: }& \mathsf{\text{Com}}(m_i)=H(m_i)\\ \text{Hiding: }& \mathsf{\text{Com}}(m_i,r)=H(m_i\parallel r)\end{array} \end{gathered}$$ committing to

$m_i$ via

$H(m_i)$ is non-hiding because an adversary can brute-force all commitments to find

$m_i$. Committing to

$m_i$ using a random hiding factor

$r$ via

$H(m_i\parallel r)$ is hiding because an adversary cannot brute-force all commitments without without knowing

$r$.

Comparison of Commitment Schemes:

Name	Commitment	Properties
CRHF	$\mathsf{\text{Com}}(m)=H(m)$	non-hiding, non-homomorphic
CRHF w/ Blinding	$\mathsf{\text{Com}}(m,r)=H(m\parallel r)$	hiding, non-homomorphic
Enc.	$\mathsf{\text{Com}}(m)=g^m$	non-hiding, homomorphic
Pedersen	$\mathsf{\text{Com}}(m,r)=g^m{h}^r$	hiding, homomorphic
CRHF	$\mathsf{\text{Com}}(f)=H(a_0\parallel \cdots \parallel a_d)$	must reveal all $a_i$
Enc.	$\mathsf{\text{Com}}(f)=(g^{a_0},\dots ,g^{a_d})$	partially revealing
Pedersen Vector	$\mathsf{\text{Com}}(f,r)=h^r{g}_0^{a_0}\dots g_d^{a_d}$	hiding, homomorphic, must reveal all $a_i$
Merkle Tree	$\mathsf{\text{MerkleTree}}(a_0,\dots ,a_d).\mathsf{\text{root}}$	partially revealing, ${\log }_2(d)$ communication
KZG10	$\mathsf{\text{Com}}(f)=g_1^{f(s)}$	hiding, homomorphic, constant commitment size, non-revealing, constant communication

Recap

PLONK represents witnesses

$\mathit{u}=(u_1,\dots ,u_w)$ using polynomials

$f(X)=u_1{X}^0+\cdots +u_w{X}^{w-1}$ and uses a PCS to commit to those polynomials.

The PRT equality for a polynomial

$f(X)$ evaluated at

$z$ is:

$$f(X)-f(z)=(X-z)h(X).\phantom{}$$

Encryption of an integer

$a\in \mathbb{Z}$ using a cyclic group

$\mathbb{G}=⟨g⟩=\{g^1,\dots ,g^p\}$ is:

$$g^a=g\ast \cdots \ast g.\phantom{}$$

Cyclic group encryption gives us homomorphic addition, scalar multiplication, and polynomial evaluation.

$$\begin{array}{rl}{g}^a{g}^b& =g^{a+b}\\ g^a/g^b& =g^{a-b}\\ {\left(g^a\right)}^c& =g^{ca}\\ g^{f(z)}& =\prod _{i\in [0,d]}{\left(g^{z^i}\right)}^{a_i}\end{array}$$

Pairings give us homomorphic multiplication.

$$\begin{gathered} e(g_1^a,g_2^b)=g_t^{ab} \\ e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_t \\ {\mathbb{G}}_1=⟨g_1⟩{\mathbb{G}}_2=⟨g_2⟩{\mathbb{G}}_t=⟨g_t⟩ \end{gathered}$$

KZG10 is a PCS that allows a prover to commit to a polynomial

$f(X)$ and a verifer to check claimed evaluations of that polynomial

$f(z)$. KZG is the PRT equality evaluated at a random input

$s$ (Schwarz-Zippel) generated during a trusted-setup. Because

$s$ is known to no party, the PRT equality is rewritten homomorphically.

$$\begin{array}{rl}e(g_1^{f(s)-f(z)},g_2)& =e(g_1^{h(s)},g_2^{s-z})\\ \Rightarrow g_t^{f(s)-f(z)}& =g_t^{h(s)(s-z)}\end{array}$$