深度解析Algorand共识协议

*免责声明：该文仅代表研究人员个人观点，不代表Qtum量子链基金会立场概述

1.1 引言

Algorand 称其突破了”公链不可能三角“，项目创始人是图灵奖得主、MIT CSAIL 实验室的 Silvio Micali 教授。Algorand 提出的共识协议是项目的一大亮点，本文主要分析 Algorand 共识协议的工作原理，并分析其优缺点。

1.2 Algorand 设计的初衷

Algorand 想解决的核心问题是：去中心化网络中低延时（Latency）和高置信度（Confidence）之间的矛盾[1]。

其中，延时指从发起交易到确认交易所需要的时间；置信度指的是发出的交易不会再被更改的概率。

在比特币网络中，为了提高交易的置信度，用户必须等待 6 个区块确认（约 1 个小时）的确认延时；而如果选择低延时，比如少于 6 个确认，甚至是 0 确认，则必然导致低置信度，增加“双花”攻击的可能。双花问题是绝大多数加密数字货币的核心问题。比特币中采用 PoW 共识来解决，但链本身仍然有分叉的可能，并且需要较长的共识达成过程和确认时间。

同时 Algorand 还想解决比特币中 PoW 挖矿耗费巨大资源、交易确认时间长、易分叉、网络呈中心化趋势，可扩展性差等问题。

1.3 Algorand 是什么？

根据官方描述，Algorand 是一个采用 permissionless 的纯 PoS 共识的公链项目，结合改进的拜占庭共识协议，可实现快速的交易确认，几乎不会分叉，并且用户数可无限扩展，不会影响交易确认速度。同时兼顾“可扩展、安全性、去中心化”这个“公链不可能三角”[2]。

（注：”公链不可能三角“的正确性和具体定义存在较多争议[7]。在 Algorand 中：可扩展性指在较大用户规模下仍可实现较高的吞吐量[8]，安全性指的是可以对抗恶意攻击[9]，去中心化指的是网络完全开放，成为节点没有任何门槛[10]。）

下面详细介绍 Algorand 的共识协议。

Algorand 协议详述

几乎所有公链项目的区块产生和共识的过程都可以抽象为两个步骤：

以上步骤周而复始，最终形成一条“不可篡改”的区块链。

整个共识过程虽然简单，但在实际实现中，必须解决几个关键问题：

比特币采用哈希函数的随机性来确保公平，采用工作量证明（PoW）达成共识，同时能够在一定程度上抵抗算力攻击。然而比特币仍然面临上述消耗计算资源、确认时间长、易分叉以及扩展性差等问题。以 Qtum 为代表的采用纯权益证明（PoS）共识机制的项目，同样采用了哈希函数，并且不需要消耗大量的计算资源，然而仍然面临易分叉、安全性及扩展性的问题。

Algorand 提出了一种新的共识机制解决上述 5 个问题。

2.1 基础知识

正式介绍 Algorand 共识协议之前，本文假设读者基本了解以下名词的含义：

如果读者对上述概念不理解，请先搜索相关关键词进一步了解，再阅读以下内容。

2.2 Algorand 的基本过程

Algorand 协议可以按照时间顺序划分为不同轮次，每一轮都会达成共识并生成新区块。其典型的通用过程如下：

接下来具体讨论 Algorand 共识协议细节，本节主要参考[4]。

2.3 保证 Algorand 的随机性：可验证随机函数

Algorand 利用 VRF 来选择区块生产者和验证者，保证所有共识参与者都是随机地、公平地被选出的。可验证随机函数（VRF，Verifiable Random Function）是由 Micali 教授等提出的一种伪随机函数，和普通的随机函数一样，对于不同输入，其输出也具有随机性（严格来说是“伪随机”）。其独特之处在于调用者可以提供一个证明，表明这个随机输出确实由该调用者产生。

VRF 可以有多种实现方式，Micali 等人在其原始论文中提供了一种较复杂的实现方式[3]。Algorand 利用哈希函数和数字签名的特性，提供了一种较为简单的 VRF 实现。具体实现方式是调用者 i 将输入 m 通过数字签名和哈希函数映射为固定长度的输出 H[SIGi(m)],即 m -> H[SIGi(m)]。

对于任何输入 m，不同的调用者 i 生成的数字签名 SIGi(m) 都是唯一的；而对于不同输入，哈希函数 H 的输出具有随机性，因此上述映射符合 VRF 的”随机性“要求。同时，由于 i 的数字签名 SIGi(m) 可通过其公钥对其身份进行验证，因此其也符合 VRF ”可验证“ 的特性，SIGi(m) 就是 VRF 中提到的”证明“。

这个函数特别适合在所有节点中随机选择出共识的参与者，下面具体讨论。

2.3.1 随机选出每一轮的区块生产者（Leader）

每一轮共识开始时，每个节点都可以通过以下 VRF 独立地验证自己是否是潜在的 leader：

.H[SIG(r, 1, Q(r-1))] <=1 / SIZE(PK(r-k))

其中，H 是哈希运算；SIG 是签名运算；r 是目前的轮次；Q(r-1) 为与 r-1 轮的种子（将在后续 2.6 节中解释）；SIZE(PK(r-k)) 是在 r-k 轮所有符合要求的公钥的数量（为什么是 r-k ？k 为回溯系数，也将在 2.6 节中阐述）；公式开始的 . 表示将哈希结果转化为小数位，从而保证结果为[0,1)的某个值。

节点通过自己的私钥计算上面签名的哈希值是否符合要求，从而知道自己是否属于候选的 leader，在此过程中无需和其他节点交换信息。由于哈希函数输出的随机性，可以认为符合要求的候选节点都是随机选出的。候选节点随后可以生成新区块，并向全网提供签名证实自己的身份。如果有多个候选 leader，最终上述哈希值最小的 leader 将在后续的共识中成为本轮最终的 leader。Leader 产生的区块 Br 包含了本轮的所有交易和上述的证明信息，由验证组成员进行共识验证。

2.3.2 随机选出每一轮每一阶段的验证组

验证组成员的选择与上述过程类似，在每一轮和每一阶段（step），所有节点都可以独立验证自己是否属于验证组成员：

.H[SIG(r, s, Q(r-1))] <=n / SIZE(PK(r-k))

其中 s 为本轮所处的不同阶段，Algorand 在每一轮的各个阶段都有不同的验证组，从而进一步保证安全性；n 为预期的验证组成员数量，可以人为设定；其他参数含义不再重复。

与候选 leader 一样，每一阶段的验证组成员均随机选出，验证节点在证实自己身份后，可以开始参与共识验证过程，揭露自己的签名即可证明其身份。

2.3.3 引入权益证明（Proof-of-Stake，PoS）机制

上述的随机选择过程没有考虑 Token 持有者的权重，恶意节点可能通过大量生成有效私钥从而有极大概率成为区块的生产者和验证者。Algorand 在其公布的实现建议中引入了名为 Honest Majority of Money （HMM）的条件假设，其基本思想来源于 PoS 共识机制，即在上述随机选择过程中引入代币持有量（Stake）作为权重，持有量多的节点被选中的概率较高，而代币持有者往往更倾向于保护网络的安全性。具体可以表示为如下公式：

.H[SIG(r, 1, Q(r-1))] <=(a(i,r) / M) * (1 / SIZE(PK(r-k)))

其中，a(i,r) / M 为节点所持有的币的数量占代币总数 M 的权重。其余过程与前面描述一直。

2.4 Algorand 如何对新区块达成共识：改进的拜占庭协议 BA*

Algorand 中验证者对新区块达成共识的过程，实际上是一种改进的拜占庭协议（Byzantine Agreement），Algorand 称其为 BA*。

BA* 由一种改进的二元拜占庭协议（Binary Byzantine Agreement，BBA）和分级共识协议（Graded Consensus，Protocol GC）组合而成[5]。

2.4.1 改进的二元拜占庭协议 BBA*

Algorand 引入的 BBA* 是一个改进的二元拜占庭协议（所谓二元，即只能达成 0 或 1 两种共识）。BBA* 可以在诚实节点超过 ? 的情况下，快速达成共识。其具体过程是一个 3 步循环，循环中每一步都有 ? 的概率达成共识。

节点之间需要进行 P2P 通信，假设被选中的验证节点中有 t 个恶意节点，验证组总的节点数为 n >=3t 1，即恶意节点不超过 ? 。协议过程如下：

上述协议中各符号的具体含义可参考[4]。所有验证节点i都有一个初始值 bi（bi=0 或 1），协议开始时，每个验证节点都会向其他验证节点发送各自的初始值，

协议第一步（Step 1）是归 0 过程：

第二步（Step 2）为归 1 过程：

第三步（Step 3）为重新设定初始值的过程：

在 Algorand 中， BBA* 的结果是对是否接受某个区块达成共识，共识结果只有接受（0）或拒绝（1）两种情况。

2.4.2 分级共识协议 GC

上述 BBA* 只适用于二元情况，当需要对任意值达成共识，需要引入分级共识协议，将任意值问题转化为二元问题：

Algorand 采用的 GC 分为两步（上图来自 Algorand 白皮书[4]，为了和文中其他部分对应，将两个步骤命名为 Step 2 和 3），协议开始时，每个验证节点i各自都有一个初始值 vi（在 Algorand 中即候选的新区块的哈希）：

第一步 （Step 2），所有验证节点将各自的 vi 发给其他所有验证节点；

第二步（Step 3），对于某个x值，当且仅当节点收到其他验证节点发来该 x 值的总次数（多次收到同一节点发送的x值，只算一次）超过总验证节点数的 ? 时，这个节点会对其它节点发送值 x：

经过 GC，每个节点都会输出一个值对 (vi, gi)，输出规则：

简单来说，分级共识的作用是从多个可能的候选新区块中选择被大多数认可的一个作为最终候选的区块，再通过上面的 BBA* 最终达成共识。

2.4.3 BA*=GC BBA*

改进的拜占庭协议 BA* 结合了上述 GC 和 BBA*，先通过 GC 把任意值问题（从多个区块中选择一个候选）转化为二元问题（接收或拒绝新区块？），再利用 BBA* 达成快速二元拜占庭共识，从而可以快速对任意值达成共识，其共识过程如下[4]：

BA* 的第一步，和第二步，所有验证节点 i 执行 2.4.2 中分级共识 GC，各自得到一个关于新区块的数值对 (vi, gi)，其中 vi 为验证节点 i 认为的候选区块哈希（有可能为空），gi=0 或 1 或 2 。

第三步，所有验证节点根据各自的 (vi, gi) 设定 BBA* 的初始值，如果 gi=2，则设定初始值为 0，如果 gi=0 或 1， 则设定初始值为 1 。之后进行 2.4.1 中的 BBA* 共识过程：

无论哪种情况，BA* 都可以在验证节点中达成共识，从而确定新区块及其包含的交易（有可能为空区块）。

2.5 Algorand 区块链分叉的可能性

Algorand 实际采用的是经典拜占庭共识的升级版 BA*，它和以比特币为代表的中本聪共识的最大区别在于分叉的可能性。后者由于完全去中心化，节点之间无法完全通信，因此可能仅在部分节点间达成共识，容易发生分叉。

Algorand 可以通过设定最大可接受的错误概率 F 调整分叉的概率。在 Algorand 提供的两种实现中，其分叉概率分别为 10^-12 和 10^-18，在现实中分叉仅存在理论上的可能。为给读者一个直观概念，假设 Algorand 每秒生成一个区块，10^-18 的概率意味着从宇宙大爆炸至今的时间内，只有可能发生一次分叉，可见其概率极低。

即使真的发生分叉，Algorand 仍可以从分叉中恢复：

2.6 Algorand 如何保证安全性

上述的共识算法在理想情况下可以实现去中心化环境下较快速的拜占庭共识，数字签名和 VRF 本身的安全性也对系统安全提供了基本的保障。除此之外，Algorand 还引入了以下机制，进一步提升安全性：

种子 Q(r)

Algorand 中的随机性主要靠 VRF 保证，每轮随机的选出 leader 及验证组。一个比较直接的想法是把上一区块 B(r-1) 作为随机函数的输入。但这种方法将给恶意节点带来一定的优势：因为区块和其包含的交易高度相关，恶意节点可以通过调整区块中包含的交易集，获得多个输出，并选择对其最有利的交易集产生新区块，从而提高自己在下一轮中成为 leader 或验证组的概率。

为解决这一问题，Algorand 引入了一个随机的、不断更新的种子参数 Q(r)，Q(r) 与交易集本身相互独立，因此恶意节点无法通过调整交易集而获利。

当区块非空时，Q(r)=H(SIG(Q(r-1),r) （其中，SIG 为 本轮 leader 的签名）

当区块为空时，Q(r)=H(Q(r-1),r)

可以看出，Q(r) 在每一轮都发生变化，且与交易本身无关。可以证明，当 Q(r-1) 是随机的，则 Q(r) 也是随机的。因此恶意节点无法通过改变交易集影响下一个种子的生成。其中，Q(1)的定义没有在相关文献中找到。

回溯系数 k

种子参数降低了恶意节点预测 leader 的可能性，但拥有多个潜在 leader 的恶意节点仍可以有比普通节点更高的概率成为下一个区块的 leader，但这个概率会随着区块的变多而逐渐变小。因此，Algorand 引入了一个回溯系数 k，第 r 轮的候选组只从 r-k 轮已存在的候选组中选取，恶意节点在 r-k 轮能够影响第 r 轮候选组的概率极低。

一次性公钥

上一节中提到，Algorand 从协议层面的分叉仅在理论上可能发生。在实际中，如果恶意节点可以挟持其他节点，仍可以在验证组被公开的瞬间，强制这些节点重新签名新的区块，从而产生短暂的分叉。Algorand 引入了一种一次性公钥的机制，以杜绝这种可能性。

具体原理是所有节点在加入 Algorand 网络时（即发生第一笔交易时），都生成足够多的一次性公钥，并公布。这些公钥将用作后续所有轮次的签名验证，并且每个公钥只使用一次，一旦被使用后就销毁。一次性公钥的生成过程需要一定的时间，在 Algorand 的典型实现中，每个新节点需要约 1 小时来生成未来 10^6 轮的所有公钥（约 180 MB 数据）。虽然这增加了节点加入时的门槛，但可以从根本上杜绝上述分叉攻击：因为一旦签名完成，公钥即被销毁，即使被恶意节点劫持，也无法再次签名产生分叉。

2.7 Algorand 的可扩展性

对于目前大多数去中心化区块链，如比特币，以太坊以及 Qtum 等，可扩展性的主要瓶颈在于所有链上计算都要进行全网验证，而达成全网共识往往需要一定的时间。Algorand 采用 PoS VRF 机制进行随机选择区块生产者和验证者，无论网络中有多少节点，每一轮都只需要在少数节点上进行验证，大大提高了共识速度，提高可扩展性。同时，Algorand 还采用了改进的拜占庭共识 BA*，该协议可以减少共识节点之间的通信量，从而进一步提高共识速度。

此前 Algorand 发布了其性能测试数据，结果表明，在 1000 台 EC2 服务器（AWS 虚拟云服务器）、500,000 用户场景下，Algorand 网络确认时间稳定为 1 分钟，吞吐量约为比特币网络的 125 倍。（比特币约为 7 TPS）且吞吐量不会随着节点数的变多而明显下降[1]。

Algorand 的优缺点

通过上述分析，Algorand 基本解决了第 2 节开头提出的一系列问题：

Algorand 在可扩展性，安全性和去中心化程度三个方面达到了一个很好的均衡，但这不意味着其真的打破了所谓的”不可能三角“。

可扩展性方面：本质上还是通过较少的验证节点对所有交易进行验证，当网络中全节点变多时，只能保证性能不下降太多，不是真正意义上的可扩展。另外，每一轮验证节点之间的通信依赖于所处的网络状态，网络不稳定将导致共识时间变长，影响 TPS。官方称 Algorand 在 Permissinoed 环境下将有更好的性能[4]，原因可能在于 Permissionless 环境下节点所处环境有太多不确定性，会在一定程度上影响可扩展性。

安全性方面：Algorand 本质上采用的还是拜占庭共识，恶意节点不能超过 ?，而比特币可以在恶意节点数小于 ? 的情况下保证安全。

去中心化方面：Algorand 采用 PoS 共识和 VRF 决定区块生产者和验证者，拥有较多代币的节点在 PoS 过程中被选中的概率较高，且 Staking 奖励向大户集中，有一定的中心化趋势；而 VRF 选举机制的引入让链上计算只由部分节点进行验证，损失了去中心化系统全网验证的特性。

此外，Algorand 的主网刚刚发布[6]，此前所有结果均是理想环境下的数据，且部分代码未开源，虚拟机相关设计也暂未提及，其实现的复杂度、稳定性和实际性能还有待时间的检验。

总结

Algorand 通过创新共识协议设计，同时实现了较高的可扩展性，较好的安全性和一定程度的去中心化，并且所有结论都有较为严格的数学证明，是一种较为创新和严谨的共识机制，目前较适用于有一定准入门槛的去中心化、高吞吐量加密数字货币项目。

参考文献

[1]https://algorandcom.cdn.prismic.io/algorandcom/a26acb80-b80c-46ff-a1ab-a8121f74f3a3_p51-gilad.pdf

[2]https://www.algorand.com/what-we-do/technology/core-blockchain-innovation

[3] S. Micali, M. Rabin and S. Vadhan. Verifiable Random Functions. 40th Foundations of Computer Science (FOCS), New York, Oct 1999.

[4]https://algorandcom.cdn.prismic.io/algorandcom/ece77f38-75b3-44de-bc7f-805f0e53a8d9_theoretical.pdf

[5]https://algorandcom.cdn.prismic.io/algorandcom/218ddd09-8d6f-42f7-9db9-5cfbc0aedbe5_algorand_agreement.pdf

[6]https://www.algorand.com/resources/blog/the-borderless-economy-is-here

[7] https://www.odaily.com/post/5134308

[8] https://www.algorand.com/what-we-do/technology/scalability/

[9] https://www.algorand.com/what-we-do/technology/security/

[10]https://www.algorand.com/what-we-do/technology/permissionless-blockchain/