Consistency Protocol
The PBFT algorithm was proposed in 1999 as an algorithm specifically designed to solve the Byzantine general problem (Gao, Z., & Yang, L., 2020; Yu, G., et al., 2020). The algorithm aims to solve the problem of ensuring the consistency and correctness of the final decision in the presence of malicious nodes throughout the network.
The PBFT algorithm can tolerate no more than (n-1)/3 amount of malicious or faulty nodes (n is the total number of nodes), as shown in equation (1). If there are f malicious nodes, the number of normal nodes is at least f+1, and the total number of nodes is at least 3f+1 to allow the system to function properly, as shown in equation (2). If there is an extreme case with f malicious nodes as well as f faulty nodes, the total number of nodes is at least 3f+1 to ensure that the system can reach consensus smoothly:
(1)(2)In the PBFT algorithm, all nodes are classified into three types: client, master, and replica nodes. The master node mainly assigns sequence numbers to the transaction requests initiated by the clients, and the replica nodes execute the requests based on the sequence numbers to check whether there is any problem with the master node. When the master node is unable to complete the consensus, it will use the view change mechanism formula to continue the selection of a new master node as shown in equation (3). In this equation P is the master node number, V is the view number, and |R| is the number of nodes:
(3)The consensus process of PBFT consists of five stages: request, pre-prepare, prepare, commit, and reply. The algorithm flow is shown in Figure 1.
- •
Request: Client C sends a transaction request <REQUEST,o,t,c> to master node 0, where REQUEST contains the message content m and the message digest d(m). The client needs to sign the request; t is the timestamp, o indicates the operation, and c represents this client.
- •
Pre-prepare: Master node 0 receives the request from client C, determines whether the number of messages being processed exceeds the limit, and if the limit is exceeded, it is first cached and then packaged and processed together later; if the limit is not exceeded, it generates <<PRE-PREPARE,v,n,d>,m> messages and broadcasts them to other nodes, where v is the view number, n is the sequence number of the request assigned a sequence number, and d is the summary of message m.
- •
Prepare: Each replica node receives a “Prepare” message and verifies the current view, sequence number, transaction, and signature. If all pass, it broadcasts a <PREPARE,v,n,d,i> message to the other nodes to indicate that it received and acknowledged the request, where i is the node number; if not, it ignores the message.
- •
Commit: After receiving 2f valid prepare messages, the node broadcasts a commit message <COMMIT,v,n,d,i> from the node, which receives 2f confirmation messages from other nodes, writes the received messages to the log if they are passed, executes the request, and replies with the message <REPLY,v,t,c,i,r> to the client, where r is a response of node i.
- •
Reply: The result is valid when the client node receives at least f+1 identical response results from different nodes.