售前客服二维码
文章均源于网络收集编辑侵删
提示:仅接受技术开发咨询!
Algorand算法是图灵奖得主Si高仿lvio Micali。在互联网上的许多电影中都可以找到他介绍的Algorand。他坚持认为,与其他现有做法相比,Algorand实施的PoS确实是公平的。纯粹的股权证明。因为在他的设计中,货币持有人不需要抵押一定数量的资金(暂时不会使用),或委托其他人参与PoS共识机制,但只要他们自己钱包里面有一个平衡,你可以参与这个共识机制。
除了这种似乎阻止集中化的设计之外,Algorand真正的创新突破是VRF(可验证随机功能)领导者和委员会加密分类,参与者替换机制的组合,以防止重要节点被恶意用户攻击。并且将逐一介绍在委员会中迅速形成共识的拜占庭共识算法BA *。
可验证的随机函数(VRF)
Algorand最重要的机制之一是引入VRF - 可验证随机函数,这是一个可验证的随机函数。简而言之,VRF可以生成一组可验证的伪随机混沌Y和来自私钥(SK)和消息(X)的证明。任何人都可以使用Verify函数来检查随机字符串是否实际上是公钥的私钥持有者,并使用指定的Evaluate函数,而不是混乱。三个VRF功能的更详细描述如下(从这篇文章):
·Keygen(r)→(VK,SK)。在随机输入上,密钥生成算法产生验证密钥VK和密钥SK对。
·评估(SK,X)→(Y,⍴)。评估算法将秘密密钥SK,消息X作为输入,并产生伪随机输出字符串Y和证明⍴。
·验证(VK,X,Y,⍴)→0/1。验证算法将验证密钥VK,消息X,输出Y和证明takes作为输入。当且仅当它验证Y是评估算法在输入SK和X上产生的输出时,它才输出1.
为什么我们需要这样一个随机的字符串生成器,我们都自己生成但可以验证?这是因为在Algonand的拜占庭算法中,尽管存在不同轮组的不同区块生成者(称为领导者)和验证委员会(委员会,核查员),但它们并未被“公共选举”选中。但是通过每个用户自己的奖励方式来看看他们是否是下一轮的领导者。他们称之为加密排序,其背后的逻辑是依靠VRF的原则。
C ryptographic Sortition
无论BFT共识机制如何,领导和委员会都会完成议案的发布和协商一致的决议。例如,EOS的dPoS BFT是固定的PBFT一致性算法,其中21个BP依次作为领导者和选民,Zilliqa通过PoW加入Comte。这些更直观的拜占庭共识算法的一个共同特点是,每个人都可以看到下一个区块的领导者是谁以及谁负责协议。这可能会使这些区块生产者和委员会成员容易遭受DDOS或贿赂。
为了解决这一潜在风险,Algorand使用VRF来掩盖领导者选择的步骤。可以想象,一般的BFT将在每轮开始时公开选择领导者和委员会。 Algorand将在每轮开始时公布获胜号码。每个用户都可以自己购买奖品并赢得奖品。这个人可以成为下一轮领导者(或委员会审核员),但没有人知道谁在获胜者出现之前赢得了奖项,也就是说,没有人可以预测下一轮的领导者和委员会。当然,获胜者不是口号。获胜者需要出示获奖证书,并且每个人都可以验证此证明。这正是我们刚刚提到的VRF。
在创建每个新块之前,每个用户可以使用Sortition()函数将新一轮的彩票消息(上面的X)与其私钥相匹配,并传递VRF中的Evaluate()字母。输出一组伪随机字符串,如果您足够幸运,符合某些规则,您就有资格成为领导者或委员会成员(概率与持有的货币成比例)。如果你发现自己是领导者,那么用户将准备好发布该块,并用Proof进行广播,他真的赢了。同样,在后面提到的共识过程中,在需要委员会决议投票的每个步骤之前,每个节点将首先检查奖品,看看他们是否幸运被吸引到委员会。如果是这样,他们将为自己投票。或者与证明一起广播的其他价值观。
Sortition()函数,其中返回的π是证明,j是权重,也就是说,可以多次选择用户(想象总共随机选择1000个人的提交,一个用户拥有整个网络的20%),当然,他应该被选中多次,所以用户在委员会中的权重会更高)
小心,你可能会注意到这种自我奖励模式让很多人同时成为领导者?答案是肯定的,可能有多个节点有资格成为Leader,但最后您可以指定一个简单的哈希进行排序,确定最高优先级的领导者,并且只帮助广播其块。
BA - 拜占庭协议
BA *
下图是整个BA程序的伪代码。 Algorand使用的BA算法分为两个阶段。在第一阶段,它被称为减少。它将经历两个步骤并将共识问题简化为两个备选问题:同意块哈希或空块哈希。第二阶段是产出共识的结果。可能是Block Hash表示每个人都同意该块,或者它可能是空块。
BA *还将输出最终或暂定的共识结果。最终表明BA已与足够多的人达成共识。该块不能被反驳或分叉;由于分区或网络,暂定可能是异步的。其他节点达成了“暂定共识”的另一个块。
下面我们将分层BA中的操作的汇编模式。
投票
从最简单的投票开始。以下伪代码描述了每轮中的每个步骤。用户必须使用刚刚描述的Sortition()函数来测试他们是否具有参与共识投票的权利(以及多少权重)。
如果j> 0表示他们有权参与此步骤的共识协议,他们将通过Gossiping广播其商定的价值。
点票投票
这里,T和τ分别是两个参数,T表示在该步骤中需要投票的成员的比例,τ表示在该步骤中选择的成员的数量。因此,T×τ是在此步骤中值达到共识所需的总票数。一旦值的值超过T×τ,CountVotes将返回该值。
减少
如上所述,Reduction()是BA *的第一阶段。它通过两个步骤简化共识问题来选择hblock,并选择empty_hash进行多项选择。
在第一步中,委员会成员将投票支持其最初支持的hblock,并等待接收来自其他成员的投票以查看是否存在具有比阈值更多的投票的块散列(T·τ)。如果有,请在第二步投票给哈希。如果没有收到超出阈值的哈希值,请投票给empty_hash。
二元BA
然后我们看看BA *的第二阶段,即BinaryBA。此消息将返回共识,这是新块的共识结果。由于上一步中的Reduction()确保最多只有一个不是empty_hash的着名块散列,因此只需在最着名的block_hash和empty_hash之间进行选择。一般逻辑类似于前一个逻辑。投票后,CountVotes()用于等待此步骤的投票结果。
您可以在程序中看到,在达成共识后,您将继续在接下来的三个步骤中广播值(r)的投票消息(参见步骤< s<步骤+ 3循环)。这是为了允许可能在不同步骤中的其他诚实节点接收我对此block_hash或empty_hash的投票。否则,如果每个人都是异步的,很可能一些诚实的节点已经在步骤1中收集了足够的票数以达成共识,但其余节点在步骤1中没有成功收集投票,但已经进入步骤2或更高版本,所以它无法收集足够的票数。
强同步&弱同步
在弱同步的情况下,不同的诚实节点可能遇到不同的条件。例如,节点A在步骤1中为block_hash收集足够的投票,但是所有其他诚实节点都没有收集足够的投票,因此再次转到下一步和TIMEOUT,因此每个人都更改为empty_string,因此其他节点在比较后面。在就empty_string达成共识的步骤中。
这种事情在一般的BFT中并不常见,因为通常不允许节点签署两个不同的值。但由于Algorand的投票是分阶段的,一个节点可能会在不同的阶段发出不同的投票,所以这个看似荒谬的事件可能会发生。在这种情况下,所有节点都是诚实的,但没有达到完全一致的协议,因此Algorand需要设计FINAL和TENTATIVE来描述共识的状态。
在Strong Synchrony的情况下,大多数用户将在步骤1中达成共识,投票给同一个block_hash,然后他们将被标记为FINAL的委员会投票,其他节点在BA的最后阶段收到*如果有足够的最终投票,它将标记达到分辨率的块是最终的,也就是说,它的最终性可以得到保证。
另一方面,在刚刚介绍的Weak Synchrony中,由于只有少数人 - 节点A在第一轮达成共识,因此COMMteVote(FINAL,block_hash),最终BA *无法收集足够的最终投票,因此该块将是标记为TENTATIVE。暂时变成中国人是暂时的和犹豫不决的,这意味着我们不能保证封锁的终结性。我们必须等到网络恢复正常(强同步)并在块之后看到下一个FINAL块。一切都无法追溯。
所有这些都是Algorand的BA共识算法,每个块的共识将在块在网络上广播时执行。除了这种快速一致的算法外,Algorand还设计了从分区恢复的Recovery机制,这样节点可以清楚地判断网络分区是否发生,可以直接进入Recovery模式等待网络恢复,然后重新同步在一起。你不必像傻瓜那样工作。
委员会规模
在Algorand的设计中,每个投票过程由不同的委员会处理。显然,委员会越大,它就越公平和安全,但肯定会增加通讯造成的延误。在实施过程中,Algorand选择将事故概率控制在5 * 10 ^ -9以下。从下图中可以看出,假设80%的节点是诚实的,委员会需要2000个成员足够大。
实施和评估
最后,将结果和评估结果附在原始论文中。
由于整个算法中不同步骤的安全性或性能不同,Algorand的T,τ的两个参数在正常阶段或FINAL中会有所不同。下图显示了Algorand用于实现其自身算法的参数,这些参数是相对保守的参数。
最后,附上一些实验结果。这是运行100个节点(运行100~1000个VM)的50个节点上运行的Algorand共识的结果,可以发现这几乎是不变的。
另一个有趣的实验结果是不同比例的恶意节点对共识速度的影响。可以看出,在预设比率下,其运行效率不受影响。
后记
写这篇文章的目的可能是虽然我一直说PoS很棒,但我仍然不熟悉它的操作细节。这只是因为我最近阅读了DEXON并看到了关键字Algorand,我决定认真对待它。一点。
个人认为Algorand最有趣的部分应该在本文的前半部分,VRF和Participant Replacement。看到这些聪明的加密应用程序真的很有启发性。我希望我能有时间对未来的其他PoS共识机制有更深入的了解。这很酷很有趣,但真的很难理解!
文章均源于网络收集编辑侵删
提示:仅接受技术开发咨询!