\section{Introduction}

The Unspent Transaction Output (UTXO) model is a design common to many cryptocurrencies, including Bitcoin \cite{nakamoto2008bitcoin} and many of its derivatives, Cardano \cite{cardanoEUTXO}, Avalanche~\cite{Ava19}, and IOTA \cite{2020coordicide}.  In the UTXO model, transactions specify the outputs of previous transactions as inputs and create new outputs spending the inputs. Thus, a transaction consists of a list of inputs and a list of outputs. 
The outputs are associated to users` addresses by certain unlock conditions; in general, an account ``posseses'' a  private key and addresses that allow to spend and receive UTXOs. Accounts then track their balance by maintaining a list of the received (unspent) outputs.
This model differs to the account-based model used in most smart-contract-based cryptocurrencies, as for example Ethereum \cite{buterin2013ethereum}. The latter represents assets as balances within accounts, and transactions describe how these balances change, see Figure \ref{fig:AccountModel}. A comparison of blockchain data-models can be for example found in \cite{DataTypeInBlockchain} and we refer to \cite{vademecum} for a detailed discussion on these two models.



\begin{figure}
    \centering
    \includegraphics[width=0.48\textwidth]{ledger_overview2.png}
    \caption{Reality-based Ledger: the double-spending transactions $x$ and $y$ create two realities, $R_x$ and $R_y$. Each reality yields a valid ledger state.}
    \label{fig:realityBasedLedger}
\end{figure}

A conceptual difference is that the account-based model updates user balances globally, while the UTXO model only records transaction receipts. This construction allows transactions to be processed in parallel, leading to performance benefits and possible scalability advantages.  There is, however, a limiting effect for scalability in the presence of conflicting transaction. Here, conflicts are transactions that spent the same output. As the UTXO Ledger is an append-only structure, the conflicts have to be sorted out before changes are made to the ledger. This is currently done with the help of consensus protocols that are based on a (unique) leader or other mechanism to create a total ordering of the transactions.

We propose a solution to this ``bottleneck'' problem that allows leaderless conflict resolution that does not require a total ordering. To this end we define  an augmented data structure, the \emph{Reality-based Ledger}, which processes transactions optimistically and manages possible conflicts until they are resolved.
As a consequence, we can update the ledger on the arrival of the transactions. This contrasts with a blockchain system where transactions can only be processed once they are included in a batch or block. In further work,~\cite{OTV}, this feature is used to design a stream process-oriented DLT.  




\subsection{Results}
A UTXO Ledger induces a partial order on its transactions and thus can be seen as a partially ordered set (poset). Posets are in a one-to-one correspondence\footnote{The correspondence is in fact not one-to-one in the strict sense, but is in a weaker sense involving equivalence relations, see Section~\ref{sec: graph-theoretical notions}.} to directed acyclic graphs (DAGs). Typically, conflicts are excluded from an accepted state in such a ledger, however, this requires that participants reach consensus on which transactions to add to the ledger. This selection is usually performed by choosing a ``leader'' among the participants, and only this leader can add transactions to the ledger. These transactions are added in batches that are called \emph{blocks}. This leader is a ``centralized'' bottleneck that hinders scalability and annihilates most of the scalability advantages of the UTXO model. Some of these limitations remain even for leaderless consensus protocols that are based on a total ordering, as the total ordering requires a ``complete'' or ``non-sharded'' view of the set of transactions.

We define the \textit{Reality-based Ledger} as an augmented data structure of the conflict-free  UTXO Ledger, which may contain conflicting transactions. This Reality-based Ledger can contain several different \emph{realities}, where each of the realities corresponds to a conflict-free  UTXO Ledger, see Figure~\ref{fig:realityBasedLedger} for an illustration. We show that this data structure does not depend on the order of the incoming transactions and forms therefore an eventual consistent distributed data structure. We propose an additional data structure, called the Branch DAG, to manage the dependencies of the different realities. We provide several algorithms for an efficient management and update of the above graph data structures.
Notably, these algorithms update the data structures on the arrival of new data, thus minimizing the delay between issuance of transactions and addition to the distributed ledger and enabling a higher degree of stream processing in the underlying DLT.


To obtain a most recent valid ledger state, e.g., to determine the current balance for an account owner, we provide algorithms that extract a reality, based on a weight function that is imposed on the branches. 
Finally, we prove that the augmented data structure can be pruned back into a conflict-free UTXO Ledger in the presence of a conflict resolution mechanism.

\subsection{Related Work}

The benefits and drawbacks of the UTXO model have been discussed extensively, and several extensions of the UTXO model have been proposed. We refer to \cite{vademecum} for a excellent overview. However, we want to note that most of the variants concern either the extension of the UTXO model itself, e.g.,~\cite{cardanoEUTXO}, are proposed to increase their applicability towards smart contracts, or are designed to combine the UTXO and the account-based  model. 

From  a general point of view our approach is natural and was already successfully applied in various settings. It relies on the construction of  systems that allow to  work effectively and efficiently with inconsistent information and where ``context switching'' is a low-cost operation; e.g.~\cite{TMS}. We also want to note that this approach can be found in the field of belief revision. 


Finally, we want to draw some connections with the field of replicated invariant data types. The UTXO model, if distributed on multiple nodes, falls into the class of a replicated data types as the nodes can make concurrently changes to the data. Its append-only design and the invariant constraints render the operation of adding a transaction not commutable. This means that the order of the incoming transaction matters for the construction of the ledger. However, if there is a deterministic rule on how to process conflicts or a ``leader'' that pre-filters the transactions, this data structure can be turned into a conflict-free replicated data type (CRDT), e.g.,~see~\cite{CRDT}. The proposed Reality-based Ledger is already a CRDT without the need of a consensus mechanism since all operations on the involved data types are commutative.

In the context of replicated data structure, some works increase the performances in ``augmenting'' the data structure and distinguishing between different notions of consistency, e.g.,~\cite{redblue, automatingChoiceOfConsitency}. From a conceptual idea, this resembles our approach. However, the concrete proposals are distinct due to different assumptions on the communication model and field of applications. To our knowledge, our method is the first that allows a leaderless ``ex-post'' conflict resolution on these types of models. 

\subsection{Structure of the Paper}

The document is structured as follows. In Section \ref{sec: Standard UTXO} we provide an introduction to a standard conflict-free UTXO Ledger. In Section \ref{sec: graph-theoretical notions} we give an overview of some of the graph theoretical preliminaries used in this paper. In Section \ref{sec: Reality-based Ledger} we introduce the concept of a Reality-based Ledger and additional data structures that provide the necessary tools to manage this novel type of ledger. In Section \ref{sec: operations on the ledger} some of the core operations to maintain and access the ledger are presented.

We employ several graph structures to efficiently manage the Reality-based Ledger. Table~\ref{tab: graph overview} gives an overview of the utilised graphs. 

\begin{table}[b]
    \centering
    \begin{tabular}{c|c|c}
         Graph &  Vertices & Edges   \\   \hline\hline
         UTXO DAG  & in-, outputs, transaction IDs & spending relations \\
          Ledger DAG & transactions  & spending relations \\
         Conflict DAG & conflicts  &  conflict dependencies \\
         Conflict Graph & conflicts  &  conflict relations  \\
        Branch DAG  & branches  &  branch dependencies 
    \end{tabular}
    \caption{Overview of the graphs used in this paper.}
    \label{tab: graph overview}
\end{table}


\begin{figure}
    \centering
    \includegraphics[width=0.3\textwidth]{transaction-simplified3.png}
    \caption{Simplified transaction layout. The fund owner signs the transaction in the unlock blocks. Inputs are consumed and new outputs are created. The new outputs can be spent once the unlock conditions are satisfied.}
    \label{fig:transactionLayout}
\end{figure}

\begin{figure*}[t]
    \centering
    \includegraphics[width=0.8\textwidth]{AccountModel.png}
    \caption{Comparison between account- and UTXO-based model. }
    \label{fig:AccountModel}
\end{figure*}



\section{Conflict-Free UTXO Ledger}\label{sec: Standard UTXO}

In the standard UTXO model, transactions specify the outputs of previous transactions as inputs and create new outputs spending (or consuming) the inputs. 
Thus, a transaction consists of a list of inputs and a list of unique outputs. To every output, we associate a unique reference or output ID. Typically such an output ID is created with the involvement of a hash function.
\begin{remark}\label{rem: hash function}
A collision-resistant hash function is used to map data of arbitrary size to a fixed-size binary sequence, i.e., $\mathop{\mathrm{hash}}: \{0,1\}^*\to \{0,1\}^h$. Moreover, it is required that it is practicably impossible to find for a given sequence $x$ another sequence $x'$ such that $\mathop{\mathrm{hash}}(x) =\mathop{\mathrm{hash}}(x')$.
Throughout the remainder of the paper, we assume that a particular hash function is fixed and used by all participants.
\end{remark}
For example, the output ID could be created through the concatenation of the index of the output within the transaction and the hash of the transaction's content.
Every output represents a specific amount of the underlying cryptocurrency. The value of all inputs, i.e., spent outputs, must equal the value of all outputs of a transaction.
Every output can be spent only once and, hence, value is conserved overall.
With each output comes an unlock condition, which declares by whom and under which conditions it can be spent. With each input comes an unlock block containing a proof that the transaction issuer is allowed to spend the inputs and fulfills the unlock condition, e.g., a signature proving ownership of a given input's address. We refer to Figure~\ref{fig:transactionLayout} for a general transaction layout. In Section~\ref{sec:realities} we propose a more general description of this model. 

In this model, an account that is controlled by an entity holding the corresponding private / public key pair, is a collection of UTXOs that can be unlocked through the key pair. This type of book keeping of balances and transactions differs fundamentally from the account-based model, such as it is used in Ethereum \cite{buterin2013ethereum}. In the account-based model funds are represented as balances within accounts and transactions describe how these balances change, see Figure \ref{fig:AccountModel}. 

Let us define the UTXO Ledger model more formally. We follow the approach of~\cite{IOTASC}. Note that for the purpose of this work we consider a simplification of the UTXO models used in practice.
\begin{definition}[Output and input]
An \textit{output} is a pair of a value $v\in \mathbb{R}^+$ and an unlock condition $\mathrm{cond}$. We write $o=(v, \mathrm{cond})$ to denote the output. An \textit{input} $i$ is a reference to an output. In such a case, we say the input consumes the output. 
\end{definition}

\begin{definition}[Transaction]\label{def: transaction}
A transaction $x$ is a collection of inputs $\mathrm{in}(x),$ outputs $\mathrm{out}(x)$, and an unlock data $\mathrm{unlock}(x)$:
\begin{enumerate}[leftmargin=*]
    \item $\mathrm{in}(x)=(i_1,\ldots, i_n)$ is a list of inputs, i.e., references to outputs. We say that those outputs are \textit{consumed} or \textit{spent} by transaction $x$.
    \item $\mathrm{out}(x)=(o_1,\ldots, o_m)$ is a list of new outputs produced by transaction $x$.
    \item $\mathrm{unlock}(x)$ is a data which unlocks the inputs. This is usually done by cryptographic proof of authorization that ensures that the issuer of the transaction satisfies the condition $\mathrm{cond}$ of the consumed outputs.
\end{enumerate}
\end{definition}

\begin{definition}[Ledger]\label{def: ledger}
The \emph{ledger} is a set of transactions and denoted as $\mathcal{L}$. 
\end{definition}

\begin{definition}[Ledger state]\label{def: ledger state}
The \emph{ledger state}, written as $\mathrm{state}(\mathcal{L})$, is the set of all outputs that are not consumed by a transaction in the ledger $\mathcal{L}$. In other words, the ledger state is the set of outputs, for which no input exists that references them.
\end{definition}


The ledger progresses through the addition of new transactions. Furthermore, it is an append-only structure, i.e., transactions can only be added and not removed from the ledger.


In a distributed system, the append-only nature of this data structure makes it necessary that the operators of the distributed ledger have consensus on which transactions should be added to the ledger. In a blockchain setting, such as Bitcoin, this can be achieved by the selection of a leader who typically extends the longest chain. The longest chain then determines which transactions  are included in the ledger and in which order. 

To provide consistency there can be specific \emph{ledger constraints} which ought to be fulfilled before a certain  transaction $x$ can be added to the ledger $\mathcal{L}$. The ledger constraints are generally enforced by transaction validation rules applied prior to addition of the transaction to the ledger. We define $\mathrm{constr}(\mathcal{L},x)=1$ if all imposed constraints are satisfied by transaction $x$ and $\mathrm{constr}(\mathcal{L},x)=0$ otherwise. 
The constraints of a transaction being added to the ledger adhere typically to the following assumption:
\begin{ass}[Ledger constraints]\label{ass:constraints}
A transaction $x$ is added to the ledger $\mathcal{L}$ if it follows the following rules:
\begin{enumerate}[leftmargin=*]
    \item the transaction $x$ is syntactically correct;
    \item the sum of values of $\mathrm{in}(x)$ equals the sum of values of $\mathrm{out}(x)$;
    \item the unlocking data $\mathrm{unlock}(x)$ is valid;
    \item $\mathrm{in}(x)$ are references to existing unspent (not yet spent) outputs in the ledger state  $\mathrm{state}(\mathcal{L})$;
\end{enumerate}
\end{ass}

\begin{definition}[Consistent Ledger]\label{def: consistent ledger}
We say that the ledger  $\mathcal{L}$ is \emph{consistent} if and only if $\mathrm{constr}(\mathcal{L},x)=1$ for all $x\in \mathcal{L}$.
\end{definition} 

The UTXO Ledger starts at the so-called \emph{genesis} $\rho$, i.e., the transaction that is the ultimative predecessor of any transaction of the UTXO Ledger. The genesis transaction only contains outputs and no inputs. 
Each new transaction is an atomic update of the ledger and the ledger state. A transaction $x$ is added to a consistent ledger $\mathcal{L}$ if $\mathcal{L}\cup \{x\}$ is a consistent ledger or, equivalently, if $\mathrm{constr}(\mathcal{L}, x)=1.$
The above constraints or consistency rules imply that each output can be consumed by at most one transaction and thus a consistent ledger can not contain a so-called \textit{double spend}. 

An important property of the UTXO Ledger is that the validity of the state update (adding a new transaction) can be determined  by only using the context of the transaction itself, i.e., inputs, outputs, and unlock conditions. This allows a certain degree of parallelism and turns the UTXO Ledger into a partially ordered data structure. 


\begin{remark}\label{rem: invariant ledger}
We can talk about a ledger invariant $\mathbf{Invar}(\mathcal{L})$ which is preserved by each addition of a transaction to the ledger. In other words, $\mathbf{Invar}(\mathcal{L})=\mathbf{Invar}(\mathcal{L}')$ for any two consistent ledgers $\mathcal{L}$ and $\mathcal{L}'$.  The prime example is that the sum of the values of all unspent outputs in the ledger state remains constant.
\end{remark}














\iffalse

\section{System Model and Notation}

\note{ the concept of nodes and a network may not be  necessary. It is sufficient to assume an entity that receives transactions including conflicting ones. The latter is in contrast to the standard UTXO Ledger, where conflicts are selected out prior through the consensus mechanism.  }

\seb{We need to model nodes, and the distributed data structure, as well as information flow between the nodes, we might get inspired by \url{https://ieeexplore.ieee.org/document/910857}}


\seb{
The system that we consider consists of $N$ nodes executing adding new transactions to the distributed ledger (or global state) concurrently. If a node adds a new transaction it communicates this transaction to all the other nodes and that this transaction is eventually seen by any other nodes. This can be performed by standard procedures, as [gossip, causal broadcast TO BE DONE]. If a node issues a double spend it is not guaranteed that the eventual result is a consistent, i.e., that every node has the same perception of the ledger state. Note that such double spends can occur because of faulty nodes or malicious nodes.}
\fi

\section{Graph Theoretical Preliminaries}\label{sec: graph-theoretical notions}

In the section, we summarize basic graph theoretical notations and results that are used in the remaining part of the paper.

The set of integers between $1$ and $m$ is denoted by $[m]$. A \emph{graph} ${G}$ is a pair $(V,E)$, where $V$ denotes the set of vertices and $E$ denotes the set of edges. A graph is called \emph{directed} if every edge has its direction, e.g.,  for an edge $(u,v)$, the direction goes from $u$ to $v$. 

\begin{definition}[DAG]
A \emph{directed acyclic graph (DAG)} is a directed graph with no directed cycles, i.e.,  by following the directions of edges, we never form a closed loop.
\end{definition}


A vertex $v$ in a graph ${G}=(V,E)$ is called \textit{adjacent} to a vertex $u$ if $(u,v)\in E$. An edge $e\in E$ is said to be adjacent to a vertex $v\in V$ if $e$ contains $v$. The \textit{out-degree} and \textit{in-degree} of a vertex $v$ in a directed graph $G=(V,E)$ is the number of adjacent edges of the form $(v,u)$ and, respectively, $(u,v)$. A vertex in a graph is called \textit{isolated} if there is no edge adjacent to it.
\begin{definition}[Neighbours in a graph]~\label{def: neighbours in graph}
Let ${G}=(V,E)$ be a graph. For a vertex $v\in V$, define the \emph{set of neighbours} (or ${G}$-neighbours), written as $N_{{V}}(v)$\footnote{In the remainder of the paper, we will often identify the graph with its vertex set, since for a given set of vertices $V$, we will have only one DAG $D=(V,E)$. Thereby, the set of neighbours $N_{{V}}(v)$ and other concepts that use $V$ as a subscript will be clear from the context.}, to be the vertices adjacent to $v$. 
\end{definition}
\begin{definition}[Parents, children and leaves in a DAG]
Let ${D}=(V,E)$ be a DAG. For a vertex $v\in V$, define the set of \emph{parents}, written as $\parent{V}{v}$, to be the set of vertices $u\in V$ such that $(v,u)\in E$. Similarly, we define the set of \emph{children}, written as $\child{V}{v}$, to be the set of vertices $u\in V$ such that $(u,v)\in E$. A vertex $v\in V$ with in-degree zero is called a \emph{leaf}. 
\end{definition}

\begin{definition}[Partial order induced by a DAG]
Let ${D}=(V,E)$ be a DAG. We write $u\le_{{V}} v$  for some $u,v\in V$ if and only if there exists a directed path from $u$ to $v$, i.e., there are some vertices $w_0=u,w_1,\ldots,w_{s-1},w_s=v$ such that  $(w_{i-1},w_{i})\in E$ for all $i\in[s]$.  Furthermore, we write $u<_{{V}}v$ if $u\le_{{V}} v$ and $x\neq v$.
\end{definition}
Note there could be different DAGs producing the same partial order. The DAG with the fewest number of edges that gives the partial order $\le_{{V}}$ is usually called the \emph{transitive reduction} of ${D}$ or the \emph{Hasse diagram} of $\le_{{V}}$. In the following definition, we give a more general definition of the minimal subDAG of ${D}=(V,E)$ induced by a set of vertices $S\subseteq V$ which coincides with the transitive reduction of ${D}$ when $S=V$. 

\begin{definition}[Minimal subDAG induced by a set of vertices]\label{def: minimal subDAG}
Let ${D}=(V,E)$ be a DAG.  For a subset of vertices $S\subseteq V$, we define the \emph{minimal subDAG} of ${D}$ induced by $S$ to be the DAG ${D'}=(V',E')$ whose vertex set is $V'=S$ and there is an edge $(v,u)\in E'$ if and only if $u,v\in S$, $v<_{{V}}u$ and there is no $w\in S\setminus \{u,v\}$ such that $v<_{{V}} w <_{{V}}u$. 
\end{definition}
  

\begin{definition}[Maximal and minimal elements]\label{def: min and max elements} Let ${D}=(V,E)$ be a DAG and let $\le_{{V}}$ be the partial order induced by ${D}$. For a subset of vertices $S\subseteq V$,  an element $u\in S$ is called \emph{${D}$-maximal} (\emph{${D}$-minimal}) in $S$ if there is no $v\in S\setminus\{u\}$ such that $u\le_{{V}}  v$ ($v\le_{{V}}  u$). Define $\maximal{V}{S}$ and $\minimal{V}{S}$ to be the set of ${D}$-maximal and, respectively, ${D}$-minimal elements in $S$.
\end{definition}

\begin{remark}
The maximal (minimal) elements of a DAG $D$ are also called the geneses (tips) of $D$. Usually, we consider DAGs with only one genesis, whereas the number of tips can be large. 
\end{remark}

\begin{definition}[Future and past cones] \label{def: future and past cones}
Let ${D}=(V,E)$ be a DAG. For $x\in V$, define the \emph{past cone} of $x$ in ${D}$, written as $\cone{p}{V}{x}$ 
to be the set of all vertices $y\in V$ such that $x\le_{{V}} y$. Similarly, define the \emph{future cone} of $x$ in ${D}$, written as $\cone{f}{V}{x}$ 
to be the set of all vertices $y\in V$ such that $y\le_{{V}} x$. 
\end{definition}

\begin{definition}[Future-closed and past-closed sets]\label{def: future and past closed}
Let ${D}=(V,E)$ be a DAG. A subset $S\subset V$ is called \emph{${D}$-past-closed} if and only if for every $u\in S$, the past cone $\cone{p}{{V}}{u}$ is contained in $S$. 
Similarly, a subset $S\subset V$ is called \emph{${D}$-future-closed} if and only if for every $u\in S$, the future cone $\cone{f}{{V}}{u}$  is contained in $S$. 
\end{definition}

We conclude with a definition of maximal independent sets for general graphs.

\begin{definition}[Maximal Independent Set]\label{def: maximal independent set}
Let ${G}=(V,E)$ be a finite graph. A subset $S\subset V$ is an \emph{independent set} if and only if for every two vertices $u,v \in S$  there is no edge connecting the two, i.e., $(u,v)\notin E$. An independent set $S$ is called a \emph{maximal independent set} if and only if there is no other independent set $S'$ such that  $S\subsetneq S'$.
\end{definition}




\section{Reality-based Ledger}\label{sec: Reality-based Ledger}


In Section \ref{sec: Standard UTXO} we described the model of a conflict-free UTXO Ledger that is suitable for an environment where transactions are pre-filtered by a consensus mechanism. Since that ledger was conflict-free a valid ledger state could be readily extracted, see Definition~\ref{def: ledger state}.

To alleviate the restriction of requiring a conflict-free data structure, we propose an augmented version of the standard conflict-free UTXO Ledger model that allows more than one output spend. The ledger $\mathcal{L}$ continues to be defined by Definition~\ref{def: ledger}, however, the total set of transactions must not be conflict-free. We will derive a concept, called a \textit{reality}, which allows to reduce $\mathcal{L}$ to a subset of transactions that yield a valid (\textit{Reality-based}) Ledger state, see also Definition~\ref{def: ledger state}.


The purpose of the augmentation is to identify and track possible conflicting transactions. We add this information to each transaction and output. For a given transaction we may set an additional flag or \textit{label} $\mathrm{label}$.

Let us highlight that the transaction layout itself does not change and $\mathrm{label}$ is assigned a value only if needed.
We can therefore think of an output as a triplet of a value $v$, an unlock condition $\mathrm{cond}$, and a  label $\mathrm{label}$, i.e., $o=(v, \mathrm{cond}, \mathrm{label})$. Let us now define what we mean by conflicts.  

\begin{definition}[Conflicts]\label{def:conflicts}
A transaction $x\in \mathcal{L}$ is called a \textit{conflict} if and only if there exists a transaction $y\in \mathcal{L}\setminus\{x\}$ such that $x$ and $y$ contain at least one same input. The set of all conflicts is denoted by $\mathcal{C}$ and dubbed the \emph{conflict set} of the ledger $\mathcal{L}$.
\end{definition}

{\noindent We can now define how we set the label  $\mathrm{label}$:}
\begin{enumerate}[leftmargin=*]
    \item if a transaction $x$ is not a conflict, the label is not set;
    \item otherwise the label is set to a generic unique reference to the transaction, e.g., the transaction ID. 
\end{enumerate}
{\noindent More formally we define the label as follows.}

\begin{definition}[Label]\label{def:label}
We define $\bot$  to be the label of the  genesis $\rho$. 
Let $\mathcal{Y}$ be a label space such that $\bot\in\mathcal{Y}$, and $\mathrm{label}: \mathcal{L} \to \mathcal{Y}$ be a function with the following properties:
\begin{enumerate}[leftmargin=*]
  
   \item if $x \in \mathcal{L} \setminus \{ \mathcal{C}\}$, then $\mathrm{label}(x)=\bot$;
    \item the restriction of the function $\mathrm{label}$ on the set $\mathcal{C}\cup \{\rho\}$ is injective, i.e., the image  $\mathrm{label}(\mathcal{C}\cup \{\rho\}):=\{\mathrm{label}(x): x\in \mathcal{C}\cup \{\rho\}\}$ has size $|\mathcal{C}|+1$.  
\end{enumerate} 
\end{definition}
\begin{remark}
One natural choice to set a unique (with high probability) label function is to utilize a hash function $\mathop{\mathrm{hash}}(\cdot):  \{0,1\}^*\to \{0,1\}^h$ (cf. Remark~\ref{rem: hash function}) for large enough $h$. Then the label set $\mathcal{Y}$ is $\{0,1\}^h \cup \bot$.
\end{remark}

In the presence of this label, we can remove the forth constraint from the ledger, see Assumption~\ref{ass:constraints}. However, to avoid that the data structure becomes ``meaningless'' we still need a notion of ``consistency'' as we will see in Assumption~\ref{ass:constraints2}, and a mechanism  to track the dependencies of the conflicts. 


The next part of this section  defines several data structures that can be derived from the UTXO inter-dependencies. These structures are used to track conflicting transactions without the need for consensus. More precisely, in Section~\ref{sec: Standard UTXODAG} we will explain how the UTXO transactions and their in- and outputs result in a DAG structure. In Section~\ref{sec:conflictGraph} we present how we can use the UTXO data structure to manage the conflicting transactions efficiently. 

In Section~\ref{sec:conflictDAGconflictGraph} the information contained in the UTXO DAG is split into the Conflict Graph, which keeps track of the conflicting transactions, and the Conflict DAG, which describes the inherited dependencies of conflicts. Finally, in Section~\ref{sec:branchDAG} branches are introduced, which form a possible non-conflicting state of the ledger. Combining non-conflicting branches can create maximally independent sets of conflicts called realities. Each  reality can be associated to a consistent ledger, see Theorem \ref{thm:Rledger}.


\subsection{UTXO and Ledger DAGs }\label{sec: Standard UTXODAG}
We introduced the concept of UTXO and defined UTXO based transactions as an operation spending inputs and creating outputs in Section~\ref{sec: Standard UTXO}.
The inputs and outputs in one transaction are ``atomic'' in the sense that either all inputs are consumed and all outputs are created or the transaction is not added to the ledger at all. The atomic nature of a transaction is represented by a unique transaction ID. In our graphical representation, these dependencies are expressed  using an additional vertex identified with the corresponding transaction ID, see Figure~\ref{fig: UTXO DAG}. 


The collection of all transactions since genesis, i.e., the ledger $\mathcal{L}$,
provides the content for a DAG, which we call the UTXO DAG.
\begin{definition}[UTXO DAG]\label{def: UTXO DAG}
The vertex set of the UTXO DAG 
consists of all in- and outputs and all transaction IDs.  The interrelations between these form the set of directed edges. More specifically, directed edges exist from inputs to outputs, from the transaction ID to its inputs, and from the outputs to the ID of the transaction creating these outputs. We allow here to appear inputs several times as vertices, turning the vertex set formally into a multi-set. This allows to track possible double spends.
\end{definition}
\begin{example}
For a simplified illustration of an example for such a DAG see Figure~\ref{fig: UTXO DAG}. The depicted UTXO DAG contains five transactions.
\end{example} 
\begin{definition}[Ledger DAG]\label{def: ledgerDAG}
We define the Ledger DAG $D_{\ledger}$ to be a DAG whose vertex set is the ledger $\mathcal{L}$. There is a directed edge $(x,y)$ in the edge set of  $D_{\ledger}$ if and only if an input of $x$ references an output of $y$.
\end{definition}

\begin{remark}
The results derived in this paper are in respect to the Ledger DAG. However, due to the atomic nature of transactions the results also apply for the UTXO DAG.
\end{remark}

\begin{figure}
    \centering
    \includegraphics[width=0.8\textwidth]{UTXODAG.png}
    \caption{Atomic UTXO abstraction of a transaction and an example of a UTXO DAG. }
    \label{fig: UTXO DAG}
\end{figure}


Equipped with the notion from Section~\ref{sec: graph-theoretical notions},  we write $\le_{\mathcal{L}}$ to denote the partial order on the ledger $\mathcal{L}$ induced by $D_{\ledger}$. In other words,  $y\le_{\mathcal{L}} x$ if transaction $y$ spends (indirectly) from $x$. Note that the genesis $\rho$ is the only $D_{\ledger}$-maximal element in $\mathcal{L}$. Further, we write 
$\cone{p}{\mathcal{L}}{x}$ to denote the Ledger past cone and  
$\cone{f}{\mathcal{L}}{x}$ to denote the Ledger future cone.

As a typical rule in a DLT with a UTXO model, an output can only be spent once. Thus, if there are multiple transactions that attempt to spend the same output, it is the role of the consensus mechanism to select at most one transaction that is allowed to consume the output. 
Once some consensus mechanism decided on which conflicts to keep and which to reject, we can reduce or prune the augmented ledger as described in Section \ref{sec:ConflictPruning}.




\subsection{Conflict Graph}\label{sec:conflictGraph}

In Definition~\ref{def:conflicts} we introduced the notion of conflicts. Due to the causal dependency of ordered transactions, transactions can be conflicting even if they do not consume the same output.

\begin{definition}[Conflicting transactions]\label{def:conflictingTx}
Two distinct transactions $x,y\in \mathcal{L}$ are \emph{directly conflicting} if they have at least one input in common. 
Two distinct transactions $x_1,y_1\in \mathcal{L}$ are said to be \emph{indirectly} conflicting  if there exist distinct $x_2,y_2\in \mathcal{L}$ with either $x_1 <_{\mathcal{L}} x_2$ and $y_1\le_{\mathcal{L}} y_2$ or $x_1 \le_{\mathcal{L}} x_2$ and $y_1<_{\mathcal{L}} y_2$ such that $x_2$ and $y_2$ are directly conflicting. Two transactions are said to be \emph{conflicting} if they are directly or indirectly conflicting.
\end{definition}

\begin{remark}\label{rem: conflicting transaction are not conflicts}
Note that due to Definition~\ref{def:conflicts} some (or possibly the majority of) conflicting transactions are not necessarily conflicts. On the other hand, if two transactions are directly conflicting, then they are conflicts.
\end{remark}


\begin{definition}[Conflict-free set and conflicting sets]\label{def: conflicting sets}
A subset of transactions $S\subseteq \mathcal{L}$ is called \textit{conflict-free} if it does not contain any two  conflicting transactions. We also say that $S_1\subseteq \mathcal{L}$ is \textit{conflict-free with respect to} $S_2\subseteq \mathcal{L}$ if there is no $c_1\in S_1$ and $c_2\in S_2$ such that $c_1$ and $c_2$ are conflicting. Alternatively, $S_1$ is \textit{conflicting} with $S_2$ if $S_1$ is not conflict-free with respect to $S_2$.
\end{definition}
By Remark~\ref{rem: conflicting transaction are not conflicts}, conflicting transactions are not necessarily conflicts. However, the $D_{\ledger}$-maximal transactions that are conflicting with a given transaction have to be conflicts as described below. 

\begin{proposition}\label{prop: conflicting transactions}
For a transaction $x\in \mathcal{L}$, define $C=C(x)$ to be the set of   transactions that are conflicting with $x$. Then $C$ is $D_{\ledger}$-future-closed and it holds that 
$\maximal{\mathcal{L}}{C}\subseteq \mathcal{C}$.
\end{proposition}

\begin{proof}
By Definition~\ref{def:conflictingTx}, if $x$ is conflicting with a transaction $y\in \mathcal{L}$, then $x$ is conflicting with $z$, where $z$ is any transaction $z\in \mathcal{L}$ such that $z\le_{\mathcal{L}} y$. Thus, the set $C$ has to be $D_{\ledger}$-future-closed. Let $u\in \maximal{\mathcal{L}}{C}$. By definition of conflicting transactions, there exists some $x'$ and $u'$ such that $x\le_{\mathcal{L}} x'$, $u\le_{\mathcal{L}} u'$ and $x'$ and $u'$ are directly conflicting. Then by Definitions~\ref{def:conflicts} and~\ref{def:conflictingTx}, $u'\in \mathcal{C}$. Note that $u'$ and $x$ are conflicting and, thus, $u'\in C$. Since $u\le_{\mathcal{L}} u'$ and $u'\in \maximal{\mathcal{L}}{C}$, we conclude that $u=u'\in \mathcal{C}$.
\end{proof}

The set of relations between conflicts can be described with the notion of a Conflict Graph.

\begin{definition}[Conflict Graph]\label{def: Conflict Graph}
The \emph{Conflict Graph} $G_{\conflictset}$ has vertex set $\mathcal{C}$.  Two vertices in $G_{\conflictset}$ are connected by an undirected edge if and only if the corresponding two conflicts are conflicting. 
\end{definition}

\begin{example}
We refer the reader to Figure~\ref{fig:conflicts} for an illustration of conflicts and the Conflict Graph. On the left part of the figure, we depict a UTXO DAG, where by coloring the box of a transaction, we indicate whether the transaction is a conflict. For instance, it can be seen that the orange transaction is directly conflicting with the red transaction, whereas the blue transaction is indirectly conflicting with the purple transaction. The relations between conflicts are demonstrated with the help of the corresponding Conflict Graph which is depicted on the right part of the figure.
\end{example}


\begin{figure}[t]
\centering
    \includegraphics[width=0.8\textwidth]{conflicts2.png}
    \caption{The UTXO DAG representation and the Conflict Graph} 
    \label{fig:conflicts}
\end{figure}

In contrast to the standard UTXO model, where no conflicts are allowed, they can be present in our generalization. We, however, require any two  conflicting transactions to be not comparable by the partial order $\le_{\mathcal{L}}$. The constraints in Assumption \ref{ass:constraints} about the addition of a transaction are relaxed:
\begin{ass}[Reality-based Ledger constraints]\label{ass:constraints2}
A transaction $x$ is added to the ledger $\mathcal{L}$ if it follows the following rules:
\begin{enumerate}[leftmargin=*]
    \item the transaction $x$ is syntactically correct;
    \item the sum of values of the inputs equals the sum of values of the outputs;
    \item the unlocking data $\mathrm{unlock}(x)$ is valid;
    \item $\mathrm{in}(x)$ are references to outputs which are not already consumed in $\cone{p}{\mathcal{L}}{x} \setminus \{ x\}$
\end{enumerate}
\end{ass}

\begin{remark}[Conflict-free past cone]\label{rem:conflictFree}
A  consequence of the $4$th point in Assumption~\ref{ass:constraints2} is that all past cones are conflict-free. In other words, we have that for every transaction $x\in\mathcal{L}$,  $\cone{p}{\mathcal{L}}{x}$  does not contain any pair of two conflicting transactions.
\end{remark}

\subsection{Labeled UTXO and Ledger DAGs and Conflict DAG}\label{sec:conflictDAGconflictGraph}

The existence of conflicts in the Ledger DAG plays a crucial role, as they eventually need to be resolved. In the following, we extract the necessary information for conflict resolution from the Ledger DAG. To this end, we labeled the transactions, see Definition~\ref{def:label}. We add this labeling to our UTXO and Ledger DAGs to keep  track of the conflicts and their dependencies.

\begin{figure*}[h!]
    \centering
    \includegraphics[width=.8 \textwidth]{DAGtransition.png}
    \caption{Derivation of the various graphs from the labeled UTXO DAG and the resulting realities (leaves of the Branch DAG). The colors represent the different labels of the conflicts. }
    \label{fig:DAGtransition}
\end{figure*}


\begin{definition}[Labeled UTXO and Ledger DAGs]
The \emph{labeled UTXO and Ledger DAGs} are the UTXO and Ledger DAGs with the  additional labels as described in Definition~\ref{def:label}.
\end{definition}

\begin{example} 
For an illustration of a labeled Ledger DAG, we refer the reader to Figures~\ref{fig:conflicts} and~\ref{fig:DAGtransition}. Note that the different colors correspond to the different labels in these figures. 
\end{example}
Now we define the restriction of the labeled Ledger DAG to the conflict set and the genesis using  Definition~\ref{def: minimal subDAG}.

\begin{definition}[Conflict DAG] \label{def: Conflict DAG}
The \emph{Conflict DAG}, written as $D_{\conflictset}$, is defined as the minimal subDAG of $D_{\ledger}$ induced by the set of vertices $\mathcal{C}\cup \{\rho\}$. 
\end{definition}

\begin{example}
For a more visual explanation of the above concept, we depict Figure~\ref{fig:DAGtransition}. Specifically, we demonstrate a UTXO DAG on the left part of the figure and the corresponding Conflict DAG in the middle. We note that the purple transaction in the Conflict DAG is not connected by an edge with the white one since there is a path connecting them which goes through the yellow transaction.
\end{example}
\begin{remark}
We observe that the Conflict DAG and the Conflict Graph represent only some partial information about the labeled UTXO DAG. Specifically, they are used to demonstrate different relations between the conflicts. Note that in general, it is not possible to construct the Conflict DAG using only the Conflict Graph and vice versa.
\end{remark}

Using the notion from Section~\ref{sec: graph-theoretical notions}, we denote the partial order on the set $\mathcal{C}$ induced by $D_{\conflictset}$ by $\le_{\mathcal{C}}$. The past and future cones of a conflict $x\in\mathcal{C}$ in the Conflict DAG are written as  $\cone{p}{\mathcal{C}}{x}$ and $\cone{f}{\mathcal{C}}{x}$, respectively. Finally, we give an observation saying that if a transaction is conflicting with some subset of conflicts $S$ (see Definition~\ref{def: conflicting sets}), it is possible to find a $D_{\conflictset}$-minimal conflict in $S$ which is conflicting with that transaction.

\begin{proposition}[Transaction conflicting with a set]\label{prop: only minimal elements in branch}
Let a subset of conflicts $S\subseteq \mathcal{C}$ be conflicting with a transaction $x\in \mathcal{L}$. Then there exists $c\in\min_{\mathcal{C}}(S)$ such that $x$ and $c$ are conflicting.
\end{proposition} 

 \begin{proof}
By Definition~\ref{def: conflicting sets}, there exists some $y\in S$ such that $y$ and $x$ are directly or indirectly conflicting. From Definition~\ref{def: min and max elements}, it follows that there exists some $c\in\min_{\mathcal{C}}(S)$  such that $c\le_{\mathcal{C}} y$. Then by Definition~\ref{def:conflictingTx}, we conclude that $c$ is  conflicting with $x$.
 \end{proof}


\subsection{Branches and Branch DAG}\label{sec:branchDAG}

This section introduces the concepts of branches and Branch DAG, which help to handle the conflicting transactions. 



\begin{definition}[Branch and set of branches]\label{def:branch}
A set of conflicts ${B}\subseteq \mathcal{C}$ is called a \emph{branch} if and only if the two properties hold:
\begin{enumerate}[leftmargin=*]
    \item ${B}$ is conflict-free (cf. Definition~\ref{def: conflicting sets});
    \item ${B}$ is $D_{\conflictset}$-past-closed (cf. Definition~\ref{def: future and past closed}).
\end{enumerate}
Define $\mathcal{B}$ to be the set of all branches, including  the so-called \emph{main branch} which represents the empty set.
\end{definition}
Note that by Assumption~\ref{rem:conflictFree}, for any conflict $x\in \mathcal{C}$, the past cone $\cone{p}{\mathcal{C}}{x}$ is a branch. In the following statement we discuss a sufficient condition for the union of branches to be a branch.

\begin{lemma}\label{lem:aggregateBranch}
Let ${B}_1,\dots,{B}_n\in \mathcal{B}$ be branches such that there exists a branch $A\in\mathcal{B}$ with ${B}_1,\dots,{B}_n\subseteq A$ . Then, the union  
\[{B}_1\cup\cdots\cup {B}_n\]
is also a branch, called the \emph{aggregate} branch of  ${B}_1,\dots,{B}_n$. 
\end{lemma}
\begin{proof}
Since, every ${B}_i$ is $D_{\conflictset}$-past-closed, the union ${B}_1\cup\cdots\cup{B}_n$ is also $D_{\conflictset}$-past-closed.  Since $ A$ contains no conflicting pairs, the union of  must not either.
\end{proof}

We proceed with a crucial observation saying that each branch can be represented as the aggregated branch of certain past cones.
\begin{lemma}[Aggregated branch]\label{lem: each branch is aggregate} 
Every branch ${B}$ can be uniquely written as the aggregated branch
$$
{B}= \cone{p}{\mathcal{C}}{c_1} \cup \cdots \cup  \cone{p}{\mathcal{C}}{c_n},
$$
where conflicts $c_1,\ldots,c_n$ are the $D_{\conflictset}$-minimal elements in ${B}$. 
\end{lemma}

\begin{proof}
The branch  ${B}$ is finite. Hence, there exist unique  $D_{\conflictset}$-minimal conflicts $c_1,\dots,c_n$ in ${B}$, i.e., for any $c_i$ and any other conflict $d\in {B}$, either it holds that $c_i\le_\mathcal{C} d$ or $d$ and $c_i$ are not comparable by the partial order.  Since ${B}$ contains the past cone of all its conflicts, it follows that ${B}$ is the aggregated branch of the branches $\cone{p}{\mathcal{C}}{c_i}$. 
\iffalse
To prove the uniqueness, toward a contradiction assume
 $$
 {B}=  \cone{p}{\mathcal{C}}{d_1} \cup \cdots \cup  \cone{p}{\mathcal{C}}{d_m}
 $$
 is another decomposition with incomparable conflicts $d_1,\ldots,d_m$. Then each $c_i$ is included in some $ \cone{p}{\mathcal{C}}{d_j}$. By the minimality of $c_i$,  we conclude that $c_i=d_j$.  After reordering, we can assume that $c_i=d_i$ for each $1\leq i\leq \min(n,m)$.  Suppose that $m>n$.  Then $d_{n+1}$ must be greater than or equal to  some minimal conflict of ${B}$, say, $c_{i}\le_\mathcal{C} d_{n+1}$.  But this is a contradiction since the $d_1,\ldots, d_m$ are assumed to be incomparable.  Now consider the case $m<n$. Then $c_{m+1}$ is not included to any of the branches $ \cone{p}{\mathcal{C}}{d_1} ,\ldots, \cone{p}{\mathcal{C}}{d_m} $. Thus, it holds $m=n$ which completes the proof.
 \fi
\end{proof}
\begin{remark}
Lemma~\ref{lem: each branch is aggregate} has some fundamental consequences for how we can implement the branches into the protocol. For instance, if a branch ${B}$ has a unique decomposition into 
 $$
{B}= \cone{p}{\mathcal{C}}{c_1} \cup \cdots \cup  \cone{p}{\mathcal{C}}{c_n},
 $$
 then we can set the branch ID of ${B}$ to be the hash of the  concatenation of the transaction IDs of the $c_i$'s (ordered in a canonical way).  Then, the branch ID of a branch of the form $\cone{p}{\mathcal{C}}{c}$ with $c\in\mathcal{C}$ is the same as the hash of the conflict $c$.  

 \end{remark}


A branch ${B}_1$ is called a \emph{subbranch} of branch ${B}_2$ if ${B}_1\subseteq {B}_2$. Lemma~\ref{lem: each branch is aggregate} already shows the recursive structure of the branches. 
This recursive structure can be encoded in the Branch DAG.


\begin{definition}[Branch DAG]\label{def:branchDAG}
Ordered by inclusion, $\mathcal{B}$ is a partially ordered set 
and defines a DAG. 
 Specifically, we put a directed edge from a branch $A$ to a branch $B$ if $A = {B}\cup c$ for some conflict $c\in \mathcal{C} \setminus {B}$. The corresponding DAG is called the \emph{Branch DAG} and denoted by $\mathcal{DAG}_{\textrm{\tiny{Branch}}}$.
\end{definition}

\begin{remark}\label{rem: complexity of Branch DAG}
We show an example of a Branch DAG in Figure~\ref{fig:DAGtransition}. In this example, the number of vertices in the Branch DAG is nine  which is larger than six, the number of conflicts. We note that in general, the number of vertices in a Branch DAG can be exponentially large in the number of conflicts. For instance, if there exist $t$ pairs of directly conflicting transactions such that any two transactions from different pairs are not conflicting, then the number of vertices in the Branch DAG is lower bounded by $2^t$.
\end{remark}

Applying the notion from Section~\ref{sec: graph-theoretical notions}, we denote the partial order on the set $\mathcal{B}$ induced by $\mathcal{DAG}_{\textrm{\tiny{Branch}}}$ by $\le_{\mathcal{B}}$; the set of parents and children of branch $B\in\mathcal{B}$ is written as $\parent{\mathcal{B}}{B}$ and $\child{\mathcal{B}}{B}$.

\iffalse
Now we turn to prove a structural statement concerning the future cone of a conflict.
\begin{lemma}\label{lem:downward}
Let $c\in \mathcal{C}$ be a conflict. Then, the future cone of~$c$  in the Conflict DAG can be uniquely decomposed as
\[
    \cone{f}{\mathcal{C}}{c} = c \,\cup  \cone{f}{\mathcal{C}}{d_1} \cup \cdots \cup  \cone{f}{\mathcal{C}}{d_n} ,
\]
 where each $d_i\in\mathcal{C}$ is a conflict and $d_1,\dots,d_n$ are pairwise incomparable with respect to the partial order $\leq_{\mathcal{C}}$. 
\end{lemma}
\begin{proof}
 Let $\{d_1,\ldots,d_n\}$ be the set of children of $c$ in $D_{\conflictset}$. Clearly, they are pairwise incomparable and the required decomposition holds. We also note that  $d_1,\ldots,d_n$ can be equivalently defined as the second largest elements in $\cone{f}{\mathcal{C}}{c}$. In other words,  for any $i\in[n]$ and any $e\in\cone{f}{\mathcal{C}}{c} \setminus\{c\}$, either $e\le_\mathcal{C} d_i$ or $e$ and $d_i$ are incomparable.  We prove the uniqueness of the decomposition by contradiction. We assume the existence of another representation
 $$
    \cone{f}{\mathcal{C}}{c} = c \,\cup  \cone{f}{\mathcal{C}}{e_1} \cup \cdots \cup  \cone{f}{\mathcal{C}}{e_m}
 $$
 with $e_1,\ldots,e_{m}$ being incomparable.
 Then each $d_i$ should belong to some $\cone{f}{\mathcal{C}}{e_j}$. Since $d_i$ is the second largest element in $\cone{f}{\mathcal{C}}{c}$, we conclude that $d_i=e_j$. Thus, after rearranging, we can assume that $e_i=d_i$ for all $1\le i \le \min(m,n)$. If $m<n$, then $d_{m+1}$ must be included to some $d_i$ with $i\le m$ which contradicts the fact that all $d_i$'s are pairwise incomparable. If $m>n$, then $e_{n+1}$ must be smaller than or equal to some second largest element in $\cone{f}{\mathcal{C}}{c}$, say, $e_{n+1}\le_\mathcal{C} d_i$. But this is a contradiction since $e_1,\ldots,e_{m}$ are assumed to be incomparable. Thus, $m=n$ which completes the proof.
\end{proof}
\fi
Conflicting transactions owe the existence of their conflict state to the presence of conflicts in their Ledger past cone. Since conflicts are labelled transactions, we can define a function that extracts all labels in this past cone. 
\begin{definition}[Maximal contained label set]\label{def:label set}
Let $\mathcal{Y}$ be the label space, and $\mathrm{label}^{(p)}: \mathcal{L} \to 2^\mathcal{Y}$ be a function that for a given transaction $x\in \mathcal{L}$ returns all labels of the transactions in its Ledger past cone i.e., $\mathrm{label}^{(p)}(x)=\{\mathrm{label}(y): y\in \cone{p}{\mathcal{L}}{x}\}$. 
\end{definition}


\begin{remark} \label{rem: how to update the set of labels}
Practically this operation can be performed, e.g., through a graph search algorithm applied to the Ledger DAG (more computational intensive), or through a transaction-by-transaction record of conflict dependencies (more memory expensive). On one hand, for a given transaction $x$ we can identify all transactions with labels in the past cone $\cone{p}{\mathcal{L}}{x}$ by traversing the graph by means of  depth-first search. We can discontinue to search deeper than certain elements by cross-checking with the conflict set.  On the other hand, we can  inherit the maximal contained label set for a new arriving transaction from its parents and if a new conflict with $x$ is created, we traverse the future cone $\cone{f}{\mathcal{L}}{x}$ and update the maximal contained label set for all transactions there. 
\end{remark}


We can also define an equivalent function to obtain branch dependencies.
\begin{definition}[Maximal contained branch]
Let $\mathcal{B}$ be the set of all branches, and $\mathrm{branch}^{(p)}_{\mathcal{L}}: \mathcal{L} \to \mathcal{B}$ be a function that for a given transaction $x\in \mathcal{L}$ returns the maximal branch contained in $\cone{p}{\mathcal{L}}{x}$. 
\end{definition}
We note that there could not be two maximal branches in the Ledger past cone of a transaction (which is conflict-free) since, otherwise, we could consider their aggregate branch.
The above two definitions have the following correlation.
\begin{lemma}
The maximal contained label set of a transaction $x$ translates to the maximal branch that is contained in the past cone $\cone{p}{\mathcal{L}}{x}$. More precisely, we have that \[\mathrm{label}^{(p)} (x)\setminus\{\bot\} =  \bigcup_{c \in \mathrm{branch}^{(p)}_{\mathcal{L}} (x)}  \mathrm{label}(c).\]
\end{lemma}

\begin{proof}
By definition, $\mathrm{label}^{(p)}(x)=\{\mathrm{label}(y): y\in \cone{p}{\mathcal{L}}{x}\}$. The branch $\mathrm{branch}^{(p)}_{\mathcal{L}} (x)$ is included to $\cone{p}{\mathcal{L}}{x}$ and $\bot$ is not a label for any conflict by Definition~\ref{def:label}. This implies that 
$$
\bigcup_{c \in \mathrm{branch}^{(p)}_{\mathcal{L}} (x)}  \mathrm{label}(c) \subseteq \mathrm{label}^{(p)} (x) \setminus \{\bot\}. 
$$
Toward a contradiction, assume that the equality in the above formula does not hold, i.e., there exists some label $\ell\in \mathcal{Y}$ which is not present in the left-hand side. Consider the unique conflict $y\in \cone{p}{\mathcal{L}}{x}$ such that $\mathrm{label}(y)=\ell$. We shall prove that this conflict should be included to the maximal contained branch. Indeed, the union $\cone{p}{\mathcal{C}}{y}\cup \mathrm{branch}^{(p)}_{\mathcal{L}}(x)$ is $D_{\conflictset}$-past-closed and is conflict-free as included to $\cone{p}{\mathcal{L}}{x}$. It follows that $y\in \mathrm{branch}^{(p)}_{\mathcal{L}}(x)$ and $\ell$ is present in the left-hand side of the displayed equation, which contradicts the assumption.
\end{proof}

\subsection{Realities in the  Branch DAG
}\label{sec:realities}
In this section, we discuss maximal aggregated branches.
They are branches that present maximal acceptable valid versions of the ledger.

\begin{definition}[Maximal branch and reality]\label{def: reality}
A branch ${B}\in\mathcal{B}$ is \emph{maximal} if there exists no other branch $A\in\mathcal{B}$ such that  ${B}\subset A$. A maximal branch is called a \textit{reality}.
\end{definition}
Note that a reality always contains the main branch by definition since the empty set is included to all branches. An immediate consequence of the above definition is the following lemma.
\begin{lemma}\label{lem:realityLeaf}
The set of realities equals the set of leaves in the Branch DAG.
\end{lemma}
\begin{example}
Following the example depicted in Figure~\ref{fig:DAGtransition}, we observe that there are exactly four realities or leaves in the Branch DAG.
\end{example}

The following statement shows a link between realities and maximal independent sets in the Conflict Graph.
\begin{proposition}\label{prop:maximalIndReality}
There is a one-to-one correspondence between maximal independent sets of the Conflict Graph and realities.
\end{proposition}
\begin{proof}
 Let $I=\{c_1, \ldots, c_n \} \subseteq \mathcal{C}$ be a maximal independent set in the Conflict Graph. We define the set  ${B}$ as follows
$$
     {B} := {B} (c_1, \ldots, c_n) :=  \cone{p}{\mathcal{C}}{c_1} \cup \cdots \cup  \cone{p}{\mathcal{C}}{c_n}.
$$
Since each past cone is $D_{\conflictset}$-past-closed, the union is either. Assume that ${B}$ contains a conflicting pair of transactions, say $d$ and $e$. There must exist conflicts $c_i$ and $c_j$ such that $d \in \cone{p}{\mathcal{C}}{c_i}$ and $e \in \cone{p}{\mathcal{C}}{c_j}$. From Definition~\ref{def:conflictingTx} it follows that $c_i$  and $c_j$ are conflicting which implies a contradiction to the fact that $I$ is an independent set in the Conflict Graph.

The branch ${B}$ is also maximal. To see this assume the existence of a larger branch $A$ containing ${B}$, i.e., ${B}\subset A$ an let $d\in A\setminus{B}$ be a conflict from $A$ not included to ${B}$. Then $d$ and $c_1,\ldots,c_n$ are pairwise indirectly non-conflicting which contradicts the fact that the independent set $I$ is maximal.

Conversely, let ${B}=\{c_1,\ldots, c_n\}$ be a reality. Hence, $c_1,\ldots,c_n$ are not conflicting and $I:={B}$ is an independent set of the Conflict Graph. Toward a contradiction assume that $I$ is not maximal, i.e., there exists $d\in\mathcal{C} \setminus {B}$ such that $d$ and $c_1,\ldots, c_n$ are pairwise non-conflicting. Define $A$ to be $  \cone{p}{\mathcal{C}}{d} \cup \cone{p}{\mathcal{C}}{c_1} \cup \cdots \cup  \cone{p}{\mathcal{C}}{c_n}$. Clearly, $A$ is a branch containing ${B}$ as a subbranch. We arrive to a contradiction with Definition~\ref{def: reality}.
\end{proof}







\begin{definition}[Ledger of a reality]\label{def: R-ledger}
Let $R$ be a reality. We define the $R$-ledger as
\[
\mathcal{L}_r({R}) := \{ x\in \mathcal{L}: \ \mathrm{label}^{(p)}(x) \subseteq \{\bot\} \cup \mathrm{label}({R})\},
\]
where  $\mathrm{label}({R}) := \bigcup\limits_{c\in {R}} \mathrm{label}(c).$
\end{definition}

We can now give one of our main results as a direct consequence of the construction the Reality-based Ledger. 
\begin{theorem}\label{thm:Rledger}
Let $R$ be a reality. Then, $\mathcal{L}_r(R)$ is a consistent ledger (cf. Definition~\ref{def: consistent ledger}).
\end{theorem}
\begin{proof}
We have to prove that Assumption~\ref{ass:constraints2} implies Assumption \ref{ass:constraints} for every $R$-ledger. Constraints $1)-3)$ are trivially satisfied. Constraint $4)$ in Assumption~\ref{ass:constraints}  follows from the fact that a reality is a branch (and, hence, conflict-free) together with Constraint $4)$ in Assumption~\ref{ass:constraints2}.
\end{proof}





Similar to  a conflict-free ledger and Remark~\ref{rem: invariant ledger}, we provide invariance properties of the Reality-based Ledger.
\begin{remark}[Invariance properties of Reality-based Ledger]\label{rem: invariance reality}
The Reality-based Ledger upholds certain invariance properties and can thus be seen as an invariant data structure. More specifically, we notice that 
\begin{enumerate}[leftmargin=*] 
\item the Reality-based Ledger  might depend on the time parameter $t$, i.e. $\mathcal{L}=\mathcal{L}(t)$;
\item for any given reality $R\in\mathcal{B}$ at any given time $t$, it holds that the sum of output values of the state of the $R$-ledger remains constant
$$
\sum_{\substack{o=(v,\mathrm{cond})\\o\in \mathrm{state}(\mathcal{L}_r(R))}} v = const.
$$
\end{enumerate}
\end{remark}

\section{Operations on the Reality-based Ledger}\label{sec: operations on the ledger}
In this section we define several operations that we can perform on the Reality-based Ledger. In Section~\ref{sec:ConflictAddition}, we describe what happens when new conflicts are added to the ledger. In Section \ref{sec:RealitySelection} we provide an algorithm for the selection of a reality, i.e., a valid conflict-free ledger state, in the presence of a weight function imposed on transactions and branches. Finally, in Section \ref{sec:ConflictPruning} we describe how and when conflicts can be pruned to maintain a reasonable data  consumption for the operation of the Ledger. 

\subsection{Adding Conflicts}\label{sec:ConflictAddition}
In this section, we explain how new  conflicting transactions result in updating the Conflict DAG and the Conflict Graph. Throughout this section we assume  that there is only one new transaction $x$ which is a leaf in the Ledger DAG. In this case, the Ledger DAG is updated with only directed edges of the form $(x,y)$ for some $y\in \mathcal{L}$. 

First, we introduce a concept of closest conflicts in the past and future cones of a transaction which will be used for updating the Conflict DAG. 


\begin{definition}[Closest conflicts in past and future cones]\label{def: closest conflicts}
For a transaction $z\in \mathcal{L}$, we define $\conflictsInCone{p}{\mathcal{L}}{z}$ to be $\min_{\mathcal{C}}(S^{(p)})$ for $S^{(p)}:=\{y\in\mathcal{C}\cup \{\rho\}:\ y<_{\mathcal{L}} z \}$, i.e., $S^{(p)}$ is the set of all conflicts in $\cone{p}{\mathcal{L}}{z}/\{z\}$.  Similarly, we define $\conflictsInCone{f}{\mathcal{L}}{z}$ to be $\max_{\mathcal{C}}(S^{(f)})$ for $S^{(f)}:=\{y\in\mathcal{C}:\ y<_{\mathcal{L}} z \}$, i.e., $S^{(f)}$ is the set of all conflicts in $\cone{f}{\mathcal{L}}{z}/\{z\}$.
\end{definition}

This notion resembles Definition~\ref{def:label set} and now we give a remark similar to Remark~\ref{rem: how to update the set of labels} on how to find these sets.  
\begin{remark}
Observe that $\conflictsInCone{p}{\mathcal{L}}{z}$  and   $\conflictsInCone{f}{\mathcal{L}}{z}$ can be obtained by first finding closest conflicts using breadth-first search (BFS) and reverse breadth-first search (RBFS). 
That means that in both cases we traverse $D_{\ledger}$ starting  at $z$ and stop traversing through transactions that are conflicts. Eventually, we identify the minimal/maximal elements in the obtained sets. 
\end{remark}

We provide a possible scheme to update the Conflict DAG in Algorithm~\ref{alg: updating Conflict DAG}.
Let $x$ be a new transaction and $Y\subseteq \mathcal{L}$ be the set of all transaction conflicting with $x$. Then, in Algorithm~\ref{alg: updating Conflict DAG}, we

\begin{enumerate}[leftmargin=*]
    \item update the set of vertices by adding the conflicts $x\cup Y$;
    \item add edges to the Conflict DAG using the notion of closest  conflicts in the past and future cones of transaction from $x\cup Y$;
    \item remove unnecessary edges in the Conflict DAG to keep it in the minimal form.
\end{enumerate} 

\begin{algorithm}[t]
\caption{Algorithm to update Conflict DAG}
\label{alg: updating Conflict DAG}
\KwData{Conflict DAG $D_{\conflictset} = (\mathcal{C}\cup \{\rho\}, E)$; new transaction  $x\in \mathcal{L}$ that is directly conflicting with transactions $Y\subseteq \mathcal{L}$}
\KwResult{updated Conflict DAG $D_{\conflictset} = (\mathcal{C}\cup \{\rho\}, E)$}
$\mathcal{C}\gets \mathcal{C}\cup\{x\}\cup Y$ \\

\For{$\forall y\in Y\cup \{x\}$}{
\For{$\forall v\in \conflictsInCone{p}{\mathcal{L}}{y}$}{
$E\gets E\cup \{(y,v)\}$\\
}
\For{$\forall v\in \conflictsInCone{f}{\mathcal{L}}{y}$}{
$E\gets E\cup \{(v,y)\}$
}
}

\For{$\forall y\in Y$}{
\For{$\forall p\in \parent{\mathcal{C}}{y}$}{
\For{$\forall c\in \child{\mathcal{C}}{p}$} {
\If{$c\in \cone{f}{\mathcal{C}}{y}$}{
$E\gets E\setminus\{(c,p)\}$\label{it: main case}
}
}
}
}
\end{algorithm}
\begin{lemma}
The resulting graph $D_{\conflictset}=(\mathcal{C}\cup \rho, E)$ in Algorithm~\ref{alg: updating Conflict DAG} is the Conflict DAG as defined in Definition~\ref{def: Conflict DAG}.
\end{lemma}
\begin{proof}
Recall that the Conflict DAG is the minimal subDAG of the Ledger DAG induced by $\mathcal{C}$. It is sufficient to check that we remove all unnecessary edges after adding correct edges using the notions $\conflictsInCone{p}{\mathcal{L}}{y}$ and $\conflictsInCone{f}{\mathcal{L}}{y}$.

Assume that some edge $(c,p)$, which was an edge in the original Conflict DAG, has to be removed to keep the Conflict DAG in the minimal form. This means that both $c$ and $p$ were already conflicts  such that $c<_{\mathcal{C}} p$ with no other conflict between them  and now some conflict $y\in Y$ satisfies $c<_{\mathcal{C}}y<_{\mathcal{C}} p$.  Let $y^*$ be a $D_{\conflictset}$-minimal conflict among all  $y$  satisfying the latter inequality, i.e, $c\in \child{\mathcal{C}}{y^*}$. One can check that all such edges $(c,p)$ are removed from the Conflict DAG in line~\ref{it: main case} of Algorithm~\ref{alg: updating Conflict DAG}.
\end{proof}

Assume that Algorithm~\ref{alg: updating Conflict DAG} is already completed. In Algorithm~\ref{alg:updateConflictGraph} we describe a possible procedure to update the Conflict Graph.  In this algorithm, we  only add new edges to the Conflict Graph $G_{\conflictset}$. Specifically, all conflicts in the future cones of conflicts in $Y$ become adjacent with $x$ in $G_{\conflictset}$. In addition, all conflicts in $x\cup Y$ inherit $G_{\conflictset}$-neighbours from their parents in $D_{\conflictset}$.

\begin{algorithm}[t]
\caption{Algorithm to update Conflict Graph}
\label{alg:updateConflictGraph}
\KwData{Conflict Graph $G_{\conflictset} = (\mathcal{C}_{old}, E)$; new transaction  $x\in \mathcal{L}$ that is directly conflicting with transactions $Y\subseteq \mathcal{L}$; updated Conflict DAG $D_{\conflictset} = (\mathcal{C}\cup \rho, E)$;}
\KwResult{updated Conflict Graph $G_{\conflictset} = (\mathcal{C}, E)$}
\For{$\forall y\in Y$}{
\For{$\forall z\in \cone{f}{\mathcal{C}}{y}$}{
$E\gets E\cup \{(x,z)\}$\label{algUpdateConflictGraph: x is directly conflicting}
}
}


\For{$\forall y\in Y\cup\{x\}$}{{\scriptsize{\Comment*[l]{assume $D_{\conflictset}$-descending order}}}
\For{$\forall p\in \parent{\mathcal{C}}{y}$}{
\For{$\forall z\in N_{\mathcal{C}}(p)$}{
{\scriptsize{\Comment*[l]{$N_{\mathcal{C}}(p)$ denotes the set of neighbours of $p$ in $G_{\conflictset}$}}}
$E\gets E\cup \{(y,z)\}$ \label{algUpdateConflictGraph: remaining}
}
}
}
\end{algorithm}
\begin{lemma}
The resulting graph $G_{\conflictset}=(\mathcal{C}, E)$ in Algorithm~\ref{alg:updateConflictGraph} is the Conflict Graph as defined in Definition~\ref{def: Conflict Graph}.
\end{lemma}
\begin{proof}
By Definition~\ref{def: Conflict Graph}, if two conflicts $c_1,c_2\in \mathcal{C}$ are connected by an edge in the Conflict Graph, then there exist $e_1,e_2\in \mathcal{C}$ with $c_1\le_{\mathcal{C}} e_1$ and $c_2\le_{\mathcal{C}} e_2$ such that $e_1$ and $e_2$ are directly conflicting. Let $E'$ denote the set of edges to be included to the Conflict Graph after transaction $x$ arrives. We claim that any edge from $E'$ should contain at least one conflict from the set $x\cup Y$. This is true since $x$ is a leaf in both the Ledger DAG and the Conflict DAG.

Let us start with considering edges from $E'$ of type $(x,z)$ for some $z\in\mathcal{C}$ such that there exists $y\in \mathcal{C}$ with $z\le_{\mathcal{C}} y$, and such that $x$ and $y$ are directly conflicting. 
Clearly, $y$ has to be from $Y$ since $x$ is directly conflicting with transactions from $Y$ only.
In line~\ref{algUpdateConflictGraph: x is directly conflicting} of Algorithm~\ref{alg:updateConflictGraph}, by traversing over all transactions $z$ in the Conflict DAG that are contained in the future cones of conflicts from $Y$, we add all such edges $(x,z)$ to $E$.

Observe that there is no edges in $E'$ of type $(y,z)$ for $y\in Y$ and $z\in \mathcal{C}\setminus\{x\}$ such that
there exists $w\in \mathcal{C}$ with $z\le_{\mathcal{C}} w$  and such that $y$ and $w$ are directly conflicting. That is true since we do not include any edge in the Ledger DAG that contains $y\in Y$ when transaction $x$ arrives.

Thus, it remains to add edges of type $(y,z)$ with $y\in Y\cup \{x\}$ such that there exist $e_1,e_2\in \mathcal{C}$ with $y<_{\mathcal{C}} e_1$ and $z<_{\mathcal{C}} e_2$ such that $e_1$ and $e_2$ are directly conflicting. Note that the above inequalities in the partial order relations are strict and we can utilize the notion of parents in $D_{\conflictset}$ to add edges recursively. Thereby, by assuming some  $D_{\conflictset}$-descending order over the set $Y\cup\{x\}$, we iteratively perform the following step in~line~\ref{algUpdateConflictGraph: remaining} of~Algorithm~\ref{alg:updateConflictGraph}.  For every conflict  $y\in  Y\cup\{x\}$, the set of $G_{\conflictset}$-neighbors of $y$  is updated by looking at $G_{\conflictset}$-neighbours of parents  of $y$ in $D_{\conflictset}$ as follows 
$$
N_{\mathcal{C}}(y)\gets N_{\mathcal{C}}(y) \cup \left\{\bigcup_{p\in\parent{\mathcal{C}}{y}} N_{\mathcal{C}}(p)\right\}.
$$
\end{proof}
\iffalse
Before proceeding with the next algorithm, we introduce a useful notation that describes that the set of branches in the Branch DAG which are different from one of the parents in a given conflict.
\begin{definition}[Set of branches different from a parent in a conflict]\label{def: branches different in a parent}
Let $x\in\mathcal{C}$ be a conflict. Define $Z(x)$ to be the set of branches ${B}\in \mathcal{B}$ such that there exists ${B}'\in \parent{\mathcal{B}}{B}$ with the property $\{x\}={B}\setminus {B}'$.
\end{definition}

Now we describe an algorithm to update the Branch DAG in Algorithm~\ref{alg: updating Branch DAG}. We assume that Algorithm~\ref{alg: updating Conflict DAG} is already completed so that the set of new conflicts $\mathcal{C}'$ is available and the Conflict DAG $D_{\conflictset}$ is updated. 

\begin{algorithm}[t]
\caption{Algorithm to update the Branch DAG when a new conflicting transaction arrives}
\label{alg: updating Branch DAG}
\KwData{Branch DAG $\mathcal{DAG}_{\textrm{\tiny{Branch}}} = (\mathcal{B}, E)$; new transaction $a\in \mathcal{L}$;  set of new conflicts $\mathcal{C}'$ in the updated Conflict DAG $D_{\conflictset}$. }
\KwResult{updated Branch DAG $\mathcal{DAG}_{\textrm{\tiny{Branch}}} = (\mathcal{B}, E)$}
\For{$\forall b\in \mathcal{C} '$} {
\For{$\forall v\in\parent{\mathcal{B}}{b}$} {
\For{$\forall {B}\in Z(v)$}{
$New \gets {B}$
 \While{RBFS $\mathcal{DAG}_{\textrm{\tiny{Branch}}}$ in reverse way using BFS}{}

}
}
}

\end{algorithm}
\fi

\subsection{Reality Selection Algorithms}\label{sec:RealitySelection}

In a system with a conflict-free UTXO Ledger, the account owners can learn about their current balance by inspecting the state of an instance of a ledger, see Section \ref{sec: Standard UTXO}. In the case of the Reality-based Ledger this is more complicated, since only a single reality represents a valid conflict-free ledger, and thus can yield a valid ledger state.
It is, therefore, up to the operator of the ledger instance, to choose which ledger state to evaluate to inform the account owners about their balance. Alternatively, and in a more trustless fashion, the account owner and the operator of the ledger instance constitute the same entity. 

In this section, we propose reality selection algorithm that construct a preferred reality by utilizing a weight function for transactions. We impose several natural constraints on the weight function.
\begin{ass}\label{ass: weight function on transaction}
We assume that there exists a weight function on the set of transactions $\mathbf{w}: \mathcal{L}\to [0,1]$ which satisfies the following properties
\begin{enumerate}[leftmargin=*]
\item unitarity: $\mathbf{w} (\rho)=1;$
\item monotonicity: for any two transactions  $x, y\in \mathcal{L}$ such that $x \le_{\mathcal{L}} y$, it holds that 
    $$
    \mathbf{w} (x) \le \mathbf{w}(y);
    $$
\item consistency: let $x_1,\ldots, x_s$ be pairwise conflicting transactions.\footnote{We say that transactions  $S\subseteq \mathcal{L}$ are pairwise conflicting if any pair of transactions $x, y\in S$ are conflicting. } Then it holds that 
$$
\sum_{i=1}^{s}\mathbf{w}(x_i) \le 1.
$$
\end{enumerate} 
\end{ass}
We naturally extend the domain of the function $\mathbf{w}$ to the set of all branches $\mathcal{B}$ as follows. For a branch $B\in\mathcal{B}$, we define $\mathbf{w}(B)$ to be 
$$
\mathbf{w}\left(B\right):=\min_{x\in B}\mathbf{w}(x).
$$

\begin{remark}\label{rem: weight function on branches}
A weight function $\mathbf{w}$ induces a weight function on the set of branches $\mathcal{B}$ with the following monotonicity property: let ${B}_1, {B}_2\in \mathcal{B}$ such that ${B}_1 \subseteq {B}_2$, it holds that 
\[
    \mathbf{w} ({B}_1) \geq \mathbf{w}({B}_2).
  \]  If the weight function satisfies Assumption \ref{ass: weight function on transaction}, we also have that  $\mathbf{w} ({B}_1) + \mathbf{w}({B}_2)\leq 1$ for any two conflicting branches ${B}_1, {B}_2\in \mathcal{B}$. We also observe that for a conflict $c\in\mathcal{C}$, $\mathbf{w}(c)=\mathbf{w}(\cone{p}{\mathcal{C}}{c})$.
\end{remark}

Let us give some examples of weight functions satisfying Assumption \ref{ass: weight function on transaction}.

\begin{example}[Minimal hash]\label{ex:min}
Transactions can be ordered, relatively to each other, through several means. One such way is to hash the content of the transaction, see Remark \ref{rem: hash function}. Here we assume the existence of such a function $\mathop{\mathrm{hash}}: \mathcal{L} \to \{0,1\}^h$. We define the weight function using the following steps:
\begin{enumerate}[leftmargin=*]
    \item $\mathbf{w}(\rho)=1$;
    \item for every $x \in \mathcal{C}$ we set $\mathbf{w}(x)=1$ if 
    \[
    \mathop{\mathrm{hash}}(x)= \min_{ y \in N_{\mathcal{C}}(x)} \mathop{\mathrm{hash}}(y),
    \]
    and $\mathbf{w}(x)=0$ otherwise;
    \item inductively starting from the genesis for every $x \in \mathcal{L} \setminus \mathcal{C}$
     we set 
    \[\mathbf{w}(x)= \min_{p \in \parent{\mathcal{L}}{x}} \mathbf{w}(p)\] and update  the weight of $x\in  \mathcal{C}$ to 
    \[\mathbf{w}(x)= \min_{p \in \parent{\mathcal{L}}{x}} \mathbf{w}(p)\] if $\mathbf{w}(x)$ was set to $1$ in the second step. 
\end{enumerate}
\end{example}
\begin{example}[Minimal timestamp]\label{ex:minTS}
Transactions can carry additional information, for instance, timestamps. These can be used to decide between two conflicting transactions. Replacing the hashes by timestamps in Example~\ref{ex:min} yields a weight function based on the timestamps of the transactions.
\end{example}
The two examples above make the most sense in a distributed system under the assumptions of eventual consistency. For applications in the DLT space, more efficient and robust weights are appropriate.

\begin{example}[External consensus]
An external consensus protocol can determine the weights. For example, nodes could agree on the weights via additional direct communication and employ Byzantine-fault-tolerance mechanisms. Weights can also be inherited by the data structure that carries the ledger; for instance, $\mathbf{w}(x)=1$ if $x$ is contained in the longest chain, \cite{nakamoto2008bitcoin}, or in the heaviest subtree, \cite{GHOST}; and $\mathbf{w}(x)=0$ otherwise. Finer weights can be obtained using the distance between the longest and second-longest chain. 
\end{example}


\begin{example}[Approval weight]
The monotonicity property, see  Assumption~\ref{ass: weight function on transaction}, suggests that we can define the weights  recursively using the underlying DAG structure of the  DLT. This definition enables an internal consensus mechanism on the weights and, therefore, on the preferred reality. These ideas are expanded in detail in~\cite{OTV}.
\end{example}





To determine which reality an operator of the ledger should prefer, we propose to perform the recursive exploration algorithm described in Algorithm~\ref{alg:selectionBranch}. In this algorithm, we start at the main branch of the Branch DAG and walk on this graph until we reach a leaf. The algorithm prefers to go to the child with the highest value of the weight function.
We observe that the resulting ${R}$ is a maximal branch or a reality by construction. One can readily see that the provided algorithm has reasonable complexity despite the fact that the Branch DAG can be exponentially large in the number of conflicts (cf. Remark~\ref{rem: complexity of Branch DAG}). Indeed,
the number of iterations in the while-loop is bounded by the depth of the Branch DAG which is at most $|\mathcal{C}|$. 
The number of elements in $\child{\mathcal{B}}{R}$ is also bounded by $|\mathcal{C}|$.
Thereby, the complexity of Algorithm~\ref{alg:selectionBranch} can be estimated as $O(|\mathcal{C}|^2)$. These observations are summarized below.

\begin{algorithm}[t]
\caption{Reality selection in Branch DAG}
\label{alg:selectionBranch}
\KwData{Branch DAG $\mathcal{DAG}_{\textrm{\tiny{Branch}}} = (\mathcal{B}, E)$}
\KwResult{reality ${R}\in \mathcal{B}$}
${R}\gets \emptyset$ {\scriptsize{\Comment*[r]{{main branch in $\mathcal{DAG}_{\textrm{\tiny{Branch}}}$}}}}
\While{${R}$ is not a leaf in $\mathcal{DAG}_{\textrm{\tiny{Branch}}}$}{
${B}^* \gets \argmax\{\mathbf{w}({B}): {B} \in \child{\mathcal{B}}{R} \}$ {\scriptsize{\Comment*[r]{use $\min\mathop{\mathrm{hash}}({B}\setminus {R})$ for breaking ties }}}
${R}\gets {B}^*$
}
\end{algorithm}
\iffalse
\begin{algorithm}[t]
\caption{Finding children in Branch DAG}
\label{alg:findingChilds}
\KwData{Branch DAG $\mathcal{DAG}_{\textrm{\tiny{Branch}}} = (\mathcal{B}, E)$, branch ${B}$}
\KwResult{set of children $\child{\mathcal{B}}{B}$}
$T\gets \emptyset$\\
\For{$\forall v\in \mathcal{C}$}{
\If{ $\mathbf{isBranch}(v,{B})=true$}{
${B}^{*}\gets v\cup{B}$\\
$T\gets T \cup {B}^{*}$
}
}
\end{algorithm}
\begin{algorithm}[t]
\caption{Function $\mathbf{isBranch}(v,{B})$}
\label{alg: isBranch}
\KwData{branch ${B}$; conflict $v\in\mathcal{C}$}
\KwResult{$true$ if $v\cup {B}$ is branch; $false$ otherwise}
\For{$\forall b\in{B}$}{
\If{$b$ is indirectly conflicting with $v$}{
\Return $false$
}
}
\For{$\forall p\in \parent{\mathcal{C}}{b}$}{
\If{$p\not\in {B}$}{
\Return $false$
}
}
\Return $true$
\end{algorithm}
\fi
\begin{proposition}
The resulting set ${R}$  in Algorithm~\ref{alg:selectionBranch} is a reality. The complexity of this algorithm is $O(|\mathcal{C}|^2)$.
\end{proposition}


As there is a one-to-one correspondence between realities and maximal independent sets of the Conflict Graph by Proposition~\ref{prop:maximalIndReality}, we propose an alternative reality selection procedure based on the Conflict Graph in Algorithm~\ref{alg:selectionConflictGraph}. In this algorithm, we start with the empty set and iteratively construct a subset $R$ of conflicts. Specifically, we add a conflict to this set if this conflict is not conflicting with $R$ and attains the highest value of the weight function. By construction, Algorithm~\ref{alg:selectionConflictGraph}  leads to a maximal independent set in the Conflict Graph or a reality in the Branch DAG. The number of iterations in the while-loop is bounded by $|\mathcal{C}|$ and the number of $G_{\conflictset}$-neighbours is also bounded by $|\mathcal{C}|$. Thus, it is possible to implement this algorithm with complexity $O(|\mathcal{C}|^2)$.  In the following statement we verify that the outcomes of the two algorithms coincide.

\begin{algorithm}[t]
\caption{Reality selection in Conflict Graph}
\label{alg:selectionConflictGraph}
\KwData{Conflict Graph $G_{\conflictset}=(\mathcal{C},E)$}
\KwResult{reality ${R}\in \mathcal{B}$}
${R}\gets \emptyset$\\
$U\gets \mathcal{C}$\\
\While{$|U|\neq 0$}{
$c^*\gets \argmax \{ \mathbf{w}(c): c\in \max_{\mathcal{C}}(U)\}$ {\scriptsize{\Comment*[r]{use $\min\mathop{\mathrm{hash}}(c)$ for breaking ties}}}
${R} \gets {R} \cup \{c^*\}$\\ $U \gets U  \setminus \{N_{\mathcal{C}}(c^{*}) \cup\{c^{*}\}\}$
}
\end{algorithm}


\begin{theorem}
Algorithms~\ref{alg:selectionBranch} and~\ref{alg:selectionConflictGraph} provide the same reality as output.
\end{theorem}

\begin{proof}
The proof is done by induction on the number of iterations in the while-loops. Both algorithms start with the empty set and add at the first step the same conflict $c^{*}$, namely the one achieving the highest value of the weight function $\mathbf{w}(\cdot)$. Note that $c^{*}$ is $D_{\conflictset}$-maximal in the set of conflicts $\mathcal{C}$ and represents a child of the main branch in $\mathcal{DAG}_{\textrm{\tiny{Branch}}}$.

Let us assume that both algorithms constructed the same branch ${R}$ after some number of steps. 
Then on one hand, Algorithm~\ref{alg:selectionConflictGraph} will pick the conflict $c^*$ with the highest value of $\mathbf{w}(\cdot)$ among all $D_{\conflictset}$-maximal elements in the set $U$, where $U$ is the set of conflicts in $\mathcal{C}\setminus {R}$ that are not conflicting with ${R}$. 
On the other hand, Algorithm~\ref{alg:selectionBranch} will pick a branch ${B}^*$ with the highest value of $\mathbf{w}(\cdot)$ over all children of ${R}$ in~$\mathcal{DAG}_{\textrm{\tiny{Branch}}}$. It remains to show that ${B}^*$ obtained in Algorithm~\ref{alg:selectionBranch} coincides with  ${R}\cup \{c^*\}$ obtained in Algorithm~\ref{alg:selectionConflictGraph}. 

First, we prove that ${R}\cup \{c^*\}$ is a branch (cf. Definition~\ref{def:branch}).  The set ${R}\cup \{c^*\}$ does not contain conflicting transactions since all transactions conflicting with ${R}$ were removed from $U$ at the previous steps  and $c^{*}\in U$. Seeking a contradiction assume that ${R}\cup \{c^*\}$ is not $D_{\conflictset}$-past-closed. Since ${R}$ is a branch by the inductive hypothesis, it may happen only when there exists some $b\in \cone{p}{\mathcal{C}}{c^{*}}$ such that $b\not\in {R}$. From $c^*\in U$ it follows that $b\in U$. Since $c^*\in \max_{\mathcal{C}}(U)$ and $c^*\le_{\mathcal{C}} b$, we conclude that $c^*=b$. Thus,  ${R}\cup \{c^*\}$ is indeed a branch which belongs to the set of children $\child{\mathcal{B}}{R}$ by Definition~\ref{def:branchDAG}.

Since ${B}^*\in \child{\mathcal{B}}{R}$, the branch ${B}^*$ can be represented as $d\cup {R}$ for some $d\in\mathcal{C}$. The set ${B}^*$ is a branch and does not contain conflicting transactions and, thus, we have that $d\in U$. Moreover, $d\in \max_{\mathcal{C}}(U)$ since ${B}^*$ is $D_{\conflictset}$-past-closed. 

Now we will show that 
\begin{equation}\label{eq: weight of d is equal}
\mathbf{w}(d)=\mathbf{w}({B}^*).
\end{equation}
By definition of the weight function $\mathbf{w}({B}^*)=\min\{\mathbf{w}(c) : c\in d\cup {R}\}$. Seeking a contradiction, assume that the minimum is attained at some $e \neq d$, i.e., $\mathbf{w}(e)<\mathbf{w}(d)$. Let $U'$ and ${R}'$ be the sets $U$ and ${R}$ right before the element $e$ was included to ${R}$. Then one can find $d'\in\cone{p}{\mathcal{C}}{d}$ such that $d'\in\max_{\mathcal{C}}(U')$. By the monotonicty of the weight function, we get that $\mathbf{w}(d')\ge \mathbf{w}(d)>\mathbf{w}(e)$ which contradicts the fact that $e$ was included to $U'$ and, thus, achieves the maximum of the weight function over all conflicts in $\max_{\mathcal{C}}(U')$.

Using similar ideas as above one can prove that 
\begin{equation}\label{eq: weight of c^* is smaller}
\mathbf{w}(c^*)\le \mathbf{w}({R}).
\end{equation}

Finally, it remains to show that $\mathbf{w}(d)=\mathbf{w}(c^*)$. By definition of $c^{*}$ in Algorithm~\ref{alg:selectionConflictGraph}, $\mathbf{w}(c^*)\ge \mathbf{w}(d)$ as both $c^*$ and $d$ belong to $\max_{\mathcal{C}}(U)$. On the other hand, by definition of ${B}^{*}$ in Algorithm~\ref{alg:selectionBranch}, $\mathbf{w}({B}^{*})\ge \mathbf{w}(c^*\cup {R})$. Combining the latter inequality with~\eqref{eq: weight of d is equal}-\eqref{eq: weight of c^* is smaller} implies
\[
\mathbf{w}(d)=\mathbf{w}({B}^*)\ge \mathbf{w}(c^*\cup {R})=\mathbf{w}(c^*),
\]
which leads to $\mathbf{w}(d)=\mathbf{w}(c^*)$. To ensure that $d=c^*$ we observe that both algorithms use $\min \mathop{\mathrm{hash}}(\cdot)$ for breaking ties.
\end{proof}


\begin{example}
In Figure~\ref{fig:RealitySelection}, we depict an illustrative example that demonstrates how both reality selection algorithms work. We make use the same labeled UTXO DAG, the Conflict DAG and the Conflict Graph as in Figure~\ref{fig:DAGtransition}. First, we note that there are three iterations in the while-loops of the both algorithms. Conflicts in Figure~\ref{fig:RealitySelection} are represented by colorful boxes. The value of the function $\mathbf{w}(\cdot)$ is depicted inside the boxes. The selected set of conflicts ${R}$ at every step is highlighted by green borders. At the first step both algorithms include to ${R}$, which was initialized as the empty set, the yellow conflict which has the highest weight $0.7$. Since the red conflict is conflicting with the yellow conflict, it should be removed from the set $U$. At the second step, Algorithm~\ref{alg:selectionBranch} takes the child of ${R}$ in $\mathcal{DAG}_{\textrm{\tiny{Branch}}}$ that has the highest weight. This child is a branch that consists of two conflicts, the yellow one and the aquamarine one. At the same moment Algorithm~\ref{alg:selectionConflictGraph} finds the conflict with the highest weight in the set of $D_{\conflictset}$-maximal elements of $U$. This set consists of the purple conflict and the aquamarine conflict and the latter has the highest weight. Finally, at last step, both algorithms update set ${R}$ by adding the blue conflict.
\end{example}

\begin{figure*}[t]
    \centering
    \includegraphics[width=0.9\textwidth]{RealitySelection.png}
    \caption{Demonstrative example of the reality selection algorithms based on the Branch DAG and the Conflict Graph.}
    \label{fig:RealitySelection}
\end{figure*}
\subsection{Pruning Conflicts}\label{sec:ConflictPruning}
In this section, we explain how we prune conflicting transactions and update the Conflict DAG, the Conflict Graph and the Ledger DAG when the weight function $\mathbf{w}$ of a certain branch exceeds a given threshold.

\begin{definition}[Confirmed branch]
Let $\theta \in (0.5, 1]$ be a fixed threshold. A branch ${B}\in\mathcal{B}$ is called $\mathbf{w}$-\textit{confirmed} if 
$\mathbf{w}({B})\ge\theta$. 
\end{definition}

\begin{lemma}\label{lem: the only minimal confirmed branch}
Let $\mathcal{B}'\subseteq\mathcal{B}$ be the set of $\mathbf{w}$-confirmed branches. Then there exists a unique $\mathcal{DAG}_{\textrm{\tiny{Branch}}}$-minimal branch in the set $\mathcal{B}'$. In other words, the subDAG of $\mathcal{DAG}_{\textrm{\tiny{Branch}}}$ induced by $\mathcal{B}'$ has  a unique leaf.
\end{lemma}

\begin{proof}
Seeking a contradiction, assume the existence of two $\mathcal{DAG}_{\textrm{\tiny{Branch}}}$-minimal confirmed branches ${B}_1$ and ${B}_2$. If these branches are conflicting, then $\mathbf{w}({B}_1)+\mathbf{w}({B}_2)\le 1$ by Remark~\ref{rem: weight function on branches} and we come to a contradiction as $\mathbf{w}({B}_1)+\mathbf{w}({B}_2)\ge2\theta>1$.  Thus, the union of these branches does not contain a pair of conflicting transactions and ${B}:={B}_1\cup {B}_2$ is also a branch. Moreover,  ${B}$ is $\mathbf{w}$-confirmed as
$$
\mathbf{w}({B})=\min_{x\in{B}_1\cup{B}_2} \mathbf{w}(x)\ge \min(\mathbf{w}({B}_1),\mathbf{w}({B}_1))\ge \theta.
$$
Clearly, ${B}<_{\mathcal{B}}{B}_1$ and  ${B}<_{{\mathcal{B}}}{B}_2$ and we arrive to a contradiction with the fact that ${B}_1$ and ${B}_2$ are $\mathcal{DAG}_{\textrm{\tiny{Branch}}}$-minimal in the set of confirmed branches $\mathcal{B}'$.
\end{proof}
Let  ${B}$ be the unique $\mathcal{DAG}_{\textrm{\tiny{Branch}}}$-minimal  $\mathbf{w}$-confirmed branch as in Lemma~\ref{lem: the only minimal confirmed branch}. We propose to update all graph structures such that the conflicts in $B$ are no longer conflicts, i.e., all transactions conflicting with $B$ should be removed from the ledger $\mathcal{L}$. A possible way to achieve that is described in Algorithm~\ref{alg: update UTXO DAG after confirmation}.

In this algorithm, we first identify  the set of conflicts $\mathcal{C}'$ conflicting with $B$ and the set of conflicts $\mathcal{C}''$ that should be removed from $\mathcal{C}$. Note that $B\cup \mathcal{C}' \subseteq \mathcal{C}''$. 
Then we
\begin{enumerate}[leftmargin=*]
    \item remove all edges adjacent to $\mathcal{C}'$ from the Conflict Graph $G_{\conflictset}$. We note that $\mathcal{C}''$ is the set of isolated vertices in $G_{\conflictset}$. We remove $\mathcal{C}''$  from $G_{\conflictset}$.
    \item prune the Ledger DAG by removing all transactions that are directly or indirectly conflicting with ${B}$ and all edges adjacent to them by traversing future cones of $\mathcal{C}'$;
    \item remove all vertices corresponding to $\mathcal{C}''$  and all edges adjacent to $\mathcal{C}''$ from the Conflict DAG. If necessary, we add some edges to the Conflict DAG to make it connected.
\end{enumerate} 

Recall that the Conflict DAG and the Conflict Graph are concepts which are derived from the Ledger DAG, i.e., $D_{\conflictset} = D_{\conflictset}(D_{\ledger})$ and $G_{\conflictset} = G_{\conflictset}(D_{\ledger})$. Thereby, one needs to show consistency between the resulting three graphs.

\begin{algorithm}[ht]
\caption{Algorithm to update Ledger DAG, Conflict DAG and Conflict Graph  after branch confirmation}
\label{alg: update UTXO DAG after confirmation}
\small
\KwData{Ledger DAG $D_{\ledger}=(\mathcal{L},E_{D_{\ledger}})$, Conflict DAG $D_{\conflictset}=(\mathcal{C}\cup\{\rho\},E_{D_{\conflictset}})$, Conflict Graph $G_{\conflictset} = (\mathcal{C}, E_{G_{\conflictset}})$, confirmed branch ${B}$}
\KwResult{updated Ledger DAG $D_{\ledger}=(\mathcal{L},E_{D_{\ledger}})$, Conflict DAG $D_{\conflictset}=(\mathcal{C}\cup\{\rho\},E_{D_{\conflictset}})$, Conflict Graph $G_{\conflictset} = (\mathcal{C}, E_{G_{\conflictset}})$}
$M\gets \min_{\mathcal{C}}({B})$\\
$\mathcal{C}'\gets \emptyset$ {\scriptsize{\Comment*[r]{conflicts conflicting with $B$}}}
$\mathcal{C}''\gets \emptyset$ {\scriptsize{\Comment*[r]{conflicts to be removed from $\mathcal{C}$}}}


\For{$\forall x\in M$}{
\For{$\forall y\in N_{\mathcal{C}}(x)$}{
$\mathcal{C}'\gets \mathcal{C}' \cup \{y\}$\\
\For{$\forall z\in N_{\mathcal{C}}(y)$}{
$E_{G_{\conflictset}}\gets E_{G_{\conflictset}}\setminus\{(y,z)\}$}}}

\For{$\forall x\in \mathcal{C}$}{
\If{$x$ is isolated in $G_{\conflictset}$}{
$\mathcal{C}''\gets \mathcal{C}'' \cup\{x\}$
}
}
\For{$\forall y\in \max_{\mathcal{C}}(\mathcal{C} ')$}{
\For{$\forall z\in \cone{f}{\mathcal{L}}{y}$}{{\scriptsize{\Comment*[l]{assume $D_{\ledger}$-descending order}}}
$\mathcal{L}\gets \mathcal{L}\setminus\{z\}$\\
\For{$\forall p\in \parent{\mathcal{L}}{z}$}{
$E_{D_{\ledger}}\gets E_{D_{\ledger}} \setminus\{(z,p)\}$
}
}
}
\For{$\forall y\in \mathcal{C} ''$}{
\For{$\forall p\in \parent{\mathcal{C}}{y}$}{
$E_{D_{\conflictset}}\gets E_{D_{\conflictset}} \setminus\{(y,p)\}$
}
\If{$y\in \max_{\mathcal{C}}(\mathcal{C}'')$}{
\For{$\forall c\in\child{\mathcal{C}}{y}$}{
$E_{D_{\conflictset}}\gets E_{D_{\conflictset}} \setminus\{(c,y)\}$\\
\If{$\parent{\mathcal{C}}{c}\subseteq \mathcal{C}''$}{
$E_{D_{\conflictset}}\gets E_{D_{\conflictset}} \cup\{(c,\rho)\}$
}
}
}
$\mathcal{C} \gets \mathcal{C} \setminus \{y\}$\\
}
\end{algorithm}

\begin{lemma}
 The resulting Conflict DAG and the resulting Conflict Graph  are consistent with the resulting Ledger DAG in Algorithm~\ref{alg: update UTXO DAG after confirmation}.
 \end{lemma}

\begin{proof}
By Proposition~\ref{prop: only minimal elements in branch}, to identify the set of all conflicts that are conflicting with ${B}$, it suffices to consider the $D_{\conflictset}$-minimal elements in ${B}$. In Algorithm~\ref{alg: update UTXO DAG after confirmation}, we set $M$ to be the set of these minimal conflicts. Then we construct the set $\mathcal{C}'\subseteq \mathcal{C}$ of conflicts that are conflicting with branch ${B}$ by looking at the neighbours of $M$ in the Conflict Graph. Similar to Proposition~\ref{prop: conflicting transactions}, one can check that the set $\mathcal{C}'$ is $D_{\conflictset}$-future-closed.  Let $\mathcal{L}'\subseteq \mathcal{L}$ denote the set of transactions that are conflicting with ${B}$. By Proposition~\ref{prop: conflicting transactions}, $\mathcal{L}'$ is $D_{\ledger}$-future-closed and $\max_{\mathcal{L}}(\mathcal{L}')=\max_{\mathcal{C}}(\mathcal{C}')$. In Algorithm~\ref{alg: update UTXO DAG after confirmation}, we 
\begin{enumerate}[leftmargin=*]
     \item remove all edges adjacent to $\mathcal{C} '$ from the Conflict Graph and construct the set  $\mathcal{C}''$ of isolated vertices in the updated Conflict Graph. Clearly, all conflicts in $\mathcal{C}''$ are no longer conflicts;
    \item update the Ledger DAG by recursive traversing the Ledger future cone  of $\max_{\mathcal{C}}(\mathcal{C}')$ and removing transactions $\mathcal{L}'$ and all edges adjacent to them;
   
   
    \item update the Conflict DAG by removing all conflicts  $\mathcal{C}''$ from $\mathcal{C}$ and all edges adjacent to them. It is possible that after performing this step some vertices in $\mathcal{C}\setminus \mathcal{C}''$ have out-degree zero. To make the Conflict DAG connected again, we add edges from all such conflicts to the genesis $\rho$.
\end{enumerate}



\end{proof}
We conclude this section with a sufficient condition for the pruned data structure to be again conflict-free.
\begin{theorem}
Let $\mathcal{L}$ be a ledger and ${B}$ be a  $\mathbf{w}$-confirmed reality. Then, the set of transactions in the pruned Ledger DAG resulting from Algorithm~\ref{alg: update UTXO DAG after confirmation} is conflict-free and coincides with the $B$-ledger $\mathcal{L}_r(B)$ as in Definition~\ref{def: R-ledger}.
\end{theorem}

\begin{proof}
Suppose ${B}$ is a reality. Then, we note that the set of conflicts to be removed from $\mathcal{C}$  is $\mathcal{C}'' = \mathcal{C}$. Indeed, since $B$ is a maximal independent set in the Conflict Graph (cf. Proposition~\ref{prop:maximalIndReality}), all conflicts in $\mathcal{C} \setminus B$ are conflicting with $B$  and has to be removed from the Ledger DAG. Thus, the conflicts in $B$ are no longer conflicts and become ordinary transactions. Thus, the resulting set of transactions does not contain a pair of directly conflicting transactions. In addition, all transactions $x$ such that $\mathrm{label}^{(p)}(x)\subseteq \mathrm{label}^{(p)}(B)$ are kept in the set of transactions.
\end{proof}


\section{Future Work}
The Reality-based Ledger provides a framework for parallel transaction processing capability. Typically in blockchains,  transactions are processed in blocks or batches, creating a total order. This linearisation creates an artificial bottleneck in the propose and vote paradigm of DLTs. However, particularly in a UTXO setting, this is not necessary, and blockchain systems can be designed using the presented framework. 
We follow this approach in~\cite{OTV}, which builds on the foundations laid out in this paper.
\subsection*{Acknowledgments}
The authors would like to 
thank precious staff members of the IOTA Foundation and members of the IOTA community for their feedback and criticism. 


\bibliographystyle{plain}

