技术公开课丨能扩容，还能提高安全性？Algorand 首席密码学家带你玩转VRF

巴比特加速器技术公开课是一款全球化的线上区块链技术栏目（Geekhub Global Online），包含深度对话及课程。我们会定期邀请世界各地的资深技术大咖在线解构区块链技术，旨在为Geekhub技术社区输送前沿高质量的区块链技术内容；同时社区成员也可以参与直播互动，共同探讨区块链的技术发展与未来。

漫漫熊市一度风平浪静，但上周ETC的51%算力攻击却再次将PoW推上风口浪尖，以太坊创始人Vitalik表示这也证明以太坊转向PoS的决定是正确的。同时，由于PoW采用不断碰撞目标哈希值的方式争夺记账权，需要耗费大量计算资源，由此产生的巨大电力消耗是PoW为部分批评者所诟病的重要原因。为了从根本上解决PoW机制中资源耗费的情况，PoS应运而生。而PoS机制应采用何种随机算法实现记账的公平性和系统的鲁棒性成为其核心问题。

作为一种低能耗、高效率的随机数算法，VRF（可验证随机函数）算法近年来得到了越来越多人的关注。可以帮助区块链扩容，还可以提高安全性，很多人认为，基于VRF的共识机制或许可以改善“不可能三角”问题。本周Geekhub Global Online第四期《VRF安全的桥梁》特别邀请了Algorand 首席密码学家、滑铁卢大学的助理教授Sergey Gorbunov为你答疑解惑，带你玩转“黑科技”——VRF。

以下为本次AMA实录。

1.什么是VRF（可验证随机函数）？VRF是如何运行的？

Sergey：可验证随机函数（VRF）是一种加密原语（primitive，通常由若干条指令组成，用来实现某个特定的操作），可将输入映射到可验证的伪随机输出。简单地说，对于固定密钥对和输入X，VRF可以生成一个唯一的伪随机可验证输出。

VRF由Micali、Rabin和Vadhan于99年提出。当前这个原语被用在各种加密方案、协议和系统中。

###更多技术细节###

VRF是Keygen，Evaluate和Verify三种算法的结合。 •Keygen（r）→（VK，SK）。对于一个随机的输入，密钥生成算法生成一个验证密钥VK和一个私密密钥SK的密钥对。 •Evaluate（SK，X）→（Y，⍴）。评估算法将私密密钥SK，消息X作为输入，并生成伪随机输出字符串Y和证明（proof）⍴。 •Verify（VK，X，Y，⍴）→0/1。验证算法将验证密钥VK，消息X，输出Y和证明⍴作为输入。当且仅当它验证得到Y是评估算法在输入SK和X才得到的输出时，它的输出为1。

它具有以下属性：

•输出Y是唯一的。也就是说，对于给定的密钥对（VK，SK）和输入X，不可能找到另一个输出（以及有效的证明⍴）。 •输出Y是伪随机的，这意味着它对于任何没有看到相关证明⍴的第三方来说，看起来是“随机的”。 （注意，对于给定的证明⍴，通过调用验证算法并检查结果，很容易将Y与一个随机输出区分开来，以确定Y是否是评估算法在输入SK和X才得到的输出）。 •即使用户对手性地选择了密钥对（VK，SK），上述属性也应保留。

2. VRF是如何在当前的区块链中使用的？

Sergey：Algorand Blockchain的核心就是一个快速的拜占庭协议。但是，不是在网络中的所有用户之间执行这一协议。相反，它每次的执行仅限于随机选择的小型用户委员会（committee）。

对于每个区块，Algorand系统中的每个用户都基于他/她的VRF密钥执行私密自选。如果用户获得的VRF值小于某个阈值，则系统会选择该用户加入委员会来执行该区块的协议。

3.将VRF添加到共识机制中会发生什么？

Sergey：它可以支持对区块链系统进行扩容以支持数百万用户的使用。这是因为我们可以随机抽取代表群体的少数人群作为样本来做出决定并达成共识。

此外，它允许支持非常强大的对手模型，用户可以私密地进行自我选择。没有人知道选定的用户是谁，直到他们广播出与他们相关的VRF输出/证明对以及他们想要签名的消息。

如果没有VRF，在一个PoS系统中，就要对所有用户执行拜占庭协议。有了VRF，只需要随机抽样一小部分的用户，让他们代表总体做出共识。因此采用VRF的可拓展性和安全性可以得到很大提高。

4.自DPOS（EOS）问世以来，公共区块链的效率得到了极大的提高，但其在去中心化和安全性方面存在缺陷。 VRF的引入能否提供更好的解决方案？

Sergey：许多PoS区块链仅支持“静态或半动态”的委员会。使用VRF，我们可以有效地为每个区块轮换委员会。

在别的PoS系统里，委员会成员要么要押下自己的stake，要么要其他用户选出代表来代表他们投票。但普通用户可以被对手攻击，无法上线，也就无法被选入委员会。有了VRF，所有用户都有机会进入委员会，来参与共识达成的过程。

5. VRF模型中的经济激励体系有何不同？经济激励如何实施？

Sergey：在任何系统中设计一套合理的激励机制都是一项棘手的工作。我们应该正确地设计激励措施使得用户失去囤积stake的激励，而是激励他们支持网络的健康发展，这一点非常重要。

6.在存在多个候选区块的情况下，如何快速达成共识？你们具体是如何处理这个问题的？

Sergey：Algorand的密码分类机制的参数被设置为，为区块提议者选择若干个候选（例如20）。实际上，这意味着少数一部分用户，而不仅仅是一个用户，将拥有其VRF函数的输出，使得该输出落在成为区块发起者的“获胜”区间中。然后，每个候选人必须将他们的候选区块和该轮的“中奖票”（获得的VRF值）广播到网络。网络选择拥有最小VRF值的候选者作为区块发起者。因此，如果某些候选区块提议者不在线，他们将不会进入最终候选人池。

所以，总的来说就是VRF输出值最小的候选人将会被选为最终的区块发起者。一个委员会会在这个区块执行拜占庭共识。

7.VRF需要一定数量的团队成员协作才能完成验证工作。在工程中，不可避免地会遇到大量的组成员签名数据，这会带来验证签名的性能开销（overheard）和磁盘存储开销。我们是否能找到优化的解决方案？

Sergey：我们正在努力提高我们使用的签名方案和VRF功能的效率和大小。现在有一些有趣的结构支持签名聚合（BLS签名），例如，将签名分成小的组。

以BLS签名为例，我们可以将一个签名集压缩成一个短签名，验证全部的签名我们只需要验证这个压缩后的短签名。我们就可以验证这个签名是否被其他用户签署。

8.Algorand目前的进展如何？我们什么时候可以看到主网络或测试网络？

Sergey：我们有一个正在运行的测试网络，非常欢迎大家访问我们的网站并注册。随着我们对测试网的可靠性越来越满意，我们将把它扩展到更广泛的社区。 与此同时，我们将继续在协议以及将在协议上创建的下一组功能上进行创新，包括对智能合约的支持以及隐私和扩容方面功能的提升。

9.从Micali教授提出的整套Algorand的想法来看，整个项目的实际开始时间是2018年下半年。在将理论转变为现实的过程中，有遇到什么困难吗？如果有，最大的困难是什么？

Sergey：我们大约在一年前与初始团队一起开始着手创建协议。最初团队的所有成员在这个项目开始前，都已经和Micali在研究和制定协议原型方面合作了好几年。因此，我们已经了解了有关构建和扩展协议的大量信息，有了充分的准备。

在公司，我们建立了从研究到生产的连续性管道（continuous pipeline）。我们的研究团队不断与开发人员进行交互，同时我们也不断在调整和改进协议。

社区问答

1.现在Algorand一个区块出来会有多少签名？签名的数据量有多大？

Sergey：Algorand每个区块都在一个委员会内执行拜占庭共识，一个区块大概需要2000多个签名，用户签名的区块可以包含几千个交易，这让我 们TPS达到几千。

2.Algorand今年的计划是什么？

Sergey：我们的工作主要还在扩容测试网上，正在准备主网的上线的工作。我们会展示如何在区块链上通过API，菜单以及各种工具创建应用。需要指出的是，Algorand不像别的项目那么，进行一次ICO就完成募资了，我们会进行一系列的拍卖来发售我们的代币。发售获得资金将用于建设我们的社区，投入到我们的技术研究中。

直播预告

本周Geekhub Global Online第四期《VRF安全的桥梁》火热进行中。1月16日（周三）11时，DFINITY创始团队成员兼首席发言人Arthur Falls将与大家分享《通过随机之路：DFINITY共识》。欢迎大家扫描海报中的二维码，加入官方直播群，参与学习和讨论。