共识机制一直是区块链领域最重要的议题之一，从比特币的PoW开始，不断的有人在改进现有的共识机制，目标无非是为了让区块链效能继续优化，并且在速度、安全性以及去中心化三者之间达成平衡。
其中PoS(Proof of Stake)并不是一个新的观念，其核心思想就是利用持有货币的数量而非运算资源来分配使用者在区块链上的权力，持有货币越多者越有机会生产区块。但实际实作的方法中也存在诸多挑战，例如如何公正选出委员会(Committee)或是下一个区块产生者(Leader)等等。比较有名的PoS模型有Snow White(NXT)、Ouroboros Praos(Cardano)、还有Algorand等等，今天就来介绍一下相对较新的Algorand演算法。
Algorand: A Pure PoS Consensus Protocol
提出Algorand演算法的是一位图灵奖的得主Silvio Micali，可以在网路上许多他介绍Algorand的影片中发现，他十分坚持相较于其他现有的实践方法，Algorand实现的PoS是真正公平的Pure Proof of Stake。因为在他的设计中，货币的持有者不需要把某数量的货币抵押出去(会有一段时间不能使用)，或是代理(delegate)给其他人来参与PoS共识机制，而是只要自己钱包里面拥有balance就可以一同参与这个共识机制。
除了这个看似能防止中心化的设计之外，Algorand真正创新的突破在于结合VRF( Verifiable Random Function )的Leader以及Committee抽签( cryptographic sortition )、防止重要节点遭到恶意使用者攻击的Participant Replacement机制、以及他们快速在Committee中形成共识的拜占庭共识演算法BA*，以下就来一一介绍。
Verifiable Random Function(VRF)
在Algorand中最重要的一个机制就是引入了VRF — Verifiable Random Function，中文是可验证随机函数。简单的说，VRF能够由私钥( SK )以及讯息( X )产生一组可验证的伪随机 (pseudorandom) 乱数Y以及证明⍴。任何人都可以透过Verify函数来检验这个随机字串是否真的是该公钥对应私钥持有者，依照规定使用Evaluate函数所产生，而不是自己乱掰的。更详细一点的VRF三个函示描述如下(from this post )：
· 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 Y and 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。他们称之为C ryptographic Sortition，这背后的逻辑便是仰赖VRF的原理。
C ryptographic Sortition
无论是在何种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。
在每一个新区块要产生前，每一个使用者都可以透过Sortition()函示，由自己的私钥配合新一轮的开奖讯息(上述的X)，一起通过VRF中的Evaluate()函示输出一组伪随机字串，若刚好幸运符合某些规定，则有资格成为Leader或是委员会的成员(机率与持有货币成正比)。若发现自己是Leader，该使用者就会准备好要发布的区块，附上自己确实中奖的Proof一起广播出去。同理，后面会提到的共识过程中，每一个需要Committee决议投票的步骤开始前，每一个节点也都先对奖看看自己是否幸运被抽中进入委员会，是的话就把自己的投票(或是其他要协议的值)随着Proof一起广播出去。
Sortition()函示，其中return的π为proof，j为weight，即一个使用者可能被选中多次 (想像一共要随机选出1000人的committee,而一位用者拥有全网20%的货币，那他当然应该被选中很多次，因此该使用者在Committee中将会有较高的权重)
细心的你可能会注意到，这种自己在家对奖的模式让很多人同时成为Leader呢？答案是会的，可能会有多个节点都符合条件成为Leader，但最后大家可以规定简单的经过hash来排序，决定出Prioroty最高的那个leader，并只帮忙广播它的区块。
Participant Replacement
上述的设计对安全性有很大的帮助，由于没有人能预测参与下一轮共识的成员，所以恶意节点无法事前锁定要攻击的对象。当一个恶意节点知道某人是这一轮的Leader时，代表这个讯息已经散布到网路之中，该Leader想要广播的区块已经让网路上的其他节点知道，因此已经可以「功臣身退」 ，现在才要攻击它一切都太晚了。同理，在后面所有的共识过程中，在每一个成员广播出自己决议的同时，投出那一票的瞬间，他们就已经达成了自己此步骤身为委员会成员的义务，而下一个步骤中，又会有新的委员会出现，生生不息的继续完成每一轮的共识。
这就是所谓的Participant Replacement，每一个共识步骤(每个round的每个step)的决议成员都不同且彼此独立，使得恶意使用者无法有效率的攻击这个网路。
小结一下VRF部分，Algorand在每一个区块leader的产生到共识的每一个决议步骤，都不是事先选择好，而是当下发现自己有权利参与的节点，在参与共识的同时附上Proof来广播。这不同于一些BFT模型是节点广播区块之后等待某些已知使用者回复签章，而是Locally收集网路上的各种签章投票，在帮助gossiping的同时自己运行自己的共识演算法。接着，我们就来看看核心的共识是如何达成的。
BA – Byzantine Agreement
BA*
下图是整个BA Procedure的pseudocode。Algorand所使用的BA演算法一共分为两个阶段，在第一个阶段称为Reduction，一共会经历两个步骤(steps)，把共识问题简化为二选一选择题：同意一个Block Hash或是Empty Block Hash。第二个阶段则是输出共识的结果，可能是一个Block Hash代表大家同意该区块，也有可能是Empty Block。
BA*还会Output这个共识结果属于Final或是Tentative，Final代表BA确定与足够多人达成共识，该区块不可能被反驳或是为Fork；而Tentative代表可能因为Partition或是网路异步，有其他节点们对另一个Block达成Tentative Consensus。
以下我们就来分层组装这个BA里面的运作模式。
Voting
从最简单的voting开始。以下的pseudocode描述了在每一轮(round)的每一个步骤(step)，一个使用者都要使用刚刚介绍得Sortition()函示来检验自己是否有权(以及多少权重)参与共识的投票。
如果j>0 表示自己有权参与此步骤的共识协议，因此会把自己同意的value透过Gossiping的方式广播出去。
Counting Votes
这里的T与τ分别为两个参数，T代表了该步骤需要多少比例的委员投票，τ则表示该步骤所选出的委员数量。所以T × τ 就是某个值要在这个步骤达成共识所需的总投票数。一旦有某个值value所得票数超过T × τ，CountVotes就会回传该value。
Reduction
如上面所说，Reduction()是BA*的第一阶段，透过两个步骤将共识问题简化到要嘛选hblock，要嘛选empty_hash的二选一选择题。
第一个步骤中，这个Committee member会投票自己原先支持的hblock，并且等着接收其他成员的投票，看看是否有某个block hash的得票数超过threshold( T · τ )。有的话就在第二步中投票给该hash，若是没有收到任何hash超过threshold，则投给empty_hash。
Binary BA
接着我们来看BA*的第二阶段，也就是BinaryBA。这个函示会回传一个Consensus，也就是一个新区块的共识结果。由于上一步中Reduction()已经确保了最多只会有一个不为empty_hash的famous block hash，接着就只要在这个最有名的block_hash与empty_hash之间做出选择。大致的逻辑跟前面类似，投票之后便透过CountVotes()来等待该步骤的投票结果。
可以看到程序中在自己达成consensus之后，会继续广播往后三个step对该值(r)的投票讯息 (看到step < s < step+3的回圈)。这是为了让其他可能处于不同step的诚实节点，也能收到我对于这个block_hash或empty_hash的投票。否则若是大家异步，很有可能一部分的诚实节点在step 1收集到足够的投票达成共识，但是剩余的节点在step1没有成功收集票数，而已经进行到step2或之后，因此一直无法收集足够的票数。
Strong Synchrony & Weak Synchrony
而在Weak Synchrony的情况下，可能发生不同诚实节点取得不同Consensus的情况。例如一个节点A在step1就收集了block_hash足够的投票，但其他所有诚实节点都没有收集到足够的票数，因此进行到下一个step并且再次TIMEOUT，所以大家都改投empty_string，因此其他节点在比较后面的步骤中对empty_string达成共识。
这种事情是一般BFT中不常见的，因为通常不会容许一个节点对两个不同的value签名。但由于Algorand的投票是有阶段性的，一个节点可能在不同的阶段发出不同的投票，因此会发生这种看似荒谬的事件。在这种情况下，所有节点都是诚实的但却没有达到完全一致的协议，所以Algorand才需要设计FINAL以及TENTATIVE来描述一个consensus的状态。
若是在Strong Synchrony的情况下，大部分的使用者会在step 1就达成共识，投票给相同的block_hash，这时他们会再进行标记为FINAL的Committee Vote，其他节点若是在BA*最后阶段收到足够多的Final Vote，就会标记这次达成决议的区块为FINAL，即可以保证其Finality。
反之在刚刚介绍的Weak Synchrony中，由于只有少数人-节点A在第一轮达成共识，进行CommitteeVote(FINAL, block_hash)，最终BA*无法收集足够的Final votes，因此会标记该block为TENTATIVE。Tentative翻成中文就是暂时、犹豫的，也就是告诉我们对于该区块的Finality无法保证，我们必须等到网路回复正常(Strong Synchrony)，并看到这个block之后出现下一个FINAL Block时，才能确保一切不可能被回溯。
这全部合起来就是Algorand的BA共识演算法，对每个区块的共识，会在这个区块在网路中广播的同时就一边进行。除了这个快速的共识演算法外，Algorand也设计了从Partition中恢复的Recovery机制，使的节点明显确定网路Partition发生时，可以直接进入Recovery模式等待网路复原，再一起重新同步。不必像个傻B一样一直做白工。
Committee Size
在Algorand的设计当中每次投票的过程都由不同的Committee负责，很明显的，要求Committee越庞大代表了越公平、安全，却势必会提高沟通造成的延迟。Algorand在他们的实作中选择把出事机率控制在5*10^-9 以下，由下图中可以看到，假设80%节点是诚实的，Committee需要2000个成员才够大。
Implementation and Evaluation
最后附上原Paper中实作的结果与评估。
由于整个演算法中不同步骤的安全性或效能接不相同，因此Algorand对于T, τ这两个参数会因是在普通阶段(step)或是FINAL有所不同。下图为Algorand实现自己的演算法时所用的参数，都是相对保守的参数。
最后附上一些实验结果。此为一个VM上运行50个节点(运行100 ~ 1000个VM)进行Algorand共识的实验结果，可以发现几乎是维持在Constant。
另一个有趣的实验结果是不同比例的恶意节点对共识速度造成的影响。可以看出在预设的比例之下，其运行效能不太受到影响。
后记
大概是这样，写这篇文章的宗旨是自己虽然口口声声说PoS很棒，但是对它的运作细节还是很不熟悉的，刚好因为最近读DEXON又看到Algorand这个关键字，才下定决心好好认真深入一点。
个人认为Algorand最有趣的部分应该在这篇文章的前半段VRF与Participant Replacement，看到这些聪明的密码学应用确实很有启发性，希望我未来也可以有时间比较深入了解其他PoS共识机制，真的是很酷很有趣但又真的很难懂阿！
