Algorand共识算法

共识机制一直是区块链领域最重要的之一，从比特币的PoW开始，不断的有人在改进现有的共识机制，目标无非是为了让区块链效率继续优化，并且在速度，安全性以及去中心化三者之间达成平衡。

其中PoS（权益证明）并不是一个新的观念，其核心思想就是利用持有的货币的数量而非运算资源来分配用户在区块链上的权力，持有货币越多者越有机会生产区块链。但实际实作的方法中也存在挑战，例如如何合理选择出委员会（委员会）或者下一个区块链产生者（Leader）等等。比较有名的PoS模型有白雪公主（NXT），Ouroboros Praos（Cardano），还有Algorand等，今天就来介绍一下相对较新的Algorand算法。

Algorand：纯粹的PoS共识协议

提出Algorand算法的是一位图灵奖的得主Silvio Micali，可以在网络上很多他介绍Algorand的影片中发现，他十分坚持相较于其他现有的实践方法，Algorand实现的PoS是真正公平的纯桩号证明因为在他的设计中，货币的持有者不需要把某数量的货币抵押出去（会有一段时间不能使用），或是代理（委托）给其他人来参与销售点共识机制，而。是只要自己的钱包里面拥有余额就可以一起参与这个共识机制。

除了这个看似能防止中心化的设计之外，Algorand真正创新的突破在于结合VRF（可验证随机函数）的领导者和委员会抽签（密码分类），防止重要的攻击被滥用者的参与者替换机制，以及他们快速在Committee中形成共识的拜占庭共识算法BA *，以下就来一一介绍。

可验证的随机函数（VRF）

在Algorand中最重要的一个机制就是约会了VRF —可验证随机函数。简单的说，VRF能够由私钥（SK）以及消息（X）产生一个可验证的伪随机（ pseudorandom）乱数Y以及证明⍴。任何人都可以透过验证函数来检验这个随机字串是否真的是该公钥对应私钥持有者，按照规定使用评估函数所产生，而不是自己乱掰的。更详细一点的VRF三个函示描述如下（从这篇文章）：

Keygen（r）→（VK，SK）。在随机输入上，密钥生成算法生成验证密钥VK和秘密密钥SK对。
求值（SK，X）→（Y，⍴）。评估算法将密钥SK和消息X作为输入，并产生伪随机输出字符串Y和证明⍴。
验证（VK，X，Y，⍴）→0/1。验证算法将验证密钥VK，消息X，输出Y和证明as作为输入。当且仅当它验证Y是评估算法在输入SK和X上产生的输出时，才输出1 。

为什么是我们需要这么一个大家自己产生，却又要可以被验证的随机字串产生器呢？这是因为在Algorand的拜占庭算法中，虽然也存在着每一轮不同的区块链生产者（称为Leader ）以及验证委员会（委员会，验证者），但并非用“公开选举”的方式来选的，而是通过每个使用者自己对奖的方式来看看自己是不是下一轮的Leader。他们称之为C 密码学分类，这背后的逻辑便是仰赖VRF的原理。

Ç ryptographic抽签

例如EOS的dPoS BFT是固定的21个BP轮流担任领导者以及投票者，Zilliqa通过PoW加入委员会进行的，都是由领导人以及委员会来完成的。 PBFT共识算法。这些比较直观的拜占庭共识算法都有一个共同特征，就是大家都可以看到下一个区块链的领导人是谁，以及负责协议共识的委员会是谁。这造成了一个可能的风险，就是这些区块链生产者以及委员会成员容易成为DDOS或贿赂的目标。

可以想像成：一般的BFT在每一轮开始时公平公开选拔出领导人以及委员会，Algorand则是像在每一轮开始时公布中奖号码，每个使用者都可以自己拿自己的票根对奖，中奖的人即可成为下一轮的Leader（或Committee Verifier），但在中奖者自己表明身分前，没有人知道谁中奖，也就是没有人当然中奖与否并非口说无凭，中奖者需要出示中奖证明，而这个证明是大家都可以验证的，这正是我们刚刚说到的VRF。

在每一个新区块链要产生前，每一个使用者都可以透过Sortition（）函示，由自己的私钥配合新一轮的开奖讯息（上述的X），一起通过VRF中的Evaluate（）函示输出一组伪随机字串，若刚好幸运符合某些规定，则有资格成为领导人或委员会的成员（机率与持有货币成正比）。若发现自己是领导人，该使用者就会准备好要发布的区块链，附上自己确实中奖的证明一起广播出去。同理，后面会提到的共识过程中，每一个需要委员会决议投票的步骤开始前，每一个议员也都先对奖看看自己是否幸运被抽中进入委员会，是的话就把自己的投票（或者其他要协议的值）转换为证明一起广播出去。

Sortition（）函授，其中返回的π为证明，j为重量，即一个使用者可能被称为重复（想像一共要随机选出1000人的委员会，而一位用者拥有全网20％的货币，那他当然应该被很多很多，因此该使用者在Committee中将会有更高的权重）

细心的你可能会注意到，这种自己在家对奖的模式让很多人同时成为Leader呢？答案是会的，可能会有多个副作用都符合条件成为Leader，但最后大家可以规定简单的经历hash来排序，决定出Prioroty最高的那个领导，并只帮忙广播它的区块链。

参加者替换

上述的设计对安全性有很大的帮助，由于没有人能预测参与下一轮共识的成员，所以恶意二进制无法事前锁定要攻击的对象。当一个恶意恶意知道某人是这一轮的Leader时，代表这个讯息已经散布到网络之中，该领导者想要广播的区块已经让网络上的其他路由器知道，因此已经可以「功臣身退」，现在才要攻击它一切都太晚了。同理，在后面所有的共识过程中，在每一个成员广播出自己的决议的同时，投出那一票的瞬间，他们就已经达成了自己此步骤身为委员会成员的义务，而下一个步骤中，又会有新的委员会出现，生生不息的继续完成每个轮的共识。

这就是所谓的参与者替换，每一个共识步骤（每个圆的每个步骤）的决议成员都不同且彼此独立，从而恶意使用者无法获得效率的攻击这个网络。

小结一下VRF部分，Algorand在每一个区块头的产生到共识的每一个决议步骤，都不是预先选择好的，而是当下下发现自己有权利参与的例程，在参与共识的同时附上Proof来广播。这是一些BFT模型是异步广播区块链之后等待的某些已知用户回复签名，而是本地收集网络上的各种签名投票，在帮助gossiping的同时自己运行自己的共识算法。然后，我们就来看看核心的共识是如何达成的。

BA-拜占庭协议

BA *

下图是整个BA程序的伪代码。Algorand所使用的BA算法一共分为两个阶段，在第一个阶段称为还原，一共会经历两个步骤（步骤），把共识问题简化为二选一选择题：同意一个Block Hash或Empty Block Hash。第二个阶段则是输出共识的结果，可能是一个Block Hash代表大家同意该区块链，也有可能是Empty Block。

BA *即将输出这个共识结果属于Final或Tentative，Final代表BA确定与足够多人达成共识，该区块链无法被反驳或是为Fork；而Tentative代表可能因为Partition或者网络异步，有其他总统们对另一个阻止达成暂时性共识。

以下我们就来分层组装这个BA里面的运作模式。

表决

从最简单的投票开始。以下的伪代码描述了在每个轮（round）的每一个步骤（步骤），一个用户都要使用刚刚介绍过得Sortition（）函示来检验自己是否有权（以及多少权重）参与共识的投票。

如果j> 0表示自己有权参与此步骤的共识协议，因此会把自己同意的值透过Gossiping的方式广播出去。

点票

这里的T与τ分别为两个参数，T代表了该步骤需要多少比例的委员投票，τ则表示该步骤替换出的委员数量。所以T×τ就是某个值要在这个步骤达成共识所需的总投票数。一旦有某个值值获得票数超过T×τ，CountVotes就回传该值。

减少

如上面所说，Reduction（）是BA *的第一阶段，通过两个步骤将共识问题简化到要嘛选hblock，要嘛选empty_hash的二选一选择题。

第一个步骤中，这个委员会成员会投票自己原先支持的hblock，并且等着接收其他成员的投票，看看是否有某人hash的得票数超过阈值（T·τ）。有的话就在第二步中投票给该哈希，如果是没有收到任何哈希超过阈值，则投给empty_hash。

二进制BA

接着我们来看BA *的第二阶段，也就是BinaryBA。这个函示会回传一个Consensus，也就是一个新区块链的共识结果。由于上一步中Reduction（）已经确保了最多只有一个没有empty_hash的著名区块哈希，然后就只要在这个最有名的block_hash与empty_hash之间进行选择。大致的逻辑跟前面类似，投票之后便穿过CountVotes（）来等待该步骤的投票结果。

可以看到程序中在自己达成共识之后，会继续广播往后三个步骤该值（r）的投票消息（看到step <s <step + 3的回圈）。这是为了让其他可能处于不同步骤的诚实节点，也能收到我对于这个block_hash或empty_hash的投票。否则若是大家异步，很有可能一部分的诚实节点在步骤1收集到足够的投票达成共识，但是剩余的节点在步骤1没有成功收集票数，而已经进行到step2或之后，因此一直无法收集足够的票数。

强同步和弱同步

而在弱同步中，情况下，可能发生不同诚实的投票获得不同共识的情况。例如，一个路由器A在step1就收集了block_hash足够的投票，但其他所有诚实竞争都没有收集到足够的票数，因此进行到下一个步骤和再次TIMEOUT，所以大家都改投empty_string，因此其他路由器在比较后面的步骤中对empty_string实现共识。

这种事情是一般BFT中不常见的，因为通常不会允许一个有人对两个不同的值签名。但由于Algorand的投票是有阶段性的，一个通常可能在不同的阶段发出不同的投票，因此在这种情况下，所有例程都是诚实的而没有达到完全一致的协议，所以Algorand才需要设计FINAL以及TENTATIVE来描述一个共识的状态。

若是在严格同步的情况下，大部分的使用者会在步骤1就达成共识，投票给相同的block_hash，这时他们会再进行标记为FINAL的委员会投票，其他则若是在BA *最后阶段收到足够多的最终投票，就会标记这次达成决议的区块链为FINAL，即可以保证其最终性。

反之在刚刚介绍的弱同步中，由于只有少数人-议员A在第一轮达成共识，进行委员会投票（FINAL，block_hash），最终BA *无法收集足够的最终票，因此会标记该block为TENTATIVE。翻成中文就是暂时，犹豫的，也就是告诉我们关于该区块链的Finality无法保证，我们必须等到网络回复正常（Strong Synchrony），并看到这个block之后出现下一个FINAL Block时，才能确保一切不可能被回溯。

这全部合起来就是Algorand的BA共识算法，对每个区块链的共识，会在这个区块链在网络中广播的同时就一边进行。除了这个快速的共识算法外，Algorand也设计了从分区中恢复的恢复机制，使的明显确定网络分区发生时，可以直接进入恢复模式等待网络恢复，再一起重新同步。不必像个傻B一样一直做白工。