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% \usepackage{pgf-umlsd} % diagrams
 11
 12
 13% prevent warnings of underfull \hbox:
 14\usepackage{etoolbox}
 15\apptocmd{\sloppy}{\hbadness 4000\relax}{}{}
 16
 17\theoremstyle{definition}
 18\newtheorem{definition}{Def}[section]
 19\newtheorem{theorem}[definition]{Thm}
 20
 21% custom lemma environment to set custom numbers
 22\newtheorem{innerlemma}{Lemma}
 23\newenvironment{lemma}[1]
 24{\renewcommand\theinnerlemma{#1}\innerlemma}
 25{\endinnerlemma}
 26
 27
 28\title{Notes on FRI and STIR}
 29\author{arnaucube}
 30\date{February 2023}
 31
 32\begin{document}
 33
 34\maketitle
 35
 36\begin{abstract}
 37	Notes taken from \href{https://sites.google.com/site/vincenzoiovinoit/}{Vincenzo Iovino} \cite{vincenzoiovino} explanations about FRI \cite{fri}, \cite{cryptoeprint:2022/1216}, \cite{cryptoeprint:2019/1020}.
 38
 39	These notes are for self-consumption, are not complete, don't include all the steps neither all the proofs.
 40
 41	An implementation of FRI can be found at\\ \href{https://github.com/arnaucube/fri-commitment}{https://github.com/arnaucube/fri-commitment} \cite{fri-impl}.
 42
 43	Update(2024-03-22): notes on STIR \cite{cryptoeprint:2024/390} from explanations by \href{https://hecmas.github.io/}{Héctor Masip Ardevol} \cite{hectormasipardevol}.
 44\end{abstract}
 45
 46\tableofcontents
 47
 48\section{Preliminaries}
 49\subsection{General degree d test}
 50
 51Query at points $\{ x_i \}_0^{d+1},~z$ (with rand $z \overset{R}{\in} \mathbb{F}$).
 52Interpolate $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$.
 53
 54V checks $p(z)=f(z)$, if the check passes, then V is convinced with high probability.
 55
 56This needs $d+2$ queries, is linear, $\mathcal{O}(n)$. With FRI we will have the test in $\mathcal{O}(\log{}d)$.
 57
 58\section{FRI protocol}
 59Allows to test if a function $f$ is a poly of degree $\leq d$ in $\mathcal{O}(\log{}d)$.
 60
 61Note: "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)$.
 62
 63\subsection{Intuition}
 64V wants to check that two functions $g,~h$ are both polynomials of degree $\leq d$.
 65
 66Consider the following protocol:
 67
 68\begin{enumerate}
 69	\item V sends $\alpha \in \mathbb{F}$ to P.
 70	\item P sends $f(x)=g(x) + \alpha h(x)$ to V.
 71	\item V queries $f(r), ~g(r), ~h(r)$ for rand $r \in \mathbb{F}$.
 72	\item V checks $f(r)=g(r) + \alpha h(r)$. (Schwartz-Zippel lema).
 73		If holds, V can be certain that $f(x)=g(x)+ \alpha h(x)$.
 74	\item P proves that $deg(f) \leq d$. 
 75	\item If V is convinced that $deg(f) \leq d$, V believes that both $g, h$ have $deg \leq d$.
 76\end{enumerate}
 77
 78%/// TODO tabulate this next lines
 79With high probability, $\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
 80
 81Let $g(x)=a \cdot x^{d+1}, ~~ h(x)=b \cdot x^{d+1}$, and set $f(x) = g(x) + \alpha h(x)$.
 82Imagine 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.
 83%///
 84
 85\quad
 86
 87Here, 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$).
 88So we halved the number of queries.
 89
 90
 91\subsection{FRI-LDT}\label{sec:fri-ldt}
 92FRI low degree testing.\\
 93Both P and V have oracle access to function $f$.
 94
 95V wants to test if $f$ is polynomial with $deg(f) \leq d$.
 96
 97Let $f_0(x)=f(x)$.
 98
 99Each polynomial $f(x)$ of degree that is a power of $2$, can be written as
100$$f(x) = f^L(x^2) + x f^R(x^2)$$
101for some polynomials $f^L,~f^R$ of degree $\frac{deg(f)}{2}$, each one containing the even and odd degree coefficients as follows:
102
103% $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$.
104
105$$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$$
106
107eg. for $f(x)=x^4+x^3+x^2+x+1$,
108\begin{align*}
109	\begin{rcases}
110	f^L(x)=x^2+x+1\\
111	f^R(x)=x+1
112	\end{rcases}
113	~f(x) = f^L(x^2) &+ x \cdot f^R(x^2)\\
114	= (x^2)^2 + (x^2) + 1 &+ x \cdot ((x^2) + 1)\\
115	= x^4 + x^2 + 1 &+ x^3 + x
116\end{align*}
117
118% \begin{enumerate}
119%         \item V sends to P some $\alpha_0 \in \mathbb{F}$.
120%                 Let
121%                 \begin{equation}\tag{$A_0$}
122%                         f_0(x) = f_0^L(x^2) + x f_0^R(x^2)
123%                 \end{equation}
124%         \item P sends
125%                 \begin{equation}\tag{$B_0$}
126%                         f_1(x) = f_0^L(x) + \alpha_0 f_0^R(x)
127%                 \end{equation}
128%                 to V.
129% 
130%                 (remember that "sends" in IOP model is that P commits to it)
131%         \item V sends to P some $\alpha_1 \in \mathbb{F}$.
132%                 Let
133%                 \begin{equation}\tag{$A_1$}
134%                         f_1(x) = f_1^L(x^2) + x f_1^R(x^2)
135%                 \end{equation}
136%         \item P sends
137%                 \begin{equation}\tag{$B_1$}
138%                         f_2(x) = f_1^L(x) + \alpha_1 f_1^R(x)
139%                 \end{equation}
140%                 to V.
141%         \item Keep repeating the process, eg. let
142%                 \begin{equation}\tag{$A_2$}
143%                         f_2(x) = f_2^L(x^2) + x f_2^R(x^2)
144%                 \end{equation}
145%                 until $f_i^L,~ f_i^R$ are constant (degree 0 polynomials).
146%         \item Once $f_i^L,~ f_i^R$ are constant, P sends them to V.
147% \end{enumerate}
148% 
149% Notice that at each step, $deg(f_i)$ halves.
150
151
152\vspace{30px}
153
154\paragraph{Proof generation}
155
156\emph{(Commitment phase)}
157P starts from $f(x)$, and for $i=0$ sets $f_0(x)=f(x)$.
158\begin{enumerate}
159	\item $\forall~i \in \{0, log(d)\}$, with $d = deg~f(x)$,\\
160		P computes $f_i^L(x),~ f_i^R(x)$ for which
161		\begin{equation}\tag{eq. $A_i$}
162			f_i(x) = f_i^L(x^2) + x f_i^R(x^2)
163		\end{equation}
164		holds.
165	\item V sends challenge $\alpha_i \in \mathbb{F}$
166	\item P commits to the random linear combination $f_{i+1}$, for
167		\begin{equation}\tag{eq. $B_i$}
168		f_{i+1}(x) = f_i^L(x) + \alpha_i f_i^R(x)
169	\end{equation}
170	\item P sets $f_i(x) := f_{i+1}(x)$ and starts again the iteration.
171\end{enumerate}
172
173Note on step 3: when we say "commits", this means that the prover P evaluates $f_{i+1}(x)$ at the $(\rho^{-1} \cdot d)$-sized evaluation
174domain $D$ (ie. $f_{i+1}(x) |_D$), and constructs a merkle tree with the
175evaluations as leaves.
176
177\vspace{0.5cm}
178Notice that at each step, $deg(f_i)$ halves with respect to $deg(f_{i-1}$).
179
180This 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.
181
182\emph{(Query phase)}
183P would receive a challenge $z \in D$ set by V (where $D$ is the evaluation
184domain, $D \subset \mathbb{F}$), and P would open the commitments at $\{z^{2^i}, -z^{2^i}\}$ for each step $i$.
185(Recall, "opening" means that would provide a proof (MerkleProof) of it).
186
187\paragraph{Data sent from P to V}
188\begin{itemize}
189	\item[] Commitments: $\{Comm(f_i)\}_0^{log(d)}$\\
190		{\scriptsize eg. $\{Comm(f_0),~ Comm(f_1),~ Comm(f_2),~ ...,~ Comm(f_{log(d)})\}$ }
191	\item[] Openings: $\{ f_i(z^{2^i}),~f_i(-(z^{2^i})) \}_0^{log(d)}$\\
192		for a challenge $z \in D$ set by V\\
193		{\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$}
194	\item[] Constant values of last iteration: $\{f_k^L,~f_k^R\}$, for $k=log(d)$
195\end{itemize}
196
197% \begin{figure}[htp]
198% \centering
199% \begin{footnotesize}
200% \begin{sequencediagram}
201%     \newinst[0]{p}{Prover}
202%     \newinst[5]{v}{Verifier}
203% 
204%     \mess{p}{$\{Comm(f_i)\}_0^{log(d)},~ \{f_i(z^{2^i}),~f_i(-(z^{2^i})) \}_0^{log(d)},~ \{f_k^L,~ f_k^R\}$}{v}
205% 
206% \end{sequencediagram}
207% \end{footnotesize}
208% \caption[FRI-LDT]{sketch of the FRI-LDT flow}
209% \label{fig:fri-ldt}
210% \end{figure}
211
212
213\paragraph{Verification}
214
215V receives:
216\begin{align*}
217	\text{Commitments:}~ &Comm(f_i),~ \forall i \in \{0, log(d)\}\\
218	\text{Openings:}~ &\{o_i, o_i'\}=\{ f_i(z^{2^i}),~f_i(-(z^{2^i})) \},~ \forall i \in \{0, log(d)\}\\
219	\text{Constant vals:}~ &\{f_k^L,~f_k^R\}
220\end{align*}
221
222\vspace{20px}
223
224For all $i \in \{0, log(d)\}$, V knows the openings at $z^{2^i}$ and $-(z^{2^i})$ for\\
225$Comm(f_i(x))$, which are $o_i=f_i(z^{2^i})$ and $o_i'=f_i(-(z^{2^i}))$ respectively.
226
227V, from (eq. $A_i$), knows that
228$$f_i(x)=f_i^L(x^2) + x f_i^R(x^2)$$
229should hold, thus
230$$f_i(z)=f_i^L(z^2) + z f_i^R(z^2)$$
231where $f_i(z)$ is known, but $f_i^L(z^2),~f_i^R(z^2)$ are unknown.
232But, V also knows the value for $f_i(-z)$, which can be represented as
233$$f_i(-z)=f_i^L(z^2) - z f_i^R(z^2)$$
234(note that when replacing $x$ by $-z$, it loses the negative in the power, not in the linear combination).
235
236Thus, we have the system of independent linear equations
237\begin{align*} % TODO add braces on left
238	f_i(z)&=f_i^L(z^2) + z f_i^R(z^2)\\
239	f_i(-z)&=f_i^L(z^2) - z f_i^R(z^2)
240\end{align*}
241for which V will find the value of $f_i^L(z^{2^i}),~f_i^R(z^{2^i})$.
242Equivalently it can be represented by
243$$
244\begin{pmatrix}
245	1 & z\\
246	1 & -z
247\end{pmatrix}
248\begin{pmatrix}
249	f_i^L(z^2)\\
250	f_i^R(z^2)
251\end{pmatrix}
252=
253\begin{pmatrix}
254	f_i(z)\\
255	f_i(-z)
256\end{pmatrix}
257$$
258where V will find the values of $f_i^L(z^{2^i}),~f_i^R(z^{2^i})$ being
259\begin{align*}
260	f_i^L(z^{2^i})=\frac{f_i(z) + f_i(-z)}{2}\\
261	f_i^R(z^{2^i})=\frac{f_i(z) - f_i(-z)}{2z}\\
262\end{align*}
263
264Once, V has computed $f_i^L(z^{2^i}),~f_i^R(z^{2^i})$, can use them to compute the linear combination of
265$$
266f_{i+1}(z^{2^i}) = f_i^L(z^{2^i}) + \alpha_i f_i^R(z^{2^i})
267$$
268obtaining then $f_{i+1}(z^{2^i})$. This comes from (eq. $B_i$).
269
270Now, V checks that the obtained $f_{i+1}(z^{2^i})$ is equal to the received opening $o_{i+1}=f_{i+1}(z^{2^i})$ from the commitment done by P.
271V checks also the commitment of $Comm(f_{i+1}(x))$ for the opening $o_{i+1}=f_{i+1}(z^{2^i})$.\\
272If the checks pass, V is convinced that $f_1(x)$ was committed honestly.
273
274Now, sets $i := i+1$ and starts a new iteration.
275
276For 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.
277
278\vspace{10px}
279It needs $log(d)$ iterations, and the number of queries (commitments + openings sent and verified) needed is $2 \cdot log(d)$.
280
281\subsection{Parameters}
282
283P commits to $f_i$ restricted to a subfield $F_0 \subset \mathbb{F}$.
284Let $0<\rho<1$ be the \emph{rate} of the code, such that
285$$|F_0| = \rho^{-1} \cdot d$$
286
287\begin{theorem}
288	For $\delta \in (0, 1-\sqrt{\rho})$, we have that if V accepts, then w.v.h.p. (with very high probability) $\Delta(f_0,~ p^d) \leq \delta$.
289\end{theorem}
290
291\section{FRI as polynomial commitment scheme}
292This section overviews the trick from \cite{cryptoeprint:2019/1020} to convert FRI into a polynomial commitment.
293
294Want to check that the evaluation of $f(x)$ at $r$ is $f(r)$, for $r \notin D, r
295\in^R \mathbb{F}$; which is equivalent to proving that $\exists ~Q \in \mathbb{F}[x]$ with $deg(Q)=d-1$, such that
296
297$$
298f(x)-f(r) = Q(x) \cdot (x-r)
299$$
300
301note that $f(x)-f(r)$ evaluated at $r$ is $0$, so $(x-r) | (f(x)-f(r))$, in other words
302$(f(x)-f(r))$ is a multiple of $(x-r)$ for a polynomial $Q(x)$.
303
304Let us define $g(x) = \frac{f(x)-f(r)}{x-r}$.
305
306Prover uses FRI-LDT \ref{sec:fri-ldt} to commit to $g(x)$, and then prove w.v.h.p that $deg(g) \leq d-1$ ($\Longleftrightarrow \Delta(g,~ p^{d-1} \leq \delta$).
307
308Prover was already proving that $deg(f) \leq d$.
309
310Now, the missing thing to prove is that $g(x)$ has the right shape. We can relate $g$ to $f$ as follows:
311V does the normal FRI-LDT, but in addition, at the first iteration:
312V has $f(z)$ and $g(z)$ openings, so can verify
313$$g(z) = (f(z)-f(r))\cdot (z-r)^{-1}$$
314
315
316\section{STIR (main idea)}
317\emph{Update from 2024-03-22, notes from Héctor Masip Ardevol\\
318(\href{https://hecmas.github.io/}{https://hecmas.github.io}) explanations.}
319
320\vspace{0.3cm}
321Let $p \in \mathbb{F}[x]^{<n}$.
322
323In FRI we decompose $p(x)$ as
324$$p(x) = p_e(x^2) + x \cdot p_o(x^2)$$
325with $p_e, p_o \in \mathbb{F}[x]^{<n}$ containing the even and odd powers respectively.
326
327The next FRI polynomial is
328$$p_1(x) = p_e(x) + \alpha p_o(x)$$
329for $\alpha \in^R \mathbb{F}$.
330
331In STIR, this would be $q(x)=x^2$,
332$$Q(z,y) = p_e(y) + z \cdot p_o(y)$$
333and then, $p(x) = Q(x, q(x))$. And $Q$ fulfills the degree from Fact 4.6 from the STIR paper.
334
335We can generalize to a $q$ with bigger degree, or with another shape, and adapting $Q$ on the choice of $q$.
336
337eg. for $q(x)=x^3$, we can take
338$$Q(z,y) = p_1(y) + z \cdot p_2(y) + z^2 \cdot p_3(y)$$
339with $p_1, p_2, p_3 \in \mathbb{F}[x]^{<n/3}$ with coefficients taken every 3 powers alternating.
340
341\bibliography{paper-notes.bib}
342\bibliographystyle{unsrt}
343
344\end{document}