PBFT共识算法.md

PBFT 共识算法

　　全名 PBFT(Practical Byzantine Fault Tolerance,实用拜占庭容错算法)，PBFT是一个历久不衰的经典诞生至今已逾20年, 它的发明源于分散式系统中一个著名的共识难题：拜占庭将军问题 (Byzantine Generals Problem)。PBFT并不是一个针对全开放环境的共识协定—事实上在区块链出现之前，并未出现任何一个针对开放环境的拜占庭容错共识。 区块链的横空出世启发了研究人员再度审视PBFT这个经典。
　　PBFT具有一些与区块链截然不同的特性，这提供了改进区块链一些有用的思路，例如以PBFT为基础建立的权益证明(Proof-of-stake)模型。接下来我们将简介PBFT的起源背景、共识运作、正确性证明，以及PBFT与区块链不同的特性。
　人类自古以来便不断追求可以永续运作的系统。 一个永续的系统，首先要能够容错以避免因单一故障而停摆。 一个实现容错的直觉作法就是让系统具有一定程度的冗余  —让有多个具有相同组成与状态的个体同时运作，如此当故障发生时只需替换故障的个体便能保证系统继续运作，在分散式系统中，我们称这样的设计为状态机复制 (State Machine Replication)。

什么是状态机？

　　状态机是一个抽象的黑盒子，它具有初始状态，并且在收到输入后，能依据相应的转换函数而转换至新的状态 且转换的过程是决定性的(Deterministic) — 只要给定相同的初始状态及输入，必定会得到相同的输出。而由数个具有相同转换函数的状态机组成的系统即为状态机复制。 为什么需要共识？由于状态机具有决定性，为了使这些冗余的状态机具有一致的状态，每个状态机都必须依相同的顺序进行状态转换，因此每个状态机必须达成对转换顺序的共识，这些状态机组成一个网路，每个状态机都是网路中的节点， 节点与节点间仅能透过通讯交换讯息以达成共识。为什么共识这么难？

　　在只依赖通讯便想达成共识的情境下，会碰到一个难解的问题，这也是在共识协定中一个著名问题：拜占庭将军问题。一群拜占庭将军围攻一座城市，他们必须达成同时进攻或同时撤退的共识，且各将军只能透过信使将自己的决定通知其他人。 然而，这群将军中有叛徒，可能会发出相反的讯息干扰，或者只通知一部分的将军。在已知有叛徒存在的情况下，该如何达成正确的共识？ 显然，状态机复制的共识问题可以被化约成拜占庭将军问题：

• 节点就是将军
• 通讯就是信使
• 进攻/撤退的决策就是需达成共识的内容
• 将军/状态机的随机行为称为拜占庭错误(Byzantine Fault) · 叛徒/敌对状态机存在的情形下仍能达成共识的特性便称为拜占庭容错(Byzantine Fault Tolerance)。

正确的共识：安全性(Safety)与活跃性(Liveness)

　　一个正确、可用的共识协定必须确保拜占庭将军们一定会达成唯一的共识(安全性)，且共识一定会形成(活跃性)。 具备安全性与活跃性的共识一定可以达成吗？答案是不一定。根据FLP原理：在非同步的网路通讯及决定性的程序(Process)下，若出现任一个毁坏故障(Crash Fault)，则共识不可能同时具备安全性与活跃性。 那怎么办？有两种方法可以绕过FLP原理的限制：第一种方法是假设网路通讯是同步的—这就是PBFT所采用的方式；第二种方法是在共识协定中引入一些随机的因子，使整个协定变为非决定性的 (Non-deterministic)，这样做的优点是协定更强健，就算在非同步的网路通讯下依然可以运作， 例如Honey Badger BFT就是一个非同步且非决定性的共识。效能如何？ 在PBFT出现前，曾出现许多不同的共识协定，但是效能都不够好，直到PBFT的出现改变了一切，由其命名中的P(Practical)便能看出端倪. ##PBFT如何运作？ 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)给拜占庭君主。
• 回报后的将军结束这回合，静待下一个提议的到来。 以上的共识形成的过程非常依赖忠诚的主导者，万一主导者是叛徒呢？为了避免不提案的主导者瘫痪所有行动，将军们需要一个轮替机制，也就是视域变换：
• 每个将军从收到“预备”讯息后开始计时，转为“已执行”状态后结束计时。
• 如果在计时后T时间内未执行讯息，则该将军可以发送“ 变换 ”(View-change)讯息，讯息内容包含新的代数(目前代数+1)以及其他重要讯息。
• 如果主导者未提案，则每个诚实的验证者最终都会因为超时而发出变换讯息。
• 新主导者若收到3则以上“ 变换 ”讯息，则新主导者可以发送“ 新域 ”(New-view)讯息，讯息内容包含新代数、所有具有“ 已预备证明 ”且尚未被执行的“ 就位 ”讯息，以及其他重要讯息。
• 各验证者收到“ 新域 ”讯息后，逐一针对尚未执行的“ 就位 ”讯息进行投票流程。
• 接下来由新主导者负责接收拜占庭君主的命令。
• 如果主导者未提案，则每个诚实的验证者最终都会因为超时而发出变换讯息。
• 新主导者若收到3则以上“ 变换 ”讯息，则新主导者可以发送“ 新域 ”(New-view)讯息，讯息内容包含新代数、所有具有“ 已预备证明 ”且尚未被执行的“ 就位 ”讯息，以及其他重要讯息。
• 各验证者收到“ 新域 ”讯息后，逐一针对尚未执行的“ 就位 ”讯息进行投票流程。
• 接下来由新主导者负责接收拜占庭君主的命令。

如何保证安全性与活跃性？

　　保证安全性即是保证每个将军的对同样的行动序号都有一致的行动。例如，假设序号3的内容是“进攻”，安全性保证：不会有任何将军的序号3内容为“撤退”。 保证活跃性即是保证行动不会因为停顿的主导者而中断，而这仰赖于视域变换的运作。为了避开FLP原理的限制，PBFT使用弱同步假设(Weak Synchrony)，即假设网路延迟的增长速度慢于每次超时增加的缓冲时间。 如果在视域变换的过程中超时，则各将军再发起一次变换，并延长等待时间至2T/3T/4T…以此类推，直到等待时间可以容忍信使的延迟。 在最坏的情况下，就算碰到连续f个叛徒，也能保证其活跃性。 PBFT是一个许可制的、基于领袖的、基于通讯的、安全性重于活跃性的共识协定。 这些特点跟我们知道的区块链截然不同： 许可制的(Permissioned)：PBFT并非完全开放的，这是由于PBFT需要让节点能够验证彼此的讯息以及精准掌握节点的数量，区块链则是属于对任何人都开放的非许可制(Permissionless) 。

　　基于PBFT的权益证明(Proof-of-stake)模型则让参与者可以依据自己的资产进行注册，兼顾对所有人开放的特性又能善用注册掌握验证所需的资讯与节点总数。 基于领袖的(Leader-based)：也就是先决定领袖(Leader)，再由领袖送出提议，这样做最直接的好处就是不需要浪费自己的运算资源去争取当领袖的机会，然而缺点就是只有在视域变换时才轮替领袖，成为领袖的机会并不公平，缺乏加入网路的诱因； 区块链则是在多个提案中选择工作证明难度最高的区块作为共识，虽然这样会造成运算资源的浪费，但是成为出块者的机率大致是公平的，其与算力成正比。

　　近来的研究显示：可以透过公平的乱数决定领袖，这样既能保证成为领袖的机会公平，也能节省运算资源。然而怎么保证乱数产生器是公平的？这是下一个大问题。 综合PBFT上述的特性：许可制、缺乏参与诱因、缺乏远程攻击的抗性、过高的通讯成本，我们无法在PBFT上建立一个完全去中心化而实用的密码货币。 然而，PBFT可以作为权益证明的共识模型，而权益证明可以是非许可制的，并且能提供经济激励— 例如Ethereum Casper 就是一个结合基于计算与基于通讯模型的混合式模型 它由工作证明决定领袖，再由存入押金的验证者(Validator)进行单轮投票以敲定共识。

结语

　　尽管目前有许多难题，但非常值得期待。 尽管在区块链蓬勃发展的今日，PBFT这个经典仍然蕴含许多值得研究人员反覆推敲的巧思 其后续也衍生出非常多新协定，例如Tendermint / HotStuff / Harmony FBFT 等等。 看懂PBFT之后再回头看其他貌似高深的协定，肯定会觉得豁然开朗。

Dream 2019/12/31