math/notes_nova.tex
notes_nova.texRaw
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{March 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
68 Thanks to \href{https://twitter.com/levs57}{Levs57}, \href{https://twitter.com/nibnalin}{Nalin Bhardwaj} and \href{https://twitter.com/cperezz19}{Carlos Pérez} for clarifications on the Nova paper.
69\end{abstract}
70
71\tableofcontents
72
73\section{NIFS}
74
75\subsection{R1CS modification}
76
77\paragraph{R1CS}
78R1CS instance: $(A, B, C, io, m, n)$, where $io$ denotes the public input and output, $A, B, C \in \mathbb{F}^{m \times n}$, with $m \geq |io|+1$.
79R1CS is satisfied by a witness $w \in \mathbb{F}^{m-|io|-1}$ such that
80$$Az \circ Bz = Cz$$
81where $z=(io, 1, w)$.
82
83\vspace{0.5cm}
84
85\textbf{Want}: 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.).
86
87\paragraph{traditional R1CS}
88Merged instance with $z=z_1 + r z_2$, for rand $r$. But, since R1CS is not linear $\longrightarrow$ can not apply.
89
90eg.
91\begin{align*}
92 Az \circ Bz &= A(z_1 + r z_2) \circ B (z_1 + r z_2)\\
93 &= 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)\\
94 &\neq Cz
95\end{align*}
96
97$\longrightarrow$ introduce error vector $E \in \mathbb{F}^m$, which absorbs the cross-temrs generated by folding.
98
99$\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)$.
100
101\paragraph{Relaxed R1CS}
102\begin{align*}
103 &u=u_1+r u_2\\
104 &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\\
105 &Az \circ Bz = uCz + E,~~ with~ z=(W,~x,~u)
106\end{align*}
107where R1CS set $E=0,~u=1$.
108
109\begin{align*}
110 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)\\
111 &= (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)\\
112 &= 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^2 u_2 C z_2\\
113 &= u_1 C z_1 + r^2 u_2 C z_2 + E\\
114 &= (u_1 + r u_2) \cdot C \cdot (z_1 + r z_2) + E\\
115 &= uCz + E
116\end{align*}
117
118For R1CS matrices $(A,~B,~C)$, the folded witness $W$ is a satisfying witness for the folded instance $(E,~u,~x)$.
119
120
121
122\vspace{20px}
123Problem: not non-trivial, and not zero-knowledge. Solution: use polynomial commitment with hiding, binding, succintness and additively homomorphic properties.
124
125\paragraph{Committed Relaxed R1CS}
126Instance for a Committed Relaxed R1CS\\
127$(\overline{E}, u, \overline{W}, x)$, satisfied by a witness $(E, r_E, W, r_W)$ such that
128\begin{align*}
129 &\overline{E} = Com(E, r_E)\\
130 &\overline{W} = Com(E, r_W)\\
131 &Az \circ Bz = uCz+E,~~ where~z=(W, x, u)
132\end{align*}
133
134
135\subsection{Folding scheme for committed relaxed R1CS}
136
137V and P take two \emph{committed relaxed R1CS} instances
138\begin{align*}
139 \varphi_1&=(\overline{E}_1, u_1, \overline{W}_1, x_1)\\
140 \varphi_2&=(\overline{E}_2, u_2, \overline{W}_2, x_2)
141\end{align*}
142
143P additionally takes witnesses to both instances
144\begin{align*}
145 (E_1, r_{E_1}, W_1, r_{W_1})\\
146 (E_2, r_{E_2}, W_2, r_{W_2})
147\end{align*}
148
149Let $Z_1 = (W_1, x_1, u_1)$ and $Z_2 = (W_2, x_2, u_2)$.
150
151% \paragraph{Protocol}
152\begin{enumerate}
153 \item P send $\overline{T} = Com(T, r_T)$,\\
154 where $T=A z_1 \circ B z_1 + A z_2 \circ B z_2 - u_1 C z_1 - u_2 C z_2$\\
155 and rand $r_T \in \mathbb{F}$
156 \item V sample random challenge $r \in \mathbb{F}$
157 \item V, P output the folded instance $\varphi = (\overline{E}, u, \overline{W}, x)$
158 \begin{align*}
159 &\overline{E}=\overline{E}_1 + r \overline{T} + r^2 \overline{E}_2\\
160 &u = u_1 + r u_2\\
161 &\overline{W} = \overline{W}_1 + r \overline{W}_2\\
162 &x = x_1 + r x_2
163 \end{align*}
164 \item P outputs the folded witness $(E, r_E, W, r_W)$
165 \begin{align*}
166 &E = E_1 + r T + r^2 E_2\\
167 &r_E = r_{E_1} + r \cdot r_T + r^2 r_{E_2}\\
168 &W=W_1 + r W_2\\
169 &r_W = r_{W_1} + r \cdot r_{W_2}
170 \end{align*}
171\end{enumerate}
172
173P will prove that knows the valid witness $(E, r_E, W, r_W)$ for the committed relaxed R1CS without revealing its value.
174
175\begin{center}
176 \begin{sequencediagram}
177 \newinst[1]{p}{Prover}
178 \newinst[3]{v}{Verifier}
179
180 \bloodymess[1]{p}{$\overline{T}$}{v}{R}{
181 \shortstack{
182 $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$\\
183 $\overline{T}=Commit(T, r_T)$
184 }
185 }{
186 \shortstack{
187 $r \in^R \mathbb{F}_p$\\
188 $\overline{E} = \overline{E}_1 + r \overline{T} + r^2 \overline{E}_2$\\
189 $u= u_1 + r u_2$\\
190 $\overline{W} = \overline{W}_1 + r \overline{W}_2$\\
191 $\overline{x} = \overline{x}_1 + r \overline{x}_2$\\
192 $\varphi=(\overline{E}, u, \overline{W}, x)$
193 }
194 }
195 \bloodymess[1]{v}{$r$}{p}{L}{}{
196 \shortstack{
197 $E = E_1 + r T + r^2 E_2$\\
198 $u= u_1 + r u_2$\\
199 $W = W_1 + r W_2$\\
200 $r_{W} = r_{W_1} + r r_{W_2}$\\
201 $(E, r_E, W, r_W)$
202 }
203 }
204 \end{sequencediagram}
205\end{center}
206
207
208The previous protocol achieves non-interactivity via Fiat-Shamir transform, obtaining a \emph{Non-Interactive Folding Scheme for Committed Relaxed R1CS}.
209
210Note: the paper later uses $\mathsf{u}_i,~ \mathsf{U}_i$ for the two inputted $\varphi_1,~ \varphi_2$, and later $\mathsf{u}_{i+1}$ for the outputted $\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)$).
211
212
213\subsection{NIFS}
214
215\underline{fold witness, $(pk, (u_1, w_1), (u_2, w_2))$}:
216\begin{enumerate}
217 \item $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$
218 \item $\overline{T}=Commit(T, r_T)$
219 % \item output the folded instance $\varphi = (\overline{E}, u, \overline{W}, x)$
220 % \begin{align*}
221 % &\overline{E}=\overline{E}_1 + r \overline{T} + r^2 \overline{E}_2\\
222 % &u = u_1 + r u_2\\
223 % &\overline{W} = \overline{W}_1 + r \overline{W}_2\\
224 % &x = x_1 + r x_2
225 % \end{align*}
226 \item output the folded witness $(E, r_E, W, r_W)$
227 \begin{align*}
228 &E = E_1 + r T + r^2 E_2\\
229 &r_E = r_{E_1} + r \cdot r_T + r^2 r_{E_2}\\
230 &W=W_1 + r W_2\\
231 &r_W = r_{W_1} + r \cdot r_{W_2}
232 \end{align*}
233\end{enumerate}
234
235\underline{fold instances $(\varphi_1, \varphi_2) \rightarrow \varphi$, $(vk, u_1, u_2, \overline{E}_1, \overline{E}_2, \overline{W}_1, \overline{W}_2, \overline{T})$}:\\
236V compute folded instance $\varphi = (\overline{E}, u, \overline{W}, x)$
237\begin{align*}
238 &\overline{E}=\overline{E}_1 + r \overline{T} + r^2 \overline{E}_2\\
239 &u = u_1 + r u_2\\
240 &\overline{W} = \overline{W}_1 + r \overline{W}_2\\
241 &x = x_1 + r x_2
242\end{align*}
243
244\section{Nova}
245IVC (Incremental Verifiable Computation) scheme for a non-interactive folding scheme.
246
247\subsection{IVC proofs}
248
249Allows prover to show $z_n = F^{(n)}(z_0)$, for some count $n$, initial input $z_0$, and output $z_n$.\\
250$F$: program function (polynomial-time computable)\\
251$F'$: augmented function, invokes $F$ and additionally performs fold-related stuff.
252
253\vspace{0.5cm}
254Two committed relaxed R1CS instances:\\
255$\mathsf{U}_i$: represents the correct execution of invocations $1, \ldots, i-1$ of $F'$\\
256$\mathsf{u}_i$: represents the correct execution of invocations $i$ of $F'$
257
258\paragraph{Simplified version of $F'$ for intuition}
259\vspace{0.5cm}
260$F'$ performs two tasks:
261\begin{enumerate}[i.]
262 \item execute a step of the incremental computation:
263 instance $\mathsf{u}_i$ contains $z_i$, used to output $z_{i+1}=F(z_i)$
264 \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}$
265\end{enumerate}
266
267\vspace{0.5cm}
268$F'$ proves that:
269\begin{enumerate}
270 \item $\exists ( (i, z_0, z_i, \mathsf{u}_i, \mathsf{U}_i), \mathsf{U}_{i+1}, \overline{T})$ such that
271 \begin{enumerate}[i.]
272 \item $\mathsf{u}_i.x = H(vk, i, z_0, z_i, \mathsf{U}_i)$
273 \item $h_{i+1} = H(vk, i+1, z_0, F(z_i), \mathsf{U}_{i+1})$
274 \item $\mathsf{U}_{i+1} = NIFS.V(vk, \mathsf{U}_i, \mathsf{u}_i, \overline{T})$
275 \end{enumerate}
276\item $F'$ outputs $h_{i+1}$
277\end{enumerate}
278
279
280$F'$ is described as follows:\\
281\underline{$F'(vk, \mathsf{U}_i, \mathsf{u}_i, (i, z_0, z_i), w_i, \overline{T}) \rightarrow x$}:\\
282if $i=0$, output $H(vk, 1, z_0, F(z_0, w_i), \mathsf{u}_{\bot})$\\
283otherwise
284\begin{enumerate}
285 \item check $\mathsf{u}_i.x = H(vk, i, z_0, z_i, \mathsf{U}_i)$
286 \item check $(\mathsf{u}_i.\overline{E}, \mathsf{u}_i.u) = (\mathsf{u}_{\bot}.\overline{E}, 1)$
287 \item compute $\mathsf{U}_{i+1} \leftarrow NIFS.V(vk, U, u, \overline{T})$
288 \item output $H(vk, i+1, z_0, F(z_i, w_i), \mathsf{U}_{i+1})$
289\end{enumerate}
290
291% TODO add diagram
292
293\paragraph{IVC Proof}
294iteration $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}$.
295$(\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}))$.
296
297
298\vspace{0.5cm}
299
300\underline{$P(pk, (i, z_0, z_i), \mathsf{w}_i, \pi_i) \rightarrow \pi_{i+1}$}:\\
301Parse $\pi_i = ( (\mathsf{U}_i, \mathsf{W}_i), (\mathsf{u}_i, \mathsf{w}_i))$, then
302\begin{enumerate}
303 \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}})$\\
304 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))$
305 \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}))$
306 \item output $\pi_{i+1} \leftarrow ((\mathsf{U}_{i+1}, \mathsf{W}_{i+1}), (\mathsf{u}_{i+1}, \mathsf{w}_{i+1}))$
307\end{enumerate}
308
309\underline{$V(vk, (i, z_0, z_i), \pi_i) \rightarrow \{0,1\}$}:
310if $i=0$: check that $z_i=z_0$\\
311otherwise, parse $\pi_i = ( (\mathsf{U}_i, \mathsf{W}_i), (\mathsf{u}_i, \mathsf{w}_i))$, then
312\begin{enumerate}
313 \item check $\mathsf{u}_i.x = H(vk, i, z_0, z_i, \mathsf{U}_i)$
314 \item check $(\mathsf{u}_i.{\overline{E}}, \mathsf{u}_i.u) = (\mathsf{u}_{\perp}.{\overline{E}}, 1)$
315 \item check that $\mathsf{W}_i,~ \mathsf{w}_i$ are satisfying witnesses to $\mathsf{U}_i,~ \mathsf{u}_i$ respectively
316\end{enumerate}
317
318\vspace{0.5cm}
319
320\paragraph{A zkSNARK of a Valid IVC Proof} prover and verifier:\\
321\underline{$P(pk, (i, z_0, z_i), \Pi) \rightarrow \pi$}:\\
322if $i=0$, output $\perp$, otherwise:\\
323parse $\Pi$ as $((\mathsf{U}, \mathsf{W}), (\mathsf{u}, \mathsf{w}))$
324\begin{enumerate}
325 \item compute $(\mathsf{U}', \mathsf{W}', \overline{T}) \leftarrow NIFS.P(pk_{NIFS}, (\mathsf{U,~W}), (\mathsf{u,~w}))$
326 \item compute $\pi_{\mathsf{u}'} \leftarrow zkSNARK.P(pk_{zkSNARK}, \mathsf{U}', \mathsf{W}')$
327 \item output $(\mathsf{U,~ u}, \overline{T}, \pi_{\mathsf{u}'})$
328\end{enumerate}
329
330\underline{$V(vk, (i, z_0, z_i), \pi) \rightarrow \{0,1\}$}:\\
331if $i=0$: check that $z_i=z_0$\\
332parse $\pi$ as $(\mathsf{U}, \mathsf{u}, \overline{T}, \pi_{\mathsf{u}'})$
333\begin{enumerate}
334 \item check $\mathsf{u}.x = H(vk_{NIFS}, i, z_0, z_i, \mathsf{U})$
335 \item check $(\mathsf{u}.{\overline{E}}, \mathsf{u}.u) = (\mathsf{u}_{\perp}.{\overline{E}}, 1)$
336 \item compute $\mathsf{U}' \leftarrow NIFS.V(vk_{NIFS}, \mathsf{U}, \mathsf{u}, \overline{T})$
337 \item check $zkSNARK.V(vk_{zkSNARK}, \mathsf{U}', \pi_{\mathsf{u}'})=1$
338\end{enumerate}
339
340
341\bibliography{paper-notes.bib}
342\bibliographystyle{unsrt}
343
344\end{document}