Ledger State Calculation

# Ledger State Calculation The ledger is modeled using _unspent transaction output_ (UTXO). It consists of a set of transactions, where each transaction has inputs and outputs and consumes the outputs of a previous transaction with its inputs. The unspent transaction outputs, i.e. the outputs that are never consumed by a transaction, represent the actual ownership of the assets. The UTXO model can be defined more formally as follows: ### UTXO Graph A _UTXO graph_ is a directed hypergraph $H = (V,T)$, where the vertices $v \in V$ are also called _transaction outputs_ and the hyperarcs $t=(I,O) \in T$ with $I,O \subset V$, are called _transactions_. The tail $I$ of transaction $t$ is also called _inputs_ of $t$, while the head $O$ is called _outputs_. The hypergraph $H$ must further have the following properties: - There exists one designated vertex $g \in V$, called _genesis_, and no transactions have $g$ as an output, i.e. $deg^{in}(g) = |\{T=(X,Y) \in A \mid g \in Y\}| = 0$. - For each vertex $v \in V \setminus \{g\}$ there exists exactly one transaction with $v$ as an output, i.e. $deg^{in}(v) = 1$. We call a UTXO graph $H = (V,T)$ _conflict free_, if for every $v \in V$ there exists at most one transaction $t = (I,O)$ with $v\in I$, i.e. $deg^{out}(v) \leq 1$. In a UTXO graph, the set $C_t = \{t'=(I',O') \in T \mid I \cap I' \neq \emptyset\}$ is called a _conflict_ or _conflict set_ of transaction $t = (I,O)$ if it has cardinality > 1. ![UTXO graph](https://i.imgur.com/sSrEI28.png) ***Image:*** Example of a UTXO graph with genesis $g$ as well as 12 transaction outputs (vertices) and 8 transactions (arcs). The depicted graph is not conflict free as the encircled transactions each form a conflict set of size two. ## Ledger State Given a set of transactions $T$ it is very easy to determine whether the induced hypergraph $H = (V,T)$ is a UTXO graph (it must be connected and have a genesis) and whether it is conflict free (count the consumers of each transaction output). This is exactly how the ledger validity of a block in Bitcoin is verified. However, it gets more complicated when conflicts are allowed to stay in the UTXO graph. This situation is considered for the IOTA Tangle. Here, new valid transactions are added to the tangle at the same time when the consensus mechanism is resolving conflicts deeper down in the graph. For this, each of the transactions has one of the following labels: _liked_, _disliked_, _young_ or _unknown_. The labels have the following necessary conditions: - _liked_: transaction $t=(I,O)$ can only be "liked", if each transaction whose outputs are consumed by $t$, i.e. $\{t'=(I',O') \mid O' \cap I \neq \emptyset\}$, is also "liked" and if there are no other "liked" transactions in its conflict set $C_t$. - _disliked_: transaction $t$ can only be "disliked", if each $t'$ that is reachable from $t$ is also "disliked". - _young_: transaction $t$ can only be "young", if it was added to $H$ recently, i.e. it is not older than time $c$. - _unknown_: no conditions. In order to find a global consensus on the ledger state, transactions can be voted on. Eventually, we want to use voting to find a valid label for each transaction $t \in T$ that is either "liked" or "disliked". This idea leads to the following algorithm: ## FCoB ##### Dislike(t) - mark $t$ as `disliked` - **for** each transaction $t'$ that consumes an output of $t$ - Dislike($t'$) ##### Like(t) - mark $t$ as `liked` - **for** each transaction $t'$ that consumes an output of $t$ - **if** $t'$ is `unknown` and can be `liked` - Like($t'$) ##### OnNewTransaction(t) - **if** $t$ is part of a conflict set $C$ - Dislike($t$) - **if** $C$ contains a transaction $t'$ that is `young` - Dislike($t'$) - vote on each $t \in C$ using the label of $t$ as initial opinion - **else** - mark $t$ as `young` - **if** $t$ is still `young` after time $c$ - **if** $t$ can be `liked` - Like($t$) - **else** - mark $t$ `unknown` ##### OnNewVotingResult(D,L) - **for** each transaction $t \in D$ - Dislike($t$) - **for** each transaction $t \in L$ (at most one per conflict) - **if** $t$ can be `liked` - Like($t$) - **else** - mark $t$ as `unknown` ### Complexity In the worst case, a conflict arises right after the genesis (or after the first not finalized), this leads to $\mathcal{O}(c\cdot n)$ label updates, where $n = |T|$ and where $c$ denotes the number of times a vote was triggered. ## Multiverse The following approach tries to reduce the computational complexity of the FCoB algorithm by defining an equivalence relation on the transactions: Equivalent transactions "behave" identically no matter how any conflicts in the underlying UTXO graph are resolved. All decisions like "like" or "dislike" will always be consistent on the equivalence classes (also called _branches_). Therefore, it is possible to work on equivalence classes (consisting of several transactions) instead of individual transactions. To simplify the definition of branches, we first introduce the concept of a _reality_: #### Reality The subgraph $R=(V',T')$ of a UTXO graph $H=(V,T)$ is called a _reality_ of $H$, if it has the following properties: - $R$ is a conflict free UTXO graph, - $R$ is maximal, i.e. adding any transaction $t \in T \setminus T'$ to $R$ would not lead to a conflict free UTXO graph. ![Realities](https://i.imgur.com/cdY7nuC.png) ***Image:*** Each possible reality of the example UTXO graph is represented by one color. The genesis must by definition be included in any reality. E.g. all the vertices that contain blue, form a conflict-free UTXO graph. #### Branch Two transactions $t_1$, $t_2$ of a UTXO graph $H=(V,T)$ are considered equivalent $t_1 \sim t_2$ $\Longleftrightarrow$ for any reality $R$ of $H$ either both or none of $t_1$, $t_2$ are contained in $R$ The equivalence classes of the equivalence relation $\sim$ on $T$ are called _branches_. ![Branches](https://i.imgur.com/nJ37oF2.png) ***Image:*** Partitioning of the example UTXO graph into branches. A branch can only consist of transactions that all have the same color combination for its outputs. #### Branch Graph The directed graph $G=(B,A)$ is called _induced branch graph_ of a UTXO graph $H$, when $B$ is the set of branches of $H$ and $A$ contains an arc $(b_1,b_2)$ when there exists an output of $t_1$ that is consumed by $t_2$, with $t_1 \in b_1$ and $t_2 \in b_2$. Note that this graph can contain arcs $a=(u,v)$ where $u$, $v$ are also connected via other arcs, these transitive arcs are redundant and could be remove in a post-processing step, but they do not change the actual algorithm. ![Branch Graph](https://i.imgur.com/0atpoqT.png) ***Image:*** The induced branch graph of the the example UTXO graph. ### Algorithm ##### Branch(transaction t) - Return the branch of $t$ ##### Branch(output o) - identify the unique transaction $t$ that belongs to $o$ - Return the branch of $t$ ##### Dislike(branch b) - mark $b$ as `disliked` - **for** each outneighbor/child $b'$ of $b$ - Dislike($b'$) ##### Like(branch b) - mark $t$ as `liked` - **for** each outneighbor/child $b'$ of $b$ - **if** $b'$ is `unknown` - Like($b'$) ##### IsConsistent(transaction t, branch b) - **for** each input $i$ of $t$ - $b' \gets$ Branch($i$) - **if** $b' \neq b$ and $b'$ is not a parent of $b$ and not a parent's parent... - Return `false` - Return `true` ($t$ is equivalent to any $t' \in b$) ##### OnNewTransaction(t) - **if** $t$ is part of a conflict set $C$ - create a new branch $b'$ only containing $t$ - mark $b'$ as `disliked` - **for** each output $o$ consumed by $t$ - $b \gets$ Branch(o) - **if** $o$ has a consuming transaction $t' \neq t$ with Branch($t'$) = Branch($o$) - split $b$ into two $b_1$, $b_2$, such that $b_1$ = Branch($o$) and $b_2$ = Branch($t'$) - add the arc $(b_1,b')$ to the branch graph - **else** - add the arc $(b, b')$ to the branch graph - **if** $C$ contains a $t$ with Branch($t$) that is `young` - Dislike(Branch($t$)) - vote on $b =$ Branch($t$) for each $t \in C$ using the label of $b$ as initial opinion - **else** - **for** each output $o$ consumed by $t$ - $b \gets$ Branch(o) - **if** IsConsistent($t$, $b$) - add $t$ to $b$ - Return - create a new branch $b'$ only containing $t$ - **for** each output $o$ consumed by $t$ - $b \gets$ Branch(o) - **if** the branch graph does not contain the arc $(b,b')$ - add the arc $(b,b')$ to the branch graph - mark $b'$ as `young` - **if** $b'$ is still `young` after time $c$ - **if** $b'$ can be `liked` - Like($b'$) - **else** - mark $b'$ `unknown` ### Complexity A branch split in the worst case requires $\mathcal{O}(n)$ operations. This leads to a complexity of $\mathcal{O}(c \cdot n)$ in the worst case.

Read more

Mnemonic Seed RFC

GoShimmer Ledger State

Bundle Mining Review

Tip Selection