block chain DAY 4¶
约 10379 个字 1 张图片 预计阅读时间 52 分钟
拜占庭容错（BFT）共识算法概述¶
定义：¶
BFT共识算法是分布式系统的核心，即使在出现任意故障（拜占庭故障，即故障服务器行为不受限制，可能撒谎、发送错误消息、串通等）的情况下，也能提供安全性和活性保证。
应用：¶
- 长期用于安全关键系统，如飞机、潜艇等，在恶劣环境下（极端天气、辐射）硬件可能变得不可靠。
- 近年来，随着区块链技术的发展，BFT算法被广泛部署于众多区块链平台，提供无需第三方信任的去中心化解决方案，支持加密货币、供应链、国际贸易平台和物联网（IoT）等应用。
- 在这些应用中，由于恶意行为日益普遍，BFT算法对于共识的正确性保证至关重要。
挑战：¶
- 不同算法使用的假设（如故障模型、网络模型）差异大。
- 复杂性指标（如消息复杂性、时间复杂性）标准不一致。
- 缺乏全面、标准和直观的协议描述（如消息传递模式和工作流程）。
BFT共识算法分类（分类法）¶
文章提出了BFT共识算法的三大类分类法：
- 更高效的BFT (More Efficient BFT)：
- 目标：专注于提高复制效率，如减少消息复杂性和共识前的流水线机制。
- 子类别：
- 减少消息复杂性：如Zyzzyva、SBFT、HotStuff。
- 多领导者共识：如MirBFT、ISS。
- 基于DAG的协议：如DAG-Rider、Narwhal、Bullshark、Shoal。
- 更鲁棒的BFT (More Robust BFT)：
- 目标：优先考虑针对各种攻击和恶意行为的鲁棒性和安全性。
- 子类别：
- 防御各种攻击：如Prime（时间攻击）、Spin（垄断攻击）、Aardvark（性能攻击）。
- 声誉共识：如Prosecutor、PrestigeBFT。
- 排序公平性：如Pompe、Fairy。
- 更可用（高可用）的BFT (More Available BFT)：
- 目标：优先考虑在不同网络条件下（包括异步协议和无领导者协议）的可用性和系统响应性。
- 子类别：
- 异步和无领导者协议：如DBFT、BEATS、Honeybadger。
BFT共识的背景概念¶
共识问题和状态机复制（SMR）：¶
- SMR是分布式系统中通过一组服务器副本协调工作，为客户端提供一个或多个服务的模型。
- 状态机包括状态变量（系统当前状态）和命令（不同状态间的转换）。
- 共识算法同步和协调多个状态机，确保每个机器计算相同结果，即使部分机器出现故障也能保持统一和一致的系统状态视图。
拜占庭故障：¶
SMR中最强的故障形式。故障服务器可以表现出任意行为，包括改变消息内容和变异自身状态，并可能与其他故障服务器串通，共同表现恶意行为。与良性故障（消息内容不变，状态变化可检测）不同。
拜占庭法定人数（Byzantine Quorums）：¶
- BFT算法的决策通常依赖于法定人数证书（Quorum Certificates），即从不同参与者收集的一组相同消息。
- 容忍良性故障的最小法定人数大小是 \(f+1\)。
- 容忍拜占庭故障的最小法定人数大小是 \(2f+1\)。在总共 \(n=3f+1\) 个节点中，由于假设有 \(f\) 个故障节点，系统必须足够灵活以在法定人数中排除 \(f\) 个故障节点，并至少包含 \(f+1\) 个非故障节点。
网络假设：¶
- 同步网络：消息传递时间有固定上限（\(\Delta\)），处理器时钟差异有固定上限（\(\delta\)），允许将执行划分为轮次。
- 异步网络：消息传递无固定上限（\(\Delta\)不存在），或处理器时钟差异无固定上限（\(\delta\)不存在）。
- 部分同步网络：\(\Delta\)和\(\delta\)都存在但未知，或在全局稳定时间（GST）后已知。
复杂性度量：¶
- 消息复杂性（Message Complexity）：发送消息的总数。在 \(n\) 个服务器的完全连接集群中，如果一个服务器广播消息 \(k\) 轮，消息复杂性为 \(O(kn)\)；如果每个服务器广播消息 \(k\) 轮，则为 \(O(kn^2)\)。
- 时间复杂性（Time Complexity）：共识执行所需的消息传递轮数。如果服务器 \(S_i\) 向 \(S_j\) 发送消息，\(S_j\) 回复 \(S_i\)，时间复杂性为2。
服务属性（正确性保证）：¶
- 终止（Termination）：每个非故障服务器最终决定一个值。
- 协议（Agreement）：没有两个非故障服务器决定不同的值。
- 有效性（Validity）：如果所有服务器输入相同，则非故障服务器决定的任何值必须是该共同输入。
- 这些属性也可解释为：
- 安全性（Safety）：在故障存在下，没有两个非故障副本对请求的执行总顺序达成不同意见。
- 活性（Liveness）：如果输入正确，执行最终会终止；在SMR中，客户端最终会收到对其请求的回复。
更高效的BFT共识算法（代表性算法）¶
- PBFT (Practical Byzantine Fault Tolerance)：
- 模型与属性：开创性的BFT共识实用解决方案。在 \(n=3f+1\) 个副本中最多容忍 \(f\) 个故障副本。在异步网络中提供安全性，但活性需要有界消息延迟的同步性。复制协议通过视图（views）连续进行，每个视图有一个主副本。
- 复制协议：
- 客户端向主节点发起操作（Request Phase），设置计时器。若 \(f+1\) 条回复，则操作完成。若超时，则向所有副本广播请求。
- 主节点开始共识：Pre-prepare Phase（分配唯一序列号，组装PRE-PREPARE消息并发送给所有备份）。
- Prepare Phase（备份验证PRE-PREPARE，广播PREPARE消息；收集2f个PREPARE消息后，认为请求已准备好，形成法定人数证书）。
- Commit Phase（副本广播COMMIT消息；收集2f个COMMIT消息后，认为请求已提交）。
- Reply Phase（备份向客户端发送REPLY消息；客户端等待 \(f+1\) 条有效签名的回复以确认）。
- 使用检查点（Checkpoints）定期验证执行状态，形成稳定检查点以清理旧日志。
- 视图变更协议：
- 当主节点失败时（客户端请求超时），备份启动视图变更。
- 进入新视图（\(v+1\)），新主节点为 \(P=(v+1)\) mod \(n\)。
- 备份广播VIEW-CHANGE消息（包含新视图号、最新稳定检查点信息C、以及预准备P和准备Q的请求信息）。
- 新主节点收集 \(2f-1\) 个VIEW-CHANGE-ACK消息，形成视图变更证书。
- 新主节点广播NEW-VIEW消息，包含新视图号V和之前视图中未提交但被法定人数看到的请求X。
- 备份验证新主节点的决定，否则再次启动视图变更。
- 优缺点：
- 优点：开创性实用解决方案，对高效BFT算法影响深远，被许多许可型区块链采用。扩展版本支持主动恢复。
- 缺点：二次消息复杂性 \(O(n^2)\) 限制其大规模应用。故障客户端可能导致系统重复视图变更而无法进展。
- SBFT (A Scalable and Decentralized Trust Infrastructure)：
- 模型与属性：领导者型BFT共识算法，容忍 \(f\) 个拜占庭服务器和 \(c\) 个崩溃或滞后服务器，共 \(3f+2c+1\) 个服务器。在无故障同步网络下有“快速路径”，否则无缝切换到“慢路径”（linear-PBFT），无需视图变更。通过使用门限签名将消息复杂性从 \(O(n^2)\) 降低到 \(O(n)\)。
- 复制协议：
- 快速路径：主节点发送指令；服务器验证后将回复发送给Commit Collector (C-collector)；C-collector收集签名回复，聚合为门限签名消息广播给其他服务器；Execution Collector (E-collector) 收集回复，聚合为门限签名消息并分发给客户端。
- linear-PBFT：在故障或部分同步下切换。消息复杂性为 \(O(n)\)。主节点始终是最后一个收集器。
- 视图变更协议：消息传输复杂性为 \(O(n^2)\)。由副本触发超时或 \(f+1\) 副本怀疑主节点故障的证明来启动。新主节点收集 \(2f+2c+1\) 个视图变更消息，发起新视图。
- 优缺点：
- 优点：门限签名实现线性消息传输。客户端通信从 \(O(f+1)\) 降至 \(O(1)\)。
- 缺点：继承PBFT的弱点。故障客户端可能通过选择性通信触发不必要的视图变更。
- HotStuff (BFT Consensus in the Lens of Blockchain)：
- 模型与属性：领导者型BFT共识算法，容忍 \(f\) 个拜占庭服务器，共 \(3f+1\) 个服务器。活性需要部分同步网络，安全性不依赖同步假设。保证乐观响应性（\(2f+1\) 条消息即可进展）。每个共识实例轮换主服务器以确保链质量。使用门限签名实现线性共识（\(O(n)\) 消息复杂性）。
- 复制协议：
- 客户端广播请求。主节点广播PREPARE消息；副本验证后发送签名prepare-vote给主节点。
- 主节点收集 \(2f+1\) 个prepare-vote形成prepareQC，广播PRE-COMMIT消息。副本存储prepareQC，发送commit-vote给主节点。
- 主节点收集 \(2f+1\) 个commit-vote形成pre-commitQC，广播COMMIT消息。副本更新lockedQC，发送COMMIT vote给主节点。
- 主节点收集 \(2f+1\) 个COMMIT vote，广播DECIDE消息。副本执行操作，递增viewNum，发送NEW-VIEW给新主节点。客户端等待 \(f+1\) 条回复确认。
- 每个共识实例轮换领导者。
- 视图变更协议：频繁的视图变更。新主节点由 \(p=v\) mod \(n\) 决定。
- 优缺点：
- 优点：门限签名实现线性消息传输。决策可以流水线化，降低时间复杂性。可扩展到无许可区块链。
- 缺点：频繁的领导者轮换在故障存在时会出现问题。故障服务器被分配主节点职责时吞吐量显著下降。
- ISS (State Machine Replication Scalability Made Simple)：
- 模型与属性：通用框架，将单领导者全序广播（TOB）协议扩展为多领导者协议。通过将工作负载分配给多个领导者，每个领导者运行一个独立的Sequenced Broadcast (SB) 实例，从而实现并行TOB实例。假设部分同步网络，容忍 \(f\) 个拜占庭故障节点，共 \(3f+1\) 个节点。吞吐量显著高于单领导者协议。
- 复制协议：
- 每个节点维护一个连续日志，包含所有接受的消息（批处理）。
- 日志分为纪元（Epochs），每个纪元包含一组连续的序列号（SNs）。纪元进一步划分为段（Segments），每个段分配给一个领导者。
- 客户端请求根据哈希函数分类到不同的桶（Buckets），每个领导者被分配一个桶。
- 领导者使用其SNs和桶中的客户端请求进行提案。
- 每个领导者运行底层TOB协议（如PBFT、HotStuff、Raft）为其SB实例达成共识，并行运行。
- 当SB实例达成共识时，所有非故障节点sb-deliver该批次。若无法达成共识，则将一个空值放入日志。
- 当所有前序SNs填满日志时，请求被SMR-DELIVERED给客户端。
- 多领导者选择：每个纪元选择多个领导者，领导者选择（LE）策略可定制，只要能保证活性。使用BFTMencius保持足够多的正确节点在领导者集中。使用故障检测器识别静默节点，并将其从领导者集中移除，分配新领导者。
- 优缺点：
- 优点：并行运行多个共识实例，显著提高吞吐量。允许客户端请求在发送后即可执行，无需等待当前纪元完成，提供更快响应。通过分桶避免重复处理请求。
- 缺点：引入额外共识延迟。客户端请求必须发送并哈希到所有节点。多领导者方式在节点故障时可能导致SB实例失败概率更高，若请求分布不均，某些节点故障会造成更大损失。
- DAG-Rider (All You Need is DAG)：
- 模型与属性：异步拜占庭原子广播（BAB）协议，具有最优时间和消息复杂性，实现量子后安全性。包含两层：基于轮次的结构化DAG用于可靠消息传播；零开销共识协议允许节点独立确定消息的总顺序，无需额外通信。使用Bracha广播，容忍 \(f\) 个故障节点，共 \(3f+1\) 个节点。通过假设全局完美硬币保证活性。
- DAG流水线：每个节点独立维护DAG，表示其对消息传播拓扑的解释。DAG按轮次进展，节点根据其轮次和事务块添加新顶点。定义强边（直接连接）和弱边（非直接连接）。客户端提案时，节点接收顶点，存入缓冲区，等待所有前置顶点到位后整合入DAG。当收到当前轮次 \(2f+1\) 个顶点后，进入下一轮并广播新顶点。最终DAG在非故障节点间收敛。
- DAG中的共识：利用完美硬币机制，节点独立检查DAG并决定要交付的区块及顺序，无需额外协调。DAG分为波次（waves），每个波次跨四轮。选择一个随机领导者顶点，交付该领导者顶点或其因果历史中的所有区块。领导者顶点必须有 \(2f+1\) 条强边连接到下一轮。
- 优缺点：
- 优点：DAG结构同时用于消息传播和投票。底层可靠广播保证DAG视图一致。实现并行事务流水线，高吞吐量。
- 缺点：高延迟，因为事务分发与共识分离。消息复杂性高 \(O(n^3 \log n + nM)\)。
- Narwhal and Tusk (A DAG-based Mempool and Efficient BFT Consensus)：
- 模型与属性：Narwhal使用基于DAG的内存池（Mempool）将事务传播与事务排序分离，以实现高性能共识。将可靠事务传播卸载到Mempool协议，共识仅负责排序少量元数据。容忍 \(f\) 个故障，共 \(n=3f+1\) 个节点。提供完整性、区块可用性、包含性、2/3因果性、1/2链质量等服务属性。
- DAG复制协议：与DAG-Rider类似，但采用新的可靠广播实现。DAG由区块组成，每个区块包含哈希签名、事务列表和上一轮区块的可用性证书。可用性证书包含对应区块的哈希以及来自 \(2f+1\) 个其他验证者的签名。
- 验证者不断接收客户端事务和证书。
- 当收到 \(2f+1\) 个证书后，验证者进入新轮次，创建新区块并广播。
- 收到区块后，验证者验证签名，确保是源验证者唯一的区块，然后签名哈希以确认。
- 当收到 \(2f+1\) 个确认签名后，验证者创建并广播可用性证书，停止广播原始区块。
- Tusk负责共识过程。通过减少波次数将共识总时间复杂性降至4.5轮。
- 优缺点：
- 优点：作为基于DAG的BFT协议的实际实现，在经验实验中吞吐量优于传统BFT算法。
- 缺点：内存池不维护顺序，导致事务共识延迟高，需等待多轮。
更鲁棒的BFT共识算法（代表性算法）¶
- Aardvark (Making Byzantine Fault-Tolerant Systems Tolerate Byzantine Failures)：
- 模型与属性：旨在提高在“宽容执行”（gracious executions，同步网络、所有客户端和服务器都正确）下实现高性能的BFT算法的鲁棒性。容忍 \(f\) 个故障副本，共 \(3f+1\) 个副本。安全性在异步网络中得到保证，活性需要有界消息延迟。强调BFT算法应首先能够容忍拜占庭故障和恶意攻击，在“不友好执行”（uncivil executions，有界网络延迟，最多 \(f\) 个拜占庭故障服务器，无限拜占庭客户端）下性能下降应保持在合理水平。
- 鲁棒性改进：更强的消息认证（签名客户端请求）、独立通信（资源隔离）、自适应领导者轮换（定期视图变更）。
- 日志复制鲁棒性：客户端请求使用数字签名进行认证。通信使用独立的NICs和线路。副本有独立的客户端请求和内部副本消息队列。验证客户端和副本消息，检查黑名单、MAC、序列、冗余、签名、每视图一次等。
- 视图变更鲁棒性：采用与PBFT相同的视图变更协议，但增加了对主节点行为的两种预期：及时、公平地发出PRE-PREPARE消息，并保持持续吞吐量。若主节点未满足，则强制视图变更，即使主节点是正确的。
- 优缺点：
- 优点：解决了PBFT类共识算法的鲁棒性问题，尤其是在容忍故障客户端方面。在不友好执行下的吞吐量下降低于宽容执行。
- 缺点：对正确主节点的严格要求（保持90%吞吐量）可能给正确副本带来不必要负担。主节点行为可能导致更多性能下降。可能不必要地替换正确主节点，阻碍更高吞吐量。
- Pompe (Byzantine Ordered Consensus Without Byzantine Oligarchy)：
- 模型与属性：构建在标准共识算法之上（如SBFT、HotStuff）的排序协议。通过民主地收集法定人数的偏好顺序来防止拜占庭副本操纵命令顺序。容忍 \(f\) 个故障副本，共 \(3f+1\) 个副本。引入“拜占庭有序共识”新属性，为每个操作分配排序指示器，防止拜占庭寡头操纵排序。
- 复制协议：
- 排序阶段：提议者广播REQUESTTS消息以征求命令的首选时间戳；提议者收集RESPONSETS消息形成法定人数后，选择中位数时间戳作为命令的顺序，并广播SEQUENCE消息。副本验证并接受顺序。
- 共识阶段：Pompe依赖于周期性运行的应用共识算法（如HotStuff）来对有序命令批次进行共识。
- 视图变更协议：没有新的视图变更设计。当主节点故障时，依赖于应用共识算法检测故障并启动视图变更。
- 优缺点：
- 优点：将BFT SMR的正确性讨论扩展到操作排序，对金融应用有重要影响。操作排序由法定人数民主决定。将共识分为排序和共识两个主要阶段。
- 缺点：未设计特定的共识算法，而是使用任何标准算法执行第二阶段。不清楚当这些算法应用于排序服务时如何保证安全性和活性。
- Spin (Byzantine Fault Tolerance With a Spinning Primary)：
- 模型与属性：解决领导者型BFT算法在故障领导者下性能下降的问题。容忍 \(f\) 个故障，共 \(3f+1\) 个副本。使用每请求轮换主节点的方式，避免特定副本的领导者垄断。使用黑名单防止被怀疑的故障副本成为主节点。
- 日志复制鲁棒性：正常操作遵循PBFT通信模式，包括PRE-PREPARE、PREPARE和COMMIT阶段。每处理一个批次请求就轮换主节点，无需序列号，使用视图号代替。副本在超时或收到 \(f+1\) 个MERGE消息时触发合并操作，确定前一视图中哪些请求可以接受和执行。
- 视图变更鲁棒性：由于每请求轮换领导者，不需要显式视图变更协议。使用黑名单排除行为不当的副本作为主节点。黑名单容量最多为 \(f\)。故障主节点触发合并操作时被列入黑名单。
- 优缺点：
- 优点：通过每请求轮换领导者，在针对主节点的恶意攻击下更鲁棒。分摊协调工作负载，缓解单主节点瓶颈。
- 缺点：在无故障情况下，领导者轮换会引入额外消息传递开销。合并操作的消息复杂性为 \(O(n^2)\)，在每次副本故障时都会触发，对系统性能产生负面影响。
- Prosecutor (Behavior-Aware Penalization Against Byzantine Attacks)：
- 模型与属性：假设部分同步网络，容忍 \(f\) 个拜占庭故障，共 \(3f+1\) 个副本。允许服务器副本主动声称自己是新主节点并进入“候选者”中间状态。通过对候选者施加计算惩罚来抑制拜占庭服务器成为主节点，惩罚难度随其过去行为而变化。
- 复制协议：高效复制客户端请求，消息复杂性为 \(O(n)\)。使用门限签名。协议有五个阶段：客户端广播请求；主节点分配顺序并发送给所有副本；副本部分签名背书并回复主节点；主节点收集 \(2f+1\) 条回复后发布提交指令；副本检查指令并通知客户端本地已提交。
- 视图变更协议：与计算惩罚相关联。包含执行计算和投票两个主要步骤。备份在计时器过期时执行类似工作量证明的哈希计算。结果需满足一定阈值，否则重复计算。满足后成为候选者，广播VOTEME消息并等待投票。若收集到 \(2f\) 票，则成为新主节点并广播NEW-VIEW消息。每次竞选会增加计算难度，行为不当的候选者会被逐渐边缘化。
- 优缺点：
- 优点：惩罚可疑故障副本，实现线性消息复杂性下的高效共识。拜占庭服务器发动攻击篡夺领导权时，会被惩罚并强制执行指数级增长的计算工作，从而被抑制和边缘化。
- 缺点：工作量证明式的惩罚在故障服务器计算能力强时效率可能降低，可能导致长时间无正确领导者。PrestigeBFT通过更细粒度和高效的方式量化可疑服务器的声誉。
- RBFT (Redundant Byzantine Fault Tolerance)：
- 模型与属性：解决Prime、Aardvark、Spin等旨在提高容错鲁棒性的方法在某些极端情况下可能导致性能下降的问题。这些极端情况通常针对主节点，可能导致单点故障。通过并行执行多个PBFT协议实例来增加共识过程中的冗余。每个副本在相应实例中扮演主节点角色。其中一个实例是“主”实例，其他是“备份”实例，监控主实例的处理速度，防止其故意减慢共识过程。容忍 \(f\) 个故障，共 \(3f+1\) 个副本。
- 复制鲁棒性：
- 请求阶段：客户端向所有副本广播请求。
- 传播阶段：副本检查签名后向所有其他副本广播请求。
- 本地PBFT实例：每个副本启动本地PBFT共识实例。
- 提交与回复：收集 \(2f+1\) 个COMMIT消息后提交请求并回复客户端。
- 冗余监控：多个并行运行的实例监控主实例的处理速度。若主实例处理速度低于阈值，则认为其故障，并启动实例变更。
- 公平性监控：实例还跟踪每个请求的平均处理延迟。若主实例对某些客户端处理时间偏离平均值过大，则认为其不公平，备份实例启动实例变更。
- 实例变更鲁棒性：与PBFT的视图变更协议类似，用于替换故障主节点。每个实例维护一个计数器 \(c\)。若主实例不满足阈值，备份实例递增 \(c\) 并广播INSTANCE-CHANGE消息。收集到 \(2f+1\) 个相同计数器的INSTANCE-CHANGE消息后，选择新的主实例，系统进入新视图。
- 优缺点：
- 优点：通过并行运行多个实例监控主实例性能，解决某些极端情况下的性能下降问题。
- 缺点：引入更多操作成本（冗余）。消息复杂性高 \(O(|M|(n^3+n^2+n))\)。在地理分布应用中，由于客户端与不同副本之间的通信延迟差异，可能导致不必要的实例变更。
更可用的BFT共识算法（代表性算法）¶
- 特点：专注于解决BFT共识中的可用性问题，在同步性有限的场景下运行。通常是无领导者算法，因为领导者型算法存在单点故障风险，且主服务器工作负载重。
-
基础构建块：
- 可靠广播 (Reliable Broadcast, Bracha's RBC)：在异步网络中实现协议。
-
发送者广播INITIAL消息。
- 接收到INITIAL消息的副本广播ECHO消息。
- 若收到 \(n-f\) 个相同ECHO消息，或 \(f+1\) 个相同READY消息，副本广播READY消息。
- 若收到 \(n-f\) 个相同READY消息，副本交付值。
-
保证若提议者正确，所有正确进程交付其提议值；若提议者故障，所有正确进程要么交付相同值，要么都不交付。
- 二元拜占庭协议 (Binary Byzantine Agreement, BA)：在异步网络中运行。通过多轮协调达到共识。每轮有三个阶段。
-
阶段1 (BV-broadcast)：每个副本提议一个估计值（0或1），广播。若收到 \(f+1\) 个相同值，则重新广播。若收到 \(2f+1\) 个相同值，则视为交付。
- 阶段2：副本广播AUX消息。
- 阶段3：若收到 \(n-f\) 个AUX消息，且所有消息包含单个值，则启动硬币翻转过程决定最终交付，并设定下一轮的估计值。
- 保证有效性（决定值由正确副本提议）、协议（无冲突决定）和终止（最终达成决定）。
1. DBFT (Democratic Byzantine Consensus)：¶
- 模型与属性：无领导者BFT协议，容忍 \(f\) 个拜占庭副本，至少 \(3f+1\) 个副本。在部分同步网络中运行，消息模式结合RBC和BA的派生版本Psync（使用弱协调器）。最佳情况下时间复杂性为6轮，消息复杂性为 \(O(n^3)\)。
- 二元拜占庭共识 (Psync)：对BA协议进行三项主要修改：增加超时触发器以处理部分同步网络；在阶段2增加弱协调器以解决冲突；在阶段3增加终止条件。弱协调器以轮询方式选择，通过广播COORD消息来解决冲突。
- DBFT协议：由RBC实例（每个实例对应一个提议值）和 \(n\) 个Psync实例（每个副本贡献一个）组成，这些Psync实例可以并行执行。
- 快速路径：若副本通过RBC交付数据，则跳过Psync阶段1的两次广播，直接从阶段2开始。
- 常规路径：若副本未通过RBC交付数据，则加入每个Psync实例，从阶段1开始，提议值为0。
- 当某个Psync实例交付1时，DBFT共识实例决定数据。
- 优缺点：
- 优点：通过引入冲突解决器（弱协调器）改进BA协议。Psync在快速路径中直接决定二元值，提高吞吐量和延迟。
- 缺点：需要部分同步网络。在有 \(f\) 个拜占庭副本时，仍需要 \(O(f)\) 的延迟。
2. HoneyBadgerBFT (The Honey Badger of BFT Protocols)：¶
- 模型与属性：无领导者BFT共识协议，容忍 \(f\) 个拜占庭副本，共 \(3f+1\) 个副本。可在异步网络中运行。使用门限加密防御审查攻击。时间复杂性为 \(O(\log n)\)，消息复杂性为 \(O(|M|n + |c|n^3 \log n)\)。
- 高效大消息可靠广播：通过在Bracha的RBC协议中使用擦除编码，将通信复杂性从 \(O(|B|n^2)\) 降低到 \(O(|B|n)\)。
- 发送者使用Reed-Solomon码编码数据批次，并分发到每个副本。
- 副本接收INITIAL消息后广播ECHO消息，并验证数据块的校验和。
- 副本在满足条件后广播READY消息。
- 收到 \(n-f\) 个READY消息后，副本收集足够数据块解码并交付。
- 带加密共同硬币的二元拜占庭协议：修改BA协议，使用门限签名生成共同硬币。新增终止条件以防BA长时间循环。
- 异步共同子集（ACS）：HoneyBadgerBFT的核心构建块。一个ACS实例包含多达 \(n\) 个修改后的RBC实例和多达 \(n\) 个修改后的BA实例并行运行。
- 阶段1：副本启动RBC实例。
- 阶段2：副本加入多达 \(n\) 个BA实例来决定是否接受提议。
- 完整协议：分三个阶段协调所有副本的步调以达成共识。
- 阶段1：副本随机选择事务批次并用门限加密方案加密。
- 阶段2：加密数据作为ACS实例的输入，获取加密数据块的集合。
- 阶段3：副本解密每个加密数据块以获取原始事务集。
- 消息复杂性与批次大小：总消息复杂性约为 \(O(|M|n+|c|n^3 \log n)\)。为获得最佳吞吐量，设置全局批次大小 \(M=\Omega(|c|n^2 \log n)\)。
- 优缺点：
- 优点：在数百个副本中可实现每秒数万次事务的高吞吐量。首个保证异步网络活性的实用解决方案。提供多种加密机制防御审查攻击。
- 缺点：为实现高吞吐量而牺牲延迟（当 \(n>48\) 时延迟较高，>10s）。擦除编码库将 \(n\) 的上限设为128。
3. BEAT (Asynchronous BFT Made Practical)：¶
- 模型与属性：包含五种无领导者异步BFT协议（BEAT0到BEAT4），旨在解决吞吐量、延迟、带宽使用和BFT存储等不同目标。受HoneyBadgerBFT启发并进行改进。
- BEAT0：
- 使用带标签的门限加密机制，并用TDH2替换基于配对的加密，显著降低加密延迟。
- 通过直接应用门限硬币剪裁器方法，替换HoneyBadgerBFT的共同硬币协议，降低获取共同硬币的延迟。
- 使用更高效的擦除编码库Jerasure 2.0，性能高于zfec，可扩展集群大小至128个副本以上。
- BEAT1和BEAT2：
- BEAT1使用原始Bracha的RBC，以获得更低的广播延迟。
- BEAT2将带标签的门限加密从服务器端移到客户端端，防止故障副本延迟事务处理进行审查攻击。使用匿名通信网络隐藏客户端信息以防御审查攻击，实现弱一致性保证（因果顺序保存）。
- BEAT3：
- 使用基于擦除编码的RBC协议AVID-FP，只在第一阶段广播分段数据块，其余阶段只传输全局交叉校验和，大幅减少网络带宽使用 \(O(|B|)\)。
- 不保证所有正确副本最终收到原始数据，但客户端可以从 \(f+1\) 个分段和校验和重建原始数据。
- 性能优于HoneyBadgerBFT，在吞吐量、延迟、可扩展性、网络带宽和存储开销方面都有提升。
- BEAT4：
- 用AVID-FP-Pyramid（使用金字塔码）替换BEAT3中的AVID-FP，降低读操作的数据重构成本。
- 金字塔码引入额外奇偶校验数据，但允许用更少信息进行部分数据重构，实现更高效数据恢复。
- 客户端可直接从对应副本请求特定数据分段和校验和，若分段故障，可先从组级别分段重建。
- 可节省50%读取带宽，增加约10%存储空间。
- 当 \(f=1\) 时延迟高于HoneyBadgerBFT，但当 \(f>1\) 时，BEAT4在所有性能指标上均优于HoneyBadgerBFT。
- 讨论：BEAT0、BEAT1、BEAT2适用于通用SMR应用，而BEAT3、BEAT4更适合BFT存储服务。
未来研究方向¶
- 可扩展性（Scalability）：在高性能（高吞吐量、低延迟）与大规模系统（数千个节点）间取得平衡仍是挑战。
- 排序公平性（Ordering Fairness）：防止故障领导者不公平处理客户端请求（如“抢跑攻击”），确保信任和公正。
- 量子安全BFT共识（Post-quantum safe BFT consensus）：当前BFT算法依赖传统密码学，易受量子计算机攻击。需研究后量子密码学或减少密码学参与来防御量子拜占庭攻击。
- 互操作性（Interoperability）：不同BFT区块链和分布式系统间的互操作性日益重要。研究跨链共识和机制以促进无缝数据和资产转移，增强系统灵活性和实用性。
- 机器学习中的BFT共识（BFT consensus for machine learning）：在分布式训练中，BFT共识对于维护数据和训练完整性至关重要，以确保机器学习模型的准确性和可靠性。在高并发多智能体系统中，高性能、鲁棒的BFT算法可防御恶意智能体和行为。
这些挑战反映了业界对构建更具可扩展性、鲁棒性和可操作性的BFT应用的需求，将极大促进安全高效分布式系统的发展和采用。
Verifiable Computing、Optimistic Approach、Coded Computing¶
在区块链领域，可验证计算 (Verifiable Computing)、乐观方法 (Optimistic Approach) 和 编码计算 (Coded Computing) 是三种不同的技术或范式，它们各自从不同角度解决区块链面临的挑战，主要是关于可扩展性、效率和信任。
1. 可验证计算¶
核心思想：
可验证计算是一种密码学技术，允许一个验证者 (verifier) 能够高效地检查由另一个证明者 (prover) 执行的计算结果的正确性，而无需自己重新执行整个计算。它旨在将计算任务外包给可能不完全受信任的第三方，同时仍然确保计算结果的完整性和准确性。
工作原理：
- 外包计算： 复杂的计算任务被外包给一个或多个计算提供者（证明者）。
- 生成证明： 证明者在执行计算的同时，会生成一个简洁的正确性证明 (proof of correctness)，这个证明通常比原始计算本身小得多。
- 高效验证： 验证者接收计算结果和证明，并使用密码学方法（如零知识证明 ZKP、SNARKs/STARKs）快速验证证明的有效性，从而确认计算结果的正确性。验证证明的开销远小于重新执行计算。
在区块链中的应用：
- 链下计算 (Off-chain Computation)： 区块链本身处理复杂计算的效率很低，成本很高。可验证计算允许将大量计算从主链转移到链下执行，然后只将计算结果和相应的正确性证明提交到链上进行验证。这显著提高了区块链的可扩展性和吞吐量。
- 智能合约的复杂逻辑： 使得智能合约能够处理更复杂、计算密集型的任务，而无需在链上消耗大量Gas。
- 数据隐私： 某些可验证计算技术（如零知识证明）还可以用于在不泄露底层数据的情况下证明计算的正确性，从而增强隐私性。
优势：
- 提高可扩展性： 大幅减少链上计算负担。
- 降低成本： 减少交易费用和资源消耗。
- 增强安全性： 即使在不信任的环境下也能保证计算结果的正确性。
2. 乐观方法 (Optimistic Approach)¶
核心思想：
乐观方法，尤其是在区块链的Optimistic Rollups (乐观汇总) 中，采取一种"性善论"的假设：默认情况下，所有链下执行的交易和计算都是有效的，除非有人证明它们是欺诈性的。
工作原理：
- 链下批处理： 大量的交易和计算在链下进行处理和打包（"汇总"），然后将汇总后的结果（通常是一个状态根的更新）提交到主链上。
- 挑战期 (Challenge Period)： 在提交到主链后，会有一个"挑战期"（通常为几天到几周）。在这个挑战期内，任何人都可以提交"欺诈证明 (fraud proof)"来质疑链下计算的正确性。
- 欺诈证明与争议解决： 如果有人发现欺诈行为，他们可以提交一个欺诈证明。主链上的智能合约会验证这个证明。如果欺诈被证实，则错误的状态更新会被回滚，并且提交欺诈行为的节点会受到惩罚（例如，他们的抵押资产会被罚没），而挑战者可能会获得奖励。
- 无挑战即最终确定： 如果在挑战期内没有提出有效的欺诈证明，那么链下提交的计算结果就被认为是最终有效的。
在区块链中的应用：
- Layer 2 扩容方案： Optimistic Rollups 是目前最流行的 Layer 2 扩容方案之一（例如 Optimism、Arbitrum），旨在提高以太坊等区块链的吞吐量并降低交易费用。
- 链下状态转换： 允许复杂的DApp逻辑在链下运行，显著减轻主链负担。
优势：
- 高吞吐量： 通过链下批处理实现更高的交易处理速度。
- 成本效益： 大幅降低链上交易费用。
- EVM兼容性好： 相对于零知识证明的方案，Optimistic Rollups 通常更容易与现有的以太坊虚拟机 (EVM) 兼容。
局限性：
- 提款延迟： 由于挑战期的存在，从 Layer 2 提款到 Layer 1 需要等待挑战期结束，这导致了用户资金的锁定时间。
- 需要活跃的监督者： 尽管理论上任何人都可以在挑战期内提交欺诈证明，但在实践中，需要有足够的激励机制来确保有足够多的"诚实"节点来监控和提交欺诈证明。
3. 编码计算¶
核心思想：
编码计算是一种利用编码理论（类似于通信中的纠错码）来提高分布式计算的鲁棒性、效率和安全性的技术。它通过在计算任务中引入冗余来应对分布式系统中常见的挑战，例如"掉队者" (stragglers)（运行缓慢或失败的节点）、通信开销和数据隐私问题。
工作原理：
- 任务编码： 原始的计算任务或数据会被编码成带有冗余信息的形式，然后分发给多个工作节点。
- 冗余处理： 每个工作节点可能只执行部分编码后的计算，或者执行多个冗余的计算。
- 容错性： 即使某些节点失败或运行缓慢（掉队），系统仍然可以通过从其他成功完成任务的节点收集足够多的结果来恢复或完成整个计算，而无需等待所有节点。
- 减少通信或隐私： 通过巧妙的编码设计，有时可以减少通信量，或者在计算过程中提供额外的隐私保护。
在区块链中的应用（潜在或研究方向）：
虽然编码计算不像可验证计算和乐观方法那样直接应用于区块链的Layer 2扩容，但在更广义的分布式系统背景下，它与区块链的某些特性是契合的：
- 分布式存储： 在去中心化存储网络中，编码计算可以增强数据的可靠性和可用性，即使部分存储节点离线也能恢复数据。
- 分布式共识： 在某些需要大量计算的共识机制中，编码计算可能有助于提高其鲁棒性，应对节点故障。
- 链下计算的容错性： 在可验证计算的外包计算阶段，如果证明者是分布式集群，编码计算可以帮助提高其容错性，确保即使部分证明者出现问题也能生成证明。
优势：
- 提高鲁棒性/容错性： 应对分布式系统中的节点故障或性能下降。
- 提高效率： 通过避免等待慢节点来加速整体计算。
- 潜在的数据安全和隐私： 某些编码方案可以提供额外的安全层。
区别总结¶
| 特性 | 可验证计算 (Verifiable Computing) | 乐观方法 (Optimistic Approach) | 编码计算 (Coded Computing) |
|---|---|---|---|
| 核心目标 | 证明计算结果的正确性，无需重新执行。 | 默认计算有效，通过挑战纠正错误。 | 提高分布式计算的鲁棒性、效率和安全性，应对故障。 |
| 信任假设 | 验证者信任证明的有效性，而非计算执行者的诚实性。 | 乐观假设诚实，通过欺诈证明机制应对不诚实。 | 基于编码冗余，容忍部分节点故障。 |
| 验证机制 | 密码学证明 (ZKP, SNARKs/STARKs) | 欺诈证明 (Fraud Proofs) | 基于编码理论的冗余和恢复机制。 |
| 关键应用 | 链下计算扩容、隐私保护、智能合约复杂逻辑。 | Layer 2 扩容 (Optimistic Rollups)。 | 去中心化存储、分布式AI训练、通用分布式计算容错。 |
| 链上交互 | 提交简洁的证明进行验证。 | 提交批处理结果，挑战期内可提交欺诈证明。 | 间接相关，主要用于优化链下分布式计算或存储。 |
| 提款/最终性 | 证明验证后立即最终确定（如果证明是有效的）。 | 有挑战期，导致提款延迟。 | 依赖于底层应用，本身不直接涉及链上最终性。 |
