# ZKEVM Aggregation Circuit Prover Load

In this first version of the write up we try to examine and estimate load of the verifier of a plonk gate.

## Batch KZG

We follow plonk paper variant of batch KZG commitment scheme in order to avoid G2 operations in verifier side.

> However we are going to implement aggregation circuit we should revisit if we get smaller aggregation circuit if we use Z(X) based batch KZG comitment scheme.

### Notation

Let's first agree on notations. Apoligies for very non formal approach for the subject but the goal is to give some intuition.

$A(X)$ is a polynomial such as $A(X) = a_0 + a_1X + a_2X^2 + a_3X^3 + ...$

$a$ is a scalar field element and an evaluation of $A(X)$ polynomial at some point. This point in our context is mostly obtained evaluating $A(X)$ at a random scalar challanges.

$A$ is a group element i.e. an elliptic curve point.

$G$ is the generator of our elliptic curve group $G_1$

$H$ is the generator of our elliptic curve group $G_2$.

#### Setup

In KZG setup phase we sample a random scalar $s$ and prapere the SRS available for both verifier and prover.

And the SRS is calculated as $s^iG$ and $sH$ where $0 < i < N$ and available to both verifier and prover along with generators $G$ and $H$

$A = Com(A(X))$ is commitment to the polynomial $A(X)$ and it is actually

$A = a_0 G + a_1 (sG) + a_2 (s^2G) + a_3 (s^3G)$

In our context we might use $X$ and $sG$ terms and $X$ and $sH$ terms interchangebly.

### Single Opening

Then let's review the single KZG opening protocol.

We want to prove that $A(x) = y$. So $A(X) - y$ must have root at $x$. It means that it is divisible by $(X - x)$. Then we can write:

$W(X) (X - x) = A(X) - y$

where $W(X)$ will be our witness polynomial. And we can also rewrite this equation
to obtain $G_2$ operation free verifier side.

$XW(X) = A(X) - y - xW(X)$

* Verifier samples random $x$ and sends it to the prover
* Prover evalution $A(X)$ at $x$ and finds $y$
* Prover commits to both $A(X)$ and $W(X)$ and finds $A$ and $W$.
* Prover send $y$, $A$ and $W$ to the verifier.

Then verifier checks the opening with following pairing equation.

$e(W, sH) = e(A - yG - xW, H)$

> Notice that if we were to commit polynomial Y(X) = y it is Com(Y(x)) = yG and if we were to commit U(X) = X in $G_2$ it is Com(U(X)) = sH. These elements are available to or can be calculated by verifier.

### Batch opening

We can generalize the idea above for multiple polynomials at various evaluation points and make verifiers work more efficient.

#### Single eval point

First let's go through multiple polynomial and single evaluation point case.

Now given evaluation point $x$ we want prove that $A_0(x) = y_0$, $A_1(x) = y_1$, ... $A_{n-1}(x) = y_{n-1}$. What we need to do is to divite linear combination of $A_i(x) - y_i$ terms with $(X-x)$

$W(X) (X - x) = \prod_{i=0}^{n} \alpha^i (A_i(X) - y_i)$

And pairing equation becomes:

$e(W, sH) = e(\sum_{i=0}^{n} \alpha^i (A_i -y_iG) - xW, H)$

#### Multiple eval point

Here we have multiple eval points. Let's say $A_i(X)$ are evaluated at $x_a$ $B_i(X)$ are evaluated at $x_b$ and $C_i(X)$ are evaluated at $x_c$. Notice that we will group polynomials by which point the are evaluated so $A_i(X)$ can be equal to $B_j(X)$. Actually this is the case with plonk KZG verification since we evaluate same column in different rotations. So lets see equations

$W_a(X) (X - x_a) = \prod_{i=0}^{n} \alpha_a^i (A_i(X) - y_{ai})$

$W_b(X) (X - x_b) = \prod_{i=0}^{n} \alpha_b^i (B_i(X) - y_{bi})$

$W_c(X) (X - x_c) = \prod_{i=0}^{n} \alpha_c^i (C_i(X) - y_{ci})$

To reduce verifiacation into single pairing equation we need to introduce another linear combination.

$F_a = \beta^0(\sum_{i=0}^{n} \alpha_a^i (A_i -y_{ai}G) - x_aW_a)$

$F_b = \beta^1(\sum_{i=0}^{n} \alpha_b^i (B_i -y_{bi}G) - x_bW_b)$

$F_c = \beta^2(\sum_{i=0}^{n} \alpha_c^i (C_i -y_{ci}G) - x_cW_c)$

$W = \beta^0W_a + \beta^1W_b + \beta^2W_c$

$e(W, sH) = e(F, H)$

## Plonk in halo2

In halo2 library linearization technique is not applied so proof and verification process a bit different than the paper. It is actually easier to reason about but obviously suboptimal for verifier. Let's define a simple gate equation as an example.

> Note that example below does not cover lookup tables yet.

$Q_a(X)A(X) + Q_b(X)B(X) + Q_{mul}(X)A(X)B(X) + Q_c(X)C(X) + Q_{c\_next}(X)C(wX) + Q_d(X) = 0$

Commitments to selector polinomials below are part of verification key:

$Q_a$, $Q_b$, $Q_c$, $Q_d$, $Q_{mul}$, $Q_{c\_next}$.

And commitments to witnesses are part of the proof:

$A$, $B$, $C$.

To verify the gate equation itself evaluations at some random point of these polynomials are also part of the proof.

$q_{a}$, $q_{b}$, $q_{c}$, $q_{c\_next}$ and $q_{d}$ for selector evaluations and

$a$, $b$, $c$ and $c\_next$ for witness evaluations.

What verifier needs to do

1. Check evaluations hold the gate equation:

$q_A * a + q_b * b + q_{mul} * a * b + q_c * c + q_{c\_next}* c_{next} + q_d = 0$

2. Check evaluations are correct openings at the random points and shifted points:

Here is the KZG part of the verification and we have two groups of commitments and evaluations.

* First one $U^1 = [A, B, C, Q_a, Q_b, Q_c, Q_d, Q_{mul}]$ and $e^1 = [a,b,c,q_a,q_b,q_c,q_d,q_{mul}]$ against evaluation point $x$

* And the other $U^2 = [C, Q_{c\_next}]$ and $e^2 = [c_{next}, q_{c\_next}]$ against $xw$

$F_{w^0} = \beta^0(\sum_{i=0}^{n} \alpha_a^i (U_i^1 - e_i^1 G) - xW_{w^0})$,

$F_{w^1} = \beta^1(\sum_{i=0}^{n} \alpha_b^i (U_i^2 - e_i^2 G) - xwW_{w^1})$,

$W = \beta^0 W_{w^0} + \beta^1 W_{w^1}$,

$e(W, sH) = e(F, H)$,

## Cost analysis

Under $G_2$ operation free approach we followed above we can conclude with this cost estimations for verifier:

1. Each column introduced with existing evaluation point $xw^i$ contributes as:

* An elliptic curve point which is the comitment to the proof size. For example $A$.
* A scalar field element which is the evaluation to the proof size. For example $a_{eval}$
* A linear combination term for batch under same eval point. Equivalent to say 2 group multiplication (1 fixed base 1 variable base) and 2 group addition. For example for this term: $\alpha * (A - a_{eval} * G)$

2. A new column with non existing evaluation point $xw^i$ contributes additional to above as:

* A elliptic curve point which is a new KZG witness commitment. For exaple $W_{w^0}$
* A linear combination term for batching witness comitments. It'd take 1 group multiplication and 1 group addition. For example $\beta^i * W_{w^i}$