Algorithms for applying the same data in the same order in a distributed environment connected through networks are called consensus algorithms. In a blockchain, blocks will be the data subject to agreement. The blockchain consensus algorithm serves to maintain only a single chain(list of blocks) when multiple nodes produce blocks or expand blockchain after receiving the produced blocks.
This article will introduce Raft, a consensus algorithm with improved performance and usability, now supported by AERGO as the company released the optimized version for enterprises.
The enterprise environment is different from a public network environment in which AERGO mainnet operates. The most significant difference is that blockchain run by enterprises operates in a secure private network environment. In such environment, there is less need for using complex consensus algorithms that requires much resource in processing to prevent random creation of blocks by malicious or unauthorized nodes used in the public network environment.
A downside of Bitcoin or Ethereum’s POW is that they put a lot of load on the server. DpoS in EOS or AERGO used in improving such a problem are light and fast. However, it does not guarantee immediate finality of the produced blocks. Using BFT consensus algorithms such as Tendermint ensures immediate finality of the blocks but is unnecessarily complex.
In exchange for giving up Byzantine Fault Tolerance to suit the characteristics of a private network environment, Raft has advantages of ensuring immediate finality of the blocks right after they are added to the chain and that forks do not occur.
Now let us explain how Raft consensus works in AERGO, in more detail.
Features of RAFT
Paxos is the most widely used consensus algorithm used between nodes. However, the Paxos algorithm is difficult to understand due to its high complexity, and thus there is no implementation that is widely used with verified stability. Therefore, Raft consensus algorithm was developed for the purpose of developing a consensus algorithm that has the same stability as Paxos but is easier to understand, implement and manage.
With such benefits, Raft, initially proposed by Diego Ongaro and John Ousterhout of Stanford University, has been adopted and used as a node-to-node consensus algorithm in distributed environments in many projects, including ETCD.
AERGO was developed by using the raft library developed in the ETCD project, among several Raft implementations.
Now let us review the benefits of using Raft.
First, Raft ensures CFT (crash fault tolerance). It ensures that a cluster functions normally until failure occurs in the majority (n/2) of the cluster’s entire nodes. However, Raft operates on the assumption that all nodes are honest. That is, it is not Byzantine Fault Tolerant. Therefore, Raft is a consensus algorithm that is suitable for private network environments.
Second, the most distinctive feature of Raft when compared with BFT consensus algorithms is that finality of blocks is ensured as soon as the blocks are added to a blockchain. Hence, there is no fork in the chain and no reorganization of the chain from it. At the moment the agreed block is added to the blockchain, Raft ensures that no other block is added to the same height. Also, it ensures that all participating nodes add the same block to the same height.
Third, Raft is simple. The protocol is not complex, and blocks continue to be generated on the same server unless the server experiences failure. If a node that generated a block fails, a new node selected through the voting process will be responsible for creating the block. These features may lead to better performance than DPoS in which multiple nodes generate blocks in turns or BFT consensus algorithms with complex consensus processes.
On Raft, multiple server nodes are connected through networks to form a cluster, and each node is in one of the following states.
– Leaders generate blocks and propagate them throughout the cluster. Also, leaders finally add the blocks to the blockchain after the other nodes form a consensus.
– Followers store and respond to blocks delivered by the leaders. These responses allow the leaders to determine whether the block delivery was successful in a majority of cluster nodes.
– If a node in a follower state loses connection with a leader node for a set amount of time, it becomes a candidate state. A candidate node becomes a new leader when it sends vote requests to the other nodes and receives votes from a majority of the nodes.
All nodes of AERGO start in the following state. Among these nodes, a new leader is chosen through the leader election process. Only the node elected as a leader can generate blocks. The leader node continues to generate blocks until it loses the leader state and propagates the generated blocks to the follower nodes through the Raft protocol. Such processes allow the entire cluster to maintain identical blockchains.
Block creation process using Raft protocol
Now let’s examine how entire nodes use the Raft protocol to generate blocks and store them in each of its own repositories. The process of adding blocks to the entire blockchain consists largely of three steps: Propose, Commit, and Apply.
– The leader node generates blocks, executes the transactions contained in the blocks, and propagates them to the follower nodes.
– A follower node receives the block propagated by the leader node, stores it in its repository (executions are postponed until the Apply step), and sends a success response. The leader node waits until the number of responses received from the follower nodes reaches a majority (N/2) of the total cluster nodes and considers the block to be successfully committed. This is ensured by a leader-election algorithm. A new leader must be elected among the nodes that include the most recently committed entry. After the new leader adds all the unadded committed blocks to the blockchain, it generates a block of the next height to ensure that the committed block remains included in the blockchain.
What does it mean when we say a block is committed?
When a block becomes committed, it refers to a state where the block is never lost even if the entire nodes of the cluster is stopped and then go through a rerun in such a state.
– The leader then adds the committed block as a top block in the blockchain. Commit information is periodically sent by the leader to follower nodes through heartbeat messages. When follower nodes receive new commit information, they execute the stored block and add it to their own blockchains.
In Raft, only the leader generates blocks and it is ensured that only one leader exists at a particular point in time. As a result, all blocks that are added become to have immediate finality. Therefore, it can be said that the leader election process is the core of Raft.
– A leader election process is as follows.
– No heartbeat message is received by a follower node, due to a failure in a current leader node or network.
– The follower node becomes a candidate node.
– The candidate node sends vote requests to the other nodes, with information about its status.
– Nodes that received vote requests send approvals only when the status of the candidate is the same or more up-to-date than its own.
– When the candidate receives approvals from the majority(n/2) of the nodes within a set amount of time, it becomes a new leader.
The most crucial aspects of the vote are the following two things.
– Only one leader exists at a time.
– The new leader must include the last commit of the previous leader.
In order to satisfy such conditions, there are the following restrictions. A follower node cannot vote for two nodes simultaneously. Also, it cannot vote for a node that has a less updated status than the Raft status saved in the node of its own.
By adhering to the two most important principles listed above, the Raft algorithm ensures its ability to expand the blockchain without causing forks even when the leader changes through the vote.
AERGO supports dynamic adding and deleting of nodes through Raft consensus. Such is a critical feature for carrying out cluster maintenance without interrupting the service. Adding and deleting of nodes are conducted through system transactions that are included in the blockchain.
Similar to the process of adding blocks, a request for a Raft membership change is generated as a Raft log and processed through Propose/Commit/Apply procedure. Let us examine the procedure in general.
1. Propose stage
– When the leader node executes a block that includes a membership change transaction, a request for Raft membership change is made. The issued request is sent from the leader to the follower nodes.
2. Commit stage
– When the leader receives responses from the majority of the follower nodes, the request for Raft membership change becomes committed.
3. Apply stage
– The committed membership change is reflected on nodes. In adding nodes, a new node should be initiated after it is confirmed that the change has been successfully reflected. The significance of this process lies in the fact that the request for membership change and the request for adding blocks is executed through the same process. As such, the concept of conducting dynamic membership change through a consistent logic shows the simplistic and intuitive aspect of Raft as its strength.
The Raft consensus algorithm of AERGO is equipped with the following features.
– Guaranteed crash fault tolerance
– Ensured immediate finality of blocks
– Flexibility in dynamic membership change
Such features make the Raft consensus algorithm particularly suited for enterprise environments in which the finality of blocks has the utmost importance and tight network security is ensured.
By implementing AERGO Raft consensus, enterprises will be able to experience improved performance and usability than the existing DPOS.
An article that can help understand the concept of a consensus: Understanding Blockchain Fundamentals, Part 1: Byzantine Fault Tolerance
Please refer to Raft github for academic journals and additional materials on Raft
Also, refer to the slides created by Diego Ongaro and John Ousterhout for detailed information about Raft.