PBFT：为什么2/3准备好后副本不能执行请求？为什么我们需要提交阶段？ [英] PBFT: Why cant the replicas perform the request after 2/3 have prepared? why do we need commit phase?

问题描述

我知道此网站上存在一些问相同问题的问题。但是答案永远不明确：

在PBFT中，为什么在2/3准备好后副本不能执行请求？为什么需要提交阶段？如果2/3 + 1副本已同意准备，那么我认为他们可以执行请求而无需再次广播吗？

解决方案

（已编辑）除了之前的答案（不完整）之外，还引用了

当副本在收到准备消息后立即执行请求时，可能会出现上述情况法定人数。我认为PBFT假设部分同步很重要。由于网络速度或对手不稳定，邮件可能会被任意延迟，但最终会被接收。因此，每个副本都可以在不同的时间点执行请求消息，并说明一个示例情况。

---

第二条评论

我想我需要通过说明包括主副本在内的恶意副本的协同攻击来详细说明答案。假设有n个副本，其中在拜占庭容错系统中，n = 3f + 1 = 100，f = 33。在系统中，系统可以容忍f个拜占庭式错误副本。现在我举一个反例来回答你的问题。请考虑以下设置；
我将n个副本分成三组；

1. G1 = {b1，b2，...，b33}对于包括拜占庭基本（b1），| G1 |的拜占庭式错误副本= 33


2. G2 = {r1，r2，...，r33}用于正确的副本组| G2 | = 33


3. G3 = {r34，r35，...，r67}用于正确的副本组| G3 | = 34

因为n = | G1 | + | G2 | + | G3 | = 33 + 33 + 34 = 100，以上分区有意义。
G1由超级天才黑客完全协调地控制，他们对破坏协议特别感兴趣。

现在，我将演示如果提交阶段从协议中消失，上述设置如何违反安全条件； （安全条件意味着G2和G3的状态应该相同）。为了简单描述，共识值被简化为二进制值，而不是带有序列号的请求。

1. [准备阶段]： Primary（b1）向G2发送一个0值，向G3发送一个1值。这种情况不是问题，因为我们假定拜占庭为主服务器。



2. [准备阶段]：现在，G2和G3中的副本交换主服务器的消息以检查它们是否都具有相同的消息。但是，在此阶段，来自G1的副本将0值发送到G2，并将1值发送到G3。消息交换后，情况如下

   
   
   

   a。 G2中的副本收到以下结果；对于0值，66票，对于1值，34票。

   
   
   

   b。 G3中的副本收到以下结果； 33票赞成0值，33 + 34 = 67票赞成1值。

因为定额为2f + 1 = 67，G3中的副本接受拜占庭主要副本的建议值，该提议的值与拜占庭副本进行协调，而G2中的副本则不接受。

因此，在系统中，即使系统可以容忍多达33个拜占庭式错误副本（包括主副本），但在您的假设中它立即失败。

I know there are some questions on this website that asks the same questions. However the answer is never clear:

In PBFT, why cant the replicas execute the requests after 2/3s have prepared? why is commit phase needed? if 2/3 + 1 replica have agreed to prepared, then I owuld think they can execute the request without broadcasting again?

解决方案

(Edited) In addition to previous (incomplete) answer, a quote from from Practical Byzantine Fault Tolerance and Proactive Recovery might help. Note that author claims that Prepare phase is enough for ordering requests in same view, but it is not enough for ordering requests across view changes, so that is why Commit phase is needed.

This ensures that replicas agree on a total order for requests in the same view but it is not sufficient to ensure a total order for requests across view changes. Replicas may collect prepared certificates in different views with the same sequence number and different requests. The commit phase solves this problem as follows.

---

Client's requests should be totally-ordered and should be executed in the exactly same order. Replicas reach consensus on the order of requests in prepare phase by collecting prepare messages by quorum size you mentioned, but doesn't execute it right away in that phase because they have to execute the same request in the same order. (In State Replication Machine system, all the state machines have to deterministically execute the same request in the same order to satisfy safety condition; Execution order affects the state machine's state)

So in commit phase, they have to reach consensus on the execution timing so that they execute the same request in the same time unit for safety condition.

Following your comment "Once the replicas received 2/3 prepared, they can commit", the internal state of each state machines(PBFT's node) would diverge, violating safety condition. That is why commit phase is needed.

---

Answer to your comment;

Above situation is possible when the replicas execute the request as soon as they get the prepare messages by quorum size. I think the important fact that PBFT assumes partial synchrony; messages can be arbitrarily delayed due to unstable network speed or adversary, but eventually received. So each replica can execute the request message at different time point, and the one example situation is illustrated.

---

Answer to your second comment

I think I need to elaborate the answer with illustrating coordinated attack of malicious replicas including primary. Let's say n replicas where n = 3f + 1 = 100, f = 33 in Byzantine fault tolerant system. In the system, the system can tolerate f number of Byzantine faulty replica. Now I give an counter-example to answer your question. Consider the following setting; I partitioned n replicas into three group;

1. G1 = {b1, b2, ... , b33} for Byzantine faulty replicas including Byzantine primary(b1), |G1| = 33
2. G2 = {r1, r2, ... , r33} for correct replica group, |G2| = 33
3. G3 = {r34, r35, ... , r67} for correct replica group, |G3| = 34

Because n = |G1| + |G2| + |G3| = 33 + 33 + 34 = 100, above partition makes sense. And G1 is entirely controlled in a coordinated way by super-genius hacker who are especially interested in destroy the protocol.

Now, I will demonstrate how above setting violates safety condition if the commit-phase disappears from the protocol; (The safety condition means that the state of G2 and G3 should be the same). For simple description, the consensus value is simplified as a binary value, not the request with sequence number.

1. [Pre-Prepare phase]: Primary(b1) sends a 0 value to G2 and 1 value to G3. This situation is not a problem cause we assume Byzantine primary.

2. [Prepare phase]: Now replicas in G2 and G3 exchange the message from the primary to check if they both have the same message. But, In this phase, replicas from G1 sends a 0 value to G2 and sends a 1 value to G3. After message exchange, the situation is as follows

   a. Replicas in G2 received following results; 66 votes for 0 value, 34 votes for 1 value.

   b. Replicas in G3 received following results; 33 votes for 0 value, 33+34=67 votes for 1 value.

Because quorum size is 2f+1 = 67, replicas in G3 accepts the proposed value from Byzantine primary who coordinates with Byzantine replicas while replicas in G2 doesn't.

So in the system, even though the system can tolerate up to 33 Byzantine faulty replicas including primary, it immediately fails in your assumption.

这篇关于PBFT：为什么2/3准备好后副本不能执行请求？为什么我们需要提交阶段？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！