OneMore14

Practical Byzantine Fault Tolerance(PBFT)

•

原文

1. Introduction

本文介绍实际可用(practical)的能容忍 BFT 的系统，和非 BFT 服务相比，性能开销很少。

2. System Model

在这个模型中，网络是异步的，可以丢失、乱序、重复、延迟。

认为每个 faulty 节点是相互独立的，为此可以要求有不同的密码，运行在不同的OS上之类的。

使用加密技术防止 spoofing 和 replays，还可以检测corrupted messages。每条消息都有公钥签名，和通用做法一样，节点 \(i\) 先对消息 \(m\) 进行哈希得到摘要 \(D(m)\)，然后对摘要签名得到 \(\langle m \rangle_{\sigma_i}\)

在这个模型中，允许对手能协调faulty nodes，延迟通讯，甚至delay正常节点(但是不能无限delay)。再假设对手有算力约束，不能伪造电子签名，也不能找到两段同样的内容，使其摘要相同。

3. Service Properties

本算法可以用于实现任何 deterministic replicated service with a state and some operations。注意需要是确定性服务，即给定状态和输入，所有节点的输出应该一样。

只要faulty节点不超过 \(\lfloor \frac{n - 1}{3} \rfloor\) 本算法保证 safety (即linearizability) 和 liveness. 但是，无法保证faulty client的破坏，比如坏 client 故意往filesystem里写垃圾数据。

本算法不需要 synchrony 来保证 safety，只是用来保证 liveness，否则本算法就能在异步环境下同时保证safety和liveness，但这是不可能的(见 Impossibility of Distributed Consensus With One Faulty Process)。因此 liveness 要求发出的消息不能一直丢失，要保证在某段时间内能够达到目的地，这也符合实际情况。

\(3f + 1\) is the minimum number of replicas that allow an asynchronous system to provide the safety and liveness properties when up to \(f\) replicas are faulty

本算法不保证fault tolerant privacy，faulty节点可能泄露信息给attacker。

4. The Algorithm

大体上是，整个系统由view(类似于Raft中的term)驱动，view是连续的且有编号，每个view的primary节点可以不同，比如对编号取模。

  1. client向这个view的primary节点发起请求
  2. primary节点广播请求
  3. 各节点执行请求，并返回结果
  4. client等待 \(f + 1\) 个节点的回复，这些节点的回复内容必须一样，这个内容就是请求的结果

由于前面规定了服务必须是确定性的，因此保证safety就是要保证 all non-faulty replicas agree on a total order for the execution of requests despite failures.

4.1 The Client

client \(c\) 发送消息请求 \({\langle REQUEST,o,t,c \rangle}_{\sigma_c}\) 给primary， \(o\) 是operation， \(t\) 是时间戳，用于保证exactly once语义。client \(c\) 的时间戳需要是递增的用于排序请求。

节点 \(i\) 直接回复给client消息 \({\langle REPLY, v, t, c, i, r \rangle}_{\sigma_i}\) 。其中 \(v\) 是current view number, \(r\) 是操作结果。

如果client没有及时收到足够回复，会广播请求给所有节点。如果节点已经处理过该请求，那么就重发回复。如果节点不是primary，那么转发请求给primary。如果primary没有广播请求给节点，最终会被认为primary挂了，发起view change(重新选主)

In this paper we assume that the client waits for one request to complete before sending the next one.

4.2 Normal-Case Operation

我觉得应该把这张图放在最前面，对流程有个大致了解，首先client发起请求给primary，然后primary广播请求，各个节点也会广播消息。每个节点根据收到的”可靠”消息的数量决定是否进入下个阶段，最后返回结果给client。

image-20240701152221469

每个节点除了有服务的state以外，还有 message log 保存接收到的消息，以及current view。

当primary \(p\) 收到client request \(m\) 时，开启3阶段协议广播请求。

  • pre-prepare primary 分配一个序号 \(n\) 给请求，广播 \(\langle {\langle PRE\_PREPARE,v, n, d \rangle}_{\sigma_p} , m\rangle\) 其中 \(v\) 是view number，\(d\) 是请求 \(m\) 的摘要。节点 accept 这个消息，如果满足以下条件

    1. the signatures in the request and the pre-prepare message are correct and \(d\) is the digest for \(m\)
    2. it is in view \(v\)
    3. it has not accepted a pre-prepare message for view \(v\) and sequence number \(n\) containing a different digest
    4. the sequence number in the pre-prepare message is between a low water mark \(h\), , and a high water mark \(H\)

    第4个条件将在后续介绍。

  • prepare 如果节点接受了pre-prepare请求，就进入prepare阶段，广播 \({\langle PREPARE,v,n, d,i \rangle}_{\sigma_i}\) 给所有节点。并且把2条消息都写进log。如果不接收，则没有任何动作。一个节点如果验证 prepare 消息的签名、view number且 \(n\) 在 \(h\) 和 \(H\)之间，就接收prepare消息，并写入自己的log。

    定义 \(prepared(m, v, n, i)\) 为 true，如果节点 \(i\) 收到 \(2f\) 个来自其他节点的对应的 prepare 消息。

    pre-prepare 和 prepare 阶段保证了 non-faulty 节点对同一个view的所有请求顺序达成了一致。或者说，是保证了在view \(v\) 时编号为 \(n\) 的请求一定是\(m\)，而不是其他请求(除非发生哈希碰撞)。因为当 \(prepared\) 为 true 时，实际是有 \(2f + 1\) 个节点接受了请求 \(m\) 的序号。如果存在另外一个请求 \(m'\) 被分配了同样的序号，且其prepared 为true，因为最多有 \(f\) 个faulty节点，所以必然存在一个诚实节点，其同时接受了\(m\) 和 \(m'\) ，与假设矛盾。

  • commit 当节点 \(i\) 的 prepared 为 true 时，开始 commit 阶段，节点发出commit广播 \({\langle COMMIT,v, n, D(m),i \rangle}_{\sigma_i}\)。同时，节点也会接受别人的commit广播，只要能通过消息验证。

    定义 \(committed(m, v, n)\) is true if and only if \(prepared(m, v, n, i)\) is true for all \(i\) in some set of \(f + 1\) non-faulty replicas.

    定义 \(committed\_local(m, v, n)\) is true if and only if \(prepared(m, v, n, i)\) is true and \(i\) has accepted \(2f + 1\) commits(包括自己，且是对应的commit)

    commit阶段保证了如果诚实节点的committed_local 为 true，那么该请求的 committed 也为true。进一步可以保证，只要在诚实节点 committed_local 为 true，那么最后一定能committed。

    每个节点在 committed_local为 true 且已经执行了所有更小的请求时，节点可以真正执行请求，并返回结果。

4.3 Garbage Collection

由于节点需要写很多接受到的消息，因此需要清理不需要的内容，但如果诚实节点把某个消息都删掉了，那么如果有某个节点需要跟上集群进度时，就需要接收其他节点的状态，因此需要为状态(state)生成证明。

证明可以每过100个请求后生成一次，每当节点 \(i\) 生成状态证明后，广播消息 \({\langle CHECKPOINT, n, d, i \rangle}_{\sigma_i}\) ，其中 \(d\) 是状态的摘要。如果节点收到 \(2f + 1\) 个相同摘要的证明，那么这 \(2f + 1\)就是状态的证明。

A checkpoint with a proof becomes stable and the replica discards all pre-prepare, prepare, and commit messages with sequence number less than or equal to \(n\) from its log; it also discards all earlier checkpoints and checkpoint messages.

4.4 View Changes

如果节点timer expires，会自动发起view change，停止接收用户request的消息，广播 \({\langle VIEW\_CHANGE , v + 1, n, C, P\rangle}_{\sigma_i}\) 消息，其中 \(n\) 是其最新stable proof中的序号，\(C\) 是最新stable proof的 \(2f + 1\)个证明，\(P\) 里包含所有编号大于 \(n\) 的已经 prepared 为 true 的消息和证明。

当 \(v + 1\)的primary收到 \(2f\) 个有效的 view_change 消息后，广播 \({\langle NEW\_VIEW, v +1, V, O \rangle}_{\sigma_p}\) 其中\(V\) 是\(2f + 1\)个view_change请求, \(O\)是一套pre-prepare messages，包含还没有进入latest stable的请求。节点收到 new_view 并验证成功后，进入 v + 1, 可能会对一些请求重做3阶段的流程，但如果已经执行过，最后并不会真的执行。

x. 附

后续章节还有讲Correctness(但比较简略)，优化和实现的，不是很重要先略过。

为什么\(n = 3f + 1\) ? 因为也要考虑节点故障(不响应)的情况，假设这样的节点有 \(f\) 个，但他们其实是好节点，那么正常运行的好节点只有\(n - 2f\) 个，而运行中的坏节点有\(f\) 个，要 \(n - 2f > f\) 。所以其实是结合了故障节点和坏节点的考虑才要求\(3f + 1\)，而不是\(2f + 1\)