# Overview of Batched Kate PCS

The Kate commitment scheme can be used prove the knowledge of a bunch of polynomials by "opening" all of them at a single scalar. Suppose we have the following polynomials to be opened at respective points (we're considering a fairly general case here):

| Polynomials | Opening points |
| -------- | :--------: |
| $f_{1,1}, f_{1,2}, \dots, f_{1,m}$ | $z_1$ |
| $f_{2,1}, f_{2,2}, \dots, f_{2,m}$ | $z_2$ |
| $\vdots$ | $\vdots$ |
| $f_{n,1}, f_{n,2}, \dots, f_{n,m}$ | $z_n$ |

Here, we'll have to compute $n$ opening polynomials $\{W_i(X)\}_{i \in [n]}$ such that

$$
W_i(X) = \frac{F_i(X) - F_i(z_i)}{X - z_i}
$$

where $F_i(X) = \sum_{j=1}^{m} \gamma_i^{j-1} f_{i,j}$. The opening proof would be $\left\{ [W_1]_1, [W_2]_1, \dots, [W_n]_1, \{[f_{i,j}]_1, s_{i,j}\}_{i \in [n], j \in [m] } \right\}$ where $s_{i,j} = f_{i,j}(z_i) \in \mathbb{F}_p$. Clearly, the number of opening polynomial commitments needed to be computed by the prover is $n$ (i.e. the number of opening points). Finally, the verification needs the pairing check:

$$
e(W, Y) = e(F - Q, [1]_2)
$$

where

\begin{aligned}
W &= \sum_{i \in [n]} u^{i-1} [W_i]_1 \\
F &= \sum_{i \in [n]}\sum_{j \in [m]} u^{i-1} \gamma_i^{j-1} [f_{i,j}]_1 \\
Q &= \left[ \sum_{i \in [n]}\sum_{j \in [m]} u^{i-1} \gamma_i^{j-1} f_{i,j}(z_i) \right]_1 \\
Y &= \left[\sum_{i \in [n]}u^{i-1}(X - z_i) \right]_2
\end{aligned}