| description | image | slug | keywords | |||||||
|---|---|---|---|---|---|---|---|---|---|---|
Since every node might have a slightly different perception of the Tangle at a given time, a notion of Finality is necessary to guarantee consensus on the Tangle and its ledger state. |
6.4Finalization |
|
This part of the specifications defines the Approval Weight tool, which allows the notion of Finality. As every node might have slightly different perceptions of the Tangle at a given time, such a notion is necessary to guarantee consensus on the Tangle and its ledger state.
The intuition behind the approval weight of a given message is that the more influential messages are approving a given message, the more trustworthy such a message will be for the other nodes, and thus the higher the probability that this message branch will be included in the main branch, i.e., will update the ledger state permanently. More details on branches and ledger state may be found in Section 5.2 - Ledger State.
The approval weight tool is inspired by the confirmation confidence tool, initially defined in the legacy Tangle whitepaper. However, unlike confirmation confidence which only considered the weight of the future cone of a message to decide if it was final, the approval weight now considers the proportion of approving active consensus Mana, making the protocol more robust against spam and Sybil attacks.
The Approval Weight and Finality specification depends on the following specifications:
- 4.7 - Markers
- 5.2 - Ledger State
- 5.3 - Mana
- 6.1 - Object of Consensus
- 6.3 - Fast Probabilistic Consensus
To define approval weight, we first need to understand what it means to support a message, we require some concepts of branches from Section 5.2 - Ledger State.
-
Conflict: Two transactions conflict if they consume the same output. A conflict is a transaction that conflicts with another transaction. A transaction
$x$ conflicts with a branch$B$ if the set of conflicts in$x$ 's UTXO past cone and the set of conflicts in$B$ conflict. -
Node Approval: We say that a node approves a given message
$x$ if it has issued a message$y$ in the strong future cone of$x$ . A node approves a transaction if it approves some message containing that transaction. -
Conflict Supporter: A node supports a conflict if:
- It issued a message approving a message containing that transaction.
- It has not issued a message on a conflicting branch with a more recent timestamp or with the same timestamp but greater message ID.
- Branch Supporter: A node supports a branch if it supports all of its conflicts. Equivalently, the supporters of a branch are the intersection of all the supporters of its conflicts.
- Message Supporter: The supporters of a message is the intersection of the approvers of the message, and the supporter of its branch.
-
Active Consensus Mana: The active consensus Mana is defined as the sum of the consensus Mana of all nodes that issued messages during the second last complete epoch
cepoch-2, before the current epochcepoch. We say that a node that has not issued a message within that epoch has 0 active consensus mana. See Section 5.3 - Mana.
To be clear a node cannot be a supporter of two conflicting transactions. If it approves two messages with conflicting transactions, it supports the one it more recently references (with respect to the timestamp). In the case where the node more recently supported an incompatible message in a different conflict set, then it doesn't support any of the messages. When a new message is booked, the node goes to the message's branch in the branch DAG and walks through the branch's history giving support to all the conflicts in its past cone and revoking support from conflicting branches.
Image 6.4.1: An example of how the propagation will look like.
In Image 6.4.1, the green node issued message 1 and attached it to Branch 1.1 + Branch 4.1.1. Thus, green node is a supporter of Branch 1.1 + Branch 4.1.1, and it's also a supporter of the parent branches, which are (from top to bottom) Branch 4.1.1, Branch 1.1, Branch 4.1, Branch 1, and Branch 4.
Later, the green node issued message 2 and attached it to Branch 4.1.2. This makes the green node a supporter of Branch 4.1.2, however, Branch 4.1.1 is conflicting with Branch 4.1.2, which makes green node not a supporter of Branch 4.1.1, and therefore the support to Branch 1.1 + Branch 4.1.1 is removed as well.
Finally, green nodes issued message 3, which is in Branch 2. Now the green node is a supporter of Branch 2, and no longer a supporter of Branch 1, since Branch 1 is conflicting with Branch 2. Note that, this supporter removal will propagate to child branches. Thus, green node is removed from Branch 1.1.
Since Branch 3, 4, and both of their child branches have nothing to do with this attachment, the supporter status remains.
The approval weight of a conflict (resp. branch or message) is the dot product of the vectors of supporters and the normalized consensus Mana vector (see Section 5.3 - Mana). Equivalently, the approval weight is the proportion of active consensus Mana that belongs to the supporters of the conflict (resp. branch or message).
We will use
-
Approval weight range: The approval weight is always between
$0$ and$1$ , and thus can be expressed as a percentage. -
Approval weight equivalency: For a conflict
$x$ attached once in a message$m$ , the following are the same: the approval weight of$x$ , the approval weight of the conflict branch defined by$x$ , and the approval weight of the message$m$ . -
Tangle Monotonicity: The approval weight of a message is smaller than its past cone, i.e. if message
$x$ approves message$y$ , then$\text{AW}(y)\geq \text{AW}(x)$ . -
Branch Monotonicity: The approval weight of a branch is greater than the branches in pastcone on the branch DAG, i.e., if branch
$B$ contains branch$C$ , then$\text{AW}(C)\geq \text{AW}(B)$ . -
No Time Monotonicity: The approval weight of a fixed message or branch
$x$ does not necessarily grow with time because of the nodes' active consensus Mana fluctuates and support can be revoked. -
Approval weight inequalities: For any message
$m$ and its branch$B$ , we have$\text{AW}(B)\geq \text{AW}(m)$ . Similarly, for any conflict$x$ within a branch,$\text{AW}(x)\geq \text{AW}(B)$ , since any supporter of the branch$B$ is a supporter of$x$ .
Observe that the non-monotonicity on time is actually desirable, as otherwise it would not be possible to orphan malicious or non-preferred conflicting messages.
Finality in IOTA 2.0 must always be considered as probabilistic, in the sense that a final message is included in the ledger with a very high probability. Two desired properties in a finality criterion are a fast confirmation rate and a high probability of non-reversibility. We use interchangeably the terms "finality" and "confirmation". We now present the proposed criterion for finality.
-
Branch Finality/Confirmation: A branch
$B$ is considered finalized (or confirmed) if its approval weight is at least$0.5$ higher than any conflicting branch. The master branch is always finalized. -
Message Finality/Confirmation: A message
$m$ is considered finalized (or confirmed) if$\text{AW}(m)>0.5$ and its branch is finalized. - Transaction Finality/Confirmation: A transaction is considered finalized (or confirmed) if both its message and its branch are final (confirmed).
Because of the Tangle monotonicity property, if a message is finalised, its entire past cone is finalised as well.
The approval weight of the branch is updated whenever the supporters are updated. However, it is impractical to store the supporters of every message, and even calculating it on demand is unfeasible, since the computational cost of doing a future cone search to determine its approvers is immense. To ease this calculation, we make use of the markers tool, see Section 4.7 - Markers, to approximate the approval of a message weight in an efficient way.
Markers are basically chains of indexed messages, and each message is associated with the most recent marker it approves and the oldest marker that approves it. When a new message arrives, the approvers of each marker can be updated by traversing the much smaller marker DAG and, from the Tangle monotonicity property, we know that if the marker achieve a certain value of approval weight, the message it approves will have a higher value.
Using those properties, we can define a lightweight criterion which we call Markers Application to Finality:
- The supporters of any mark are tracked, which is made easier by the metadata associated to each marker, see Section 4.7 - Markers.
- If any marker reaches message confirmation, we give the "confirmed" status to all messages in its past cone, and hence transaction confirmation to all transactions it may contain.
- If a tracked marker reaches age
FinalityMaxAgewithout achieving confirmation, it will receive the status "Orphaned".
Via finality, the approval weight is also used in conjunction with the fast probabilistic consensus (FPC) and to determine which branches should be considered for tip selection. To do this we have the concept of branches and conflicts being "liked".
- Liked conflict: A conflict is liked (or individually liked) if either:
- The opinion of the transaction is
trueand thelevelis either 2 or 3 (i.e. FPC has terminated withlikedstatus, see Section 6.1 - Objects of Consensus) AND it does not conflict with a finalized transaction. - The conflict is finalized.
- The opinion of the transaction is
- Individually liked conflict branch: A conflict branch is individually liked if the conflict defining it is liked.
- Monotonically liked branch: A branch is monotonically liked if all of its conflicts are liked. Equivalently, a branch is monotonically liked if all of its conflict branches in its branch past cone are individually liked.
FPC initially determines which conflicts are liked. However, nodes that are syncing and missed the FPC voting will default to the conflicts which are finalised. Decisions about each conflict set are carried out by FPC individually and so we separate between "individually liked" and "monotonically liked". Branches that are monotonically liked have their entire history liked and can be included in the strong past cone of messages. Monotonically like branch IDs will thus receive more supporters and thus eventually become finalised.
Note: Once a branch gets confirmed, the conflicting ones receive the status "Rejected".