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\usepackage{pgf-umlsd} % diagrams
 12% message between threads
 13% Example:
 14% \bloodymess[delay]{sender}{message content}{receiver}{DIR}{start note}{end note}
 15\newcommand{\bloodymess}[7][0]{
 16  \stepcounter{seqlevel}
 17  \path
 18  (#2)+(0,-\theseqlevel*\unitfactor-0.7*\unitfactor) node (mess from) {};
 19  \addtocounter{seqlevel}{#1}
 20  \path
 21  (#4)+(0,-\theseqlevel*\unitfactor-0.7*\unitfactor) node (mess to) {};
 22  \draw[->,>=angle 60] (mess from) -- (mess to) node[midway, above]
 23  {#3};
 24
 25  \if R#5
 26  \node (\detokenize{#3} from) at (mess from) {\llap{#6~}};
 27  \node (\detokenize{#3} to) at (mess to) {\rlap{~#7}};
 28  \else\if L#5
 29  \node (\detokenize{#3} from) at (mess from) {\rlap{~#6}};
 30  \node (\detokenize{#3} to) at (mess to) {\llap{#7~}};
 31       \else
 32       \node (\detokenize{#3} from) at (mess from) {#6};
 33       \node (\detokenize{#3} to) at (mess to) {#7};
 34       \fi
 35  \fi
 36}
 37
 38% prevent warnings of underfull \hbox:
 39\usepackage{etoolbox}
 40\apptocmd{\sloppy}{\hbadness 4000\relax}{}{}
 41
 42\theoremstyle{definition}
 43\newtheorem{definition}{Def}[section]
 44\newtheorem{theorem}[definition]{Thm}
 45
 46% custom lemma environment to set custom numbers
 47\newtheorem{innerlemma}{Lemma}
 48\newenvironment{lemma}[1]
 49{\renewcommand\theinnerlemma{#1}\innerlemma}
 50{\endinnerlemma}
 51
 52
 53\title{Notes on Nova}
 54\author{arnaucube}
 55\date{February 2023}
 56
 57\begin{document}
 58
 59\maketitle
 60
 61\begin{abstract}
 62	Notes taken while reading Nova \cite{cryptoeprint:2021/370} paper.
 63
 64	Usually while reading papers I take handwritten notes, this document contains some of them re-written to $LaTeX$.
 65
 66	The notes are not complete, don't include all the steps neither all the proofs.
 67\end{abstract}
 68
 69\tableofcontents
 70
 71\section{NIFS}
 72
 73\subsection{R1CS modification}
 74
 75Want: merge 2 instances of R1CS with the same matrices into a single one. Each instance has $z_i = (W_i,~ x_i)$ (public witness, private values resp.).
 76
 77\paragraph{traditional R1CS}
 78Merged instance with $z=z_1 + r z_2$, for rand $r$. But, since R1CS is not linear $\longrightarrow$ can not apply.
 79
 80eg.
 81\begin{align*}
 82	Az \circ Bz &= A(z_1 + r z_2) \circ B (z_1 + r z_2)\\
 83	&= A z_1 \circ B z_1 + r(A z_1 \circ B z_2 + A z_2 \circ B z_1) + r^2 (A z_2 \circ B z_2)\\
 84	&\neq Cz
 85\end{align*}
 86
 87$\longrightarrow$ introduce error vector $E \in \mathbb{F}^m$, which absorbs the cross-temrs generated by folding.
 88
 89$\longrightarrow$ introduce scalar $u$, which absorbs an extra factor of $r$ in $C z_1 + r^2 C z_2$ and in $z=(W, x, 1+r\cdot 1)$.
 90
 91\paragraph{Relaxed R1CS}
 92\begin{align*}
 93	&u=u_1+r u_2\\
 94	&E=E_1 + r (A z_1 \circ B z_2 + A z_2 \circ B z_1 - u_1 C z_2 - u_2 C z_1) + r^2 E_2\\
 95	&Az \circ Bz = uCz + E,~~ with~ z=(W,~x,~u)
 96\end{align*}
 97where R1CS set $E=0,~u=1$.
 98
 99\begin{align*}
100	Az \circ Bz &= A z_1 \circ B z_1 + r(A z_1 \circ B z_2 + A z_2 \circ B z_1) + r^2 (A z_2 \circ B z_2)\\
101		    &= (u_1 C z_1 + E_1) + r (A z_1 \circ B z_2 + A z_2 \circ B z_1) + r^2 (u_2 C z_2 + E_2)\\
102		    &= u_1 C z_1 + \underbrace{E_1 + r(A z_1 \circ B z_2 + A z_2 \circ B z_1) + r^2 E_2}_\text{E} + r^1 u_2 C z_2\\
103		    &= u_1 C z_1 + r^2 u_2 C z_2 + E\\
104		    &= (u_1 + r u_2) \cdot C \cdot (z_1 + r z_2) + E\\
105		    &= uCz + E
106\end{align*}
107
108For R1CS matrices $(A,~B,~C)$, the folded witness $W$ is a satisfying witness for the folded instance $(E,~u,~x)$.
109
110
111
112\vspace{20px}
113Problem: not non-trivial, and not zero-knowledge. Solution: use polynomial commitment with hiding, binding, succintness and additively homomorphic properties.
114
115\paragraph{Committed Relaxed R1CS}
116Instance for a Committed Relaxed R1CS\\
117$(\overline{E}, u, \overline{W}, x)$, satisfyied by a witness $(E, r_E, W, r_W)$ such that
118\begin{align*}
119	&\overline{E} = Com(E, r_E)\\
120	&\overline{W} = Com(E, r_W)\\
121	&Az \circ Bz = uCz+E,~~ where~z=(W, x, u)
122\end{align*}
123
124
125\subsection{Folding scheme for committed relaxed R1CS}
126
127V and P take two \emph{committed relaxed R1CS} instances
128\begin{align*}
129	\varphi_1&=(\overline{E}_1, u_1, \overline{W}_1, x_1)\\
130	\varphi_2&=(\overline{E}_2, u_2, \overline{W}_2, x_2)
131\end{align*}
132
133P additionally takes witnesses to both instances
134\begin{align*}
135	(E_1, r_{E_1}, W_1, r_{W_1})\\
136	(E_2, r_{E_2}, W_2, r_{W_2})
137\end{align*}
138
139Let $Z_1 = (W_1, x_1, u_1)$ and $Z_2 = (W_2, x_2, u_2)$.
140
141% \paragraph{Protocol}
142\begin{enumerate}
143	\item P send $\overline{T} = Com(T, r_T)$,\\
144		where $T=A z_1 \circ B z_1 + A z_2 \circ B z_2 - u_1 C z_2 - u_2 C z_2$\\
145		and rand $r_T \in \mathbb{F}$
146	\item V sample random challenge $r \in \mathbb{F}$
147	\item V, P output the folded instance $\varphi = (\overline{E}, u, \overline{W}, x)$
148		\begin{align*}
149			&\overline{E}=\overline{E}_1 + r \overline{T} + r^2 \overline{E}_2\\
150			&u = u_1 + r u_2\\
151			&\overline{W} = \overline{W}_1 + r \overline{W}_2\\
152			&x = x_1 + r x_2
153		\end{align*}
154	\item P outputs the folded witness $(E, r_E, W, r_W)$
155		\begin{align*}
156			&E = E_1 + r T + r^2 E_2\\
157			&r_E = r_{E_1} + r \cdot r_T + r^2 r_{E_2}\\
158			&W=W_1 + r W_2\\
159			&r_W = r_{W_1} + r \cdot r_{W_2}
160		\end{align*}
161\end{enumerate}
162
163P will proof that knows the valid witness $(E, r_E, W, r_W)$ for the committed relaxed R1CS without revealing its value.
164
165\begin{center}
166	\begin{sequencediagram}
167		\newinst[1]{p}{Prover}
168		\newinst[3]{v}{Verifier}
169
170		\bloodymess[1]{p}{$\overline{T}$}{v}{R}{
171			\shortstack{
172				$T=A z_1 \circ B z_1 + A z_2 \circ B z_2 - u_1 C z_2 - u_2 C z_2$\\
173				$\overline{T}=Commit(T, r_T)$
174			}
175		}{
176			\shortstack{
177				$r \in^R \mathbb{F}_p$\\
178				$\overline{E} = \overline{E}_1 + r \overline{T} + r^2 \overline{E}_2$\\
179				$u= u_1 + r u_2$\\
180				$\overline{W} = \overline{W}_1 + r \overline{W}_2$\\
181				$\overline{x} = \overline{x}_1 + r \overline{x}_2$\\
182				$\varphi=(\overline{E}, u, \overline{W}, x)$
183			}
184		}
185		\bloodymess[1]{v}{$r$}{p}{L}{}{
186			\shortstack{
187				$E = E_1 + r T + r^2 E_2$\\
188				$u= u_1 + r u_2$\\
189				$W = W_1 + r W_2$\\
190				$r_{W} = r_{W_1} + r r_{W_2}$\\
191				$(E, r_E, W, r_W)$
192			}
193		}
194	\end{sequencediagram}
195\end{center}
196
197
198The previous protocol achieves non-interactivity via Fiat-Shamir transform, obtaining a \emph{Non-Interactive Folding Scheme for Committed Relaxed R1CS}.
199
200Note: the paper later uses $\mathsf{u}_i,~ \mathsf{U}_i$ for the two inputed $\varphi_1,~ \varphi_2$, and later $\mathsf{u}_{i+1}$ for the outputed $\varphi$. Also, the paper later uses $\mathsf{w},~ \mathsf{W}$ to refer to the witnesses of two folded instances (eg. $\mathsf{w}=(E, r_E, W, r_W)$).
201
202\section{Nova}
203IVC (Incremental Verifiable Computation) scheme for a non-interactive folding scheme.
204
205\subsection{IVC proofs}
206
207Allows prover to show $z_n = F^{(n)}(z_0)$, for some count $n$, initial input $z_0$, and output $z_n$.\\
208$F$: program function (polynomial-time computable)\\
209$F'$: augmented function, invokes $F$ and additionally performs fold-related stuff.
210
211\vspace{0.5cm}
212Two committed relaxed R1CS instances:\\
213$\mathsf{U}_i$: represents the correct execution of invocations $1, \ldots, i-1$ of $F'$\\
214$\mathsf{u}_i$: represents the correct execution of invocations $i$ of $F'$
215
216\paragraph{Simplified version of $F'$ for intuition}
217\vspace{0.5cm}
218$F'$ performs two tasks:
219\begin{enumerate}[i.]
220	\item execute a step of the incremental computation:
221		instance $\mathsf{u}_i$ contains $z_i$, used to output $z_{i+1}=F(z_i)$
222	\item invokes the verifier of the non-interactive folding scheme to fold the task of checking $\mathsf{u}_i$ and $\mathsf{U}_i$ into the task of checking a single instance $\mathsf{U}_{i+1}$
223\end{enumerate}
224
225\vspace{0.5cm}
226$F'$ proves that:
227\begin{enumerate}
228	\item $\exists ( (i, z_0, z_i, \mathsf{u}_i, \mathsf{U}_i), \mathsf{U}_{i+1}, \overline{T})$ such that
229	\begin{enumerate}[i.]
230		\item $\mathsf{u}_i.x = H(vk, i, z_0, z_i, \mathsf{U}_i)$
231		\item $h_{i+1} = H(vk, i+1, z_0, F(z_i), \mathsf{U}_{i+1})$
232		\item $\mathsf{U}_{i+1} = NIFS.V(vk, \mathsf{U}_i, \mathsf{u}_i, \overline{T})$
233	\end{enumerate}
234\item $F'$ outputs $h_{i+1}$
235\end{enumerate}
236
237
238$F'$ is described as follows:\\
239$F'(vk, \mathsf{U}_i, \mathsf{u}_i, (i, z_0, z_i), w_i, \overline{T}) \rightarrow x$:\\
240if $i=0$, output $H(vk, 1, z_0, F(z_0, w_i), \mathsf{u}_{\bot})$\\
241otherwise
242\begin{enumerate}
243	\item check $\mathsf{u}_i.x = H(vk, i, z_0, z_i, \mathsf{U}_i)$
244	\item check $(\mathsf{u}_i.\overline{E}, \mathsf{u}_i.u) = (\mathsf{u}_{\bot}.\overline{E}, 1)$
245	\item compute $\mathsf{U}_{i+1} \leftarrow NIFS.V(vk, U, u, \overline{T})$
246	\item output $H(vk, i+1, z_0, F(z_i, w_i), \mathsf{U}_{i+1})$
247\end{enumerate}
248
249% TODO add diagram
250
251\paragraph{IVC Proof}
252iteration $i+1$: prover runs $F'$ and computes $\mathsf{u}_{i+1},~ \mathsf{U}_{i+1}$, with corresponding witnesses $\mathsf{w}_{i+1},~ \mathsf{W}_{i+1}$.
253$(\mathsf{u}_{i+1},~ \mathsf{U}_{i+1})$ attest correctness of $i+1$ invocations of $F'$, the IVC proof is $\pi_{i+1} = ( (\mathsf{U}_{i+1}, \mathsf{W}_{i+1}), (\mathsf{u}_{i+1}, \mathsf{w}_{i+1}))$.
254
255
256\vspace{0.5cm}
257
258\underline{$P(pk, (i, z_0, z_i), \mathsf{w}_i, \pi_i) \rightarrow \pi_{i+1}$}:\\
259Parse $\pi_i = ( (\mathsf{U}_i, \mathsf{W}_i), (\mathsf{u}_i, \mathsf{w}_i))$, then
260\begin{enumerate}
261	\item if $i=0$: $(\mathsf{U}_{i+1}, \mathsf{W}_{i+1}, \overline{T}) \leftarrow (\mathsf{u}_{\perp}, \mathsf{w}_{\perp}, \mathsf{u}_{\perp}.{\overline{E}})$\\
262		otherwise: $(\mathsf{U}_{i+1}, \mathsf{W}_{i+1}, \overline{T}) \leftarrow NIFS.P(pk, (\mathsf{U}_i, \mathsf{W}_i), (\mathsf{u}_i, \mathsf{w}_i))$
263	\item compute $(\mathsf{u}_{i+1}, \mathsf{w}_{i+1}) \leftarrow trace(F', (vk, \mathsf{U}_i, \mathsf{u}_i, (i, z_0, z_i), \mathsf{w}_i, \overline{T}))$
264	\item output $\pi_{i+1} \leftarrow ((\mathsf{U}_{i+1}, \mathsf{W}_{i+1}), (\mathsf{u}_{i+1}, \mathsf{w}_{i+1}))$
265\end{enumerate}
266
267\underline{$V(vk, (i, z_0, z_i), \pi_i) \rightarrow \{0,1\}$}:
268if $i=0$: check that $z_i=z_0$\\
269otherwise, parse $\pi_i = ( (\mathsf{U}_i, \mathsf{W}_i), (\mathsf{u}_i, \mathsf{w}_i))$, then
270\begin{enumerate}
271	\item check $\mathsf{u}_i.x = H(vk, i, z_0, z_i, \mathsf{U}_i)$
272	\item check $(\mathsf{u}_i.{\overline{E}}, \mathsf{u}_i.u) = (\mathsf{u}_{\perp}.{\overline{E}}, 1)$
273	\item check that $\mathsf{W}_i,~ \mathsf{w}_i$ are satisfying witnesses to $\mathsf{U}_i,~ \mathsf{u}_i$ respectively
274\end{enumerate}
275
276\paragraph{A zkSNARK of a Valid IVC Proof}
277
278
279\bibliography{paper-notes.bib}
280\bibliographystyle{unsrt}
281
282\end{document}