main.tex

\documentclass{llncs}

\pagestyle{plain}

\usepackage{amsmath,amssymb,amsfonts}
\usepackage{mathtools}
\usepackage{bookmark}
\setcounter{tocdepth}{3}

\newcommand{\G}{\mathbb{G}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\hash}{\mathcal{H}}
\newcommand{\func}[1]{\mathsf{#1}}
\newcommand{\addr}{\func{addr}}
\newcommand{\com}{\func{Com}}
\newcommand{\comm}{\func{Comm}}
\newcommand{\oracle}{\mathcal{O}^{\func{DAP}}}


\begin{document}

\title{Lelantus Spark: Secure and Flexible Private Transactions}
\author{Aram Jivanyan\inst{1,2}\thanks{Corresponding author: \email{aram@firo.org}} \and Aaron Feickert\inst{3}}
\institute{Firo \and Yerevan State University \and Cypher Stack}
\maketitle

\begin{abstract}
    We propose a modification to the Lelantus private transaction protocol to provide recipient privacy, improved security, and additional usability features.
    Our decentralized anonymous payment (DAP) construction, Spark, enables non-interactive one-time addressing to hide recipient addresses in transactions.
    The modified address format permits flexibility in transaction visibility.
    Address owners can securely provide third parties with opt-in visibility into incoming transactions or all transactions associated to the address; this functionality allows for offloading chain scanning and balance computation without delegating spend authority.
    It is also possible to delegate expensive proving operations without compromising spend authority when generating transactions.
    Further, the design is compatible with straightforward linear multisignature operations to allow mutually non-trusting parties to cooperatively receive and generate transactions associated to a multisignature address.
    We prove that Spark satisfies formal DAP security properties of balance, non-malleability, and ledger indistinguishability.
\end{abstract}


\section{Introduction}

Distributed digital asset protocols have seen a wealth of research since the introduction of the Bitcoin transaction protocol, which enables transactions generating and consuming ledger-based outputs, and provides a limited but useful scripting capability.
However, Bitcoin-type protocols have numerous drawbacks relating to privacy: a transaction reveals source addresses and amounts, and subsequent spends reveal destination addresses.
Further, data and metadata associated with transactions, like script contents, can provide undesired fingerprinting of transactions.

More recent research has focused on mitigating or removing these limitations, while permitting existing useful functionality like multisignature operations or opt-in third-party transaction viewing.
Designs in privacy-focused cryptocurrencies like Beam, Firo, Grin, Monero, and Zcash take different approaches toward this goal, with a variety of different tradeoffs.
The RingCT-based protocol currently used in Monero, for example, practically permits limited sender anonymity due to the space and time scaling of its underlying signature scheme \cite{ringct,clsag}.
The Sprout and Sapling protocols supported by Zcash \cite{zcash} (and their currently-deployed related updates) require trusted parameter generation to bootstrap their circuit-based proving systems, and interact with transparent Bitcoin-style outputs in ways that can leak information \cite{zcash_sprout,zcash_sapling}.
The Mimblewimble-based construction used as the basis for Grin can leak graph information prior to a merging operation performed by miners \cite{mw}.
To mitigate Mimblewimble's linkability issue, Beam has designed and implemented into its system an adaption of Lelantus for use with the Mimblewimble protocol which enables obfuscation of the transaction graph \cite{LMW}.
The Lelantus protocol currently used in Firo does not provide recipient privacy; it supports only mints and signer-ambiguous spends of arbitrary amounts that interact with transparent Bitcoin-style outputs, which can leak information about recipient identity \cite{lelantus}.
Seraphis \cite{seraphis} is a transaction protocol framework of similar design being developed concurrently.

Here we introduce Spark, an iteration on the Lelantus protocol enabling trustless private transactions which supports sender, recipient, and transaction amount privacy.
Transactions in Spark, like those in Lelantus and Monero, use specified sender anonymity sets composed of previously-generated shielded outputs.
A parallel proving system adapted from a construction by Groth and Bootle \textit{et al.} \cite{groth,bootle} (of independent interest and used in other modified forms in Lelantus\cite{lelantus} and Triptych \cite{triptych}) proves that a consumed output exists in the anonymity set; amounts are encrypted and hidden algebraically in Pedersen commitments, and a tag derived from a verifiable random function \cite{dodis,omniring} prevents consuming the same output multiple times, which in the context of a transaction protocol would constitute a double-spend attempt.

Spark transactions support efficient verification in batches, where range and spend proofs can take advantage of common proof elements and parameters to lower the marginal cost of verifying each proof in such a batch; when coupled with suitably-chosen sender anonymity sets, the verification time savings of batch verification can be significant.

Spark enables additional useful functionality.
The use of a modified Chaum-Pedersen discrete logarithm proof, which asserts spend authority and correct tag construction, enables efficient signing and multisignature operations similar to those of \cite{musig,frost,schnorrwithschnorr,bellare_frost} where computationally-expensive proofs may be offloaded to more capable devices with limited trust requirements.
The protocol further adds three levels of opt-in visibility into transactions without delegating spend authority.
Incoming view keys allow a designated third party to identify transactions containing outputs destined for an address, as well as the corresponding amounts and encrypted memo data.
Full view keys allow a designated third party to additionally identify when received outputs are later spent (but without any recipient data), which enables balance auditing and further enhances accountability in threshold multisignature applications where this property is desired.
Payment proofs allow a sender to assert the destination, value, and memo of a coin while proving (in zero knowledge) that it knows the secret data used to produce the coin; this permits more fine-grained disclosure without revealing view keys.

All constructions used in Spark require only public parameter generation, ensuring that no trusted parties are required to bootstrap the protocol or ensure soundness.


\section{Cryptographic Preliminaries}

Throughout this paper, we use additive notation for group operations.
Let $\mathbb{N}$ be the set $\{0,1,2,\ldots\}$ of non-negative integers.


\subsection{Pedersen Commitment Scheme}

A homomorphic commitment scheme is a construction producing one-way algebraic representations of input values.
The Pedersen commitment scheme is a homomorphic commitment scheme that uses a particularly simple linear combination construction.
Let $pp_{\text{com}} = (\G, \F, G, H)$ be the public parameters for a Pedersen commitment scheme, where $\G$ is a prime-order group where the discrete logarithm problem is hard, $\F$ is its scalar field, and $G,H \in \G$ are uniformly-sampled independent generators.
The commitment scheme contains an algorithm $\com: \F^2 \to \G$, where $\com(v,r) = vG + rH$ that is homomorphic in the sense that $$\com(v_1,r_1) + \com(v_2,r_2) = \com(v_1 + v_2,r_1 + r_1)$$ for all such input values $v_1,v_2 \in \F$ and masks $r_1,r_2 \in \F$.
Further, the construction is perfectly hiding and computationally binding.

This definition extends naturally to a double-masked commitment scheme.
Let $pp_{\text{comm}} = (\G, \F, F, G, H)$ be the public parameters for a double-masked Pedersen commitment scheme, where $\G$ is a prime-order group where the discrete logarithm problem is hard, $\F$ is its scalar field, and $F,G,H \in \G$ are uniformly-sampled independent generators.
The commitment scheme contains an algorithm $\comm: \F^3 \to \G$, where $\comm(v,r,s) = vF + rG + sH$ that is homomorphic in the sense that $$\comm(v_1,r_1,s_1) + \comm(v_2,r_2,s_2) = \comm(v_1 + v_2,r_1 + r_2,s_1 + s_2)$$ for all such input values $v_1,v_2 \in \F$ and masks $r_1,r_2,s_1,s_2 \in \F$.
Further, the construction is perfectly hiding and computationally binding.


\subsection{Representation proving system}

A representation proof is used to demonstrate knowledge of a set of discrete logarithms in zero knowledge.
Let $pp_{\text{rep}} = (\G, \F)$ be the public parameters for such a construction, where $\G$ is a prime-order group where the discrete logarithm problems is hard and $\F$ is its scalar field.

The proving system itself is a tuple of algorithms $(\func{RepProve},\func{RepVerify})$ for the following relation:
$$\left\{ pp_{\text{rep}}, G, \{Y_i\}_{i=0}^{l-1} \subset \G ; \{y_i\}_{i=0}^{l-1} \subset \F : \forall i \in [0,l), Y_i = y_i G \right\}$$

We require that the proving system be complete, special honest-verifier zero knowledge, and special sound; these definitions are standard \cite{groth}.

An aggregated Schnorr proving system, like that in \cite{batchschnorr}, may be used for this purpose.

As a matter of notational convenience, we drop the set and subscript notation from these algorithms in the case where $l = 1$; this represents the case of a standard (non-aggregated) representation proof.


\subsection{Modified Chaum-Pedersen Proving System}

A Chaum-Pedersen proof is used to demonstrate discrete logarithm equality in zero knowledge.
Here we require a modification to the standard proving system that uses additional group generators and supports multiple assertions within a single proof.
Let $pp_{\text{chaum}} = (\G, \F, F, G, H, U)$ be the public parameters for such a construction, where $\G$ is a prime-order group where the discrete logarithm problem is hard, $\F$ is its scalar field, and $F,G,H,U \in \G$ are uniformly-sampled independent generators.

The proving system is a tuple of algorithms $(\func{ChaumProve},\func{ChaumVerify})$ for the following relation:
\begin{multline*}
\left\{ pp_{\text{chaum}}, \{S_i, T_i\}_{i=0}^{l-1} \subset \G^2 ; (\{x_i, y_i, z_i\}_{i=0}^{l-1}) \subset \F^3 : \right. \\
\left. \forall i \in [0,l), S_i = x_i F + y_i G + z_i H, U = x_i T_i + y_i G \right\}
\end{multline*}

We require that the proving system be complete, special honest-verifier zero knowledge, and special sound.

We present an instantiation of such a proving system in Appendix \ref{app:chaum}, along with security proofs.


\subsection{Parallel One-out-of-Many Proving System}

We require the use of a parallel one-out-of-many proving system that shows knowledge of openings of commitments to zero at the same index among two sets of group elements in zero knowledge.
In the context of the Spark protocol, this will be used to mask consumed coin serial number and value commitments for balance, ownership, and double-spend purposes.
We show how to produce such a proving system as a straightforward modification of a construction by Groth and Kohlweiss \cite{groth} that was generalized by Bootle \textit{et al.} \cite{bootle}, with a further optimization from Esgin \textit{et al.} \cite{matrict}.

Let $pp_{\text{par}} = (\G, \F, n, m, pp_{\text{com}}, pp_{\text{comm}})$ be the public parameters for such a construction, where $\G$ is a prime-order group where the discrete logarithm problem is hard, $\F$ is its scalar field, $n > 1$ and $m > 1$ are integer-valued size decomposition parameters, $pp_{\text{com}}$ are the public parameters for a Pedersen commitment construction, and $pp_{\text{comm}}$ are the public parameters for a double-masked Pedersen commitment construction.

The proving system itself is a tuple of algorithms $(\func{ParProve},\func{ParVerify})$ for the following relation, where we let $N = n^m$:
\begin{multline*}
\left\{ pp_{\text{par}}, \{S_k,V_k\}_{k=0}^{N-1} \subset \G^2, S',V' \in \G ; l \in \mathbb{N}, (s,v) \in \F : \right. \\
\left. 0 \leq l < N, S_l - S' = \comm(0,0,s), V_l - V' = \com(0,v) \right\}
\end{multline*}

We require that the proving system be complete, special honest-verifier zero knowledge, and special sound.

We present an instantiation of such a proving system in Appendix \ref{app:parallel}.


\subsection{Key-Committing Authenticated Encryption Scheme}

We require the use of an authenticated symmetric encryption with associated data (AEAD) scheme that commits to keys.
In the context of the Spark protocol, this construction is used to encrypt value, memo, and other data for use by the recipient of a transaction.
Note that in general, AEAD schemes need not commit to keys; because Spark payment proofs require this property, we require it in the overall protocol.
It is possible to generically extend an AEAD scheme using the technique of \cite{key_commitment} in a flexible manner by including a commitment to the key as part of the ciphertext, and by checking this commitment during authentication; we assume this approach when describing the algorithms here.

Let $pp_{\text{aead}}$ be the public parameters for such a construction.
The construction itself is a tuple of algorithms $(\func{AEADKeyGen},\func{AEADEncrypt},\func{AEADDecrypt})$.
Here $\func{AEADKeyGen}$ is a key derivation function that accepts as input an arbitrary string, and produces a key in the appropriate key space.
The algorithm $\func{AEADEncrypt}$ accepts as input a key, associated data, and arbitrary message string, and produces ciphertext in the appropriate space.
The algorithm $\func{AEADDecrypt}$ accepts as input a key, associated data, and ciphertext string, and produces a message in the appropriate space if authentication succeeds (and fails otherwise).

Assume that such a construction is indistinguishable against adaptive chosen-ciphertext attacks (IND-CCA2) and key-private under chosen-ciphertext attacks (IK-CCA) in this context \cite{keyprivacy}.


\subsection{Symmetric Encryption Scheme}

We require the use of a symmetric encryption scheme.
In the context of the Spark protocol, this construction is used to encrypt diversifier indices used to produce public addresses.

Let $pp_{\text{sym}}$ be the public parameters for such a construction.
The construction itself is a tuple of algorithms $(\func{SymKeyGen},\func{SymEncrypt},\func{SymDecrypt})$.
Here $\func{SymKeyGen}$ is a key derivation function that accepts as input an arbitrary string, and produces a key in the appropriate key space.
The algorithm $\func{SymEncrypt}$ accepts as input a key and arbitrary message string, and produces ciphertext in the appropriate space.
The algorithm $\func{SymDecrypt}$ accepts as input a key and ciphertext string, and produces a message in the appropriate space.

Assume that such a construction is indistinguishable against adaptive chosen-ciphertext attacks (IND-CCA2) in this context.


\subsection{Range Proving System}

We require the use of a zero-knowledge range proving system.
A range proving system demonstrates that a commitment binds to a value within a specified range.
In the context of the Spark protocol, it avoids overflow that would otherwise fool the balance definition by effectively binding to invalid negative values.
Let $pp_{\text{rp}} = (\G, \F, v_{\text{max}}, pp_{\text{com}})$ be the relevant public parameters for such a construction, where $pp_{\text{com}}$ are the public parameters for a Pedersen commitment construction.

The proving system itself is a tuple of algorithms $(\func{RangeProve},\func{RangeVerify})$ for the following relation:
$$\left\{ pp_{\text{rp}}, C \in \G ; (v, r) \in \F : 0 \leq v \leq v_{\text{max}}, C = \com(v,r) \right\}$$

We require that the proving system be complete, special honest-verifier zero knowledge, and special sound.

In practice, an efficient instantiation like Bulletproofs \cite{bp} or Bulletproofs+ \cite{bp_plus} may be used to satisfy this requirement.


\section{Concepts and Algorithms}

We now define the main concepts and algorithms used in the Spark transaction protocol.

\textbf{Keys and addresses}. Users generate keys and addresses that enable transactions.
A set of keys consists of a tuple $$(\addr_{\text{in}}, \addr_{\text{full}}, \addr_{\text{sk}}).$$
In this notation, $\addr_{\text{in}}$ is an incoming view key used to identify received funds, $\addr_{\text{full}}$ is a full view key used to identify outgoing funds and conduct certain computationally-heavy proving operations, and $\addr_{\text{sk}}$ is the spend key used to generate transactions.
Spark addresses are constructed in such a way that a single set of keys can be used to construct any number of \textit{diversified} public addresses that appear indistinguishable from each other or from public addresses produced from a different set of keys.
Diversified addressing allows a recipient to provide distinct public addresses to different senders, but scan transactions on chain only once for identification and recovery of incoming coins destined for any of its diversified public addresses.

\textbf{Coins.} A coin encodes the abstract value which is transferred through the private transactions. Each coin is associated with:
\begin{itemize}
\item A secret nonce
\item A recipient address
\item An integer value
\item A memo containing arbitrary recipient data
\end{itemize}
The recipient address and value are hidden using commitments.
The nonce, a part of the recipient address, the value, and the memo are encrypted to the recipient (unless the value is made public as part of a mint operation).

\textbf{Private Transactions}. There are two types of private transactions in Spark:
\begin{itemize}
    \item Mint transactions.
    A mint transaction generates new coins of public value destined for a recipient public address in a confidential way, either through a consensus-enforced mining process, or by consuming transparent outputs from a non-Spark base layer.
    In this transaction type, a representation proof is included to show that the minted coins are of the expected values.
    \item Spend transactions.
    A spend transaction consumes existing coins and generates new coins destined for one or more recipient public addresses in a confidential way.
    In this transaction type, a representation proof is included to show that the hidden input and output values are equal.
\end{itemize}

\textbf{Tags.} Tags are used to prevent coins from being consumed in multiple transactions.
When generating a spend transaction, the sender produces the tag for each consumed coin and includes it on the ledger.
When verifying transactions are valid, it suffices to ensure that tags do not appear on the ledger in any previous transactions.
Tags are uniquely bound to validly-recoverable coins, but cannot be associated to specific coins without the corresponding full view key.

\textbf{Algorithms}. Spark is a decentralized anonymous payment (DAP) system defined as the following polynomial-time algorithms:
\begin{itemize}
\item $\func{Setup}$: This algorithm produces all public parameters used by the protocol and its underlying components.
The setup process does not require any trusted parameter generation.
\item $\func{CreateKeys}$: This algorithm produces keys that are used when constructing addresses, processing coins, and spending coins.
\item $\func{CreateAddress}$: This algorithm produces diversified public addresses used for receiving coins.
\item $\func{CreateCoin}$: This algorithm produces a coin of a given value that is destined for a recipient public address.
\item $\func{Mint}$: This algorithm produces a transaction transferring public value to recipient public addresses.
\item $\func{Identify}$: This algorithm processes a coin to determine if it is destined for a diversified address controlled by a recipient.
\item $\func{Recover}$: This algorithm processes a coin to determine if it is destined for a diversified address controlled by a recipient, and produces additional data used for spending the coin or determining if it is already spent.
\item $\func{Spend}$: This algorithm produces a transaction consuming existing coins and generating new coins of hidden value to recipient public addresses.
\item $\func{Verify}$: This algorithm determines if a given transaction is valid.
\end{itemize}

We provide detailed descriptions below, and show security of the resulting protocol in Appendix \ref{app:security}.


\section{Algorithm Constructions}

In this section we provide detailed description of the DAP scheme algorithms.


\subsection{\texorpdfstring{$\func{Setup}$}{Setup}}

This algorithm produces public parameters required for the protocol.
The security parameter and resulting public parameters are assumed to be available to all other algorithms, even where not specifically noted.

\textbf{Inputs:} Security parameter $\lambda$, size decomposition parameters $n > 1$ and $m > 1$, maximum value parameter $v_{\text{max}}$

\textbf{Outputs:} Public parameters $pp$

\begin{enumerate}
\item Sample a prime-order group $\G$ in which the discrete logarithm, decisional Diffie-Hellman, and computational Diffie-Hellman problems are hard.
Let $\F$ be the scalar field of $\G$.
\item Sample $F,G,H,U \in \G$ uniformly at random.
In practice, these generators may be chosen using a suitable cryptographic hash function on public input.
\item Sample cryptographic hash functions $$\hash_k, \hash_{Q_2},\hash_{\text{ser}},\hash_{\text{val}},\hash_{\text{ser}'},\hash_{\text{val}'},\hash_{\text{bind}}: \{0,1\}^* \to \F$$ and $$\hash_{\text{div}}: \{0,1\}^* \to \G$$ uniformly at random.
In practice, these hash functions may be chosen using domain separation of a single suitable cryptographic hash function on public input.
\item Compute the public parameters $pp_{\text{com}} = (\G,\F,G,H)$ of a Pedersen commitment scheme.
\item Compute the public parameters $pp_{\text{comm}} = (\G,\F,F,G,H)$ of a double-masked Pedersen commitment scheme.
\item Compute the public parameters $pp_{\text{rep}} = (\G,\F)$ of a representation proving system.
\item Compute the public parameters $pp_{\text{chaum}} = (\G,\F,F,G,H,U)$ of the modified Chaum-Pedersen proving system.
\item Compute the public parameters $pp_{\text{par}} = (\G,\F,n,m,pp_{\text{com}},pp_{\text{comm}})$ of the parallel one-out-of-many proving system.
\item Compute the public parameters $pp_{\text{aead}}$ of an authenticated symmetric encryption scheme.
\item Compute the public parameters $pp_{\text{sym}}$ of a symmetric encryption scheme.
\item Compute the public parameters $pp_{\text{rp}} = (\G,\F,v_{\text{max}},pp_{\text{com}})$ of a range proving system.
\item Output all generated public parameters and hash functions as $pp$.
\end{enumerate}


\subsection{\texorpdfstring{$\func{CreateKeys}$}{CreateKeys}}

We describe the construction of key types used in the protocol.

\textbf{Inputs:} Security parameter $\lambda$, public parameters $pp$

\textbf{Outputs:} Key tuple $(\addr_{\text{in}}, \addr_{\text{full}}, \addr_{sk})$

\begin{enumerate}
\item Sample $s_1, s_2, r \in \F$ uniformly at random, and let $D = \comm(0, r, 0)$ and $P_2 = \comm(s_2, r, 0)$.
\item Set $\addr_{\text{in}} = (s_1, P_2)$.
\item Set $\addr_{\text{full}} = (s_1, s_2, D, P_2)$.
\item Set $\addr_{\text{sk}} = (s_1, s_2, r)$.
\item Output the tuple $(\addr_{\text{in}}, \addr_{\text{full}}, \addr_{\text{sk}})$.
\end{enumerate}


\subsection{\texorpdfstring{$\func{CreateAddress}$}{CreateAddress}}

This algorithm generates a \textit{diversified} public address from an incoming view key.
A given public address is privately and deterministically tied to an index called the \textit{diversifier}.
Diversified public addresses share the same set of keys for efficiency purposes, but are not linkable without non-public information.

\textbf{Inputs:} Security parameter $\lambda$, public parameters $pp$, incoming view key $\addr_{\text{in}}$, diversifier $i \in \mathbb{N}$

\textbf{Outputs:} Diversified address $\addr_{\text{pk}}$

\begin{enumerate}
\item Parse the incoming view key $\addr_{\text{in}} = (s_1, P_2)$.
\item Compute the diversified address components:
\begin{align*}
d &= \func{SymEncrypt}(\func{SymKeyGen}(s_1),i) \\
Q_{1,i} &= s_1 \hash_{\text{div}}(d) \\
Q_{2,i} &= \comm(\hash_{Q_2}(s_1,i),0,0) + P_2
\end{align*}
\item Set $\addr_{\text{pk}} = (d,Q_{1,i},Q_{2,i})$ and output this tuple.
\end{enumerate}
Note that we drop the diversifier index $i$ from subsequent notation when referring to addresses in operations performed by entities other than the incoming view key holder, since such users are not provided this index and cannot compute it.


\subsection{\texorpdfstring{$\func{CreateCoin}$}{CreateCoin}}

This algorithm generates a new coin destined for a given public address.
It uses a type bit to determine if the value is intended to be publicly visible.

\textbf{Inputs:} Security parameter $\lambda$, public parameters $pp$, destination public address $\addr_{\text{pk}}$, value $v \in [0, v_{\text{max}})$, memo $m$, type bit $b$

\textbf{Outputs:} Coin $\func{Coin}$, nonce $k$

\begin{enumerate}
\item Parse the recipient address $\addr_{\text{pk}} = (d, Q_1, Q_2)$.
\item Sample a nonce $k \in \F$.
\item Compute the recovery key $K = \hash_k(k)\hash_{\text{div}}(d)$.
\item Compute the serial number commitment $$S = \comm(\hash_{\text{ser}}(k), 0, 0) + Q_2.$$
\item Generate the value commitment $C = \com(v, \hash_{\text{val}}(k))$.
\item If $b=0$, generate a range proof $$\Pi_{\text{rp}} = \func{RangeProve}(pp_{\text{rp}},C;(v,\hash_{\text{val}}(k)).$$
\item If $b = 0$, set the recipient data $r = (v,d,k,m)$; otherwise, set $r = (d,k,m)$.
\item Generate an AEAD encryption key $k_{\text{aead}} = \func{AEADKeyGen}(\hash_k(k)Q_1)$; encrypt the recipient data $$\overline{r} = \func{AEADEncrypt}(k_{\text{aead}},\texttt{r},r).$$
\item If $b=0$, output the coin $\func{Coin} = (S, K, C, \Pi_{\text{rp}}, \overline{r})$ and nonce $k$; otherwise, output the coin $\func{Coin} = (S, K, C, v, \overline{r})$ and nonce $k$.
\end{enumerate}
The case $b=0$ represents a coin with hidden value being generated in a spend transaction, while the case $b=1$ represents a coin with plaintext value being generated in a mint transaction.

The nonce $k$ is returned for use by other algorithms, but is not public.


\subsection{\texorpdfstring{$\func{Mint}$}{Mint}}

This algorithm generates new coins from either a consensus-determined mining process, or by consuming non-Spark outputs from a base layer with public value.
Note that while such implementation-specific auxiliary data may be necessary for generating such a transaction and included, we do not specifically list this here.
Notably, the coin value used in this algorithm is assumed to be the sum of all public input values as specified by the implementation.

\textbf{Inputs}:
\begin{itemize}
    \item Security parameter $\lambda$ and public parameters $pp$
    \item A set of $t$ output coin public addresses, values, and memos: $$\{\addr_{\text{pk},j}, v_j, m_j\}_{j=0}^{t-1}$$
\end{itemize}

\textbf{Outputs}: Mint transaction $\text{tx}_{\text{mint}}$

\begin{enumerate}
    \item Generate a set $\func{OutCoins} = \{\func{CreateCoin}(\addr_{\text{pk},j}, v_j, m_j, 1)\}_{j=0}^{t-1}$ of output coins.
    \item Parse the output coin value commitments $\{\overline{C}_j\}_{j=0}^{t-1}$ from $\func{OutCoins}$, where each $\overline{C}_j$ contains nonce $k_j$.
    \item Generate a representation proof for value assertion: $$\Pi_{\text{val}} = \func{RepProve}\left( pp_{\text{rep}}, H, \{ \overline{C}_j - \com(v_j,0) \}_{j=0}^{t-1}; \{\hash_{\text{val}}(k_j)\}_{j=0}^{t-1} \right)$$
    \item Output the mint transaction $\func{tx}_{\text{mint}} = (\func{OutCoins}, \Pi_{\text{val}})$.
\end{enumerate}


\subsection{\texorpdfstring{$\func{Identify}$}{Identify}}

This algorithm allows a recipient (or designated entity) to determine if it controls a coin; if so, it computes the value, memo, and diversifier from the coin (in addition to the coin nonce).
It requires the incoming view key used to produce diversified addresses to do so.
If the coin is not destined for any diversified address, the algorithm returns failure.

It is assumed that the recipient has run the $\func{Verify}$ algorithm on the transaction generating the coin being identified.

\textbf{Inputs:} Security parameter $\lambda$, public parameters $pp$, incoming view key $\addr_{\text{in}}$, coin $\func{Coin}$

\textbf{Outputs:} Value $v$, memo $m$, diversifier $i$, nonce $k$

\begin{enumerate}
\item Parse the incoming view key $\addr_{\text{in}} = (s_1, P_2)$.
\item If $\func{Coin}$ was generated in a mint transaction, parse $\func{Coin} = (S, K, C, v, \overline{r})$; otherwise, parse $\func{Coin} = (S, K, C, \Pi_{\text{rp}}, \overline{r})$.
\item Generate an AEAD encryption key $k_{\text{aead}} = \func{AEADKeyGen}(s_1 K)$ and decrypt $$r = \func{AEADDecrypt}(k_{\text{aead}},\texttt{r},\overline{r});$$ if decryption fails, return failure.
\item If $\func{Coin}$ was generated in a mint transaction, parse the recipient data $r = (d, k, m)$; otherwise, parse $r = (v, d, k, m)$.
\item Check that $K = \hash_k(k)\hash_{\text{div}}(d)$, and return failure otherwise.
\item Check that $C = \com(v,\hash_{\text{val}}(k))$, and return failure otherwise.
\item Decrypt the diversifier $i = \func{SymDecrypt}(\func{SymKeyGen}(s_1),d)$.
\item Check that $$S = \comm(\hash_{\text{ser}}(k),0,0) + \comm(\hash_{Q_2}(s_1,i),0,0) + P_2,$$ and return failure otherwise.
\item Output $(v, m, i, k)$.
\end{enumerate}


\subsection{\texorpdfstring{$\func{Recover}$}{Recover}}

This algorithm allows a recipient (or designated entity) to determine if it controls a coin; if so, it computes the serial number, tag, value, memo, and diversifier from the coin (in addition to the coin nonce).
It requires the full view key used to produce diversified addresses to do so.
If the coin is not destined for any diversified address, the algorithm returns failure.

It is assumed that the recipient has run the $\func{Verify}$ algorithm on the transaction generating the coin being recovered.

\textbf{Inputs:} Security parameter $\lambda$, public parameters $pp$, full view key $\addr_{\text{full}}$, coin $\func{Coin}$

\textbf{Outputs:} Serial number $s$, tag $T$, value $v$, memo $m$, diversifier $i$, nonce $k$

\begin{enumerate}
\item Parse the full view key $\addr_{\text{full}} = (s_1, s_2, D, P_2)$.
\item Arrange the corresponding incoming view key $\addr_{\text{in}} = (s_1, P_2)$.
\item Run $\func{Identify}(\addr_{\text{in}},\func{Coin})$ to obtain $(v, m, i, k)$, and return failure if this operation fails.
\item Compute the serial number $$s = \hash_{\text{ser}}(k) + \hash_{Q_2}(s_1,i) + s_2$$ and tag $$T = (1/s)(U - D).$$
\item If $T$ has been constructed in any other valid recovery, return failure.
\item Output $(s, T, v, m, i, k)$.
\end{enumerate}


\subsection{\texorpdfstring{$\func{Spend}$}{Spend}}

This algorithm allows a recipient to generate a transaction that consumes coins it controls, and generates new coins destined for arbitrary public addresses.
The process is designed to be modular; in particular, only the full view key is required to generate the parallel one-out-of-many proof, which may be computationally expensive.
The use of spend keys is only required for the final Chaum-Pedersen proof step, which is of lower complexity.

It is assumed that the recipient has run the $\func{Recover}$ algorithm on all coins that it wishes to consume in such a transaction.

\textbf{Inputs:}
\begin{itemize}
    \item Security parameter $\lambda$ and public parameters $pp$
    \item A full view key $\addr_{\text{full}}$
    \item A spend key $\addr_{\text{sk}}$
    \item For each $u \in [0,w)$ coin to spend, a set of $N$ input coins $\func{InCoins}_u$ as part of a cover set\footnote{It is straightforward to support the more general case where cover sets do not share a common size; for simplicity, we assume a shared common size here.} selected from coins generated in previous valid transactions
    \item For each $u \in [0,w)$ coin to spend, the index in $\func{InCoins}_u$, serial number, tag, value, and nonce: $(l_u, s_u, T_u, v_u, k_u)$
    \item An integer fee value $f \in [0,v_{\text{max}})$
    \item A set of $t$ output coin public addresses, values, and memos: $$\{\addr_{\text{pk},j}, v_j, m_j\}_{j=0}^{t-1}$$
\end{itemize}

\textbf{Outputs:} Spend transaction $\text{tx}_{\text{spend}}$

\begin{enumerate}
    \item Parse the required full view key component $D$ from $\addr_{\text{full}}$.
    \item Parse the spend key $\addr_{\text{sk}} = (s_1, s_2, r)$.
    \item For each $u \in [0,w)$:
    \begin{enumerate}
        \item Parse the cover set serial number commitments and value commitments $\{(S_{i,u}, C_{i,u})\}_{i=0}^{N-1}$ from $\func{InCoins}_u$.
        \item Compute the serial number commitment offset: $$S_u' = \comm(s_u, 0, -\hash_{\text{ser}'}(s_u, D)) + D$$
        \item Compute the value commitment offset: $$C_u' = \com(v_u, \hash_{\text{val}'}(s_u, D))$$
        \item Generate a parallel one-out-of-many proof:
        \begin{multline*}
        (\Pi_{\text{par}})_u = \func{ParProve}(pp_{\text{par}},\{S_{i,u}, C_{i,u}\}_{i=0}^{N-1}, S_u',C_u'; \\
        (l_u, \hash_{\text{ser}'}(s_u, D), \hash_{\text{val}}(k_u) - \hash_{\text{val}'}(s_u, D)))
        \end{multline*}
    \end{enumerate}
    \item Generate a set $\func{OutCoins} = \{\func{CreateCoin}(\addr_{\text{pk},j}, v_j, m_j, 0)\}_{j=0}^{t-1}$ of output coins.
    \item Parse the output coin value commitments $\{\overline{C}_j\}_{j=0}^{t-1}$ from $\func{OutCoins}$, where each $\overline{C}_j$ contains nonce $k_j$.
    \item Generate a representation proof for balance assertion:
    \begin{multline*}
    \Pi_{\text{bal}} = \func{RepProve}\left( pp_{\text{rep}}, H, \sum_{u=0}^{w-1} C_u' - \sum_{j=0}^{t-1} \overline{C}_j - \com(f,0); \right. \\
    \left. \sum_{u=0}^{w-1} \hash_{\text{val}'}(s_u,D) - \sum_{j=0}^{t-1} \hash_{\text{val}}(k_j) \right)
    \end{multline*}
    \item Let $\mu = \hash_{\text{bind}}( \func{OutCoins}, f, \left\{ \func{InCoins}_u, S_u', C_u', T_u, (\Pi_{\text{par}})_u, \right\}_{u=0}^{w-1}, \Pi_{\text{bal}} )$.
    \item Generate a modified Chaum-Pedersen proof, where we additionally bind $\mu$ to the initial transcript:
    \begin{multline*}
    \Pi_{\text{chaum}} = \func{ChaumProve}((pp_{\text{chaum}}, \mu), \{S_u', T_u\}_{u=0}^{w-1}; \\
    (\{s_u, r, -\hash_{\text{ser}'}(s_u, D)\}_{u=0}^{w-1}))
    \end{multline*}
    \item Output the tuple:
    \begin{multline*}
    \text{tx}_{\text{spend}} = ( \func{OutCoins}, f, \\
    \left\{ \func{InCoins}_u, S_u', C_u', T_u, (\Pi_{\text{par}})_u \right\}_{u=0}^{w-1}, \Pi_{\text{chaum}}, \Pi_{\text{bal}} )
    \end{multline*}
\end{enumerate}
Note that it is possible to modify the balance proof to account for other input or output values not represented by coin value commitments, similarly to the handling of fees.
This observation can allow for the transfer of value into new coins without the use of a mint transaction, or a transfer of value to a transparent base layer.
Such transfer functionality is likely to introduce practical risk that is not captured by the protocol security model, and warrants thorough analysis.


\subsection{\texorpdfstring{$\func{Verify}$}{Verify}}

This algorithm assesses the validity of a transaction.

\textbf{Inputs:} either a mint transaction $\text{tx}_{\text{mint}}$ or a spend transaction $\text{tx}_{\text{spend}}$

\textbf{Outputs:} a bit that represents the validity of the transaction

If the input transaction is a mint transaction:
\begin{enumerate}
    \item Parse the transaction $\text{tx}_{\text{mint}} = (\func{OutCoins}, \Pi_{\text{val}})$.
    \item Parse the output coin values serial number commitments, and value commitments $\{(v_j, \overline{S}_j, \overline{C}_j)\}_{j=0}^{t-1}$ from $\func{OutCoins}$.
    \item For each $j \in [0,t)$:
    \begin{enumerate}
        \item If $\overline{S}_j$ appears in an output coin in this transaction or in any previously-verified transaction, output 0.
        \item Check that $v_j \in [0,v_{\text{max}})$, and output 0 if this fails.
    \end{enumerate}
    \item Check that $\func{RepVerify}\left( pp_{\text{rep}}, \Pi_{\text{val}}, H, \{\overline{C}_j - \com(v_j, 0)\}_{j=0}^{t-1} \right)$, and output 0 if this fails.
    \item Output 1.
\end{enumerate}

If the input transaction is a spend transaction:
\begin{enumerate}
    \item Parse the transaction:
    \begin{multline*}
    \text{tx}_{\text{spend}} = ( \func{OutCoins}, f, \\
    \left\{ \func{InCoins}_u, S_u', C_u', T_u, (\Pi_{\text{par}})_u, \Pi_{\text{chaum}} \right\}_{u=0}^{w-1}, \Pi_{\text{bal}} )
    \end{multline*}
    \item Parse the cover set serial number commitments and value commitments $\{(S_i, C_i)\}_{i=0}^{N-1}$ from $\func{InCoins}$.
    \item For each $u \in [0,w)$:
    \begin{enumerate}
        \item Parse the cover set serial number commitments and value commitments $\{(S_{i,u}, C_{i,u})\}_{i=0}^{N-1}$ from $\func{InCoins}_u$, and check that each cover set member corresponds to a valid coin generated in a previous valid transaction.
        \item Check that $T_u$ does not appear again in this transaction or in any previously-verified transaction, and output 0 if it does.
        \item Check that $\func{ParVerify}(pp_{\text{par}},(\Pi_{\text{par}})_u,\{S_{i,u},C_{i,u}\}_{i=0}^{N-1},S_u',C_u')$, and output 0 if this fails.
    \end{enumerate}
    \item Compute the binding hash $\mu$ as before, check that $$\func{ChaumVerify}((pp_{\text{chaum}},\mu),\Pi_{\text{chaum}},\{S_u',T_u\}_{u=0}^{w-1}),$$ and output 0 if this fails.
    \item For each $j \in [0,t)$:
    \begin{enumerate}
        \item If $\overline{S}_j$ appears in an output coin in this transaction or in any previously-verified transaction, output 0.
        \item Check that $\func{RangeVerify}(pp_{\text{rp}},(\Pi_{\text{rp}})_j,C)$, and output 0 if this fails.
    \end{enumerate}
    \item Check that $f \in [0,v_{\text{max}})$, and output 0 if this fails.
    \item Check that $$\func{RepVerify}\left( pp_{\text{rep}}, \Pi_{\text{bal}}, H, \sum_{u=0}^{w-1} C_u' - \sum_{j=0}^{t-1} \overline{C}_j - \com(f,0) \right)$$ and output 0 if this fails.
    \item Output 1.
\end{enumerate}


\section{Multisignature Operations}

It is often useful to permit transactions requiring multiple parties to authorize; the parties may be mututally untrusting, and it may not be sufficient to rely on a separate trusted third party.
In this case, we require processes for distributed key and spend transaction generation that require either a set of specified parties or a threshold subset of a given size to complete.
Specifically, we describe a method for such signing groups to perform the $\func{CreateKeys}$ and $\func{Spend}$ algorithms to produce keys and spend transactions indistinguishable from others.

The method we use is inspired by techniques from previous work.
Because view keys are assumed to be fully known by all signers in a group, we use a method related to that of MuSig \cite{musig}, for which we do not require any threshold computations.
For spend key generation and threshold signing, FROST \cite{frost} introduces a one-round process with a precomputation phase that can be performed either during key generation or at the time of signing.
Later work \cite{schnorrwithschnorr} examines FROST security and proposes a more efficient signing protocol for it; however, this introduces subtle security implications that are examined and addressed in \cite{bellare_frost}.
We use this approach for our signing process.
Note that we defer a complete security analysis of our construction to future work.

Throughout this section, suppose we have a group of $\nu$ players who wish to collaboratively produce keys, and such that a specified threshold $1 \leq t \leq \nu$ of the players is required to produce an authorizing proof spending coins directed to any address associated to the keys.

For the modified algorithms we present here, sample cryptographic hash functions $$\hash_{\text{pok}},\hash_{s_1},\hash_{s_2},\hash_{\rho},\hash_{F},\hash_{H}: \{0,1\}^* \to \F$$ uniformly at random.


\subsection{\texorpdfstring{$\func{CreateKeys}$}{CreateKeys}}

To produce key components, each player $1 \leq \alpha \leq \nu$ engages in the following two-round key generation process:
\begin{enumerate}
    \item Selects a set of coefficients $\{a_{\alpha,j}\}_{j=0}^{t-1} \subset \F$ uniformly at random, and uses them to define the polynomial $f_\alpha(x) = \sum_{j=0}^{t-1} a_{\alpha,j}x^j$.
    \item Selects view key shares $s_{1,\alpha},s_{2,\alpha} \in \F \setminus \{0\}$ uniformly at random.
    \item Produces a proof of knowledge of $a_{\alpha,0}$:
    \begin{enumerate}
        \item Chooses $k_\alpha \in \F$ uniformly at random.
        \item Sets $R_\alpha = k_\alpha G$.
        \item Sets $c_\alpha = \hash_{\text{pok}}(\alpha,a_{\alpha,0}G,R_\alpha)$.
        \item Sets $\mu_\alpha = k_\alpha + a_{\alpha,0}c_\alpha$.
    \end{enumerate}
    \item Produces a vector of commitments $C_\alpha = \{C_{\alpha,j}\}_{j=0}^{t-1} = \{a_{\alpha,j}G\}_{j=0}^{t-1}$ to its coefficients.
    \item Sends the tuple $(R_\alpha,\mu_\alpha,C_\alpha,s_{1,\alpha},s_{2,\alpha})$ to all other players $1 \leq \beta \neq \alpha \leq \nu$.
    \item On receipt of a tuple $(R_\beta,\mu_\beta,C_\beta,s_{1,\beta},s_{2,\beta})$ from another player $\beta$:
    \begin{enumerate}
        \item Checks that $s_{1,\beta} \neq 0$ and $s_{2,\beta} \neq 0$ and aborts otherwise.
        \item Verifies the proof of knowledge by checking that $$\mu_\beta G - \hash_{\text{pok}}(\beta,C_{\beta,0},R_\beta)C_{\beta,0} = R_\beta$$ and aborting otherwise.
    \end{enumerate}
    \item For each $1 \leq \beta \leq \nu$, computes a player share $\widehat{r}_{\alpha,\beta} = f_\alpha(\beta)$ and sends it to player $\beta$.
    \item On receipt of a player share $\widehat{r}_{\beta,\alpha}$ from another player $\beta$, verifies the share by checking that $$\sum_{j=0}^{t-1} \alpha^jC_{\beta,j} = \widehat{r}_{\beta,\alpha}G$$ and aborting otherwise.
    \item Computes its private spend key share $r_\alpha = \sum_{\beta=1}^\nu \widehat{r}_{\beta,\alpha}$ and full view key component $D = \sum_{\beta=1}^\nu C_{\beta,0}$.
    \item Computes the group view keys:
    \begin{align*}
        s_1 &= \sum_{\beta=1}^\nu \hash_{s_1}(\{s_{1,\gamma}\}_{\gamma=1}^\nu,\beta)s_{1,\beta} \\
        s_2 &= \sum_{\beta=1}^\nu \hash_{s_2}(\{s_{2,\gamma}\}_{\gamma=1}^\nu,\beta)s_{2,\beta}
    \end{align*}
\end{enumerate}
Using the tuple $(s_1,s_2,D)$, any player can additionally compute the full view key component $P_2 = \comm(s_2,0,0) + D$.
Since each player holds the aggregate incoming view key, it can compute public addresses using $\func{CreateAddress}$ as needed.

Note that each player should confirm that all other players have completed the key generation process before making addresses available to receive coins; otherwise, a malicious player might selectively fail to send its shares to all other players, meaning some players may be unable to properly compute their private spend key shares.


\subsection{\texorpdfstring{$\func{Precompute}$}{Precompute}}

The signing group can reduce the communication complexity of proof generation by precomputing and sharing sets of nonce data.
Each future signing operation uses one such nonce set for each signing player, which cannot be reused.
The signing group can precompute as many nonce sets as needed for expected signing operations, and can perform this operation whenever additional nonce sets are required.
In particular, the group may wish to do so during the key generation process, where the added communication round may be less impactful than during later proof generation.

To precompute $\pi$ sets of nonce data, each player $1 \leq \alpha \leq \nu$ engages in the following one-round process:
\begin{enumerate}
    \item For $0 \leq k < \pi$, it selects $d_{\alpha,k}, e_{\alpha,k} \in \F \setminus \{0\}$ uniformly at random and defines $D_{\alpha,k} = d_{\alpha,k}G$ and $E_{\alpha,k} = e_{\alpha,k}G$.
    \item Generates a vector $L_\alpha$ such that for $0 \leq k < \pi$, we have $L_{\alpha,k} = (D_{\alpha,k}, E_{\alpha,k})$; that is, $L_{\alpha}$ contains $\pi$ nonce pairs.
    \item Sends $L_\alpha$ to all other players.
    \item On receipt of a vector $L_\beta$ from another player $\beta$, checks that $D_{\beta,k} \neq 0$ and $E_{\beta,k} \neq 0$ for all $0 \leq k < \pi$, and aborts otherwise.
\end{enumerate}



\subsection{\texorpdfstring{$\func{Spend}$}{Spend}}

Because all players possess the aggregate full view key corresponding to public addresses, any player can use it to construct all transaction components except the modified Chaum-Pedersen proof.
We describe now how a threshold of $t$ signers collaboratively produce such a proof to authorize the spending of coins, with the following proof inputs (using our previous notation):
$$\{pp_{\text{chaum}}, \{S_u', T_u\}_{u=0}^{w-1}; (\{s_u, r, -\hash_{\text{ser}'}(s_u, D)\}_{u=0}^{w-1})\}$$

For the sake of notation convenience, we assume that the signing players are indexed $1 \leq \alpha \leq t$.
Further, assume that each nonce list $L_\alpha$ contains $k + 1 \geq w$ unused nonces.
We also assume the context binding value $\mu$ has been defined.
Each such player $\alpha$ engages in the following one-round process:
\begin{enumerate}
    \item Parses the next available set of nonces $\{(D_{\beta,k-u},E_{\beta,k-u})\}_{u=0}^{w-1}$ in each $L_\beta$ for $1 \leq \beta \leq t$ (and removes them from each list after use) to compute, for $0 \leq u < w$ and $1 \leq \gamma \leq t$, the following:
    $$\rho_{u,\gamma} = \hash_{\rho}(\{\beta,D_{\beta,k-u},E_{\beta,k-u}\}_{\beta=1}^{t},\gamma,\mu,S_u',T_u)$$
    \item Sets the initial proof commitments
    \begin{multline*}
        A_1 = \sum_{u=0}^{w-1} \Biggl( \hash_F\left( \{\rho_{u,\beta}\}_{\beta=1}^t \right)F + \hash_H\left( \{\rho_{u,\beta}\}_{\beta=1}^t \right)H + \\
        \sum_{\beta=1}^t \left( D_{\beta,k-u} + \rho_{u,\beta} E_{\beta,k-u} \right) \Biggr)
    \end{multline*}
    and
    \begin{equation*}
        \{A_{2,u}\}_{u=0}^{w-1} = \left\{ \hash_F\left( \{\rho_{u,\beta}\}_{\beta=1}^t \right)T_u + \sum_{\beta=1}^t \left( D_{\beta,k-u} + \rho_{u,\beta} E_{\beta,k-u} \right) \right\}.
    \end{equation*}
    \item Computes the challenge $c$ using the proof transcript as in the original $\func{Spend}$ description.
    \item Computes its Lagrange coefficient $$\lambda_\alpha = \prod_{\beta=1,\beta \neq \alpha}^t \left( \frac{\beta}{\beta-\alpha} \right)$$ and the response share $$t_{2,\alpha} = \sum_{u=0}^{w-1} (d_{\alpha,k-u} + \rho_{u,\alpha} e_{\alpha,k-u} + \lambda_\alpha r_\alpha c^u),$$ and sends $t_{2,\alpha}$ to the other signing players.
    \item On receipt of $t_{2,\beta}$ from another player, checks that $$t_{2,\beta}G = \sum_{u=0}^{w-1} \left( D_{\beta,k-u} + \rho_{u,\beta} E_{\beta,k-u} + c^u\lambda_{\beta} \sum_{\gamma=1}^{\nu}\sum_{j=0}^{t-1} \beta^j C_{\gamma,j} \right)$$ and aborts otherwise.
    \item On receipt of all $t_{2,\beta}$ values, computes the proof responses:
    \begin{align*}
        \{t_{1,u}\}_{u=0}^{w-1} &= \left\{ \hash_F\left( \{\rho_{u,\beta}\}_{\beta=1}^t \right) + c^u s_u \right\} \\
        t_2 &= \sum_{\beta=1}^t t_{2,\beta} \\
        t_3 &= \sum_{u=0}^{w-1} \left( \hash_H\left( \{\rho_{u,\beta}\}_{\beta=1}^t \right) - c^u \hash_{\text{ser}'}(s_u,D) \right)
    \end{align*}
\end{enumerate}


\section{View Keys and Payment Proofs}

The key and proof structures in Spark enable flexible and useful functionality relating to transaction scanning, generation, and disclosure.

The incoming view key is used in $\func{Identify}$ operations to determine when a coin is directed to an associated public address, and to determine the coin's value and associated memo data.
This permits two use cases of note.
In one case, blockchain scanning can be delegated to a device or service without delegating spend authority for identified coins.
In another case, wallet software in possession of a spend key can keep this key encrypted or otherwise securely stored during scanning operations, reducing key exposure risks.

The full view key is used in $\func{Recover}$ operations to additionally compute the serial number and tag for coins directed to an associated public address.
These tags can be used to identify a transaction spending the coin.
Providing this key to a third party permits identification of incoming transactions and detection of outgoing transactions, which additionally provides balance computation, without delegating spend authority.
Users like public charities may wish to permit public oversight of funds with this functionality.
Other users may wish to provide this functionality to an auditor or accountant for bookkeeping purposes.
In the case where an address is used in threshold multisignature operations, a cosigner may wish to know if or when another cohort of cosigners has produced a transaction spending funds.

Further, the full view key is used in $\func{Spend}$ to generate one-out-of-many proofs.
Since the parallel one-out-of-many proof used in Spark can be computationally expensive, it may be unsuitable for generation by a computationally-limited device like a hardware wallet.
Providing this key to a more powerful device enables easy generation of this proof (and other transaction components like range proofs), while ensuring that only the device holding the spend key can complete the transaction by generating the simple modified Chaum-Pedersen proof.

Payment proofs, which we introduce in Appendix \ref{app:payment}, allow for disclosure of data for individual coins.
Specifically, a payment proof asserts in zero knowledge that the prover knows the spend key used to authorize the transaction generating a given coin that is destined for a given public address.
The proof convinces a verifier that the holder of the incoming view key for the public address can successfully identify the coin, as well as provides the verifier with the value and memo for the coin.
Unlike view keys, which provide broad visibility into transactions associated to a public address, a payment proof is limited to a single coin and can be bound to an arbitrary proof context to prevent replay.

Payment proofs may be useful in a number of circumstances.
For example, a customer may issue a payment to a retailer, but fail to use the correct diversified address or memo required by the retailer to associate the payment to the customer's order.
By providing the retailer with a payment proof, the customer can assert that it produced a coin destined for the retailer's address.
In another use case, a business may wish to make public details of a donation to a charity without publicly disclosing its full view key.
By providing a payment proof, anyone can verify that the specified coin was destined for the charity's address and confirm the value and memo associated to the coin.


\section{Efficiency}

It is instructive to examine the efficiency of spend transactions in size, generation complexity, and verification complexity.
In addition to our previous notation for parameters, let $v_{\text{max}} = 2^{64}$, so coin values and fees can be represented by $8$-byte unsigned integers.
Further, suppose coin memos are fixed at $M$ bytes in length, diversifiers are restricted to $I$ bytes in length, with a $16$-byte authentication tag and $32$-byte key commitment; this is the case for the ChaCha20-Poly1305 authenticated symmetric encryption construction (modified using the technique in \cite{key_commitment}), for example \cite{chachapoly}.
Additionally, the arguments in \cite{schnorr} imply that Schnorr representation proofs can use truncated hash outputs for reduced proof size.
Transaction size data for specific component instantiations is given in Table \ref{table:size}, where we consider the size in terms of group elements, field elements, and other data.
Note that we do not include input ambiguity set references in this data, as this depends on implementation-specific selection and representation criteria.

\begin{table}
    \caption{Spend transaction size by component}
    \label{table:size}
    \centering
    \begin{tabular}{|l|l|r|r|r|}
        \hline
        \textbf{Component} & \textbf{Instantiation} & \textbf{Size ($\G$)} & \textbf{Size ($\F$)} & \textbf{Size (bytes)} \\
        \hline
        $f$ & & & & $8$ \\
        $\Pi_{\text{rp}}$ & Bulletproofs+ & $2 \lceil \lg(64t) \rceil + 3$ & $3$ & \\
        $\Pi_{\text{bal}}$ & Schnorr (short)& & $1.5$ & \\
        $\Pi_{\text{chaum}}$ & this paper & $w + 1$ & $w + 2$ & \\
        \hline
        \multicolumn{5}{|c|}{Input data ($w$ coins)} \\
        \hline
        $(S',C')$ & & $2w$ & & \\
        $\Pi_{\text{par}}$ & this paper & $(2m + 2)w$ & $[m(n-1) + 3]w$ & \\
        \hline
        \multicolumn{5}{|c|}{Output data ($t$ coins)} \\
        \hline
        $(S,K,C)$ & & $3t$ & & \\
        $\overline{r}$ & ChaCha20-Poly1305 & & & $(8 + M + I + 48)t$ \\
        \hline
    \end{tabular}
\end{table}

To evaluate the verification complexity of spend transactions using these components, we observe that verification in constructions like the parallel one-out-of-many proving system in this paper, Bulletproof+ range proving system, Schnorr representation proving system, and modified Chaum-Pedersen proving system in this paper all reduce to single linear combination evaluations in $\G$.
Because of this, proofs can be evaluated in batches if the verifier first weights each proof by a random value in $\F$, such that distinct group elements need only appear once in the resulting weighted linear combination.
Notably, techniques like that of \cite{pippenger} can be used to reduce the complexity of such evaluations by up to a logarithmic factor.
Suppose we wish to verify a batch of $B$ transactions, each of which spends $w$ coins and generates $t$ coins.
Table \ref{table:time} shows the verification batch complexity in terms of total distinct elements of $\G$ that must be included in a linear combination evaluation.

\begin{table}
    \caption{Spend transaction batch verification complexity for $B$ transactions with $w$ spent coins and $t$ generated coins}
    \label{table:time}
    \centering
    \begin{tabular}{|l|r|}
        \hline
        \textbf{Component} & \textbf{Complexity} \\
        \hline
        Parallel one-out-of-many & $B[w(2m + 2) + 2n^m] + 2mn + 1$ \\
        Bulletproofs+ & $B(t + 2\lg(64t) + 3) + 128T + 2$ \\
        Modified Chaum-Pedersen & $B(3w + 1) + 4$ \\
        Schnorr & $B(w + t + 1) + 2$ \\
        \hline
    \end{tabular}
\end{table}

We further comment that the parallel one-out-of-many proving system presented in this paper may be further optimized in verification.
Because corresponding elements of the $\{S_i\}$ and $\{V_i\}$ input sets are weighted identically in the protocol verification equations, it may be more efficient (depending on implementation) to combine these elements with a sufficient weight prior to applying the proof-specific weighting identified above for batch verification.
Initial tests using a variable-time curve library suggest significant reductions in verification time with this technique.


\section*{Acknowledgments}

The authors thank pseudonymous collaborator \texttt{koe} for ongoing discussions during the development of this work.
The authors gratefully acknowledge Nikolas Kr\"{a}tzschmar for identifying an earlier protocol flaw relating to tag generation.
The authors further thank independent researcher Luke Parker (\texttt{kayabaNerve}) for pointing out the failure of the security model to capture the case of an adversary producing a duplicate serial commitment prior to an honest transaction being added to the ledger.


\bibliographystyle{splncs04}
\bibliography{main}

\appendix


\section{Modified Chaum-Pedersen Proving System}
\label{app:chaum}

The proving system is a tuple of algorithms $(\func{ChaumProve},\func{ChaumVerify})$ for the following relation:
\begin{multline*}
\left\{ pp_{\text{chaum}}, \{S_i, T_i\}_{i=0}^{l-1} \subset \G^2 ; (\{x_i, y_i, z_i\}_{i=0}^{l-1}) \subset \F^3 : \right. \\
\left. \forall i \in [0,l), S_i = x_i F + y_i G + z_i H, U = x_i T_i + y_i G \right\}
\end{multline*}
Our protocol uses a power-of-challenge technique inspired by a method used for aggregating Schnorr signatures \cite{batchschnorr}.
The protocol proceeds as follows:
\begin{enumerate}
    \item The prover selects random $\{r_i,s_i\}_{i=0}^{l-1}, t \in \F$.
    It computes the values
    \begin{align*}
        A_1 &= \sum_{i=0}^{l-1} r_i F + \sum_{i=0}^{l-1} s_i G + tH \\
        \{A_{2,i}\}_{i=0}^{l-1} &= \{r_i T_i + s_i G\}_{i=0}^{l-1}
    \end{align*}
    and sends these values to the verifier.
    \item The verifier selects a random challenge $c \in \F$ and sends it to the prover.
    \item The prover computes responses
    \begin{align*}
        \{t_{1,i}\}_{i=0}^{l-1} &= \{r_i + c^{i+1} x_i\}_{i=0}^{l-1} \\
        t_2 &= \sum_{i=0}^{l-1} (s_i + c^{i+1} y_i) \\
        t_3 &= t + \sum_{i=0}^{l-1} c^{i+1} z_i
    \end{align*}
    and sends them to the verifier.
    \item The verifier accepts the proof if and only if $$A_1 + \sum_{i=0}^{l-1} c^{i+1} S_i = \sum_{i=0}^{l-1} t_{1,i} F + t_2 G + t_3 H$$ and $$\sum_{i=0}^{l-1} (A_{2,i} + c^{i+1} U) = \sum_{i=0}^{l-1} t_{1,i} T_i + t_2 G.$$
\end{enumerate}

This interactive protocol can be made non-interactive using the Fiat-Shamir technique, which replaces the verifier challenge $c$ with the output of a cryptographic hash function on transcript inputs.
We now prove that the protocol is complete, special sound, and special honest-verifier zero knowledge.

\begin{proof}
Completeness of the protocol follows by inspection.

We now show it is (l+1)-special sound by building a polynomial-time extractor as follows.
Given a statement and initial proof transcript $(A_1, \{A_{2_i}\}_{i=0}^{l-1})$, the verifier sends $l+1$ distinct challenge values $c_0, c_1, \ldots, c_l$ and receives the corresponding transcript values $(\{t^0_{1,i}\}_{i=0}^{l-1}, t^0_2, t^0_3), \ldots, (\{t^l_{1,i}\}_{i=0}^{l-1}, t^l_2, t^l_3)$ from the prover.
From the first verification equation, we build the following linear system:
\begin{align*}
A_1 + \sum_{i=0}^{l-1} c_0^{i+1} S_i &= \sum_{i=0}^{l-1} t^0_{1,i} F + t^0_2 G + t^0_3 H \\
A_1 + \sum_{i=0}^{l-1} c_1^{i+1} S_i &= \sum_{i=0}^{l-1} t^1_{1,i} F + t^1_2 G + t^1_3 H \\
&\vdotswithin{=} \\
A_1 + \sum_{i=0}^{l-1} c_l^{i+1} S_i &= \sum_{i=0}^{l-1} t^l_{1,i} F + t^l_2 G + t^l_3 H
\end{align*}

Subtracting the first equation from the rest, we obtain another linear system:
\begin{gather}
\begin{aligned}
\label{eqn:chaum}
\sum_{i=0}^{l-1} (c_1^{i+1} - c_0^{i+1}) S_i &= \sum_{i=0}^{l-1} (t^1_{1,i} - t^0_{1,i})F + (t^1_2 - t^0_2)G + (t^1_3 - t^0_3)H \\
\sum_{i=0}^{l-1} (c_2^{i+1} - c_0^{i+1}) S_i &= \sum_{i=0}^{l-1} (t^2_{1,i} - t^0_{1,i})F + (t^2_2 - t^0_2)G + (t^2_3 - t^0_3)H \\
&\vdotswithin{=} \\
\sum_{i=0}^{l-1} (c_l^{i+1} - c_0^{i+1}) S_i &= \sum_{i=0}^{l-1} (t^l_{1,i} - t^0_{1,i})F + (t^l_2 - t^0_2)G + (t^l_3 - t^0_3)H
\end{aligned}
\end{gather}

Finally, we let the set $\{x_i\}_{i=0}^{l-1} \subset \F$ be defined through the following linear system:
\begin{align*}
\sum_{i=0}^{l-1} (c_1^{i+1} - c_0^{i+1})x_i &= \sum_{i=0}^{l-1} (t^1_{1,i} - t^0_{1_i}) \\
\sum_{i=0}^{l-1} (c_2^{i+1} - c_0^{i+1})x_i &= \sum_{i=0}^{l-1} (t^2_{1,i} - t^0_{1_i}) \\
&\vdotswithin{=} \\
\sum_{i=0}^{l-1} (c_l^{i+1} - c_0^{i+1})x_i &= \sum_{i=0}^{l-1} (t^l_{1,i} - t^0_{1_i})
\end{align*}
Since each challenge is uniformly distributed at random, the square coefficient matrix corresponding to the system has nonzero determinant except with negligible probability, and hence the system is solvable for all $\{x_i\}_{i=0}^{l-1}$.
Further, we can form similar linear systems to define corresponding $\{y_i\}_{i=0}^{l-1}$ and $\{z_i\}_{i=0}^{l-1}$ such that we let $S_i = x_i F + y_i G + z_i H$ and the equations in system \ref{eqn:chaum} hold.

It remains to show that these solutions are unique; that is, that no $S_i$ has a different representation with coefficients $x_i',y_i',z_i'$ consistent with successful verification.
If this were the case, then we must have the polynomial equation $\sum_{i=0}^{l-1} c^{i+1}(x_i - x_i') = 0$ in $c$; however, since $c$ is selected randomly by the verifier, all coefficients of the polynomial must (with overwhelming probability) be zero by the Schwartz-Zippel lemma.
Hence each $x_i = x_i'$ (and by the same reasoning, $y_i = y_i'$ and $z_i = z_i'$), and the extracted witness set is unique.

To show the protocol is special honest-verifier zero knowledge, we construct a valid simulator producing transcripts identically distributed to those of valid proofs.
The simulator chooses a random challenge $c \in \F$ and random values $\{t_{1,i}\}_{i=0}^{l-1}, t_2, t_3 \in \F$.
It also randomly selects $\{A_{2,i}\}_{i=1}^{l-1} \in \G$, and sets $$A_1 = \sum_{i=0}^{l-1} t_{1,i} F + t_2 G + t_3 H - \sum_{i=0}^{l-1} c^{i+1} S_i$$ and $$A_{2,0} = \sum_{i=0}^{l-1} t_{1,i} T_i + t_2 G - \sum_{i=1}^{l-1} A_{2,i} -  \sum_{i=0}^{l-1} c^{i+1} U.$$
The forms of $A_1$ and $A_{2,0}$ are defined such that the verification equations hold, and therefore such a transcript will be accepted by an honest verifier.
Observe that all transcript elements in a valid proof are independently distributed uniformly at random if the generators $F,G,H,U$ are independent, as are transcript elements produced by the simulator.

This completes the proof.
\end{proof}


\section{Parallel One-out-of-Many Proving System}
\label{app:parallel}

The proving system itself is a tuple of algorithms $(\func{ParProve},\func{ParVerify})$ for the following relation, where we let $N = n^m$:
\begin{multline*}
\left\{ pp_{\text{par}}, \{S_k,V_k\}_{i=0}^{N-1} \subset \G^2, S',V' \in \G ; l \in \mathbb{N}, (s,v) \in \F : \right. \\
\left. 0 \leq l < N, S_l - S' = \comm(0,0,s), V_l - V' = \com(0,v) \right\}
\end{multline*}

Let $\delta(i,j): \mathbb{N}^2 \to \F$ be the Kronecker delta function.
For any integers $k$ and $j$ such that $0 \leq k < N$ and $0 \leq j < m$, let $k_j$ denote the $j$ digit of the $n$-ary decomposition of $k$.
Let $\func{MatrixCom}: \F^{mn} \times \F^{mn} \times \F \to \G$ be an additively-homomorphic matrix commitment construction that commits to the entries of two matrices, and is perfectly hiding and computationally binding.

The protocol proceeds as follows, where we use some of the notation of \cite{lelantus,triptych}:
\begin{enumerate}
    \item The prover selects $$r_A, r_B, \{a_{j,i}\}_{j=0,i=1}^{m-1,n-1} \in \F$$ uniformly at random, and, for each $j \in [0,m)$, sets $$a_{j,0} = -\sum_{i=1}^{n-1} a_{j,i}.$$
    \item The prover computes the following:
    \begin{align*}
        A &\equiv \func{MatrixCom}\left(\{a_{j,i}\}_{j,i=0}^{m-1,n-1}, \{-a_{j,i}^2\}_{j,i=0}^{m-1,n-1}, r_A\right) \\
        B &\equiv \func{MatrixCom}\left(\{\delta(l_{j},i)\}_{j,i=0}^{m-1,n-1}, \lbrace a_{j,i}(1-2\delta(l_j,i))\rbrace_{j,i=0}^{m-1,n-1}, r_B\right)
    \end{align*}
    \item For each $j \in [0,m)$, the prover selects $\rho_j, \rho'_j \in \F$ uniformly at random, and computes the following:
    \begin{align*}
        X_j &\equiv \sum_{k=0}^{N-1}p_{k,j}(S_k - S') + \comm(0, 0, \rho_j) \\
        X'_j &\equiv \sum_{k=0}^{N-1}p_{k,j}(V_k - V') + \com(0, \rho'_j)
    \end{align*}
    Here each $p_{k,j}$ is defined such that for all $k \in [0,N)$ we have $$\prod_{j=0}^{m-1} \left( \delta(l_j,k_j)x + a_{j,k_j} \right) = \delta(l,k)x^m + \sum_{j=0}^{m-1} p_{k,j}x^j$$ for indeterminate $x$.
    \item The prover sends $A, B, \{X_j, X'_j\}_{j=0}^{m-1}$ to the verifier.
    \item The verifier selects $x \in \F$ uniformly at random and sends it to the prover.
    \item For each $j \in [0,m)$ and $i \in [1,n)$, the prover computes $f_{j,i} \equiv \delta(l_{j},i)x + a_{j,i}$ and the following values:
    \begin{align*}
        z &\equiv r_A + xr_B \\
        z_S &\equiv sx^m -  \sum_{j=0}^{m-1}\rho_j x^j \\
        z_V &\equiv vx^m - \sum_{j=0}^{m-1}\rho'_j x^j
    \end{align*}
    \item The prover sends $\{f_{j,i}\}_{j=0,i=1}^{m-1,n-1}, z, z_S, z_V$ to the verifier.
    \item For each $j \in [0,m)$, the verifier sets $f_{j,0} \equiv x - \sum_{i=1}^{n-1} f_{j,i}$ and accepts the proof if and only if
    $$A + xB = \func{MatrixCom}\left(\lbrace f_{j,i} \rbrace_{j,i=0}^{m-1,n-1}, \lbrace f_{j,i}(x - f_{j,i})\rbrace_{j,i=0}^{m-1,n-1}, z\right)$$
    and
    \begin{align*}
        \sum_{k=0}^{N-1} \left(\prod_{j=0}^{m-1} f_{j,k_j}\right)(S_k - S') - \sum_{j=0}^{m-1} x^j X_j &= \comm(0, 0, z_S) \\
        \sum_{k=0}^{N-1} \left(\prod_{j=0}^{m-1} f_{j,k_j}\right)(V_k - V') - \sum_{j=0}^{m-1} x^j X'_j &= \com(0, z_V)
    \end{align*}
    are true.
\end{enumerate}

This interactive protocol can be made non-interactive using the Fiat-Shamir technique, which replaces the verifier challenge $x$ with the output of a cryptographic hash function on transcript inputs.

We now prove that the above protocol is complete, special sound, and honest-verifier zero knowledge.
The proofs proceed similarly to those of \cite{bootle,lelantus,triptych}.

\begin{proof}
    Completeness of the protocol follows by straightforward algebra.

    To show that the protocol is special honest-verifier zero knowledge, we construct a simulator that, when provided a valid statement and random verifier challenge $x$, produces a proof transcript identically distributed to that of a real proof.

    To produce our simulated transcript on random $x$, the simulator samples $$B,\{X_j,X'_j\}_{j=1}^{m-1} \in \G$$ and $$z,z_S,z_V,\{f_{j,i}\}_{j=0,i=1}^{m-1,n-1} \in \F$$ uniformly at random.
    It defines
    $$f_{j,0} = x - \sum_{i=1}^{n-1} f_{j,i}$$
    for each $j \in [0,m)$, and sets
    $$A = \func{MatrixCom}\left(\lbrace f_{j,i} \rbrace_{j,i=0}^{m-1,n-1}, \lbrace f_{j,i}(x - f_{j,i})\rbrace_{j,i=0}^{m-1,n-1}, z\right) - xB$$
    as well.
    It uses the final two verification equations to compute $X_0$ and $X'_0$:
    \begin{alignat*}{1}
        X_0 &= \sum_{k=0}^{N-1} \left(\prod_{j=0}^{m-1} f_{j,k_j}\right)(S_k - S') - \sum_{j=1}^{m-1} x^j X_j - \comm(0, 0, z_S) \\
        X'_0 &= \sum_{k=0}^{N-1} \left(\prod_{j=0}^{m-1} f_{j,k_j}\right)(V_k - V') - \sum_{j=1}^{m-1} x^j X'_j - \com(0, z_V)
    \end{alignat*}

    Since the challenge $x$ is sampled uniformly at random by construction, the commitment constructions are perfectly hiding, $\{\rho_j,\rho'_j\}_{j=0}^{m-1}$ are sampled uniformly at random in a real proof, and the decisional Diffie-Hellman problem is hard in $\G$, all proof elements in both the simulation and real proofs are either independently uniformly distributed at random or uniquely determined by other transcript elements.
    Hence the protocol is special honest-verifier zero knowledge.

    We now show that the protocol is $(m+1)$-special sound for $m > 1$.
    That is, we construct an extractor that, when presented with a set of $m+1$ distinct challenges and corresponding responses to the same initial statement, produces a set of extracted witness elements consistent with the statement.
    Consider a collection of $m+1$ distinct challenges $\{x_\iota\}_{\iota=0}^m$, and corresponding valid responses:
    $$\left\{ \{f_{j,i}^{(\iota)}\}_{j=0,i=1}^{m-1,n-1}, z^{(\iota)}, z_S^{(\iota)}, z_V^{(\iota)} \right\}_{\iota=0}^m$$
    Successful verification on indices $\iota \in \{0,1\}$ gives the following:
    \begin{multline*}
        (x^{(0)} - x^{(1)})B = \func{MatrixCom}\left( \{f_{j,i}^{(0)} - f_{j,i}^{(1)}\}_{j,i=0}^{m-1,n-1}, \right. \\
        \left. \{f_{j,i}^{(0)}(x^{(0)} - f_{j,i}^{(0)}) - f_{j,i}^{(1)}(x^{(1)} - f_{j,i}^{(1)})\}_{j,i=0}^{m-1,n-1}, z^{(0)} - z^{(1)} \right)
    \end{multline*}
    For all $j \in [0,m)$ and $i \in [0,n)$, if we let
    $$b_{j,i} = \frac{f_{j,i}^{(0)} - f_{j,i}^{(1)}}{x^{(0)} - x^{(1)}}$$
    and
    $$c_{j,i} = \frac{f_{j,i}^{(0)}(x^{(0)} - f_{j,i}^{(0)}) - f_{j,i}^{(1)}(x^{(1)} - f_{j,i}^{(1)})}{x^{(0)} - x^{(1)}}$$
    and
    $$r_B = \frac{z^{(0)} - z^{(1)}}{x^{(0)} - x^{(1)}},$$
    then we can express
    $$B = \func{MatrixCom}\left( \{b_{j,i}\}_{j,i=0}^{m-1,n-1}, \{c_{j,i}\}_{j,i=0}^{m-1,n-1}, r_B \right).$$
    If for $j \in [0,m)$ and $i \in [0,n)$ we further define
    $$a_{j,i} = f_{j,i}^{(0)} - x^{(0)}b_{i,j}$$
    and
    $$d_{i,j} = f_{j,i}^{(0)}(x^{(0)} - f_{j,i}^{(0)}) - x^{(0)}c_{j,i}$$
    and $r_A = z^{(0)} - x^{(0)}r_B$, then we can express
    $$A = \func{MatrixCom}\left( \{a_{j,i}\}_{j,i=0}^{m-1,n-1}, \{d_{j,i}\}_{j,i=0}^{m-1,n-1}, r_A \right)$$
    as well.
    Observe that since the commitment construction is computationally binding, for all $\iota \in [0,m]$ we must have $b_{j,i}x^{(\iota)} + a_{j,i} = f_{j,i}^{(\iota)}$ and $c_{j,i}x^{(\iota)} + d_{j,i} = f_{j,i}^{(\iota)}(x^{(\iota)} - f_{j,i}^{(\iota)})$ for $j \in [0,m)$ and $i \in [0,n)$.
    This implies in particular that for $\iota \in \{0,1,2\}, j \in [0,m), i \in [0,n)$ we have
    $$c_{j,i}x^{(\iota)} + d_{j,i} = b_{j,i}(1 - b_{j,i})x^{(\iota) 2} + (1 - 2b_{j,i})a_{j,i}x^{(\iota)} - a_{j,i}^2$$
    and hence $b_{j,i}(1 - b_{j,i}) = 0$, so each $b_{j,i} \in \{0,1\}$.

    We also have, by construction, that
    $$x^{(\iota)} = \sum_{i=0}^{n-1} f_{j,i}^{(\iota)} = x^{(\iota)} \sum_{i=0}^{n-1} b_{j,i} + \sum_{i=0}^{n-1} a_{j,i}$$
    for $\iota \in [0,m], j \in [0,m)$, so $\sum_{i=0}^{n-1} b_{j,i} = 1$.
    This means we can extract $l \in [0,N)$ such that each $b_{j,i} = \delta(l_j,i)$.

    Now if we define for each $k \in [0,N)$ the polynomial
    $$p_k(x) = \prod_{j=0}^{m-1} \left[ \delta(l_j,k_j)x + a_{j,k_j} \right]$$
    in $x$, we have $\deg(p_k) = m$ if and only if $k = l$.
    Verification can therefore be expressed as
    \begin{align*}
        x^{(\iota)m}(S_l - S') - \sum_{j=0}^{m-1} x^{(\iota)j} \overline{X}_j &= \comm(0,0,z_S^{(\iota)}) \\
        x^{(\iota)m}(V_l - V') - \sum_{j=0}^{m-1} x^{(\iota)j} \overline{X}'_j &= \com(0,0,z_V^{(\iota)})
    \end{align*}
    for $\iota \in [0,m]$, where the sets $\{\overline{X}_j\}_{j=0}^{m-1}$ and $\{\overline{X}'_j\}_{j=0}^{m-1}$ can be uniquely derived.
    Consider a Vandermonde matrix $V$ such that the $\iota$ row is the vector $(1, x^{(\iota)}, \ldots, x^{(\iota)m})$, and note since each challenge is distinct, we have $\det(V) \neq 0$ with high probability, so the rows of $V$ span $\F^{m+1}$.
    This means we can find $\{\theta_\iota\}_{\iota=0}^m$ such that the equation
    $$\sum_{\iota=0}^m \theta_\iota x^{(\iota)j} = \delta(j,m)$$
    holds for $j \in [0,m]$.

    We can therefore build a linear combination of each of the two above verification equations, taking advantage of the Vandermonde-derived weights:
    \begin{align*}
        S_l - S' &= \sum_{\iota=0}^m \theta_\iota x^{(\iota)m}(S_l - S') + \sum_{\iota=0}^m \theta_\iota \left(x^{(\iota)j}\overline{X}_j\right) = \comm\left(0, 0, \sum_{\iota=0}^m \theta_\iota z_S^{(\iota)}\right) \\
        V_l - V' &= \sum_{\iota=0}^m \theta_\iota x^{(\iota)m}(S_l - S') + \sum_{\iota=0}^m \theta_\iota \left(x^{(\iota)j}\overline{X}'_j\right) = \com\left(0, \sum_{\iota=0}^m \theta_\iota z_V^{(\iota)}\right)
    \end{align*}
    These equations provide the remaining extractions
    $$s = \sum_{\iota=0}^m \theta_\iota z_S^{(\iota)}$$
    and
    $$v = \sum_{\iota=0}^m \theta_\iota z_V^{(\iota)}$$
    such that $S_l - S' = \comm(0,0,s)$ and $V_l - V' = \com(0,v)$, which completes the proof.
\end{proof}

\section{Payment System Security}
\label{app:security}
 
Zerocash \cite{zerocash} established a robust security framework for decentralized anonymous payment (DAP) scheme security that captures a realistic threat model with powerful adversaries who are permitted to add malicious coins into transactions' input ambiguity sets, control the choice of transaction inputs, and produce arbitrary transactions to add to a ledger.
Here we formally prove Spark's security within a related (but modified) security model; proofs follow somewhat similarly to that of \cite{zerocash}.

The DAP construction is a tuple of algorithms
\begin{multline*}
(\func{Setup}, \func{CreateKeys}, \func{CreateAddress}, \func{CreateCoin}, \\
\func{Mint}, \func{Identify}, \func{Recover}, \func{Spend}, \func{Verify})
\end{multline*}
that is secure if it satisfies properties of completeness, balance, non-malleability, and ledger indistinguishability.

Each security property is formalized as a game between a polynomial-time adversary $\mathcal{A}$ and a challenger $\mathcal{C}$, where in each game the behavior of honest parties is simulated via an oracle $\oracle$.
The oracle $\oracle$ maintains a ledger $L$ of transactions and provides an interface for executing the $\func{CreateAddress}$, $\func{Mint}$, and $\func{Spend}$ algorithms.
To simulate behavior from honest parties, $\mathcal{A}$ passes a query to $\mathcal{C}$, which makes sanity checks and then proxies the queries to $\oracle$, returning the responses to $\mathcal{A}$ as needed.
For $\func{CreateAddress}$ queries, the oracle first runs the $\func{CreateKeys}$ protocol algorithm, then calls $\func{CreateAddress}$ using the resulting incoming view key and a randomly-selected diversifier index, and finally returns the public address $\addr_{\text{pk}}$.
For $\func{Mint}$ queries, the adversary specifies the value, memo, and destination public address for the transaction, and the resulting transaction is produced and returned if the inputs are semantically valid.
For $\func{Spend}$ queries, the adversary specifies the input coins to be consumed, as well as the values, memos, and destination public addresses for the transaction, and the resulting transaction is produced after coin recovery if the inputs are semantically valid, all consumed coins are validly controlled by an address produced by the oracle, and all consumed coins are unspent according to the ledger state.
The oracle $\oracle$ also provides an $\func{Insert}$ query that allows the adversary to insert arbitrary and potentially malicious $\text{tx}_{\text{mint}}$ or $\text{tx}_{\text{spend}}$ transactions into the ledger $L$, provided they are semantically valid and pass verification by the oracle.

For each security property, we say the DAP satisfies the property if the adversary can win the corresponding game with only negligible probability.

We now state a lemma that will be useful when examining the security of our construction.

\begin{lemma}\label{lem:extract}
    Given a ledger, two otherwise valid spend transactions reveal the same tag only if there exist coins with serial commitments $S_1,S_2$ produced in previous valid transactions and an extractor that produces representations of the following form:
    \begin{alignat*}{1}
        S_1 &= \comm(x,y,\beta_1) \\
        S_2 &= \comm(x,y,\beta_2)
    \end{alignat*}
\end{lemma}

\begin{proof}
    Let $T$ be the tag common to the two spend transactions.
    Each transaction has a valid modified Chaum-Pedersen proof.
    One transaction's valid proof yields statement values $T,S_1' \in \G$ and witness values $x_1,y_1,z_1 \in \F$ such that $U = x_1 T + y_1 G$ and $S_1' = x_1 F + y_1 G + z_1 H$.
    Similarly, the other transaction's valid proof yields statement values $T,S_2' \in \G$ and witness values $x_2,y_2,z_2 \in \F$ such that $U = x_2 T + y_2 G$ and $S_2' = x_2 F + y_2 G + z_2 H$.
    Since $U$ and $G$ are independent and Pedersen commitments are computationally binding, we must have (except with negligible probability) that $x_1 = x_2 = x$ and $y_1 = y_2 = y$.
    Hence $S_1' = xF + yG + z_1 H$ and $S_2' = xF + yG + z_2 H$.

    Each transaction further has a valid parallel one-of-many proof.
    From the first transaction's proof we have (by index extraction referencing an element of its input cover set) a group element $S_1 \in \G$ and scalar $\alpha_1 \in \F$ such that $S_1 - S_1' = \alpha_1 H$.
    For the second proof, we similarly have $S_2 \in \G$ and $\alpha_2 \in \F$ such that $S_2 - S_2' = \alpha_2 H$.

    This means in particular that $$S_1 = xF + yG + (z_1 + \alpha_1)H$$ and $$S_2 = xF + yG + (z_2 + \alpha_2)H$$ by combining these results.
    Since transaction validity requires all input cover set elements to exist as outputs of previous valid transactions, we have extracted representations of the desired form by setting $\beta_1 = z_1 + \alpha_1$ and $\beta_2 = z_2 + \alpha_2$.
\end{proof}
Observe that the result also holds for duplicate tags revealed in the same (otherwise valid) transaction, with almost identical reasoning.

\subsection{Completeness}

Completeness requires that no bounded adversary can prevent an honest user from spending a coin.
\footnote{We note that the security model does not capture the case where an adversary observes a valid transaction prior to its addition to the ledger and generates its own transaction producing a coin with the same serial commitment, possibly rendering the honest transaction invalid.
It is possible to mitigate this by allowing duplicate serial commitments on the ledger and requiring either coin identification to account for this by only accepting one such coin, or by binding unique data like linking tags or other additional context into serial commitments to be checked during coin identification.}
Specifically, this means that if the user is able to identify a coin using its incoming view key, then it can recover the coin using its full view key and generate a valid spend transaction consuming the coin using its spend key.

To see why this property holds, note that by construction, if an honest user is unable to produce a spend transaction for a coin with serial commitment $S$ that it has recovered, the corresponding tag $T$ must appear in a previous valid transaction.
The identified coin $S$ must be a commitment of the form $S = \comm(s,r,0)$ for serial number $s$ and spend key component $r$ according to the $\func{Identify}$ definition.
By Lemma \ref{lem:extract}, any previous transaction revealing $T$ must consume a coin with serial commitment $\overline{S} = \comm(s,r,z)$ for $z \neq 0$ (since coins must have unique serial commitments).
Since the user cannot have identified $\overline{S}$ because $z$ is nonzero, it did not generate the transaction consuming $\overline{S}$, a contradiction since that transaction implies knowledge of the spend key $r$ by extraction.


\subsection{Balance}

Balance requires that no bounded adversary $\mathcal{A}$ can control more coins than are minted or spent to it.
It is formalized by a $\func{BAL}$ game.
The adversary $\mathcal{A}$ adaptively interacts with $\mathcal{C}$ and the oracle with queries, and at the end of the interaction outputs a set of coins $\func{AdvCoins}$.
Letting $\func{ADDR}$ be set of all addresses of honest users generated by $\func{CreateAddress}$ queries, $\mathcal{A}$ wins the game if
$$v_{\text{unspent}} + v_{\mathcal{A} \to \func{ADDR}} > v_{\text{mint}} + v_{\func{ADDR} \to \mathcal{A}},$$
which implies that the total value the adversary can spend or has spent already is greater than the value it has minted or received.
Here:
\begin{itemize}
    \item $v_{\text{unspent}}$ is the total value of unspent coins in $\func{AdvCoins}$;
    \item $v_{\text{mint}}$ is the total value minted by $\mathcal{A}$ to itself through $\func{Mint}$ or $\func{Insert}$ queries;
    \item $v_{\func{ADDR} \xrightarrow{} \mathcal{A}}$ is the total value of coins received by $\mathcal{A}$ from addresses in $\func{ADDR}$; and
    \item $v_{\mathcal{A} \xrightarrow{} \func{ADDR}}$ is the total value of coins sent by the adversary to the addresses in $\func{ADDR}$.
\end{itemize}
We say a DAP scheme $\Pi$ is $\func{BAL}$-secure if the adversary $\mathcal{A}$ wins the game $\func{BAL}$ only with negligible probability:
$$\text{Pr}[\func{BAL}(\Pi, \mathcal{A}, \lambda) = 1] \leq \text{negl}(\lambda)$$

Assume the challenger maintains an extra augmented ledger $(L, \vec{a})$ where each $a_i$ contains secret data from transaction $\text{tx}_i$ in $L$.
In that case where $\text{tx}_i$ was produced by a query from $\mathcal{A}$ to the challenger $\mathcal{C}$, $a_i$ contains all secret data used by $\mathcal{C}$ to produce the transaction.
If instead $\text{tx}_i$ was produced by a direct $\func{Insert}$ query from $\mathcal{A}$, $a_i$ consists of all extracted witness data from proofs contained in the transaction.
The resulting augmented ledger $(L, \vec{a})$ is balanced if the following conditions are true:
\begin{enumerate}
    \item\label{cond:distinct} Each valid spend transaction $\text{tx}_{\text{spend},k}$ in $(L, \vec{a})$ consumes distinct coins, and each consumed coin is the output of a valid $\text{tx}_{\text{mint},i}$ or $\text{tx}_{\text{spend},j}$ transaction for some $i < k$ or $j < k$.
    This requirement implies that all transactions spend only valid coins, and that no coin is spent more than once within the same valid transaction.
    
    \item\label{cond:multiple} No two valid spend transactions in $(L, \vec{a})$ consume the same coin.
    This implies no coin is spent through two different transactions.
    Together with the first requirement, this implies that each coin is spent at most once.
    
    \item\label{cond:value} For each $(\text{tx}_{\text{spend}}, a)$ in $(L, \vec{a})$ consuming input coins with value commitments $\{C_u\}_{u=0}^{w-1}$, for each $u \in [0,w)$:
    \begin{itemize}
        \item If $C_u$ is the output of a valid mint transaction with augmented ledger witness $a'$, then the value of $C_u$ contained in $a'$ is the same as the corresponding value contained in $a$ for the value commitment offset $C_u'$.
        \item If $C_u$ is the output of a valid spend transaction with augmented ledger witness $a'$, then the value of $C_u$ contained in $a'$ is the same as the corresponding value contained in $a$ for the value commitment offset $C_u'$.
    \end{itemize}
    This implies that values are maintained between transactions.
    
    \item\label{cond:balance} For each $(\text{tx}_{\text{spend}}, a)$ in $(L, \vec{a})$ with fee $f$ that consumes input coins with value commitment offsets $\{C_u'\}_{u=0}^{w-1}$ and generates coins with value commitments $\{\overline{C}_j\}_{j=0}^{t-1}$, $a$ contains values $\{v_u\}_{u=0}^{w-1}$ and $\{\overline{v}_j\}_{j=0}^{t-1}$ corresponding to the commitments such that the balance equation
    $$\sum_{u=0}^{w-1} v_u = \sum_{j=0}^{t-1} \overline{v}_j + f$$
    holds.
    For each $(\text{tx}_{\text{mint}}, a)$ in $(L, \vec{a})$ generating coins with value commitments $\{\overline{C}_j\}_{j=0}^{t-1}$ and public values $\{\overline{v}_j\}_{j=0}^{t-1}$, $a$ contains values $\{\overline{v}'_j\}_{j=0}^{t-1}$ corresponding to the commitments such that $\overline{v}_j = \overline{v}'_j$ for all $j \in [0,t)$.
    This implies that values cannot be created arbitrarily.
    
    \item\label{cond:honest} For each $\text{tx}_{\text{spend}}$ in $(L, \vec{a})$ inserted by $\mathcal{A}$ through an $\func{Insert}$ query, each consumed coin in $\text{tx}_{\text{spend}}$ is not recoverable by any address in $\func{ADDR}$.
    This implies that the adversary cannot generate a transaction consuming coins it does not control.
\end{enumerate}
If these five conditions hold, then $\mathcal{A}$ did not spend or control more money than was previously minted or spent to it, and the inequality
$$v_{\text{mint}} + v_{\func{ADDR} \to \mathcal{A}} \leq v_{\text{unspent}} + v_{\mathcal{A} \to \func{ADDR}}$$
holds.
We now prove that Spark is $\func{BAL}$-secure under this definition.

\begin{proof}
By way of contradiction, assume the adversary $\mathcal{A}$ interacts with $\mathcal{C}$ leading to a non-balanced augmented ledger $(L, \vec{a})$ with non-negligible probability; then at least one of the five conditions described above is violated with non-negligible probability:

\textbf{$\mathcal{A}$ violates Condition \ref{cond:distinct}:} Suppose that the probability $\mathcal{A}$ wins the game violating Condition 1 is non-negligible.
Each $\text{tx}_{\text{spend}}$ generated by a non-$\func{Insert}$ oracle query satisfies this condition already, so there must exist a transaction $(\text{tx}_{\text{spend}}, a)$ in $(L, \vec{a})$ inserted by $\mathcal{A}$.

Suppose there exist inputs $u_1,u_2 \in [0,w)$ of $\text{tx}_{\text{spend}}$ that consume the same coin with serial commitment $S$.
Validity of the modified Chaum-Pedersen proof $\Pi_{\text{chaum}}$ gives extracted openings $S_{u_1}' = s_{u_1} F + r_{u_1} G + y_{u_1} H$ and $S_{u_2}' = s_{u_2} F + r_{u_2} G + y_{u_2} H$ and tag representations such that $U = s_{u_1} T_{u_1} + r_{u_1} G$ and $U = s_{u_2} T_{u_2} + r_{u_2} G$.
Because transaction validity implies $T_{u_1} \neq T_{u_2}$, we must have $(s_{u_1},r_{u_1}) \neq (s_{u_2},r_{u_2})$.
Validity of the corresponding parallel one-out-of-many proofs $(\Pi_{\text{par}})_{u_1}$ and $(\Pi_{\text{par}})_{u_2}$ yields indices (corresponding to the same input set group element $S$) and discrete logarithm extractions such that $S - S_{u_1}' = x_{u_1} H$ and $S - S_{u_2}' = x_{u_2} H$.
This means
$$S = \comm(s_{u_1},r_{u_1},x_{u_1}+y_{u_1}) = \comm(s_{u_2},r_{u_2},x_{u_2}+y_{u_2}),$$
a contradiction since the commitment scheme is computationally binding.

The second possibility for violation of the condition is that the transaction $\text{tx}_{\text{spend}}$ consumes a coin that is not generated in any previous valid transaction.
This follows immediately using similar reasoning as above, since transaction validity asserts knowledge of an opening to a commitment contained in the input set, all of which must have been previously generated in valid transactions by definition.

\textbf{$\mathcal{A}$ violates Condition \ref{cond:multiple}:} Suppose that the probability $\mathcal{A}$ wins the game violating Condition \ref{cond:multiple} is non-negligible.
This means the augmented ledger $(L, \vec{a})$ contains two valid spend transactions consuming the same coin but producing distinct tags.
Similarly to the previous argument, this implies distinct openings of the coin serial number commitment, which is a contradiction.

\textbf{$\mathcal{A}$ violates Condition \ref{cond:value}:} Suppose that the probability $\mathcal{A}$ wins the game violating Condition \ref{cond:value} is non-negligible.
Let $C$ be the value commitment of the coin consumed by an input of $\text{tx}_{\text{spend}}$ and generated in a previous transaction (of either type) in $(L, \vec{a})$.
Since the generating transaction is valid, we have an extracted opening $C = vG + aH$ from either the value proof (in a mint transasction) or the range proof (in a spend transaction).
Validity of the corresponding parallel one-out-of-many proof in $\text{tx}_{\text{spend}}$ gives an extracted discrete logarithm $C - C' = xH$, where $C'$ is the input's value commitment offset.
But this immediately gives $C' = vG + (a - x)H$, a contradiction since the commitment scheme is binding.

\textbf{$\mathcal{A}$ violates Condition \ref{cond:balance}:} Suppose that the probability $\mathcal{A}$ wins the game violating Condition \ref{cond:balance} is non-negligible.
If the augmented ledger $(L, \vec{a})$ contains a spend transaction that violates the balance equation, this immediately implies a break in the commitment binding property since the corresponding balance proof $\Pi_{\text{bal}}$ is valid, which is a contradiction.
If instead the augmented ledger $(L, \vec{a})$ contains a mint transaction that violates the balance requirement, this immediately implies a break in the commitment binding property since the corresponding value proof $\Pi_{\text{val}}$ is valid, again a contradiction.

\textbf{$\mathcal{A}$ violates Condition \ref{cond:honest}:} Suppose that the probability $\mathcal{A}$ wins the game violating Condition \ref{cond:honest} is non-negligible.
That is, $\mathcal{A}$ produces a spend transaction $\text{tx}_{\text{spend}}$ by an $\func{Insert}$ question that is valid on the augmented ledger $(L, \vec{a})$ and consumes a coin corresponding to a coin serial number commitment $S$ that can be recovered by a public address $(d, Q_1, Q_2) \in \func{ADDR}$.

Validity of the Chaum-Pedersen proof corresponding to $\text{tx}_{\text{spend}}$ yields an extracted representation $S' = s'F + r'G + yH$.
Validity of the corresponding parallel one-of-many proof gives a serial number commitment $S$ and extraction such that $S - S' = xH$, so $S = s'F + r'G + (x + y)H$.

Now let $(s_1,s_2,r)$ be the spend key corresponding to the address $(d,Q_1,Q_2)$.
Since $\text{tx}_{\text{spend}}$ consumes a coin recoverable by this address, a serial number commitment for the recovered coin is
\begin{align*}
\overline{S} &= \hash_{\text{ser}}(k)F + Q_2 \\
&= (\hash_{\text{ser}}(k) + \hash_{Q_2}(s_1,i) + s_2)F + rG
\end{align*}
for nonce $k$ and some diversifier index $i$.

Since the commitment scheme is binding, we must therefore have $r' = r$, which is a contradiction since $\mathcal{A}$ cannot extract this discrete logarithm from the public address.

This completes the proof.
\end{proof}


\subsection{Transaction Non-Malleability}

This property requires that no bounded adversary can substantively alter a valid transaction. 
In particular, non-malleability prevents malicious adversaries from modifying honest users' transactions by altering data or redirecting the outputs of a valid transaction before the transaction is added to the ledger.
Since non-malleability of mint transactions is offloaded to authorizations relating to consensus rules or base-layer operations, we need only consider the case of spend transactions.

This property is formalized by an experiment $\func{TRNM}$, in which a bounded adversary $\mathcal{A}$ adaptively interacts with the oracle $\oracle$, and then outputs a spend transaction $\text{tx}'$.
If we let $T$ denote the set of all transactions produced by $\func{Spend}$ queries to $\oracle$, and $L$ denote the final ledger, $\mathcal{A}$ wins the game if there exists $\text{tx} \in T$ such that:
\begin{itemize}
    \item $\text{tx}' \neq \text{tx}$; 
    \item $\text{tx}'$ reveals a tag also revealed by $\text{tx}$; and
    \item both $\text{tx}'$ and $\text{tx}$ are valid transactions with respect to the ledger $L^{\prime}$ containing all transactions preceding $\text{tx}$ on $L$.
\end{itemize}

We say a DAP scheme $\Pi$ is $\func{TRNM}$-secure if the adversary $\mathcal{A}$ wins the game $\func{TRNM}$ only with negligible probability:
$$\text{Pr}[\func{TRNM}(\Pi, \mathcal{A}, \lambda) = 1] \leq \text{negl}(\lambda)$$

Let $\mathcal{T}$ be the set of all $\text{tx}_{\text{spend}}$ transactions generated by the $\oracle$ in response to $\func{Spend}$ queries.
Since these transactions are generated by these oracle queries, $\mathcal{A}$ does not learn any secret data used to produce these transactions.

\begin{proof}
Assume that the adversary $\mathcal{A}$ wins the game with non-negligible probability.
That is, $\mathcal{A}$ produces a transaction $\text{tx}'$ revealing a tag $T$ also revealed in a transaction $\text{tx}$.
Without loss of generality, assume each transaction consumes a single coin.

Observe that a valid spend binds all transaction elements except for the modified Chaum-Pedersen proof into each such proof via $\hash_{\text{bind}}$ and the proof transcripts.
Therefore, in order to produce valid $\text{tx}' \neq \text{tx}$, we consider two cases:
\begin{itemize}
    \item the modified Chaum-Pedersen proofs are identical, but $\text{tx}'$ and $\text{tx}$ differ in another element of the transaction structures; or
    \item the modified Chaum-Pedersen proof in $\text{tx}'$ is distinct from the proof in $\text{tx}$.
\end{itemize}

In the first case, at least one input to the binding hash $\hash_{\text{bind}}$ used to initialize the modified Chaum-Pedersen transcripts must differ between the proofs.
Because we model this hash function as a random oracle, the outputs differ except with negligible probability, a contradiction since the resulting proof structures must be identical.

In the second case, because the tag revealed in both $\text{tx'}$ and $\text{tx}$ is identical, Lemma \ref{lem:extract} gives extractions of the form $(s,r,y)$ and $(s,r,0)$ respectively.
Further, the coin $S = \comm(s,r,0)$ consumed in $\text{tx}$ was generated such that $r$ is a spend key component for an address $(d,Q_1,Q_2)$ not controlled by $\mathcal{A}$.
Since $\mathcal{A}$ does not control this address, it cannot produce $r$ without extracting from $S$ or from any set of corresponding diversified address components $\{Q_{2,i}\}_i$ produced from the same spend key.
However, each $Q_{2,i}$ is produced linearly against $Q_2$ and querying $\hash_{Q_2}$ with unique $(s_1,i)$ input, a contradiction.
\end{proof}


\subsection{Ledger Indistinguishability}

This property implies that no bounded adversary $\mathcal{A}$ received any information from the ledger except what is already publicly revealed, even if it can influence valid ledger operations by honest users.

Ledger indistinguishability is formalized through an experiment $\func{LIND}$ between a bounded adversary $\mathcal{A}$ and a challenger $\mathcal{C}$, which terminates with a binary output $b^{\prime}$ by $\mathcal{A}$.
At the beginning of the experiment, $\mathcal{C}$ samples $\func{Setup}(1^\lambda) \to pp$ and sends the parameters to $\mathcal{A}$; next it samples a random bit $b \in \lbrace 0,1 \rbrace$ and initializes two separate DAP oracles $\oracle_0$ and $\oracle_1$, each with its own separate ledger and internal state.
At each consecutive step of the experiment:
\begin{enumerate}
\item $\mathcal{C}$ provides $\mathcal{A}$ two ledgers $(L_{\text{left}} = L_b, L_{\text{right}} = L_{1-b})$ where $L_b$ and $L_{1-b}$ are the current ledgers of the oracles $\oracle_b$ and $\oracle_{1-b}$ respectively. 
\item $\mathcal{A}$ sends to $\mathcal{C}$ two queries $Q, Q^{\prime}$ of the same type (one of $\func{CreateAddress}$, $\func{Mint}$, $\func{Spend}$, or $\func{Insert}$). 
\begin{itemize}
    \item If the query type is $\func{Insert}$ or $\func{Mint}$, $\mathcal{C}$ forwards $Q$ to $L_{b}$ and $Q^\prime$ to $L_{1-b}$, permitting $\mathcal{A}$ to insert its own transactions or mint new coins to $L_{\text{left}}$ and $L_{\text{right}}$.
    \item For all queries of type $\func{CreateAddress}$ or $\func{Spend}$, $\mathcal{C}$ first checks if the two queries $Q$ and $Q^\prime$ are publicly consistent, and then forwards $Q$ to $\oracle_0$ and $Q^\prime$ to $\oracle_1$.
    It receives the two oracle answers $(a_0,a_1)$, but returns $(a_b,a_{1-b})$ to $\mathcal{A}$.
\end{itemize}
\end{enumerate}
As the adversary does not know the bit $b$ and the mapping between $(L_{\text{left}}, L_{\text{right}})$ and $(L_0, L_1)$, it cannot learn whether it affects the behavior of honest parties on $(L_0, L_1)$ or on $(L_1, L_0)$.
At the end of the experiment, $\mathcal{A}$ sends $\mathcal{C}$ a bit $b^\prime \in \lbrace 0,1 \rbrace$.
The challenger outputs 1 if $b = b^\prime$, and 0 otherwise.

We require the queries $Q$ and $Q^\prime$ be publicly consistent as follows
If the query type of $Q$ and $Q^\prime$ is $\func{CreateAddress}$, both oracles generate the same address.
If the query type of $Q$ and $Q^\prime$ is $\func{Mint}$, then the number of generated coins and the public value of each coin must be equal in both queries.
If the query type of $Q$ and $Q^\prime$ is $\func{Spend}$, then:
\begin{itemize}
    \item Both $Q$ and $Q^\prime$ must be well-formed and valid, so the referenced input coins must have been generated in a previous transaction on the ledger and be unspent.
    Further, the transaction must balance.
    \item The number of spent coins and output coins must be the same in $Q$ and $Q^\prime$.
    \item If a consumed coin in $Q$ references a coin in $L_0$ posted by $\mathcal{A}$ through an $\func{Insert}$ query, then the corresponding index in $Q^\prime$ must also reference a coin in $L_1$ posted by $\mathcal{A}$ through an $\func{Insert}$ query and the values of these two coins must be equal as well (and vice versa for $Q^\prime$). 
    \item If an output coin referenced by $Q$ does not reference a recipient address in the oracle $\func{ADDR}$ list (and therefore is controlled by $\mathcal{A}$), then the corresponding value must equal that of the corresponding coin referenced by $Q$ at the same index (and vice versa for $Q^\prime$).
\end{itemize}

We say a DAP scheme $\Pi$ is $\func{LIND}$-secure if $\mathcal{A}$ wins the game $\func{LIND}$ only probability at most negligibly better than chance:
$$\text{Pr}[\func{LIND}(\Pi, \mathcal{A}, \lambda) = 1] - \frac{1}{2} \leq \text{negl}(\lambda)$$

\begin{proof}
In order to prove that $\mathcal{A}$'s advantage in the $\func{LIND}$ experiment is negligible, we first consider a simulation experiment $\mathcal{D}^{\text{sim}}$, in which $\mathcal{A}$ interacts with $\mathcal{C}$ as in the $\func{LIND}$ experiment, but with modifications.

\textbf{The simulation experiment $\mathcal{D}^{\text{sim}}$}: Since the parallel one-out-of-many, modified Chaum-Pedersen, representation, and range proving systems are all special honest-verifier zero knowledge, we can take advantage of the simulator for each.
Given input statements and verifier challenges, each proving system's simulator produces transcripts indistinguishable from honest proofs.
Additionally, we now define the behavior of the full simulator.

\textbf{The simulation.} The simulation $\mathcal{D}^{\text{sim}}$ works as follows.
As in the original experiment, $\mathcal{C}$ samples the system parameters $\func{Setup}(1^\lambda) \to pp$ and a random bit $b$, and initializes DAP oracles $\oracle_0$ and $\oracle_1$.
Then $\mathcal{D}^{\text{sim}}$ proceeds in steps.
At each step, it provides $\mathcal{A}$ with ledgers $L_{\text{\text{left}}} = L_{b}$ and $L_{\text{\text{right}}} = L_{1-b}$, after which $\mathcal{A}$ sends two publicly-consistent queries $(Q, Q^\prime)$ of the same type.
Recall that the queries $Q$ and $Q^\prime$ are consistent with respect to public data and information related to the addresses controlled by $\mathcal{A}$.
Depending on the query type, the challenger acts as follows:
\begin{itemize}
    \item Answering $\func{Insert}$ queries: The challenger proceeds as in the original $\func{LIND}$ experiment.
    \item Answering $\func{CreateAddress}$ queries: In this case the challenger replaces the public address components $(d,Q_1,Q_2)$ with random strings of the appropriate lengths, producing $\addr_{\text{pk}}$ that is returned to $\mathcal{A}$.
    \item Answering $\func{Mint}$ queries: The challenger does the following to answer $Q$ and $Q^\prime$ separately, where $t$ is the number of generated coins specified by $\mathcal{A}$ as part of its queries:
    \begin{enumerate}
        \item For each $j \in [0,t)]$:
        \begin{enumerate}
            \item If $\mathcal{A}$ provided a public address $\addr_{\text{pk}}$ not generated by the challenger, it produces a coin using $\func{CreateCoin}$ as usual.
            \item Otherwise, it simulates coin generation:
            \begin{enumerate}
                \item Samples a recovery key $K_j$ uniformly at random.
                \item Samples a serial number commitment $S_j$ uniformly at random.
                \item Samples a value commitment $\overline{C}_j$ uniformly at random.
                \item Samples a random input used to produce an AEAD encryption key $\func{AEADKeyGen} \to k_{\text{enc}}$.
                \item Simulates the recipient data encryption by selecting random $r$ of the proper length, and encrypting it to produce $$\func{AEADEncrypt}(k_{\text{enc}},\texttt{r},r) \to \overline{r}.$$
            \end{enumerate}
        \end{enumerate}
        \item Simulates the value proof $\Pi_{\text{val}}$ on the statement $\{ \overline{C}_j - \com(v_j,0)\}_{j=0}^{t-1}$.
        \item Assembles the transaction and adds it to the ledger as appropriate.
    \end{enumerate}
    \item Answering $\func{Spend}$ queries: The challenger does the following to answer $Q$ and $Q^\prime$ separately, where $w$ is the number of consumed coins and $t$ the number of generated coins specified by $\mathcal{A}$ as part of its queries:
    \begin{enumerate}
        \item For each $u \in [0,w)$, where $l_u$ represents the index of the consumed coin in $\func{InCoins}_u$:
        \begin{enumerate}
            \item Parses the input cover set serial number commitments and value commitments as $\func{InCoins}_u = \{(S_{i,u}, C_{i,u})\}_{i=0}^{N-1}$.
            \item Samples a tag $T_u$ uniformly at random.
            \item Samples a serial number commitment offset $S_u'$ and value commitment offset $C_u'$ uniformly at random.
            \item Simulates a parallel one-out-of-many proof $(\Pi_{\text{par}})_u$ on the statement $(\{S_{i,u}, C_{i,u}\}_{i=0}^{N-1},S_u',C_u')$.
        \end{enumerate}
        \item For each $j \in [0,t)$:
        \begin{enumerate}
            \item If $\mathcal{A}$ provided a public address $\addr_{\text{pk}}$ not generated by the challenger, it produces a coin using $\func{CreateCoin}$ as usual.
            \item Otherwise, it simulates coin generation:
            \begin{enumerate}
                \item Samples a recovery key $K_j$ uniformly at random.
                \item Samples a serial number commitment $S_j$ uniformly at random.
                \item Samples a value commitment $\overline{C}_j$ uniformly at random.
                \item Samples a random input used to produce an AEAD encryption key $\func{AEADKeyGen} \to k_{\text{enc}}$.
                \item Simulates the recipient data encryption by selecting random $r$ of the proper length, and encrypting it to produce $$\func{AEADEncrypt}(k_{\text{enc}},\texttt{r},r) \to \overline{r}.$$
                \item Simulates a range proof $(\Pi_{\text{rp}})_j$ on the statement $(\overline{C}_j)$.
            \end{enumerate}
        \end{enumerate}
        \item Simulates the balance proof $\Pi_{\text{bal}}$ on the statement $$\left(\sum_{u=0}^{w-1} C_u' - \sum_{j=0}^{t-1} \overline{C}_j - \com(f,0)\right).$$
        \item For each $u \in [0,w)$, computes the binding hash $\mu$ as defined and simulates the modified Chaum-Pedersen proof $\Pi_{\text{chaum}}$ on the statement $(\{S_u', T_u\}_{u=0}^{w-1})$.
        \item Assembles the transaction and adds it to the ledger as appropriate.
    \end{enumerate}
\end{itemize}

For experiments defined below, we define $\func{Adv}^{\mathcal{D}}$ as the advantage of $\mathcal{A}$ in some experiment $\mathcal{D}$ over the original $\func{LIND}$ game.
By definition, all answers sent to $\mathcal{A}$ in $\mathcal{D}^{\text{sim}}$ are computed independently of the bit $b$, so $\func{Adv}^{\mathcal{D}^{\text{sim}}} = 0$. We will prove that $\mathcal{A}$'s advantage in the real experiment $\mathcal{D}^{\text{real}}$ is at most negligibly different than $\mathcal{A}$'s advantage in $\mathcal{D}^{\text{sim}}$.
To show this, we construct intermediate experiments in which $\mathcal{C}$ performs a specific modification of $\mathcal{D}^{\text{real}}$ against $\mathcal{A}$.

\textbf{Experiment $\mathcal{D}_1$}: This experiment modifies $\mathcal{D}^{\text{real}}$ by simulating all one-out-of-many proofs, range proofs, representation proofs, and modified Chaum-Pedersen proof.
As all these protocols are special honest-verifier zero knowledge, the simulated proofs are indistinguishable from the real proofs generated in $\mathcal{D}^{\text{real}}$.
Hence $\func{Adv}^{\mathcal{D}_1} = 0$.

\textbf{Experiment $\mathcal{D}_2$}: This experiment modifies $\mathcal{D}_{1}$ by replacing all encrypted recipient data in transactions with challenger-generated recipient public addresses with encryptions of random values of appropriate lengths under keys chosen uniformly at random, and by replacing recovery keys with uniformly random values.
Since the underlying authenticated symmetric encryption scheme is IND-CCA and IK-CCA secure and we assume the decisional Diffie-Hellman problem is hard, the adversarial advantage in distinguishing ledger output in the $\mathcal{D}_2$ experiment is negligibly different from its advantage in the $\mathcal{D}_{1}$ experiment.
Hence $\lvert \func{Adv}^{\mathcal{D}_2} - \func{Adv}^{\mathcal{D}_1} \rvert$ is negligible.

\textbf{Experiment $\mathcal{D}^{\text{sim}}$}: The $\mathcal{D}^{\text{sim}}$ experiment is formally defined above.
In particular, it differs from $\mathcal{D}_{2}$ by replacing consumed coin tags, serial number commitment offset, and value commitment offsets with uniformly random values; and by replacing output coin serial number and value commitments with random values.
In previous experiments (including $\mathcal{D}^{\text{real}}$), tags are generated using a pseudorandom function \cite{dodis}, and the other given values are generated as commitments with masks derived from hash functions modeled as independent random oracles, so the adversarial advantage in distinguishing ledger output in $\mathcal{D}^{\text{sim}}$ is negligibly different from its advantage in the $\mathcal{D}_2$ experiment.
Hence $\lvert \func{Adv}^{\mathcal{D}^{\text{sim}}} - \func{Adv}^{\mathcal{D}_2} \rvert$ is negligible.

This shows that the adversary has only negligible advantage in the real $\func{LIND}$ game over the simulation, where it can do no better than chance, which completes the proof.
\end{proof}


\section{Payment Proofs}
\label{app:payment}

We describe now the informal security properties required for a payment proving system, describe such a construction, and (informally) prove that our construction meets the requirements.

The security requirements of a payment proving system are as follows:
\begin{enumerate}
    \item\label{pay:context} The proof cannot be replayed in a different context.
    \item\label{pay:secret} The prover asserts that it knows secret data sufficient to authorize the transaction originally generating a specified coin.
    \item\label{pay:value_memo} The verifier can obtain and confirm the value and memo associated to the coin.
    \item\label{pay:identify} The holder of an incoming view key corresponding to a specified public address can successfully identify the coin.
    \item\label{pay:malicious} A computationally-bound adversary cannot produce valid proofs for the same coin claiming distinct public addresses.
\end{enumerate}

We note that coin identification relies on the assumption that the claimed recipient address was generated using the protocol-specified method from an incoming view key.


\subsection{Protocol}

A prover wishes to produce a payment proof on a given coin $\func{Coin}$ with nonce $k$ to a claimed destination public address $(d,Q_1,Q_2)$.
Suppose that $\text{tx}$ is the spend transaction on a ledger that produced $\func{Coin}$.
The prover does the following:
\begin{enumerate}
    \item Parses the serial number commitment, value commitment, and recovery key from $\func{Coin}$: $(S,C,K)$
    \item Generates a modified Chaum-Pedersen proof $\Pi_{\text{auth}}$ using the same inputs and proving system as the proof $\Pi_{\text{chaum}}$ from $\text{tx}$, but also binding the tuple $(\func{Coin},k,d,Q_1,Q_2)$, any context relevant to the payment proof instance, and a globally-fixed payment proof domain separator to the proof context.
    \item Assembles the payment proof: $\Pi_{\text{pay}} = (\func{Coin},k,d,Q_1,Q_2,\Pi_{\text{auth}})$
\end{enumerate}

To verify a payment proof on a coin, the verifier does the following:
\begin{enumerate}
    \item Parses the payment proof: $\Pi_{\text{pay}} = (\func{Coin},k,d,Q_1,Q_2,\Pi_{\text{auth}})$
    \item Parses public data from $\func{Coin}$: $(S,C,K,\overline{r})$
    \item Verifies that $\text{tx}$ is a valid transacton on its own ledger that originally generated $\func{Coin}$.
    \item Verifies the proof $\Pi_{\text{auth}}$ using the data from $\text{tx}$ and the additional binding tuple $(\func{Coin},k,d,Q_1,Q_2)$, and aborts if verification fails.
    \item Generates an AEAD key $k_{\text{aead}} = \func{AEADKeyGen}(\hash_k(k) Q_1)$ and decrypts the recipient data: $$(v, d', k', m) = \func{AEADDecrypt}(k_{\text{aead}},\texttt{r},\overline{r})$$
    If decryption fails, or if $k' \neq k$, or if $d' \neq d$, aborts.
    \item Checks that $K = \hash_k(k)\hash_{\text{div}}(d)$, and aborts otherwise.
    \item Checks that $S = \comm(\hash_{\text{ser}}(k),0,0) + Q_2$, and aborts otherwise.
    \item Checks that $C = \com(v, \hash_{\text{val}}(k))$, and aborts otherwise.
\end{enumerate}


\subsection{Security}

We now describe why this construction meets our security requirements.

\textbf{Requirement \ref{pay:context}}. To show that a payment proof cannot be replayed in another context, note that since proof context is bound to the transcript of $\Pi_{\text{auth}}$ along with the statement and coin data, the overall payment proof $\Pi_{\text{pay}}$ cannot be successfully replayed against any other context.

\textbf{Requirement \ref{pay:secret}}. To show that successful verification of a payment proof asserts the prover knows secret data sufficient to authorize the transaction that generated the coin, we simply note that the modified Chaum-Pedersen proof $\Pi_{\text{chaum}}$ from $\text{tx}$ uses the same statement input as $\Pi_{\text{auth}}$ (albeit with different proof context).

\textbf{Requirement \ref{pay:value_memo}}. To show that the verifier can obtain the correct value and memo for the coin on successful verification of a payment proof, we simply note that successful AEAD decryption provides the unique values for the value and memo originally used to produce the coin, and that the decrypted value uniquely corresponds to the coin's value commitment since the commitment scheme is binding and successful verification implies an opening to this commitment.

\textbf{Requirement \ref{pay:identify}}. We now show that if the given address $(d,Q_1,Q_2)$ was generated from an incoming view key $(s_1,P_2)$, this key can identify $\textsf{Coin}$ if a payment proof verifies.
Successful verification of a payment proof implies in particular that $K = \hash_k(k)\hash_{\text{div}}(d)$ and that AEAD decryption succeeds on a key generated using $\hash_k(k) Q_1$.
This implies that the incoming view holder uses the AEAD key
\begin{align*}
    s_1 K &= s_1 \hash_k(k)\hash_{\text{div}}(d) \\
    &= \hash_k(k) Q_1
\end{align*}
and hence decryption succeeds.
The remaining steps for identification follow from corresponding steps taken during payment proof verification.

\textbf{Requirement \ref{pay:malicious}}. We now show that a computationally-bound adversary cannot produce valid proofs against the same coin for distinct destination addresses.
Suppose such an adversary produces for the same coin valid payment proofs
$$\Pi_{\text{pay}} = (\mathsf{Coin},k,d,Q_1,Q_2,\Pi_{\text{auth}})$$
and
$$\Pi_{\text{pay}}' = (\mathsf{Coin},k',d',Q_1',Q_2',\Pi_{\text{auth}}')$$
on addresses $(d,Q_1,Q_2) \neq (d',Q_1',Q_2')$.
Note that $\mathsf{Coin} = (S,C,K,\overline{r})$ must be identical in both proofs by definition.

Successful AEAD decryption of $\overline{r}$ on both proofs implies in particular that $d = d'$ and $k = k'$ except with negligible probability.
Further, the AEAD keys derived in both proofs must be equal (again except with negligible probability), so $\hash_k(k) Q_1 = \hash_k(k') Q_1'$ requires $Q_1 = Q_1'$.
Finally, since
\begin{alignat*}{1}
    S &= \comm(\hash_{\text{ser}}(k),0,0) + Q_2 \\    
    &= \comm(\hash_{\text{ser}}(k'),0,0) + Q_2'
\end{alignat*}
it also follows that $Q_2 = Q_2'$, a contradiction.


\end{document}