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\usepackage{centernot}
 12
 13
 14% prevent warnings of underfull \hbox:
 15\usepackage{etoolbox}
 16\apptocmd{\sloppy}{\hbadness 4000\relax}{}{}
 17
 18\theoremstyle{definition}
 19\newtheorem{definition}{Def}[section]
 20\newtheorem{theorem}[definition]{Thm}
 21
 22% custom lemma environment to set custom numbers
 23\newtheorem{innerlemma}{Lemma}
 24\newenvironment{lemma}[1]
 25{\renewcommand\theinnerlemma{#1}\innerlemma}
 26{\endinnerlemma}
 27
 28
 29\title{Notes on Spartan}
 30\author{arnaucube}
 31\date{April 2023}
 32
 33\begin{document}
 34
 35\maketitle
 36
 37\begin{abstract}
 38	Notes taken while reading about Spartan \cite{cryptoeprint:2019/550}.
 39
 40	Usually while reading papers I take handwritten notes, this document contains some of them re-written to $LaTeX$.
 41
 42	The notes are not complete, don't include all the steps neither all the proofs.
 43\end{abstract}
 44
 45\tableofcontents
 46
 47\section{R1CS into Sum-Check protocol}
 48\begin{definition}{R1CS}
 49	$\exists w \in \mathbb{F}^{m - |io| - 1}$ such that $(A \cdot z) \circ (B \cdot z) = (C \cdot z)$, where $z=(io, 1, w)$.
 50\end{definition}
 51
 52
 53\textbf{Thm 4.1} $\forall$ R1CS instance $x = (\mathbb{F}, A, B, C, io, m, n)$, $\exists$ a degree-3 log m-variate polynomial $G$ such that $\sum_{x \in \{0,1\}^{log m}} G(x) = 0$ iff $\exists$ a witness $w$ such that $Sat_{R1CS}(x, w)=1$.
 54% \begin{theorem}{4.1} // TODO use theorem gadget
 55%	$\forall$
 56% \begin{end}
 57\vspace{0.5cm}
 58
 59% For a RCS instance $x$, let $s = \lceil \log m \rceil$.
 60
 61We can view matrices $A, B, C \in \mathbb{F}^{m \times m}$ as functions $\{0,1\}^s \times \{0,1\}^s \rightarrow \mathbb{F}$ ($s= \lceil \log m \rceil$).
 62For a given witness $w$ to $x$, let $z=(io, 1, w)$.
 63View $z$ as a function $\{0,1\}^s \rightarrow \mathbb{F}$, so any entry in $z$ can be accessed with a $s$-bit identifier.
 64
 65\begin{small}
 66$$
 67F_{io}(x)=\left( \sum_{y \in \{0,1\}^s} A(x, y) \cdot Z(y) \right) \cdot \left( \sum_{y \in \{0,1\}^s} B(x, y) \cdot Z(y) \right) - \sum_{y \in \{0,1\}^s} C(x, y) \cdot Z(y)
 68$$
 69\end{small}
 70
 71\begin{lemma}{4.1}
 72	$\forall x \in \{0,1\}^s,~ F_{io}(x)=0$ iff $Sat_{R1CS}(x,w)=1$.
 73\end{lemma}
 74
 75$F_{io}(\cdot)$ is a function, not a polynomial, so it can not be used in the Sum-check protocol.
 76
 77$F_{io}(x)$ function is converted to a polynomial by using its polynomial extension $\widetilde{F}_{io}(x): \mathbb{F}^s \rightarrow \mathbb{F}$,
 78\begin{small}
 79$$
 80\widetilde{F}_{io}(x)=\left( \sum_{y \in \{0,1\}^s} \widetilde{A}(x, y) \cdot \widetilde{Z}(y) \right) \cdot \left( \sum_{y \in \{0,1\}^s} \widetilde{B}(x, y) \cdot \widetilde{Z}(y) \right) - \sum_{y \in \{0,1\}^s} \widetilde{C}(x, y) \cdot \widetilde{Z}(y)
 81$$
 82\end{small}
 83
 84\begin{lemma}{4.2}
 85	$\forall x \in \{0,1\}^s,~ \widetilde{F}_{io}(x)=0$ iff $Sat_{R1CS}(x, w)=1$.
 86\end{lemma}
 87
 88(proof: $\forall x \in \{0,1\}^s,~ \widetilde{F}_{io}(x)=F_{io}(x)$, so, result follows from Lemma 4.1.) % TODO link to lemma
 89
 90\vspace{0.5cm}
 91
 92So, for this, V will need to check that $\widetilde{F}_{io}$ vanishes over the boolean hypercube ($\widetilde{F}_{io}(x)=0 ~\forall x \in \{0,1\}^s$).
 93
 94Recall that $\widetilde{F}_{io}(\cdot)$ is a low-degree multivariate polynomial over $\mathbb{F}$ in $s$ variables.
 95Thus, checking that $\widetilde{F}_{io}$ vanishes over the boolean hypercube is equivalent to checking that $\widetilde{F}_io=0$.
 96
 97Thus, V can check $\sum_{x \in \{0,1\}^s} \widetilde{F}_{io}(x)=0$ using the Sum-check protocol (through SZ lemma, V can check if for a random value it equals to 0, and be convinced that applies to all the points whp.).
 98
 99But: as $\widetilde{F}_{io}(x)$ is not multilinear, so $\sum_{x\in \{0,1\}^s} \widetilde{F}_{io}(x)=0 \centernot\Longleftrightarrow F_{io}(x)=0 ~\forall x \in \{0,1\}^s$.
100Bcs: the $2^s$ terms in the sum might cancel each other even when the individual terms are not zero.
101
102Solution: combine $\widetilde{F}_{io}(x)$ with $\widetilde{eq}(t, x)$ to get $Q_{io}(t, x)$ which will be the unique multilinear polynomial, and then check that it is a zero-polynomial
103
104$$Q_{io}(t)= \sum_{x \in \{0,1\}^s} \widetilde{F}_{io}(x) \cdot \widetilde{eq}(t, x)$$
105
106where $\widetilde{eq}(t, x) = \prod_{i=1}^s (t_i \cdot x_i + (1- t_i) \cdot (1- x_i))$, which is the MLE of $eq(x,e)= \{ 1 ~\text{if}~ x=e,~ 0 ~\text{otherwise} \}$.
107
108Basically $Q_{io}(\cdot)$ is a multivariate (the unique multilinear) polynomial such that
109$$Q_{io}(t) = \widetilde{F}_{io}(t) ~\forall t \in \{0,1\}^s$$
110thus, $Q_{io}(\cdot)$ is a zero-polynomial iff $\widetilde{F}_{io}(x)=0 ~\forall x\in \{0,1\}^s$.
111$\Longleftrightarrow$ iff $\widetilde{F}_{io}(\cdot)$ encodes a witness $w$ such that $Sat_{R1CS}(x, w)=1$.
112
113$\widetilde{F}_{io}(x)$ has degree 2 in each variable, and $\widetilde{eq}(t, x)$ has degree 1 in each variable, so $Q_{io}(t)$ has degree 3 in each variable.
114
115To check that $Q_{io}(\cdot)$ is a zero-polynomial: check $Q_{io}(\tau)=0,~ \tau \in^R \mathbb{F}^s$ (Schwartz-Zippel-DeMillo–Lipton lemma) through the sum-check protocol.
116
117This would mean that the R1CS instance is satisfied.
118
119
120\paragraph{Recap}
121\begin{itemize}
122	\item[] We have that $Sat_{R1CS}(x,w)=1$ iff $F_{io}(x)=0$.
123	\item[] To be able to use sum-check, we use its polynomial extension $\widetilde{F}_{io}(x)$, using sum-check to prove that $\widetilde{F}_{io}(x) =0 ~\forall x \in \{0, 1\}^s$, which means that $Sat_{R1CS}(x,~w)=1$.
124	\item[] To prevent potential canceling terms, we combine $\widetilde{F}_{io}(x)$ with $\widetilde{eq}(t, x)$, obtaining $G_{io, \tau}(x)= \widetilde{F}_{io}(x) \cdot \widetilde{eq}(t, x)$.
125	\item[] Thus $Q_{io}(t)= \sum_{x \in \{0,1\}^s} \widetilde{F}_{io}(x) \cdot \widetilde{eq}(t, x)$, and then we prove that $Q_{io}(\tau)=0$, for $\tau \in^R \mathbb{F}^s$.
126\end{itemize}
127
128\section{NIZKs with succinct proofs for R1CS}
129
130From Thm 4.1: to check R1CS instance $(\mathbb{F}, A, B, C, io, m, n)$ V can check if
131$\sum_{x \in \{0,1\}^s} G_{io, \tau} (x) = 0$, which through sum-check protocol can be reduced to $e_x = G_{io, \tau} (r_x)$, where $r_x \in \mathbb{F}^s$.
132
133Recall: $G_{io, \tau}(x) = \widetilde{F}_{io}(x) \cdot \widetilde{eq}(\tau, x)$.
134
135Evaluating $\widetilde{eq}(\tau, r_x)$ takes $O(log~m)$, but to evaluate $\widetilde{F}_{io}(r_x)$, V needs to evaluate
136$$\widetilde{A}(r_x, y), \widetilde{B}(r_x, y), \widetilde{C}(r_x, y), \widetilde{Z}(y),~ \forall y \in \{0,1\}^s$$
137
138which requires 3 sum-check instances (\begin{scriptsize}
139$\left( \sum_{y \in \{0,1\}^s} \widetilde{A}(x, y) \cdot \widetilde{Z}(y) \right)$,\\ $\left( \sum_{y \in \{0,1\}^s} \widetilde{B}(x, y) \cdot \widetilde{Z}(y) \right)$, $\left( \sum_{y \in \{0,1\}^s} \widetilde{C}(x, y) \cdot \widetilde{Z}(y) \right)$
140\end{scriptsize}), one for each summation in\\ $\widetilde{F}_{io}(x)$.
141
142But note that evaluations of $\widetilde{Z}(y) ~\forall y \in \{0,1\}^s$ are already known as $(io, 1, w)$.
143
144Solution: combination of 3 protocols:
145\begin{itemize}
146	\item Sum-check protocol
147	\item randomized mini protocol
148	\item polynomial commitment scheme
149\end{itemize}
150Basically to do a random linear combination of the 3 summations to end up doing just a single sum-check.
151
152Observation: let $\widetilde{F}_{io}(r_x) = \overline{A}(r_x) \cdot \overline{B}(r_x) - \overline{C}(r_x)$, where
153$$\overline{A}(r_x) = \sum_{y \in \{0,1\}} \widetilde{A}(r_x, y) \cdot \widetilde{Z}(y),~~\overline{B}(r_x) = \sum_{y \in \{0,1\}} \widetilde{B}(r_x, y) \cdot \widetilde{Z}(y)$$
154$$\overline{C}(r_x) = \sum_{y \in \{0,1\}} \widetilde{C}(r_x, y) \cdot \widetilde{Z}(y)$$
155
156Prover makes 3 separate claims: $\overline{A}(r_x)=v_A,~ \overline{B}(r_x)=v_B,~ \overline{C}(r_x)=v_C$,
157then V evaluates:
158$$G_{io, \tau}(r_x) = (v_A \cdot v_B - v_C) \cdot \widetilde{eq}(r_x, \tau)$$
159
160
161\begin{footnotesize}
162	which equals to
163	$$=\left(\overline{A}(r_x) \cdot \overline{B}(r_x) - \overline{C}(r_x)\right) \cdot \widetilde{eq}(r_x, \tau)=$$
164	$$\left(\left(\sum_{y \in \{0,1\}} \widetilde{A}(r_x, y) \cdot \widetilde{Z}(y)\right) \cdot \left(\sum_{y \in \{0,1\}} \widetilde{B}(r_x, y) \cdot \widetilde{Z}(y)\right) - \sum_{y \in \{0,1\}} \widetilde{C}(r_x, y) \cdot \widetilde{Z}(y)\right) \cdot \widetilde{eq}(r_x, \tau)$$
165\end{footnotesize}
166
167\vspace{0.5cm}
168
169This would be 3 sum-check protocol instances (3 claims: $\overline{A}(r_x)=v_A$, $\overline{B}(r_x)=v_B$, $\overline{C}(r_x)=v_C$).
170
171Instead, combine 3 claims into a single claim:
172
173\begin{itemize}
174	\item V samples $r_A, r_B, r_C \in^R \mathbb{F}$, and computes $c= r_A v_A + r_B v_B + r_C v_C$.
175	\item V, P use sum-check protocol to check:
176$$r_A \cdot \overline{A}(r_x) + r_B \cdot \overline{B}(r_x) + r_C \cdot \overline{C}(r_x) == c$$
177
178
179% Let $L(r_x) = r_A \cdot \overline{A}(r_x) +r_B \cdot \overline{B}(r_x) +r_C \cdot \overline{C}(r_x)$,
180Let
181\begin{small}
182\begin{align*}
183	&L(r_x) = r_A \cdot \overline{A}(r_x) +r_B \cdot \overline{B}(r_x) +r_C \cdot \overline{C}(r_x)\\
184	&= \sum_{y \in \{0,1\}^s}
185	       \left( r_A \cdot \widetilde{A}(r_x, y) \cdot \widetilde{Z}(y)
186	       + r_B \cdot \widetilde{B}(r_x, y) \cdot \widetilde{Z}(y)
187	       + r_C \cdot \widetilde{C}(r_x, y) \cdot \widetilde{Z}(y) \right)\\
188	       &= \sum_{y \in \{0,1\}^s} M_{r_x}(y)
189\end{align*}
190\end{small}
191
192$M_{r_x}(y)$ is a s-variate polynomial with deg $\leq 2$ in each variable ($\Longleftrightarrow \mu = s,~ l=2,~ T=c$).
193
194\end{itemize}
195
196
197\begin{align*}
198M_{r_x}(r_y) &=
199r_A \cdot \widetilde{A}(r_x, r_y) \cdot \widetilde{Z}(r_y)
200+ r_B \cdot \widetilde{B}(r_x, r_y) \cdot \widetilde{Z}(r_y)
201+ r_C \cdot \widetilde{C}(r_x, r_y) \cdot \widetilde{Z}(r_y)\\
202	     &=
203	     (r_A \cdot \widetilde{A}(r_x, r_y)
204+ r_B \cdot \widetilde{B}(r_x, r_y)
205+ r_C \cdot \widetilde{C}(r_x, r_y)) \cdot \widetilde{Z}(r_y)\\
206\end{align*}
207
208only one term in $M_{r_x}(r_y)$ depends on prover's witness: $\widetilde{Z}(r_y)$, the other terms can be computed locally by V in $O(n)$ time (Section 6 of the paper for sub-linear in $n$).
209
210Instead of evaluating $\widetilde{Z}(r_y)$ in $O(|w|)$ communications, P sends a commitment to $\widetilde{w}(\cdot)$ (= MLE of the witness $w$) to V before the first instance of the sum-check protocol.
211
212
213\paragraph{Recap}
214\begin{itemize}
215	\item[] To check the R1CS instance, V can check $\sum_{x \in \{0,1\}^s} G_{io, \tau} (x) = 0$, which through the sum-check is reduced to $e_x = G_{io, \tau} (r_x)$, for $r_x \in \mathbb{F}^s$.
216	\item[] Evaluating $G_{io, \tau}(x)$ ($G_{io, \tau}(x) = \widetilde{F}_{io}(x) \cdot \widetilde{eq}(\tau, x)$) is not cheap. Evaluating $\widetilde{eq}(\tau, r_x)$ takes $O(log~m)$, but to evaluate $\widetilde{F}_{io}(r_x)$, V needs to evaluate $\widetilde{A}, \widetilde{B}, \widetilde{C}, \widetilde{Z},~ \forall y \in \{0,1\}^s$
217	% \item[] Solution: combine 3 protocols: sum-check protocol, randomized mini protocol, polynomial commitment scheme.
218	\item[] P makes 3 separate claims: $\overline{A}(r_x)=v_A,~ \overline{B}(r_x)=v_B,~ \overline{C}(r_x)=v_C$, so V can evaluate $G_{io, \tau}(r_x) = (v_A \cdot v_B - v_C) \cdot \widetilde{eq}(r_x, \tau)$
219	\item[] The previous claims are combined into a single claim (random linear combination) to use only a single sum-check protocol:
220		\begin{itemize}
221			\item[] P: $c= r_A v_A + r_B v_B + r_C v_C$, for $r_A, r_B, r_C \in^R \mathbb{F}$
222			\item[] V, P: sum-check $r_A \cdot \overline{A}(r_x) + r_B \cdot \overline{B}(r_x) + r_C \cdot \overline{C}(r_x) == c$
223		\end{itemize}
224	\item[] $c=L(r_x)=\sum_{y \in \{0,1\}^s} M_{r_x}(y)$, where $M_{r_x}(y)$ is a s-variate polynomial with deg $\leq 2$ in each variable ($\Longleftrightarrow \mu = s,~ l=2,~ T=c$). Only $\widetilde{Z}(r_y)$ depends on P's witness, the other terms can be computed locally by V.
225	\item[] Instead of evaluating $\widetilde{Z}(r_y)$ in $O(|w|)$ communications, P uses a commitment to $\widetilde{w}(\cdot)$ (= MLE of the witness $w$).
226\end{itemize}
227
228\subsection{Full protocol}
229\begin{footnotesize}
230	(Recall: Sum-Check params: $\mu$: n vars, n rounds, $l$: degree in each variable upper bound, $T$: claimed result.)
231\end{footnotesize}
232
233\begin{itemize}
234	\item $pp \leftarrow Setup(1^{\lambda})$: invoke $pp \leftarrow PC.Setup(1^{\lambda}, log m)$; output $pp$
235	\item $b \leftarrow <P(w), V(r)>(\mathbb{F}, A,B,C, io, m, n)$:
236	\begin{enumerate}
237		\item P: $(C, S) \leftarrow PC.Commit(pp, \widetilde{w})$ and send $C$ to V
238		\item V: send $\tau \in^R \mathbb{F}^{log~m}$ to P
239		\item let $T_1=0,~ \mu_1=log~m,~ l_1=3$
240		\item V: set $r_x \in^R \mathbb{F}^{\mu_1}$
241		\item Sum-check 1. $e_x \leftarrow <P_{SC}(G_{io,\tau}), V_{SC}(r_x)>(\mu_1, l_1, T_1)$
242		\item P: compute $v_A=\overline{A}(r_x),~ v_B=\overline{B}(r_x),~ v_C=\overline{C}(r_x)$, send $(v_A, v_B, v_C)$ to V
243		\item V: abort with $b=0$ if $e_x \neq (v_A \cdot v_B - v_C)\cdot \widetilde{eq}(r_x, \tau)$
244		\item V: send $r_A, r_B, r_C \in^R \mathbb{F}$ to P
245		\item let $T_2 = r_A \cdot v_A + r_B \cdot v_B + r_C \cdot v_C,~ \mu_2=log~m,~ l_2=2$
246		\item V: set $r_y \in^R \mathbb{F}^{\mu_2}$
247		\item Sum-check 2. $e_y \leftarrow <P_{SC}(M_{r_x}), V_{SC}(r_y)>(\mu_2, l_2, T_2)$
248		\item P: $v \leftarrow \widetilde{w}(r_y[1..])$, send $v$ to V
249		\item $b_e \leftarrow <P_{PC.Eval}(\widetilde{w}, S), V_{PC.Eval}(r)>(pp,  C, r_y, v, \mu_2)$
250		\item V: abort with $b=0$ if $b_e==0$
251		\item V: $v_z \leftarrow (1 - r_y[0]) \cdot \widetilde{w}(r_y [1..]) + r_y[0] \widetilde{(io, 1)} (r_y[1..])$
252		\item V: $v_1 \leftarrow \widetilde{A}(r_x, r_y),~ v_2 \leftarrow \widetilde{B}(r_x, r_y),~ v_3 \leftarrow \widetilde{C}(r_x, r_y)$
253		\item V: abort with $b=0$ if $e_y \neq (r_A v_1 + r_B v_2 + r_C v_3) \cdot v_z$
254		\item V: output $b=1$
255	\end{enumerate}
256\end{itemize}
257
258Section 6 of the paper, describes how in step 16, instead of evaluating $\widetilde{A},~\widetilde{B},~\widetilde{C}$ at $r_x,~r_y$ with $O(n)$ costs, P commits to $\widetilde{A},~\widetilde{B},~\widetilde{C}$ and later provides proofs of openings.
259
260In a practical implementation those commits to $\widetilde{A},~\widetilde{B},~\widetilde{C}$ could be done in a preprocessing step.
261
262\vspace{1cm}
263\framebox{WIP: covered until sec.6}
264
265
266
267\bibliography{paper-notes.bib}
268\bibliographystyle{unsrt}
269
270\end{document}