Diving into Protocol Consensus

You have probably heard about PoW, PoS, and DPoS. They are consensus protocols or consensus algorithm. In the article, I will describe what consensus exactly is, how transactions are inserted into blocks and what are the most important properties of a consensus. I will try to explain it easily without deep details and no math. After reading you should know basic principles and requirements for making consensus in a distributed environment.

Consensus definition

Generally speaking, the distributed network consists of a certain number of nodes that have the same rights related to change data. In the crypto world, data are stored in a ledger. The ledger is in most cases a chain of blocks. The very first block of the chain is the so-called genesis block. To add another block behind the genesis block, and thus change the ledger, requires mutual agreement of nodes in the network. The protocol defines all rules which must be followed to achieve the agreement. If the agreement is not achieved then the ledger is not changed. Adding a new block always requires making an agreement upon the block that is to be added at the end of the blockchain.

Copy of the ledger sits on all nodes and they all have the same version at a given time. Once the agreement is achieved a new block is added into the blockchain on all nodes simultaneously. Thus, the ledger is highly protected against tampering. An attacker is not usually able to change the ledger on all nodes at the same time.

Now you know the purpose of making the consensus. Let’s define the consensus:

A protocol consensus is a set of rules that are used for making a decision between mutually distributed parties.

The rules are implemented by protocol developers. You can find source code for a given project on GitHub if the project is an open-source one. It is the so-called implementation of the protocol and a client is built from the source code. The client is a piece of software that is installed on nodes by their owners. Thus nodes can participate in making the agreement.

As stated above, in our case the decision is made about the addition of a new block. Every block consists of new transactions that must be valid in regard to the blockchain history. The important part of the mutual agreement is the verification of transactions in a proposed block.

Rules for a new block creation

Now you understand that nodes must agree upon a block addition. However, not all nodes might agree. Image one deceptive node that would disagree with all proposed blocks. The network would never add a new block so no transaction would not be processed. A new block is added only when the majority of nodes agree with the addition. It is usually 51% of nodes in PoW or some PoS (Cardano Ouroboros PoS). It is 33% in DPoS networks that are often based on the Byzantine Fault Tolerance algorithm.

A protocol must have some set of rules dedicated to a selection of a node with a right to produce a block. The most effective way is to select one node that will produce a new block and let the rest of the nodes to make a decision whether the block will be added into the blockchain or not. The faster the selection is the sooner a block can be added.

Rules for the selection of a node with the right to produce a block are very different in PoW and PoS systems.

In PoW, there is an open competition between a few groups. Each group consists of a pool operator and all miners who dedicate hash-rate to the pool. The winner with the right to produce a block is selected based on the hash-rate of a given group with a little piece of randomness. It might be said that the higher the hash-rate given group has the more often it produces a block. The winner is selected approximately after 10 minutes of searching. It takes 10 minutes to pick one pool operator from approximately 10 biggest pools. It is not a very effective rule, however, hash-rate is used also for security.

In PoS, there might be used more sophisticated cryptographic tools which are able to generate random number in a second. Thus node with the right to produce a block might be found right away. Only one node, not more.

The disadvantage of the PoW approach is that the competition takes 10 minutes. Thus, only one block is added into the blockchain in 10 minutes what is not much and it will be very difficult to scale the protocol on the first layer. Moreover, more nodes might succeed in the competition at nearly the same time since the propagation of the block on the internet takes some time.

P2P networks have some limitations. See time needed for delivering 2Mb block from London via TCP/IP:

• Paris - 0.1s
• US East coast - 1.1s
• US West coast - 2.5s
• Brazil - 3.0s
• Korea - 3.4s
• Australia - 5.3s

So some node e.g. in the USA continues and succeeds in solving math puzzles at the moment there have already been found a block in China. As a result, a fork is created. There are two proposed blocks and both are valid. The addition of other blocks will eventually decide which branch will stay valid (the famous longer chain rule) and which one will be discarded (including all transactions). It is proposed to wait for the next 6 blocks to be absolutely sure that a transaction is finally settled. The advantage is that the addition of the block requires 10 minutes of work so it is difficult to propose deceptive block. However, PoW rule “the longer chain wins” is mostly about the power of hash-rate and the security is based on an assumption that it is not easy for an individual to collect a huge amount of the hash-rate which would be required for the attack. Bitcoin was decentralized at the early stages but it is rather centralized nowadays. It happened within a few years thanks to ASIC miners and pools.

PoS/DPoS are able to select a node with the right to produce block within a second and a block might also be created quite quickly. So the selected node is able to produce a block nearly immediately it finds that it gets the right to do so and the block gets propagated to other nodes. The whole consensus might be made within a few seconds and mostly the network latency is the biggest enemy to make the process even faster. Another advantage is that a blockchain is not forked if everything works fine. If there is some issue, e.g. with block propagation, consensus rules solve any issue quickly.

It is often said that PoS networks cannot be as safe as PoW since there is no computation effort needed to produce a block. An attacker can create a deceptive block and propagate it to other nodes. Well, why would other honest nodes accept such deceptive block if it was not created by the rules? In the case of Cardano, all nodes can easily verify which node got the right to create a block in a given slot. The block must contain a special number that can know only the node which had the right to produce a block in a given slot. The system based on science and math might be as secure as PoW and still be much more effective in regards to scalability. A high level of decentralization is what makes Cardano secure.

Transaction correctness

The goal of a consensus is to keep one global state (one version of the truth) among all nodes what basically means that the ledger must be consistent. The ledger must be the same on all honest nodes and changes simultaneously only if the consensus is achieved. It might not always be the case since there can be deceptive nodes or some network issues preventing the correct propagation of blocks. A consensus must be resilient enough to deal with such cases and must be able to continue with making consensus (liveness). So there must be a valid state that can be taken as an input for the creation of a new block. After the addition of a new block, the global state will be also changed.

Users of the network, like Alice and Bob, send transactions over and over. There might be millions of users sending transactions at a given time. All transactions are propagated over all nodes by the network. A node chooses transactions and inserts them into a block. Once the block is created it can be propagated and consensus between nodes can be made. As you can see the consensus is mainly about transactions in the block. There are more parameters that are guarded by the consensus. For example, whether the maximum supply is not broken or whether the new block can be correctly added at the end of the blockchain and contains a valid link to the previous block. Projects might differ at this point. Let’s focus on transactions in the section.

Adding new blocks at the end of blockchain is basically a form of synchronization of transactions. Transactions have an order which must be kept and guarded by the consensus. Let’s have a look at the following transaction example.

Block 1:

• Transaction 1: Alice sends coin M to Bob.
• Transaction 2: Alice sends coin M to Carol.
• Transaction 3: Bob sends coin M to Dave.

As you can see all three transactions send coin M. However, Alice tries to commit fraud. She wants to spend coin M twice (the so-called double-spend attack). Alice used her private key to sign two transactions T1 and T2. Both transactions are valid. However, the order is what matters since both cannot be accepted by the consensus. The consensus probably takes only T1 and will reject to insert T2 into a new block.

Notice, that T3 can be accepted only if T1 has been accepted. If protocol would add T2 instead of T1 then Bob would not be the owner of coin M and could not send it.

The node with the right to produce a block must insert only such transactions into a new block that will be also accepted by the required majority of other honest nodes participating in consensus. The whole block must be accepted. Only in this case, the node will be rewarded for the block production. Let’s assume the block 1 was accepted and there are other transactions waiting for processing.

Block 2:

• Transaction 4: Carol sends coin M to Dan.
• Transaction 5: Dave sends coin M to Eve.

Now you probably know what is going to happen. There is another node trying to create a new block. It must take into account the state which was valid in the accepted block 1. So if T1 and T3 were added into the block 1 then T5 can be inserted into the block 2. If T2 was added then T4 can be inserted into the block 2.

Few notes: All transactions must be signed and the signatures are also validated. Only owners of private keys are able to sing transactions so nodes can hardly cheat with transactions.

Nodes are responsible for inserting transactions into a new block. They can choose based on fees. Thus there is a higher chance that T2 will be inserted into block 1 if the fee is higher than in T1.

A block can be considered as a method of how to synchronize a bunch of transactions. In PoW, mining takes 10 minutes so pool operators create blocks and then the competition might begin. Mining plays an important synchronization role in PoW. In PoS the synchronization is a bit complicated. In the Cardano network, only one node in a given slot retrieves the right for block production. All other nodes must know which slot is currently active and when to continue with the next slot if the node fails to produce a block in the active slot. In PoS, forking of blockchain might be prevented so it also is good protection against a double-spend attack.

Every consensus for the public distributed network must reward honest behavior and prevent fraud. It is the topic itself so maybe next time.

Consensus responsibilities

There are two important properties that must be guaranteed by the consensus: Safety and liveness.

Safety is guaranteed if the required majority of nodes behave honestly and deceptive nodes cannot convince any client to accept incorrect or invalid transactions. In other words safety guarantees that bad things will never happen.

Liveness is guaranteed if the required majority of nodes behave honestly and deceptive nodes cannot indefinitely delay the acceptance of correct transactions. You can also understand that as a requirement that eventually something positive happens (there is no upper bound) and protocol will progress in making the consensus.

We can simply say that consensus should be able to safely adding blocks and never stops.

If safety and liveness are guaranteed then the transaction history cannot be changed by deceptive nodes and protocol is able to continue with adding new blocks. Honest nodes always know which version of the truth (the global state) is correct and thus new block can be correctly added. In case the properties are guaranteed then, from the point of the ledger, it is also true that deceptive nodes cannot change the history of the ledger and honest nodes are always able to retrieve the correct version of the ledger. Notice that both properties are inseparable and support each other. If a protocol would prefer liveness to safety then it would be easy adding blocks but it could be also easy to cheat. Contrary, if a protocol would prefer safety to liveness then it could be hard to add a new block, maybe it would be smart not to add a new block at all. Then, it would not be a consensus. Designers of a consensus are looking for balance.

There was a case in the past the consensus of Stellar Lumens stopped making the mutual consensus after one node gets broken. It can be said that the protocol preferred safety to liveness. It protected user’s funds from what was better than to continue with processing new transactions.

In the case of Cardano, consensus rules are defined in a way that safety and liveness can be provably guaranteed even in case there is a minority of deceptive nodes. The consensus must be fault-tolerant.

Consensus rules

The consensus is about a set of rules which are transferred by programmers into a source code of a protocol. There are many rules that are required to build a protocol. Rules must define things like the following:

• How valid the transaction looks like.
• Order of transaction in a block.
• Property of a block.
• Rules for the propagation of transactions and blocks.
• How to create a new block.
• Rules for selecting a node that gets the right to produce a block.
• How to make a mutual agreement for adding a new proposed block.
• And many others.

Most significant differences between consensus algorithms are related to making the mutual agreement for adding a new proposed block. In PoW a block is just simply added if there is proof of consumed electricity. The proof is basically a hash of the block that must be correct within the current difficulty target. If a node receives such block and all other requirements are correct (all transactions, hash, timestamp, etc.) the node adds the block at the end of the blockchain.

Cardano’s Ouroboros PoS requires proof that a node propagating a new block got the right to produce a block in a given slot. There are more rules and functionality implemented for that in the protocol. Every node asks in every slot whether now it has the right to produce a block. If it is the case there is a rule that the node must insert the proof of the winning the right into the block together with transactions and other parameters. Another set of rules allows other nodes to verify that the received proposed block was really created by the correct node.

PoW consensus relies on electricity consumption while PoS is based on math and science. Both approaches guarantee safety and liveness. We would have to explore properties like scalability, security, decentralization, permissionless, fairness, censorship-resistance, finality, and others to see major differences between consensus protocols. We will do it in some other article.

Conclusion

It cannot be said that PoW is better than PoS or vice versa. Both have advantages and disadvantages. However, PoS is able to confirm transactions faster and it is more scalable. PoS can be even more scalable with sharding. Sharding allows one to make more parallel consensus at the same time and still keep one valid global state of the ledger.

I hope you understand the term consensus well and know what decentralized and distributed networks need to do to keep the history of transactions immutable and adding new ones safely and continuously.

Source: Diving into Protocol Consensus