Achieving Consensus on the Internet Computer
The asynchronous finalization of the blockchain’s novel consensus protocol is unbelievably fast — finality happens in under two seconds.
By Manu Drijvers, Engineering Manager (Consensus) | DFINITY
Security and reliability are essential to the vision of the Internet Computer — the world’s first web-speed, internet-scale public blockchain, which enables smart contracts to securely serve interactive web content directly into the browsers of end users. The Internet Computer extends the functionality of the public internet so that it can host software, making next-generation dapps and open internet services possible.
The Internet Computer is powered by machines in data centers across the world that communicate through the Internet Computer Protocol (ICP). By collaborating in this way, the machines form a virtual Internet Computer that allows developers to write and deploy pieces of software called canister smart contracts in a secure and reliable way. “Secure” means that the state of a canister will only change according to the rules of the canister and cannot be tampered with, and “reliable” means that the canister will not suddenly stop running.
The Internet Computer achieves these properties using a novel consensus protocol: the different machines, or replicas, must reach consensus on which inputs to process and in what order, such that they maintain a coherent state. Every piece of software is executed by many machines around the world instead of just one; the majority of the machines together define the true state of the software. If some individual replicas report a tampered state, have connection issues, or are even malicious, this will not make a difference as long as the majority of the replicas correctly execute the software.
Additionally, we want the Internet Computer to scale, meaning that we can run more and more decentralized applications in the form of canister smart contracts on the platform. To achieve this scalability requirement, we split the canisters into smaller groups, and each group runs on what we call a subnet. A subnet is powered by many different replicas around the world, and they all execute the canisters running on that subnet. Canisters on different subnets can also communicate securely. We can always add subnets to the Internet Computer, thereby growing its capacity.
Why consensus is important
Any number of replicas could be unavailable or malicious without affecting the correct state of the subnet as long as the majority of machines function correctly. This approach of using replication to gain security requires a consensus protocol. The subnet must process different messages, namely messages from users to canisters and from canisters to canisters. And they must all process the same messages in the same order, such that all replicas always end up in the same state — but each of the replicas that powers the subnet might actually see the messages in a different order. We use a consensus protocol so that all of the nodes that are powering subnets can agree on the order of the messages to process.
We are going to reach consensus by using a blockchain. The messages that the subnet should process are grouped together and placed in blocks, where each block points to a previous block, thereby forming a chain of blocks. The property of security is achieved when all replicas agree on the blockchain, thereby giving an ordering of the messages to execute.
More precisely, we want what we call “safety” — that is, if two honest replicas think that they agree on the blockchain up to a certain point, then they must in fact have the same view of the blockchain up to that point.
Secondly, we want “liveness,” meaning that the blockchain keeps growing and we keep agreeing on more and more blocks and continuously process additional messages.
Thirdly, we want what we call “validity,” meaning that all of the blocks and the messages in the blocks are actually valid. This, for example, ensures that all messages in blocks are correctly signed by the sender.
The difficulty here is that we want these three properties to hold even if some of the nodes powering the subnet might become faulty, go offline, or even be actively malicious. More precisely, we want all of these properties to hold as long as less than a third of the nodes in a subnet are offline or malicious. In the examples below, we will often use four nodes, meaning that we should satisfy these properties if at most one of them is malicious. At Genesis, the Internet Computer will use larger subnets that can tolerate more than one corrupt replica.
We’re going to zoom into a single subnet and see how we use a blockchain to reach consensus, but it’s important to remember that the Internet Computer consists of many subnets, and therefore many blockchains. We will present our consensus protocol by a building on top of a peer-to-peer gossip network. We will often say that the replica “sends this message out.” By that, we mean we use our gossip network to exchange the message with the other replicas on the subnet. We’re also only going to focus on the ordering of the messages. Some other parts of our protocol will take care of the processing of these messages.
It is important to note that we chose to design our consensus protocol by tailoring it to the needs of the Internet Computer. We’re trying to optimize for throughput, latency, and also protocol simplicity. Our protocol contains four main parts:
- First, we have block making. This part creates candidate blocks out of which we can build blockchains.
- Second, we have notarization. This part is responsible for identifying valid blocks out of which we can build valid blockchains.
- Third, we have the random beacon. The random beacon will give us some randomness that we can use to further enhance our protocol.
- Lastly, we have finalization, which will tell us when we have actually reached agreement.
Block making
A replica on the subnet can serve as the block maker, proposing a block to extend the chain. It will have some messages available that should be processed by the canisters that run on this subnet. It might have a blockchain up to a certain height (e.g., 29). It gathers messages waiting to be processed, groups them together into a block, and proposes an extension to the blockchain by sending it on this gossip network to the other replicas.
It’s important to remember that we want this protocol to work even if some participants are actually misbehaving. This means that we cannot elect one single block maker to extend the blockchain because this one block maker might actually be malicious and we could be stuck, which would compromise our liveness. Therefore, we must have many replicas serving as block makers.
Notarization
For the same reason, these block proposals may actually be invalid. To deal with that, we have a notarization process that works in rounds, and in every round it ensures that we have at least one valid block that can extend the blockchain.
As an example, let’s say Replica 1 has a notarized blockchain up to height 29. If it now sees a block extending the blockchain at height 30, it will validate that block. If Replica 1 sees that this block is valid, it might place a cryptographic signature on it that we call the notarization share. The notarization share will be sent to the other replicas and the subnets expressing that Replica 1 thinks this is a good block.
Maybe Replica 3 and Replica 4 might also create notarization shares on that same block. Let’s define that three out of the four replicas is sufficient approval. Note that in this instance three out of four is the highest percentage of approval we can hope to get, where the protocol should make progress even if one of the notes is misbehaving or offline. We combine these three notarization shares into a single artifact, which we call the notarization, meaning block 30 is notarized. The notaries will now move on to the next round and start looking for blocks at height 31.
For these notarization shares, we use special signatures called multi-signatures. Multi-signatures have a nice property that allows many signatures on the same message to be compressed into a single constant-size signature that proves that all of the nodes signed the message. This means that even if we have a very large subnet with many notaries, the notarization will still be a small artifact.
Notarization will not always work as well as just described. The replica might see a valid block and create a notarization share on that block. However, it might now see another candidate block at the same height, which is also valid. If the replica would only sign one of the blocks, we might actually get stuck because some notaries might support one block while others support another block, and neither will ever get enough approval. To satisfy the liveness property, the notary will now actually sign both of the blocks, making sure that at least one of them will become notarized this way. This means that we may obtain multiple notarized blocks at one height.
Random beacon
The block maker and the notary can identify valid blocks, but we have not reached agreement yet because there may be multiple notarized blocks at every height — so what we have might look like a tree of many valid blocks. In order to finally achieve agreement on the blockchain, we are going to reduce the number of notarized blocks that we get every round by adding something to our protocol: the random beacon. At every height, we have a random-looking artifact that we call a random beacon, which is an unpredictable value.
A replica might have a random beacon at height 29 and when the notarization process for round 29 finishes, it decides that it is time to create the next random beacon. It will create a special signature on the previous random beacon value which we call a random beacon share. This is another artifact that we share via the gossip network.
If we now get another random beacon share, we can combine the shares to construct the next random beacon value. We do this by using special signatures, namely threshold BLS signatures. They have the special property that they are unique, which means it does not matter which replicas participate to construct the value. However, they are also unpredictable because the replicas cannot construct that value by themselves. These threshold BLS signatures require special key material where a secret key is shared among the parties, which we set up via a protocol called noninteractive distributed key generation.
Now that we have this common randomness, we are going to use it to rank the block makers every round.
For example, using the random beacon that we created in round 23, we are going to rank the block makers in round 24. At round 24, we can agree that Replica 1 is the top priority block maker (i.e., the rank 0 block maker). Of course we still need to have fallbacks because Replica 1 might not do its job properly. For example, Replica 4 might be chosen as the rank 1 block maker, the first fallback. And if that does not work, then Replica 3 is the rank 2 block maker. And finally, Replica 2 is the last resort. Since the random beacon offers common randomness, all the replicas agree on this ordering of the block makers.
We are now going to use this block maker ranking to further enhance the notary behavior. More precisely, when a notary enters a round, it starts a timer. At the beginning of the timed period, it is only looking to create a notarization share for the block by the rank 0 block maker. Only if that fails after a certain amount of time does the notary fall back to a block proposal from the rank 1 block maker. After another preset amount of time, it will fall back even further to the rank 2 or rank 3 block maker.
By having the notary take the block maker ranking into consideration, the goal is that we reduce the number of notarized blocks that we get every round. Let’s look at an example: Replica 1 is in round 30 and it receives a valid block proposal for height 30, but it is only the rank 1 block maker. It is going to wait because it is not willing to sign the rank 1 block yet. If things go well, it might now receive a block proposal from the rank 0 block maker. Now the notary creates a notarization share on this block, and not on the rank 1 block. If sufficiently many other notaries do the same, then only the rank 0 block will become fully notarized. In this scenario, we actually reduced the number of blocks that become notarized. This brings us closer to consensus.
Now we might still have multiple notarized blocks in some rounds, but hopefully in most rounds, we have only one notarized block from the rank 0 block maker. In fact, if there is only one notary around, then we have actually already reached agreement. This is because a valid chain must exist of notarized blocks in every round and if there is only one candidate block, then every chain that moves past that point must go through that block. Therefore, the chain implied by that block must actually be agreed upon.
Finalization
So the challenge remains: How do we know that we have reached agreement? How can replicas know that they can accept the chain? One option would be for a replica to simply wait for some amount of time and assume that after this time period it will have seen all notarized blocks that exist, and if there is just one notarized block at a height, it considers the chain to be agreed upon up to this height.
But this is a very risky approach. Perhaps the network has not been functioning properly, and there are actually other notarized blocks that we simply have not seen yet. This means that if we do not wait long enough, we may violate the safety property. This puts us in a very difficult position; we want blocks to be agreed-upon quickly such that the subnets are responsive for the user, but at the same time, we know that we need to wait a long time to guarantee the safety property.
We avoid this trade-off by using a different mechanism to observe agreement. We have a separate asynchronous finalization process that helps us detect when we have reached agreement. Remember that notaries create notarization shares until they see that one block is fully notarized, at which point they move on to the next round. Now we are going to have the notaries share some information about how many blocks they notarized, which will help us reach agreement. More precisely, if the notary did not create any notarization shares for blocks other than the first notarized block it received in that round, it will create a different type of signature that we call the finalization share.
A finalization share on a height-30 block from Replica 1 essentially means that Replica 1 did not notary-sign any height-30 block other than this one. This is another artifact that it will gossip to the rest of the subnets. If a sufficient number of replicas also create finalization shares for the same block, then we can aggregate them into a single finalization. Whenever we see such a finalization on the block, we know that we can trust the blockchain up to that point because a finalization is proof that no other notarized block at that height can exist. If the network behaves well, this means that we can actually reach agreement on blocks very quickly compared to traditional blockchains, because we can quickly create these finalization shares and reach agreement. With this asynchronous finalization approach, a block can be finalized in less than two seconds after being proposed.
In addition, we are not at risk of network attacks. Even if the network does not behave well, we know that we are still safe because we only rely on signatures and not on the assumption that we have seen all messages.
A full finalization means that other notarized blocks cannot exist as long as less than a third of the nodes of a subnet are corrupt. Let’s go a little bit into the theory and see why that is actually the case in the scenario with four nodes. We know that if a block is finalized, it means that three notaries created finalization shares on this block because we have four nodes. We assume at most one of them is corrupt, but that still means that we know for sure that at least two replicas were honest and created a finalization share on the block. We also know that honest replicas only create such a finalization share if they did not sign any other block at that height.
That means that two replicas did not create notarization shares for any block other than the finalized one at this height. We also know that a notarization requires three notarization shares. This means three replicas must participate to reach that, but we only have four replicas on the subnet. Additionally, we said that two out of them definitely did not contribute to notarizing any other block, which leaves only two replicas. And two is not sufficient to reach this notarization threshold of three, thereby concluding the proof that finalization implies that there are no other notarized blocks at that height.
This is under the assumption that less than a third of the replicas are corrupt. The above demonstration used a subnet size of four replicas with at most one that was corrupt, but you can easily extend the same argument to “n” replicas out of which “f” are corrupt, as long as “f” is less than a third of “n.”
In summary, we have a consensus protocol that consists of four components. The block maker creates candidate blocks to extend the blockchain. We have a notarization process that ensures valid blocks are identified. We then add a random beacon that we use to rank block makers and reduce the number of notarized blocks we get in every round. Lastly, we use an asynchronous finalization mechanism that lets us know when a blockchain is actually agreed upon without having to rely on networking assumptions altogether.
This consensus protocol allows us to use replication within a subnet, achieving the security and reliability that we want from the Internet Computer.
_____
Stay tuned for more releases detailing the technologies behind the Internet Computer.
