TECH

DxChain Study: An Overview of Consensus Algorithms


The galloping progress of the fledgling blockchain technology is out of one’s mind. This would-be revolution, which is merely 10-year-old, has been developing significantly over the past few years and branched out into new applications that can be hardly imagined before.

While we can dive deep into blockchain technologies in many ways: cryptography, identity privacy, data privacy, data storage, turing complete, incentives, throughput and latency of the system, security protection, threat model, how to deal with forks, and etc., the consensus algorithm is always the linchpin of all proper techniques, basically laying the groundwork for other features.

Consensus algorithm is a favorite research direction in distributed systems, a field of computer science in which components located on different network computers communicate and coordinate their actions. In fact, the blockchain itself can also be regarded as a type of distributed system.

This article will touch upon some of the most popular consensus algorithms to date, from classical consensus algorithms, proof-of-work(PoW), proof-of-anything (PoX), to the state-of-the-art multi-committee election.

1. Traditional Consensus Algorithms

There are many traditional consensus algorithms. We begin with two-phase commit protocol (2PC), an atomic commitment protocol for distributed systems.

A typical 2PC consists of two phases — a commit-request phase and a commit phase. In a typical execution of a single distributed transaction, a participant (or cohort, worker) will notify a coordinator the result of a transaction, and the coordinator will decide whether to commit (only if all have voted “Yes”) or abort the transaction (otherwise) based on votings of the participants.

Similar to 2PC, Paxos and Raft are the two widely-used algorithms in large-scale distributed systems today.

Paxos is a family of protocols designed for a more complicated situation. It has more roles (client, acceptor, proposer, learner, and leader) to perform different decision functions.

While Paxos is widely implemented in the industry, the protocol itself is too complicated to reason about, raising challenges to engineers in a situation where unexpected problems occur.

WechatIMG12.jpeg

Meanwhile, Apache Hadoop which uses traditional consensus algorithm that can achieve good performance in centralized distributed systems.

WechatIMG13.jpeg

2. PoW and PoX

Bitcoin’s PoW algorithm is designed based on a statistical concept — Gambler’s Ruin. Every single node can independently run a process of leader election. This algorithm can reach the consensus of the entire system by accumulating computing power.

Despite maintaining the consensus of the system, PoW itself does not yet provide any additional functionality. At the same time, each node generates a block through repeated calculations, which waste much computational power. That is why many new algorithms are spawned to provide additional functionality while achieving the consensus of the system.

Here is a quick rundown of the new proof-of-anything algorithms. For simplicity, these are referred to as PoX.

PoS (Proof of Stake) — the odds of a miner creating the next block are proportional to the tokens they are staking on which blocks are valid.

PoS (Proof of Space) — a consensus algorithm based on storage capacity a miner can provide.

uPoW (Proof of Useful Work) — a class of consensus algorithms providing a quantity of useful tasks that can help blockchain to grow.

3. Multi-committee Election

PoW and the mentioned PoX let single nodes to generate a new block, resulting in low performance, in particular, low throughput and high latency.

Here comes the single-committee election in a bid to solve the problem of low performance. Through a particular type of election mechanism, token holders can vote to elect a group of delegates, or a committee, which consists of supernodes.

There are three primary types of approaches in this single-committee election:

Hyperledger, an umbrella project of open source blockchains and related tools, applies an invitation mechanism to ask trustworthy node to participate in the committee.

The invitation mechanism is usually adopted by the consortium blockchain, regarded as a compromise to efficiency and centralization.

ByzCoin, an enhancement of Bitcoin, uses PoW to decide which node can join.

Algorand, a new cryptocurrency that confirms transactions with latency on the order of a minute, uses cryptography lottery, an anonymous election process that makes it impossible for anyone to know in advance who is a delegate.

Although a single-committee election has achieved a significant improvement in performance compared to a single-node method, there are still unsolved problems regarding horizontal scaling. When the performance of a committee reaches its limit, it can only lift up performance by adding more delegates.

We are looking at the idea of blockchain sharding, where the entire state of the network splits into many partitions called shards that contain their independent piece of state and transaction history. This idea is built on multiple committees, each of which handles part of the transaction. The increase of committees brings more operability than the increase of delegates, and as a result, boosts the overall performance.

Introduced by we DxChain, the “Chains-on-chain” architecture is a similar technology that consists of three different chains — master chain, storage chain and computation chain. Each chain has distinct requirements for performance, so we use different consensus algorithm for the master chain and side chain.

This article introduces the blockchain consistency algorithm. Many details are not discussed in depth, such as how PoS prevents attacks, how committee delegates rotate, and how the committee internally agrees. We will discuss in detail in a future technical article.

Author image

About DxChain

DxChain committed to building a development platform for smart contracts and cross-chain ecosystem, and tend to create the most suitable public chain for decentralized applications.