digitalcash.tex

\documentclass{article}
\title{The Mathematics of Digital Cash}
\date{2018-12-23}
\author{Joey Yandle}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mathtools}
%\usepackage{overunderset}
\newcommand\Set[2]{\{\,#1\mid#2\,\}}
\newcommand\underoverset[3]{\underset{#1}{\overset{#2}{#3}}}
\usepackage{geometry}
 \geometry{
   a4paper,
   total={170mm,257mm},
   left=20mm,
   top=20mm,
 }
\begin{document}
\begin{figure}
  \includegraphics[width=\linewidth]{digitalcash.png}
\end{figure}
\maketitle

While traditional cryptocurrencies were groundbreaking in many ways, they lacked the privacy protections that cash inherently provides.  This document will explore the math which can provide some of those protections.  The goal is to build a cryptocurrency which deserves the name Digital Cash.

There are many papers which outline, define, use, mutate, expand on, or cite the following techniques.  But these papers invariably use different terminology, swapping variable names and using various subsets as needed.  In this document, I will endeavor to be both thorough and strongly consistent, which should not only make the math easier to understand, but also expose the deep connections and demonstrate how each piece builds on the previous.
\newpage


\section{
  Notation
}

We define a hash function $H_n$ as a function that maps an unbounded list of arbitrarily-sized binary inputs to an output set $O$ of $n$ bits:
\begin{align}
  H_n \coloneqq \Set{i_1, i_2, ...}{b \in \{0,1\}, k \in \mathbb{N}, i \in {b_1b_2...b_k}} \mapsto \Set{b_1b_2...b_n}{b \in \{0,1\}}\nonumber
\end{align}

If we do not define $n$, then we assume it is implementation dependent, but that the output set is still bounded at some $n$ bits:
\begin{align}
  H \coloneqq \Set{i_1, i_2, ...}{b \in \{0,1\}, k \in \mathbb{N}, i \in {b_1b_2...b_k}} \mapsto \Set{b_1b_2...b_n}{b \in \{0,1\}}\nonumber
\end{align}


\section{
  Schnorr Proofs and the Fiat Shamir Transform
}

Schnorr proofs \cite{schnorr} allow the owner of a private key to demonstrate that ownership to someone who knows the corresponding public key.  It is an interactive 3-move protocol, i.e. a Sigma protocol.  But like all Sigma protocols, it can be made non-interactive using the Fiat-Shamir transform \cite{fiatshamir}.  This allows the protocol to function as a signature.

Let $g$ be a generator in a finite group $G$ of prime order $p \in \mathbb{P}$, with private key $x \in \mathbb{Z}_p$, and public key $y = g^x$. The prover chooses a random $v \in Z_p$, then sets $t = g^v$.

In the interactive version of the protocol, the prover sends $t$ to the verifier, who responds with the challenge $c$.  This way the prover cannot choose $t$ after seeing $c$, which would allow the prover to cheat.  To make this non-interactive, Fiat and Shamir proposed to choose $c$ based on a hash including $t$, which prevents the prover from cheating, since $c$ depends on $t$:
\begin{align}
  c = H(g,y,t)
\end{align}

The prover then defines $r$ as below, and calculates it from $(v, c, x)$:
\begin{align}
  r = v - cx
\end{align}
 
This is equivalent algebraically to
\begin{align}
  v = r + cx \nonumber
\end{align}

We can use this derived expression for $v$ to expand $t$:
\begin{align}
  t = g^v= g^{r + c x} = g^r g^{cx} = g^r g^{xc} = g^r (g^x)^c = g^r y^c
\end{align}

So if $t = g^r y^c$, then the prover must have known $x$.  Otherwise the prover would not have been able to construct a proper $r$, allowing the equation to balance.  The set $(r,c,t)$ thus forms the proof of ownership of $y$.



\section{Ring signatures}

A Schnorr proof allows us to sign a public key, proving we know the corresponding private key.  But the signature is tied to a single key, which is bad for privacy.  It would be better to construct a one out of many signature, to prove that we knew the private key for one out of $N$ public keys.  Such a signature is called a ring signature \cite{cryptonote}.

Start with public key $y$ for which the prover knows the private key $x$, and as before, choose a random $v \in \mathbb{Z}_p$ . To mix in an additional key $y_1$ whose private key $x_1$ is unknown, select a random $r_1$ and $c_1$.  The prover sets $c$ as follows, using the values known to calculate it:
\begin{align}
  c = H(g^v, g^{r_1} y^{c_1}) - c_1
\end{align}

This is equivalent algebraically to:
\begin{align}
  c + c_1 = H(g^v, g^{r_1} y^{c_1})\nonumber
\end{align}

Now that the prover has c, r is as before:
\begin{align}
  r = v - cx
\end{align}

The prover then sends $(y, r, c, y_1, r_1, c_1)$ to the verifier, who then calculates the hash
\begin{align}
  H(g^r y^c, g^{r_1} y_1^{c_1})\nonumber
\end{align}

Since $g^v = g^r y^c$, the two hashes are identical.  Thus 
\begin{align}
  c + c_1 = H(g^r y^c, g^{r_1} y_1^{c_1})
\end{align}

So if $\sum c$ is equal to the hash, then the prover must have known $x$ for some $y$.  And since the prover can put the real $(y,r,c)$ in either position, there is no way for the verifier to know which key was actually signed.

We can do the same for any number of additional public keys $y_k$: choose a random $(r_k,c_k)$ which is added to the hash in the form of $g^{r_k}y_k^{c_k}$ then subtracting the new $c_k$ from the hash to form the real $c$. Then $\sum c$ will be equal to the hash for both prover and verifier.



\subsection{Linkable Ring Signatures}

Now that we can use ring signatures to hide which public key is being signed, we have a new problem: assuming each public key corresponds to a spendable output, how do we know which output was actually spent?  We need a way to track this to prevent double spends, but in such a way that we preserve the privacy which the ring signature grants.

First we construct a key image \cite{cryptonote}, which is a commitment to the public key used but cannot be used to find the public or private keys, and is unique:
\begin{align}
  I = H(y)^x
\end{align}

We then add a term to the hash for each $y$ that uses the key image.  For the real $y$, we know that
\begin{align}
  H(y)^v &= H(y)^r H(y)^{cx}\nonumber\\
         &= H(y)^r (H(y)^x)^c\nonumber\\
         &= H(y)^r I^c
\end{align}

Putting the real $y$ first, the prover hash becomes:
\begin{align}
  H(g^v, H(y)^v, g^{r_1} y^{c_1}, H(y_1)^{r_1} I^{c_1})
\end{align}

We define $c$ as before, then solve for the hash:
\begin{align}
  c &= H(g^v, H(y)^v, g^{r_1} y^{c_1}, H(y_1)^{r_1} I^{c_1}) - c_1\\
  c_1 + c &= H(g^v, H(y)^v, g^{r_1} y^{c_1}, H(y_1)^{r_1} I^{c_1})\nonumber
\end{align}

So as before, $\sum c$ is equal to the hash.  The prover now sends $(I, y, r, c, y_1, r_1, c_1)$ to the verifier, who can check that their hash is still equal to $\sum c$:
\begin{align}
  c + c_1 = H(g^r y^c, H(y)^r I^c, g^{r_1} y^{c_1}, H(y)^{r_1} I^{c_1})
\end{align}

Since the key image $I$ is now tied to the signature, any attempt to sign two different ring signatures with the same y will result in the same $I$, so preventing double spends is easy.  You just keep track of which key images have previously been used, and reject any new signatures with a previously used $I$.


\subsection{Linkable Spontaneous Anonymous Group Signatures}

Linkable ring signatures do a good job of proving ownership while obscuring origins, but they get large as the number of mixins rises. LSAG signatures address this by constructing the $c$ terms via an iterative process, so it is only necessary to send one of them.  For a large ring, this results in nearly 33\% space savings.

Consider a set of public keys $y_i, i \in \{0, …, n-1\}$ with a secret index $j$ which denotes the public key to which we know the corresponding private key $x$.  As before, choose random $v$, and $r_i$ $\forall i \ne j$.  As with linkable signatures, define $I = H(y_j)^x$. Then define
\begin{align}
      L_j &= g^v\\
      R_j &= H(y_j)^v\\
  c_{j+1} &= H(L_j,R_j)
\end{align}

For the remaining $i \in \{j+1, …, n, …, j-1\}$ ($\mod{n}$ so $n$ goes to zero, then back to $j$)
\begin{align}
  L_i &= g^{r_i} {y_i}^{c_i}\\
  R_i &= H(y_i)^{r_i} I^{c_i}\\
  c_{i+1} &= H(L_i,R_i)\\
  &... \nonumber\\
  c_j &= H(L_{j-1}, R_{j-1})
\end{align}

Now that we have $c_j$, we can define
\begin{align}
  r_j = v - c_j x
\end{align}

Then we can calculate $L_j$ and $R_j$ as we did for all $L_i$ and $R_i$, using $r_j$ and $c_j$, and the values should be equal to the original $L_j$ and $R_j$ calculated using $v$. The prover now sends $(I, y_0, r_0, …, y_{n-1}, r_{n-1}, c_0)$ to the verifier.  The verifier can reconstruct all $(c_i, L_i, R_i)$ and then check that $c_0 = c_n$.


\subsection{Multilayered LSAG Signatures}

LSAG signatures allow a compact representation of a linked ring signature, but each real key needs its own signature, and there is no way to associate the real keys with interleaved data.

The MLSAG solves this by using key vectors rather than single keys \cite{ringct}.  So key $y_i$ is instead a vector of $m$ keys
\begin{align}
  y_i = (y_{i,0}, ..., y_{i,m-1})
\end{align}

As before, there exists a secret index $j$, for which we know the private keys to each public key.  Each $r_i$ is now also a vector, and
\begin{align}
  r_i = (r_{i,0}, ..., r_{i,m-1})
\end{align}

$\forall i \ne j$, $r_i$ consists of random numbers.

The prover proceeds as with an LSAG, starting with index $j$.  $v$ is now a vector of $m$ elements.  The $L_{j,k}$ and $R_{j,k}$ entries are calculated in the same way, but using $y_{j,k}$ and $v_k$.  $c_{j+1}$ is calculated using all $L_{j,k}$ and $R_{j,k}$:
\begin{align}
  L_{j,k} &= g^{v_k}\\
  R_{j,k} &= H(y_{j,k})^{v_k}\\
  c_{j+1} &= H(L_{j,0}, R_{j,0}, ..., L_{j,m-1}, R_{j,m-1})
\end{align}

As before, the prover calculates the remaining $L_i$ and $R_i$ using the corresponding $c_i$, $r_i$, and $I$, and the hash for $c_{i+1}$ contains the full set of $L_{i,k}$ and $R_{i,k}$:
\begin{align}
  L_{i,k} &= g^{r_{i,k}} y_{i,k}^{c_i}\\
  R_{i,k} &= H(y_i)^{r_{i,k}} I^{c_i}\\
  c_{i+1} &= H(L_{i,0}, R_{i,0}, ..., L_{i,m-1}, R_{i,m-1}) \\
  &... \\
  c_j &= H(L_{j-1,0}, R_{j-1,0}, ..., L_{j-1,m-1}, R_{j-1,m-1}) 
\end{align}

Now that we have $c_j$, we can calculate the $r_{j,k}$ as before:
\begin{align}
  r_{j,k} = v_k - c_j x_k
\end{align}

The prover sends the same set of $(I, y_0, r_0, ..., y_{m-1}, r_{m-1}, c_0)$ as for LSAG, but each $y_i$ and $r_i$ is now a vector.  The verifier again calculates the full set of $c_i$, with corresponding $L_i$ and $R_i$, and checks that $c_0 = c_n$.


\subsection{Signing external data}

Schnorr proofs and ring signatures do a good job of signing public keys, with a variety of options for obfuscating mixins and consolidating space.  But it is often desirable to sign external data, such as a transaction body.  This way the signature validates not only ownership of the inputs, but also locks the signature to the spent outputs, amounts, or any other metadata which is necessary to prevent transaction malleability.

To sign external data $d$, take a hash of it then prepend it to the signature hash.  But hashing the external data directly can lead to collisions, which obviates the point of hashing.  So it is common to use domain separators in the hash:
\begin{align}
  m = H(\textsf{"transaction body"}, d)
\end{align}

For a standard linkable ring signature, the prover would do the following:
\begin{align}
  c + c1 = H(m, g^v, H(y)^v, g^{r_1} y^{c_1}, H(y)^{r_1} I^{c_1})
\end{align}

The verifier also has access to the external data, and does the same calculation:
\begin{align}
  m &= H(\textsf{"transaction body"}, d)\\
  c+c1 &= H(m, g^r y^c, H(y)^r I^c, g^{r_1} y^{c_1}, H(y)^{r_1} I^{c_1})
\end{align}

This links the signature to the external data, and if the data is altered the verifier signature will fail validation.



\section{Confidential Transactions}

Using linkable ring signatures, we can obscure (but not hide) the real inputs to a transaction.  However, the amounts of each input must be visible in order to show that the transaction does not generate free coins: the sum of the inputs must equal the sum of the outputs.  How can we hide the actual amounts, while keeping the ability to check that the transaction is balanced?


\subsection{Pedersen Commitments}

We can again use the difficulty of solving discrete logarithms to hide the real amounts behind a commitment.  The naive approach would be to simply raise our group generator $g$ to the value $v$:
\begin{align}
  C=g^v
\end{align}

Then we can check that the sum of the input values is equal to the sum of the outputs:
\begin{align}
  v_{i_1} + v_{i_2} &= v_{o_1} + v_{o_2}\\
  g^{v_{i_1} + v_{i_2}} &= g^{v_{o_1} + v_{o_2}}\\
  g^{v_{i_1}} g^{v_{i_2}} &= g^{v_{o_1}} g^{v_{o_2}}\\
  C_{i_1} C_{i_2} &= C_{o_1} C_{o_2}
\end{align}
  
So to check that the transaction is balanced, we check the product of the input commitments against the product of the output commitments: if they are equal, then the transaction is balanced.

This simple approach does not work, however, because the range of values in a cryptocurrency is usually only $[0, 2^{64})$.  So an attacker can brute force any commitment by trying all $2^{64}$ possible values.  To prevent this, we add a random blinding factor $s$ to the commitment \cite{ringct}:
\begin{align}
  C = g^s h^v
\end{align}
  
This requires another generator $h$, which is usually defined as a hash-to-group of the generator $g$.  If the group is a prime order group, then any element of the group is a generator, and so a simple hash will suffice.  Otherwise, care must be made to assure that $h$ is orthogonal to $g$.

Now when we check the transaction balance, we end up with
\begin{align}
  \frac{C_{i_1} C_{i_2}}{C_{o_1} C_{o_2}} &= \frac{g^{s_{i_1}} h^{v_{i_1}} g^{s_{i_2}} h^{v_{i_2}}}{g^{s_{o_1}} h^{v_{o_1}} g^{s_{o_2}} h^{v_{o_2}}}\\
                                          &= g^{s_{i_1} + s_{i_2} - s_{o_1} - s_{o_2}} h^{v_{i_1} + v_{i_2} - v_{o_1} - v_{o_2}}
\end{align}

But if the transaction is balanced, then $v_{i_1} + v_{i_2} - v_{o_1} - v_{o_2} = 0$, so
\begin{align}
  \frac{C_{i_1} C_{i_2}}{C_{o_1} C_{o_2}} = g^{s_{i_1} + s_{i_2} - s_{o_1} - s_{o_2}}
\end{align}

We define the sum of the input blinding factors minus the output blinding factors to be
\begin{align}
  z = s_{i_1} + s_{i_2} - s_{o_1} - s_{o_2}
\end{align}

Which means that the ratio of the product of the commitments is now just $g^z$, and thus we know the private key $z$ which corresponds to the public key generated from the commitments:
\begin{align}
  \frac{C_{i_1} C_{i_2}}{C_{o_1} C_{o_2}} = g^z
\end{align}

We already know how to sign a public key if we know the private key, which means we can sign this commitment to zero, and a verifier can check it.  This allows a verifier to validate the transaction is balanced.


\subsection{Range Proofs}

Now that the values can be hidden, we have a new problem.  Since we are checking that the sum of the inputs matches the sum of the outputs, what happens if one of the output values is negative?  The transaction will be balanced, but we will end up minting new coins.  How can we prevent this?  The answer is via the use of range proofs \cite{ringct}.

First, consider a $n$-bit binary expansion of $v$:
\begin{align}
  v = b_0 2^0 + b_1 2^1 + ... + b_{n-1} 2^{n-1}
\end{align}

If $v$ is in the range $[0, 2^{64})$ then we know that each $b_k \in {0, 1}$.  Remember that we committed to $v$ with $C = g^s h^v$.  Choose a series of $s_k$ such that
\begin{align}
  \sum_0^{n-1} s_k = s 
\end{align}

Then write commitments for each bit in the binary expansion thus
\begin{align}
  C_k = g^{s_k} h^{b_k 2^k}
\end{align}

As before, the sum of the values in these commitments will be equal to $v$, but also the sum of the bit blinding factors $s_k$ will also equal $s$.  So
\begin{align}
  C_k = C
\end{align}

This allows the validator to check that the binary expansion is valid.  And if each $b_k \in {0, 1}$, then one of the following must be a commitment to zero:
\begin{align}
  \{g^{s_k} h^{b_k 2^k}, g^{s_k} h^{b_k 2^k - 2^k}\}
\end{align}

So either the first or the second terms will reduce to $g^{s_k}$, and since the prover know $s_k$ he can sign the ring.  We don't need linkability, so we can use basic ring signatures of size $2$. The prover of course knows which term is actually a commitment to zero, and can sign accordingly.

The range proof thus consists of the $n$ bit commitments $C_i$ and corresponding ring signatures.  The verifier checks the validity of each bit proof, and then verifies that
\begin{align}
  C = \prod{C_i}
\end{align}



\section{Bulletproofs}

Range proofs allow us to verify that output commitments are not negative, but they use a lot of space; each output range proof consists of $64$ separate ring signatures.  It would be preferable to somehow consolidate them, and there are a variety of techniques to do so.  Bulletproofs \cite{bulletproofs} are a compact way to represent aggregated range proofs, and result in significant space savings.

Bulletproofs are not just useful as aggregated range proofs; more generally, they also have the ability to represent arbitrary arithmetic circuits.  They have similar functionality with zkSNARKs, but require no trusted setup.

\subsection{Notation}

The bulletproofs paper uses several notation systems.  Some were innovative, like the use of boldfaced group elements to represent that they were arrays.  Some were just obscure, like using the $\circ$ operator to denote pairwise multiplication of vectors,  But other, like using the python$[:n]$ array slicing operator were verbose and annoying.  So pretty much everyone who implented, or tried to explain bulletproofs, ended up replacing something with their own.  Here I will limit myself to replacing the $[:n]$ operator with $B$ for the bottom half and $T$ for the top.  We can do this because we are only ever dealing with powers of two, so it is never ambiguous.

\subsection{Improved Inner Product Argument}

The heart of a bulletproof is a vector commitment that links a committed value with an inner product.  The prover uses a recursive protocol that at every step cuts the size of the vectors in half and generates a new commitment, until only a single element remains, then sends the final values with the corresponding generators and commitment as the proof.  The verifier checks that the final commitment is valid, then unwinds the stack.

So for some $(\textbf{g}, \textbf{h}) \in \mathbb{G}^n$, $(\textbf{a}, \textbf{b}) \in \mathbb{Z}_p^n$, $(u, P) \in \mathbb{G}$, $c \in \mathbb{Z}_p$, let $P = \textbf{g}^\textbf{a} \textbf{h}^\textbf{b}$ and $c = \left<\textbf{a}, \textbf{b}\right>$.  The goal is to find a way to prove knowledge of $\textbf{a}$ and $\textbf{b}$ to someone who knows $P$ and $c$, without revealing them.  To do this, the prover adds the inner product to the commitment itself:
\begin{align}
  P = \textbf{g}^\textbf{a} \textbf{h}^\textbf{b} \cdot u^{\left<\textbf{a}, \textbf{b}\right>}
\end{align}

Since the goal is to shrink the problem in half, let $n' = n/2$.  Since $(\textbf{g}, \textbf{h})$ are still size $n$, split each into bottom $(\textbf{g}_{B}, \textbf{h}_{B})$ and top $(\textbf{g}_{T}, \textbf{h}_{T})$, with the first $n'$ elements in the bottom vector and the second $n'$ in the top.  Then for some $\textbf{a}_1, \textbf{a}'_2, \textbf{b}_1, \textbf{b}'_2 \in \mathbb{Z}_p^n$, define the function $H$ to operate on the split vectors. 
\begin{align}
  H(\textbf{a}_1, \textbf{a}'_2, \textbf{b}_1, \textbf{b}'_2, c) = \textbf{g}_{B}^{\textbf{a}_1} \textbf{g}_{T}^{\textbf{a}'_2} \textbf{h}_{B}^{\textbf{b}_1} \textbf{h}_{T}^{\textbf{b}'_2} \cdot u^c
\end{align}

We can define $P$ in terms of $H$, splitting the real $(\textbf{a}, \textbf{b})$ as well into bottom and top:
\begin{align}
  P &= \textbf{g}^{\textbf{a}} \textbf{h}^{\textbf{b}} \cdot u^{\left<a, \textbf{b}\right>}\\
    &= \textbf{g}_{B}^{\textbf{a}_{B}} \textbf{g}_{T}^{\textbf{a}_{T}} \textbf{h}_{B}^{\textbf{b}_{B}} \textbf{h}_{T}^{\textbf{b}_{T}} \cdot u^{\left<\textbf{a}, \textbf{b}\right>}\\
    &= H(\textbf{a}_{B}, \textbf{a}_{T}, \textbf{b}_{B}, \textbf{b}_{T}, \left<\textbf{a}, \textbf{b}\right>)
\end{align}

$H$ is additively homomorphic:
\begin{align}
  H(\textbf{a}_1, & \textbf{a}'_1, \textbf{b}_1, \textbf{b}'_1, c_1) \cdot H(\textbf{a}_2, \textbf{a}'_2, \textbf{b}_2, \textbf{b}'_2, c_2) = H(\textbf{a}_1 + \textbf{a}_2, \textbf{a}'_1 + \textbf{a}'_2, \textbf{b}_1 + \textbf{b}_2, \textbf{b}'_1 + \textbf{b}'_2, c_1 + c_2)
\end{align}

Now define $L, R \in \mathbb{G}$:
\begin{align}
  L &= H(\textbf{0}^{n'}, \textbf{a}_{B}, \textbf{b}_{T}, \textbf{0}^{n'}, \left<\textbf{a}_{B}, \textbf{b}_{T}\right>)\\
  R &= H(\textbf{a}_{T}, \textbf{0}^{n'}, \textbf{0}^{n'}, \textbf{b}_{B}, \left<\textbf{a}_{T}, \textbf{b}_{B}\right>)
\end{align}

Prover sends $(L, R)$ to the verifier, who responds with the challenge $x \in \mathbb{Z}_p$.  Prover then combines the left and right parts of (\textbf{a}, \textbf{b}) into single vectors using the challenge:
\begin{align}
  \textbf{a}' &= x \textbf{a}_{B} + x^{-1} \textbf{a}_{T}\\
  \textbf{b}' &= x^{-1} \textbf{b}_{B} + x \textbf{b}_{T}
\end{align}

Prover sends $(\textbf{a}', \textbf{b}')$ to verifier, who first computes $P'$ from $(P, L, R, x)$:
\begin{align}
  P' = L^{(x^2)} \cdot P \cdot R^{(x^{-2})}
\end{align}

Verifier then uses $(x, \textbf{a}', \textbf{b}')$ to calculate $Q'$:
\begin{align}
  Q' = H(x^{-1} \textbf{a'}, x \textbf{a'}, x \textbf{b'}, x^{-1} \textbf{b'}, \left<\textbf{a'}, \textbf{b'}\right>)
\end{align}

Verifier validates if $P' = Q'$.  If we expand $Q'$ we can see why:
\begin{align}
  Q' = H(&x^{-1}(x \textbf{a}_{B} + x^{-1} \textbf{a}_{T}), x(x \textbf{a}_{B} + x^{-1} \textbf{a}_{T}),
         x(x^{-1} \textbf{b}_{B} + x \textbf{b}_{T}), x^{-1}(x^{-1} \textbf{b}_{B} + x \textbf{b}_{T}),\nonumber\\
         &\left<x \textbf{a}_{B} + x^{-1} \textbf{a}_{T}, x^{-1} \textbf{b}_{B} + x \textbf{b}_{T}\right>)\nonumber\\
     = H(&\textbf{a}_{B} + x^{-2} \textbf{a}_{T}, x^2 \textbf{a}_{B} + \textbf{a}_{T},
          \textbf{b}_{B} + x^2 \textbf{b}_{T}, x^{-2} \textbf{b}_{B} + \textbf{b}_{T},
          x^2 \left<\textbf{a}_{B}, \textbf{b}_{T}\right> + \left<\textbf{a}, \textbf{b}\right> + x^{-2} \left<\textbf{a}_{T}, \textbf{b}_{B}\right>)
\end{align}

It's because we get the same thing when we expand $P'$:
\begin{align}
  P' = H(&\textbf{0}^{n'}, x^2 \textbf{a}_{B}, x^2 \textbf{b}_{T}, \textbf{0}^{n'}, x^2 \left<\textbf{a}_{B}, \textbf{b}_{T}\right>) \cdot 
       H(\textbf{a}_{B}, \textbf{a}_{T}, \textbf{b}_{B}, \textbf{b}_{T}, \left<\textbf{a}, \textbf{b}\right>) \cdot \nonumber\\
       H(&x^{-2} \textbf{a}_{T}, \textbf{0}^{n'}, \textbf{0}^{n'}, x^{-2} \textbf{b}_{B}, x^{-2} \left<\textbf{a}_{T}, \textbf{b}_{B}\right>)\nonumber\\
     = H(&\textbf{a}_{B} + x^{-2} \textbf{a}_{T}, x^2 \textbf{a}_{B} + \textbf{a}_{T},
          \textbf{b}_{B} + x^2 \textbf{b}_{T}, x^{-2} \textbf{b}_{B} + \textbf{b}_{T},
          x^2 \left<\textbf{a}_{B}, \textbf{b}_{T}\right> + \left<\textbf{a}, \textbf{b}\right> + x^{-2} \left<\textbf{a}_{T}, \textbf{b}_{B}\right>)
\end{align}

So if the prover can construct $(L, R, \textbf{a'}, \textbf{b'})$ such that $P' = Q'$, then he must have known $(\textbf{a}, \textbf{b})$.


\subsection{Range Proof Using Inner Product}

Let $\textbf{a}_L$ be a vector with the $n$ bits of $v$.  Then the following must all be true:
\begin{align}
  \left<\textbf{a}_L, 2^n\right> = v ; \textbf{a}_L \circ  \textbf{a}_R = \textbf{0}^n ; \textbf{a}_R = \textbf{a}_L - \textbf{1}^n
\end{align}
  
$\textbf{a}_R$ is defined to be the negation of $\textbf{a}_L$: $0$ where $1$, and $-1$ where $0$.  So any pairwise multiplication between $\textbf{a}_R$ and $\textbf{a}_L$ will be $0$.

Given a verifier chosen $y \in \mathbb{G}$, these relations are equivalent to:
\begin{align}
  \left<\textbf{a}_L, 2^n\right> = v ; \left<\textbf{a}_L, \textbf{a}_R \circ y^n\right> = 0 ; \left<\textbf{a}_L - \textbf{1}^n - \textbf{a}_R, \textbf{y}^n\right> = 0
\end{align}

As before, pairwise multiplication between $\textbf{a}_R$ and $\textbf{a}_L$ will be $0$, regardless of multiplying by $\textbf{y}^n$, and summing the dot product will likewise be $0$. And solving the third relation for $0$ gives us another dot product of $0$ with our new $\textbf{y}^n$.

Using another verifier chosen $z \in \mathbb{G}$, we can combine these into one relation:
\begin{align}
  z^2 \cdot \left<\textbf{a}_L, 2^n\right> + z \cdot \left<\textbf{a}_L - 1^n - \textbf{a}_R, y^n\right> + \left<\textbf{a}_L, \textbf{a}_R \circ \textbf{y}^n\right> = z^2 v
\end{align}

Multiplying the first relation by $z^2$ gives us the $z^2 v$ term, and since the other two relations were $0$ we can add them for free (swapping order and multiplying one by $z$).

If we expand the inner products, then start isolating prover and verifier terms, we get:
\begin{align}
  z^2 \cdot \left<\textbf{a}_L, \textbf{2}^n\right> + z \cdot \left<\textbf{a}_L, \textbf{y}^n\right> - z \cdot \left<\textbf{1}^n, \textbf{y}^n\right> - z \cdot \left<\textbf{a}_R, \textbf{y}^n\right> + \left<\textbf{a}_L, \textbf{a}_R \circ \textbf{y}^n\right> = z^2 v\nonumber\\
  z^2 \cdot \left<\textbf{a}_L, \textbf{2}^n\right> + z \cdot \left<\textbf{a}_L, \textbf{y}^n\right> - z \cdot \left<\textbf{a}_R, \textbf{y}^n\right> + \left<\textbf{a}_L, \textbf{a}_R \circ \textbf{y}^n\right> = z^2 v + z \cdot \left<\textbf{1}^n, \textbf{y}^n\right>\nonumber
\end{align}

Since an inner product $\left<\textbf{a}, \textbf{b}\right>$ can be broken into a pairwise/inner product $\left<\textbf{1}^n, \textbf{a} \textbf{b}\right>$:
\begin{align}
  z^2 \cdot \left<\textbf{a}_L, \textbf{2}^n\right> + z \cdot \left<\textbf{a}_L, \textbf{y}^n\right> - z \cdot \left<\textbf{1}^n, \textbf{a}_R \circ \textbf{y}^n\right> + \left<\textbf{a}_L, \textbf{a}_R \circ \textbf{y}^n\right> = z^2 v + z \cdot \left<\textbf{1}^n, \textbf{y}^n\right>\nonumber\\
  \left<\textbf{a}_L, z^2 \cdot \textbf{2}^n + z \cdot \textbf{y}^n\right> + \left<\textbf{a}_L - z \cdot \textbf{1}^n, \textbf{a}_R \circ \textbf{y}^n\right> = z^2 v + z \cdot \left<\textbf{1}^n, \textbf{y}^n\right>\nonumber
\end{align}

In order to merge the inner products via the first term, add $\left<-z \textbf{1}^n, z^2 \textbf{2}^n + z \textbf{y}^n\right>$:
\begin{align}
  \left<\textbf{a}_L - z \cdot \textbf{1}n, z^2 \cdot \textbf{2}^n + z \cdot \textbf{y}^n + \textbf{a}_R \circ \textbf{y}^n\right> = z^2 v + z \cdot \left<\textbf{1}^n, \textbf{y}^n\right> + \left<-z \cdot \textbf{1}^n, z2 \cdot \textbf{2}^n + z \cdot \textbf{y}^n\right>\nonumber\\
  \left<\textbf{a}_L - z \cdot \textbf{1}n, z^2 \cdot \textbf{2}^n + z \cdot \textbf{y}^n + \textbf{a}_R \circ \textbf{y}^n\right> = z^2 v + z \cdot \left<\textbf{1}^n, \textbf{y}^n\right> - z \cdot \left<\textbf{1}^n, z^2 \cdot \textbf{2}^n + z \cdot \textbf{y}^n\right>\nonumber\\
  \left<\textbf{a}_L - z \cdot \textbf{1}^n, z^2 \cdot \textbf{2}^n + z \cdot \textbf{y}^n + \textbf{a}_R \circ \textbf{y}^n\right> = z^2 v + z \cdot \left<\textbf{1}^n, \textbf{y}^n\right> - z3 \cdot \left<\textbf{1}^n, \textbf{2}^n\right> - z^2 \cdot \left<\textbf{1}^n, \textbf{y}^n\right>\nonumber\\
  \left<\textbf{a}_L - z \cdot \textbf{1}^n, z^2 \cdot \textbf{2}^n + z \cdot \textbf{y}^n + \textbf{a}_R \circ \textbf{y}^n\right> = z^2 v + (z - z^2) \cdot \left<\textbf{1}^n, \textbf{y}^n\right> - z^3 \left<\textbf{1}^n, \textbf{2}^n\right>\nonumber
\end{align}
  
Let $d(y,z) = (z - z^2) \left<\textbf{1}^n, \textbf{y}^n\right> - z^3 \left<\textbf{1}^n, \textbf{2}^n\right>$, and we get the final form:
\begin{align}
  \left<\textbf{a}_L - z \cdot \textbf{1}^n, z^2 \cdot \textbf{2}^n + z \cdot \textbf{y}^n + \textbf{a}_R \circ \textbf{y}^n\right> = z^2 v + d(y,z)
\end{align}

The verifier can calculate the right side (using the commitment $V$ for $v$), and the problem is now reduced to an inner product argument.


\subsection{Blinding the inner product}

We have shown how to make a logarithmically efficient inner product argument, and how to reduce a range proof to an inner product.  But the inner product argument is not zero knowledge, so we can't use it directly; we must first blind the parameters.

Let $(\textbf{s}_L, \textbf{s}_R)$ be vectors of integers:
\begin{align}
  (\textbf{s}_L, \textbf{s}_R) \leftarrow \mathbb{Z}_p^n
\end{align}

Replace $\textbf{a}_L$ with $(\textbf{a}_L + \textbf{s}_L x)$ and $\textbf{a}_R$ with $(\textbf{a}_R + \textbf{s}_R x)$, and the inner product becomes:
\begin{align}
  \left<(\textbf{a}_L + \textbf{s}_L x) - z \textbf{1}^n, z^2 \textbf{2}^n + z \textbf{y}^n + (\textbf{a}_R + \textbf{s}_R x)\circ\textbf{y}^n\right> = z^2 v + d(y,z)
\end{align}

Then construct vector polynomials $l(x)$ and $r(x)$ from the two sides of the inner product:
\begin{align}
  l(x) &= \textbf{a}_L + \textbf{s}_L x - z \textbf{1}^n\\
  r(x) &= z^2 \textbf{2}^n + z \textbf{y}^n + (\textbf{a}_R+ \textbf{s}_R x)\circ\textbf{y}^n
\end{align}

The zeros of these vector polynomials are just the unblinded inner product terms:
\begin{align}
  l(0) &= \textbf{a}_L - z \textbf{1}^n\\
  r(0) &= z^2 \textbf{2}^n + z \textbf{y}^n + \textbf{a}_R\circ\textbf{y}^n
\end{align}

The inner product then becomes
\begin{align}
  \left<l(0), r(0)\right> = z^2 v + d(y,z)
\end{align}

We can express $l(x)$ and $r(x)$ as generic degree one polynomials
\begin{align}
  l(x) &= l_0 + l_1 x\\
  r(x) &= r_0 + r_1 x
\end{align}

Where
\begin{align}
  l_0 &= \textbf{a}_L - z \textbf{1}^n\\
  l_1 &= \textbf{s}_L\\
  r_0 &= z^2 \textbf{2}^n + z \textbf{y}^n + \textbf{a}_R\circ\textbf{y}^n\\
  r_1 &= \textbf{s}_R\circ\textbf{y}^n\\
\end{align}

If we define $t(x)$ as the inner product of the blinded vector polynomials, we get
\begin{align}
  t(x) = \left<l(x), r(x)\right> 
\end{align}

We can express this in terms of x:
\begin{align}
  t(x) = t_0 + t_1 x + t_2 x^2
\end{align}

Where
\begin{align}
  t_0 &= \left<l_0, r_0\right> = z^2 v + d(y,z)\\
  t_2 &= \left<l_1, r_1\right>\\
  t_1 &= \left<l_0 + l_1, r_0 + r_1\right> - t_0 - t_2
\end{align}

Proving the blinded inner product range proof now depends on simply verifying that both 
\begin{align}
  t_0 &= z^2 v + d(y,z)\\
  t(x) &= \left<l(x), r(x)\right> = t_0 + t_1 x + t_2 x^2
\end{align}



\section{CryptoNote}

CryptoNote \cite{cryptonote} is a privacy focused cryptocurrency system which implements many of the techniques explored above, plus a novel method for tying long term public keys to one time addresses.  CryptoNote is defined to use elliptic curves rather than exponentials, but I will break with that to maintain consistency with the rest of the document, and use exponentials in this section.


\subsection{One time addresses}

A CryptoNote key consists of a pair of public keys $(A, B)$ with their associated private keys $(a, b)$.  To construct a one time address, the creator of a transaction starts with a transaction private key $r$, and an associated transaction public key $R$:
\begin{align}
  R=g^r
\end{align}

The creator then uses this, with the destination public key $(A, B)$, to construct the one time address $y$.  This address is a public key, with an associated private key $x$:
\begin{align}
  y = g^x = g^{H(rA)} B
\end{align}

The owner of the destination key $(A, B)$ can scan the transaction one time addresses to determine if he is the owner.  He first uses his private key $(a, b)$ to attempt to recover the one time private key $x$:
\begin{align}
	x = H(Ra) + b
\end{align}

Then raise $g$ to this power to reconstruct the public key $y$:
\begin{align}
  g^x = g^{H(Ra)} g^b
\end{align}

If $y = g^x$, then the destination key was the same one used to construct the one time address, and the key owner is the owner of the one time address.  Since the owner knows the private key $x$, he is able to sign the key $y$ in a ring signature, allowing him to spend it.


\subsection{View keys}

One time addresses allow a user to find the transaction outputs which he owns.  But this requires the user to scan the entire blockchain, looking at every output.  For users with limited storage and bandwidth, this can be problematic.  It would be preferable to allow a trusted node to do the scanning for the user, while preventing the node from being able to spend the output.

To do this, the user can pass a tuple of his private key $a$ with his public key $B$:
\begin{align}
  V = (a, B)
\end{align}

The node can then look at each transaction, and use the view key with the transaction public key $R$ to attempt to reconstruct the one time public key $y$:
\begin{align}
  Y = g^{H(Ra)} B
\end{align}

If $Y = y$, then the node knows that the one time key belongs to the user, and returns it.


\subsection{Ring signatures}

CryptoNote uses linkable ring signatures, with external data.  It defines a transaction prefix to be all of the transaction data except for the ring signatures themselves, which includes the input and output public keys, with the transaction public key and amounts.  The transaction prefix is serialized then hashed to create the signed message m.



\section{Monero}

Monero is a privacy focused cryptocurrency.  In its initial implementation, it used a vanilla implementation of cryptonote \cite{cryptonote}.  Later iterations added confidential transactions, with standard range proofs \cite{ringct}.  Recent work includes upgrading the range proofs with bulletproofs for significant space savings.


\subsection{RingCT}

The Monero implementation of confidential transactions is called RingCT \cite{ringct}.  It uses MLSAG signatures that tie a set of Pedersen Commitments to a set of input keys.  This is necessary because to verify a confidential transaction, it is required to have a full set of the commitments used in order to recover $g^z$.  Without the MLSAG, any attempt to include the commitments would either be unable to recover $g^z$, or would expose the real input keys.

To accomplish this, the MLSAG signature adds the corresponding commitments to the public key vectors, then passes them in the signature output:
\begin{align}
  y_i = ((y_{i,0}, C_{i,0}), ..., (y_{i,m-1}, C_{i,m-1}))
\end{align}

When constructing the hashes, the prover signs a final term which is the sum of the input commitments minus the sum of the output commitments:
\begin{align}
  g^z &= \frac{C_i}{C_o}\\
  L_{j,m} &= g^{v_m}\\
  c_{j+1} &= H(L_{j,0}, R_{j,0}, ... , L_{j,m-1}, R_{j, m-1}, L_{j,m})
\end{align}

As before, if this sum is a commitment to zero, then it will take the form of a public key $g^z$, where the user knows the private key $z$.  So it can be signed like any other public key in a ring signature.  Since the commitment does not need to be linkable, it is not necessary to include a $R_{j,m}$ term, or a key image.  It will be necessary to create a new $v_m$ and include an additional $r_{j,m}$ in the signature:
\begin{align}
  r_{j,m} = v_m - c_j z
\end{align}

The verifier uses this additional $r_{j,m}$ and $c_j$ to build a standard Schnorr term:
\begin{align}
  c_{j+1} = H(L_{j,0}, L_{j,0}, ... , L_{j,0}, L_{j,0}, g^{r_{j,m}} y^{c_j})
\end{align}

As before, if the sum was a commitment to zero, then this term will be the same in the prover and verifier hashes.



\section{Zcash}

Zcash is one of the more technically advanced cryptosystems available on current exchanges.  It uses zero-knowledge proofs to allow for completely hidden transactions, that can still be validated externally.  It divides its address space into t-addresses, whose details are transparent, and z-addresses, which are hidden from all but the participants.  Money that passes from a t-address to a z-address cannot be tracked, even if it later goes back to a t-address.


\subsection{zkSNARKs}

A zkSNARK is a zero-knowledge, short, non-interactive argument of knowledge.  It allows the prover to create a representation of an arbitrary arithmetic or logic circuit, then make proofs about assertions relative to that circuit.  The proofs are computationally difficult to construct, though easier to evaluate, and require a trusted setup between prover and verifier.



\section{Lelantus}

There is a new Zerocoin based cryptocurrency system called Lelantus \cite{lelantus}, released 2018-12-22.  It uses confidential transactions, and claims to be able to hide the inputs fully while still being auditable.  

As per Zerocoin, Lelantus uses the output commitments as the transaction inputs/outputs themselves, rather than associating the commitments with a one time address as in RingCT.  It is thus necessary to reveal the commitment secret during the spend, similar to the way that CryptoNote reveals the key image.  So it is necessary to make the commitments double blind, or else after secret reveal it would be possible to brute force the values as per the naive approach to Pedersen commitments.  Adapting Lelantus to a more CryptoNote-ish system could obviate this need, and allow single blinded commitments.


\subsection{$\Sigma$-protocol for commitment to $0$ or $1$}

Consider a commitment to a message $m$ with random blinding factor $r$:
\begin{align}
  c=Com(m, r)
\end{align}

To prove that $c$ opens to $0$ or $1$, pick random $(a,s,t)$ and use them to construct $(c_a, c_b)$:
\begin{align}
  a,s,t &\in \mathbb{Z}_p\\
  c_a &= Com(a, s)\\
  c_b &= Com(am, t)
\end{align}

In an interactive protocol, the prover would send $(c_a,c_b)$ to the verifier, who would respond with the challenge $x$.  To make it non-interactive, hash $(c, c_a, c_b)$:
\begin{align}
  x = H(c, c_a, c_b)
\end{align}

Either way, the prover uses $x$ to construct $(f, z_a, z_b)$ and sends it to the verifier:
\begin{align}
  f &= mx + a\\
  z_a &= rx + s\\
  z_b &= r(x-f) + t
\end{align}

The verifier now has the full set of $(c, c_a, c_b, x, f, z_a, z_b)$ and accepts the proof if both of the following are true:
\begin{align}
  c^x c_a &= Com(f, z_a)\\
  c^{x-f} c_b &= Com(0, z_b)
\end{align}

This follows as 
\begin{align}
  c^x c_a &= Com(xm,xr) \cdot Com(a,s)\\
          &= Com(xm+a, xr+s)\\
          &= Com(f, za)\\
  c^{x-f} c_b &= Com((x-f)m, (x-f)r) \cdot Com(am, t)\\
              &= Com(xm - fm + am, (x-f)r + t)\\
              &= Com(xm - (mx + a)m + am, z_b)\\
              &= Com(xm - m^2 x, z_b)
\end{align}

Since $x$ is not $0$, then $x (m-m^2)$ is only $0$ when $(m-m^2)$ is $0$, or when
\begin{align}
  m = m^2
\end{align}

This is only true $\forall m \in {0,1}$.  So if $c^{x-f} c_b = Com(0,zb)$, $m \in {0,1}$.


\subsection{One out of Many $\Sigma$-proofs}

Ring signatures allow hiding a signature in a set of mixins.  But they grow in size linearly with the mixin set size.  So the mixin set must be limited, and cannot contain every transaction in the ledger.  Merkle proofs offer a logarithmic sized proof for ledger inclusion, but are not zero knowledge.  It would be ideal to be able to demonstrate both ownership and leder inclusion with a single proof.  One out of many proofs do this, in logarithmic size.  So every output in the ledger functions as a mixin, and the proof size scales logarithmically with the ledger size.

Consider a set of $N$ commitments:
\begin{align}
  c_i = g^{s_i} h^{v_i}
\end{align}

If we know that this set contains a commitment to $0$, then we know an index $l$ such that
\begin{align}
  c_l = \prod_{i=0}^{N-1} c_i^{\delta_{il}}
\end{align}

is a commitment to zero.  This is true because $\delta_{ll} = 1$, while all other $\delta_{il} = 0$. So this product is simply $c_l$ as the rest of the $c_i$ are canceled by raising to $0$.

Assuming $N = 2^n$, extending as necessary, expand $i$ and $l$ in binary:
\begin{align}
  i = i_1...i_n\\
  l = l_1...l_n
\end{align}

We can now express $\delta_{il}$ in terms of these bits:
\begin{align}
  \delta_{il} = \prod_{j=1}^{n} \delta_{i_jl_j}
\end{align}
  
Combining these two terms, our commitment to $0$ $C$ becomes
\begin{align}
  C = \prod_{i=0}^{N-1}c_i^{\prod_{j=1}^{n} \delta_{i_jl_j}}
\end{align}

Next we iterate over all $n$ bits, committing to the bits of $l$ and proving they are all zero or one using the previous protocol.  After getting the challenge $x$ we will generate an $f$, but now there is one for each bit of $l$:
\begin{align}
  f_j = l_j x + a_j
\end{align}

We can further define $f_{j, i_j}$ as a function of $f_j$ that depends on $i_j$:
\begin{align}
  f_{j,1} = f_j = l_j x + a_j\\
  f_{j,0} = x - f_j = (1 - l_j) x - a_j
\end{align}

For each $i$, we can take the product $p_i(x)$ of the $f_{j, i_j}$ terms:
\begin{align}
  p_i(x) = \prod_{j=1}^{n} f_{j, i_j}
\end{align}

In all cases, $f_{j, i_j}$ will be a linear function of $x$, so $p_i(x)$ will be a polynomial in $x$ of degree $n$; but the $x$ term will cancel $\forall j$ such that $l_j \ne i_j$.  So $\forall i \ne l$, at least one of the $x$ terms will cancel; thus
\begin{align}
  p_i(x) = \prod_{j=1}^n f_{j,i_j} = {\prod_{j=1}^{n}\delta_{i_jl_j} x} + \sum_{k=0}^{n-1}{p_{i,k} x^k}
\end{align}

If we have $x$, then we can calculate this product directly.  But before we have $x$, we can still evaluate this polynomial algebraically.  If we do so, we can determine the $p_{i,k}$ parameters in terms of $a_j$.  This allows us to use $p_{i,k}$ once we have $a_j$:

For all $j = (1, ..., n)$ with $k = j - 1$:
\begin{align}
  (&r_j, a_j, s_j, t_j, \rho_j) \longleftarrow \mathbb{Z}_q\\
  &c_{l_j} = Com(l_j; r_j)\\
  &c_{a_j} = Com(a_j; s_j)\\
  &c_{b_j} = Com(l_j a_j; t_j)\\
  &c_{d_k} = \prod_{i=0}^{N-1}{c_i^{p_{i,k}}} \cdot Com(0; \rho_k)
\end{align}

The verifier responds with the challenge $x$, or it is generated via Fiat-Shamir.  Prover then uses $x$ as per the previous protocol to construct, $\forall j$:
\begin{align}
  f_j &= l_j + a_j\\
  z_{a_j} &= r_j x + s_j\\
  z_{b_j} &= r_j (x - f_j) + t_j
\end{align}

The prover then constructs the final value:
\begin{align}
  z_d = r x^n - \sum_{k=0}^{n-1}{\rho_k x^k}
\end{align}

The verifier must check the individual bit proofs:
\begin{align}
  c_{l_j}^x c_{a_j} &= Com(f_j; z_{a_j})\\
  c_{l_j}^{x-f_j} c_{b_j} &= Com(0; z_{b_j})
\end{align}
    
As before, the first line proves knowledge of $l_j$, and the second proves it was binary.  Finally, the verifier checks $z_d$ against $c_{d_k}$ using $c_i$ and $f_{j,i_j}$:
\begin{align}
  \prod_{i=0}^{N-1}{c_i^{\prod_{j=1}^{n}{f_{j,i_j}}}} \prod_{k=0}^{n-1}{c_{d_k}^{-x^k}} = Com(0; z_d)
\end{align}

If we simplify using $p_i(x)$ and expand we can see why this is true:
\begin{align}
  \prod_{i=0}^{N-1}{c_i^{\prod_{j=1}^{n}{f_{j,i_j}}}} &  \prod_{k=0}^{n-1}{c_{d_k}^{-x^k}} = \prod_{i=0}^{N-1}{c_i^{p_i(x)}} \prod_{k=0}^{n-1}{(\prod_{i=0}^{N-1}{c_i^{p_{i,k}}} Com(0; \rho_k))^{-x^k}}\\
      &= \prod_{i=0}^{N-1}{c_i^{  \underoverset{j=1}{n}{\prod}{\delta_{i_jl_j} x} + \underoverset{k=0}{n-1}{\sum}{p_{i,k} x^k}   }} \prod_{k=0}^{n-1}{(\prod_{i=0}^{N-1}{c_i^{p_{i,k}}} Com(0; \rho_k))^{-x^k}}\\
      &= c_l^{x^n} \prod_{i=0}^{N-1}{c_i^{ \underoverset{k=0}{n-1}{\sum}{p_{i,k} x^k} }}        \prod_{k=0}^{n-1}{ Com(0; \rho_k)^{-x^k}}         \prod_{k=0}^{n-1}{(\prod_{i=0}^{N-1}{c_i^{p_{i,k}}})^{-x^k}}\\
      &= Com(0; r x^n) \prod_{k=0}^{n-1}{ Com(0; \rho_k)^{-x^k}}      \prod_{k=0}^{n-1}{\prod_{i=0}^{N-1}{c_i^{p_{i,k}  x^k}}}          \prod_{k=0}^{n-1}{\prod_{i=0}^{N-1}{c_i^{-p_{i,k} x^k}}}\\
      &= Com(0; r x^n) \prod_{k=0}^{n-1}{ Com(0; \rho_k)^{-x^k}}\\
  Com(0; z_d) &= Com(0; rx^n - \sum_{k=0}^{n-1}{\rho_k x^k})\\
      &= Com(0; rx^n) \prod_{k=0}^{n-1}{Com(0; \rho_k)^{-x^k}}
\end{align}


\subsection{Hiding Transaction Amounts and Origins}
 
Confidential Transactions are good at hiding amounts, but it is necessary to reveal the commitments themselves in order to prove that a transaction is balanced, i.e. that the sum of the inputs equals the sum of the outputs.  RingCT obfuscates the actual input commitments in a ring of mixins (with both addresses and commitments), but the data is still present and subject to analysis.  It would be better to be able to prove both input ownership and transaction balance without ever showing the input commitments.

Lelantus accomplishes this via a two step process.  It establishes input ownership via a set of one out of many $\Sigma$-proofs, then uses elements of the $\Sigma$-proofs to to establish a balance proof.  At no time are the input commitments themselves revealed to the verifier.

To show how the balance proof arises from the elements of the $\Sigma$-proofs, consider the following values:
\begin{align}
  z_i &= v_i x^n - \sum_{k=0}^{n-1}{\rho_k^i x^k}\\
  Com(0, \rho_k^i) &= g^0 h^{\rho_k^i}
\end{align}

The verifier can then compute the following:
\begin{align}
  A &= (\prod_{i=1}^{N_{new}}{C_{o_i}})^{x^n} = (\prod_{i=1}^{N_{new}}{g^{s_{o_i}} h^{v_{o_i}}})^{x^n}  =  g^{(\Sigma s_o) x^n}  h^{(\Sigma v_o) x^n}\\
  B &= Com(0, \sum_{i=1}^{N_{old}}{z_i}) \prod_{i=1}^{N_{old}}{(\prod_{k=0}^{n-1} Com(0, \rho_k^i)^{x^k})}\\
    &= g^0 h^{(\sum{v_i}) x^n} \prod_{i=1}^{N_{old}}{h^{-\sum_{k=0}^{n-1}{\rho_k^i x^k}}} \prod_{i=1}^{N_{old}}{(\prod_{k=0}^{n-1}{g^0 h^{\rho_k^i x^k}})}\\
    &= h^{(\sum{v_i}) x^n} \prod_{i=1}^{N_{old}}{h^{-\sum_{k=0}^{n-1}{\rho_k^i x^k}}}  \prod_{i=1}^{N_{old}}{h^{\sum_{k=0}^{n-1}{\rho_k^i x^k}}}\\
    &= h^{(\sum{v_i}) x^n}
\end{align}

The ratio of A to B is thus:
\begin{align}
  \frac{A}{B} = \frac{g^{(\sum{s_o}) x^n} g^{(\sum{v_o}) x^n}}{g^{(\sum{v_i}) x^n}}
\end{align}
  
As before, if the transaction is balanced then 
\begin{align}
  \sum{v_i} = \sum{v_o}
\end{align}

And thus
\begin{align}
  \frac{A}{B} = g^{(\sum{s_o}) x^n}
\end{align}

Since the prover knows the output serial numbers, this is a public key to which he knows the private key.  So it suffices to provide a regular Schnorr proof for this ratio to prove that the transaction is balanced, and no input commitments have been revealed.



\section{Mimblewimble}

Some of the most recently released cryptocurrencies use a relatively new system called Mimblewimble \cite{mimblewimble}.  The goals are to implement a system with the benefits of RingCT, but with a pruned blockchain that still verifies even after removing spent outputs.  As a downside, the sender and receiver of a transaction must complete an interactive protocol.


\subsection{One Way Aggregate Signatures}

While RingCT uses ring signatures with mixins to obscure the links between inputs and outputs, Mimblewimble rather aggregates all of the transactions in a block via a technique they call One Way Aggregate Signatures \cite{increasingBitcoinAnonymity}.  Thus the individual links between the inputs and outputs of the transactions is lost, and only the block level linking is still present.  This happens naturally as a result of the transaction format.

Consider a transaction with input commitments $C_i$ and output commitments $C_o$.  As with all implementations of confidential transactions, the sum of the input commitments minus the outputs will be the ratio of their products, and this will be a public key to which the owner knows the private key:
\begin{align}
  \frac{\prod C_i}{\prod C_o} = g^{s_i - s_o} = g^z = C_T
\end{align}

The transaction format is thus the set $(C_{i_1}, ..., C_{i_N}, C_{o_1}, ..., C_{o_M}, C_T)$, with a signature on CT to prove the balance.  Given this format, it is trivial to combine transactions; you can simply add the new input, output, and balance commitments to the existing set, and the balance check should still succeed with the combined sets:
\begin{align}
  \prod (\frac{\prod C_i}{\prod C_o})_k= \prod (C_T)_k
\end{align}

A verifier can check the signatures on the individual $C_T$ and the aggregated balance check; if they all succeed, the aggregated transaction set is still valid.

Using this technique, miners will aggregate all of the transactions in a block into a single set with a single aggregated signature.  After the new block is formed, nodes can again merge the transactions from the new block into the set of all transactions.  Once this is done, any spent outputs will appear in both the output list and the input list.  Such outputs can be safely pruned from both lists, and a balance check over the entire ledger will still be valid.  This is clear, as any such transactions will appear in both the top and bottom of the input/output ratio, and will thus cancel each other out.  

Thanks to this pruning, Mimblewimble achieves its goal of maintaining a lightweight ledger, with only unspent outputs and no inputs.  This makes the ledger small, only growing with the UTXO set.  And for observers who want to analyze the ledger, there is no way to link transactions.

However, any observer who sees the advertised transactions (either a peer or a miner) has full visibility into the money flow, and can easily link transactions, since the inputs and outputs are directly listed with no obfuscation.  And all node operators get a list of the inputs and outputs in every block, which gives them obfuscated access to the same data (though on a per block rather than per transaction level).

Since spent outputs will be removed, it will no longer be possible to validate a block using normal merkle tree semantics, since this requires having all leaf nodes to construct the root hash.  So every output will need a separate merkle proof, to tie it to the root hash at time of block creation.  Validating a block will require validating each remaining output's merkle proof.

Finally, while there are indeed space savings from removing inputs and spent outputs, it is necessary to store all balance commitments $C_T$ and their associated Schnorr proofs forever.  This set grows monotonically with each added transaction.  



\section{MobileCoin}

MobileCoin is a new cryptocurrency, whose goals are privacy, convenience, and provable correctness.  The proof of concept implementation uses CryptoNote as a transaction format, with the Stellar Consensus Protocol to achieve blockchain consensus, rather than a wasteful proof of work.  All computation on the nodes uses a secure enclave, to prevent even node operators from having access to view keys or rings.  

For maximal convenience, MobileCoin will be introduced directly into secure messaging apps, using mobile devices' secure storage for keys.  Since there is no mining, transactions will be confirmed quickly.  A user will be able to open a messaging app and quickly send untraceable money, usually within a matter of seconds.

The main weakness of CryptoNote is that the ring signatures contain the actual inputs used in the transaction, though these are obscured by a number of mixins.  So anyone with access to the ledger can perform a number of attacks, linking payments to their eventual destinations.  This can be used in the common Overseer scenario, where collusion between two parties can unmask the owners of coins sent by one and cashed out at the other.  So the FBI could send coins to a suspect address, then wait for those coins to make their way to an exchange, at which point the identity of the owner of the suspect address can be determined.

To address this, MobileCoin currently drops the inputs from transactions before writing them to the ledger, indeed before the transactions even leave the secure enclave.  This guarantees full privacy from ledger analysis, at the cost of external verifiability.  The consensus quorum becomes the arbiter of correctness, and since the software is open source and anyone can run a node, this functions to attest to the correctness of the ledger.



\section{Acknowledgements}

The author would like to thank Toby Segaran for initial help on ring signatures, and Isis Lovecruft for the initial review.


\newpage
\begin{thebibliography}{8}

\bibitem{schnorr}
  \emph{Schnorr signature}.
  \texttt{https://en.wikipedia.org/wiki/Schnorr\%5Fsignature}

\bibitem{fiatshamir}
  \emph{Fiat Shamir heuristic}.
  \texttt{https://en.wikipedia.org/wiki/Fiat\%2DShamir\%5Fheuristic}

\bibitem{cryptonote}
  Nicolas van Saberhagen.
  \emph{CryptoNote} v$2.0$ October 17, 2013.
  \texttt{https://www.bytecoin.org/old/whitepaper.pdf}

\bibitem{ringct}
  Shen Noether, Adam Mackenzie, the Monero Research Lab.
  \emph{Ring Confidential Transactions for Monero} DOI 10.5195/LEDGER.2016.34.
  \texttt{http://eprint.iacr.org/2015/1098}

\bibitem{bulletproofs}
  Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, and Greg Maxwell.
  \emph{Bulletproofs: Short proofs for confidential transactions and more} Cryptology ePrint Archive, Report 2017/1066, 2017.
  \texttt{https://eprint.iacr.org/2017/1066}

\bibitem{lelantus}
  Aram Jivanyan.
  \emph{Lelantus: Private transactions with hidden origins and amounts based on DDH} 2018.12.22.
  \texttt{https://lelantus.io/lelantus.pdf}

\bibitem{increasingBitcoinAnonymity}
  Dr. Yuan Horas Mouton.
  \emph{Increasing Anonymity in Bitcoin}.\\
  \texttt{https://download.wpsoftware.net/bitcoin/wizardry/horasyuanmouton-owas.pdf}

\bibitem{mimblewimble}
  Tom Elvis Jedusor.
  \emph{MIMBLEWIMBLE} 19 July, 2016.\\
  \texttt{https://download.wpsoftware.net/bitcoin/wizardry/mimblewimble.txt}

\end{thebibliography}

\end{document}