Finality Explained: How Nodes Sync the Ledger

IOTA 2.0 Introduction Part 9

TL;DR:

IOTA 2.0 uses slot commitment chains to achieve consensus and synchronization of its distributed ledger. Each block contains a cryptographic commitment to a specific past time interval called a “slot”. These slot commitments form a chain that ensures nodes agree on accepted data, aid in dynamic availability and fork resolution, and drive finalization for added security. Overall, slot commitment chains play a crucial role in creating a reliable, decentralized, and scalable network for IOTA 2.0.

In any distributed ledger, regular checkpoints are crucial for achieving consensus on an accepted and finalized state – in other words, checkpoints help sync the different records of a ledger among its nodes. Checkpoints also enable data to be compressed into a local snapshot and any unnecessary information to be pruned. IOTA’s solution to create such checkpoints is slot commitment chains.

This advanced blog post dives into the technical nitty-gritty of slot commitment chains and how they help achieve finality by syncing the ledger.

Introduction to slot commitment chains

Every block issued by a node includes a reference to a slot commitment, which is a cryptographic commitment to a specific time interval in the past known as a “slot”. These slots are precisely defined 10-second intervals that do not overlap with one another. The slot commitment encapsulates all the crucial information about that slot, including accepted blocks and transactions. It also commits to the preceding slot’s commitment, effectively forming a linked sequence known as a “slot commitment chain”.

When nodes agree on a slot commitment, they essentially concur on the data accepted by the network until the end of that particular slot. In this way, slot commitments function as checkpoints that nodes can use to synchronize their ledger. Slot commitments and the slot commitment chain allow nodes to synchronize their local versions of the ledger by comparing them with each other. If they are identical, nodes know they have the same information. This blog post explores additional functionalities based on slot commitments.

Structure of slot commitments

A slot commitment is created by combining different pieces of information through hashing. These pieces of information are:

• Protocol Version denotes the protocol version, increased with each protocol upgrade.
• Slot Index indicates the index of a slot to which the commitment of slot content is committed. The slot with this index is considered committable by the block’s issuer.
• Previous Slot Commitment refers to the commitment of the slot with the preceding slot index.
• Commitment of Slot Content is the hash root of a Merkle tree that contains all commitment elements at the slot’s conclusion.
• Cumulative Weight represents the collective weight of validators referencing a particular past commitment, including the cumulative weight of the previous slot commitment.
• Reference Mana Cost (RMC) is calculated from both the slot’s contents and the previous slot’s RMC.

A slot commitment uniquely identifies a committed slot and its contents. Analogous to a block header in a blockchain, each slot commitment references the commitment of the previous slot, creating a slot commitment chain that extends back to the Genesis commitment.

Block header

As shown in the figure below, the slot commitment is contained in the block’s header. This design makes it easier to create an attestation of a slot commitment – a cryptographically verifiable list of nodes that agree on the history of the Tangle up to the respective slot.

Commitment of slot content

An important ingredient of a slot commitment, the Commitment of Slot Content is a hash value calculated as the Merkle Root of the binary tree with the following leaves:

• Tangle Root: The hash root of a sparse Merkle tree that contains all accepted blocks issued within the slot. This serves as a statement of accepted blocks in the Tangle. It is used to prove the inclusion or absence of accepted blocks.
• State Root: The hash root of a sparse Merkle tree containing all Unspent Transaction Outputs (UTXOs) at the slot’s conclusion. It is used to prove the existence or absence of UTXOs.
• State Mutation Root: The hash root of a sparse Merkle tree containing accepted transactions in the current slot and serving as proof of state mutation from the prior slot to the current one. It helps to prove the inclusion or absence of accepted transactions.
• Accounts Root: The hash root of a sparse Merkle tree containing Block Issuer (Block Issuance Credits, Issuer Public Keys, Expiry Slot) and staking data (Fixed Cost, Stake End Epoch, Staking Amounts) for accounts that are staking or are block issuers. It is used to prove the issuance of blocks for a given account ID.
• Committee Root: The hash root of a sparse Merkle tree containing account IDs representing current or upcoming committee members. It is updated only when the committee is successfully rotated. It is used to prove the inclusion or absence of a specific account to the committee.
• Rewards Root: The hash root of a sparse Merkle tree that contains data related to rewards (e.g., pool stake, pool reward, fixed cost) for committee members at the previous epoch’s conclusion. It helps to prove the existence or absence of rewards for a given Staker or Delegator.
• Attestation Root: The hash root of a sparse Merkle tree that contains data related to the attestation of all account IDs at the end of the slot. It is used to prove the attestation of previous commitments by a given account ID.

How are slot commitments generated?

Nodes maintain their own slot commitment chain based on their understanding of the Tangle, which includes accepted blocks and transactions. Each node tracks the online validator committee, which consists of validator committee members who have issued at least one block with recent timestamps and aligned their slot commitment chains with one another. When the online validator committee reaches consensus on accepting all the blocks and transactions within a slot, or when a maximum timeout is reached, the nodes generate the commitment for that slot.

Under normal network conditions, all nodes should observe the same blocks, resulting in the acceptance of the same blocks and transactions. Consequently, this leads to the generation of identical slot commitments by all nodes.

Why are slot commitment chains necessary?

In IOTA 2.0, slot commitment chains are used to create a reliable history of consensus decisions made by the validator committee. These chains serve three main purposes:

1. Synchronization: Slot commitment chains provide a reliable means for network participants to synchronize the content of the Tangle up to the latest committed slot. This feature is particularly useful when initializing a new node, rejoining the network after inactivity, or switching a slot commitment chain.

For example, when initializing a new node, the genesis block of the Tangle serves as the ultimate truth. The node connects with neighboring nodes in the network, either manually or through autopeering, and begins receiving the latest blocks via gossiping.

However, the challenge lies in determining which blocks have been accepted and whether the node’s peers share the same ledger state. The solution is to use the slot commitments included in the received blocks.

As the new node starts receiving blocks through the gossip protocol, it can trace the chain of slot commitments, with each new slot commitment referring to the previous one, creating a chain that extends back to the Genesis block. While the node processes the received blocks, it verifies the commitments for all slots, monitors the evolution of the validator committee through epochs, and identifies the latest finalized slot. This process ensures that the node is synchronized with the network and maintains the ledger state corresponding to the slot commitment.

2. Dynamic Availability and Fork Resolution: The design of the IOTA 2.0 protocol allows nodes to progress the Tangle and the ledger, thereby preserving the network’s functionality and integrity even under challenging conditions such as network partitions or offline validators. Indeed, the acceptance of blocks, transactions, and the subsequent creation of slot commitments rely on the online validator committee’s active participation in the consensus.

However, in challenging network conditions as described above, nodes may not see the same blocks at the same time. This divergence could result in different blocks being accepted, leading to forks or different commitments for the same slots. Forks, in turn, can lead to varying interpretations of the ledger state among nodes, making it challenging to determine which version of the ledger is correct.

One of the significant advantages of using slot commitments is that nodes can quickly identify if some blocks contain slot commitments different from their own. Slot commitment chains make it easier to identify the point in the Tangle where nodes initially disagreed. Nodes can immediately check which chain is heavier and start following the heaviest chain of blocks, i.e., the chain with the majority of consensus. Without slot commitments, it would be difficult to determine the point at which nodes started seeing different blocks and how they need to switch to the correct state. For more about dynamic availability, check out the upcoming Part 12 in this series of blog posts, Dynamic Availability: Protocol-Based Assurances.

3. Finalization: In IOTA 2.0, finalization occurs on the slot commitment level. The committee finalizes slot commitments, along with all the transactions and blocks associated with those commitments.

To finalize a slot commitment, a supermajority (holding more than two-thirds of the voting power) of the committee must reference this commitment in their validation blocks. In addition, all these validation blocks must be issued within the same slot and be confirmed.

Finalization flags are computed by each node based on their locally maintained copy of the Tangle. However, a node’s perception of finalization is represented in the block header, i.e. when issuing a new block, the node includes both a slot commitment of the latest committable slot and the Slot Index of the latest finalized slot commitment in the respected chain. For more on consensus, check out the Wiki article on our consensus model.

How does it work?

To better understand the mechanics of slot commitment chains in IOTA 2.0, let’s delve into the two critical components: the Chain Switching Rule, which addresses the resolution of forked slot commitment chains, and the Heaviest Chain Selection, which explains how nodes determine the heaviest and reliable chain.

Chain Switching Rule

In challenging network conditions, nodes may perceive different blocks being accepted, thus creating different slot commitment chains. Nodes may not even be aware that this is happening until the problem disappears (e.g. the network is merged again) and all nodes in the network see the same blocks. In the following visualization of the Tangle, the forked slot commitment chains resemble forks in a blockchain.

To resolve this, each node tracks and updates its own slot commitment chain and checks the slot commitments contained in blocks received from other nodes. Forks in slot commitment chains can’t be merged as these could lead to inconsistencies and double spending in the set of accepted transactions. Instead, each node selects which slot commitment chain is heaviest. Nodes in the minority partitions switch to the majority chain after their current slot ends, abandoning blocks from the minority chains. The abandoned blocks need to be re-issued by their issuers after they switched the chain.

The Chain Switching Rule enables liveness for the finalization flag in the IOTA 2.0 consensus. Once the network recovers from its divided state and validators are back online, nodes successfully switch to the heaviest chain and the validator committee continues to finalize slot commitments.

Heaviest chain selection

Because each block is signed by its issuer, nodes can create for each slot commitment attestation (commitment-issuer) lists with committed validation blocks that reference a past slot commitment. Attestation lists allow a node to determine the cumulative weight of a slot commitment chain. Specifically, the weight of a slot commitment is computed as the voting weight of validators in the respected attestation list. The cumulative weight of a slot commitment chain is then determined as the sum of the weights of all slot commitments in that chain.

The first step to selecting the heaviest chain is for a node to request the cumulative weight of the received commitment of the fork from its peers. Since the cumulative weight is a part of the tree data structure used to obtain the slot commitment, the required data to be sent is rather small. If the cumulative weight of the fork is lower than or equal to the weight of the main chain, the node discards the fork. In addition, if the last finalized slot for the node happened after the fork started, the fork is discarded.

The first step is done naively without requesting all attestations. To check the correctness of the cumulative weight, the node must request attestation lists for the slot commitment chain after the forking point. If the cumulative weight was computed incorrectly, then the fork is discarded and the neighbor dropped. Otherwise, the node creates a candidate engine for the fork.

If the candidate engine learns that the cumulative weight of the fork is correct, then the node needs to switch engines. It discards the minority chain along with all the blocks and transactions issued after the forking point and puts the heavier one in the place of the main chain.

Our proposed Chain Switching Rule is a distinctive approach compared to fork choice rules in other consensus protocols. For instance, Ethereum’s LMD-GHOST algorithm prioritizes the fork with the heaviest subtree, considering only the latest vote per validator. In contrast, our solution counts validator votes with multiplicity, per chain rather than per tree. Meanwhile, Cardano’s densest chain rule favors the chain with more blocks in a bounded segment following the forking point. In comparison, when selecting between two chains, our Chain Switching Rule gives precedence to the chain with the latest finalized slot commitment. If the two chains are equal, it gives preference to the chain with the highest cumulative weight (without restricting to a segment).

Conclusion

Slot commitment chains are pivotal in achieving consensus, maintaining ledger synchronization, resolving forks, and driving finalization. By enabling nodes to create a reliable and consistent ledger state, slot commitment chains ensure the integrity and trustworthiness of the network, even under challenging conditions.

The next blog post in this series, published on November 8th, looks at the benefits of IOTA’s underlying Directed Acyclic Graph architecture.

IOTA 2.0 Introduction

Part 1: Digital Autonomy for Everyone: The Future of IOTA

Part 2: Five Principles: The Fundamentals That Every DLT Needs

Part 3: Data Flow Explained: How Nodes Process Blocks

Part 4: Data Structures Explained: The Building Blocks that Make the Tangle

Part 5: Accounts, Tokens, Mana and Staking

Part 6: A New Consensus Model

Part 7: Confirming Blocks: How Validators Operate

Part 8: Understanding Congestion Control

Source