Algorithm to Compute a Block’s Branch
This section provides an algorithm to compute the branch for a given block .
In the following, the blocks from are considered. There are three types of references in IOTA 2.0, which are called strong, weak, and shallow like.
Let denote the strong parents of block . Let denote the weak parents of , where each contains transaction . Let denote the shallow like parents of , where contains transaction .
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 returns the set of all conflicts conflicting with at least one element from . Finally, you can define the branch of the block in two steps. First:
Second, add the branch of the payload of to the result, i.e. .
The set 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 to be the set of all conflicts and 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 .
- Remove all transactions that are conflicting with the selected transaction from .
- If is non-empty, proceed with step 3. Otherwise, output .
- 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.