Algofans | Algorand爱好者

深度解析Algorand共识协议(下)

云上春野云上春野 2019-08-21 39 次 收藏0

 

 

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* 都可以在验证节点中达成共识,从而确定新区块及其包含的交易(有可能为空区块)。

 

2.5 Algorand 区块链分叉的可能性

 

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

 

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

 

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

 

  • 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 节开头提出的一系列问题:

 

  • 通过 PoS 和可验证随机函数(VRF)实现区块生产者和验证者的选择
  • 通过改进的拜占庭共识 BA* 对新产生的区块达成共识
  • 通过一定的参数设计,从数学上将分叉的概率降至极低值
  • 引入种子参数,回溯系数以及一次性公钥等机制进一步增强安全性
  • 每一轮都只进行局部验证,并通过减少节点间通信量进一步提升系统的吞吐量,提高可扩展性

 

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

 

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

 

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

 

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

 

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

 

总结

 

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

 

Algofans是由Algorand技术爱好者自发建立的技术和生态交流社群,Algofans立足于建立最好的Algorand中文技术社区,持续推广和普及Algorand技术与知识,帮助Algorand释放技术潜力。如果您和我们一样,相信Algorand技术实力、Algo以及无边界经济的潜在价值,请扫码加入Algofans社区!

 

本文系作者个人观点,转载请注明出处!
喜欢 0
支付宝扫码打赏
微信打赏

相关文章

更多