Comment on page
pbft协议是什么
- PBFT是Practical Byzantine Fault Tolerance的缩写，即：实用拜占庭容错算法。该算法是Miguel Castro（卡斯特罗）和Barbara Liskov（利斯科夫）在1999年提出来的，解决了原始拜占庭容错算法效率不高的问题，算法的时间复杂度是O(n^2)，使得在实际系统应用中可以解决拜占庭容错问题。该论文发表在1999年的操作系统设计与实现国际会议上（OSDI99）。其中Barbara Liskov就是提出了著名的里氏替换原则（LSP）的人，2008年图灵奖得主。以下拜占庭容错问题简称BFT。
- BFT是区块链共识算法中，需要解决的一个核心问题，以比特币和以太访为代表的POW，EOS为代表的DPOS，以及今后以太访逐渐替换的共识算法POS，这些都是公链算法，解决的是共识节点众多情况下的BFT。而PBFT是在联盟链共识节点较少的情况下BFT的一种解决方案。
- PBFT是一个具有拜占庭容错的状态机复制。欲解决拜占庭将军问题，一个直觉的想法就是利用一轮或多轮的投票以获得多数共识。然而，要由谁来发起投票？要投几次票才能确保共识具有安全性与活跃性？PBFT的创新在于三阶段投票的设计，分为“就位”(Pre-prepare)、“预备”(Prepare)、“执行”(Commit)三个阶段。
假设
- 只有4个将军，最多能容忍1个叛徒(4 = 3f+1，f为能容忍叛徒数量，关于3f+1的意义，笔者将于下文的安全性分析详述)。
- 每个将军都有编 号(0~3)。
- 每个将军都能辨识彼此的签名。
- 每次行动都有一个序号(Sequence Number)
- 进攻/撤退会组成一连串按序号排列的序列，例如：进攻—进攻—防守—进攻— …。
- 有一个主导者(Primary)和数个验证者(Validator)。
- 主导者分成不同代，主导者的代数称为视域(View)。
- 将军们遵照循环制 (Round-robin)轮流担任主导者，例如：第1代主导者由编号1的将军担任，第2代主导者由编号2的将军担任，以此类推；第4代主导者由编号0的将军再度担任。
- 有将军主动发起轮替的提议时才会轮替主导者，该轮替机制称为视域变换(View-change)。
- 第一阶段：就位(Pre-prepare)
- 主导者负责接收拜占庭君主(Client)的进攻/撤退命令(Request)
- 由主导者负责发起提议，内容包含进攻或撤退(Message)、第几代(View)、第几次进攻(Sequence Number)。
- 主导者透过信使发送附有自己签名的“ 就位 ”讯息给其他验证者。
- 第二阶段：预备(Prepare)
- 各验证者收到“ 就位 ”讯息后需决定是否接受主导者的提议，若赞成提议则发送附有自己签名的” 预备 ”讯息给所有将军；若不赞成则不发送任何讯息。
- 发出“ 预备 ”讯息的验证者开始“ 预备 ”阶段。
- 各将军若收到3则以上“ 预备 ”讯息，则该将军进入“ 已预备 ”(Prepared)状态，这些“ 预备 ”讯息的集合统称为“ 已预备证明 ”(Prepared Certificate)
- 第三阶段：执行(Commit)
- “ 已预备 ”的将军若决定执行，则发送附有签名的“ 执行 ”讯息给所有将军；若决定不执行则不发送任何讯息。
- 发出“ 执行 ”讯息的将军开始“ 执行 ”阶段。
- 各将军若收到3则以上“执行”讯息，则执行讯息内 容，这也代表该提议取得了共识。
- 执行讯息后的将军进入“ 已执行 ”状态并将执行结果回报(Reply)给拜占庭君主。
- 回报后的将军结束这回合，静待下一个提议的到来。
- 对于拜占庭將軍問題，PBFT 算法至少通過三个阶段达成一致性的协议：
- 请求 Request、預准备 Pre-Prepare、回复 Reply
- 根据不同的协议設計，亦可能同時包含
- 准备 Prepare、确认 Commit
PBFT流程图
- PBFT是一个许可制的、基于领袖的、基于通讯的、安全性重于活跃性的共识协定。这些特点跟我们知道的区块链截然不同：
- 许可制的(Permissioned)：PBFT并非完全开放的，这是由于PBFT需要让节点能够验证彼此的讯息以及精准掌握节点的数量，基于中本共识(Nakamoto Consensus)的区块链则是属于对任何人都开放的非许可制(Permissionless)。基于PBFT的权益证明(Proof-of-stake)模型则让参与者可以依据自己的资产进行注册，兼顾对所有人开放的特性又能善用注册掌握验证所需的资讯与节点总数。
- 基于领袖的(Leader-based)：也就是先决定领袖(Leader)，再由领袖送出提议，这样做最直接的好处就是不需要浪费自己的运算资源去争取当领袖的机会，然而缺点就是只有在视域变换时才轮替领袖，成为领袖的机会并不公平，缺乏加入网路的诱因；区块链则是在多个提案中选择工作证明难度最高的区块作为共识，虽然这样会造成运算资源的浪费，但是成为出块者的机率大致是公平的，其与算力成正比。近来的研究显示：可以透过公平的乱数决定领袖，这样既能保证成为领袖的机会公平，也能节省运算资源。然而怎么保证乱数产生器是公平的？这是下一个大问题。
- 基于通讯的(Communication-based)：PBFT的安全性奠基于3阶段投票，虽然不必如工作证明般消耗大量计算资源，但数量庞大的通讯也造成可扩展性的瓶颈—就算是号称最实用的PBFT ，也无法扩展到1000个以上个节点。不仅如此，PBFT使用讯息验证码(MAC)，每投一轮票就需要每一个节点验证一次讯息，大量的签名/验证也是另一个潜在的瓶颈。另一个潜在的问题是，基于通讯的模型是主观的 (Subjective)，对于远程攻击(Long-range Attack)没有抵抗能力，新参与者无从分辨哪一个才是由诚实节点维护的状态。相对地，区块链是基于计算的(Computation-based)，它的安全性奠基于可验证的计算证明，虽然在效率上不如基于通讯的作法，然而这样模型却是客观的 (Objective)，欲加入的新节点只需要根据中本共识(Nakamoto Consensus)选择困难度最高的链加入即可。
- 安全性重于活跃性的(Safety over Liveness)：PBFT不论在何种网路假设下(同步/非同步)都能确保安全性，几乎不可能出现分岔，因此具有即时敲定(Instant Finality)的特性；相对地，区块链则是活跃性重于安全性，其安全性有赖于同步的网路，而具有复数个共识(及分岔)的情况也相当常见，需要经过一定数量的区块「确认」才能保证其不再分岔的机率足够大。
Last modified 4yr ago