Consensus on the Mina Blockchain
Since writing this post, Coda has rebranded to Mina Protocol. I’ve left the article in its original form but all references to Coda are equivalent to Mina.
Coda is a succinct blockchain where full nodes only require downloading and verification of a tiny proof to ensure that the state of the blockchain is valid. It achieves this through incrementally computed SNARKs where the latest block contains a proof that validates the new block in addition to the previous SNARK.
For the full technical details of Coda’s consensus mechanism consult the Coda technical whitepaper.
Coda utilizes a proof of stake (PoS) consensus mechanism as opposed to the proof of work (PoW) consensus mechanism popularized by Bitcoin. PoS consensus algorithms have unique challenges, most notably the nothing at stake issue. Whereas in PoW, miners are forced to complete work that expends energy and has a cost, in a PoS system it is essentially free to participate, and an adversary can try different things to see what is favorable at no cost.
While there are a variety of PoS consensus algorithms, none of the existing solutions either provide security guarantees or are not suitable for use in a succinct blockchain that requires bootstrapping from a genesis block in a trustless manner.
Determining consensus in Coda
In Bitcoin and other PoW blockchains, consensus is determined by selecting the longest chain, which has the most cumulative work backing it. Given the nothing at stake issue, in a PoS system, this isn’t always feasible where an adversary may have modified the staking distribution in their favor to potentially produce a longer chain.
In Coda, there are two separate chain selection rules depending on how long ago in time a fork occurred. Firstly there is a short-range fork, which is a fork that occurred recently (fuller definition follows). In this case, we can determine that an adversary would not have had a chance to modify the stake distribution and so we can simply select the longest chain.
However, for forks that occurred an arbitrarily long time in the past, known as a long-range fork, no assumptions can be made as to the stake distribution. Therefore it is entirely feasible that a longer adversarial chain exists, and we can’t simply choose the longest fork. Imagine the case of a new node in Coda bootstrapping from the genesis block, how do they know which chain to select if they can’t simply choose the longest chain? In some PoS systems, a trusted third party may provide this information via checkpoints, but clearly, this adds some centralization risk. To understand how this is solved in Coda, we first need to understand how this is handled in Ouroboros as Coda builds on top of this foundation.
From Ouroboros to Ouroboros Samisika
Coda is based on the Ouroboros PoS consensus mechanism developed by IOHK, and in use on the Cardano blockchain. This consensus protocol has been through several iterations from Ouroboros, the original protocol that worked in a synchronous setting i.e., nodes are always online. Next came Ouroboros Praos, which allowed nodes to join and leave in a semi-synchronous setting and is also secure against adaptive attackers. Finally, Ouroboros Genesis solved the issue of bootstrapping from a genesis block without involving a trusted party.
The key finding from Ouroboros Genesis is in distinguishing between competing long-range forks and in considering only the blocks immediately after the fork point. Here, before the attacker has a chance to modify the staking distribution, we can look at the density of the chain, or, more simply, the number of blocks immediately after the fork point. On competing chains, assuming a majority of the stake is honest, there will always be a higher density on the honest chain. The Ouroboros Genesis paper includes a security proof to this effect. Now, an honest node simply needs to select the chain with the highest density when determining between multiple forks when bootstrapping from a genesis block.
While this idea of selecting the chain with the highest density is compatible with Coda, we don’t know when the fork occurred in the past, and as we don’t have a chain history (Coda is a succinct blockchain after all), we need an alternate means of determining and storing the chain density after the fork point. However, before we discuss how this is resolved, let’s review how block producers are chosen in Ouroboros and, by extension, Coda.
Block production
Coda implements a block producer selection very similar to Ouroboros. In Coda, time is divided into epochs and each epoch into a slot. On the last testnet (3.2b), each slot was 3 mins in length, and there were 480 slots in an epoch, resulting in an epoch length of 1440 mins or 1 day.
In Coda, there is no minimum staking amount, and anyone can stake (or delegate their stake). The chance of producing a block for a slot is proportional to your stake. The stake distribution is determined at the last block of current epoch-2 (so any recently acquired or delegated stake, for example, would have to wait a while before being considered). For example, if the current epoch is 10, we would consider the stake distribution at the last block of the 8th epoch.
The opportunity to produce a block for a slot is determined by a verifiable random function (VRF), which can be thought of as a lottery. Each block producer independently runs this function for each slot, and if they get a VRF output greater than a threshold proportional to the producer’s stake, they get the chance to produce a block at the designated slot.
Existing producers on the Coda testnet can monitor this by viewing the log output, where you can see this lottery function running. In the example below epoch 34, slot 365 was a “winner,” and assuming the node stays online and synced will be eligible to propose a block for that slot. In the current implementation of Coda, VRF evaluations are completed once at the start of the epoch and after a block has been produced. Only the next winning slot will be displayed (though you can win multiple slots per epoch).
The VRF function takes as input a random seed in addition to the producer’s public key and current stake distribution and is deterministic i.e., will always return the same output regardless of how often it is run.
Notably, this process is secret, in that only the private key holder can determine the VRF output, and hence only they know when they are to produce a block. This aids security as it is impossible for an adversary to target a known block producer at a certain slot e.g., by a denial of service or targetted attack. As a result, it also means that multiple producers can be selected for the same slot.
If multiple producers produce a valid block for the same slot, this will produce a short-range fork where the consensus rules are to select the longest chain. If there are only equal length forks, in the current implementation of Coda, a node will accept the first-seen block but replace it if an alternative is seen with a larger VRF output. Hence the process for selecting between multiple producers for the same slot is random, albeit practically a block that is propagated faster has a greater likelihood of being built upon and hence becoming part of the longest chain when the fork is resolved.
If multiple blocks are seen by the same producer, all unique blocks will be broadcast with ties being resolved by comparing hashes of the block protocol state hash. This process is deterministic so all nodes will agree on the same block if there are multiple blocks proposed by the same block producer. There is no double signing penalty, common in other protocols, for producing multiple blocks with the same key.
If a producer is chosen for a slot, they are eligible to propose a block for the designated slot, and if selected for the canonical chain earn the associated coinbase rewards and transaction fees. In Coda, the correctness of the VRF evaluation can be calculated in the SNARK, so other nodes only need to verify the SNARK to know that the block was proposed by a slot winner. This block will only be considered valid if it is received within the maximum acceptable delay of the network (which in the latest testnet was 9 mins). This delay is included to thwart any potential disruption of the network by an adversary. In addition, to ensure the network can “catch up” in case of such delays of messages, empty slots are introduced as an artificial way to provide short periods of silence. On the latest testnet, this value, known as f, is set to 0.5 i.e., 50% of all slots should be empty.
Finally, making the slot leader selection fair and secure requires a good source of randomness as input for the VRF. This is obtained by hashing the output of the VRF function of block producers for the first 2/3rd of the previous epoch (current epoch -1). This output from the blockchain itself becomes the randomness for the next epoch (which is the origin of the name Ouroboros). As a result, the blockchain gets new randomness at every epoch.
Solving for the long-range fork
Now we understand how blocks are produced we can revisit the question of how to determine between forks that occurred at an arbitrary distance in the past where we have no chain history and can make no assumptions as to the stake distribution (and hence longest chain).
The major issue with a long-range fork is knowing which information to store when we don’t know when the fork occurred. This typically isn’t an issue for a non-succinct chain that has the full history available.
This is solved in Coda through utilizing a sliding window of slots where we determine the minimum chain density i.e., the minimum number of blocks seen for each slot window and store that information in each block.
The Coda technical whitepaper provides a security proof (assuming an honest majority and minimum threshold of active stake) that given a slot window length greater than a critical window and shift size, we can choose the chain with the largest minimum chain density. That is, assuming there is an honest majority the honest chain will always have a higher minimum chain density.
The challenge is in determining the size of the window where we only compare the total number of blocks following the fork where the adversary wouldn’t have had a chance to affect/skew the block distribution yet. This critical window needs to be long enough to tell the distributions apart, but not too long as we cannot guarantee the density on the adversarial chain. The resulting sliding window length should be slightly greater than this critical window length. As the chain progresses, the window then shifts by a fraction of its size, and at each block, the minimum density for the window is determined and compared to the minimum ever seen, updating if this value is lower.
As a result, any node is going to follow the chain that has the highest minimum density, even if it is not the longest chain.
Short-range forks
As noted earlier, with a short-range fork, we can simply choose the longest chain (or in the case of an equal length chain choose arbitrarily).
This leaves the final question, what constitutes a short-range fork? In Ouroboros, it is considered a short-range fork if it occurred < k blocks ago. However, in Coda, due to its succinctness, we can’t simply store the last k blocks as this is inefficient. Instead, this is resolved by storing two checkpoints in each epoch that can provide an estimate on how long ago the fork occurred. A start checkpoint is determined at the beginning of every epoch and a lock checkpoint, which is set to the last block of the first 2/3rd of an epoch. As a result, the lock checkpoint always increases until the last 2/3rds of an epoch where it is frozen. The checkpoints can then be compared between competing chains to determine when the fork occurred.
If the fork was in the current epoch, then it is considered a short-range one. As the block producers were already determined by the prior 2/3rd of the previous epoch, an adversary cannot have affected the distribution, so we can just choose the longest chain.
Alternatively, if a fork is in the previous epoch but has the same lock checkpoint, we can again assume the block producer distribution is well distributed even after the fork, so we can assume a short-ranged one and simply select the longer chain. For all other cases, a fork is treated as a long-range one and resolved by checking the minimum chain density for competing chains and choosing the one with the highest.
Sample block output
We can view the consensus configuration and block output from a sample block from the latest testnet. All of this data is available from the GraphQL API. This output shows the minWindowDensity in addition to the last block producer’s VRF output and start and lock checkpoints used for updating randomness and determining chain selection rules, respectively.
