mina

How Does The Mina Protocol Achieve Consensus?

ChainSafe Systems

Oct 3, 2022 — 8 min read

Authored by Timothy Hao Chi Ho

This post gives a brief overview of how the Mina Protocol maintains a shared and valid view of the state of the blockchain in the presence of multiple participating and potentially malicious peers.

Target audience: You know the basic architecture of any popular blockchain implementation, such as Ethereum or Bitcoin.

This post was originally written by a Mina contributor from the ChainSafe team.

Consensus in a blockchain

A blockchain is made up of blocks, an abstraction that batches transactions and state changes together in a distributed ledger maintained by a network. Additionally, all blocks also contain the hash of the previous block, which is essential for maintaining the tamper-proof property of a blockchain. These elements together then become your digital ledger. But this on its own is not enough to maintain a valid view of the chain. The next important element in the blockchain is to ensure the ledger does not fall under the control of any one central authority. Otherwise, it would function similarly to a database controlled by a central entity.

To avoid this scenario, the responsibility of updating the ledger is shared across nodes in the network. With the decision-making process distributed, all participants need a way to agree on the legitimacy of the data or state in the ledger. This is where a consensus mechanism is needed to make sure all the nodes/peers in the network share the same viewpoint eventually.

On Mina, the consensus algorithm is inspired by Cardanos' Ouroboros family of proof-of-stake (PoS) algorithms. It is called Ouroboros Samasika, which means succinct in Sanskrit (संक्षिप्त).

Forks and consensus

With every node independent of each other in a peer-to-peer network, consensus is the key mechanism that allows the nodes to get a shared and valid view of the world. For a blockchain node to update its state, each node requests the most recent blocks from its peers. Once they receive the blocks, one of the key phases in consensus is how a given node arrives at the canonical chain by selecting which chain or block to build its chain on top of. This choice is what may introduce a temporary fork in the network, i.e., multiple conflicting chains. Forks can happen due to many reasons:

Node being offline
Networking latency
Protocol upgrade (soft/hard forks)
Malicious nodes
Duplicate proposals - ouroboros is non-byzantine fault tolerant (BFT) and conducts local block producer elections rather than network-wide ones

In contrast to Bitcoin's proof-of-work (PoW) algorithm, Mina uses the PoS consensus algorithm to arrive at a canonical state in the event of forks. To set context for consensus in the Mina protocol, in the next section, we'll go in brief on the lifecycle of a blockchain node performing state synchronization with respect to other peers in the network.

Syncing a node

This section describes the bootstrapping process for a blockchain node in a general setting and is not specific to Mina. We'll take the case of a new node joining the network.

A node (say X) always starts up with the genesis block of the network.

The genesis block is the only block that all nodes can accept as their first state transition. Genesis block parameters are usually hardcoded in the node. As node X connects to peers on the network, it goes into a bootstrap mode and tries to sync with the network to the valid chain or the most recent valid state transition. In the process, other peers in the network may have different views of the network. As a result, X is presented with all possible chains or state transitions in the network. In a traditional blockchain/cryptocurrency implementation, node X cannot possibly tell which is the correct branch to choose from - just the most recent blocks. If it were possible, it would be the same situation as having a central authority providing information on the correct chain.

The same situation would apply to a node that has been, say, offline for a year and has recently rebooted itself in order to sync with the network.

Case 2 of syncing a node is when a node is offline. Post-being-offline, when a node (say Y) boots up, it receives n number of chains and now has a multitude of chains (let's call them candidate chains) to choose between. Now, being a decentralized network where anyone can participate, it might also be the case that a retrieved candidate chain might be from a malicious node that has created its own history from the genesis block and has more or an equal number of blocks compared to a valid chain. This, as we know, introduces a fork in the network. It's important to note that a node also has built-in consensus checks that prevent it from ever accepting an obviously wrong chain, e.g., a block producer/miner that was not authorized in that slot or did not meet the PoW requirement or some invalid transaction was included. These types of chains will always be rejected by a properly functioning (non-modified) node.

Forks can be intentional to evolve/upgrade the network or, as we have learned, can be malicious. In the case that it's a malicious fork, based on how far back in time a fork has occurred, we can divide them into two kinds:

a long-range fork, where the blockchain has been forked long ago
or a short-range fork, where the fork was created near the most recent blocks

To distinguish between them and to choose the correct and canonical chain, Mina approaches it in the following phases:

Distinguishing between the short-range and long-range fork
Depending on the fork duration, applying the short-range fork or the long-range fork rule

In the next section, we'll go over them in brief. But before we explain them, it's important to understand the notion of an epoch in Mina.

Mina consensus in brief

Before we understand how Mina arrives at consensus, we need to understand the idea of an epoch in the ouroboros family of consensus algorithms. All ouroboros consensus algorithms divide time into slots and epochs. An epoch is a discrete chunk of time used to categorize and identify events and state updates as they happen in the Mina network.

💡 An epoch is used to mark changes in the set of validators (key rotations, new validators, validators being removed) to quantify important events in the network. Put in another way, epochs exist to provide boundaries between staking distributions and randomness so that with additional rules, staking distributions and verifiable random function (VRF) randomness cannot be manipulated by an adversary.

Each epoch is divided further into slots. It is within these slots that a block producer may get elected to produce a block. In the diagram below, we have the current canonical chain on the left. For a given epoch during consensus, slots 1 to 4 have had a few blocks produced, but only the canonical block will be considered. To decide between multiple blocks produced in the same slot, the chain selection algorithm, aka ouroboros samasika is used to decide how the canonical chain will get extended.

To handle forks, the ouroboros family of consensus algorithms relies on the history of the chain all the way back to genesis to resolve the fork. But since Mina is a succinct blockchain (all history of previous blocks is combined into a single state of finite size using recursive snark proofs), we don't have historical information. Instead, Mina uses checkpointing around the epochs to help the node identify forks in the network.

Enter checkpointing

Mina uses a concept called decentralized checkpointing to decide whether the fork is a short-range or a long-range when deciding between the candidate chain. A fork is short-range if it occurred less than n blocks ago. Since Mina is a succinct blockchain, it relies on the history of the last few 100 blocks to resolve forks. Moreover, the information of the last few 100 blocks is contained within the top block's consensus data.

To achieve this, each epoch is split into three parts with an equal number of slots. The first 2/3 of the epoch is called the seed update range because this is where the verifiable random function (VRF) is seeded. Think of VRF as a cryptographic lottery. Seeding a VRF ensures that we don't get duplicate hashes.

💡 A Verifiable Random Function (VRF) is a public-key pseudorandom function that provides proof that its outputs were calculated correctly. [ref: wikipedia]

The idea of decentralized checkpointing is that each chain maintains two checkpoints in every epoch. These checkpoints are simply the hash of previous blocks' consensus state (state hash) and start as hardcoded values in the genesis block. These checkpoints are used to estimate how long ago a fork has occurred:

Start checkpoint - State hash of the first block of the epoch
Lock checkpoint - State hash of the last known block in the seed update range of an epoch (first 2/3 of an epoch, not including the current block)

Using the above state hashes, a fork is considered short-range if either:

the fork point of the candidate chains are in the same epoch
or the fork point is in the previous epoch with the same lock_checkpoint

Anything before the previous epoch's lock_checkpoint is a long-range fork.

When we have a short-range fork, we end up choosing the longest chain. Otherwise, it's a case of a long-range fork, and we need to rely on additional states to decide between candidate chains. This is taken care of by a part in the consensus state called the chain density.

Sliding window and chain density

To recap, when the fork is beyond the lock checkpoint of its previous epoch, we have a long-range fork.

In the case of a long-range fork, the malicious node eventually ends up creating a denser chain. However, the malicious node will have a lower density (or density that is equal to the canonical chain) initially because the node will have a less active stake than the real network - assuming the malicious node has a less active stake than the real network. Thus, we can only rely on the density difference in the first few slots following the fork, the so-called critical window. The idea is that the density for an honest chain's critical window should be overwhelmingly likely to be higher within this window because this chain contains the majority of stake.

This critical window is the time (or a portion of the epoch) where if a malicious node tries forking a network, it would likely have a lower density for a while since the main chain would have more blocks produced. So in this window, the honest chain would have a higher minimum window density, whereas the adversarial chain's density would be a lot lower.

The long-range fork rule simply uses the critical window density value to allow the network to resolve the fork and selects the chain with the higher minimum density. However, there are a lot of nitty-gritty details as to how this happens, which we intend to cover in a future blog post, should there be interest. For the curious, the technical specification goes into more detail and is an ongoing effort to put together an accessible description of Mina's Ouroboros Samasika consensus algorithm.

Conclusion

Chain selection is essential for a stable node operation and makes sure all nodes in the network have a unified view of the world state.

Beyond this, there are a lot of specific details to checkpointing and the sliding window density components of Mina's consensus state. If there's interest in learning more, please let us know in the comments.

About ChainSafe

ChainSafe is a leading blockchain research and development firm specializing in infrastructure solutions for web3. Alongside its contributions to major ecosystems such as Ethereum, Polkadot, Filecoin, Mina, and more, ChainSafe creates solutions for developers and teams across the web3 space utilizing our expertise in gaming, bridging, NFTs, and decentralized storage. As part of its mission to build innovative products for users and improved tooling for developers, ChainSafe embodies an open source and community-oriented ethos to advance the future of the internet. To learn more, click here.