1\documentclass{article}
  2\usepackage[utf8]{inputenc}
  3\usepackage{amsfonts}
  4\usepackage{amsthm}
  5\usepackage{amsmath}
  6\usepackage{enumerate}
  7\usepackage{hyperref}
  8\hypersetup{
  9    colorlinks,
 10    citecolor=black,
 11    filecolor=black,
 12    linkcolor=black,
 13    urlcolor=blue
 14}
 15\usepackage{xcolor}
 16
 17\usepackage{pgf-umlsd} % diagrams
 18% message between threads
 19% Example:
 20% \bloodymess[delay]{sender}{message content}{receiver}{DIR}{start note}{end note}
 21\newcommand{\bloodymess}[7][0]{
 22  \stepcounter{seqlevel}
 23  \path
 24  (#2)+(0,-\theseqlevel*\unitfactor-0.7*\unitfactor) node (mess from) {};
 25  \addtocounter{seqlevel}{#1}
 26  \path
 27  (#4)+(0,-\theseqlevel*\unitfactor-0.7*\unitfactor) node (mess to) {};
 28  \draw[->,>=angle 60] (mess from) -- (mess to) node[midway, above]
 29  {#3};
 30
 31  \if R#5
 32    \node (#3 from) at (mess from) {\llap{#6~}};
 33    \node (#3 to) at (mess to) {\rlap{~#7}};
 34  \else\if L#5
 35         \node (#3 from) at (mess from) {\rlap{~#6}};
 36         \node (#3 to) at (mess to) {\llap{#7~}};
 37       \else
 38         \node (#3 from) at (mess from) {#6};
 39         \node (#3 to) at (mess to) {#7};
 40       \fi
 41  \fi
 42}
 43
 44% prevent warnings of underfull \hbox:
 45\usepackage{etoolbox}
 46\apptocmd{\sloppy}{\hbadness 4000\relax}{}{}
 47
 48\theoremstyle{definition}
 49\newtheorem{definition}{Def}[section]
 50\newtheorem{theorem}[definition]{Thm}
 51
 52
 53\title{Notes on Halo}
 54\author{arnaucube}
 55\date{July 2022}
 56
 57\begin{document}
 58
 59\maketitle
 60
 61\begin{abstract}
 62	Notes taken while reading Halo paper \cite{cryptoeprint:2019/1021}. Usually while reading papers I take handwritten notes, this document contains some of them re-written to $LaTeX$.
 63
 64	The notes are not complete, don't include all the steps neither all the proofs.
 65\end{abstract}
 66
 67\tableofcontents
 68
 69\section{modified IPA (from Halo paper)}
 70Notes taken while reading about the modified Inner Product Argument (IPA) from the Halo paper \cite{cryptoeprint:2019/1021}.
 71
 72\paragraph{Objective:}
 73Prover wants to prove that the polynomial $p(X)$ from the commitment $P$ evaluates to $v$ at $x$, and that $deg(p(X)) \leq d-1$.
 74
 75\subsection{Notation}
 76\begin{description}
 77    \item[Scalar mul] $[a]G$, where $a$ is a scalar and $G \in \mathbb{G}$
 78    \item[Inner product] $<\overrightarrow{a}, \overrightarrow{b}> = a_0 b_0 + a_1 b_1 + \ldots + a_{n-1} b_{n-1}$
 79    \item[Multiscalar mul] $<\overrightarrow{a}, \overrightarrow{G}> = [a_0] G_0 + [a_1] G_1 + \ldots + [a_{n-1}] G_{n-1}$
 80\end{description}
 81
 82
 83\subsection{Transparent setup}
 84$\overrightarrow{G} \in^r \mathbb{G}^d$, $H \in^r \mathbb{G}$
 85
 86Prover wants to commit to $p(x)=a_0$
 87\subsection{Protocol}
 88Prover:
 89$$P=<\overrightarrow{a}, \overrightarrow{G}> + [r]H$$
 90$$v=<\overrightarrow{a}, \{1, x, x^2, \ldots, x^{d-1} \} >$$
 91
 92where $\{1, x, x^2, \ldots, x^{d-1} \} = \overrightarrow{b}$.
 93
 94We can see that computing $v$ is the equivalent to evaluating $p(X)$ at $x$ ($p(x)=v$).
 95
 96We will prove:
 97\begin{enumerate}[i.]
 98    \item polynomial $p(X) = \sum a_i X^i$\\
 99	$p(x) = v$ (that $p(X)$ evaluates $x$ to $v$).
100    \item $deg(p(X)) \leq d-1$
101\end{enumerate}
102
103
104Both parties know $P$, point $x$ and claimed evaluation $v$. For $U \in^r \mathbb{G}$.
105
106Prover computes $P'$:
107
108$$P' = P + [v] U = <\overrightarrow{a}, G> + [r]H + [v] U$$
109
110Now, for $k$ rounds ($d=2^k$, from $j=k$ to $j=1$):
111\begin{itemize}
112    \item Prover sets random blinding factors: $l_j, r_j \in \mathbb{F}_p$
113    \item Prover computes
114	$$L_j = < \overrightarrow{a}_{lo}, \overrightarrow{G}_{hi}> + [l_j] H + [< \overrightarrow{a}_{lo}, \overrightarrow{b}_{hi}>] U$$
115	$$R_j = < \overrightarrow{a}_{hi}, \overrightarrow{G}_{lo}> + [r_j] H + [< \overrightarrow{a}_{hi}, \overrightarrow{b}_{lo}>] U$$
116    \item Verifier sends random challenge $u_j \in \mathbb{I}$
117    \item Prover computes the halved vectors for next round:
118	$$\overrightarrow{a} \leftarrow \overrightarrow{a}_{hi} \cdot u_j^{-1} + \overrightarrow{a}_{lo} \cdot u_j$$
119	$$\overrightarrow{b} \leftarrow \overrightarrow{b}_{lo} \cdot u_j^{-1} + \overrightarrow{b}_{hi} \cdot u_j$$
120	$$\overrightarrow{G} \leftarrow \overrightarrow{G}_{lo} \cdot u_j^{-1} + \overrightarrow{G}_{hi} \cdot u_j$$
121\end{itemize}
122
123After final round, $\overrightarrow{a}, \overrightarrow{b}, \overrightarrow{G}$ are each of length 1.
124
125Verifier can compute
126$$G = \overrightarrow{G}_0 = < \overrightarrow{s}, \overrightarrow{G} >$$
127and $$b = \overrightarrow{b}_0 = < \overrightarrow{s}, \overrightarrow{b} >$$
128where $\overrightarrow{s}$ is the binary counting structure:
129
130\begin{align*}
131    &s = (u_1^{-1} ~ u_2^{-1} \cdots ~u_k^{-1},\\
132    &~~~~~~u_1 ~~~ u_2^{-1} ~\cdots ~u_k^{-1},\\
133    &~~~~~~u_1^{-1} ~~ u_2 ~~\cdots ~u_k^{-1},\\
134    &~~~~~~~~~~~~~~\vdots\\
135    &~~~~~~u_1 ~~~~ u_2 ~~\cdots ~u_k)
136\end{align*}
137
138
139And verifier checks:
140$$[a]G + [r'] H + [ab] U == P' + \sum_{j=1}^k ( [u_j^2] L_j + [u_j^{-2}] R_j)$$
141
142where the synthetic blinding factor $r'$ is $r' = r + \sum_{j=1}^k (l_j u_j^2 + r_j u_j^{-2})$.
143
144\vspace{1cm}
145
146Unfold:
147
148$$
149\textcolor{brown}{[a]G} + \textcolor{cyan}{[r'] H} + \textcolor{magenta}{[ab] U}
150==
151\textcolor{blue}{P'} + \sum_{j=1}^k ( \textcolor{violet}{[u_j^2] L_j} + \textcolor{orange}{[u_j^{-2}] R_j})
152$$
153
154\begin{align*}
155&Left~side = \textcolor{brown}{[a]G} + \textcolor{cyan}{[r'] H} + \textcolor{magenta}{[ab] U}\\
156& = \textcolor{brown}{< \overrightarrow{a}, \overrightarrow{G} >}\\
157&+ \textcolor{cyan}{[r + \sum_{j=1}^k (l_j \cdot u_j^2 + r_j u_j^{-2})] \cdot H}\\
158&+ \textcolor{magenta}{< \overrightarrow{a}, \overrightarrow{b} > U}
159\end{align*}
160
161
162\begin{align*}
163&Right~side = \textcolor{blue}{P'} + \sum_{j=1}^k ( \textcolor{violet}{[u_j^2] L_j} + \textcolor{orange}{[u_j^{-2}] R_j})\\
164&= \textcolor{blue}{< \overrightarrow{a}, \overrightarrow{G}> + [r] H + [v] U}\\
165&+ \sum_{j=1}^k (
166\textcolor{violet}{[u_j^2] \cdot <\overrightarrow{a}_{lo}, \overrightarrow{G}_{hi}> + [l_j] H + [<\overrightarrow{a}_{lo}, \overrightarrow{b}_{hi}>] U}\\
167&\textcolor{orange}{+ [u_j^{-2}] \cdot <\overrightarrow{a}_{hi}, \overrightarrow{G}_{lo}> + [r_j] H + [<\overrightarrow{a}_{hi}, \overrightarrow{b}_{lo}>] U}
168)
169\end{align*}
170
171
172\vspace{1.5cm}
173The following diagram ilustrates the main steps in the scheme:
174
175\begin{center}
176\begin{sequencediagram}
177    \newinst[1]{p}{Prover}
178    \newinst[3]{v}{Verifier}
179
180    \bloodymess[1]{p}{P}{v}{R}{knows $p(X)\in \mathbb{F[X]}$, commits to $p(X)$, $P$}{rand $x \in \mathbb{F},~U\in \mathbb{G},~\overrightarrow{u} \in \mathbb{F}^d$}
181    \bloodymess[1]{v}{$x, U, u$}{p}{R}{}{}
182    \bloodymess[1]{p}{$proof, a, L_j, R_j, v$}{v}{R}{gen proof}{$verify(proof, P, a, x, L_j, R_j)$}
183
184    % \begin{callself}{p}{knows $p(X) \in \mathbb{F}[X]$}{}
185    % \end{callself}
186    % \begin{callself}{p}{commit to $p(X),~P$}{}
187    % \end{callself}
188    % 
189    % \mess[0]{p}{$P$}{v}
190    % \begin{callself}{v}{rand $x \in \mathbb{F},~U\in \mathbb{G},~\overrightarrow{u} \in \mathbb{F}^d$}{}
191    % \end{callself}
192    % 
193    % \mess[0]{v}{$x,U,u$}{p}
194
195    % \node[anchor=west] (p2) at (mess to) {gen proof2}
196
197    % \begin{callself}{p}{gen proof $\pi$}{}
198    % \end{callself}
199    % 
200    % \mess[0]{p}{$a, L_j, R_j, v$}{v}
201    % 
202    % \begin{callself}{v}{$verify(P, a, x, v, L_j, R_k$)}{}
203    % \end{callself}
204\end{sequencediagram}
205\end{center}
206
207\section{Amortization Strategy}
208TODO
209
210\bibliography{paper-notes.bib}
211\bibliographystyle{unsrt}
212
213\end{document}