Collaborating to agree: Consensus in 2018

Introduction:

The Bitcoin paper published in 2008 gives us a practical way of transferring value over the internet in a decentralised manner. The Bitcoin protocol is innovative in the sense that it tries to model the rationale behind a greedy human and aligns proper incentives to ensure resilience against misbehaviour in an open and global distributed network. Satoshi Nakamoto tries to solve the problem of transferring value over the internet (over a decentralised network) by proposing a 3 part solution:

1. Maintaining a global, public ledger which anyone in the network can see and keep a copy of (the Blockchain)
2. The consensus protocol which defines the set of rules to reach global, decentralised consensus on the valid blockchain (using the Proof-of-Work algorithm)
3. Aligning a proper incentive structure to motivate the nodes to maintain the network’s liveness and consistency.

The stability of any type of decentralised currency system depends greatly upon the stability of the consensus protocol. Consensus is not a new problem. It has been studied for decades and people have been able to develop robust and practical protocols for closed networks. What is unique about Satoshi Nakamoto’s proposition is that the Bitcoin protocol enables consensus in an open, decentralised network. In this post I will be surveying (and also briefly writing about) some of the really cool consensus protocols which hope to replace the PoW algorithm. So before we get to these newer protocols lets have a brief look at some of the problems with PoW

Issues with PoW:

1. A lot of computational resources is spent in a wasteful way. This has lead to huge amount of electricity being wasted thereby damaging our environment.
2. Mining in bitcoin has become highly centralised. Miners have form cartels in the form of mining pools to reduce their variance in block rewards.
3. The current design of the protocol is not highly scalable meaning it is not yet perfectly ready to carry out transactions at a global scale to meet global demands. If this remains the case and more people join the network and carry out transactions, transaction fees will rapidly increase which will make micro-payments on the bitcoin network impossible.

Note that even though the bitcoin network uses huge amounts of electricity, it is also the reason that keeps the network secure. It is the price that the network pays for decentralisation. The fact that miners have to use “external resources”, resources that they need to pay for, to keep the network running makes it impractical for them to cheat the network. If they do so they will incur losses as any malicious activity will simply devalue the currency. Given this, it is still important that we find a better way to build up on this great innovation. The next generation of consensus protocols need to be more energy efficient and allow blockchains to be more scalable so that it can sustain global demands. Here are a few candidates that can possibly replace PoW.

Casper -A practical PoS implementation:

Hostage your money

Casper (a type of Proof-of-Stake implementation) is seen as a very practical alternative to PoW. Ethereum right now uses PoW as its consensus algorithm. However the team wants to eventually shift to Casper which is a more energy efficient and supposedly more secure consensus algorithm. In PoS there is no such thing as miners as there is no computational hard work required to add a block to the blockchain. Instead there are validators. At a high level, this is how the Casper protocol will be implemented:

1. The validators will have to lock at least, say, 1000 ETH that they own, as a stake in the network.
2. After that, they will start validating the blocks. Meaning, when they discover a block which they think can be added to the chain, they will validate it by placing a bet on it.
3. If the particular block that they put a bet on, is added to the blockchain they receive a reward proportionate to their bets.
4. However, if a node tries to act in a malicious manner, its stake is slashed/burned and hence it can no more act as a validator.

The validators are rewarded for maintaining a valid blockchain but their stake acts as a hostage which is burned if the node is found to be acting maliciously. The overall design principles of the Casper protocol are as follow:

• Using fear, fear of losing stake, to stop bad actors. This kind of system increases the cost of attack thereby making the network economically secure.
• Having a system which will not lead to centralisation in terms of block production. What we have seen in case of Bitcoin is that miners have formed a cartel in the form of mining pools to reduce their variance in block rewards. This has simply led to centralisation in block production. In case of casper there is no benefit in pooling their stake in hope of better rewards.
• Design that makes it possible to attribute faults to bad actors as much as possible. Casper relies on the ability to slash attributable Byzantine behaviour (i.e. the behaviour of not following the protocol).

PoS will also be somewhat useful in making the blockchain more scalable. It is definitely more energy efficient as there is no need to spend wasteful computational resources. Though PoS has its own issues it will be interesting to see how Ethereum is going to implement it.

Delegated Proof-of-Stake (DPoS):

DPoS is an interesting form of PoS. It is being used by blockchains like EOS, Lisk, Bitshares, etc to achieve huge scalability. EOS promises upto million transactions per second on its network using DPoS. Just to give you a comparison, Bitcoin settles transaction at the rate of 7 transactions per second, Ethereum does it at 15 transactions per second and companies like Visa and PayPal settle transaction in order of thousands or even tens of thousands, which is still 100 times less than what EOS says it can achieve. Here is a high level description of how it works:

1. Nodes in the network vote for a delegate to secure the network.
2. The votes of the nodes carry a weight in accordance to their stake in the network. Hence a node which has a greater stake in the network has greater voting powers.
3. The top delegates chosen cooperate (instead of compete) to decide the next block to be appended to the blockchain

Vitalik Buterin (the founder of Ethereum) does have some reservations against this type of consensus protocol and only time will tell if EOS can flawlessly implement DPoS into their network.

Proof-of-Importance:

Proof-of-Importance (PoI) is a consensus algorithm used by the NEM network. The network uses its own cryptocurrency called XEM. NEM’s proof-of-importance (PoI) consensus algorithm is used to determine the user that will calculate a block of transactions on the blockchain. A user’s importance is dependent on numerous factors, which include: the amount of coins owned by the user, the number of transactions that a user makes, and with whom the transactions are being made. Taking into account transactions in calculating a user’s importance is intended to encourage users to transact using NEM coins, instead of simply holding them. The higher a user’s importance, the greater the likelihood of a user being selected to calculate and harvest the fees inside a block. The PoI consensus algorithm can be contrasted with the PoW and PoS consensus algorithm, that do not account for user transaction volumes.

Identity Aging:

The central idea of this consensus algorithm is to establish reliable, long term identities and choose the oldest one as the miner in each round. It uses two systems to make this possible. The first one SCIFER (Semi - Centralised Incentivised Fair Efficient Resilient consensus), which leverages Intel’s SGX attestation for identity bootstrapping in a partially-decentralised setting, where blockchain is permission less. The second system is DIFER (Decentralised Incentivised Fair Efficient Resilient consensus), creates new identities through a novel mining mechanism and provides consensus in a fully-decentralised setting, similar to Bitcoin. This is a relatively new algorithm submitted as a research paper in April of 2018. Its a very detailed and well written paper which talks about each and every aspect of the algorithm including some initial test results that the authors did. I highly recommend the readers to go through the paper here and have a look at it :)

Proof-of-Exercise:

Proof of eXercise aims to direct the computing power towards real-world scientific problems. The PoX whitepaper describes a system where miners will be given matrix-based problems provided by so-called “employers” within the system. The reasoning for using matrices is two-fold: matrices are compose-able, allowing for easier tuning of network difficulty, and matrices are a principle abstraction for many scientific computational problems. The whitepaper provides the following problems as examples: DNA and RNA sequencing, protein structure analysis, data mining, face detection, and more.

To avoid potential collusion between miners, employers, and verifiers, solutions the matrix problems are sent through a shuffling service. This is done in two parts: directly after an employer publishes the matrix data, and directly after a miner sends the data for verification. In addition, should multiple miners win a bid to solve the same problem, the coin reward for the solution will be shared between them.

Conclusion:

Consensus protocols is one of the most important open research challenge in the field of blockchain technology. Satoshi Nakamoto’s solution has really stood the test of time (at least till now) even though it has some inefficiencies. Some say that Bitcoin is that rare invention which really works well in practice but not in theory. Well then there has got be something wrong with our theory. One of the reasons that Bitcoin works so well in practice is that it does not answer the question “How can an adversary attack an open, decentralised network and what could be a possible solution to secure it?”. No. Instead it considers an even important question of why would an adversary want to attack the system in the first place. Bitcoin relies on an unknown combination of socioeconomic factors which is hopelessly untractable to model with sufficient precision, hence failing to yield a convincing argument for the system’s soundness in theory. Bitcoin’s premise that the rational of a greedy person can be modeled and incentives can be aligned to secure the network is not only the central theme of Bitcoin but every cryptocurrency today. The field of “consensus” in an open decentralised network or even the field of blockchain technologies in general lies at the intersection of a lot of fields of study like computer science, cryptography, game theory, economics, etc. Its just exciting times to live in ;)

My name is Miraj and I am a student from India. Thank you very much for reading the post. I intend to write more technical stuff and would love to hear any feedbacks you guys might have. I am also on Patreon and if you feel like contributing go ahead and feel free to checkout my Patreon page here. https://www.patreon.com/mirajshah
THANK YOU.