简评三种基于VRF的* * *识别算法

Algorand、Dfinity、Ouroboros Praos(虽然Dfinity是项目名称，这里称之为* * *算法也没有错)最近比较受关注，都是基于VRF(可验证随机函数)设计的，可以比较研究。Algorand有多种版本，指的是以下哪一种？1607.05438+0341V9，暂称为algrand '(作者有最新版本的algrand，其中修正了下面提到的几个问题，请参考本文)。

一、VRF * * *

VRF的意思很容易理解——它用来完成对人(群体)的随机选择。因此，VRF的回报值应该尽可能不可预测。我们先来看看Algorand '和Dfinity的套路是怎么做的:一般来说，前面的随机数(初始随机数是协议给定的)和某个代表高度和转弯的变量组合，用某个私钥签名(或者先签名再组合)，最后哈希得到最新的随机数。这样产生的随机数容易被别人验证符合算法，从而得到“V”；而且hash返回值是随机分布的，所以保证了“r”。在这个过程中，为了减少结果被操纵的可能性，有两点需要注意:a)签名算法要唯一，即使用同一个私钥对同一条信息进行签名，只能验证一个合法的签名——普通的非对称加解密算法一般不具备这个属性，比如SM2。如果使用的签名算法不具备这种唯一性属性，那么在生成新的随机数时，就有反复尝试签名以挑出最有利的一个的空间，会降低安全性。b)避免在生成新随机数时，将当前块的数据作为随机性的来源之一，比如引用本块交易列表的merkle根值等。，因为这样会给块主空间去尝试改变打包交易的顺序，打包不同的交易，生成最有利的新随机数。在设计和检验新的* * *识别算法时，要特别注意以上两点。

检查应该如何使用VRF的返回结果。在目前的用法中，VRF的返回结果可以用来完成公有或私有的节点或节点组的选择。以Dfinity为例，它使用mod运算来唯一公开地确定一个组。“Algorand”和“Ouroboros Praos”是私人选择的例子。一般的例程是用rounds之类的变量对VRF的最新返回值进行签名和哈希。如果哈希值小于某个阈值，则节点可以知道它是私有选择的。这种方法很可能在网络节点数量较多的情况下更加稳定，否则幸运者数量会出现较大波动，影响协议性能，包括空块和分叉。

第二，简要评论Algorand的强同步假说版本

私有选择提供了很强的抵抗定点攻击的能力，但是对于任何一个幸运者来说，幸运者的总数都是不可预测的，这给后续识别算法的设计和区块链的优化带来了困难。Algorand ' '采用强同步网络假设(同步网络假设下的* * *识别算法当然更容易做)，要求提前知道网络消息传播时间的上限:在固定时间内完成对固定比例用户的网络传播。比如你要知道1KB的消息可以在1秒内传播95%的全网，而1MB的消息需要1.5分钟才能传播95%的全网。但是这个传输上限怎么选呢？通过实证统计一段时间的统计结果乘以一个系数？只能说“感觉还可以”，但如果要严谨和安全的话，Algorand ' '算法要补充证明在DDOS或者互联网拥塞的情况下，即使消息传播严重超限，算法仍然可以保证安全——然而，这个证明是缺失的。相比之下，Ouroboros Praos公开承认在同步网络假设下设计的Ouroboros协议在异步网络条件下会出错，于是又做了Ouroboros Praos。新版Algorand承认网络弱同步时会在不同块上达到* * *知识(后面网络强同步时可以解决分叉)，可以借鉴。

即使我们暂时同意Algorand的算法可以通过设置较大的传播时间上限来应对上述问题，但可以看出，这种算法缺少一个非常好的特性:响应性。这个特性意味着，如果一个协议被设计成在一个较大的传播时间上限delta下工作，但如果实际传播时间是一个较小的delta，那么协议的实际前进步伐将只与DELTA有关，这个协议被称为反应式的。把* * *识别算法和同步网络假设结合起来会比较理想——为了安全，上限可以设得很大，但是协议的执行速度只和当时的网络条件有关。“阿尔格兰德”没有这个特点。平均而言，Algorand '需要11轮消息传输才能完成* * *知识。如果每一轮都要保证安全，那么* * *知识需要很长时间才能完成，单个分区的吞吐量也不会太高。当然，架构设计涉及许多权衡。最后，评价一个算法好不好，还是要回到初心——要达到的目标是什么。以上分析只是试图客观地指出Algorand算法几个鲜为人知的固有特点，供读者自我评价。

第三，简要评述了Dfinity的可扩展性

私下选，马上上任的做法，也给体制分割带来很大挑战。Dfinity肯定是要分片的，所以我们必须直面挑战。可伸缩性的问题非常复杂。要彻底解决这个问题，需要考虑网络、存储、计算的可扩展性。目前大部分区块链3.0项目只关注计算的碎片化和可扩展性，忽略了另外两个，所以无法实现理想的扩展。由于公链节点网络带宽的限制，通常很难将计算契约所需的数据从一个节点快速复制到另一个节点，所以即使使用VRF来选择不时来往的节点，存储节点也无法像风一样优雅。有几个明显的选择:所有节点存储所有数据，不同节点静态分配存储不同分区。前者的可扩展性很差。对于后者，如果传出节点浮动，传出节点需要完成契约操作，意味着基于P2P网络的远程存储来回访问的性能会急剧下降。动态确定的分块节点只完成排序、计算能力和存储捆绑，通过静态划分提供可扩展性，可能是合理的回应。然而最可恨的还是“然而”二字——即便如此，系统中的存储和网络仍然存在压力:最终用户提交的待打包交易。普通公链(不考虑EOS)的带宽是有限的。如果用户提交的要打包的事务必须广泛分布在整个网络中，现有的网络带宽能提供多少TPS？如果输出节点是静态分区或至少提前一段时间为公众所知，则仍有回旋余地；如果传出节点如此飘忽不定，并且只有这些节点直到最后一刻才知道，那么无论是用户还是传出节点的候选，似乎最直接的反应就是泛洪整个网络，保存所有要打包的事务，这样带宽和存储仍然成为系统瓶颈。

所以我们这里遇到的，本质上是一个安全、可扩展、去中心化的不可能三位一体。

第四，简单评论一下大毒蛇Praos

BMŭ·大毒蛇的作品已经广为流传。当然，BM的话明显是错的。比如大毒蛇的DPOS指的是“动态[栈分布] POS”而不是BM的委托POS，但其对帕累托分布的评论值得玩味。如果我们仔细浏览一下Ouroboros Praos，可以发现协议的安全假设和安全证书完全没有考虑经济博弈的因素，那么振振有词的证明很可能错过了真正需要保护的方向——毕竟POS/DPOS协议血管里流淌的血液一直是基于经济博弈和人性的。最明显的例子就是前向安全签名的实现方法。协议目前的设计要求每一个好节点自愿安全地删除使用过的私钥，没有考虑近乎零的私钥存储成本如何面对贿赂攻击的诱惑。但是，这是值得考虑的。除了形式证明，Ouroboros Praos本身并没有太多值得关注的协议特性。总的来说，它使用VRF彩票结合POS算法来形式化证明一些安全假设，做事的态度非常值得称道。

动词 （verb的缩写）摘要

这些算法很有创意，值得学习。同时，看了以太坊的CASPER披露的分区技术，笔者的体验是，区块链3.0的竞争才刚刚开始。从以太坊团队的技术路线来看，他们的技术考量和选择比很多号称超越以太坊的团队更加深刻和全面。如果我们真的想超越以太坊，首先要了解以太坊。

顺便感谢邱伟伟博士对本文的贡献！