main.tex

\documentclass[a4paper]{article}
\usepackage[hmargin=2cm,vmargin=2cm]{geometry}


\pagestyle{plain}

\usepackage{amssymb,amsthm,amsmath,amsfonts,longtable, comment,array, ifpdf, hyperref,url}
\usepackage{graphicx}

\title{Fast amortized Kate proofs}
\author{Dankrad Feist and Dmitry Khovratovich \\Ethereum Foundation}

\begin{document}

\maketitle

\section{Definitions}

\subsection{Setup}

Let $g$ be a group $\mathbb{G}$ element, and denote $[a] = a\cdot g$ a group element where $a$ is an integer. 

Let $s$ be a secret, then a universal setup of degree $m$ consists of  $m$ elements of $\mathbb{G}$:
$$
[s], [s^2], \ldots, [s^m].
$$


\subsection{Commitment}
Let $f(X) = \sum_{0\leq i \leq m}f_i X^i$ be a polynomial of degree $m$. Then a commitment $C_f\in \mathbb{G}$ is defined as
$$
C_f = \sum_{0\leq i \leq m} f_i[s^i],
$$
being effectively an evaluation of $f$ at point $s$.

\subsection{Proof}
Note that for any $y$ we have that $(X-y)$ divides $f(X) - f(y)$. Then the proof that $f(y) = z$ is defined as
$$
\pi[f(y)=z] = C_T,
$$
where $T_y(X) = \frac{f(X)-z}{X-y}$ is a polynomial of degree $(m-1)$.

Note that a proof can be constructed using $m$ scalar multiplications in the group. The coefficients of $T$ are computed with one multiplication each:
\begin{align}
    T_y(X) &= \sum_{0\leq i \leq m-1}t_i X^i;\\
    t_{m-1} &= f_m;\\
    t_j &= f_{j+1}+y\cdot t_{j+1} .
\end{align}
Expanding on the last equation, we get
\begin{multline}
T_y(X) =f_mX^{m-1} + (f_{m-1}+yf_{m})X^{m-2} + (f_{m-2}+yf_{m-1}+y^2f_m)X^{m-3} +\\+
(f_{m-3}+yf_{m-2}+y^2f_{m-1}+y^3)X^{m-4}+\cdots +  (f_{1}+yf_{2}+y^2f_3+\cdots+y^{m-1}f_m).
\end{multline}
\section{Multiple proofs}\label{sec:multiproof}

Let $w$ be a $2^n$-th root of unity. We show how to construct Kate proofs for  $w,w^2,w^3,\ldots, w^{2^n}=1$. 

Note that a proof for $w^k$ is
\begin{multline}
\pi[f(w^k)=z^k] = C_{T_{w^k}}  =f_m[s^{m-1}] + (f_{m-1}+w^kf_{m})[s^{m-2}] + (f_{m-2}+w^kf_{m-1}+w^{2k}f_m)[s^{m-3}] +\\+
(f_{m-3}+w^kf_{m-2}+w^{2k}f_{m-1}+w^{3k})[s^{m-4}]+\cdots +  (f_{1}+w^kf_{2}+w^{2k}f_3+\cdots+w^{(m-1)k}f_m).
\end{multline}
Regrouping the terms, we get (for $2^n\geq m$):
\begin{align}
     C_{T_{w^k}} 
     =&\left(f_m[s^{m-1}]+f_{m-1}[s^{m-2}]+f_{m-2}[s^{m-3}]+\cdots + f_2[s]+f_1\right)+\\
     &+\left(f_m[s^{m-2}]+f_{m-1}[s^{m-3}]+f_{m-2}[s^{m-4}]+\cdots + f_3[s]+f_2\right)w^k+\\
     &+\left(f_m[s^{m-3}]+f_{m-1}[s^{m-4}]+f_{m-2}[s^{m-5}]+\cdots + f_4[s]+f_3\right)w^{2k}+\\
     &+\left(f_m[s^{m-4}]+f_{m-1}[s^{m-5}]+f_{m-2}[s^{m-6}]+\cdots + f_5[s]+f_4\right)w^{3k}+\\
     &\cdots\\
     &+(f_m[s]+f_{m-1})w^{(m-2)k}+f_mw^{(m-1)k}.
\end{align}
Let for $1
\leq i \leq 2^n$ denote $$
h_i = \left(f_m[s^{m-i}]+f_{m-1}[s^{m-i-1}]+f_{m-2}[s^{m-i-2}]+\cdots + f_{i+1}[s]+f_i\right).
$$
with $h_i=0$ for $i>m$. Then
\begin{equation}\label{eq:ct}
     C_{T_{w^k}} = h_1 + h_2w^k + h_3w^{2k}+\cdots + h_mw^{(m-1)k}.
\end{equation}

Let us denote
$$
\mathbf{C}_T = [C_{T_{w^1}},C_{T_{w^2}},\ldots,C_{T_{w^{2^n}}}]
$$
and
\begin{equation}\label{eq:h}
\mathbf{h} = [h_1,h_2,\ldots,h_{2^n}].
\end{equation}
Recalling that the Discrete Fourier Transform of $\mathbf{a}=[a_1,a_2,\ldots,a_{2^n}]$ is
$$
\widehat{\mathbf{a}}= [\widehat{a_1},\widehat{a_2},\ldots,\widehat{a_{2^n}}]
$$
where 
$$
\widehat{a_k} = \sum_{i}a_iw^{ki}
$$
Therefore, from Equation~\eqref{eq:ct}
\begin{equation}
 \mathbf{C}_T = \mathrm{DFT}(\mathbf{h}), 
\end{equation}
and can be computed in $O(n2^n)$ cost given $\mathbf{h}$ using FFT algorithms\footnote{This works directly as described if $m\leq2^n$. Otherwise, the vector $\mathbf{h}$ can be modified, "wrapping around" the extra $\neq 0$ terms, so the idea also works for $m>2^n$.}.

\subsection{Computing $\mathbf{h}$}\label{sec:h}

Now we demonstrate that $\mathbf{h}$ can be also computed efficiently from $\{f_i\}$. Indeed, by definition
$$
\begin{bmatrix}
h_1\\
h_2\\
h_3\\
\vdots\\
h_{m-1}\\
h_m
\end{bmatrix}= \begin{bmatrix}
f_m &f_{m-1}&f_{m-2}&f_{m-3}&\cdots & f_1\\
0& f_m &f_{m-1}&f_{m-2}&\cdots & f_2\\
0 & 0& f_m &f_{m-1}&\cdots & f_3\\
&&\ddots&&&\\
0 & 0& 0 &0&\cdots & f_{m-1}\\
0 & 0& 0 &0&\cdots & f_m\\
\end{bmatrix}\cdot\begin{bmatrix}
[s^{m-1}]\\
[s^{m-2}]\\
[s^{m-3}]\\
\vdots\\
[s]\\
1
\end{bmatrix}
$$
The matrix 
$$
A = \begin{bmatrix}
f_m &f_{m-1}&f_{m-2}&f_{m-3}&\cdots & f_1\\
0& f_m &f_{m-1}&f_{m-2}&\cdots & f_2\\
0 & 0& f_m &f_{m-1}&\cdots & f_3\\
&&\cdots&&&\\
0 & 0& 0 &0&\cdots & f_{m-1}\\
0 & 0& 0 &0&\cdots & f_m\\
\end{bmatrix}
$$
is a \emph{Toeplitz} matrix. It is known that a multiplication of a vector by a $m\times m$ Toeplitz matrix costs $O(m\log m)$ operations using FFT (e.g. see "Matrix Computations" by Golub and Van Loan, or in \url{https://alinush.github.io/2020/03/19/multiplying-a-vector-by-a-toeplitz-matrix.html#:~:text=To%20multiply%20a%20Toeplitz%20matrix,x%20T%20n%20x%20%E2%86%92%20.}). 

Therefore, we can first compute $\mathbf{h}$ from SRS and then all  $2^n$ Kate proofs, i.e. $\mathbf{C}_T$, using $O(n2^n)$ multiplications compared to $O(2^{2n})$ for the naive approach (assuming $m = O(2^n)$).

\section{Multi-reveal}

Let $\psi\in\mathbb{F}_p$ be an $\ell$-th root of unity ($\psi^\ell=1$). Let's say we want to reveal the polynomial evaluations $f(y) = z_0$, $f(\psi y) = z_1$, $\ldots$, $f(\psi^{\ell-1} y)=z_{\ell - 1}$.

Noting that $(x-y)\cdot(x-\psi y) \cdots (x - \psi^{\ell-1} y) = x^\ell - y^\ell$, the proof for this can be given by computing the polynomial
\begin{equation}
g(x) = f(x) // (x^\ell - y^\ell)\text{,}
\end{equation}
where $//$ stands for the truncated long division, and then computing the proof
\begin{equation}
     \pi[f(y) = z_0, \ldots, f(\psi^{\ell-1}y)=z_{\ell - 1}] = [g(s)] \text{.}
\end{equation}

This proof can be verified by computing the checking polynomial $h(x) = f(x) \mod (x^\ell - y^\ell)$ (which can be interpolated from the given values), and checking that
\begin{equation}
e(C_f, \cdot) = e(\pi[f(y) = z_0, \ldots, f(\psi^{\ell-1}y)=z_{\ell - 1}], [s^\ell - y^\ell]) e(h(s),\cdot) \text{.}
\end{equation}

\subsection{Multiple multi-reveals -- odd $\ell$}

We now want to generalise the result in section \ref{sec:multiproof} to the case were each of the reveals is actually a multireveal.

Letting $w$ a $2^n$-th root of unity, we want to compute proofs
\begin{eqnarray}
     \pi[f(1), \ldots, f(\psi^{\ell-1})] &=& C_{T_{w^0, \ell}} \\
     \pi[f(w), \ldots, f(w\psi^{\ell-1})] &=& C_{T_{w^1, \ell}} \\
     &\vdots& \nonumber \\
     \pi[f(w^{2^n-1}), \ldots, f(w^{2^n-1}\psi^{\ell-1})] &=& C_{T_{w^{2^n-1}, \ell}} \text{.}
\end{eqnarray}

The proof for $w^k$ is
\begin{multline}
\pi[f(w^k), \ldots, f(w^k\psi^{\ell-1})] = C_{T_{w^k,\ell}}  =f_m[s^{m-\ell}] + f_{m-1}[s^{m-\ell - 1}] + \dots + f_{m-\ell+1}[s^{m-2\ell+1}] +\\
+ (f_{m-\ell}+w^{k\ell}f_{m})[s^{m-2\ell}] + (f_{m-\ell-1}+w^{k\ell}f_{m-1})[s^{m-2\ell-1}] + \cdots + (f_{m-2\ell+1}+w^{k\ell}f_{m-\ell+1})[s^{m-3\ell+1}] +\\
+ (f_{m-2\ell}+w^{k\ell}f_{m-\ell} +w^{2k\ell}f_{m})[s^{m-3\ell}] + (f_{m-2\ell-1}+w^{k\ell}f_{m-\ell-1} + w^{2k\ell}f_{m-1})[s^{m-3\ell-1}] + \\ \cdots + (f_{m-3\ell+1}+w^{k\ell}f_{m-2\ell+1}+w^{2k\ell}f_{m-\ell+1})[s^{m-4\ell+1}] +\\
\vdots \\
\end{multline}
Regrouping the terms, we get (for $2^n\geq m$):
\begin{align}
     C_{T_{w^k,\ell}} 
     =&\left(f_m[s^{m-\ell}]+f_{m-1}[s^{m-\ell -1}]+f_{m-2}[s^{m-\ell-2}]+\cdots + f_{\ell+1}[s]+f_\ell\right)+\\
     &+\left(f_m[s^{m-2\ell}]+f_{m-1}[s^{m-2\ell-1}]+f_{m-2}[s^{m-2\ell-2}]+\cdots + f_{2\ell+1}[s]+f_{2\ell}\right)w^{k\ell}+\\
     &+\left(f_m[s^{m-3\ell}]+f_{m-1}[s^{m-3\ell-1}]+f_{m-2}[s^{m-3\ell-2}]+\cdots + f_{3\ell+1}[s]+f_{3\ell}\right)w^{2k\ell}+\\
     &+\left(f_m[s^{m-4\ell}]+f_{m-1}[s^{m-4\ell-1}]+f_{m-2}[s^{m-4\ell-2}]+\cdots + f_{4\ell+1}[s]+f_{4\ell}\right)w^{3k\ell}+\\
     &\vdots \\
     & (\cdots) w^{\lfloor m / \ell\rfloor k\ell} 
\end{align}
Let for $i \geq 1$ denote 
$$
h_i = \left(f_m[s^{m-i}]+f_{m-1}[s^{m-i-1}]+f_{m-2}[s^{m-i-2}]+\cdots + f_{i+1}[s]+f_i\right).
$$
with $h_i=0$ for $i>m$. Then
\begin{equation}\label{eq:ctl}
     C_{T_{w^k,\ell}} = h_\ell + h_{2\ell}w^{k\ell} + h_{3\ell}w^{2k\ell}+\cdots + h_{m\ell}w^{(m-1)k\ell}.
\end{equation}

Let us denote
$$
\mathbf{C}_{T_\ell} = [C_{T_{w, \ell}},C_{T_{w^{2}, \ell}},\ldots,C_{T_{w^{2^n}, \ell}}]
$$
and
$$
\mathbf{h_\ell} = [h_\ell,0h_{\ell+1},\ldots,0h_{2\ell-1},h_{2\ell},0h_{2\ell+1},\ldots,0h_{3\ell-1},h_{3\ell+1},0h_{3\ell+1},\ldots,0h_{2^n+\ell-1}].
$$
Then, from Equation~\eqref{eq:ctl}
\begin{equation}
 \mathbf{C}_{T_\ell} = \mathrm{DFT}(\mathbf{h_\ell}), 
\end{equation}
and can be computed in $O(n2^n)$ cost given $\mathbf{h_\ell}$ using FFT algorithms.

\subsubsection{Computing $\mathbf{h_\ell}$}\label{sec:hl}

In order to compute $\mathbf{h_\ell}$ we need to slightly modify the algorithm from section \ref{sec:h}. First, define
\begin{multline}
\mathbf{h}_{\ell, i\ell, j} = f_{m-j}[s^{m-i\ell-j}] + f_{m-\ell-j}[s^{m-(i+1)\ell-j}] + f_{m-2\ell-j}[s^{m-(i+2)\ell-j}] + \cdots\\ + f_{(m - j) \% \ell + (i+1)\ell}[s^{(m-j)\% \ell + \ell}]  + f_{(m - j) \% \ell + i\ell}[s^{(m-j)\% \ell}].
\end{multline}
Using this,
\begin{equation}
\mathbf{h}_{i\ell} = \sum_{j=0}^{\ell-1}\mathbf{h}_{\ell, i\ell, j}\text{.}
\end{equation}

The $\mathbf{h}_{\ell, i\ell, j}$ can be computed by the $\ell$ Toeplitz matrix multiplications:
$$
\begin{bmatrix}
h_{\ell,1\ell,j}\\
h_{\ell,2\ell,j}\\
h_{\ell,3\ell,j}\\
\vdots\\
h_{\ell,(\lfloor \frac{m-j}{\ell}\rfloor-1)\ell,j}\\
h_{\ell,\lfloor \frac{m-j}{\ell}\rfloor\ell,j}
\end{bmatrix}= \begin{bmatrix}
f_{m-j} &f_{m-1\ell-j}&f_{m-2\ell-j}&f_{m-3\ell-j}&\cdots & f_{(m - j) \% \ell + \ell}\\
0& f_{m-j} &f_{m-1\ell-j}&f_{m-2\ell-j}&\cdots & f_{(m - j) \% \ell + 2\ell}\\
0 & 0& f_{m-j} &f_{m-1\ell-j}&\cdots & f_{(m - j) \% \ell + 3\ell}\\
&&&&\ddots&\\
0 & 0& 0 &0&\cdots & f_{m-\ell-j}\\
0 & 0& 0 &0&\cdots & f_{m-j}\\
\end{bmatrix}\cdot\begin{bmatrix}
[s^{m-1\ell-j}]\\
[s^{m-2\ell-j}]\\
[s^{m-3\ell-j}]\\
\vdots\\
[s^{(m-j)\% \ell + \ell}]\\
[s^{(m-j)\% \ell}]
\end{bmatrix}
$$

These matrix multiplications can be done in the same way as the Toeplitz matrix multiplication in section \ref{sec:h} using FFTs. Note that the vector multiplied by the matrix is independent from the polynomial coefficients, so its Fourier transform can be precomputed, necessitating $\ell$ Fourier transforms of size $2m/\ell$ in the precompute. However, the output of the multiplication can be added before transforming back, so only one IFT of size $2m/\ell$ is necessary.

\subsection{Multiple multi-reveals -- $\ell$ power of two}

Let $\ell=2^r<2^n$. Define $\psi=w^{2^{n-r}}$.

We want to compute the proofs
\begin{eqnarray}
     \pi[f(1), \ldots, f(\psi^{\ell-1})] &=& C_{T_{w^0, \ell}} \\
     \pi[f(w), \ldots, f(w\psi^{\ell-1})] &=& C_{T_{w^1, \ell}} \\
     &\vdots& \nonumber \\
     \pi[f(w^{2^{n-r}-1}), \ldots, f(w^{2^{n-r}-1}\psi^{\ell-1})] &=& C_{T_{w^{2^{n-r}-1}, \ell}} \text{.}
\end{eqnarray}
We do not need proofs for $w^{2^{n-r}}$ to $w^{2^{n}-1}$, as these would already be covered.

Things follow analogously to equation \eqref{eq:ctl}:
\begin{equation}
     C_{T_{w^k,\ell}} = h_\ell + h_{2\ell}w^{k\ell} + h_{3\ell}w^{2k\ell}+\cdots + h_{m\ell}w^{(m-1)k\ell}
\end{equation}

Define $\varphi=w^\ell$ and get
\begin{equation}\label{eq:ctle}
     C_{T_{w^k,\ell}} = h_\ell + h_{2\ell}\varphi^{k} + h_{3\ell}\varphi^{2k}+\cdots + h_{m\ell}\varphi^{(m-1)k}
\end{equation}

Defining
$$
\mathbf{C}_{T_\ell} = [C_{T_{w}},C_{T_{w^{2}}},\ldots,C_{T_{w^{2^{n-r}}}}]
$$
and
$$
\mathbf{h'_\ell} = [h_\ell, h_{2\ell},\ldots,h_{(2^{n-r}-1)\ell}],
$$
we get
\begin{equation}
 \mathbf{C}_{T_\ell} = \mathrm{DFT}_\varphi(\mathbf{h_\ell}), 
\end{equation}
and can be computed in $O((n-r)2^{n-r})$ cost given $\mathbf{h'_\ell}$ using FFT algorithms. The vector $\mathbf{h'_\ell}$ can be computed in a similar way as described in section \ref{sec:hl}.

\end{document}