$$
\def\bold#1{\boldsymbol{#1}}
\def\stop{{\rlap{\quad.}\hphantom{}}}
\def\qed{{\rlap{\quad \tiny\blacksquare}\hphantom{}}}
\def\par{{\thinspace {\parallel} \thinspace}}
\def\hso{{\hspace{1pt}}}
\def\F{{\mathbb{F}}}
\def\G{{\mathbb{G}}}
\def\Z{{\mathbb{Z}}}
\def\la{{\langle}}
\def\ra{{\rangle}}
\def\LHS{{\text{LHS}}}
\def\RHS{{\text{RHS}}}
$$

# 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 $\bold{u} = (u_1, \dots, u_n)$ can be encoded into a polynomial $f(X) = u_1X^0 + \dots + u_nX^{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 $\bold{u}$ without learning any $u_i \in \bold{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)$.

$$
\eqalign{
f(X) - f(a) &= c\prod_i (X - r_i) \\
&= (X - a)h(X)
} \\
~\\
(X - a) \mathbin{\large|} f(X) - f(a)
$$

The PRT can be used to prove that a polynomial $f(X)$ contains the point $(a, f(a))$ by showing that $(X - a) \mathbin{\large|} f(X) - f(a)$ without remainder.

## Encryption

Here, *encryption* of an integer $a \in \Z$ means computing $g^a = g * \dots * g$ where $g$ is a generator of a prime order multiplicative cyclic group $\G = \la g \ra = \{g^1, \dots, g^p\}$ (which has a hard discrete log).
$$
(\G, \times) = \la g \ra = \{g^1, \dots, g^p\} \\
g^a \in \G \\
\Pr[\mathcal{A}(g, g^a) = a] = \textsf{negl}
$$

## Homomorphic Encryption

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


$$
\begin{array}{|c|c|c|c|c|}
\hline
& \textbf{Have} & \textbf{Want} & \textbf{How} \\
\hline
\text{Add.} & g^a, g^b & g^{a + b} & g^ag^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_0X^0 + \dots + a_dX^d,\ g^{s^0}, \dots, g^{s^d} & g^{f(s)} & \prod_{i \in [0, d]} (g^{s^i})^{a_i} \\
\hline
\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}$.
$$
\eqalign{
f(X) &= a_0X^0 + a_1X^1 + a_2X^2 \\
g^{f(s)} &= g^{a_0s^0 + a_1s^1 + a_2s^2} \\
&= \left(g^{a_0s^0}\right) \left(g^{a_1s^1}\right) \left(g^{a_2s^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} & \stop
}
$$

## Pairings

We cannot perform homomorphic multiplication using cyclic group encryption alone:
$$
(g^a, g^b)\ \rlap{\mapsto}{\ /}\ \ g^{ab}
$$ but, we can do so using pairings.

A **pairing** $e$ is a 2:1 function between groups $(\G_1, \G_2)$ and $\G_t$ such that exponents in the inputs (i.e. encrypted integers) are multiplied in the output.
$$
e: \G_1 \times \G_2 \rightarrow \G_t \\
e(g_1^a, g_2^b) = g_t^{ab}
$$

Here, $\G_1$, $\G_2$, and $\G_t$ are multiplicative, cyclic, and cryptographic groups of equal prime order $p$.
$$
(\G_1, \times) = \la g_1 \ra \quad\quad (\G_2, \times) = \la g_2 \ra \quad\quad (\G_t, \times) = \la g_t \ra
$$

We can homomorphically evaluate a product of polynomials $f(X)h(X)$ at an input $s$ given encrypted powers of $s$ in $\G_1$ and $\G_2$.
$$
\eqalign{
f(X) &= a_0X^0 + \dots + a_dX^d, \quad\quad & \text{deg}(f) = d, \quad\quad & (g_1^{s^0} {=}\hso g_1,\ \underline{g_1^{s^1}, \dots, g_1^{s^d}}) \\
h(X) &= X + b, & \text{deg}(h) = 1, \quad\quad & (g_2^{s^0} {=}\hso g_2,\ \underline{g_2^{s^1}}) \\
} \\
f(s)h(s) = \text{???} \\
~\\
\eqalign{
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 \\
} \\
~\\
e(g_1^{f(s)}, g_2^{h(s)}) = g_t^{f(s)h(s)}
$$

## ZKG10 PCS

KZG is parameterized by $(\kappa, \G_1, \G_2, \G_t, d)$:
* $\kappa$ - the security parameter (in bits) which gives the minimum group size, i.e. $p \geq 2^\kappa$.
* $\G_1$, $\G_2$, and $\G_t$ - cryptographic groups of equal prime order $p$ for which a pairing function is defined $e: \G_1 \times \G_2 \rightarrow \G_t$.
* $d$ - the largest polynomial degree that a prover can commit to.
$$
\textsf{new}(\kappa) \rightarrow (\G_1, \G_2, \G_t, d)
$$

KZG requires homomorphically evaluating a degree-$d$ polynomial in $\G_1$ and a degree-1 polynomial in $\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 $\G_1$ and $\G_2$, i.e. the **structured reference string** (SRS).
$$
\textsf{setup}() \rightarrow \textsf{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_0X^0 + \dots + a_dX^d$ by homomorphically evaluating it at $s$.
$$
\textsf{commit}(f) \rightarrow \textsf{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 \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)$.
$$
\textsf{eval}(z) \rightarrow (f(z), g_1^{h(s)}) \\
\eqalign{
f(X) &- f(z) = (X - z)h(X) \\
\Rightarrow \quad h(X) &= {f(X) - f(z) \over (X - z)} = b_0X^0 + \dots + b_{d - 1}X^{d - 1} \\
} \\
g_1^{h(s)} = \prod_{i \in [0, d - 1]} \left(g_1^{s^i}\right)^{b_i}
$$ $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$.
$$
\textsf{verify}(\bold{\cdot}) \rightarrow \{0, 1\} \\
\eqalign{
e(\textsf{Com}(f)/g_1^{f(z)}, g_2) &\overset{?}= e(g_1^{h(s)}, g_2^{s^1}/g_2^z) \\
\Rightarrow \quad e(g_1^{f(s) - f(z)}, g_2) &\overset{?}= e(g_1^{h(s)}, g_2^{s - z}) \\
\Rightarrow \quad\quad\quad\ \ \hso g_t^{f(s) - f(z)} &\overset{?}= g_t^{h(s)(s - z)}
}
$$ Which is equivalent to checking the PRT equality at a random input $s$ (Schwartz-Zippel).
$$
f(s) - f(z) \overset{?}= 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)] \leq {d \over |\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$.
$$
\eqalign{
h(s)(s - z)\ \ &\leadsto\ \ 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)\ \ &\leadsto\ \ e(g_1^{h(s) - f(z)}, g_2) = e(g_1^{h(s)}, g_2^{s - z})
}
$$

## Random Linear Combinations

A **linear combination** is a sum of binary products. The linear combination of two vectors $\bold{a}$ and $\bold{b}$ is their dot product.
$$
\bold{a} \bold{\cdot} \bold{b} = a_1b_1 + \dots + a_nb_n
$$

A **random linear combination** (RLC) of a vector $\bold{a}$ is its dot product with a vector of random values $\bold{\gamma} = (\gamma_1, \dots, \gamma_n) \leftarrow \F^n$.
$$
\bold{a} \bold{\cdot} \bold{\gamma} = a_1\gamma_1 + \dots + a_n\gamma_n
$$

The modular powers of an integer form a psuedorandom sequence, thus for a random $\gamma$ we consider $\bold{\gamma} = (\gamma^1, \dots, \gamma^d)$ to be *random*.

Schwartz-Zippel tells us that for a random $\gamma$, the RLC of a vector $\bold{a}$ with powers of $\gamma$ is (w.h.p.) unique.
$$
f(X) = a_0X^0 + \dots + a_dX^d \\
g(X) = b_0X^0 + \dots + b_dX^d \\
\bold{a} \neq \bold{b} \\
\gamma \leftarrow \F \\
\Pr[\bold{a} \bold{\cdot} \bold{\gamma} = \bold{b} \bold{\cdot} \bold{\gamma}] \leq {d \over |\F|}
$$

### 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$.
$$
\gamma \leftarrow \F \\
F(X) = f_1(X)\gamma^0 + \dots + f_t(X)\gamma^{t - 1}
$$ 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.
$$
\beta \leftarrow \F \\
F(\beta) = f_1(\beta)\gamma^0 + \dots + f_t(\beta)\gamma^{t - 1} \\
G(\beta) = g_1(\beta)\gamma^0 + \dots + g_t(\beta)\gamma^{t - 1} \\
F(\beta) = G(\beta) \overset{\text{w.h.p.}} \Longrightarrow F(X) = G(X),\ \ \text{i.e. } \forall f_i(X) = g_i(X)
$$

### 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.
$$
f_1(X) = g_1(X) \\
\vdots \\
f_t(X) = g_t(X) \\
\gamma \leftarrow \F \\
F(X) = f_1(X)\gamma^0 + \dots + f_t(X)\gamma^{t - 1} \\
G(X) = g_1(X)\gamma^0 + \dots + g_t(X)\gamma^{t - 1} \\
F(X) = G(X) \\
\beta \leftarrow \F \\
F(\beta) = G(\beta) \overset{\text{w.h.p.}}\Longrightarrow F(X) = G(X),\ \text{i.e. } \forall f_i(X) = g_i(X)
$$

### 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$.
$$
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 \F \\
\eqalign{
(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)
}
$$

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:
$$
f(X_1, \dots, X_n) \neq g(X_1, \dots, X_n) \\
\bold{\gamma} = (\gamma_1, \dots, \gamma_n) \leftarrow \F^n \\
\Pr[f(\bold{\gamma}) = g(\bold{\gamma})] \leq {d \over |\F|}
$$ 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))$.
$$
g(X, Y) = f_0(X)Y^0 + \dots + f_d(X)Y^d \\
\text{deg}(f_i) = d - i \
$$

Schwartz-Zippel says us that a univariate polynomial evaluated at a random input $\beta \leftarrow \F$ is (w.h.p.) unique.
$$
f_1(\beta) \neq 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 + \dots + f_d(\beta)Y^d
$$ The probability that the coefficient vectors of two different bivariate polynomials $g_1(X, Y) \neq g_2(X, Y)$ are equal after partially applying the random input $X = \beta$ is zero.
$$
\eqalign{
g_1(X, Y) &= f_0(X)Y^0 + \dots + f_d(X)Y^d \\
g_2(X, Y) &= h_0(X)Y^0 + \dots + 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)] \\
&= {d \over |\F|} \dots {0 \over |\F|} \\
&= 0
}
$$ Thus, partial application of $X = \beta$ yields a unique univariate polynomial, which Schwartz-Zippel tells us evaluates uniquely on random input $Y = \gamma \leftarrow \F$.
$$
g_1(X, Y) \neq g_2(X, Y) \\
\beta \leftarrow \F \\
g_1(\beta, Y) \neq g_2(\beta, Y) \\
\gamma \leftarrow \F \\
\Pr[g_1(\beta, \gamma) = g_2(\beta, \gamma)] = {d \over |F|}
$$

[Somewhat surprisingly] the bivariate and univariate Schwartz-Zippel probabilities are equal, which by induction can be generalized into the multivariate Schwartz-Zippel expression.
$$
f(X_1, \dots, X_n) = g_0(X_1, \dots, X_{n - 1})X_n^0 + \dots + g_d(X_1, \dots, X_{n - 1})X_n^d \\
(\gamma_1, \dots, \gamma_n) \leftarrow \F^n \\
\Pr[f_1(\gamma_1, \dots, \gamma_n) = f_2(\gamma_1, \dots, \gamma_n)] = {d \over |F|} \stop
$$

**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, \G_1, \G_2, \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$.
$$
\textsf{setup}() \rightarrow \textsf{SRS} =\{g_1^{s^0}, \dots, g_1^{s^d}, g_2^{s^0}, g_2^{s^1}\} \\
~\\
(f_1, \dots, f_t) \\
\textsf{commit}(f_i) \rightarrow \textsf{Com}(f_i) = g_1^{f_i(s)} \\
(\textsf{Com}(f_1), \dots, \textsf{Com}(f_t))
$$

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 \leq t$ distinct inputs, the verifier samples a random value $\gamma$ and sends it to the prover $(\gamma_1, \dots, \gamma_k) \leftarrow \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)$.
$$
\eqalign{
\forall i \in [t]: \quad & h_i(X) &= {f_i(X) - f(z_j) \over (X - {z_j})} = b_0X^0 + \dots + b_{d - 1}X^{d - 1} \\
\forall i \in [t]: \quad & g_1^{h_i(s)} &= \prod_{i \in [0, d - 1]} \left(g_1^{s^i}\right)^{b_i} \\
\forall j \in [k]: \quad & g_1^{H_j(s)} &= g_1^{h_\mu(s)\gamma_j^0 + \dots + h_\nu(s)\gamma_j^{t_j - 1}} = \prod_{i \in [t_j]} \left(g_1^{h_i(s)}\right)^{\gamma_j^{i - 1}}
} \\
(f_1(z_1), \dots, f_t(z_t), g_1^{H_1(s)}, \dots, g_1^{H_k(s)})
$$

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$.
$$
\eqalign{
g_1^{F_j(s)} &= g_1^{f_1(s)\gamma_j^0 + \dots + f_{t_j}(s)\gamma_j^{t_j - 1}} &= \prod_{i \in [t_j]} \textsf{Com}(f_i)^{\gamma_j^{i - 1}} \\
g_1^{F_j(z_j)} &= g_1^{f_1(z_j)\gamma_j^0 + \dots + f_{t_j}(z_j)\gamma_j^{t_j - 1}}
}
$$

The verifier now has three values for each partition: the compressed polynomial commitments, the compressed polynomial evaluations, and the compressed PRT cofactor polynomials.
$$
\left(g_1^{F_1(s)}, g_1^{F_1(z_1)}, g_1^{H_1(s)}\right), \dots, \left(g_1^{F_k(s)}, g_1^{F_k(z_k)}, g_1^{H_k(s)}\right)
$$

The verifier samples a random $\beta \leftarrow \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$:
$$
\eqalign{
A &= g_1^{F_1(s)\beta^0 + \dots + 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 + \dots + F_k(z_k)\beta^{k - 1}} \\
C &= g_1^{H_1(s)\beta^0 + \dots + 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^0z_1 + \dots + H_k(s)\beta^{k - 1}z_k} \quad &= \prod_{j \in [k]} \left(g_1^{H_j(s)}\right)^{\beta^{j - 1}z_j} \\
}
$$ then checks the verification equation:
$$
e(AD/B, g_2) \overset{?}= e(C, g_2^{s^1})
$$ which homomorphically checks the batched-batched-PRT equality:
$$
\underline{(F_1(s) - F_1(z_1))\beta^0} + \dots + (F_k(s) - F_k(z_k))\beta^{k - 1} = \underline{H_1(s)(s - z_1)\beta^0} + \dots + H_k(s)(s - z_k)\beta^{k - 1} \stop
$$

## 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.

<br/>

**Hiding** - the function's output contains no information about its input, e.g.
$$
M = \{m_1 = \unicode{x201C}\text{Yes"}, m_2 = \unicode{x201C}\text{No"}\} \\
\eqalign{
\text{Non-hiding: } &\textsf{Com}(m_i) = H(m_i) \\
\text{Hiding: } &\textsf{Com}(m_i, r) = H(m_i \par r)
}
$$ 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 \par r)$ is hiding because an adversary cannot brute-force all commitments without without knowing $r$.

<br/>

**Comparison of Commitment Schemes:**

| Name | Commitment | Properties |
| :--------: | :--------: | :--------: |
| CRHF | $\textsf{Com}(m) = H(m)$ | non-hiding, non-homomorphic |
| CRHF w/ Blinding | $\textsf{Com}(m, r) = H(m \par r)$ | hiding, non-homomorphic |
| Enc. | $\textsf{Com}(m) = g^m$ | non-hiding, homomorphic |
| Pedersen | $\textsf{Com}(m, r) = g^mh^r$ | hiding, homomorphic |
| CRHF | $\textsf{Com}(f) = H(a_0 \par \dots \par a_d)$ | must reveal all $a_i$ |
| Enc. | $\textsf{Com}(f) = (g^{a_0}, \dots, g^{a_d})$ | partially revealing |
| Pedersen Vector | $\textsf{Com}(f, r) = h^rg_0^{a_0}\dots g_d^{a_d}$ | hiding, homomorphic, must reveal all $a_i$ |
| Merkle Tree | $\textsf{MerkleTree}(a_0, \dots, a_d).\textsf{root}$ | partially revealing, $\log_2(d)$ communication |
| KZG10 |$\textsf{Com}(f) = g_1^{f(s)}$ | hiding, homomorphic, constant commitment size, non-revealing, constant communication |

# Recap

PLONK represents witnesses $\bold{u} = (u_1, \dots, u_w)$ using polynomials $f(X) = u_1X^0 + \dots + u_wX^{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) \stop
$$

Encryption of an integer $a \in \Z$ using a cyclic group $\G = \la g \ra = \{g^1, \dots, g^p\}$ is:
$$
g^a = g * \dots * g \stop
$$

Cyclic group encryption gives us homomorphic addition, scalar multiplication, and polynomial evaluation.
$$
\eqalign{
g^ag^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}
}
$$

Pairings give us homomorphic multiplication.
$$
e(g_1^a, g_2^b) = g_t^{ab} \\
e: \G_1 \times \G_2 \rightarrow \G_t \\
\G_1 = \la g_1 \ra \quad\quad \G_2 = \la g_2 \ra \quad\quad \G_t = \la g_t \ra
$$

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.
$$
\eqalign{
e(g_1^{f(s) - f(z)}, g_2) &= e(g_1^{h(s)}, g_2^{s - z}) \\
\Rightarrow \quad\quad\quad\ \ g_t^{f(s) - f(z)} &= g_t^{h(s)(s - z)}
}
$$