共识技术分析系列一：Algorand 共识算法

1、Algorand共识算法简介

Algorand共识算法的论文的下载地址：https://people.csail.mit.edu/nickolai/papers/gilad-algorand.pdf

Algorand采用了VRF函数，并结合账户的余额比例，随机确定区块生成以及投票人角色。

所谓VRF（Verifiable Random Function）就是可验证随机函数。

随机数对于区块链技术来说很关键。 本质上，分布式账本的核心问题就是随机选择出块人的问题，这个随机性要能被全网确认，并且不能被操控，也不能被预测， 否则恶意节点通过操控这个随机数就可以操控长链，从而实现双花攻击。

PoW的方案是让大家进行算力竞赛，设置一个计算哈希的难题，谁先算出来谁赢，算力高的赢的概率高，算力低的赢的概率低，以这样的方式保证胜出者是随机的。投入的算力能够体现在哈希值上， 这样全网能够验证，并选择包含最多算力的那条链。恶意节点只能通过提升自己的算力来增加攻击成功的概率。

PoS的方案是选举，大家不用浪费电力去进行算力竞赛，而是文明一点，随机选举一个节点来出块，并且被选中的概率和它拥有的份额相关。 如果“随机”这一步没有问题的话，恶意节点只能通过增加自己的份额，增加自己被选中的概率，从而增加双花攻击的成功概率。 这里有一点比PoW的方案要好就是，要实现攻击，先得成为持币大户，如果攻击成功币价大跌，攻击者也会承受最大的损失。

那么接下来的核心问题就是，这个不能被操控不能被预测的随机数从哪来。传统地PoS方案尝试从链上现有的数据入手，比如使用上一个区块的哈希值，上一个区块的时间戳等等来作为随机数的来源，但这些会带来额外的安全风险。 因为区块本身的信息就是节点写进去的，然后又要根据里面的信息来选举后续的出块者，存在循环论证的嫌疑，安全性不会太好。 这也是传统地认为PoS方案不如PoW可靠的部分原因。

Algorand提出的VRF能够由私钥( SK )以及讯息( X )产生一组可验证的伪随机 (pseudorandom) 数Y以及证明 ⍴。任何人都可以透过Verify函数来检验这个随机字串是否真的是该公钥对应私钥持有者，依照规定使用Evaluate函数所产生，而不是自己乱掰的。更详细一点的VRF三个函示描述如下：

•Keygen(r) → (VK, SK). On a random input, the key generation algorithm produces a verification key VK and a secret key SK pair. •Evaluate(SK, X) → (Y, ⍴) . The evaluation algorithm takes as input the secret key SK , a message X and produces a pseudorandom output string Yand a proof ⍴ . •Verify(VK, X, Y, ⍴) → 0/1 . The verification algorithm takes as input the verification key VK , the message X , the output Y, and the proof ⍴ . It outputs 1 if and only if it verifies that Y is the output produced by the evaluation algorithm on inputs SK and X .

为什么我们需要这么一个大家自己产生，却又要可以被验证的随机字串产生器呢？这是因为在Algorand的拜占庭演算法中，虽然也存在着每一轮不同的区块生产者(称为Leader)以及验证委员会(Committee, Verifiers)，但并不是用「公开选举」的方式来选的，而是透过每个使用者自己对奖的方式来看看自己是不是下一轮的Leader。

algorand就是通过随机算法从一群大范围的验证者中选取一部分验证者运行BFT算法(Micali教授实现的BA*算法)，从而达到提高共识的效果。

无论是在何种BFT的共识机制中，都是由Leader以及Committee来完成区块的发布以及共识决议。例如EOS的dPoS BFT是固定21个BP轮流担任Leader以及投票者、Zilliqa透过PoW加入Committee进行PBFT共识算法。这些比较直观的拜占庭共识演算法都有一个共同特征，就是大家都可以看到下一个区块的Leader是谁，以及负责协议共识的Committee是谁。这造成了一个可能的风险，就是这些区块生产者以及Committee成员容易成为DDOS或是贿赂的目标。

Algorand为了解决这种潜在的风险，利用VRF来掩盖Leader Selection的步骤。可以想像成：一般的BFT在每一轮开始时公平公开选出Leader以及Committee，Algorand则是像在每一轮开始时公布中奖号码，每个使用者都可以自己拿自己的票根对奖，中奖的人即可成为下一轮的Leader(或是Committee Verifier)，但在中奖者自己表明身分前，没有人知道谁中奖，也就是没有人能预测下一轮的Leader以及Committee。当然中奖与否并不是口说无凭，中奖者需要出示中奖证明，而这个证明是大家都可以验证的，这正是我们刚刚说到的VRF。

2、Algorand共识算法缺陷

(1)现实环境的随机选择的空间并不大。

VRF是可以提供了公平且不容易收到伪造和攻击的委员会随机选择方式，但是任何随机数的生成必须依赖大的种子集合才可以有作用，在VRF中假设80%节点是诚实的，Committee需要2000个成员才够大，现实情况是不太可能有这么多成员的。

(2)完全没考虑网络延迟情况。

VRF Committee集合选举时依赖数量庞大的主机通讯的，主机之间相互沟通造成的延迟，必然大大拖慢整个系统的处理速度。

(3)没考虑节点的动态加入和退出情况。

Algorand的下一个区块的发布者是从k个区块之前的所有参与者（在k区块之前的某段链上发过交易的节点）里选。于是，恶意节点想影响下个区块的发布者，他得影响k个区块才行，当k很大的时候，这个影响也是微乎其微。于是，Algorand得到了一个无偏向的随机数产生器。不过，这个做法有一个问题——k区块之前的节点，有可能已经不在线了。而对于这一点，虽然Micali做出了解释，但是个人觉得并不符合实际情况。

(4)签名数据庞大，造成存储浪费并影响性能。

Algorand使用VRF来确定提案组与验证组，这个方式充分发挥了VRF的可验证性优势，且后验优势使得Algorand的共识体系更安全。但是，Algorand进入验证阶段，采用的是一种可扩展的拜占庭容错算法，即BA*算法，参与节点通过VRF秘密抽签选出。这一设计使Algorand在验证前必须等待凭证（VRF prove）到来，才能知晓参与节点。而且，由于使用了可扩展的拜占庭容错算法，使得Algorand的验证组规模必须比较大(2000～4000人)，这将导致签名数据异常庞大。根据我们的估算，在平均每组3000个验证节点的规模下，每组的签名数据长达126KB，加上其它信息，通知信息约300K，每块的签名数据可达2000*64*12=1M（共12组，每组3000人，至少2/3达成共识。ed25519签名数据长度是64。），远超一般门限签名几十个字节，严重浪费存储和容量（因每块存储的交易量将被占用，不存储签名又会影响安全），不仅造成存储浪费，而且更影响性能。

(5)无法构建很好的激励机制

在POW中，提案者得到提案权需要预先付出算力成本，若其提案区块有问题（交易双花），则该提案区块在全网其他节点验证必将失败，从而不但没有铸块收益，还付出了算力成本。

Algorand协议并没有设计经济激励机制，Micali教授曾回应”Algorand协议只需要进行平凡的计算，因此不需要激励”。在没有经济激励机制下，高性能带宽和服务器必然不愿意参与（因为它本身要消耗费用），整个网络会遇到网络本身无法解决的困难。

(6)存在潜在的安全问题

网络用户必须连续访问其私钥，以确定其在每一轮中的VRF状态（即验证者、提议者，或者两者都不是）。

一般认为，对于那些将大量资产存储在区块链上的个人，为了防止攻击，他们应该把私钥以冷存储的方式进行保存。而持续的验证（需要经常签名）会需要高频率地动用私钥，从而增加被攻击的风险。这显然将导致网络中很多诚实的个体（出于安全的考虑）会避免参与验证过程，从而造成区块链缺乏活力的问题。

(7)买断问题

在区块链的婴儿期，系统的通证价值通常较低，其市值也是处在相对较低的水平。Token的发行往往要经过私募-->基石-->公募 等逐步分散的过程，因此很长一段时间里币是集中在少数人手里的，因此任何POS共识都面临着EOS类似的中心化的问题。

(8)没有惩罚问题

Algorand所存在的另一个问题是，没有办法识别“离线验证者”并惩罚它们。因此，在没有惩罚措施来防止无效的情况下，没有经济激励就是一个问题，很多人会选择不为共识做贡献，因此离开这个网络。假设网络中只有10%的诚信节点在不断地进行验证，而其余节点是离线的状态，与此同时，恶意的节点选择保持在线，那其就很容易超过在线委员会节点。这使得恶意节点更容易控制共识。

总的来说，Algorand的VRF和加密抽签后验性给出了一个解决“三角悖论”的很好设计思想，但其在验证环节的设计更偏单纯的学术化理想化，导致其对网络流量、有效通讯数据等实际工程落地思考不够，严重影响了公链运行性能、节点网络规模、账本存储容量和去中心化程度。

Algorand 共识算法对区块链行业有帮助吗?

共识算法对区块链行业有重要的帮助作用。共识算法的定义是一种用来确定分布式系统中的一个状态是否正确的算法，用于节点集合中的分布式协议和共识。这是衡量区块链协议中的确定性、透明性、安全性和有效性的重要标准。