# Proof of evaluation

## 1. Problem

* $f\in \mathbb{F}^d[X]$;
* $(a_1,a_2,\ldots,a_d)\in \mathbb{F}$
* $(c_1,c_2,\ldots,c_d)\in \mathbb{F}$
* $c(X)$ such that $c(\omega^i) = a_i$ and $c(\omega^{d + i}) = c_i$
* Prove that $f( c(w^i))=c_i$ for all $1 \leq i \leq d$.

## 2. Warmup: Proof of Division

* $f(X) \in \mathbb{F}^{2d}[X],\;q(X),g(X),r(X) \in \mathbb{F}^d[X]$
* Prove that $f(X) = q(X)g(X)+r(X)$

### 2.1 IOP form

* Let $f(X) = \sum f_i X^i$. Same for $g(X),q(X),r(X)$.
* Let $N$ be the smallest power of 2 exceeding $5d+3$.
* Let $\omega$ be $N$-th root of unity.

1. Prover constructs $h_1(X)$ such that
\begin{align}
h_1(\omega^i) &= f_i;\quad 0\leq i \leq 2d\\
h_1(\omega^{2d+1+i}) &=q_i;\quad 0\leq i \leq d\\
h_1(\omega^{3d+2+i}) &=g_i;\quad 0\leq i \leq d\\
h_1(\omega^{4d+3+i}) &=r_i;\quad 0\leq i \leq d\\
\end{align}

2. Prover sends $h_1$ to Oracle.
3. Verifier sends $\alpha$ to Prover.
4. Prover claims that $f(\alpha) = q(\alpha)g(\alpha)+r(\alpha)$. They construct $h_2,h_3,h_4,h_5,f_{\alpha}$ as follows:
\begin{align}
f_{\alpha}(\omega^i) &= \alpha^i;\\
h_2(\omega^0)&=0;\\
h_2(\omega^{i+1}) &= h_2(\omega^i)+\alpha^i q_i;\\
h_3(\omega^0)&=0;\\
h_3(\omega^{i+1}) &= h_3(\omega^i)+\alpha^i g_i;\\
h_4(\omega^0)&=0;\\
h_4(\omega^{i+1}) &= h_4(\omega^i)+\alpha^i r_i;\\
h_5(\omega^0)&=0;\\
h_5(\omega^{i+1}) &= h_5(\omega^i)+\alpha^i f_i+\alpha^{i+d+1}f_{i+d+1};
\end{align}
so that
\begin{align}
h_2(\omega^{d+1}) = q(\alpha) = \sum \alpha^i q_i;\\
h_3(\omega^{d+1}) = g(\alpha)=\sum\alpha^i g_i;\\
h_4(\omega^{d+1}) = r(\alpha)=\sum\alpha^i r_i;\\
h_5(\omega^{d+1}) = f(\alpha)=\sum\alpha^i f_i;
\end{align}


5. Prover sends $h_2,h_3,h_4,h_5$ to Oracle.
6. Verifier sends $\alpha$ to Oracle and checks at Oracle:
\begin{align}
h_2(\omega^{d+1})\cdot h_3(\omega^{d+1}) + h_4(\omega^{d+1})&=h_5(\omega^{d+1});\\
h_2(\omega^0)&=h_3(\omega^0)=h_4(\omega^0)=h_5(\omega^0)=0;\\
h_2(X\omega) &\equiv h_2(X)+f_{\alpha}(X)h_1(\omega^{2d+1}X);\\
h_3(X\omega) &\equiv h_3(X)+f_{\alpha}(X)h_1(\omega^{3d+2}X);\\
h_4(X\omega) &\equiv h_4(X)+f_{\alpha}(X)h_1(\omega^{4d+3}X);\\
h_5(X\omega) &\equiv h_5(X)+f_{\alpha}(X)h_1(X)+f_{\alpha}(\omega^{d+1}X)h_1(\omega^{d+1}X);\\
\end{align}

## 3. Batched Proof of Division

* $\{f^1,f^2,\ldots, f^k\}\in \mathbb{F}^{2d}[X],\;\{q^j,g^j,r^j\}_{1 \leq j \leq k}\in \mathbb{F}^d[X]$
* Prove that $f^i(X) = q^i(X)g^i(X)+r^i(X)$

### 3.1 IOP form

We highlight the difference with Section 2.1. We need $N$ be the smallest power of 2 exceeding $(5d+3)k$.

1. Prover constructs a single $h_1$ for all $f^j$:
\begin{align}
h_1(\omega^{i+(j-1)(5d+4)} &= f_i^j;\quad 0\leq i \leq 2d,\;1 \leq j \leq k\\
h_1(\omega^{2d+1+i+(j-1)(5d+4)}) &=q_i^j;\quad 0\leq i \leq d,\;1 \leq j \leq k\\
h_1(\omega^{3d+2+i+(j-1)(5d+4)}) &=g_i^j;\quad 0\leq i \leq d,\;1 \leq j \leq k\\
h_1(\omega^{4d+3+i+(j-1)(5d+4)}) &=r_i^j;\quad 0\leq i \leq d,\;1 \leq j \leq k\\
\end{align}

2. The same.
3. The same.
4. Prover constructs single $h_2,h_3,h_4, h_5$ by stacking witnesses for $f^1,\ldots,f^k$ as in $h_1$. So that

\begin{align}
h_2(\omega^{d+1+(j-1)(5d+4)}) = q^j(\alpha) ;\\
h_3(\omega^{d+1+(j-1)(5d+4)}) = g^j(\alpha) ;\\
h_4(\omega^{d+1+(j-1)(5d+4)}) = r^j(\alpha) ;\\
h_5(\omega^{d+1+(j-1)(5d+4)}) = f^j(\alpha);
\end{align}
5. The same
6. The same except that we use another set of selector polynomials for the first equation:
$$
h'(X)h_2(X)\cdot h_3(X) + h'(X)h_4(X)=h'(X)h_5(X);
$$
where $h'(X)=\begin{cases} 1,\quad \text{if }X = \omega^{d+1+(j-1)(5d+4)};\\
0,\quad\text{otherwise}
\end{cases}$
and use a stack of powers of $\alpha$ to construct $f_{\alpha}(X)$

## 4. Proof of Evaluation

* $F\in \mathbb{F}^{d}[X]$;
* $A=(a_1,a_2,\ldots,a_d)\in \mathbb{F}$
* $C=(c_1,c_2,\ldots,c_d)\in \mathbb{F}$
* Prove that $f(a_i)=c_i$ for all $i$.

### 4.1 IOP form

In the beginning, Prover sends interpolants $f_A(X)$ and $f_C(X)$ for $A$ and $C$ to Oracle.

The main argument is recursive. At the $k$th layer of recursion ($k$ starts with 1) we take as input $\mathbf{F}(X)$, $f_A(X)$, $f_C(X)$, and aim to prove that $F_i( f_A(\omega^{i 2^{d-k} +j}) ) = f_C(\omega^{i 2^{d-k} + j})$ for all $0\leq j <2^{d-k}$ and $0\leq i <2^k$.

1. Prover splits $A$ into $2^k$ parts $A_1,A_2,\ldots,A_{2^k}$. Accordingly they proceed with $C$.
3. Prover computes
\begin{align}
g_{i,1}(X) = \prod_{a\in A_{2i}} (X-a);\\
g_{i,2}(X) = \prod_{a\in A_{2i+1}} (X-a);\\
\end{align}
and divides $F_i(X)$ by $g_{i,1}(X)$ and $g_{i,2}(X)$ such that
\begin{align}
F_i(X) = q_{i,1}(X)g_{i,1}(X)+r_{i,1}(X);\\
F_i(X) = q_{i,2}(X)g_{i,2}(X)+r_{i,2}(X);\\
\end{align}

3. Prover creates a batch proof of division for $(F_i,q_{i,1},g_{i,1},r_{i,1})$ and $(F_i,q_{i,2},g_{i,2},r_{i,2})$.
4. Prover recurses to a batch proof of evaluation:
* $r_{i,1}(X)$ evaluates at $A_{2i}$ to $C_{2i}$;
* $r_{i,2}(X)$ evaluates at $A_{2i+1}$ to $C_{2i+1}$
with using batch proof of division at each level of recursion for all functions at this level.
5. Verifier verifies all batched proofs of division. At the last level of recursion they use $f_A(X)$ as a polynomial for stacked $r(X)$, and $X-f_C(X)$ as a polynomial for stacked $g(X)$.

7. Verifier checks the consistency between batched proofs by verifying that $r_i(X)$ at one step of recursion is exactly $f_i(X)$ at the next step of recursion by using a single polynomial equation for one recursion step.

We note that it is possible to use the same evaluation point $\alpha$ for all proofs of division provided that Prover sends all their $h_1$ polynomials to Oracle beforehand.

### Complexity

Each level of recursion deals with $k$ polynomials of degree $d/k$. The depth of recursion is $\log d$ so that the total communication complexity is $O(d \log d)$.

The complexity of computing all $q_i,g_i,r_i$ in the monomial form is $O(d \log^2 d)$ using fast evaluation algorithms (each recursion step costs $d\log d$).

## 5. Fast evaluation algorithm

Input:
* $F\in \mathbb{F}^{d}[X]$;
* $A=(a_1,a_2,\ldots,a_d)\in \mathbb{F}$

Output:
* $C=(c_1,c_2,\ldots,c_d)\in \mathbb{F}$

Such that $f(a_i)=c_i$ for all $i$.

### 5.1 Construction

1. If $d=1$ compute $F(a_1)$ in constant time and return.
2. Else split $A$ into $A_1$ and $A_2$.
3. Let $g_1(X) =\prod_{a\in A_1}(X-a)$ be vanishing poly of degree $d/2$ for $A_1$, and $g_2(X)$ be vanishing poly of degree $d/2$ for $A_2$.
4. Compute $f_1(X) = F(X) \bmod{g_1(X)}$ and $f_2(X) = F(X) \bmod{g_2(X)}$ of degree $d/2$ using fast division algorithm.
5. Evaluate $f_1$ on $A_1$ and get $C_1$ recursively (go to step 1). Evaluate $f_2$ on $A_2$ and get $C_2$. Return $C_1\cup C_2$.

### 5.2 Complexity

Our algorithm is divide-and-conquer. At the combination step we apply a fast division algorithm of complexity $O(d\log d)$. The cost of computing all vanishing polynomials is $d\log^2 d$ (see below). Thus for the complexity $C(d)$ of the evaluation algorithm without it we have an equation
$$
C(d) = d\log d + 2C(d/2)
$$
Thus the total complexity is $O(d\log^2 d)$.

### 5.3 Constructing all vanishing polys

We construct all vanishing polynomials in the monomial form from low degree to high degree. To compute a vanishing poly of degree $r$, we multiply two vanishing polys of degree $r/2$ using fast multiplication algorithm. The complexity of the combination step is $r\log r$ so we have for the complexity $V(r)$ an equation:
$$
V(r) = r\log r + 2V(r/2)
$$
This yields total complexity of $r \log^2 r$.

## 6. Fast division algorithm

Input:
* $f\in \mathbb{F}^{n}[X]$
* $g\in \mathbb{F}^{m}[X]$.

Output:
* $q\in \mathbb{F}^{n-m}[X]$
* $r\in \mathbb{F}^{m-1}[X]$
such that
$$
f(X) = q(X)g(X)+r(X)
$$

### 6.1 Idea

For $f(X) = f_0 + f_1X+\cdots+f_nX^n$ define
$$
\mathrm{rev}(f) = f_n +f_{n-1}X + \cdots + f_0 X^n
$$
Note that
$$
x^n f(1/x) = x^{n-m} q(1/x) x^m g(1/x) +x^{n-m+1}x^{m-1}r(1/x).
$$
In terms of reverses:
$$
\mathrm{rev}(f)= \mathrm{rev}(q)\cdot \mathrm{rev}(g) +x^{n-m+1}\mathrm{rev}(r).
$$
Then
$$
\mathrm{rev}(f)\equiv \mathrm{rev}(q)\cdot \mathrm{rev}(g) \pmod{x^{n-m+1}}.
$$
And

$$
\mathrm{rev}(q)\equiv \mathrm{rev}(f)\cdot \mathrm{rev}(g)^{-1} \pmod{x^{n-m+1}}.
$$
### 6.2 Construction
1. Compute $\mathrm{rev}(f),\mathrm{rev}(g)$.
2. Compute $\mathrm{rev}(g)^{-1}\bmod{x^{n-m+1}}$ using fast inversion algorithm.
3. Find $\mathrm{rev}(q)$, then $q$ and $r$ using fast polynomial multiplication.

### 6.3 Complexity
Both fast inversion algorithm and fast multiplication algorithm have complexity $O(d\log d)$ (see below) so the total complexity is $O(d\log d)$ .

## 7. Fast Inversion Algorithm
Input:
* $f\in \mathbb{F}[X]$
* $l$.

Output:
* $g\in \mathbb{F}[X]$
such that
$$
f(X)g(X)\equiv 1 \pmod{X^l}
$$

### 7.1 Idea
We find a "root" of an equation $\frac{1}{g}-f=0$ using Newton iteration for $\phi(g)=0$:
$$
g_{i+1} = g_i - \frac{\phi(g_i)}{\phi'(g_i)}
$$
which in our case is
$$
g_{i+1} = g_i - \frac{1/g_i-f}{-1/g_i^2} = 2g_i - fg_i^2
$$

### 7.2 Construction

1. Initialize $g_0=\frac{1}{f(0)}$.
2. Compute for $i$ up to $\log l$:
$$
g_{i+1} = (2g_i - f g_i^2)\bmod{x^{2^{i+1}}}
$$
3. Return $g_{\log l +1}$.

### 7.3 Complexity

At each step we do 3 fast polynomial multiplications of degree $2^i$. Using that
$$
\sum_{1\leq i \leq r} c\cdot 2^i \cdot i \leq 2cr 2^r
$$
the total cost is still $O(d\log d)$ as reduction modulo $x^{2^{i+1}}$ is easy.

## 8. Fast multiplication Algorithm

We multiply 2 polynomials of degree $d$ in $O(d\log d)$ time using FFT:
1. Compute $2d$-FFT of both polys.
2. Multiply pairwise.
3. Compute inverse FFT.