基于Algorand结合VRF的共识机制介绍

相信大家对于PoS权益证明的概念都不陌生，但是究竟一个PoS的Protocol是如运作的？如何公平的选出下个区块的生产者？如何保证区块生产者不能bias下次自己再次当选的机率？这些实行的细节都是需要经过更多特别设计的。今天就来简单介绍一下Algorand这个相对新的共识算法。

提出Algorand算法的是一位图灵奖的得主Silvio Micali，若是以一个投资者的角度来看，这个项目背后的学术实力是绝对不容质疑的。Silvio称Algorand为Pure Proof of Stake。因为在他的设计中，货币的持有者不需要把某数量的货币抵押出去（会有一段时间不能使用），或是代理（delegate）给其他人来参与PoS共识机制，而是只要自己钱包里面拥有balance就可以一同参与这个共识机制。这确实比较符合去中心化的理念，毕竟降低了参与共识的门坎。

个人认为Algorand真正创新的突破在于结合VRF（Verifiable Random Function）的Leader以及Committee抽签（cryptographic sorTITIon）、防止重要节点遭到恶意使用者攻击的ParTIcipant Replacement机制，以下就针对VRF做一些基本介绍，至于Algorand改良的拜占庭算法BA*。

Verifiable Random FuncTIon（VRF）

Verifiable Random Function，中文是可验证随机函数。简单的说，VRF能够由私钥（SK）以及信息（X）产生一组可验证的伪随机（pseudorandom）随机数Y以及证明Ρ。任何人都可以通过Verify（）函数来检验这个随机字串是否真的是该公钥对应私钥持有者，依照规定使用Evaluate（）函数所产生，而不是自己乱掰的：

· Evaluate（SK，X）→（Y，⍴）。产生随机数：输入私钥SK，信息X，输出pseudorandom output string Y以及proof⍴。

· Verify（VK，X，Y，⍴）→0/1.验证随机数：输入公钥VK，信息X，随机数Y，以及the proof⍴。若该随机数确实是由该公钥对应之私钥使用Evaluate函示所产生，则回传1（true）

为什么我们需要这个VRF呢？一起看下去吧

Cryptographic Sortition

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

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

在每一轮每一个步骤（step）开始前，每一个使用者都可以通过Sortition（）函示，由自己的私钥配合VRF来检验自己有没有资格成为Leader或是委员会的成员（看VRF的evaluate（）函示output是否符合某些规定，机率与持有货币成正比）。若发现自己是Leader，该使用者就会准备好要发布的区块，附上自己确实中奖的Proof一起广播出去。同理，在接下来每一个需要Committee决议投票的步骤中，每一个使用者都先检验自己是否成功被抽中进入委员会，是的话就把自己的投票（或是其他要协议的值）随着Proof一起广播出去。

Participant Replacement

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

这就是所谓的Participant Replacement，每一个共识步骤的决议成员都不同且彼此独立，使得恶意使用者无法有效率的攻击这个网络。

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

总结一下，Algorand在每一个区块leader的产生到共识的每一个决议步骤，都不是事先选择好，而是当下发现自己有权利参与的节点，在参与共识的同时附上Proof来广播。这不同于一些BFT模型是节点广播区块之后等待某些已知使用者回复签章，而是Locally收集网络上的各种签章投票，在帮助gossiping的同时自己运行自己的共识算法。

小结

Algorand算法的出现造成了一阵不小的轰动（单然还有BA*也是重点），透过VRF来进行去中心化世界中随机数生产的概念也被越来越区块链应用。这里仅仅简单介绍了一下VRF以及他在共识协议中可以带来的改变。