详解 Algorand 共识协议的工作原理及优缺点

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 过程：

• 如果某验证节点 i 收到 0 的总数超过总验证节点数的 ⅔ ，输出共识结果为 0，共识结束，不再执行后面所有步骤
• 如果某验证节点 i 收到 1 的总数超过总验证节点数的 ⅔，则该验证节点把自己的 bi 设为 1
• 如果收到的 0 或 1 都没超过 ⅔， 则验证节点把自己的 bi 设为 0
• 第一步结束节点再次向其他节点发送各自的 bi

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

• 如果某验证节点 i 收到 1 的总数超过总验证节点数的 ⅔ ，输出共识结果为 1，共识结束，不再执行后面所有步骤
• 如果某验证节点 i 收到 0 的总数超过总验证节点数的 ⅔，则该验证节点把自己的 bi 设为 0
• 如果收到的 0 或 1 都没超过 ⅔， 则验证节点把自己的 bi 设为 1
• 第二步结束节点再次向其他节点发送各自的 bi

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

• 如果某验证节点 i 收到 0 的总数超过总验证节点数的 ⅔，设定 bi = 0
• 如果某验证节点 i 收到 1 的总数超过总验证节点数的 ⅔，设定 bi = 1
• 如果收到的 0 或 1 都没超过 ⅔，则每个验证节点会对某个和本轮本阶段相关的信息进行签名，并对签名求哈希。bi 被设置为这些哈希值中最小哈希的最低有效位（仍然是 0 或 1）
• 之后返回第一步，直到达成共识

在 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)，输出规则：

• 当收到 x 的总次数超过总验证节点数的 ⅔ 时，设定 vi = x， gi = 2；
• 当收到 x 的总次数超过总验证节点数的 ⅓ 时，设定 vi = x， gi = 1；
• 否则，设定 vi = 空， gi = 0；

简单来说，分级共识的作用是从多个可能的候选新区块中选择被大多数认可的一个作为最终候选的区块，再通过上面的 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* 共识过程：

• 若共识结果为 0，则最终输出结果为 vi （非空新区块）
• 若共识结果为 1， 则最终输出结果为空（即新区块为空）

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