Source: https://dl.acm.org/doi/10.1145/3132747.3132757

Algorand: Scaling Byzantine Agreements for Cryptocurrencies

区块链 BIT-NetLab

Gilad Y, Hemo R, Micali S, et al. Algorand: Scaling Byzantine Agreements for Cryptocurrencies[C]//Proceedings of the 26th ACM Symposium on Operating Systems Principles (SOSP). ACM, 2017: 51-68.

在比特币中确认一笔交易需要等待大约一个小时——这是工作量证明（PoW）机制为防止分叉而不得不付出的代价。发表于 SOSP 2017 的 Algorand，由 MIT CSAIL 的图灵奖得主 Silvio Micali 等人提出，从根本上消除了分叉的可能性，将交易确认时间缩短至分钟级，同时吞吐量达到比特币的 125 倍。其核心是一个名为 BA⋆ 的拜占庭共识协议，通过可验证随机函数（VRF）实现了面向百万级用户的高效共识。

一、研究动机：PoW 共识的根本瓶颈

比特币使用 PoW 让矿工通过计算哈希竞争出块权，最长链被视为权威链。然而 PoW 天然允许分叉存在——两条不同的链可能同时具有相同长度。为缓解分叉风险，比特币将出块间隔设为 10 分钟，并推荐等待 6 个区块确认。结果是确认一笔交易需要约一个小时。

传统拜占庭容错（BFT）协议虽然能快速达成共识，但它们依赖固定的服务器集合，无法抵抗女巫攻击（Sybil Attack），也难以扩展到大规模用户场景。而混合方案（如 ByzCoin）虽然将延迟降至 35 秒，但仍因使用 PoW 选取参与者而存在分叉风险，且只能抵抗”温和自适应”的攻击者。

Algorand 的目标是在开放、去中心化的环境中，同时实现低延迟、无分叉和强扩展性。

二、三大核心技术

Algorand 围绕三个关键挑战分别提出了解决方案。

第一，抵抗女巫攻击。Algorand 以用户持有的货币量作为权重。只要超过总货币量 2/3 的用户是诚实的，BA⋆ 就能保证共识安全。攻击者必须投入大量资金才能影响共识结果，而将资金分散到多个伪身份（女巫）并不能获得额外优势——这一点通过二项分布的可加性得到数学保证。

第二，将拜占庭共识扩展到百万级用户。BA⋆ 在每一步协议中从全体用户中随机选出小规模委员会执行共识，其他用户通过观察消息获知结果。委员会规模与总用户数无关，仅取决于安全参数，因此通信开销保持可控。

第三，防止对委员会成员的定向攻击。Algorand 引入密码学抽签（Cryptographic Sortition）：每个用户在本地计算私钥与区块链公开种子的 VRF，私密地判断自己是否被选中。攻击者在用户发送消息前无法得知其身份。更关键的是，BA⋆ 要求委员会成员只需发言一次，发言后立即被替换——协议不保留任何私有状态（除私钥外），所有用户平等地具备参与下一步的能力。

三、BA⋆ 协议的运行流程

BA⋆ 分为两个阶段。第一阶段”归约”（Reduction）将对任意区块达成共识的问题简化为两个候选值的选择；第二阶段”二值共识”（BinaryBA⋆）在这两个值之间达成最终一致。

区块提案环节中，所有用户执行密码学抽签判断自己是否被选为提议者。由于可能有多个提议者，Algorand 利用 VRF 输出的哈希值为每个提案赋予优先级，用户只关注最高优先级的区块。为减少通信开销，系统先广播仅包含优先级证明的小消息（约 200 字节），让用户快速识别最高优先级提议者后再接收完整区块。

BA⋆ 区分”最终共识”（Final Consensus）和”暂定共识”（Tentative Consensus）。在强同步网络中，如果最高优先级提议者是诚实的，BA⋆ 仅需 4 步交互即可达成最终共识。为解决诚实用户可能被分裂为两组的僵局，BinaryBA⋆ 的第三步引入”公共硬币”机制——基于 VRF 输出的最小哈希值的最低有效位产生一个对多数用户相同的随机比特。每次循环，共识以至少 1/3 的概率达成，使协议快速收敛。

四、安全性设计

Algorand 的安全目标是：以压倒性概率，所有诚实用户对已确认交易达成一致，即使部分用户被网络隔离也不例外。

活性方面，Algorand 依赖”强同步”假设：95% 的诚实用户的消息能在已知时间内被 95% 的其他诚实用户收到。安全性则依赖更宽松的”弱同步”假设：网络可被攻击者完全控制一段有限时间（如一天或一周），但之后必须恢复强同步。

为应对弱同步期间可能产生的分叉，Algorand 设计了恢复协议：用户被动监控所有 BA⋆ 投票并跟踪所有分叉，定期通过 BA⋆ 就应采纳的分叉达成共识，选择最长分叉以确保所有最终共识区块被保留。

五、实验评估：分钟级确认与百倍吞吐提升

论文在 1,000 台 Amazon EC2 虚拟机上部署了 Algorand 原型系统，模拟了 5,000 到 500,000 的不同用户规模。

延迟方面，Algorand 在 50,000 用户规模下确认一个 1MB 区块仅需约 22 秒。随着用户数从 5,000 增加到 50,000，延迟几乎保持不变；扩展到 500,000 用户时，延迟增加也十分有限。

吞吐量方面，使用 10MB 区块时，Algorand 每小时可提交约 750MB 的交易数据，是比特币（每小时 6MB）的 125 倍。BA⋆ 的共识时间与区块大小无关，始终约为 12 秒，意味着增大区块可有效摊薄共识开销。

资源消耗方面，每个 Algorand 进程仅使用约 6.5% 的 CPU 核心和约 10 Mbit/s 带宽。通信开销与总用户数无关，仅取决于委员会规模。

在恶意用户场景下，即使恶意用户比例达到 20%（最高优先级提议者向不同节点发送不同版本区块），Algorand 的性能也未受到显著影响。

六、总结与展望

Algorand 证明了拜占庭共识可以在去中心化、开放参与的加密货币场景中高效运行。通过密码学抽签、委员会即时替换和公共硬币等精巧设计，BA⋆ 实现了分钟级交易确认和数量级的吞吐量提升，同时从根本上消除了分叉。

论文也指出了若干开放问题：如何设计激励机制鼓励用户参与共识？如何降低新用户同步全量区块数据的成本？如何通过前向安全性防止攻击者事后腐化足够多的用户密钥伪造证书？这些方向的推进将进一步完善 Algorand 的工程落地能力。

论文链接：https://dl.acm.org/doi/10.1145/3132747.3132757