# Relevant Algorithms

## Algorithm to Compute a Block’s Branch

This section provides an algorithm to compute the branch for a given block $b$.

In the following, the blocks from $b.References$ are considered. There are three types of references in IOTA 2.0, which are called strong, weak, and shallow like.

Let $s_1,\ldots,s_{n_s}$ denote the strong parents of block $b$. Let $w_1,\ldots,w_{n_w}$ denote the weak parents of $b$, where each $w_i$ contains transaction $w_i.Tx$. Let $l_1,\ldots,l_{n_l}$ denote the shallow like parents of $b$, where $l_i$ contains transaction $l_i.Tx$.

You can define the conflicts that come from the branches of the strong parents as:

Similarly, you can define the sets of conflicts that come from the weak and shallow like parents. Note that in these operations, the branches of the corresponding payloads (transactions) are used:

Shallow like references allow for the removal of conflicts from the aggregation of branches that do not belong to the preferred reality:

The function $ConflictWith(S)$ returns the set of all conflicts conflicting with at least one element from $S$. Finally, you can define the branch of the block $b$ in two steps. First:

Second, add the branch of the payload of $b$ to the result, i.e. $Branch(b)\gets Branch(b)\cup Branch(b.Tx)$.

The set $Branch(b)$ is subjective for a node that computes the branch. This is because some new conflicts might appear, or some existing conflicts might be resolved in the perception of this node.

## Algorithm to Compute the Preferred Reality

There could be many realities in the reality-based UTXO ledger. However, a unique preferred reality for a node identifies all *conflicting transactionsTransactions that consume the same UTXO.* supported by the node. To find the preferred reality, the node can proceed with the following steps:

- Calculate the
*approval weightMeasure of approval of each conflicting transaction using the voting power of the validation blocks "issuer".*for each unaccepted conflict. The*approval weightMeasure of approval of each conflicting transaction using the voting power of the validation blocks "issuer".*is determined as the combined weight of the online committee members who have voted in favor of this particular conflict and have not altered their stance in favor of a different conflicting transaction in any subsequent block. - Set $C$ to be the set of all conflicts and $R$ to be the empty set (which will eventually be constructed as a reality).
- Find the conflict with the largest
*approval weightMeasure of approval of each conflicting transaction using the voting power of the validation blocks "issuer".*. In the case of many conflicts of equal weight, find the conflict with the largest hash of the conflict id. Include this transaction to $R$. - Remove all transactions that are conflicting with the selected transaction from $C$.
- If $C$ is non-empty, proceed with step 3. Otherwise, output $R$.

## Additional Literature

- Sebastian Müller, Andreas Penzkofer, Nikita Polyanskii, Jonas Theis, William Sanders, and Hans Moog. "Tangle 2.0 Leaderless
*Nakamoto ConsensusNamed after Bitcoin's creator, Satoshi Nakamoto, this consensus describes the use of a cryptographic puzzle (Proof-of-Work) to replace coordination/communication between known agents. Solving the puzzle determines the subsequent agent's action.*on the Heaviest DAG." IEEE Access 10 (2022): 105807-105842. - Sebastian Müller, Andreas Penzkofer, Nikita Polyanskii, Jonas Theis, William Sanders, and Hans Moog. "Reality-based UTXO ledger." ACM DLT 2.3 (2023): 1-33.