Paxos、PoW、VDF：一条美丽的黄金线

共识问题是分布式系统的根本问题之一。

虽然共识 (Consensus) 和一致性 (Consistency) 在很多文献和应用场景中被认为是近似等价和可互换使用的，但二者涵义还是有着根本的差别。

这个差别和分布式系统的准确概念以及集群的概念密切相关，鉴于分布式系统在不同语境下的模糊使用，以及为了清晰阐述区块链系统的必要，这里借用图灵奖得主Jim Gray的总结解释如下：

集群与分布式系统有何不同？集群似乎只是一种分布式计算系统，就像万维网或Solaris系统的网络，或者……当然，集群是一种简化的分布式系统。但是，这些差异足以使集群算法显著不同。

1. 同质性：集群是同质系统，系统节点具有相同的安全策略、相同的审计策略、相同的命名方案，并且可能运行相同品牌的处理器和操作系统。不同节点之间的软件和硬件的速度和版本可能不同，但它们都非常相似。分布式系统是一个计算机的动物园——由许多不同种类的计算机组成。
2. 局部性：集群的所有节点都在附近的区域内，并通过高速的本地网络连接。由于集群具有现代的硬件和软件，所以具有很高的带宽。带宽很便宜，因为它不是租用电信公司的带宽。集群是可靠的，因为它处于在一个受控的环境。而且集群是高效的，因为它可以使用专门为本地通信优化的协议栈。分布式系统中的通信相对较慢、不可靠且昂贵。
3. 信任：集群中的节点彼此信任。它们为彼此进行身份验证，共享负载，为彼此提供故障转移，通常充当联盟节点。分布式系统通常是相互怀疑的节点的自治集合。

界定分布式系统与集群系统的不同，才能更好的理解共识在不同发展阶段的意义。

袁勇等人的研究成果认为：共识研究侧重于分布式系统节点达成一致的过程及其算法，而一致性研究则侧重于节点共识过程最终达成的稳定状态。此外，传统分布式一致性研究大多不考虑拜占庭容错问题，即假设不存在恶意篡改和伪造数据的拜占庭节点，因此在很长一段时间里，传统分布式一致性算法的应用场景大多是节点数量有限且相对可信的分布式数据库环境。

拜占庭将军问题：拜占庭位于现在土耳其的伊斯坦布尔，是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔，为了防御敌人，每个军队都分隔很远，将军与将军之间只能靠信差传递消息。在战争时期，拜占庭军队内所有将军必须达成一致共识，发现有赢的机会时才去攻打敌人的阵营，但是有些将军可能是叛徒，他们会故意发出错误信息竭力扰乱其他人。忠诚的将军们如何在已知有叛徒的情况下达成一致协议。这就是拜占庭将军问题。

也就是说，一致性更适合于集群系统，共识适合于真正的分布式系统。

一直以来，集群和分布式系统都依赖一个根本的组件，这个组件可以称为网络通信、或者是消息传递。在分布式系统领域圣经级教科书《分布式系统：概念与设计》中，这样定义分布式系统：

分布式系统是指联网的计算机通过消息传递来协调其行为的系统。

在PoW共识机制提出之前，消息传递或网络通信一直是分布式系统的定语。这个定语首先致敬计算机网络发展的功劳，其次也说明了分布式系统作为异步系统的特点和难点。

本文主要阐述：

• 集群与分布式系统
• 共识与一致性
• 共识中的协议与机制
• 机器共识与人的共识
• 分布式系统的理论解与工程解
• 拜占庭将军问题与容错
• paxos三十年：非拜占庭容错共识
• PoW十年：拜占庭容错共识
• VDF的概念和原理
• VDF的应用

一、Paxos三十年：非拜占庭容错共识

计算机发展的历史或多或少直接与计算机网络的历史联系在一起。

上个世纪70年代，计算机网络的发展直接导致了超级计算和并行计算的分野：结束了60年代大型机的分时计算之殇，催生了分布式系统的发展。这个分野背后的深层力量是计算机体系结构领域的两个著名定律：1965年发轫的摩尔定律和1967年提出的Amdahl定律。

分布式系统的初期形态是集群。第一个商业集群产品是由Datapoint于1977年开发的ARCnet，但并未获得商业上的成功，直到数字设备公司DEC于1984年为VAX / VMS操作系统发布其VAXcluster产品，集群本身才真正起飞。同时，任何一个技术浪潮都在不起眼的技术领域里为未来埋下了伏笔：第一台个人电脑Altair 8800于1975年推出，1976年，乔布斯和沃兹尼亚克设计了苹果，并在次年推出了Apple II。

计算机网络的基础理论中孕育了分布式系统最初的胚芽。1975 年，纽约州立大学石溪分校的阿克云卢 (Akkoyunlu E. A.)、埃卡纳德汉姆 (Ekanadham K.) 和胡贝尔 (Huber R. V.) 在论文 “Some constraints and tradeoffs in the design of network communications” 中首次提出了计算机领域的两 军问题及其无解性证明[7]，著名的数据库专家、图领奖得主JimGray正式将该问题命名为”两军问题”。 两军问题表明，在不可靠的通信链路上试图通过通信达成一致共识是不可能的，这被认为是计算机通信研究中第一个被证明无解的问题。两军问题对计算机通信研究产生了重要的影响，时至今日最重要的TCP/IP 协议中的 “三次握手” 过程即是为解决两军问题不存在理论解而诞生的简单易行、成本可控的 “工程解”。

网络技术的发展，给计算机科学家带来了极大的信心和研究动力，这也让上个世纪70年代后期和80年代成为分布式系统基础理论研究的黄金年代。

在这一时期，诞生了四篇至今依然熠熠生辉的理论成果：

1. 1978年，Leslie Lamport 发表《Time, Clocks, and the Ordering of Events in a Distributed System 》，第一次用因果关系定义了分布式系统的时序问题，为消息传递分布式系统奠定根本性的基础。分布式系统的时间问题经过几十年的研究，包括Google的原子时钟等，而如今从VDF来看，时间相关的问题依然是一个根本问题。
2. 1982年，Leslie Lamport 发表《The Byzantine Generals Problem》也就是著名的拜占庭将军问题。消息传递分布式系统中，节点可能出错而发送错误的信息，节点之间的通信链路也可能导致消息损坏，这使得系统中的节点关于全体协作的策略得出不同结论，从而破坏系统一致性。拜占庭将军问题被认为是容错性问题中最难的问题类型之一，从此以后, 分布式共识算法分为两 类，即拜占庭容错共识和非拜占庭容错类共识。 但本文不重点讨论这篇文章的原因是，该文章只是提出了问题，并未解决问题，直到paxos算法的提出（解决了非拜占庭容错类共识）和工作量证明（PoW）的出现（真正解决了拜占庭将军问题）。工作量证明是解决比特币系统中拜占庭问题的关键，是对整个系统的运行状态有着重要的意义。
3. 1985年，Fischer, Lynch and Patterson 发表《Impossibility of Distributed Consensus with One Faulty Process》。按照作者姓氏的首字母，这篇文章以《FLP Impossibility》（FLP 不可能定理）传世，是分布式系统领域的经典结论之一，并由此获得了 Dijkstra 奖。简言之：在含有多个确定性进程的 异步系统中，只要有一个进程可能发生故障，那么就不存在协议能保证有限时间内使所有进程达成一致。FLP 不可能定理同样指出了存在故障进程的异步系统的共识问题不存在有限时间的理论解，因而必须寻找其可行的 “工程解”。为此，研究者们只能通过调整问题模型来规避 FLP 不可能定理，例如牺牲确定性、增加时间（设计分布式系统时都会遇到超时值的问题）等。
4. 1989年，Leslie Lamport 发表了分布式系统一致性协议：Paxos算法（The Part-time Parliament）。对于分布式协议来说，Paxos的历史相对丰富多彩，稍后详细介绍。总之，Paxos给出了非拜占庭故障的同步系统中，使用消息传递实现分布式系统一致性的算法。随着分布式系统共识研究的深入，Paxos 算法获得了学术界和工业界的广泛认可，并衍生出 Abstract paxos、Classic paxos、Byzantine paxos 和 Disk paxos 等变种算法，成为解决异步系统共识问题最重要的算法家族。Lamport在本文中还提出“租约”的的概念，即在有限的时间内为系统分配资源，以便即使在系统停止工作时也可以回收和重用资源。

Leslie Lamport在20世纪80年代末发现Paxos算法，然后他写了一篇论文，并将其提交给《Transactions on Computer Systems 》(TOCS)。由于《拜占庭将军问题》的成功先例（使用寓言或隐喻来描述复杂问题），Lamport将这个重要算法转换为古希腊岛屿上的议会。这就是兼职议会的隐喻：

公元十世纪初，爱琴海上的Paxos小岛是一个繁荣的商业中心。财富导致了政治的复杂化，Paxos的公民采用了议会形式的政府代替了古代的神权政治。但是商业在公民义务之上，在Paxos，没有人愿意将其一生投入到议会当中。Paxos议会需要在议员们不断退出或加入议会的情况下保持工作。 兼职议会面对的问题和当今的容错分布式系统是非常相似的，议员对应于进程，议员离开会议则对应于分布式系统中的失败（故障）。因此，Paxos的解决方案也许对计算机科学有一定的借鉴意义。

Lamport 试图在这个主题中加入一些幽默，但以令人沮丧的失败告终。听过Lamport讲座的人都想起《夺宝奇兵》之类的故事，但都不记得算法。评审论文的人显然被这个希腊寓言弄得心烦意乱，他们无法理解这个算法。

三位评审都说这篇论文有点意思，虽然不是很重要，但所有Paxos的东西都必须删除。Lamport对在这个领域工作的每个人看起来都那么没有幽默感感到很恼火，所以他拒绝对这篇论文进行任何修改。

Lamport把这篇文章发给了南希·林奇(Nancy Lynch)、瓦索斯·哈兹拉科斯(Vassos Hadzilacos)和菲尔·伯恩斯坦(Phil Bernstein)等人，他们自称读过这篇文章。几个月后，Lamport给他们发了一封电子邮件，问了如下问题:

您能否实现一个分布式数据库，该数据库能够在不丢失一致性的情况下容忍任意数量的进程(可能是所有进程)的失败，并且在超过一半的进程再次正常工作时恢复正常行为?

但他们都没有注意到这个问题和Paxos算法之间有任何联系。

然而，该协议开始通过口头传播，并通过德•普里科、林奇和兰普森撰写的一篇正式得多（且冗长得多）的论文开始流行起来。Lamport在最初尝试大约的8年后重新提交了论文，TOCS在第二次请求时几乎以原始形式发表了论文。

对比于常规的理论性的计算机科学论文，这是一个有趣的和受欢迎的变化。

尽管如此，人们还是普遍觉得很难理解。当像南希·林奇这样的名人在读这篇论文都有困难，普通人会更难把握文章内容。最终，Lamport 出版了《Paxos Made Simple》，这是一篇很短的论文，它的语气掩盖了作者对Paxos的策略没有完全奏效的失望：

“The Paxos algorithm, when presented in plain English, is very simple.”“Paxos算法，用通俗易懂的英语表达，非常简单。”

从那以后，Paxos就变得广为人知，部分原因是谷歌将其作为其Chubby系统的核心部分而变得流行起来。正如谷歌的《Paxos Made Live》中所解释的那样，在工程中正确使用Paxos协议是困难的：工程实现会对基本协议做一些变化，其中最重要的可能是multi-Paxos，它允许将请求链接在一起，以减少消息的复杂性。

后面的事情很多读者都已经非常熟悉了，各家互联网公司对paxos算法做了充分的定制和推广，有兴趣的读者可以从《类Paxos共识算法研究进展》和《拜占庭系统技术研究综述》获得一个整体视图。以下是对Paxos衍生文章的简要评述：

1. 《Paxos Made Simple》：以全新的方式呈现Paxos，简短且非常易读。
2. 《Paxos Made Live》：Google的这篇论文弥合了理论算法和工作系统之间的差距。在实施可能无法想象的Paxos时，需要考虑许多实际问题。如果想使用Paxos构建系统，应该首先阅读本文。
3. 《Cheap Paxos》和《Fast Paxos》：两篇论文对原始协议进行了一些优化。
4. 《Consensus on Transaction Commit》：Lamport和Jim Gray的这篇简短论文表明，2PC是Paxos的简化版本，可以容忍零故障。本文是对Paxos的可读介绍。
5. 《How To Build a Highly Available System Using Consensus》：Butler Lampson演示了如何将Paxos共识作为更大系统的一部分。

理论领先于时代，但需要等待工程的检验。互联网大规模应用之后，Lamport终于在2013年获得图灵奖。80年代的分布式系统理论进展，触及了彼时仍然无法想象的未来，恰如此时，我们正处于另一个黎明的前夜。

二、PoW十年：拜占庭容错共识

《比特币的学术谱系》一文如此评价比特币：几乎所有比特币的技术组件都起源于 20 世纪 80 年代和 90 年代的学术文献。 这并不是为了削弱中本聪的成就，而是指出他站在巨人的肩膀上。

比特币已经稳定运行了10年，其机制和原理随着其经济效应已经深入人心。如果向区块链从业者提问关于比特币的技术问题，每个人可能都会同意经济激励和工作量证明的作用和意义。

引入经济激励和工作量证明，比特币解决了开放系统中的拜占庭将军问题——这个结论虽然熟悉分布式系统的人都会同意，但是中本聪在最初的白皮书中没有引用任何拜占庭的文献，也没有使用相关的术语。这与他明确声明参考了链式时间戳的文献（包括工作量证明）形成鲜明对比。他用了一些概念和协议描述共识机制，并以攻击者的形式，以及节点加入和离开网络的方式来考虑故障问题。只有在关于比特币与拜占庭将军问题（一个思想实验）的邮件讨论列表中，中本聪声称工作量证明解决了这个拜占庭将军问题。

研究比特币的学术谱系，我们可以看到每个领域的研究者所面临的困境：Paxos协议的研究者没有考虑节点的激励问题；最初的数字货币（包括hashcash，b-money 和 bit gold）没有考虑共识算法来解决双花问题。也就是说，节点的激励和数字货币的双花问题之间存在一个双环困境：节点需要数字货币激励而抑制作恶；数字货币需要节点达成共识来避免双花。对于这个困境，工作量证明PoW或许可以提供一个桥梁，但依然存在一个双环困境：作为经济机制的数字货币早已存在，但没有转换为激励机制；作为反垃圾邮件措施的工作量证明（PoW）由于缺乏激励而导致使用动机不足。

这就是一个相互矛盾的困窘：没有人支持你除非你已经成功了，但是如果没有人支持，你怎么可能成功呢?

中本聪的天才在于这样的逻辑：强制规定工作量证明就是货币。这样比特币的共识和激励逻辑就是这样的：工作量证明就是货币，这激励矿工努力挖矿提供工作量证明，然后获得货币；同时利用经济学原理设定规则，让恶意节点的投入大于受益，恶意节点没有动力破坏共识，就可以解决拜占庭将军问题中因为将军叛变而不能达成共识的难题，进而也就保护了数字货币的双花问题。

比特币基于 PoW 共识算法是最早和迄今为止最安全可靠的公链共识算法。PoW 的共识思想是：系统节点（即矿工）基于各自的计算机算力相互竞争来共同解决一个求解复杂但是验证容易的 SHA256 数学难题（即挖矿），最快解决该难题的节点将获得下一区块的出块权和系统自动生成的比特币奖励。从分布式系统的角度来看，PoW 共识算法和和类Paxos共识算法相比，有两点重大不同：

1. 竞争出块权是一个leader选举过程，类Paxos共识算法，包括PBFT算法的leader选举都需要节点之间的多次通信，而PoW 共识算法的leader选举是一个自举的过程，竞争出块权本身不需要节点之间互相通信（当然，缺点则是时间延迟和资源浪费）。
2. PoW 共识算法参与节点的算力竞争过程是并行执行的，无需协调节点，而类Paxos共识过程是同步的，一般都需要一个协调节点。

总之，就机器共识来说，一些在区块链中采用的类PBFT和Paxos共识算法，以及目前L1中各种选举类、权益证明类、随机类、联盟类、混合类等共识算法，虽然在一些规模较小的联盟链场景下可以发挥作用，但和比特币的中心思想相比，不能不说一种倒退。

区块链共识算法的历史演进

关于PoW 共识机制与拜占庭将军问题的探讨，袁勇等人指出，现有文献研究的共识问题实际上可以分为算法共识和决策共识两个分支，前者致力于研究在特定的网络模型和故障模型前提下，如何在缺乏中央控制和协调的分布式网络中确保一致性，其实质是一 种 “机器共识”；后者则更为广泛地研究无中心的群体决策中，如何就最优的决策达成一致的问题，例如关于比特币系统扩容问题和分叉问题的社区讨论与路线选择，其实质是 “人的共识”。二者的区别在于：前者是机器间的确定性共识，以工程复杂性为主， 而后者则是以 “人在环回中 (Human-in-the-loop)” 的复杂系统为特点的不确定性共识，以社会复杂性为主。区块链共识算法研究应属于算法共识分支的子集，而决策共识则大多见于分布式人工智能、多智能体等研究领域。

拜占庭将军问题是分布式共识的基础，也是上述两个研究分支的根源。拜占庭将军问题有两个交 互一致性条件，即一致性和正确性。由于大多数情况 下，正确性涉及到人的主观价值判断，很难施加到分布式系统的节点上，因此算法共识采用的是 “降级的正确性 (Degraded correctness)，即从“表达的内容是正确的” 降级为 “正确地表达”，这就导致区块链的拜占庭共识实际上是一种机器共识，其本身等价于分布式一致性+正确表达(不篡改消息)。与之相对的是，决策共识可以认为是人的共识，不仅要求一致性，而且要求所有节点相信 “表达的内容是正确的”，因而决策共识不仅要求内容的客观一致性，而且还要求其在共识节点间的主观正确性。由此可见，算法共识处理的是客观的二值共识，即对 (唯一正确的账本) 和错 (所有错误的账本)，而决策共识处理的是主观的多值共识，即意见 1 (及其所属群体)、意见 2 (及 其所属群体)、···、意见N (及其所属群体)，各节点最终通过群体间的协调和协作过程收敛到唯一意见 (共识)，而此过程可能失败 (不收敛)。

三、VDF：引领未来

据BBC中文网2015年8月1日报道：塞尔维亚国家彩票摇奖过程出现惊人失误，促使警方介入调查。

在通常的电视直播摇奖过程中，每当摇奖机摇出一个带有号码的球之后，电视屏幕上就会随之显示这个号码，加以确认。 在星期二（7月28日）的摇奖中，当摇奖机摇出27号球之后，电视画面错误地显示了21号。 但是，摇奖机接下来摇出的球正是21号。 电视画面早于摇奖机准确预测摇奖号码，这引发了舞弊的猜测，也促使塞尔维亚国家彩票负责人辞职。 塞尔维亚警方已经对事件展开调查，收缴了摇奖机和有关的计算机软件。

彩票引起舞弊的猜测，赌局或游戏中的骰子都依赖于人们手艺，计算机中随机数依赖于一个安全的随机源，这些都是生活中常见的例子。从公众集会、国家彩票到比赛抽签，一个根本的需求是，如何让别人相信你没有作弊？这个根本需求就是如何产生安全的随机数。

目前具有较高可信度的随机数产生方案是美国国家标准技术研究所的NIST Randomness Beacon 和 random.org（这两个都是中心化的随机源）。NIST使用光子和量子力学定律（双光子纠缠）产生随机数，random.org使用大气噪音做为熵源。这些随机数也被称之为”真“随机。

在数字世界中，以比特币为代表的区块链也被用来作为随机源（去中心化的随机源）。这些随机源拥有足够的随机性（70+比特位，更严格地讲，是最小熵），但区块链是开放性网络，当随机数所对应的利益足够大时，区块链将受到区块抑制攻击和贿赂攻击。

为了针对区块链随机源的攻击问题，一个延迟函数被引入进来。也就说通过引入一个延迟函数，这个函数需要1个小时（举例）才能计算出结果，这样只有在1个小时后之后才能得到延迟函数的计算结果（区块链上的随机源作为参数），这样使得区块链成为一个安全的去中心化随机源。

可验证延迟函数VDF的概念是斯坦福大学计算机科学和电子工程教授、计算机安全实验室联合主任Dan Boneh在Crypto 2018大会发布的《Verifiable Delay Functions》论文中首次提出。尽管之前已经有很多研究，包括proof of sequence work（计算结果不唯一），Sloth: slow-timed has（验证不高效）等，但VDF一经提出，就引起了学界和工业界的极大兴趣，在VDF论文发表的10天内，两个VDF的构造论文发布，次月Dan Boneh对两种构造进行了综合评述。迄今为止，关于VDF构造的主要研究按时间线如下所示。

2019—Döttling, Garg, Malavolta, Vasudevan 《Tight Verifiable Delay Functions》

2019—Ephraim, Freitag, Komargodski, Pass 《Continuous Verifiable Delay Functions》

2019—De Feo, Masson, Petit, 《Sanso Verifiable delay functions from supersingular isogenies and pairings》

2018 (30 July)—Boneh, Bünz, Fisch 《A Survey of Two Verifiable Delay Functions》

2018 (22 June)—Pietrzak 《Simple Verifiable Delay Functions》

2018 (20 June)—Wesolowski 《Efficient Verifiable Delay Functions》

2018 (12 June)—Boneh, Bonneau, Bünz, Fisch 《Verifiable Delay Functions》

2015—Lenstra, Wesolowski 《A Random Zoo: Sloth, Unicorn, and Trx》

在产业界，对VDF感兴趣的区块链项目有：

其中Filecoin和Ethereum宣布成立联合实验室，共同研究VDF的构造函数。他们在声明中写道：也许更重要的是，设计和开发一个安全可用的VDF构造将是应用密码学和分布式系统的一个重大突破，其适用性甚至超越了区块链。

并且协议实验室和以太坊基金会还共同出资50/50成立了两个VDF相关的项目：supra national 和 ligero。

VDF的模型非常简单，意义却非常重大。

VDF是 Verifiable Delay Function的缩写， Function说明VDF是一个函数，对每一个输入都有一个唯一的输出。Delay 可以用一个时间T（wall time）来表示，延迟函数在时间T完成计算，但不能通过并行加速在小于时间T完成计算。Verifiable 要求延迟函数的输出非常容易验证。

wall time，也称为真实世界的时间或挂钟时间，是指由钟表或挂钟等计时器确定的经过时间。（“wall”一词最初得名于对挂钟的引用。）

为了VDF的功能，即”抗并行加速的延迟”以及“可验证的结果”，VDF 中必然包含一个用于计算结果的算法以及一个用于验证结果的算法。同时，这样的密码学 工具 通常还包含一个设置阶段，用来确定后续需要使用的参数。因此，VDF 被描述为三个算法的一个三元组 (Setup, Eval, Verify)。

每个算法的定义如下：

1. Setup(λ,T)→pp=(ek,vk) 接受安全参数 λ 以及时间参数 T，生成一个公共参数 ，这个参数是所有人都可以看到的。公共参数包含了一个用于计算的参数 ek 和一个用于验证的参数 vk。
2. Eval(ek,x)→(y,π) 接受计算参数 ek 和输入 x∈X，计算出输出 y∈Y 和证明 π。
3. Verify(vk,x,y,π)→{accept,reject}接受 vk，x，y 以及 π，输出 true（验证通过）或者 false（验证失败）。

如下图所示 VDF 的运行流程。

上述VDF过程最重要的一点是：在计算时要求大量计算资源，但验证时只需花费相对少的计算资源。这样种计算和验证的非对称关系乍看起来有点像工作量证明（PoW）。批评接踵而至：“ 听起来我们又回到了工作量证明 ”，“ 不再烧一轮 CPU 我们就干不了这事是吗 ？”——文献《VDF不是工作量证明》一文指出：虽然 VDF 和传统的 PoW 算法都拥有“难以计算”且“易于验证”这样的属性，最核心的区别在于区块链工作量证明共识算法是可并行化工作量证明，并且只是有概率会成功，不是一种函数。相反，VDF 是连续工作量证明，是确定的函数。

关于VDF和PoW的区别，邱飞旸在《一文搞懂可验证延迟函数 VDF》中指出：PoW 直接作为随机数的来源是有缺陷的，同时，VDF 也无法直接替代 PoW。但是这并不能说明 VDF 不可以被用到共识协议里。原因如下：

1. PoW 不抵抗并行计算加速而 VDF 抵抗。实际上，PoW 不抵抗并行计算加速是符合中本聪的“一 CPU 一票”的设想的，而抗并行加速的性质只会与这个目的背道而驰。VDF 会使得多 CPU 的计算者和单 CPU 的计算者相比几乎没有什么优势。
2. 对于固定的难度设定 d，PoW 可以有很多合法的解，这也是保证 PoW 共识网络拥有稳定的吞吐量以及刺激矿工进行竞争的前提。而对于给定输入 x，VDF 拥有唯一的输出（这也是为什么它被称作函数）。

VDF的应用范围很多，包括增强公共可验证随机数的安全性，解决 Nothing-at-stake Attack，减轻 Long-range Attack等，这些内容可以参考邱飞旸在《一文搞懂可验证延迟函数 VDF》。本文主要关注VDF思想在期望共识、复制证明和时空证明中的应用。

复制证明是要证明一个台服务器上存储了数据的唯一副本，这和存储证明是有区别的。Ben Fisch 在BPASE '18上指出，通过加密学无法实现最强复制证明（Impossibility of Strongest Replication Definition），然后通过引入“理性敌人”的概念，以及设计激励机制让作恶的收益非常低，且在任意时刻转换为“好”策略的代价非常低，这样就没有动机作恶。复制证明的一个思路是利用VDF在时间上不对称的编码方案（也就是编码很慢，但是解码很快），如下图所示，如果服务器删除数据，将无法快速的响应验证着的挑战。

时空证明的基本思想是将时空证明分为多个EPOCHS的周期，每个周期必须接受来自随机信标的挑战，该信标在每隔固定时间输出一个挑战（对于Filecoin，区块链充当随机信标）。时空证明生成proof的过程如以下伪代码所示。

<code>- *Step 1*: Generate `POST_EPOCHS` proofs: </code>
<code> - `mix = challenge_seed`</code>
<code> - `challenge_stream = NewChallengeStream(PublicParams)`</code><code> - Repeat `POST_EPOCHS` times:</code>
<code>   - `(challenges, challenged_sectors) = challenge_stream(mix)` </code>
<code>   - Generate proof: `porep_proof = OnlinePoRep.prove(challenges, challenged_sectors, commR, replica)`</code>
<code>   - append `porep_proof` to `porep_proofs[]`</code>
<code>   - Add `porep_proof` to `porep_proofs`</code>
<code>   - Slow challenge generation from previous proof `porep_proof`:</code>
<code>     - Run VDF and generate a proof</code>
<code>        - `x = ExtractVDFInput(porep_proof))`</code>
<code>        - `y, vdf_proof = VDF.eval(x)`</code>
<code>        - Add `vdf_proof` to `vdf_proofs`</code>
<code>        - Add `y` to `ys`</code>
<code>        - `mix = y`</code>
<code>- Step 3: Output `porep_proofs`, `vdf_proofs`, `ys`</code>

时空证明的验证过程如以下伪代码所示。

<code>- *VDF Output Verification*</code>
<code>  - For `i` in `0..POST_EPOCHS-1`</code>
<code>    - assert: `VDF.verify(pp_vdf, ExtractVDFInput(porep_proofs[i]), ys[i], vdf_proofs[i])`  </code>
<code>- *Sequential Online PoRep Verification*</code>
<code>  - assert: `OnlinePoRep.verify(commR, challenges_0, porep_proofs[0])`</code>
<code>  - for `i` in `1..POST_EPOCHS`</code>
<code>    - Generate challenges  `for j in 0..CHALLENGE_COUNT: challenges[j] = H(H(ys[i-1])|j)` `</code>
<code>    - assert: `OnlinePoRep.verify(commR, challenges, porep_proofs[i])`</code>

VDF硬件可以加速VDF的运行。在每个“EPOCHS”中，一小部分的加速增益将导致在最快和最慢的验证者之间的“总验证时间”有很大的时间差。Filecoin把最快证明时间和平均证明之间的差异称为“VDF加速差距”，并且将VDF加速差距规范为(0-1)。由于时空证明的每个周期都必须接受来自随机信标的挑战，更快的验证器可以在每个EPOCHS期间加速“VDF加速差距”，但不能缩短整个时空证明的“VDF加速差距”。换句话说，最快的验证者不能累积每个EPOCHS期间的收益，因为他们必须等待来自随机信标的新挑战。

期望共识协议是一种概率拜占庭容错一致性协议。从高层次来说，它的运作方式是每一轮进行一次leader节点选举，一名leader节点提交区块个数的数学期望为1。基于时空证明，可以证明矿工拥有系统总资源的X%的资源，那么拥有X%资源的矿工在任何出块周期中挖到区块数量的数学期望是X%。然后将X%的资源分成X份，每份1%，对于x1，…，xn个不同的值。然后对每个X进行独立随机试验：

1. Ri = HASH(xi) (0,N)
2. 矿工找到 R=Min(R1,...,Rn)

然后通过x和前面的区块得到一个不可预测的挑战随机数，用这个随机数和与R成比例的延迟时间T作为参数，执行VDF计算。

通过复制证明、时空证明和期望共识的例子，VDF展示了基于资源的证明和基于延迟的共识协议的基础性的、可行性的未来，这会为安全随机数以及更多可证明应用和算法奠定基础，正如Boneh在其开创性论文《Verifiable Delay Functions》中的结论所说：

鉴于其大量有趣的应用，我们希望这项工作能够刺激VDF新的实际应用，并继续研究其理论构造。我们仍然缺乏一个理论上最优的VDF，它由一个简单的内在顺序函数组成，需要较低的并行度来计算，但是验证非常快(例如对数)。这些要求激发了对密码学中传统上没有使用的新问题的探索。理想情况下，我们希望VDF也是后量子安全的。

四、总结

 

拜占庭将军问题和Paxos算法的提出近40年，真正大规模应用是过去10年。Bitcoin从2008年提出至今已过10年，其共识机制PoW算法也稳定运行超过10年。2018年6月12日VDF函数机制提出，到今天2018年6月12日，刚好满一年。从Paxos到PoW，再到VDF，分布式系统的理论发展画出了一条美丽的黄金线。在这条黄金线背后，是计算机系统的基本问题：时间和空间。当牛顿以为了解这一切的时候，爱因斯坦笑了；当爱因斯坦以为了解这一切的时候，海森堡和薛定谔笑了；当人类开始思考时间和空间的时候，上帝笑了。

VDF的提出，是应用加密学，分布式系统和区块链领域的重大技术突破，为区块链的资源共识，时空证明，leader选举等难题奠定可行性的基础。不仅如此，作为一种延迟服务和随机信标服务，也可以应用到其他领域。相对于Paxos，VDF保留了区块链开放系统的特点，支持拜占庭容错。相对于PoW，VDF继承了其“工作量”效果，化解了电力之殇。所以，过去的十年是paxos和pow的十年，未来的十年将是VDF的十年。因此我倡议成立VDF中国社区，共建硬件和软件生态，一起研究，一起探索新的应用领域。

VDF中国社区：https://github.com/taoshengshi/research/blob/master/vdf.md

本文参考文献：

《类Paxos共识算法研究进展》

《拜占庭系统技术研究综述》

《CAP理论与分布式系统设计》

《加密数字货币系统共识机制综述》

《PoW 共识算法中的博弈困境分析与优化》

《比特币的学术谱系》

《VDF不是工作量证明》

《一文搞懂可验证延迟函数 VDF》

《区块链共识算法的发展现状与展望》

《The Part-Time Parliament》

《Proof of Replication using Depth Robust Graphs - BPASE '18》

《Verifiable Delay Functions - Crypto 2018》

时间是幻想

  “ 对相信物理的我们来说，不管时间多么持久，过去、现在、未来之间的分别，只是持续存在的幻想。 ——爱因斯坦（Albert Einstein） ”

“过去10年最有价值的初创公司没有筹集资金，没有员工，没有上限，让任何人都可以投资。” ——Bitcoin和Uber都是2009年左右推出的。如今，Bitcoin的市值约为1380亿美元；Uber的估值约为750亿美元。他们将从这里走向何方?

本文来源： 补天遗石 （微信公众号：butianys）

作者：tshi