比特币验证双花 Algorand共识协议的工作原理及优缺点

概述

1.1 简介

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

1.2 Algorand设计初衷

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

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

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

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

1.3 什么是 Algorand？

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

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

· 可扩展性：Algorand 通过可验证随机函数（VRF）随机选择区块的生产者和验证者。 一旦知道被选中，生产者或验证者只需要广播一条短消息来证明自己的身份。 每次产生新区块需要在网络中交换的消息不会随着用户数量的增加而改变，所以即使用户数量增加，系统仍然可以保持较高的TPS（处理的交易数量）每秒）。 Algorand 的 TPS 是比特币的 125 倍。

安全性：由于前面提到的VRF是用来随机选择生产者和验证者，选择过程是由节点独立完成的，Algorand网络中的攻击者无法提前知道下一个出块者和验证者，从而也无法完成攻击. 具体来说，生产者和验证者的身份只有在确定自己被选中并广播相应的证明信息后才会公开。 消息在网络中的传播。

·去中心化：Algorand每一轮的区块生产者和验证者都是随机选择的，没有加入网络的门槛，因此是完全去中心化的。

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

lgorand 协议细节

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

1. 选择一个区块生产者生成一个新的区块

2. 其他节点对新区块达成共识

重复上述步骤，最终形成一个“不可篡改”的区块链。

整个共识过程虽然简单，但在实际执行中，需要解决几个关键问题：

· 如何选择区块生产者，并保证公平性和不可预测性？

· 如何就新区块达成共识？

· 如何避免分叉？

· 如何提高安全性？

· 如何扩展到更大的用户？

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

Algorand 提出了一种新的共识机制来解决以上五个问题。

2.1 基础知识

在正式介绍 Algorand 共识协议之前，本文假设读者对以下术语的含义有基本的了解：

· 哈希函数

· 公钥/私钥

· 电子签名

· 贸易

· 堵塞

· 账本

· 共识

·拜占庭协议（BA）

· 诚实节点

· 攻击节点

· P2P通信

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

2.2 Algorand的基本流程

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

1. 每轮共识开始时，随机选出潜在的领导者，每人产生一个新区块，对新区块进行签名和广播

2. 随机选择一个验证组来验证组长广播的新区块。 达成共识后，广播确认新区块，进入下一轮

接下来，我们讨论 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 独立验证自己是否是潜在的领导者：

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

其中，H为哈希运算； SIG为签名操作； r 是当前回合； Q(r-1)是第r-1轮的种子（后面2.6节会解释）； SIZE (PK (rk) )是第rk轮中满足要求的所有公钥的个数（为什么是rk？k是回溯系数，2.6节也会解释）； 公式开始。 表示将哈希结果转换为小数位，这样保证结果是[0, 1)的某个值。

节点使用自己的私钥计算上述签名的哈希值是否满足要求，从而知道自己是否属于候选领导者，过程中无需与其他节点交换信息。 由于哈希函数输出的随机性，可以认为满足要求的候选节点是随机选择的。 候选节点然后可以生成新的块并向整个网络提供签名以证明其身份。 如果有多个候选leader，则在后续共识中，上面hash值最小的leader将成为本轮的最终leader。 Leader 生成的区块 Br 包含本轮所有交易和上述证明信息，并由验证组成员协商一致验证。

2.3.2 每轮每阶段随机选择验证组

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

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

其中，s为本轮的不同阶段，Algorand在每一轮的每个阶段都有不同的验证组，进一步保证安全性； n为验证组期望成员数，可手动设置； 其他参数有不同的含义 Repeat。

与候选领导者一样，每个阶段的验证组成员都是随机选择的。 在验证了自己的身份后，验证节点就可以开始参与共识验证过程，并公开自己的签名来证明自己的身份。

2.3.3 引入权益证明（PoS）机制

上述随机选择过程没有考虑 Token 持有者的权重。 恶意节点可能生成大量有效私钥，大概率成为区块生产者和验证者。

Algorand 在其已发布的实施提案中引入了一个称为诚实多数货币 (HMM) 的条件假设。 其基本思想来源于PoS共识机制，即在上述随机选择过程中引入代币持有量（Stake）作为权重。 ，持有量越多的节点被选中的概率越高，代币持有者往往更倾向于保护网络的安全。 具体可以表示为如下公式：

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

其中，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）。 当协议启动时，每个验证节点将其初始值发送给其他验证节点，

协议的第一步（步骤 1）是归零过程：

如果某个验证节点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和Step 3）。 在协议开始时，每个验证节点 i 都有一个初始值 vi（Algorand 中候选新区块的哈希值）：

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

第二步（Step 3），对于某个x值，当且仅当该节点从其他验证节点接收到x值的总次数（多次收到同一个节点发送的x值，统计only once) exceeds the total 当验证节点数的⅔时，本节点将值x发送给其他节点：

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

当接收总数x超过验证节点总数的⅔时，设vi = x, gi = 2；

当接收总数x超过验证节点总数的⅓时，设vi=x，gi=1；

· 否则，设置 vi = null 和 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* 都可以在验证者之间达成共识，以确定新区块及其包含的交易（可能是空区块）。

2.5 Algorand区块链分叉的可能性

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

Algorand可以通过设置最大可接受错误概率F来调整分叉概率。在Algorand提供的两种实现中，分叉概率分别为10^-12和10^-18。 实际上，fork 只在理论上是可能的。 给读者一个直观的想法，假设Algorand每秒产生一个区块，10^-18的概率意味着从Big Bang到现在的时间里只能出现一次分叉，可见概率极低。

即使确实发生分叉，Algorand 仍然可以从分叉中恢复：

· Algorand遵守中本聪共识中的最长链规则

· 如果有多个最长链，选择包含非空块的最长链

· 如果还是一样，可以根据区块哈希值排序选择

2.6 Algorand 如何保证安全

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

种子Q(r)

Algorand 中的随机性主要由 VRF 保证，leader 和 verification group 是每一轮随机选择的。 一个更直接的想法是使用前一个块 B(r-1) 作为随机函数的输入。 但是，这种方法会给恶意节点带来一定的优势：由于区块与其中包含的交易高度相关，恶意节点可以通过调整区块中包含的交易集来获得多个输出，并选择最有利的一个给它。 交易集产生一个新的区块，从而增加成为下一轮领导者或验证组的概率。

为了解决这个问题，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

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

一次性公钥

正如上一节所述，Algorand 从协议层面的分叉只是理论上可能的。 在实践中，如果恶意节点可以劫持其他节点，他们仍然可以在验证组公开的那一刻迫使这些节点重新签署新的区块，从而产生短分叉。 Algorand 引入了一次性公钥机制来消除这种可能性。

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

2.7 Algorand 的可扩展性

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

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

Algorand 的优点和缺点

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

· 通过 PoS 和可验证随机函数 (VRF) 选择区块生产者和验证者

通过改进的拜占庭共识BA*对新生成的区块达成共识

通过一定的参数设计，从数学上将分叉的概率降到极低的值

引入种子参数、回溯系数、一次性公钥等机制，进一步增强安全性

· 每轮只进行部分验证，通过减少节点间的通信，进一步提高系统的吞吐量，提高可扩展性

Algorand 在可扩展性、安全性和去中心化方面取得了很好的平衡，但这并不意味着它真的打破了所谓的“不可能三角”。

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

安全方面：Algorand本质上采用拜占庭共识，恶意节点数不能超过⅓，而比特币在恶意节点数小于½时可以保证安全。

在去中心化方面：Algorand 使用 PoS 共识和 VRF 来确定区块生产者和验证者。 代币多的节点在 PoS 过程中被选中的概率更高，staking 奖励集中给大玩家比特币验证双花，具有一定的中心化性 VRF 选举机制的引入使得链上的计算只经过部分节点验证，失去了去中心化系统全网验证的特性。

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

总结

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