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% prevent warnings of underfull \hbox:
 18\usepackage{etoolbox}
 19\apptocmd{\sloppy}{\hbadness 4000\relax}{}{}
 20
 21\theoremstyle{definition}
 22\newtheorem{definition}{Def}[section]
 23\newtheorem{theorem}[definition]{Thm}
 24
 25
 26\title{Notes on Halo}
 27\author{arnaucube}
 28\date{July 2022}
 29
 30\begin{document}
 31
 32\maketitle
 33
 34\begin{abstract}
 35	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$.
 36
 37	The notes are not complete, don't include all the steps neither all the proofs.
 38\end{abstract}
 39
 40\tableofcontents
 41
 42\section{modified IPA (from Halo paper)}
 43Notes taken while reading about the modified Inner Product Argument (IPA) from the Halo paper \cite{cryptoeprint:2019/1021}.
 44
 45\subsection{Notation}
 46\begin{description}
 47    \item[Scalar mul] $[a]G$, where $a$ is a scalar and $G \in \mathbb{G}$
 48    \item[Inner product] $<\overrightarrow{a}, \overrightarrow{b}> = a_0 b_0 + a_1 b_1 + \ldots + a_{n-1} b_{n-1}$
 49    \item[Multiscalar mul] $<\overrightarrow{a}, \overrightarrow{b}> = [a_0] G_0 + [a_1] G_1 + \ldots [a_{n-1}] G_{n-1}$
 50\end{description}
 51
 52
 53\subsection{Transparent setup}
 54$\overrightarrow{G} \in^r \mathbb{G}^d$, $H \in^r \mathbb{G}$
 55
 56Prover wants to commit to $p(x)=a_0$
 57\subsection{Protocol}
 58Prover:
 59$$P=<\overrightarrow{a}, \overrightarrow{G}> + [r]H$$
 60$$v=<\overrightarrow{a}, \{1, x, x^2, \ldots, x^{d-1} \} >$$
 61
 62where $\{1, x, x^2, \ldots, x^{d-1} \} = \overrightarrow{b}$.
 63
 64We can see that computing $v$ is the equivalent to evaluating $p(x)$ at $x$ ($p(x)=v$).
 65
 66We will prove:
 67\begin{enumerate}[i.]
 68    \item polynomial $p(X) = \sum a_i X^i$\\
 69	$p(x) = v$ (that $p(X)$ evaluates $x$ to $v$).
 70    \item $deg(p(X)) \leq d-1$
 71\end{enumerate}
 72
 73
 74Both parties know $P$, point $x$ and claimed evaluation $v$. For $U \in^r \mathbb{G}$,
 75
 76$$P' = P + [v] U = <\overrightarrow{a}, G> + [r]H + [v] U$$
 77
 78Now, for $k$ rounds ($d=2^k$, from $j=k$ to $j=1$):
 79\begin{itemize}
 80    \item random blinding factors: $l_j, r_j \in \mathbb{F}_p$
 81    \item
 82	$$L_j = < \overrightarrow{a}_{lo}, \overrightarrow{G}_{hi}> + [l_j] H + [< \overrightarrow{a}_{lo}, \overrightarrow{b}_{hi}>] U$$
 83	$$L_j = < \overrightarrow{a}_{lo}, \overrightarrow{G}_{hi}> + [l_j] H + [< \overrightarrow{a}_{lo}, \overrightarrow{b}_{hi}>] U$$
 84    \item Verifier sends random challenge $u_j \in \mathbb{I}$
 85    \item Prover computes the halved vectors for next round:
 86	$$\overrightarrow{a} \leftarrow \overrightarrow{a}_{hi} \cdot u_j^{-1} + \overrightarrow{a}_{lo} \cdot u_j$$
 87	$$\overrightarrow{b} \leftarrow \overrightarrow{b}_{lo} \cdot u_j^{-1} + \overrightarrow{b}_{hi} \cdot u_j$$
 88	$$\overrightarrow{G} \leftarrow \overrightarrow{G}_{lo} \cdot u_j^{-1} + \overrightarrow{G}_{hi} \cdot u_j$$
 89\end{itemize}
 90
 91After final round, $\overrightarrow{a}, \overrightarrow{b}, \overrightarrow{G}$ are each of length 1.
 92
 93Verifier can compute
 94$$G = \overrightarrow{G}_0 = < \overrightarrow{s}, \overrightarrow{G} >$$
 95and $$b = \overrightarrow{b}_0 = < \overrightarrow{s}, \overrightarrow{b} >$$
 96where $\overrightarrow{s}$ is the binary counting structure:
 97
 98\begin{align*}
 99    &s = (u_1^{-1} ~ u_2^{-1} \cdots ~u_k^{-1},\\
100    &~~~~~~u_1 ~~~ u_2^{-1} ~\cdots ~u_k^{-1},\\
101    &~~~~~~u_1^{-1} ~~ u_2 ~~\cdots ~u_k^{-1},\\
102    &~~~~~~~~~~~~~~\vdots\\
103    &~~~~~~u_1 ~~~~ u_2 ~~\cdots ~u_k)
104\end{align*}
105
106
107And verifier checks:
108$$[a]G + [r'] H + [ab] U == P' + \sum_{j=1}^k ( [u_j^2] L_j + [u_j^{-2}] R_j)$$
109
110where the synthetic blinding factor $r'$ is $r' = r + \sum_{j=1}^k (l_j u_j^2 + r_j u_j^{-2})$.
111
112\vspace{1cm}
113
114Unfold:
115
116$$
117\textcolor{brown}{[a]G} + \textcolor{cyan}{[r'] H} + \textcolor{magenta}{[ab] U}
118==
119\textcolor{blue}{P'} + \sum_{j=1}^k ( \textcolor{violet}{[u_j^2] L_j} + \textcolor{orange}{[u_j^{-2}] R_j})
120$$
121
122\begin{align*}
123&Right~side = \textcolor{blue}{P'} + \sum_{j=1}^k ( \textcolor{violet}{[u_j^2] L_j} + \textcolor{orange}{[u_j^{-2}] R_j})\\
124&= \textcolor{blue}{< \overrightarrow{a}, \overrightarrow{G}> + [r] H + [v] U}\\
125&+ \sum_{j=1}^k (\\
126&\textcolor{violet}{[u_j^2] \cdot <\overrightarrow{a}_{lo}, \overrightarrow{G}_{hi}> + [l_j] H + [<\overrightarrow{a}_{lo}, \overrightarrow{b}_{hi}>] U}\\
127&\textcolor{orange}{+ [u_j^{-2}] \cdot <\overrightarrow{a}_{hi}, \overrightarrow{G}_{lo}> + [r_j] H + [<\overrightarrow{a}_{hi}, \overrightarrow{b}_{lo}>] U}
128)
129\end{align*}
130
131\begin{align*}
132&Left~side = \textcolor{brown}{[a]G} + \textcolor{cyan}{[r'] H} + \textcolor{magenta}{[ab] U}\\
133& = \textcolor{brown}{< \overrightarrow{a}, \overrightarrow{G} >}\\
134&+ \textcolor{cyan}{[r + \sum_{j=1}^k (l_j \cdot u_j^2 + r_j u_j^{-2})] \cdot H}\\
135&+ \textcolor{magenta}{< \overrightarrow{a}, \overrightarrow{b} > U}
136\end{align*}
137
138
139\section{Amortization Strategy}
140TODO
141
142\bibliography{paper-notes.bib}
143\bibliographystyle{unsrt}
144
145\end{document}