PBFT Byzantine protocol security analysis: not suitable for alliance chain or common chain

Professor yongge wang is a distinguished Chinese cryptographer and tenured professor of computer science at the university of north Carolina, Charlotte. He holds a doctorate from the university of Heidelberg in Germany.

The design of consensus protocol is always a challenging subject. Lamport, a Turing award winner, described his design of the Paxos consensus protocol for distributed computing in 1989, using a group of amateur lawmakers on the Greek island of Paxos to enact a law. Lamport submitted his article to the ACM TOCS. Perhaps the editor of the magazine failed to grasp the importance of the article and refused to publish it. It was not until the Paxos consensus protocol was widely discussed in academia and widely used in industry that the journal published this article in 1998:

Lamport, Leslie. "The part-time parliament." ACM Transactions on Computer Systems (TOCS) 16.2 (1998): 133-169.

Lamport joked that this was the second longest article he had ever published. To date, the Paxos consensus protocol has been used in almost all distributed systems. For example, Google's Bigtable USES the Chubby lock service system to ensure the consistency of data across nodes. The Chubby lock service is based on the Paxos protocol. In addition, cloud services from Microsoft, IBM, and amazon all use the Paxos protocol to provide consistency. Roughly speaking, the Paxos protocol consists of a series of rounds. ROUND starts at 0 until consensus is reached. Each ROUND is divided into the following four steps:

1. The master node generates a sequence number and broadcasts to all nodes. I hope you can participate in the activities of this serial number
2. Each node sends the master node the following information: the serial number of the votes it participated in and the votes it voted
3. After receiving most of the responses from the second step, the master node selects a value v that will not violate SAFETY. Broadcast the value v to all nodes
4. After each node receives the value v of the third step of the primary node, it votes for v and broadcasts its vote to all nodes

Because the Paxos protocol is difficult to implement, researchers at Stanford proposed a modular, easy-to-implement Paxos protocol in 2014 and named it the Raft protocol. The Paxos/Raft protocol works in a milder threat model. In other words, the protocol is robust only for non-byzantine errors in asynchronous networks. In the non-byzantine threat model, the offending node can only make passive errors (such as stopping work) and cannot launch aggressive attacks. The maximum number of non-byzantine error nodes a system with n nodes can tolerate is (n-1) /2. The Paxos/Raft protocol achieves this maximum number of fault-tolerant nodes.

Because the Paxos/Raft protocols are not robust to Byzantine errors, they cannot be used in open network systems such as blockchain systems. Byzantine errors are aggressive errors, such as lying, falsifying messages, conspiring to attack, or launching selective DoS attacks. As we have mentioned in previous articles, the decentralized blockchain system is based on the open network system, so we must use the Byzantine threat model.

The most used Byzantine protocol on the block chain is the practical Byzantine fault-tolerant system PBFT (practical BFT) designed by Turing award winner Barbara Liskov and her student Castro. PBFT is widely used in alliance chains (such as Hyperledger sawtooth and hyperchains of interest chain technology) and many corporate chains. PBFT can be seen as a Byzantine version of the Paxos protocol. The main difference is that PBFT adds a validation step to the Paxos protocol to prevent Byzantine errors. Before analyzing its security, we give a formal description of its protocol.

In PBFT protocol, we assume that n=3t+1 node P1... , Pn. At most t nodes are controlled by the attacker. PBFT requires all nodes to maintain a state together and take consistent action. The PBFT protocol is implemented through a series of views. In each view, there is a node called the master node (leader). The PBFT system starts with the view (v=0) and then enters the view (v= 1, v=2... And so on. Only when the system thinks that the primary node is not working properly will the view change protocol be started and go to the next view. We assume that all nodes know who the primary node of each view is. After each client submits a task to the primary node of the current view, the PBFT protocol communicates in three phases: pre-prepare, prepare, and commit. The pre-prepare phase assigns a sequence number to each task, and the prepare and commit phases provide a global sort for all tasks. Let's say we're in view v now, and the primary node is Pi. Then the whole process of the agreement is as follows:

1. The client sends a task request m to activate the service operation of the master node.
2. After the master node Pi receives the task request m, start the three-phase protocol:
A. pre-prepare phase: the master node selects a unique sequence number seq to give the task request m. The primary node then broadcasts the following message to all nodes
m,<PRE-PREPARE, v, seq, H(m)>，SIGNATURE
Where H is a hash function. A node Pj accepts the above message if all the following conditions are met
I. Digital SIGNATURE SIGNATURE is valid
Ii. Pj has not yet accepted another task request containing the same v, seq
Iii. The serial number seq is within a reasonable range

B. mutual interaction (prepare) stage: if the node Pj receives the broadcast message from the primary node, then the Pj enters the mutual interaction (prepare) stage and broadcasts the following message to all nodes

< PREPARE, V, seq, H (m), Pj >, SIGNATURE

C. Commit phase: for node Pj, an array < M, v, seq, Pj> Is prepared if and only if Pj receives at least 2t valid messages. PREPARE, v, seq, H(m), P> . When the array & lt; M, v, seq, Pj> When ready for Pj, Pj broadcasts the following confirmation message to all nodes:

<COMMIT, v, seq, H(m), Pj>,SIGNATURE

When a node receives a 2t+1 acknowledgement message, it executes the task contained in task request m and sends the result directly to the customer.
3. The client is waiting for the reply from different nodes. If t+1 reply is the same, the reply is the result of operation.

Recently, we analyzed the security of PBFT in the following articles:

Yongge Wang. Byzantine Fault Tolerance in Partially Connected Asynchronous Networks

The paper concludes that the PBFT consensus protocol is not secure in asynchronous networks. In this article, we briefly introduce the attack method we designed on PBFT protocol in asynchronous network. To simplify our description, we assume that the system has n=3+1=4 nodes P1,P2, P3 and P4. Where node P1 is controlled by an attacker. In addition, we assume that the primary node of view v is P1. Our attack unfolds in view v:

1. During the pre-prepare phase of view v, master node P1 sends the broadcast message "m, < pre-prepare, v, seq, H(m) >, SIGNATURE" to P1,P2, P3. But not P4.

2. During the prepare phase, P1 sends the broadcast message "< prepare, v, seq, H(m), P1>, SIGNATURE" to P1,P2, P3. But not P4. During the prepare phase, nodes P2 and P3 send broadcast messages "< prepare, v, seq, H(m), P2>, SIGNATURE" and "< prepare, v, seq, H(m), P3>, SIGNATURE" to all nodes. Of course, if possible, an attacker might launch a DoS attack so that node P4 does not receive broadcast messages from nodes P2 and P3 (this DoS attack is not very important for our attack). At this point, the array < M, v, seq, Pj> It's ready for nodes P1,P2, P3. Because P4 receives at most two interactive messages, and we need at least 2+1=3 messages to prepare an array, the array is not ready for P4.

3. During the serial number confirmation (commit) phase, P1 sends the broadcast message "< commit, v, seq, H(m), P1>, SIGNATURE" to P1,P2. But not P4. During the serial number confirmation (commit) phase, nodes P2 and P3 send broadcast messages "< commit, v, seq, H(m), P2>, SIGNATURE" and "<PREPARE, v, seq, H(m), P3>, SIGNATURE" to all nodes. Of course, if possible, an attacker might launch a DoS attack so that node P4 does not receive broadcast messages from nodes P2 and P3 (this DoS attack is not very important for our attack). At this point, nodes P1 and P2 receive three confirmation messages for task m. Nodes P3 and P4 receive up to two confirmation messages for task m. So node P2 will execute the tasks contained in the task request m and send the results directly to the customer. But P1,P3, P4 will not perform the task. So customers don't get enough replies.

After the above attack, node P1 will no longer reply to any messages from view v. So the system will start the view and change the protocol into the next view v +1. After entering view v +1, the internal data state of P2,P3 and P4 of the honest node is different. So the system goes into disharmony.

In the PBFT protocol, the CHECKPOINT status update process is designed to prevent some nodes from receiving certain messages (such as in our attack scenario above). In particular, after every 100 tasks, each node Pj broadcasts its current status message to all nodes:

<CHECKPOINT, seq, H(state), Pj>，SIGNATURE

If a node Pi receives 2t+1 of the above status update messages and its state, then the node Pi will replace its current state with the state in the above message. In our attack above, if the dishonest node P1 does not publish status updates, then the status updates published by P2 will be different from the status updates published by P3 and P4. Since we need at least 2+1=3 identical status updates to update the status of a node, the status of P2 cannot be updated to the status of P3 and P4. So the system will always be out of sync.

In the later view, the dishonest node P1 can cooperate with the honest nodes P3 and P4 to perform another task request on the client side. Therefore, the state of each node will enter an unrecoverable uncoordinated state.

In our previous article, we mentioned that DoS attacks are easy to deploy in internet-based blockchain technology. Since the Internet is an asynchronous network, we use the following model to describe its network communication:

· there is a Global Stabilization Time (GST) before which any messages can be lost (such as a DoS attack) or reordered. After GST, the network becomes a synchronous network. But when GST will start, no one knows.

Therefore, our above attack can be carried out before the GST of the asynchronous network. So if a blockchain system USES PBFT as its consensus protocol, what are the results of our attack above? In general, the blockchain system will first fork and then crash (that is, no new blockchain blocks will be created) after the attack. In particular, before launching the attack described above, it was agreed that the block chain was: A→B→C→D. Using the above attack scheme, the attacker first lets P2 decide that the next block is E. In other words, in P2's record, the current block chain is: A→B→C→D→E. However, the current block chain recorded by P3 and P4 is still A→B→C→D. Then the attacker P1 makes the nodes P3 and P4 decide the next node is F. So in the records of P3 and P4, the current block chain is: A→B→C→D→F. Because block E is different from block F. The blockchain has bifurcated. Since the next block must have the current block chain extended out. If the node does not participate in any activity from now on, then the system does not send the minimum number of votes 2+1=3. So no new blocks can be generated. Taken together, our analysis in this paper concludes that the PBFT consensus protocol cannot guarantee the safety and liveness requirements of the block chain system. Therefore, we suggest that PBFT should not be used as the consensus protocol in either the alliance chain or the Commons chain.

Welcome to join the official BlockBeats community:

Telegram Subscription Group: https://t.me/theblockbeats

Telegram Discussion Group: https://t.me/BlockBeats_App

Official Twitter Account: https://twitter.com/BlockBeatsAsia