seraphis.tex

\documentclass{article}
\usepackage[top=1.0in,bottom=1.0in,left=1.0in,right=1.0in]{geometry}
\usepackage{amsmath,amssymb,amsthm,amsfonts}
\usepackage[utf8]{inputenc}
\usepackage{hyperref}

\theoremstyle{plain}
\newtheorem{definition}{Definition}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}{Corollary}[theorem]
\newtheorem{lemma}[theorem]{Lemma}

\theoremstyle{remark}
\newtheorem*{remark}{Remark}

\title{A Report on Seraphis}
\author{coinstudent2048}
\date{\today}

\begin{document}

\maketitle

\begin{abstract}
This document contains a concise description of koe's Seraphis \cite{seraphis}, a novel privacy-preserving transaction protocol abstraction, and its security model. Note that this does not cover all of it, but a rather simple variant of it for easier security analysis. Because of this, extensions/modifications presented there, with some mentioned here, would not be analyzed here.
\end{abstract}

%\section{Introduction}
%[UNFINISHED]

\section{Preliminaries}
\subsection{Public parameters}
Let $\lambda$ be the security parameter. Let $\mathbb{G}$ be a prime order group based on $\lambda$ where the Discrete Logarithm (DL) and Decisional Diffie-Hellman (DDH) problems are hard, and let $\mathbb{F}$ be its scalar field. Let $H_0, H_1, G_0, G_1, G_2, J$ be generators of $\mathbb{G}$ with unknown DL relationship to each other (see Definition \ref{dl-rel} for the formalization); these may be produced through public randomness. Let $a_{max}, d_{1,max}\in\mathbb{F}$ (to be used in range proofs and account balance respectively) with $d_{1,max} \le a_{max}$, and $s\in\mathbb{N}$ (to be used in membership proofs). Let $\mathcal{H}:\{0,1\}^*\rightarrow\mathbb{F}$ be a cryptographic hash function. We assume that $\mathcal{H}$ is a random oracle, hence we work in the random oracle model. We add a subscript to $\mathcal{H}$, such as $\mathcal{H}_0$, in lieu of domain-separating the hash function explicitly; any domain-separation method may be used in practice. All these public parameters are collected as $pp$, and we now define the setup algorithm: $pp\leftarrow\textsf{Setup}(1^{\lambda})$. $\textsf{Setup}$ is implicitly executed by all players involved in the beginning, hence it can be omitted in protocol descriptions.

The notation $\xleftarrow{\$}$ will be used to denote for a uniformly randomly chosen element, and $(1/x)$ for the modular inverse of $x\in\mathbb{F}$. Lastly, we use additive notation for group operations.

\subsection{E-notes and e-note images}
\begin{definition}\label{e-note}
An \textbf{\em e-note} for scalars $k_1^o, k_2^o, a \in\mathbb{F}$ is a tuple $(C, K^o, m)$ such that $C = x H_0 + a H_1$ for $x\xleftarrow{\$}\mathbb{F}$, $K^o = k_0^o G_0 + k_1^o G_1 + k_2^o G_2$, and $m$ is arbitrary data.
\end{definition}
$C$ is called the \textbf{amount commitment} for the amount $a$ with blinding factor $x$, $K^o$ is called the \textbf{one-time address} for (one-time) private keys $k_0^o$, $k_1^o$, $k_2^o$ (the $o$ superscript indicates ``one-time"), and $m$ is the \textbf{memo field} which includes information helping wallet owners to know if they own the e-note. We say that someone \textit{owns} an e-note if they know the corresponding scalars $k_0^o, k_1^o, k_2^o, a, x \in\mathbb{F}$. Basically, e-notes are \textit{exactly} what the (hidden) wallet owners currently own and can currently spend.

\begin{definition}\label{e-note-img}
An \textbf{\em e-note image} for an e-note $(C, K^o, m)$ is a tuple $(C', K'^o, \tilde{K})$ such that
\begin{align*}
C' &= t_c H_0 + C \\ &= (t_c+x) H_0 + a H_1 \\ &= v_c H_0 + a H_1 \ , \\
K'^o &= t_k G_0 + K^o \\ &= (t_k + k_0^o) G_0 + k_1^o G_1 + k_2^o G_2 \\ &= v_k G_0 + k_1^o G_1 + k_2^o G_2 \ ,\ \text{and} \\
\tilde{K} &= (k_2^o/k_1^o)J
\end{align*}
for $t_c, t_k \xleftarrow{\$}\mathbb{F}$ and independent to each other.
\end{definition}
$C'$ is called the \textbf{masked amount commitment}, $K'^o$ is called the \textbf{masked address}, and $\tilde{K}$ is called the \textbf{linking tag}. Basically, e-note images are ``commitments" to e-notes for wallet owners to communicate that those e-notes are just spent in a transaction.

\subsection{Sender-receiver shared secret scheme}
Although Diffie-Hellman key exchange would be the most common implementation for this, any scheme that satisfies the following can be used:
\begin{definition}\label{sha-sec}
A \textbf{\em sender-receiver shared secret scheme} is a tuple of functions $(\mathcal{S}_0, \mathcal{S}_1, \mathcal{S}_2)$ such that:
    \begin{itemize}
        \item If $X = \mathcal{S}_0(x)$ and $(R, S) = \mathcal{S}_1(r, X)$, then $S = \mathcal{S}_2(x, R)$.
        \item Given $X$, $R$, and the tuple, the problem of determining $S$ satisfying the previous condition is hard.
    \end{itemize}
\end{definition}

\begin{definition}\label{recv-addr}
A \textbf{\em receiver address} is a tuple $(K^r, M^r) = \mathcal{S}_0(k_0^r, k_1^r, k_2^r, m^r)$  such that $K^r = k_0^r G_0 + k_1^r G_1 + k_2^r G_2$ and $M^r$ and $m^r$ are public and private arbitrary data, respectively.
\end{definition}
We say that someone \textit{owns} a receiver address if they know the corresponding scalars $k_0^r, k_1^r, k_2^r, m^r \in\mathbb{F}$.

\subsection{Authenticated symmetric encryption scheme}
We require the use of an authenticated symmetric encryption scheme. The shared secret can be used to produce the key for encryption and the authentication tag. We denote the encryption and decryption of data $x$ with the input $k$ for Key Derivation Function (KDF) as ${\tt enc}[k](x)$ and ${\tt dec}[k](x)$, respectively. We put overlines (e.g. $\overline{x}$) to indicate encrypted data.

The required security properties for application to Seraphis are described in Subsection \ref{sec-symm}.

\section{A Simple Seraphis transaction}\label{ser-tx}
Suppose that Alice would send $a_t\in\mathbb{F}$ amount of funds to Bob. Alice owns a set of e-notes $\{(C_i,K_i^o,m_i)\}_{i=1}^n$ with a total amount of $\big(\sum_{i=1}^{n}{a_i}\big)\ge a_t$, all \textit{connected} to a receiver address $(K_{ali}^r, M_{ali}^r)$. This ``connection" will be elaborated later on. On the other hand, Bob owns a receiver address  $(K_{bob}^r, M_{bob}^r)$. For Bob to receive the funds, he will now send his receiver address to Alice. Alice will actually send funds to two addresses: to Bob's and to herself (for the ``change" $a_{c} = \sum_{i=1}^{n}{a_i} - a_t$ \textit{even if} $a_{c}=0$). Hence, Alice must create 2 new e-notes. She starts the transaction by doing the following:
\begin{enumerate}
    \item Generate $r_{ali}, r_{bob}\xleftarrow{\$}\mathbb{F}$ and independent to each other.
    \item Compute $(S_{ali}, R_{ali}) = \mathcal{S}_1(r_{bob}, (K_{ali}^r, M_{ali}^r))$ and $(S_{bob}, R_{bob}) = \mathcal{S}_1(r_{bob}, (K_{bob}^r, M_{bob}^r))$ and store $R_{ali}$ and $R_{bob}$ to new empty memos $m_{ali}$ and $m_{bob}$, respectively. The two secrets must be independent to each other.
    \item Compute the one-time addresses
    \begin{align*}
        K_{ali}^o &= \mathcal{H}_0(S_{ali}) G_0 + \mathcal{H}_1(S_{ali}) G_1 + \mathcal{H}_2(S_{ali}) G_2 + K_{ali}^r\\
        K_{bob}^o &= \mathcal{H}_0(S_{bob}) G_0 + \mathcal{H}_1(S_{bob}) G_1 + \mathcal{H}_2(S_{bob}) G_2+ K_{bob}^r.
    \end{align*}    
    \item Compute the amount commitments $C_{ali} = \mathcal{H}_3(S_{ali}) G + a_c H$ and $C_{bob} = \mathcal{H}_3(S_{bob}) G + a_t H$. 
    \item Encrypt the amounts: $\overline{a_c} = {\tt enc}[\mathcal{H}_4(S_{ali})](a_c)$ and $\overline{a_t} = {\tt enc}[\mathcal{H}_4(S_{bob})](a_t)$, and store $\overline{a_c}$ and $\overline{a_t}$ to memos $m_{ali}$ and $m_{bob}$, respectively.
\end{enumerate}
Alice now has two new e-notes: ${\tt enote}_{ali} = (C_{ali}, K_{ali}^o, m_{ali})$ and ${\tt enote}_{bob} = (C_{bob}, K_{bob}^o, m_{bob})$. These will then be stored to a new (empty) \textit{whole transaction} $T$. Other objects that will be stored to the whole transaction are from proving systems, which can be executed in \textit{any} order. Proving systems are discussed in the next subsections and the required security properties for application to Seraphis are described in Subsection \ref{prov-prop}.

For specific instances of Seraphis, there might be changes in some parts of the above steps, and as a consequence, in reflected parts of the Receipt. Here are some notable changes:
\begin{itemize}
\item A Seraphis transaction can easily have multiple receivers aside from Bob, which implies that Alice will create more than 2 new e-notes. This technically breaks the privacy property described in Subsection \ref{sec-thm}. However, the same property guarantees that the number of receivers would be the \textit{only} break.
\item It may be possible that a Seraphis transaction can be collaboratively constructed by multiple players. This is the subject of the so-called ``Modular Transaction Building" in ``Implementing Seraphis" \cite{seraphis}, Section 10.
\end{itemize}

\subsection{Ownership and Unspentness (O\&U) proofs}\label{own-unsp}
Ownership and unspentness proof guarantees to verifiers that Alice the sender truly owns her set of e-notes and she doesn't already spent it. For each of Alice's owned e-notes $\{(C_i,K_i^o,m_i)\}_{i=1}^n$, Alice must do the following:
\begin{enumerate}
    \item If the masked address $K_i'^o$ is already in the e-note image ${\tt enimg}_i$ in $T$, then go to next step. Else generate $K_i'^o$ from $(C_i, K_i^o, m_i)$ as per definition, and insert it to ${\tt enimg}_i$ in $T$.
    \item If the linking tag $\tilde{K}_i$ is already in ${\tt enimg}_i$ in $T$, then go to next step. Else generate $\tilde{K}_i$ from $(C_i, K_i^o, m_i)$ as per definition, and insert it to ${\tt enimg}_i$ in $T$.
    \item Prepare the proof transcript $\Pi_{\text{o\&u}, i}$ for a non-interactive proving system for the following relation:
$$\{(K_i'^o, \tilde{K}_i\in\mathbb{G}; t_{k,i}, v_{k,i}, k_{1,i}^o, k_{2,i}^o\in\mathbb{F}): K_i'^o = v_{k,i} G_0 + k_{1,i}^o G_1 + k_{2,i}^o G_2 \wedge k_{1,i}^o \ne 0 \wedge \tilde{K}_i = (k_{2,i}^o/k_{1,i}^o)J \}$$
    \item Insert $\Pi_{\text{o\&u}, i}$ to $\{{\tt enimg}_i, \ldots\}$ in $T$.
\end{enumerate}
Aside from verifying the proof transcript, the verifier must confirm that the linking tags do not yet appear in the ledger.

\subsection{Amount balance}\label{amt-bal}
Amount balance guarantees to verifiers that the sum of input amounts always equals the sum of output amounts in
every transaction. For each of Alice's owned e-notes $\{(C_i,K_i^o,m_i)\}_{i=1}^n$, Alice must do the following:
\begin{enumerate}
    \item If the masked amount commitment $C_i'$ is already in ${\tt enimg}_i$ in $T$, then exit this subsection. Else generate $C_i'$ from $(C_i, K_i^o, m_i)$ as per definition. Then compute the difference:
    $$D = d_0 H_0 + d_1 H_1 = C_{ali}+C_{bob} - \sum_{i=1}^n{C_i'}$$
    Note that $d_0$ is uniformly random because of $t_c$ inside $C_i'$ and random oracle $\mathcal{H}$ inside $C_{ali}$ and $C_{bob}$, while $d_1$ is a publicly known extra amount (e.g. transaction fee).
    \item Insert $C_i'$ to ${\tt enimg}_i$ in $T$, and store $(d_0, d_1)$ to $T$.
\end{enumerate}
The verifier must verify the amount balance $\sum_{i=1}^n{C_i'} + D = C_{ali}+C_{bob}$ and $0\le d_1 \le d_{1,max}$.

\subsection{Membership proofs}\label{mem}
Membership proof guarantees to verifiers that each owned e-note of Alice is in a set of e-notes in the ledger. For each of Alice's owned e-notes $\{(C_i,K_i^o,m_i)\}_{i=1}^n$, Alice must do the following:
\begin{enumerate}
    \item If the masked amount commitment $C_i'$ is already in ${\tt enimg}_i$ in $T$, then go to next step. Else generate $C_i'$ from $(C_i, K_i^o, m_i)$ exactly like in Step 1 of Subsection \ref{amt-bal}, and insert it to ${\tt enimg}_i$ in $T$.
    \item If the masked address $K_i'^o$ is already in ${\tt enimg}_i$ in $T$, then go to next step. Else generate $K_i'^o$ from $(C_i, K_i^o, m_i)$ as per definition, and insert it to ${\tt enimg}_i$ in $T$.
    \item Collect $s-1$ number of random e-notes from the ledger and add her owned $(C_i,K_i^o,m_i)$, for a total of $s$ e-notes. The number $s$ is called the \textbf{anonymity size}.
    \item For each e-note in the collection (of size $s$), extract only the amount commitment and one-time address like this: $(C_j, K_j^o)$. Then arrange the $s$ e-notes in random positions. Alice now has an array (of length $s$) of pairs: $\mathbb{S}_i = \{(C_j, K_j^o)\}_{j=1}^s$, which is called the \textbf{ring}. Its elements $(C_j, K_j^o)$ are called the \textbf{ring members}. 
    \item Prepare the proof transcript $\Pi_{\text{mem}, i}$ for a non-interactive proving system for the following relation:
$$\{(C_i', K_i'^o \in\mathbb{G}, \mathbb{S}_i\subset\mathbb{G}^2; \pi_i\in\mathbb{N}, t_{c,i}, t_{k,i}\in\mathbb{F}): 1\le\pi_i\le s \wedge C_i' - C_{\pi_i} = t_{c,i} H_0 \wedge K_i'^o - K_{\pi_i}^o = t_{k,i} G_0 \}$$
    \item Insert $\mathbb{S}_i$, $\Pi_{\text{mem}, i}$ to $\{{\tt enimg}_i, \ldots\}$ in $T$.
\end{enumerate}
Aside from verifying the proof transcript, the verifier must confirm that all the collected e-notes in rings appear in the ledger.

Specific proving systems satisfying the relation include CSAG (CLSAG \cite{clsag} without linking) and One-out-of-Many proving system adapted from Groth and Bootle \textit{et al.} \cite{groth, bootle}.

\subsection{Range proofs}\label{range}
Range proof guarantees to everyone that the committed amount $a$ lies in a range.  For the new e-notes ${\tt enote}_{ali}$ and ${\tt enote}_{bob}$, Alice must do the following:
\begin{enumerate}
    \item Prepare the respective proof transcript $\Pi_{\text{ran}, ali}$ and $\Pi_{\text{ran}, bob}$ for a non-interactive proving system for the following relation:
$$\{(C \in\mathbb{G}, a_{max}\in\mathbb{F}; x, a\in\mathbb{F}): C = x H_0 + a H_1 \wedge 0\le a \le a_{max}\}$$
	where $a_{max}$ is the maximum e-note amount.
    \item Store $\Pi_{\text{ran}, ali}$ and $\Pi_{\text{ran}, bob}$ to $T$.
\end{enumerate}

Specific proving systems satisfying the relation include Bulletproofs \cite{bp} and Bulletproofs+ \cite{bp-plus}.

\subsection{Receipt}
Once the construction of $T$ is completed, Alice sends it to the network. Its contents must now be
$$T=\{{\tt enote}_{ali}, {\tt enote}_{bob}, \Pi_{\text{ran}, ali}, \Pi_{\text{ran}, bob}, d_0, d_1, \{{\tt enimg}_i, \Pi_{\text{o\&u}, i}, \mathbb{S}_i, \Pi_{\text{mem}, i}\}_{i=1}^n\}.$$
We denote the full construction of $T$ as the function ${\tt tx}(\cdot)$. This function would be used for describing Seraphis security properties (Subsection \ref{sec-thm}).

Suppose that the verifier accepts $T$, hence $T$ is now stored in the ledger. When Bob scans the ledger for new transactions, he must do the following for every $T$ he encounters:
\begin{enumerate}
    \item Get a new e-note $(C, K^o, m)$ in $T$. Note that $m$ contains $\{R, \overline{a}\}$ (see the beginning of this whole section).
    \item Compute the nominal sender-receiver shared secret: $S_{nom} = \mathcal{S}_2((k_0^r, k_1^r, k_2^r, m^r), R) $.
    \item Compute the nominal spend public key: $K_{nom}^r = K^o - \mathcal{H}_0(S_{nom}) G_0 - \mathcal{H}_1(S_{nom}) G_1 - \mathcal{H}_2(S_{nom}) G_2$. If $K_{nom}^r = K_{bob}^r$, then the e-note is \textit{connected} to Bob's receiver address, and proceed to the next step (this is the ``connection" hinted at the beginning of this whole section).  Otherwise (if not equal), the e-note is not connected, and hence go to Step 1.
    \item Decrypt the amount: $a = {\tt dec}[\mathcal{H}_4(S_{nom})](\overline a)$.
    \item Compute the nominal amount commitment: $C_{nom} = \mathcal{H}_3(S_{nom}) H_0 + a H_1$. If $C_{nom} \ne C$, then the e-note is malformed and cannot be spent. The balance property described in Subsection \ref{sec-thm} must prevent Bob from spending it successfully.
    \item Compute the nominal linking tag: $$\tilde{K}_{nom} = \frac{k_2^r + \mathcal{H}_2(S_{nom})}{k_1^r + \mathcal{H}_1(S_{nom})}J.$$ If he finds a copy of $\tilde{K}_{nom}$ in the ledger, then the e-note has already been spent. The balance property described in Subsection \ref{sec-thm} and the verifier checking that new linking tags do not yet appear in the ledger (see Subsection \ref{own-unsp}) must prevent Bob from spending it successfully.
\end{enumerate}
If an e-note $(C, K^o, m)$ is connected to Bob's receiver address, then he knows its corresponding scalars $k_0^o, k_1^o, k_2^o, a, x$ (e.g. $k_0^o = k_0^r + \mathcal{H}_0(S_{nom})$). Hence, connection implies e-note ownership. The transaction is complete for Bob.

For Alice to receive the change e-note, she must do the same above steps. After that, the transcation is complete for Alice. This finishes a Seraphis transaction.

\section{Security model}\label{sec}
For a start, we assume that the distributed ledger is immutable. Therefore, the adversary in our analysis will never be able to modify transactions already stored in the ledger. This ledger immutability can be actualized through, for instance, the Nakamoto consensus protocol \cite{bitcoin}.

Subsections \ref{prov-prop} to \ref{comm} outline the required security properties of the cryptographic components for Seraphis, and Subsection \ref{sec-thm} is the main security analysis of Seraphis. Proofs for these properties are found in Appendix \ref{proofs}.

\subsection{Proving systems security properties}\label{prov-prop}
We define a proving system as a tuple $(\textsf{Setup}, \mathcal{P}, \mathcal{V})$. $\textsf{Setup}$ is the setup algorithm: $pp\leftarrow\textsf{Setup}(1^{\lambda})$, and $\mathcal{P}$ and $\mathcal{V}$ are $\textsf{PPT}$ algorithms called \textbf{Prover} and \textbf{Verifier}, respectively. We denote the \textit{transcript} (all data being sent and received in the protocol) produced by $\mathcal{P}$ and $\mathcal{V}$ when dealing with inputs $x$ and $y$ as $tr\leftarrow\langle\mathcal{P}(x), \mathcal{V}(y)\rangle$. Once the transcript is produced, we denote the final transcript verification as $tr=1$ if accepted and $tr=0$ if rejected. 

Let $\mathcal{R}$ be an NP (polynomial-time verifiable) relation of the form $\{(x,w):P(x, w)\}$ where $x$ is the \textit{statement}, $w$ is the \textit{witness}, and $P$ is a predicate of $x$ and $w$. Then ``$(\textsf{Setup}, \mathcal{P}, \mathcal{V})$ is a proving system for the relation $\mathcal{R}$" informally means that when $\mathcal{P}$ gives an $x$ to $\mathcal{V}$, $\mathcal{P}$ must convince $\mathcal{V}$ that it knows a $w$ such that $(x,w)\in\mathcal{R}$ by generating $tr\leftarrow\langle\mathcal{P}(pp, x, w), \mathcal{V}(pp, x)\rangle$ that $\mathcal{V}$ accepts.

Here are the \textit{minimal} needed security properties of proving systems for Seraphis:

\begin{definition}[Perfect Completeness]
$(\emph{\textsf{Setup}}, \mathcal{P}, \mathcal{V})$ is perfectly complete for $\mathcal{R}$ if for all $\emph{\textsf{PPT}}$ adversary $\mathcal{A}$,
\begin{align*}
\emph{\textsf{Pr}}\left[
\begin{array}{c|c}
    \begin{gathered}
        (x,w)\in\mathcal{R}\\
        \wedge\ tr=0
    \end{gathered}
    &
    \begin{gathered}
        pp\leftarrow\emph{\textsf{Setup}}(1^{\lambda}); (x, w)\leftarrow\mathcal{A}(pp); \\
        tr\leftarrow\langle\mathcal{P}(pp,x,w), \mathcal{V}(pp,x)\rangle
    \end{gathered}
\end{array}
\right]
= 0.
\end{align*}
\end{definition}

\begin{definition}[Computational Soundness]
$(\emph{\textsf{Setup}}, \mathcal{P}, \mathcal{V})$ is computationally sound for $\mathcal{R}$ if for all $\emph{\textsf{PPT}}$ adversary $\mathcal{A}$, there exists a negligible function $\emph{\textsf{negl}}(\lambda)$ such that
\begin{align*}
\emph{\textsf{Pr}}\left[
\begin{array}{c|c}
    \begin{gathered}
        (x,w)\not\in\mathcal{R}\\
        \wedge\ tr=1
    \end{gathered}
    &
    \begin{gathered}
        pp\leftarrow\emph{\textsf{Setup}}(1^{\lambda}); (x, w)\leftarrow\mathcal{A}(pp); \\
        tr\leftarrow\langle\mathcal{P}(pp,x,w), \mathcal{V}(pp,x)\rangle
    \end{gathered}
\end{array}
\right]
\le \emph{\textsf{negl}}(\lambda).
\end{align*}
\end{definition}

There is another notion of soundness called \textit{Special Soundness}. For a proving system to be special sound, there must exist a \textit{witness extractor} that has an ability to ``rewind time" and make the prover answer several different challenges, and it must be able to extract a witness given the several accepted transcripts with the prover. Special soundness is a stronger notion of soundness, hence this already implies computational soundness.

\begin{definition}[Perfect Special HVZK]
$(\emph{\textsf{Setup}}, \mathcal{P}, \mathcal{V})$ is perfect special honest-verifier zero knowledge (PSHVZK) for $\mathcal{R}$ if there exists a $\emph{\textsf{PPT}}$ simulator $\mathcal{S}$ such that for all $\emph{\textsf{PPT}}$ adversary $\mathcal{A}$,
\begin{align*}
\emph{\textsf{Pr}}\left[
\begin{array}{c|c}
    \begin{gathered}
        (x,w)\in\mathcal{R}\\
        \wedge\ tr = 1
    \end{gathered}
    &
    \begin{gathered}
        pp\leftarrow\emph{\textsf{Setup}}(1^{\lambda}); (x, w, \rho)\leftarrow\mathcal{A}(pp); \\
        tr\leftarrow\langle\mathcal{P}(pp,x,w), \mathcal{V}(pp,x; \rho)\rangle
    \end{gathered}
\end{array}
\right] \\
=\emph{\textsf{Pr}}\left[
\begin{array}{c|c}
    \begin{gathered}
        (x,w)\in\mathcal{R}\\
        \wedge\ tr = 1
    \end{gathered}
    &
    \begin{gathered}
        pp\leftarrow\emph{\textsf{Setup}}(1^{\lambda}); (x, w, \rho)\leftarrow\mathcal{A}(pp); \\
        tr\leftarrow\mathcal{S}(pp, x, \rho)
    \end{gathered}
\end{array}
\right]
\end{align*}
where $\rho$ is the public randomness used by $\mathcal{V}$.
\end{definition}

\textit{Fiat-Shamir heuristic} is applied to make interactive protocols non-interactive. Moreover, it transforms interactive protocols satisfying PSHVZK into non-interactive (fully) zero-knowledge (NIZK) protocols in the random oracle model.

All proving systems for application to Seraphis must be non-interactive and at least have perfect completeness,  computational soundness, and NIZK.

\subsection{Authenticated symmetric encryption scheme}\label{sec-symm}
We require that the authenticated symmetric encryption scheme must at least have the following properties: indistinguishable against adaptive chosen-ciphertext attack (IND-CCA2) and key-private under chosen-ciphertext attacks (IK-CCA). The definitions of these properties can be found in \cite{omniring}, Appendix A.4.

\subsection{Commitment schemes}\label{comm}
We define a commitment scheme as a tuple $(\textsf{Setup}, \textsf{Comm})$. $\textsf{Setup}$ is the setup algorithm: $pp\leftarrow\textsf{Setup}(1^{\lambda})$, and $\textsf{Comm}:\mathcal{M}\times{\chi}\rightarrow\mathcal{C}$ is the $\textit{commitment function}$, where $\mathcal{M}$ is the message space, $\chi$ is the randomness space, and $\mathcal{C}$ is the commitment space. Note that $\mathcal{M}, \chi$ and $\mathcal{C}$ are all constructed from $pp$.
To commit to a message $m \in M$, the sender selects $r\xleftarrow{\$}\chi$ and computes the commitment $C = \textsf{Comm}(m; r)$. We define the required security properties of commitment schemes.

\begin{definition}[Hiding Property]
A commitment scheme $(\emph{\textsf{Setup}}, \emph{\textsf{Comm}})$ is computationally hiding if for all $\emph{\textsf{PPT}}$ adversary $\mathcal{A}$, there exists a negligible function $\emph{\textsf{negl}}(\lambda)$ such that
\begin{align*}
\left| \frac{1}{2} - \emph{\textsf{Pr}}\left[
\begin{array}{c|c}
    \begin{gathered}
        b' = b
    \end{gathered}
    &
    \begin{gathered}
        pp\leftarrow\emph{\textsf{Setup}}(1^{\lambda}); (m_0, m_1)\leftarrow\mathcal{A}(pp); \\
        b\xleftarrow{\$}\{0,1\}; r \xleftarrow{\$}\chi; \\
        C = \emph{\textsf{Comm}}(m_b; r); b'\leftarrow\mathcal{A}(C)
    \end{gathered}
\end{array}
\right]\right|
\le \emph{\textsf{negl}}(\lambda).
\end{align*}
\end{definition}
A commitment scheme is \textit{perfectly hiding} if $\textsf{negl}(\lambda)$ is replaced by $0$.

\begin{definition}[Binding Property]
A commitment scheme $(\emph{\textsf{Setup}}, \emph{\textsf{Comm}})$ is computationally binding if for all $\emph{\textsf{PPT}}$ adversary $\mathcal{A}$, there exists a negligible function $\emph{\textsf{negl}}(\lambda)$ such that
\begin{align*}
\emph{\textsf{Pr}}
\left[
\begin{array}{c|c}
    \begin{gathered}
         \emph{\textsf{Comm}}(m_0;r_0) \\
        = \emph{\textsf{Comm}}(m_1;r_1) \\
        \wedge\ m_0 \ne m_1
    \end{gathered}
    &
    \begin{gathered}
        pp\leftarrow\emph{\textsf{Setup}}(1^{\lambda}); \\
        (m_0,m_1,r_0,r_1)\leftarrow\mathcal{A}(pp)
    \end{gathered}
\end{array}
\right]
\le \emph{\textsf{negl}}(\lambda).
\end{align*}
\end{definition}
A commitment scheme is \textit{perfectly binding} if $\textsf{negl}(\lambda)$ is replaced by $0$.

\noindent The first kind of commitment we define is commonly known as \textbf{Pedersen commitments} \cite{pedersen}. We define two instances, $\textsf{PedersenC}:\mathbb{F}^2\rightarrow\mathbb{G}$ and $\textsf{PedersenK}:\mathbb{F}^3\rightarrow\mathbb{G}$ as follows:
\begin{align*}
\textsf{PedersenC}(a; x) &= x H_0 + a H_1 \\
\textsf{PedersenK}(k_1^o, k_2^o; k_0^o) &= k_0^o G_0 + k_1^o G_1 + k_2^o G_2
\end{align*}
$\textsf{PedersenC}$ corresponds to the formulas of amount commitment $C$ and masked amount commitment $C'$, while $\textsf{PedersenK}$ corresponds to the formulas of one-time address $K^o$.
\begin{theorem}[From \cite{pedersen}]\label{thm-pedersen}
Pedersen commitment is perfectly hiding and computationally binding under the DL assumption.
\end{theorem}

\noindent We now define a custom commitment $\textsf{LinkTag}:\mathbb{F}\times\mathbb{F}\setminus\{0\}\times\mathbb{F}\times\mathbb{F}\rightarrow\mathbb{G}^2$ as follows:
\begin{align*}
\textsf{LinkTag}(k_0^o, k_1^o, k_2^o; t_k) = ((t_k + k_0^o) G_0 + k_1^o G_1 + k_2^o G_2, (k_2^o/k_1^o) J)
\end{align*}
with $t_k\xleftarrow{\$}\mathcal{F}$ being the blinding factor. $\textsf{LinkTag}$ corresponds to the combination of formulas of masked address $K'^o$ and linking tag $\tilde{K}$.

\begin{theorem}\label{thm-linktag}
$\emph{\textsf{LinkTag}}$ is perfectly hiding and computationally binding under the DL assumption.
\end{theorem}

\subsection{Seraphis security properties}\label{sec-thm}
The required security properties for Seraphis are loosely based on Omniring's security model, with modifications to fit Seraphis. The Omniring paper presents a rigorous treatment of RingCT constructions, providing precision for security analysis against several realistic attacks.

The first security property is \textbf{Completeness} (called \textit{Correctness} in Omniring), which means that if an e-note appears on the ledger, then its owner can honestly generate an accepted transaction spending it. Seraphis satisfying completeness immediately follows from the completeness properties of the cryptographic components and by inspection of the protocol description.

Next we consider the \textbf{Balance} property, which means that a spender adversary should never be able to spend more amounts than it truly owns, hence preventing double-spending. Balance property involves an experiment $\textsf{BAL}(\mathcal{A}, 1^{\lambda})$  on a $\textsf{PPT}$ adversary $\mathcal{A}$. The adversary succeeds in the experiment (i.e. $\textsf{BAL}(\mathcal{A}, 1^{\lambda})=1$) if it managed to generate an accepted transaction such that
1) some of ``spent e-notes" are just made up and not in the ledger, 2) all spent e-notes are in the ledger, but some are supposedly owned by others, 3) some linking tags are not generated from the given one-time private keys, leading to double-spend of owned e-notes, or 4) the amount of the new e-note for the receiver is larger than the supposed total amount of e-notes it owns.

\begin{figure}[htbp]
\centering
\fbox{\begin{minipage}{0.85\textwidth}
\underline{$\textsf{BAL}(\mathcal{A}, 1^{\lambda})$}
\begin{itemize}
\item $pp\leftarrow\textsf{Setup}(1^{\lambda})$.
\item $\mathcal{A}$ is provided the whole ledger $\{T_i\}$, scalars $k_0^r, k_1^r, k_2^r, m^r$ to construct the address ${\tt addr}_{\mathcal{A}} = (K_{\mathcal{A}}^{r}, M_{\mathcal{A}}^r)$, scalars $\{k_{0,i}^o, k_{1,i}^o, k_{2,i}^o, a_i, x_i\}_{i=1}^n$ that makes ${\tt addr}_{\mathcal{A}}$ connect to $\{{\tt enote}\}_{\mathcal{A}}=\{(C_i,K_i^o,m_i)\}_{i=1}^n$ in the ledger, all the other addresses $\{{\tt addr}\}_{\neg\mathcal{A}}$, and knowledge of all the connections between every e-note to every address. The e-notes not owned by $\mathcal{A}$ are denoted as $\{{\tt enote}\}_{\neg\mathcal{A}}$.
\item $\mathcal{A}$ chooses any receiver address ${\tt addr}_{\mathcal{B}}$.
\item $T \leftarrow\mathcal{A}(pp, \{{\tt enote}\}_{\mathcal{A}}, \{{\tt enote}\}_{\neg\mathcal{A}}, \{k_{0,i}^o, k_{1,i}^o, k_{2,i}^o, a_i, x_i\}_{i=1}^n)$, where $T$ is a transaction.
\item $b_0:=1$ if Verifier accepts $T$, else $:=0$.
\item $b_1:=1$ if some ``spent e-notes" in $T$ are not in ledger, else $:=0$.
\item $b_2:=1$ if some spent e-notes in $T$ are from $\{{\tt enote}\}_{\neg\mathcal{A}}$, else $:=0$.
\item $b_3:=1$ if all spent e-notes in $T$ are owned by $\mathcal{A}$, but $\exists i: \tilde{K}_i \ne (k_{2,i}^o / k_{1,i}^o) J$, else $:=0$.
\item $b_4:=1$ if all spent e-notes in $T$ are owned by $\mathcal{A}$, but $a_t > \sum_{i=1}^n{a_i}$, else $:=0$.
\item Return $b_0 \wedge (b_1 \vee b_2 \vee b_3 \vee b_4)$.
\end{itemize}
\end{minipage}}
\caption{Balance experiment $\textsf{BAL}$}
\label{exp-bal}
\end{figure}

\begin{theorem}[Balance]\label{thm-bal}
Seraphis is balanced: for all $\emph{\textsf{PPT}}$ adversary $\mathcal{A}$, there exists a negligible function $\emph{\textsf{negl}}(\lambda)$ such that
\begin{align*}
\emph{\textsf{Pr}}
\left[
\emph{\textsf{BAL}}(\mathcal{A}, 1^{\lambda})=1
\right]
\le \emph{\textsf{negl}}(\lambda).
\end{align*}
where $\emph{\textsf{BAL}}$ is described in Figure \ref{exp-bal}.
\end{theorem}

Next we consider the \textbf{Privacy} property, which means that an adversary should never be able to distinguish between transactions, hence providing sender and receiver anonymity, and confidential transfer of amounts. Privacy property involves an experiment $\textsf{PRV}(\mathcal{A}, 1^{\lambda})$ on a $\textsf{PPT}$ adversary $\mathcal{A}$. In the experiment, it is as if $\mathcal{A}$ itself ``sent" amounts to the two potential senders, hence $\mathcal{A}$ is provided the sender and receiver addresses, the e-notes themselves, and the private scalars of the amount commitment $C$ in those e-notes. Given a whole transaction $T$, the adversary succeeds in the experiment if it can guess which of the two is used, hence breaking the privacy of $T$.

\begin{figure}[htbp]
\centering
\fbox{\begin{minipage}{0.85\textwidth}
\underline{$\textsf{PRV}(\mathcal{A}, 1^{\lambda})$}
\begin{itemize}
\item $pp\leftarrow\textsf{Setup}(1^{\lambda})$.
\item $\mathcal{A}$ is provided two random potential sender addresses ${\tt send}_0$ and ${\tt send}_1$, sets of e-notes $\{{\tt enote}\}_0$ and $\{{\tt enote}\}_1$ (with both containing $n$ e-notes) connected to ${\tt send}_0$ and ${\tt send}_1$ respectively, private scalars of $C$, $\{x_{0, i}, a_{0, i}\}_{i=1}^n$ and $\{x_{1, i}, a_{1, i}\}_{i=1}^n$, of each e-note in ${\tt enote}_0$ and ${\tt enote}_1$, respectively, and two random potential receiver addresses ${\tt recv}_0$ and ${\tt recv}_1$.
\item $\mathcal{A}$ constructs $\{\mathbb{S}_i\}_{i=1}^n$ such that each $\mathbb{S}_i$ contains only one e-note in $\{{\tt enote}\}_0$ and only one e-note in $\{{\tt enote}\}_1$.
\item $\mathcal{A}$ chooses any valid amount the potential senders would send: $0 \le a_{\mathcal{A}, 0} \le \sum_{i=1}^n{a_{0, i}}$ and $0 \le a_{\mathcal{A}, 1} \le \sum_{i=1}^n{a_{1, i}}$ for ${\tt send}_0$ and ${\tt send}_1$, respectively.
\item $b\xleftarrow{\$}\{0,1\}$.
\item $T\leftarrow{\tt tx}(pp, {\tt send}_b, {\tt recv}_b, \{{\tt enote}\}_b, \{\mathbb{S}_i\}_{i=1}^n, a_{\mathcal{A}, b})$. The owner of ${\tt send}_b$ honestly spends all e-notes in $\{{\tt enote}\}_b$ (which are also in $\{\mathbb{S}_i\}_{i=1}^n$) to send the amount $a_{\mathcal{A}, b}$ to ${\tt recv}_b$.
\item If Verifier rejects $T$, then return $0$.
\item $b'\leftarrow\mathcal{A}(pp, T, \{{\tt send}_j, {\tt recv}_j, \{x_{j, i}, a_{j,i}\}_{i=1}^n, a_{\mathcal{A},j}\}_{j\in \{0,1\}})$.
\item Return $1$ if $b = b'$, else $0$.
\end{itemize}
\end{minipage}}
\caption{Privacy experiment $\textsf{PRV}$}
\label{exp-prv}
\end{figure}

\begin{theorem}[Privacy]\label{thm-prv}
Seraphis is private: for all $\emph{\textsf{PPT}}$ adversary $\mathcal{A}$, there exist a negligible function $\emph{\textsf{negl}}(\lambda)$ such that
\begin{align*}
\emph{\textsf{Pr}}
\left[
\emph{\textsf{PRV}}(\mathcal{A}, 1^{\lambda})=1
\right]
\le \emph{\textsf{negl}}(\lambda).
\end{align*}
where $\emph{\textsf{PRV}}$ is described in Figure \ref{exp-prv}.
\end{theorem}

Lastly, we consider the \textbf{Non-slanderability} property, which means that an adversary should never be able to forge a linking tag of an honest user's e-notes when those are spent. Non-slanderability property involves an experiment $\textsf{NSLAND}(\mathcal{A}, 1^{\lambda})$ on a $\textsf{PPT}$ adversary $\mathcal{A}$. This property prevents the following attack known as \textit{denial-of-spending attack} \cite{denial-of-spend}: the adversary is in a remote node that can receive transactions, and also acts as a verifier of a victim transaction $T$. This means that $\mathcal{A}$ can see the linking tags in $T$. $\mathcal{A}$ then temporarily blocks $T$ from entering the ledger, creates a new transaction $T'$ that matches some linking tags in $T$, and enters $T'$ first in the ledger before finally entering $T$. This way $T$ is marked as a double-spend, and some e-notes of the victim sender are now unspendable. Now the adversary succeeds in the experiment if it successfully accomplished a denial-of-spending attack.

\begin{figure}[htbp]
\centering
\fbox{\begin{minipage}{0.85\textwidth}
\underline{$\textsf{NSLAND}(\mathcal{A}, 1^{\lambda})$}
\begin{itemize}
\item $pp\leftarrow\textsf{Setup}(1^{\lambda})$.
\item $\mathcal{A}$ is provided the whole ledger $\{T_i\}$, scalars $k_0^r, k_1^r, k_2^r, m^r$ to construct the address ${\tt addr}_{\mathcal{A}} = (K_{\mathcal{A}}^{r}, M_{\mathcal{A}}^r)$, scalars $\{k_{0,i}^o, k_{1,i}^o, k_{2,i}^o, a_i, x_i\}_{i=1}^n$ that makes ${\tt addr}_{\mathcal{A}}$ connect to $\{{\tt enote}\}_{\mathcal{A}}=\{(C_i,K_i^o,m_i)\}_{i=1}^n$ in the ledger, all the other addresses $\{{\tt addr}\}_{\neg\mathcal{A}}$, and knowledge of all the connections between every e-note to every address. The e-notes not owned by $\mathcal{A}$ are denoted as $\{{\tt enote}\}_{\neg\mathcal{A}}$.
\item $\mathcal{A}$ chooses any receiver address ${\tt addr}_{\mathcal{B}}$, the victim address ${\tt addr}_{\mathcal{C}}$, and another address ${\tt addr}_{\mathcal{D}}$.
\item $T\leftarrow{\tt tx}(pp, {\tt addr}_{\mathcal{C}}, {\tt addr}_{\mathcal{D}}, \{{\tt enote}\}_{\mathcal{C}})$. The owner of ${\tt addr}_{\mathcal{C}}$ honestly spends all e-notes in $\{{\tt enote}\}_{\mathcal{C}}$ to send some amounts to ${\tt addr}_{\mathcal{D}}$. Let $\{\tilde{K}_{\mathcal{C}}\}$ be all the linking tags in $T$.
\item $\mathcal{A}$ is provided $T$ and verifies it honestly. If $\mathcal{A}$ rejects $T$, then return 0.
\item $T' \leftarrow\mathcal{A}(pp, \{{\tt enote}\}_{\mathcal{A}}, T)$, where $T'$ is a transaction. Let $\{\tilde{K}_{\mathcal{A}}\}$ be all the linking tags in $T'$.
\item $b_0:=1$ if Verifier accepts $T'$, else $:=0$
\item $b_1:=1$ if $\{\tilde{K}_{\mathcal{A}}\}\cap \{\tilde{K}_{\mathcal{C}}\}\ne\emptyset$, else $:=0$
\item Return $b_0 \wedge b_1$.
\end{itemize}
\end{minipage}}
\caption{Non-slanderability experiment $\textsf{NSLAND}$}
\label{exp-nsland}
\end{figure}

\begin{theorem}[Non-slanderability]\label{thm-nsland}
Seraphis is non-slanderable: for all $\emph{\textsf{PPT}}$ adversary $\mathcal{A}$, there exist a negligible function $\emph{\textsf{negl}}(\lambda)$ such that
\begin{align*}
\emph{\textsf{Pr}}
\left[
\emph{\textsf{NSLAND}}(\mathcal{A}, 1^{\lambda})=1
\right]
\le \emph{\textsf{negl}}(\lambda).
\end{align*}
where $\emph{\textsf{NSLAND}}$ is described in Figure \ref{exp-nsland}.
\end{theorem}

\bibliographystyle{plain}
\bibliography{seraphis}

\appendix

\section{Proofs of theorems in Section \ref{sec} [WIP!]}\label{proofs}
We first present another hardness assumption which will be helpful for the next proof. This assumption is used in Bulletproofs \cite{bp} and Bulletproofs+ \cite{bp-plus}:

\begin{definition}[Discrete Logarithm Relation Assumption]\label{dl-rel}
DL Relation assumption holds relative to $\emph{\textsf{Setup}}$ if for all $n \ge 2$ and  $\emph{\textsf{PPT}}$ adversary $\mathcal{A}$, there exists a negligible function $\emph{\textsf{negl}}(\lambda)$ such that
\begin{align*}
\emph{\textsf{Pr}}\left[
\begin{array}{c|c}
	\begin{gathered}
		\exists i \in \{1, \ldots, n\}: x_i \ne 0 \\
		\wedge \sum_{i=1}^{n} x_i G_i = 0
	\end{gathered}
	&
	\begin{gathered}
		(\mathbb{G}, \mathbb{F})\leftarrow\emph{\textsf{Setup}}(1^{\lambda}); \\
		\{G_i\}_{i=1}^n \xleftarrow{\$}\mathbb{G}; \\
		\{x_i\}_{i=1}^n \leftarrow\mathcal{A}(\mathbb{G}, \mathbb{F}, \{G_i\}_{i=1}^n) \\
	\end{gathered}
\end{array}
\right]
\le \emph{\textsf{negl}}(\lambda).
\end{align*}
\end{definition}

\begin{proof}[Proof of Theorem \ref{thm-linktag}]
For perfect hiding, assume an adversary with unlimited computational power. It can easily find the DL of $\tilde{K}$ base $J$, which is $(k_2^o/k_1^o)$. However, it still cannot find the inputted $k_0^o$, $k_1^o$ and $k_2^o$ because $K'^o = (t_k + k_0^o) G_0 + k_1^o G_1 + (k_1^o) (k_2^o/k_1^o) G_2 = (t_k + k_0^o) G_0 + k_1^o (G_1 + (k_2^o/k_1^o) G_2)$ is a Pedersen commitment for $k_1^o$ with $t_k + k_0^o$ as blinding factor.

For computational binding, by breaking the binding of $\textsf{LinkTag}$, $\mathcal{A}$ finds $(k_0^o, k_1^o, k_2^o; t_k)$ and $(k_0'^o, k_1'^o, k_2'^o; t'_k)$ such that the two are \textit{not} equal but $\textsf{LinkTag}$ evaluates to the same commitment value. This implies that
$$(t_k + k_0^o - t'_k - k_0'^o) G_0 + (k_1^o - k_1'^o) G_1 + (k_2^o - k_2'^o) G_2 = 0$$
and this breaks the DL relation assumption of $G_0, G_1, G_2 \in \mathbb{G}$.
\end{proof}
\begin{proof}[Proof of Theorem \ref{thm-bal}]
Assume that $\mathcal{A}$ succeeds in the $\textsf{BAL}$ experiment with non-negligible probability. There are four cases to consider:
\begin{enumerate}
\item Case 1: $b_0 \wedge b_1 = 1$. $\mathcal{A}$ makes up ${\tt enote}_*=(C,K^o,m)$, and pretends owning it. Then $\mathcal{A}$ has two possible actions: 1) $\mathcal{A}$ successfully found a set of corresponding scalars $k_0^o, k_1^o, k_2^o, a, x \in\mathbb{F}$. However this breaks the hiding or binding property of $\textsf{PedersenC}$ and $\textsf{PedersenK}$. 2) Even without a set of corresponding scalars, $\mathcal{A}$ managed to produce verified proofs for ${\tt enote}_*$. For the case of $C$, if $C'$ is generated correctly (i.e. $C' = t_c H_0 + C$), then $\mathcal{A}$ found $d_0, d_1 \in\mathbb{F}$ such that $ d_0 H_0 + d_1 H_1 = C_{ali} + C_{bob} - C'$ for a successful amount balance check, but this breaks the DL assumption of $\mathbb{G}$. On the other hand, if $\mathcal{A}$ came up with $d_0, d_1 \in\mathbb{F}$, then $\mathcal{A}$ produced a verified membership proof because $t_c$ is among the witness. But successfully finding $t_c$ breaks the DL assumption of $\mathbb{G}$ and not finding it breaks the soundness of membership proof. For the case of $K^o$, $\mathcal{A}$ produced a verified o\&u proof because $k_1^o, k_2^o$ are among the witnesses, but this breaks the soundness of o\&u proof.
\item Case 2: $b_0 \wedge b_2 = 1$. This is the same with Case 1 but with $\mathcal{A}$ knowing the ${\tt addr}_*$ connected to an ${\tt enote}_* \in\{{\tt enote}\}_{\neg\mathcal{A}}$ and the rest of the transaction $T_*$ containing ${\tt enote}_*$. Then $\mathcal{A}$ has four possible actions: 1) $\mathcal{A}$ successfully found a set of corresponding scalars $k_0^r, k_1^r, k_2^r, m^r \in\mathbb{F}$ of ${\tt addr}_*$, 2) $\mathcal{A}$ successfully found just $S_{nom}$, 3) $\mathcal{A}$ successfully found a set of corresponding scalars $k_0^o, k_1^o, k_2^o, a, x \in\mathbb{F}$ with the use of $T_*$, and 4) even without a set of corresponding scalars, $\mathcal{A}$ managed to produce verified proofs for ${\tt enote}_*$ with the use of $T_*$. Actions 1 and 2 both break the shared-secretness of $(\mathcal{S}_0, \mathcal{S}_1, \mathcal{S}_2)$. For action 1, it is because $\mathcal{A}$ can now easily compute $S_{nom}$ through $\mathcal{S}_2$. Action 3 breaks either the hiding or binding property of $\textsf{PedersenC}$ (from range proof) or $\textsf{LinkTag}$ (from o\&u proof), or NIZK of proving systems. Lastly, action 4 also breaks NIZK of proving systems, because action 4 implies that $\mathcal{A}$ obtained some information about the witnesses in proofs of $T_*$.
\item Case 3: $b_0 \wedge b_3 = 1$. This means for some $i$, $\mathcal{A}$ made up $\tilde{K}_{i,*}\in\mathbb{G}$ and then produced a verified o\&u proof with $\tilde{K}_{i,*}$ in statement, but $\tilde{K}_{i,*} \ne (k_{2,i}^o/k_{1,i}^o)J$, but this breaks the soundness of o\&u proof.
\item Case 4: $b_0 \wedge b_4 = 1$. For a start, the soundness of range proof prevents $\mathcal{A}$ in producing a valid transaction such that $a_t > a_{max}$. If $\mathcal{A}$ just made $a_t$ to be greater than $\sum_{i=1}^n{a_i}$ and proceed honestly, then the $d_1$ in account balance becomes ``negative", which implies that account balance is violated. If account balance is satisfied, then $\mathcal{A}$ successfully found $(a', x') \ne (a_i, x_i)$ such that $\textsf{PedersenC}(a'; x') = C_i$ for some $i$, but this breaks the binding property of $\textsf{PedersenC}$.
\end{enumerate}
This completes the proof.
\end{proof}
\begin{proof}[Proof of Theorem \ref{thm-prv}]
We prove by hybrid arguments \cite{hybrid}.
\end{proof}
\begin{proof}[Proof of Theorem \ref{thm-nsland}]
Assume that $\mathcal{A}$ succeeds in the $\textsf{NSLAND}$ experiment with non-negligible probability.
\end{proof}
\end{document}