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 Nova}
 27\author{arnaucube}
 28\date{February 2023}
 29
 30\begin{document}
 31
 32\maketitle
 33
 34\begin{abstract}
 35	Notes taken while reading Nova \cite{cryptoeprint:2021/370} paper.
 36
 37	Usually while reading papers I take handwritten notes, this document contains some of them re-written to $LaTeX$.
 38
 39	The notes are not complete, don't include all the steps neither all the proofs.
 40\end{abstract}
 41
 42\tableofcontents
 43
 44\section{Folding Scheme for Committed Relaxed R1CS}
 45
 46\subsection{R1CS modification}
 47
 48Want: 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.).
 49
 50\paragraph{traditional R1CS}
 51Merged instance with $z=z_1 + r z_2$, for rand $r$. But, since R1CS is not linear $\longrightarrow$ can not apply.
 52
 53eg.
 54\begin{align*}
 55	Az \circ Bz &= A(z_1 + r z_2) \circ B (z_1 + r z_2)\\
 56	&= 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)\\
 57	&\neq Cz
 58\end{align*}
 59
 60$\longrightarrow$ introduce error vector $E \in \mathbb{F}^m$, which absorbs the cross-temrs generated by folding.
 61
 62$\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)$.
 63
 64\paragraph{Relaxed R1CS}
 65\begin{align*}
 66	&u=u_1+r u_2\\
 67	&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\\
 68	&Az \circ Bz = uCz + E,~~ with~ z=(W,~x,~u)
 69\end{align*}
 70where R1CS set $E=0,~u=1$.
 71
 72\begin{align*}
 73	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)\\
 74		    &= (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)\\
 75		    &= 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\\
 76		    &= u_1 C z_1 + r^2 u_2 C z_2 + E\\
 77		    &= (u_1 + r u_2) \cdot C \cdot (z_1 + r z_2) + E\\
 78		    &= uCz + E
 79\end{align*}
 80
 81For R1CS matrices $(A,~B,~C)$, the folded witness $W$ is a satisfying witness for the folded instance $(E,~u,~x)$.
 82
 83
 84
 85\vspace{20px}
 86Problem: not non-trivial, and not zero-knowledge. Solution: use polynomial commitment with hiding, binding, succintness and additively homomorphic properties.
 87
 88\paragraph{Committed Relaxed R1CS}
 89Instance for a Committed Relaxed R1CS\\
 90$(\overline{E}, u, \overline{W}, x)$, satisfyied by a witness $(E, r_E, W, r_W)$ such that
 91\begin{align*}
 92	&\overline{E} = Com(E, r_E)\\
 93	&\overline{W} = Com(E, r_W)\\
 94	&Az \circ Bz = uCz+E,~~ where~z=(W, x, u)
 95\end{align*}
 96
 97
 98\subsection{Folding protocol}
 99
100V and P take two \emph{committed relaxed R1CS} instances
101\begin{align*}
102	\varphi_1&=(\overline{E}_1, u_1, \overline{W}_1, x_1)\\
103	\varphi_2&=(\overline{E}_2, u_2, \overline{W}_2, x_2)
104\end{align*}
105
106P additionally takes witnesses to both instances
107\begin{align*}
108	(E_1, r_{E_1}, W_1, r_{W_1})\\
109	(E_2, r_{E_2}, W_2, r_{W_2})
110\end{align*}
111
112Let $Z_1 = (W_1, x_1, u_1)$ and $Z_2 = (W_2, x_2, u_2)$.
113
114% \paragraph{Protocol}
115\begin{enumerate}
116	\item P send $\overline{T} = Com(T, r_T)$,\\
117		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$\\
118		and rand $r_T \in \mathbb{F}$
119	\item V sample random challenge $r \in \mathbb{F}$
120	\item V, P output the folded instance $\varphi = (\overline{E}, u, \overline{W}, x)$
121		\begin{align*}
122			&\overline{E}=\overline{E}_1 + r \overline{T} + r^2 \overline{E}_2\\
123			&u = u_1 + r u_2\\
124			&\overline{W} = \overline{W}_1 + r \overline{W}_2\\
125			&x = x_1 + r x_2
126		\end{align*}
127	\item P outputs the folded witness $(E, r_E, W, r_W)$
128		\begin{align*}
129			&E = E_1 + r T + r^2 E_2\\
130			&r_E = r_{E_1} + r \cdot r_T + r^2 r_{E_2}\\
131			&W=W_1 + r W_2\\
132			&r_W = r_{W_1} + r \cdot r_{W_2}
133		\end{align*}
134\end{enumerate}
135
136P uses a zkSNARK showing that knows the valid witness $(E, r_E, W, r_W)$ for the committed relaxed R1CS without revealing its value.
137Then, vie Fiat-Shamir transform we achieve non-interactivity.
138
139\section{IVC proofs}
140\textbf{WIP}
141
142
143\bibliography{paper-notes.bib}
144\bibliographystyle{unsrt}
145
146\end{document}