math/notes_nova.tex

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{enumerate}
\usepackage{hyperref}
\usepackage{xcolor}

\usepackage{pgf-umlsd} % diagrams
% message between threads
% Example:
% \bloodymess[delay]{sender}{message content}{receiver}{DIR}{start note}{end note}
\newcommand{\bloodymess}[7][0]{
  \stepcounter{seqlevel}
  \path
  (#2)+(0,-\theseqlevel*\unitfactor-0.7*\unitfactor) node (mess from) {};
  \addtocounter{seqlevel}{#1}
  \path
  (#4)+(0,-\theseqlevel*\unitfactor-0.7*\unitfactor) node (mess to) {};
  \draw[->,>=angle 60] (mess from) -- (mess to) node[midway, above]
  {#3};

  \if R#5
  \node (\detokenize{#3} from) at (mess from) {\llap{#6~}};
  \node (\detokenize{#3} to) at (mess to) {\rlap{~#7}};
  \else\if L#5
  \node (\detokenize{#3} from) at (mess from) {\rlap{~#6}};
  \node (\detokenize{#3} to) at (mess to) {\llap{#7~}};
       \else
       \node (\detokenize{#3} from) at (mess from) {#6};
       \node (\detokenize{#3} to) at (mess to) {#7};
       \fi
  \fi
}

% prevent warnings of underfull \hbox:
\usepackage{etoolbox}
\apptocmd{\sloppy}{\hbadness 4000\relax}{}{}

\theoremstyle{definition}
\newtheorem{definition}{Def}[section]
\newtheorem{theorem}[definition]{Thm}

% custom lemma environment to set custom numbers
\newtheorem{innerlemma}{Lemma}
\newenvironment{lemma}[1]
{\renewcommand\theinnerlemma{#1}\innerlemma}
{\endinnerlemma}


\title{Notes on Nova}
\author{arnaucube}
\date{March 2023}

\begin{document}

\maketitle

\begin{abstract}
	Notes taken while reading Nova \cite{cryptoeprint:2021/370} paper.

	Usually while reading papers I take handwritten notes, this document contains some of them re-written to $LaTeX$.

	The notes are not complete, don't include all the steps neither all the proofs.
	
	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.
\end{abstract}

\tableofcontents

\section{NIFS}

\subsection{R1CS modification}

\paragraph{R1CS}
R1CS 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$.
R1CS is satisfied by a witness $w \in \mathbb{F}^{m-|io|-1}$ such that
$$Az \circ Bz = Cz$$
where $z=(io, 1, w)$.

\vspace{0.5cm}

\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.).

\paragraph{traditional R1CS}
Merged instance with $z=z_1 + r z_2$, for rand $r$. But, since R1CS is not linear $\longrightarrow$ can not apply.

eg.
\begin{align*}
	Az \circ Bz &= A(z_1 + r z_2) \circ B (z_1 + r z_2)\\
	&= 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)\\
	&\neq Cz
\end{align*}

$\longrightarrow$ introduce error vector $E \in \mathbb{F}^m$, which absorbs the cross-temrs generated by folding.

$\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)$.

\paragraph{Relaxed R1CS}
\begin{align*}
	&u=u_1+r u_2\\
	&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\\
	&Az \circ Bz = uCz + E,~~ with~ z=(W,~x,~u)
\end{align*}
where R1CS set $E=0,~u=1$.

\begin{align*}
	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)\\
		    &= (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)\\
		    &= 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\\
		    &= u_1 C z_1 + r^2 u_2 C z_2 + E\\
		    &= (u_1 + r u_2) \cdot C \cdot (z_1 + r z_2) + E\\
		    &= uCz + E
\end{align*}

For R1CS matrices $(A,~B,~C)$, the folded witness $W$ is a satisfying witness for the folded instance $(E,~u,~x)$.



\vspace{20px}
Problem: not non-trivial, and not zero-knowledge. Solution: use polynomial commitment with hiding, binding, succintness and additively homomorphic properties.

\paragraph{Committed Relaxed R1CS}
Instance for a Committed Relaxed R1CS\\
$(\overline{E}, u, \overline{W}, x)$, satisfied by a witness $(E, r_E, W, r_W)$ such that
\begin{align*}
	&\overline{E} = Com(E, r_E)\\
	&\overline{W} = Com(E, r_W)\\
	&Az \circ Bz = uCz+E,~~ where~z=(W, x, u)
\end{align*}


\subsection{Folding scheme for committed relaxed R1CS}

V and P take two \emph{committed relaxed R1CS} instances
\begin{align*}
	\varphi_1&=(\overline{E}_1, u_1, \overline{W}_1, x_1)\\
	\varphi_2&=(\overline{E}_2, u_2, \overline{W}_2, x_2)
\end{align*}

P additionally takes witnesses to both instances
\begin{align*}
	(E_1, r_{E_1}, W_1, r_{W_1})\\
	(E_2, r_{E_2}, W_2, r_{W_2})
\end{align*}

Let $Z_1 = (W_1, x_1, u_1)$ and $Z_2 = (W_2, x_2, u_2)$.

% \paragraph{Protocol}
\begin{enumerate}
	\item P send $\overline{T} = Com(T, r_T)$,\\
		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$\\
		and rand $r_T \in \mathbb{F}$
	\item V sample random challenge $r \in \mathbb{F}$
	\item V, P output the folded instance $\varphi = (\overline{E}, u, \overline{W}, x)$
		\begin{align*}
			&\overline{E}=\overline{E}_1 + r \overline{T} + r^2 \overline{E}_2\\
			&u = u_1 + r u_2\\
			&\overline{W} = \overline{W}_1 + r \overline{W}_2\\
			&x = x_1 + r x_2
		\end{align*}
	\item P outputs the folded witness $(E, r_E, W, r_W)$
		\begin{align*}
			&E = E_1 + r T + r^2 E_2\\
			&r_E = r_{E_1} + r \cdot r_T + r^2 r_{E_2}\\
			&W=W_1 + r W_2\\
			&r_W = r_{W_1} + r \cdot r_{W_2}
		\end{align*}
\end{enumerate}

P will prove that knows the valid witness $(E, r_E, W, r_W)$ for the committed relaxed R1CS without revealing its value.

\begin{center}
	\begin{sequencediagram}
		\newinst[1]{p}{Prover}
		\newinst[3]{v}{Verifier}

		\bloodymess[1]{p}{$\overline{T}$}{v}{R}{
			\shortstack{
				$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$\\
				$\overline{T}=Commit(T, r_T)$
			}
		}{
			\shortstack{
				$r \in^R \mathbb{F}_p$\\
				$\overline{E} = \overline{E}_1 + r \overline{T} + r^2 \overline{E}_2$\\
				$u= u_1 + r u_2$\\
				$\overline{W} = \overline{W}_1 + r \overline{W}_2$\\
				$\overline{x} = \overline{x}_1 + r \overline{x}_2$\\
				$\varphi=(\overline{E}, u, \overline{W}, x)$
			}
		}
		\bloodymess[1]{v}{$r$}{p}{L}{}{
			\shortstack{
				$E = E_1 + r T + r^2 E_2$\\
				$u= u_1 + r u_2$\\
				$W = W_1 + r W_2$\\
				$r_{W} = r_{W_1} + r r_{W_2}$\\
				$(E, r_E, W, r_W)$
			}
		}
	\end{sequencediagram}
\end{center}


The previous protocol achieves non-interactivity via Fiat-Shamir transform, obtaining a \emph{Non-Interactive Folding Scheme for Committed Relaxed R1CS}.

Note: 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)$).


\subsection{NIFS}

\underline{fold witness, $(pk, (u_1, w_1), (u_2, w_2))$}:
\begin{enumerate}
	\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$
	\item $\overline{T}=Commit(T, r_T)$
	% \item output the folded instance $\varphi = (\overline{E}, u, \overline{W}, x)$
	%         \begin{align*}
	%                 &\overline{E}=\overline{E}_1 + r \overline{T} + r^2 \overline{E}_2\\
	%                 &u = u_1 + r u_2\\
	%                 &\overline{W} = \overline{W}_1 + r \overline{W}_2\\
	%                 &x = x_1 + r x_2
	%         \end{align*}
	\item output the folded witness $(E, r_E, W, r_W)$
		\begin{align*}
			&E = E_1 + r T + r^2 E_2\\
			&r_E = r_{E_1} + r \cdot r_T + r^2 r_{E_2}\\
			&W=W_1 + r W_2\\
			&r_W = r_{W_1} + r \cdot r_{W_2}
		\end{align*}
\end{enumerate}

\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})$}:\\
V compute folded instance $\varphi = (\overline{E}, u, \overline{W}, x)$
\begin{align*}
	&\overline{E}=\overline{E}_1 + r \overline{T} + r^2 \overline{E}_2\\
	&u = u_1 + r u_2\\
	&\overline{W} = \overline{W}_1 + r \overline{W}_2\\
	&x = x_1 + r x_2
\end{align*}

\section{Nova}
IVC (Incremental Verifiable Computation) scheme for a non-interactive folding scheme.

\subsection{IVC proofs}

Allows prover to show $z_n = F^{(n)}(z_0)$, for some count $n$, initial input $z_0$, and output $z_n$.\\
$F$: program function (polynomial-time computable)\\
$F'$: augmented function, invokes $F$ and additionally performs fold-related stuff.

\vspace{0.5cm}
Two committed relaxed R1CS instances:\\
$\mathsf{U}_i$: represents the correct execution of invocations $1, \ldots, i-1$ of $F'$\\
$\mathsf{u}_i$: represents the correct execution of invocations $i$ of $F'$

\paragraph{Simplified version of $F'$ for intuition}
\vspace{0.5cm}
$F'$ performs two tasks:
\begin{enumerate}[i.]
	\item execute a step of the incremental computation:
		instance $\mathsf{u}_i$ contains $z_i$, used to output $z_{i+1}=F(z_i)$
	\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}$
\end{enumerate}

\vspace{0.5cm}
$F'$ proves that:
\begin{enumerate}
	\item $\exists ( (i, z_0, z_i, \mathsf{u}_i, \mathsf{U}_i), \mathsf{U}_{i+1}, \overline{T})$ such that
	\begin{enumerate}[i.]
		\item $\mathsf{u}_i.x = H(vk, i, z_0, z_i, \mathsf{U}_i)$
		\item $h_{i+1} = H(vk, i+1, z_0, F(z_i), \mathsf{U}_{i+1})$
		\item $\mathsf{U}_{i+1} = NIFS.V(vk, \mathsf{U}_i, \mathsf{u}_i, \overline{T})$
	\end{enumerate}
\item $F'$ outputs $h_{i+1}$
\end{enumerate}


$F'$ is described as follows:\\
\underline{$F'(vk, \mathsf{U}_i, \mathsf{u}_i, (i, z_0, z_i), w_i, \overline{T}) \rightarrow x$}:\\
if $i=0$, output $H(vk, 1, z_0, F(z_0, w_i), \mathsf{u}_{\bot})$\\
otherwise
\begin{enumerate}
	\item check $\mathsf{u}_i.x = H(vk, i, z_0, z_i, \mathsf{U}_i)$
	\item check $(\mathsf{u}_i.\overline{E}, \mathsf{u}_i.u) = (\mathsf{u}_{\bot}.\overline{E}, 1)$
	\item compute $\mathsf{U}_{i+1} \leftarrow NIFS.V(vk, U, u, \overline{T})$
	\item output $H(vk, i+1, z_0, F(z_i, w_i), \mathsf{U}_{i+1})$
\end{enumerate}

% TODO add diagram

\paragraph{IVC Proof}
iteration $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}$.
$(\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}))$.


\vspace{0.5cm}

\underline{$P(pk, (i, z_0, z_i), \mathsf{w}_i, \pi_i) \rightarrow \pi_{i+1}$}:\\
Parse $\pi_i = ( (\mathsf{U}_i, \mathsf{W}_i), (\mathsf{u}_i, \mathsf{w}_i))$, then
\begin{enumerate}
	\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}})$\\
		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))$
	\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}))$
	\item output $\pi_{i+1} \leftarrow ((\mathsf{U}_{i+1}, \mathsf{W}_{i+1}), (\mathsf{u}_{i+1}, \mathsf{w}_{i+1}))$
\end{enumerate}

\underline{$V(vk, (i, z_0, z_i), \pi_i) \rightarrow \{0,1\}$}:
if $i=0$: check that $z_i=z_0$\\
otherwise, parse $\pi_i = ( (\mathsf{U}_i, \mathsf{W}_i), (\mathsf{u}_i, \mathsf{w}_i))$, then
\begin{enumerate}
	\item check $\mathsf{u}_i.x = H(vk, i, z_0, z_i, \mathsf{U}_i)$
	\item check $(\mathsf{u}_i.{\overline{E}}, \mathsf{u}_i.u) = (\mathsf{u}_{\perp}.{\overline{E}}, 1)$
	\item check that $\mathsf{W}_i,~ \mathsf{w}_i$ are satisfying witnesses to $\mathsf{U}_i,~ \mathsf{u}_i$ respectively
\end{enumerate}

\vspace{0.5cm}

\paragraph{A zkSNARK of a Valid IVC Proof} prover and verifier:\\
\underline{$P(pk, (i, z_0, z_i), \Pi) \rightarrow \pi$}:\\
if $i=0$, output $\perp$, otherwise:\\
parse $\Pi$ as $((\mathsf{U}, \mathsf{W}), (\mathsf{u}, \mathsf{w}))$
\begin{enumerate}
	\item compute $(\mathsf{U}', \mathsf{W}', \overline{T}) \leftarrow NIFS.P(pk_{NIFS}, (\mathsf{U,~W}), (\mathsf{u,~w}))$
	\item compute $\pi_{\mathsf{u}'} \leftarrow zkSNARK.P(pk_{zkSNARK}, \mathsf{U}', \mathsf{W}')$
	\item output $(\mathsf{U,~ u}, \overline{T}, \pi_{\mathsf{u}'})$
\end{enumerate}

\underline{$V(vk, (i, z_0, z_i), \pi) \rightarrow \{0,1\}$}:\\
if $i=0$: check that $z_i=z_0$\\
parse $\pi$ as $(\mathsf{U}, \mathsf{u}, \overline{T}, \pi_{\mathsf{u}'})$
\begin{enumerate}
	\item check $\mathsf{u}.x = H(vk_{NIFS}, i, z_0, z_i, \mathsf{U})$
	\item check $(\mathsf{u}.{\overline{E}}, \mathsf{u}.u) = (\mathsf{u}_{\perp}.{\overline{E}}, 1)$
	\item compute $\mathsf{U}' \leftarrow NIFS.V(vk_{NIFS}, \mathsf{U}, \mathsf{u}, \overline{T})$
	\item check $zkSNARK.V(vk_{zkSNARK}, \mathsf{U}', \pi_{\mathsf{u}'})=1$
\end{enumerate}


\bibliography{paper-notes.bib}
\bibliographystyle{unsrt}

\end{document}