1\documentclass{article}
  2\usepackage[utf8]{inputenc}
  3\usepackage{amsfonts}
  4\usepackage{amsthm}
  5\usepackage{amsmath}
  6\usepackage{mathtools}
  7\usepackage{enumerate}
  8\usepackage{hyperref}
  9\usepackage{xcolor}
 10
 11% prevent warnings of underfull \hbox:
 12\usepackage{etoolbox}
 13\apptocmd{\sloppy}{\hbadness 4000\relax}{}{}
 14
 15\theoremstyle{definition}
 16\newtheorem{definition}{Def}[section]
 17\newtheorem{theorem}[definition]{Thm}
 18
 19% custom lemma environment to set custom numbers
 20\newtheorem{innerlemma}{Lemma}
 21\newenvironment{lemma}[1]
 22{\renewcommand\theinnerlemma{#1}\innerlemma}
 23{\endinnerlemma}
 24
 25
 26\title{Notes on FRI}
 27\author{arnaucube}
 28\date{February 2023}
 29
 30\begin{document}
 31
 32\maketitle
 33
 34\begin{abstract}
 35	Notes taken from \href{https://sites.google.com/site/vincenzoiovinoit/}{Vincenzo Iovino} explainations about FRI \cite{fri}, \cite{cryptoeprint:2022/1216}.
 36
 37	These notes are for self-consumption, are not complete, don't include all the steps neither all the proofs.
 38
 39	An implementation of FRI can be found at \href{https://github.com/arnaucube/fri-commitment}{https://github.com/arnaucube/fri-commitment}.
 40\end{abstract}
 41
 42\tableofcontents
 43
 44\section{Preliminaries}
 45\subsection{Low degree testing}
 46V wants to ensure that $deg(f(x)) \leq d$.
 47
 48We are in the IOP setting, V asks on a point, P sends back the opening at that point.
 49
 50TODO
 51
 52\subsubsection{General degree d test}
 53
 54Query at points $\{ x_i \}_0^{d+1},~z$ (with rand $z \overset{R}{\in} \mathbb{F}$).
 55Interpolate $p(x)$ at $\{f(x_i)\}_0^{d+1}$ to reconstruct the unique polynomial $p$ of degree $d$ such that $p(x_i)=f(x_i)~\forall i=1, \ldots, d+1$.
 56
 57V checks $p(z)=f(z)$, if the check passes, then V is convinced with high probability.
 58
 59This needs $d+2$ queries, is linear, $\mathcal{O}(n)$. With FRI we will have the test in $\mathcal{O}(\log{}d)$.
 60
 61\section{FRI protocol}
 62Allows to test if a function $f$ is a poly of degree $\leq d$ in $\mathcal{O}(\log{}d)$.
 63
 64Note: "P \emph{sends} $f(x)$ to V", "\emph{sends}", in the ideal IOP model means that all the table of $f(x)$ is sent, in practice is sent a commitment to $f(x)$.
 65
 66\subsection{Intuition}
 67V wants to check that two functions $g,~h$ are both polynomials of degree $\leq d$.
 68
 69Consider the following protocol:
 70
 71\begin{enumerate}
 72	\item V sends $\alpha \in \mathbb{F}$ to P. P sends $f(x) = g(x) + \alpha h(x)$ to V.
 73	\item P sends $f(x)=g(x) + \alpha h(x)$ to V.
 74	\item V queries $f(r), ~g(r), ~h(r)$ for rand $r \in \mathbb{F}$.
 75	\item V checks $f(r)=g(r) + \alpha h(r)$. (Schwartz-Zippel lema).
 76		If holds, V can be certain that $f(x)=g(x)+ \alpha h(x)$.
 77	\item P proves that $deg(f) \leq d$. 
 78	\item If V is convinced that $deg(f) \leq d$, V belives that both $g, h$ have $deg \leq d$.
 79\end{enumerate}
 80
 81%/// TODO tabulate this next lines
 82With high probablility, $\alpha$ will not cancel the coeffs with $deg \geq d+1$. % TODO check which is the name of this theorem or why this is true
 83
 84Let $g(x)=a \cdot x^{d+1}, ~~ h(x)=b \cdot x^{d+1}$, and set $f(x) = g(x) + \alpha h(x)$.
 85Imagine that P can chose $\alpha$ such that $a x^{d+1} + \alpha \cdot b x^{d+1} = 0$, then, in $f(x)$ the coefficients of degree $d+1$ would cancel.
 86%///
 87
 88\quad
 89
 90Here, P proves $g,~h$ both have $deg \leq d$, but instead of doing $2 \cdot (d+2)$ queries ($d+2$ for $g$, and $d+2$ for $h$), it is done in $d+2$ queries (for $f$).
 91So we halved the number of queries.
 92
 93
 94\subsection{FRI}
 95Both P and V have oracle access to function $f$.
 96
 97V wants to test if $f$ is polynomial with $deg(f) \leq d$.
 98
 99Let $f_0(x)=f(x)$.
100
101Each polynomial $f(x)$ of degree that is a power of $2$, can be written as
102$$f(x) = f^L(x^2) + x f^R(x^2)$$
103for some polynomials $f^L,~f^R$ of degree $\frac{deg(f)}{2}$, each one containing the even and odd degree coefficients as follows:
104
105% $f^L(x)$ is built from the even degree coefficients divided by $x$, and $f^R(x)$ from the odd degree coefficients divided by $x$.
106
107$$f^L(x)= \sum_0^{\frac{d+1}{2}-1} c_{2i} x^i ,~~ f^R(x)= \sum_0^{\frac{d+1}{2}-1} c_{2i+1} x^i$$
108
109eg. for $f(x)=x^4+x^3+x^2+x+1$,
110\begin{align*}
111	\begin{rcases}
112	f^L(x)=x^2+x+1\\
113	f^R(x)=x+1
114	\end{rcases}
115	~f(x) = f^L(x^2) &+ x \cdot f^R(x^2)\\
116	= (x^2)^2 + (x^2) + 1 &+ x \cdot ((x^2) + 1)\\
117	= x^4 + x^2 + 1 &+ x^3 + x
118\end{align*}
119
120% \begin{enumerate}
121%         \item V sends to P some $\alpha_0 \in \mathbb{F}$.
122%                 Let
123%                 \begin{equation}\tag{$A_0$}
124%                         f_0(x) = f_0^L(x^2) + x f_0^R(x^2)
125%                 \end{equation}
126%         \item P sends
127%                 \begin{equation}\tag{$B_0$}
128%                         f_1(x) = f_0^L(x) + \alpha_0 f_0^R(x)
129%                 \end{equation}
130%                 to V.
131% 
132%                 (remember that "sends" in IOP model is that P commits to it)
133%         \item V sends to P some $\alpha_1 \in \mathbb{F}$.
134%                 Let
135%                 \begin{equation}\tag{$A_1$}
136%                         f_1(x) = f_1^L(x^2) + x f_1^R(x^2)
137%                 \end{equation}
138%         \item P sends
139%                 \begin{equation}\tag{$B_1$}
140%                         f_2(x) = f_1^L(x) + \alpha_1 f_1^R(x)
141%                 \end{equation}
142%                 to V.
143%         \item Keep repeating the process, eg. let
144%                 \begin{equation}\tag{$A_2$}
145%                         f_2(x) = f_2^L(x^2) + x f_2^R(x^2)
146%                 \end{equation}
147%                 until $f_i^L,~ f_i^R$ are constant (degree 0 polynomials).
148%         \item Once $f_i^L,~ f_i^R$ are constant, P sends them to V.
149% \end{enumerate}
150% 
151% Notice that at each step, $deg(f_i)$ halves.
152
153
154\vspace{30px}
155
156\paragraph{Proof generation}
157P starts from $f(x)$, and for $i=0$ sets $f_0(x)=f(x)$.
158
159\begin{enumerate}
160	\item $\forall~i \in \{0, log(d)\}$, with $d = deg~f(x)$,\\
161		P computes $f_i^L(x),~ f_i^R(x)$ for which
162		\begin{equation}\tag{eq. $A_i$}
163			f_i(x) = f_i^L(x^2) + x f_i^R(x^2)
164		\end{equation}
165		holds.
166	\item V sends challenge $\alpha_i$
167	\item P commits to the random linear combination $f_{i+1}$, for
168		\begin{equation}\tag{eq. $B_i$}
169		f_{i+1}(x) = f_i^L(x) + \alpha_i f_i^R(x)
170	\end{equation}
171	\item P sets $f_i(x) := f_{i+1}(x)$ and starts again the iteration.
172\end{enumerate}
173Notice that at each step, $deg(f_i)$ halves.
174
175This is done until the last step, where $f_i^L(x),~ f_i^R(x)$ are constant (degree 0 polynomials). For which P does not commit but gives their values directly to V.
176
177\paragraph{Data sent from P to V}
178\begin{itemize}
179	\item[] Commitments: $\{Comm(f_i)\}_0^{log(d)}$\\
180		{\scriptsize eg. $\{Comm(f_0),~ Comm(f_1),~ Comm(f_2),~ ...,~ Comm(f_{log(d)})\}$ }
181	\item[] Openings: $\{ f_i(z^{2^i}),~f_i(-(z^{2^i})) \}_0^{log(d)}$\\
182		for a challenge $z \in \mathbb{F}$ set by V\\
183		{\scriptsize eg. $f_0(z),~ f_0(-z),~ f_1(z^2),~ f_1(-z^2),~ f_2(z^4),~ f_2(-z^4),~ f_3(z^8),~ f_3(-z^8),~ \ldots$}
184	\item[] Constant values of last iteration: $\{f_k^L,~f_k^R\}$, for $k=log(d)$
185\end{itemize}
186
187\paragraph{Verification}
188
189V receives:
190\begin{align*}
191	\text{Commitments:}~ &Comm(f_i),~ \forall i \in \{0, log(d)\}\\
192	\text{Openings:}~ &\{o_i, o_i'\}=\{ f_i(z^{2^i}),~f_i(-(z^{2^i})) \},~ \forall i \in \{0, log(d)\}\\
193	\text{Constant vals:}~ &\{f_k^L,~f_k^R\}
194\end{align*}
195
196\vspace{20px}
197
198For all $i \in \{0, log(d)\}$, V knows the openings at $z^{2^i}$ and $-(z^{2^i})$ for $Comm(f_i(x))$, which are $o_i=f_i(z^{2^i})$ and $o_i'=f_i(-(z^{2^i}))$ respectively.
199
200V, from (eq. $A_i$), knows that
201$$f_i(x)=f_i^L(x^2) + x f_i^R(x^2)$$
202should hold, thus
203$$f_i(z)=f_i^L(z^2) + z f_i^R(z^2)$$
204where $f_i(z)$ is known, but $f_i^L(z^2),~f_i^R(z^2)$ are unknown.
205But, V also knows the value for $f_i(-z)$, which can be represented as
206$$f_i(-z)=f_i^L(z^2) - z f_i^R(z^2)$$
207(note that when replacing $x$ by $-z$, it loses the negative in the power, not in the linear combination).
208
209Thus, we have the system of independent linear equations
210\begin{align*} % TODO add braces on left
211	f_i(z)&=f_i^L(z^2) + z f_i^R(z^2)\\
212	f_i(-z)&=f_i^L(z^2) - z f_i^R(z^2)
213\end{align*}
214for which V will find the value of $f_i^L(z^{2^i}),~f_i^R(z^{2^i})$.
215Equivalently it can be represented by
216$$
217\begin{pmatrix}
218	1 & z\\
219	1 & -z
220\end{pmatrix}
221\begin{pmatrix}
222	f_i^L(z^2)\\
223	f_i^R(z^2)
224\end{pmatrix}
225=
226\begin{pmatrix}
227	f_i(z)\\
228	f_i(-z)
229\end{pmatrix}
230$$
231where V will find the values of $f_i^L(z^{2^i}),~f_i^R(z^{2^i})$ being
232\begin{align*}
233	f_i^L(z^{2^i})=\frac{f_i(z) + f_i(-z)}{2}\\
234	f_i^R(z^{2^i})=\frac{f_i(z) - f_i(-z)}{2z}\\
235\end{align*}
236
237Once, V has computed $f_i^L(z^{2^i}),~f_i^R(z^{2^i})$, can use them to compute the linear combination of
238$$
239f_{i+1}(z^2) = f_i^L(z^2) + \alpha_i f_i^R(z^2)
240$$
241obtaining then $f_{i+1}(z^2)$. This comes from (eq. $B_i$).
242
243Now, V checks that the obtained $f_{i+1}(z^2)$ is equal to the received opening $o_{i+1}=f_{i+1}(z^2)$ from the commitment done by P.
244V checks also the commitment of $Comm(f_{i+1}(x))$ for the opening $o_{i+1}=f_{i+1}(z^2)$.\\
245If the checks pass, V is convinced that $f_1(x)$ was committed honestly.
246
247Now, sets $i := i+1$ and starts a new iteration.
248
249For the last iteration, V checks that the obtained $f_i^L(z^{2^i}),~f_i^R(z^{2^i})$ are equal to the constant values $\{f_k^L,~f_k^R\}$ received from P.
250
251\vspace{10px}
252It needs $log(d)$ iterations, and the number of queries (commitments + openings sent and verified) needed is $2 \cdot log(d)$.
253
254\section{FRI as polynomial commitment}
255\emph{[WIP. Unfinished document]}
256
257
258\bibliography{paper-notes.bib}
259\bibliographystyle{unsrt}
260
261\end{document}