A New Consensus Model: Nakamoto Consensus on a DAG

16.10.2023

IOTA 2.0 Introduction Part 6

TL;DR:

This article delves into the IOTA 2.0 consensus mechanism, an evolution of the Nakamoto consensus. It focuses on vote propagation and validation blocks in the Tangle. It explores how nodes vote on a single view of the ledger state through a committee of selected validators. The weight of votes ensures security against malicious actions, while the uniform random tip selection algorithm dictates the structure of the Tangle. The article also covers consensus flags, slot commitment chains, conflicts, and the chain-switching rule.

In digital ledgers shared across several nodes, a fundamental challenge arises: How can everyone agree on what’s stored and valid in the ledger? This agreement ensures consistent views among nodes, and this is where a consensus mechanism comes into play.

The new IOTA 2.0 consensus protocol represents the next evolutionary step of the Nakamoto Consensus, initially popularized by Bitcoin. This blog post describes IOTA’s consensus mechanism: For a more detailed view, consult the Wiki version of this article, to be published on October 17th.

Adapting the Nakamoto Consensus

In Bitcoin, blocks are linked together in a sequential chain. This is the backbone of the Nakamoto consensus, which resolves disagreement among forking blockchains by favoring the longest or heaviest sub-chain.

Now envision a scenario where agreements aren’t limited to a chain of blocks but expand into a dynamic web of interconnected blocks — a Directed Acyclic Graph (DAG). As we’ve seen in Data Structures Explained: The Parts that Make the Tangle, the IOTA network’s underlying data structure, known as the Tangle, is a DAG where each block is linked to multiple preceding blocks.

Network disruptions and malicious participants can lead each node to have a distinct view of the Tangle, potentially resulting in disparate ledger versions. The IOTA 2.0 consensus protocol applies a robust and efficient method for nodes to collectively vote and agree on a single view of what is valid in the Tangle. This builds upon Nakamoto’s concept, integrating it with the idea of the heaviest subDAG, creating a more adaptable consensus model.

How do nodes vote on the Tangle?

In IOTA 2.0, each node plays a role in consensus. When creating a new block, the issuer attaches it to existing blocks so that the new block encodes the node’s opinion about valid blocks and transactions in the Tangle. Essentially, a block votes on the validity of the blocks it is attached to and adds to the validity of the preceding blocks.

For secure and efficient voting, the IOTA network relies on votes written in validation blocks. As explained in the next blog post,Confirming Blocks: How Validators Operate, these blocks are issued by the validator committee, which is chosen via the staking mechanism. Each committee member can issue validation blocks at regular intervals. This property, coupled with the limited committee size, facilitates swift and efficient decision-making.

A validation block’s vote carries the weight of the respective validator, which is determined through the committee selection procedure. Adding up the weight of blocks that validate a specific block or transaction yields the Approval Weight. This weight determines the inclusion of consensus flags for blocks and transactions (more about flags later).

Conflicts and the ledger DAG

IOTA 2.0 employs the Unspent Transaction Output (UTXO) model for processing and registering transactions. Transactions consume outputs and generate new ones corresponding to the transferred and remaining value.

This has two advantages. First, it is easy to map the history of funds by associating the blocks with the transactions that generated and consumed a UTXO. These associations between blocks allow us to create the Ledger DAG, as it represents all the changes in the ledger made by blocks.

The second advantage of the UTXO system is that it allows us to easily identify conflicts, as they can be simply defined as different transactions that consume the same UTXO! The UTXO protocol prevents many complex double-spend scenarios that account-based ledgers face, such as when four transactions consume funds that are enough for only two of them, creating many different scenarios for resolution.

The third advantage of the UTXO model is that different outputs are independent of one another, so they can be spent in parallel.

We’ll see more details about the potential of the UTXO protocol in UTXO vs. Accounts – Merging the Best of Both Worlds, Part 14 of this blog post series, to be published on November 15th.

Tip selection

Now that we’ve seen how conflicting transactions are defined and nodes’ votes are propagated, how do nodes construct the Tangle and decide which conflicting transactions should be added to the ledger?

Recall that each block represents the issuer’s opinion, propagating along the block’s past in the Tangle. Ideally, a node would reference every other block in the past that it considers to be “eligible” (i.e. successfully processed and “gossiped”, or shared). However, because the amount of references necessary for every eligible block is unfeasible, the Tip Selection Algorithm (TSA) chooses a few references at random.

The TSA dictates the “topology” or structure of the Tangle. The aim is for every node to select the minimum number of references necessary to create a diverse Tangle. This means avoiding any predetermined patterns dictating which blocks are referenced by specific nodes. The TSA is also designed to satisfy the principle that any block should be able to be quickly referenced by all tips; luckily, when nodes choose tips at random, referencing two blocks is sufficient (although the protocol allows for more references if the nodes prefer to do so: more references can enhance Tangle connectivity and confirmation speed).

Once tips are chosen, nodes can attribute different reference types to various tips. This allows nodes to cast their votes on conflicting transactions: transactions with the largest Approval Weight receive support. For more details, check out our Consensus whitepaper.

In summary, IOTA 2.0 uses a uniform random selection of references restricted to eligible blocks because it is simple, lightweight, and fulfills the requirements for opinion propagation in the Tangle.

Consensus flags and slot commitment chains

So now we know how blocks are chosen to be processed by the consensus mechanism. But how is consensus itself actually achieved?

The consensus mechanism is all about reaching an agreement on the status of blocks and the transactions they contain. Consensus is facilitated by the use of consensus flags and slot commitment chains Before we talk about them, let’s briefly talk about supermajority

A supermajority is used to define good proportions of the committee for the flags and is separated into two types: online supermajority means that the voting weight of over two-thirds of the committee members satisfies a given condition, while total supermajority means that the voting weight of over two-thirds of committee members satisfies a given condition.

This separation between online supermajority and total supermajority enables a continuous operation of the Tangle. The online committee enables a preliminary consensus to be reached and commitments to be generated. However, if the consensus is based on a total supermajority, it can be halted if a significant portion of the committee goes offline. For more details on this, look out for our blog post on Dynamic Availability, to be published on November 2nd.

But what are consensus flags? Consensus flags represent confidence levels about whether a block is successfully gossiped and included in the Tangle by the network, striking a balance between safety and liveness for effective network management. “Acceptance” is live and used to determine which blocks will be included in slot commitments, while “Confirmation” and “Finalization” are related to the safety of the network, and are the ones that users will rely on.

Pre-Acceptance Flag: A block is given this flag when an online supermajority of the committee votes for it.
Acceptance Flag: A block (or transaction) is given this flag when an online supermajority of the committee votes for it with Pre-Accepted validation blocks. This flag favors liveness and works adaptively fast under all network conditions.
Pre-Confirmation Flag: A block is given this flag when a total supermajority of the committee votes for it. It signifies a higher level of approval compared to the pre-acceptance flag, but it is raised slowly under bad network conditions.
Confirmation Flag: A block (or transaction) is given this flag when the total supermajority of the committee votes for it with Pre-Confirmed validation blocks. This flag favors safety and it can be slow under bad network conditions.
Finalization Flag: A block (or transaction) is given this flag when its commitment is included in another block that gets confirmed.

We learned about commitment and slots in Data Structures Explained: The Parts that Make the Tangle. Here we expanded on these concepts, as now we know that accepted blocks and transactions are included in the slot commitments of new blocks.

The purpose of commitments is to simply enable nodes to compare their views of what is valid. Different visions of what should be considered valid (and thus confirmed and finalized) can be represented by the nodes in a tree, from where we can extract chains that represent a possible opinion of the nodes. These are the slot commitment chains, which you can learn more about in “Finality: How Nodes Sync the Ledger”, published on October 25th.

Chain Switching Rule

How does consensus work in challenging circumstances like network disruptions?

Network delays could cause nodes to perceive different blocks as accepted, leading to forking slot commitment chains, which are similar to forks in traditional blockchains. To handle these divergences, IOTA 2.0 uses a strategy similar to the Nakamoto Consensus, where the longest or heaviest sub-chain is favored.

More specifically, each node tracks and updates its own slot commitment chain while checking slot commitments in blocks from other nodes. The consensus protocol embraces a simple yet effective strategy: nodes assess the cumulative weight of their slot commitment chains and privilege the chain with the latest finalized slot commitment and the heaviest weight. When nodes on the minority chain recognize the majority chain, they switch to the majority chain after their current slot concludes.

The cumulative weight of a slot commitment chain is determined by adding the weights of all slot commitments within that chain. A slot commitment’s weight is calculated based on the voting weight of validators who agreed on it during a short period.

Once the network is healed, the Chain Switching Rule navigates all nodes to the heaviest slot commitment chain, enabling the continued process of confirmation and finalization. This mechanism allows IOTA 2.0 to uphold consensus even when facing dynamic challenges caused by network discrepancies.

Tip of the iceberg

And so we conclude our journey through the consensus mechanism of IOTA 2.0. But beware: this is just the tip of the iceberg. To learn all the technical aspects of how the consensus mechanism works, watch out for the Wiki version of this article tomorrow.

The next blog post in this introduction to IOTA 2.0, published on October 18th, takes a closer look at confirmation and the role of validators and validator committees.