Aarhus University Seal / Aarhus Universitets segl

Distributed Consensus

Distributed Consensus

  • The consensus protocol is an important part of a blockchain 

An important part of a blockchain is the consensus protocol. When a message is sent in a peer-to-peer network, it happens in a flooding manner. If two message are sent at different nodes at the same time, they will arrive at different nodes in different orders. Also, a message is only delivered to the nodes that are connected to the network when the message is sent. So different nodes will see different sets of messages delivered in different orders.

The purpose of the consensus layer is to create order in this chaos. It ensures that all nodes connected at a given time agree on which messages have been sent, and in which order. The basic design principle is to have a so-called lottery mechanism that will occasionally appoint one of the nodes as the next winner. This is done in such a way that the rest of the network learns who the winner is. This winner will then take some of the outstanding messages and add them to a so-called block, in the order in which the winner saw these messages. Then this block is sent to the peer-to-peer network. This block determines what are the next messages in the sequence and in which order they arrived. To prevent that the block can be tampered with, the winner of the lottery signs the block using a digital signature scheme.

Due to the random nature of the peer-to-peer network, the lottery mechanism is such that sometimes there are several winners. When this happens each of them then sends a proposal for the next block. To deal with the confusion thus created, each block is required to include a pointer to what the winner considered to be the latest block at the time it created the new block. This creates a chain of blocks. When there are multiple winners, the chain turns into a tree instead. To deal with this, the rule is that a lottery winner should extend the longest chain in the tree, and in case of a tie, extend the chain it saw first. This will eventually lead to one of the chains growing longer. It is the longest chain that represents the true order of the messages. The branches from this true chain represents alternative short-lived truths that were rolled back, as it is called.

In the figure, we see a network with four nodes. At time 11, and then 12, two different nodes win, and do not have time to see the new block sent out by the winner. Both of them consider the block added at time 8, to be the latest. So we get a branch. Eventually, one of them grow longer, all nodes discover this and jump to this branch. The branch ending in block 15 experiences a so-called rollback.

In Bitcoin, the lottery was implemented by solving hard puzzles, known as proof-of-work. This leads to the Bitcoin network spending a lot of energy. Winning a block is associated with a reward to incentivize nodes to solve the puzzles. This, in turn, makes nodes spend a lot of energy to be the first to solve the puzzle, creating a market where the amount of energy used to solve puzzles automatically goes up with the value of the currency.

One of the research challenges we will consider in consensus, is proof-of-stake lottery mechanisms. Proof-of-stake lottery mechanisms is the name of a class of modern lottery systems that are designed to be millions of times more energy efficient than proof-of-work. Instead of solving puzzles, the winners are picked in proportion to how much cryptocurrency the nodes have stored in the network. The rationale is that the more stake a node has in a system the more likely it is to behave honestly in running the system. We will also design and prove secure completely novel types of lottery systems.

Another research topic will be sharding. In a basic design of a peer-to-peer network and consensus layer, all nodes see all messages. As the network scales up, this leads to inefficiency. Sharding means that the network is divided into possibly overlapping smaller groups, taking care of each their share of the messages. This can lead to dramatic efficiency improvements, and when done right, without loosing security. We will design and prove secure novel modes of sharding.

Another research topic will be finalization. Seen from a user’s point of view, the main problem with a blockchain is the possibility of a rollback. When the order of transactions is changed, a transaction that was valid before, might turn invalid. Say, an account with 100 coins on its account transfers 60 coins to account 1, and 60 coins to account 2. The last of these transactions should be invalid, as we do not want accounts to go negative. But to determine which transaction is last, depends on which order messages are delivered in. This order might change during a rollback. If the owner of account 1 thinks she received 60 coins, and sends off some physical goods to the customer, the goods might be impossible or cumbersome to retrieve when the payment is suddenly invalidated. The purpose of a finality layer is to annotate blocks as final, when they can never be part of a rollback. A shop can then await sending off goods until a payment is final. A research goal is to design faster and more secure finality layers.

There is a large number of other research topics that we plan to look at, within consensus, including better security models and better mathematical specifications of what consensus layers and finality layers achieve.