PBFT

Practical Byzantine Fault Tolerance（Castro & Liskov，1999）。许可集合上的拜占庭复制状态机：三阶段投票 + view-change。模型见 BFT。

系统模型

• \(n = 3f+1\) 副本，至多 \(f\) 个拜占庭。
• 视图 \(v\) 的主节点 \(p = v \bmod n\)。
• 客户端接受 \(f+1\) 条相同 reply（至少 1 条诚实）。
• 消息带签名（或 MAC）。无不可伪造认证则 quorum 相交不成立。
• 部分同步：safety 不依赖计时；liveness 依赖 GST 后超时大于 \(\Delta\)。

不变量：诚实副本对同一序号 \(n\) 提交相同请求 \(m\)。已 committed 的 \(m\) 在后续视图中不得被替换。

正常路径

sequenceDiagram
  participant C as Client
  participant P as Primary
  participant R as Replicas
  C->>P: REQUEST m
  P->>R: PRE-PREPARE(v, n, d)
  R->>R: PREPARE(v, n, d, i)
  Note over P,R: prepared := PRE-PREPARE + 2f PREPARE
  R->>R: COMMIT(v, n, d, i)
  Note over P,R: committed := 2f+1 COMMIT
  R->>C: REPLY

记 \(d = H(m)\)。

1. Pre-prepare。主节点分配序号 \(n\)，广播 \(\langle\text{PRE-PREPARE}, v, n, d\rangle_{\sigma_p}\)。备份校验：签名、\(v\) 为当前视图、\(n\) 在水印窗口 \((h, H]\)、同一 \((v,n)\) 未接受过其它 \(d\)。
2. Prepare。备份广播 \(\langle\text{PREPARE}, v, n, d, i\rangle\)。副本 \(i\) 在持有匹配 pre-prepare 且收到 \(2f\) 条匹配 prepare 时进入 prepared（合计 \(2f+1\)）。prepared 意味着本视图内诚实节点不会再给 \(n\) 绑定另一个 \(m\)。
3. Commit。prepared 后广播 \(\langle\text{COMMIT}, v, n, d, i\rangle\)。收到 \(2f+1\) 条匹配 commit 后进入 committed，按序号执行，reply 客户端。

Prepare 把本视图对 \((n,m)\) 的锁定扩散开；Commit 保证该锁定已被足够多副本看见，从而能随 view-change 转移。仅 prepared 未 committed 时，新视图仍可能把该序号改成 no-op。

正常路径每阶段全对全，通信 \(O(n^2)\)。

水印

稳定检查点推进低水位 \(h\)，高水位 \(H = h+L\)。\(h\) 之前的日志可丢；超出 \(H\) 的 pre-prepare 被拒绝，防止主节点把序号拉飞。

View-change

备份在当前视图超时未提交则广播：

\[ \langle \text{VIEW-CHANGE}, v+1, n_{\text{last}}, C, P_{\text{set}}, i \rangle \]

• \(n_{\text{last}}\)：最近稳定检查点序号。
• \(C\)：检查点证明。
• \(P_{\text{set}}\)：检查点之后已 prepared 的请求及其 \(2f+1\) prepare 证明。

新主节点 \(p’=(v+1)\bmod n\) 收集 \(2f+1\) 条 view-change 后构造 new-view：

1. 取消息中最高稳定检查点为起点。
2. 检查点之后每个序号：若 \(P_{\text{set}}\) 中存在该序号的 prepared 证明，必须沿用该 \(m\)；否则填 no-op。
3. 广播 \(\langle\text{NEW-VIEW}, v+1, V, O\rangle\)。\(V\) 为那 \(2f+1\) 条 view-change，\(O\) 为选定的 pre-prepare 列表。

备份重算 \(O\) 是否符合上述规则，然后从这些 pre-prepare 重新走 prepare/commit。

提交保持：若 \(m\) 已在旧视图 committed，则至少 \(f+1\) 个诚实节点已 prepared。任意 \(2f+1\) 条 view-change 的交集包含这 \(f+1\) 个诚实节点之一，新主节点无法改掉 \(m\)。

View-change 仍是全对全，并携带历史证明，复杂度 \(O(n^2)\) 且消息更大。HotStuff 把切换收成「新领导携带最高 QC」。

活性

超时必须在 GST 之后大于 \(\Delta\)。过短导致持续空切（livelock）；过长让坏主节点拖死进度。原论文用指数退避拉长超时。

部署边界

节点身份已知、规模约数十、需要确定最终性的许可系统。公链不能直接用：没有身份就没有 \(n=3f+1\) 的分母；\(n\) 到数百时平方通信先饱和。公链路径是质押选出有界委员会再投票（CometBFT），或线性化视图切换（HotStuff）。