Paxos，PoW，VDF：美丽的金线

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

虽然在许多文献和应用场景中认为共识和一致性大致相同且可互换，但两者的含义根本不同。

这种差异与分布式系统的确切概念和集群的概念密切相关。鉴于分布式系统在不同环境中的模糊使用以及需要清楚地解释区块链系统，这里是图灵奖得主吉姆格雷的总结。说明如下：

集群和分布式系统有什么区别？集群似乎只是一个分布式计算系统，如万维网或Solaris系统的网络，或……当然，集群是一个简化的分布式系统。但是，这些差异足以使聚类算法显着不同。

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

定义分布式系统和集群系统之间的差异可以更好地理解在不同开发阶段达成共识的重要性。

袁勇等人的研究成果。认为共识研究侧重于分布式系统节点的过程和算法，而一致性研究侧重于节点共识过程最终达到的稳定状态。此外，大多数传统的分布式一致性研究都没有考虑拜占庭容错问题，即没有拜占庭节点用于恶意篡改和伪造数据。因此，长期以来，传统分布式一致性算法的应用场景大多受到限制。并且相对可靠的分布式数据库环

拜占庭将军：拜占庭位于土耳其伊斯坦布尔，是东罗马帝国的首都。由于当时拜占庭罗马帝国的广阔领土，为了抵御敌人，每支军队都远离敌人，将军和将军只能靠信使传递新闻。在战争期间，拜占庭军队的所有将军必须达成共识并发现在攻击敌方阵营之前有机会获胜，但是一些将军可能是叛徒，他们会故意发出虚假信息试图扰乱他人。忠诚的将军如果知道有叛徒，他们怎么能达成协议。这是拜占庭将军的问题。

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

传统上，集群和分布式系统依赖于基本组件，可以称为网络通信或消息传递。在分布式系统领域的圣经教科书“分布式系统：概念和设计”中，这定义了一个分布式系统：

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

在提出PoW共识机制之前，消息传递或网络通信一直是分布式系统的属性。这种属性首先表达了对计算机网络发展的贡献，其次说明了分布式系统作为异步系统的特性和难点。

本文主要介绍：

I. Paxos三十年：非拜占庭容错共识

计算机开发的历史或多或少与计算机网络的历史直接相关。

在20世纪70年代，计算机网络的发展直接导致了超级计算和并行计算的划分：20世纪60年代大型机分时计算的结束，导致了分布式系统的发展。这种鸿沟背后的深层动力是计算机体系结构领域的两个众所周知的法则：1965年出版的摩尔定律和1967年提出的阿姆达尔定律。

分布式系统的初始形式是群集。第一个商业集群产品是由Datapoint在1977年开发的，但直到数字设备公司DEC于1984年发布其用于VAX / VMS操作系统的VAXcluster产品并且集群本身起飞之前，它才取得商业成功。与此同时，任何技术浪潮都为谦逊的技术领域奠定了未来的基础：第一台个人电脑Altair 8800于1975年推出，1976年，乔布斯和沃兹尼亚克设计苹果，而Apple II则在那一年。

计算机网络的基本理论催生了分布式系统的原始细菌。 1975年，Akkoyunlu EA，Ekanadham K.和Huber RV在纽约州立大学石溪分校的论文“在网络通信设计中的一些限制和权衡第一次，在计算机领域的两个军事问题提出了他们无法解决的证据（7）。著名的数据库专家和人物获得者JimGray正式将这个问题命名为“两个军事问题”。两军的问题表明，通过不可靠的方式达成共识是不可能的。通信链路被认为是计算机通信研究中第一个被证明无法解决的问题。这两个军事问题对计算机通信研究产生了重要影响。最重要的TCP / IP中的“三次握手”过程迄今为止的协议简单易行，解决了两个军事问题的成本。控制的“工程解决方案”。

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

在此期间，今天依然闪耀的四个理论成果诞生了：

1. 1978年，Leslie Lamport发表了“分布式系统中的时间，时钟和事件排序”。有史以来第一次使用因果关系来定义分布式系统的时序问题，为消息传递分布式系统奠定了基础。几十年来已经研究了分布式系统的时间问题，包括谷歌的Atom钟，而现在，从VDF，时间相关的问题仍然是一个基本问题。
2. 1982年，Leslie Lamport出版了拜占庭将军问题，也被称为拜占庭将军。在分布式消息传递系统中，节点可能发送错误并发送错误消息。节点之间的通信链路也可能导致消息损坏，这导致系统中的节点得出关于所有协作策略的不同结论，从而破坏系统一致性。 。拜占庭式的一般问题被认为是最难以容错的问题之一。从那时起，分布式共识算法被分为两类，即拜占庭容错共识和非拜占庭容错共识。然而，本文不关注本文的原因是文章只提出了问题，并且直到paxos算法的出现（解决非拜占庭容错共识）和出现的问题才解决问题。工作量证明（PoW）（真的解决了）。拜占庭将军问题）。工作量证明是解决比特币系统中拜占庭问题的关键，对整个系统的运行状态具有重要意义。
3. 1985年，Fischer，Lynch和Patterson发表了“在一个错误的过程中不可能达成分布式共识”。根据作者姓氏的第一个字母，这篇文章是FLP不可能性（FLP不可能性定理），这是分布式系统领域的经典结论之一，因此获得了Dijkstra奖。简而言之：在具有多个确定性进程的异步系统中，只要一个进程可能失败，就没有协议可以保证所有进程在有限的时间内达成一致。 FLP不可能性定理还指出，对于具有错误过程的异步系统的共识问题，没有有限时间的理论解决方案，因此有必要找到一个可行的“工程解决方案”。为此，研究人员只能通过调整问题模型来规避FLP不可能定理，例如牺牲确定性，增加时间（设计分布式系统时的超时值问题）。
4. 1989年，Leslie Lamport发布了分布式系统一致性协议：兼职议会。对于分布式协议，Paxos的历史相对丰富和详细，稍后将对此进行详细描述。总之，Paxos提供了一种算法，该算法使用具有非拜占庭故障的同步系统中的消息传递来实现分布式系统一致性。随着分布式系统共识研究的深入，Paxos算法得到了学术界和业界的广泛认可，并衍生出变异算法，如抽象paxos，Classic paxos，拜占庭paxos和Disk paxos，这是解决共识问题最重要的。异步系统。算法族。 Lamport还在本文中提出了“租赁”的概念，它在有限的时间内为系统分配资源，以便即使系统停止工作也可以回收和重用资源。

Leslie Lamport在20世纪80年代后期发现了Paxos算法，然后他写了一篇论文并将其提交给了计算机系统交易（TOCS）。由于拜占庭将军的成功先例（使用寓言或隐喻来描述复杂问题），Lamport将这一重要算法转换为古希腊群岛的议会。这是兼职委员会的比喻：

在10世纪初，爱琴海上的Paxos岛是一个繁荣的商业中心。财富导致了政治上的复杂化，Paxos的公民采用了议会政府而不是古代神权政治。但是，企业高于公民义务，而在Paxos，没有人愿意将自己的生命投入议会。 Paxos委员会需要继续工作，而议员们不断提现或加入议会。兼职议会面临的问题与当今的容错分布式系统非常相似。成员对应于流程，议会离开会议以对应于分布式系统中的故障（故障）。因此，Paxos解决方案可能会参考计算机科学。

兰波特试图为这个话题添加一些幽默，但最终却以令人沮丧的失败告终。听过Lamport讲座的人会想到像“迷失方舟的攻略”这样的故事，但不记得算法。回顾这些论文的人显然对这个希腊寓言感到不安，他们无法理解这个算法。

所有三位评委都说这篇论文有点有趣，虽然不是很重要，但所有Paxos的东西都必须删除。 Lamport很生气，所有在该领域工作的人都显得如此幽默，所以他拒绝对报纸做任何修改。

Lamport将这篇文章发给了Nancy Lynch，Vassos Hadzilacos和Phil Bernstein，他们声称已经阅读过这篇文章。文章。几个月后，Lamport向他们发送了一封电子邮件，询问了以下问题：

您是否可以实现一个分布式数据库，该数据库可以容忍任意数量的进程（可能是所有进程）的失败而不会丢失一致性，并在超过一半的进程再次运行时恢复正常行为？

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

然而，该协议开始口头传播，并受到De Prico，Lynch和Lampson撰写的更正式（更冗长）论文的欢迎。 Lamport在初次尝试后大约八年后重新提交了论文，TOCS在第二次请求时以原始形式发表了论文。

与传统的理论计​​算机科学论文相比，这是一个有趣且受欢迎的变化。

尽管如此，人们仍然觉得很难理解。当像Nancy Lynch这样的名人难以阅读本文时，普通人更难掌握文章的内容。最后，Lamport发表了一篇简短的论文Paxos Made Simple，其语气掩盖了作者对Paxos的失望。战略并不完全有效：

“Paxos算法以简单的英语呈现，非常简单。” “Paxos算法，用简单的英语表达，非常简单。”

从那时起，Paxos就广为人知，部分原因是谷歌已经成为其胖乎乎的系统的核心部分。如Google的Paxos Made Live中所解释的，很难在工程中正确使用Paxos协议：工程实现对基本协议进行一些更改，其中最重要的可能是多Paxos，它允许请求被链接。共同降低消息的复杂性。

许多读者已经熟悉以下内容。各种互联网公司已经完全定制和推广了paxos算法。有兴趣的读者可以从“Paxos共识算法研究进展”和“拜占庭系统技术研究评测”中获得评测。总体看法。以下是Paxos派生文章的简要回顾：

1. Paxos变得简单：以全新的方式呈现Paxos，简短且易于阅读。
2. Paxos Made Live：来自Google的这篇论文弥合了理论算法和工作系统之间的差距。在实施可能无法实现的Paxos时，需要考虑许多实际问题。如果您想使用Paxos构建系统，您应该首先阅读本文。
3. 便宜的Paxos和Fast Paxos：两篇论文优化了原始协议。
4. 关于交易提交的共识：Lamport和Jim Gray的一篇简短文章表明，2PC是Paxos的简化版本，可以容忍零故障。本文是Paxos的可读介绍。
5. 如何使用共识构建高度可用的系统：Butler Lampson演示了如何将Paxos共识用作更大系统的一部分。

该理论领先于时代，但需要等待项目的检查。在大规模应用互联网之后，Lamport最终在2013年赢得了图灵奖.20世纪80年代分布式系统理论的发展触及了当时仍然难以想象的未来，正如我们在另一个人的前夕黎明。

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

文章“比特币的学术谱系”以这种方式评估比特币：几乎所有比特币的技术组件都起源于20世纪80年代和90年代的学术文献。这并不是要削弱Nakamoto的成就，而是要指出他站在巨人的肩膀上。

比特币已经稳定运行了10年，其机制和原则已经受到其经济影响的欢迎。如果你向区块链从业者询问有关比特币的技术问题，每个人都可以就经济激励的作用和意义以及努力的证据达成一致。

比特币引入了经济激励和工作证明，解决了开放系统中拜占庭将军的问题 – 即使熟悉分布式系统的人也同意这一结论，但Nakamoto在原始白皮书中没有引用任何拜占庭文献。没有使用相关条款。这与他明确提到的关于链时间戳的文献形成鲜明对比，包括工作量证明。他使用一些概念和协议来描述共识机制，并以攻击者的形式考虑问题以及节点如何加入并离开网络。 Nakamoto只在比特币和拜占庭将军的邮件列表（一个思想实验）中说，工作量证明可以解决这个拜占庭式的一般问题。

通过研究比特币的学术谱系，我们可以看到研究人员在各个领域面临的困境：Paxos协议的研究人员没有考虑节点的激励问题;原始的数字货币（包括hashcash，b-money和bit gold）没有考虑一致的算法来解决双花问题。也就是说，节点的激励与数字货币的双花问题之间存在双环困境：节点需要数字货币激励来抑制邪恶;数字货币需要节点达成共识以避免双花。对于这种困境，工作量证明了PoW可能提供了一个桥梁，但仍然存在双循环困境：数字货币作为一种经济机制已经存在，但尚未转变为激励机制;作为反垃圾邮件措施的工作证明（PoW）是由于缺乏激励导致使用动机不足。

这是一个矛盾的尴尬：没有人支持你，除非你成功，但如果没有人支持你，你怎么能成功？

Nakamoto的天才基于强制性工作量证明金钱的逻辑。比特币的共识和激励逻辑是这样的：工作证明就是金钱，鼓励矿工努力提供工作量的证据，然后获得货币;同时，利用经济学原理设定规则，使恶意节点的投入大于利益，如果恶意节点没有力量破坏共识，那就可以解决一般拜占庭问题所不能解决的问题因为一般的反叛而被触及，从而保护了数字货币的双花问题。

基于比特币的PoW一致性算法是最早，最安全可靠的公共链一致性算法。 PoW的共识是系统节点（即矿工）一起工作以根据各自的计算机功率解决复杂但经过验证的SHA256数学问题（即挖矿）。这个问题的最快解决方案将是下一步。块的右侧块和比特币奖励由系统自动生成。从分布式系统的角度来看，PoW一致性算法和类似Paxos的一致性算法之间存在两个主要差异：

1. 竞争性区块权是领导者的选举过程。 Paxos一致性算法，包括PBFT算法的领导者选举，需要节点之间的多个通信。 PoW一致性算法的领导者选举是一个自举过程，竞争块本身。节点不需要相互通信（当然，缺点是时间延迟和资源浪费）。
2. PoW一致性算法参与节点的计算能力竞争过程在没有协调节点的情况下并行执行，并且Paxos一致过程是同步的，并且通常需要协调节点。

简而言之，就机器共识而言，区块链中使用的一些PBFT和Paxos一致性算法，以及L1中的选举，股权证明，随机类，联盟和混合等各种一致性算法，尽管一些较小的联盟链方案可以工作，但与比特币的中心思想相比，人们不得不说倒退。

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

在讨论PoW共识机制和拜占庭将军时，袁勇等人指出，现有文献研究的共识问题可以分为两个分支：算法共识和决策共识。前者致力于研究特定的网络模型和故障模型。在此前提下，如何确保缺乏中心化控制和协调的分布式网络的一致性本质上是“机器共识”;后者更广泛地研究如何在非中心群体决策中做出最佳决策。共识问题，例如关于比特币系统扩展和分叉问题的社区讨论和路由选择，基本上是“人类共识”。两者之间的区别在于，前者是机器之间的确定性共识，主要基于工程复杂性，而后者的特点是复杂的“人在环”系统。确定性共识基于社会复杂性。区块链一致性算法研究应属于算法共识分支的子集，决策共识主要见于分布式人工智能，多智能体等研究领域。

拜占庭式的一般问题是分布式共识的基础，也是两个研究分支的根源。拜占庭一般问题有两个互动一致性，一致性和正确性的条件。由于在大多数情况下，正确性涉及人的主观价值判断，因此难以应用于分布式系统的节点。因此，算法共识采用“降级正确性”，即从“表达的内容是正确的”降级为“正确表达”，这导致区块链的拜占庭共识实际上是机器共识，其本身就是相当于分布式一致性+正确表达式（不篡改消息）。是的，决策共识可以被视为人们的共识，不仅要求一致性，而且要求所有节点都相信“表达的内容是正确的”，因此决策共识不仅要求客观一致性。内容，但也要求它在共识节点之间。主观正确性。可以看出，算法共识处理的是客观的二元共识，即（唯一正确的书）和错误的（所有错误的账户），决策共识处理主观的多值共识，即意见1（和其组），意见2（和其组），···，意见N（及其组），每个节点最终通过组之间的协调和合作过程收敛到一个独特的意见（共识），并且这个过程可能会失败（不收敛）。

三，VDF：引领未来

据英国广播公司中文网站报道，2015年8月1日：塞尔维亚国家彩票彩票过程出现了一个令人惊讶的错误，促使警方介入调查。

在通常的直播电视彩票中，每当彩票用数字摇动球时，该数字将显示在电视屏幕上以确认。在周二（7月28日）的抽奖中，当抽奖震动第27球时，电视屏幕错误地显示第21个。然而，彩票随后震动的球是第21位。电视屏幕比彩票机更准确地预测了彩票号码，这引发了猜测并促使塞尔维亚国家彩票官员辞职。塞尔维亚警方已对事件进行了调查，并没收了彩票机和相关的计算机软件。

彩票引起了欺诈性的猜测。游戏或游戏中的博彩取决于人们的工艺。计算机中的随机数取决于安全的随机源。这些是生活中的常见例子。从公众涨势，国家彩票到抽奖，一个基本要求是如何说服别人你不是在作弊？基本要求是如何生成安全随机数。

当前的高可靠性随机数生成方案是美国国家标准与技术研究院的NIST随机信标和random.org（两者都是中心化随机源）。 NIST使用光子和量子力学定律（双光子纠缠）来生成随机数，random.org使用大气噪声作为熵的来源。这些随机数也称为“真”随机数。

在数字世界中，由比特币表示的区块链也被用作随机源（去中心化的随机源）。这些随机源具有足够的随机性（70+位，更严格地说，最小熵），但区块链是开放网络。当对应于随机数的兴趣足够大时，区块链将受到块的影响。阻止攻击和贿赂攻击。

为了解决块源随机源的攻击问题，引入了延迟函数。也就是说，通过引入延迟功能，该功能需要1小时（例如）来计算结果，因此延迟功能的计算结果只能在1小时后获得（使用区块链上的随机源）作为参数）。这使得区块链成为一种安全的去中心化随机源。

可验证延迟函数VDF的概念最初是由斯坦福大学计算机科学与电子工程教授Dan Boneh和计算机安全实验室的联合主任在加密货币 2018出版的“可验证延迟函数”一文中提出的。虽然有以前做了很多研究，包括序列工作的证明，懒惰：慢时间等等，VDF引起了学术界和业界的极大兴趣。在VDF论文发表后的10天内，发布了两份VDF施工文件，下个月Dan Boneh对这两种结构进行了全面审查。到目前为止，根据时间表对VDF建设的主要研究如下。

2019-Döttling，Garg，Malavolta，Vasudevan严格可验证的延迟功能

2019-Ephraim，Freitag，Komargodski，通过“连续可验证的延迟函数”

2019-De Feo，Masson，Petit，“Sanso Verifiable延迟函数来自超奇异同源和配对”

2018年（7月30日）-Boneh，Bünz，Fisch“对两个可验证延迟函数的调查”

2018年（6月22日）-Pietrzak“简单可验证延迟函数”

2018年（6月20日）-Wesolowski高效可验证延迟功能

2018年（6月12日）-Boneh，Bonneau，Bünz，Fisch可验证延迟功能

2015-Lenstra，Wesolowski“随机动物园：懒惰，独角兽和Trx”

在行业中，VDF感兴趣的区块链项目是：

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

协议实验室和以太坊基金会共同资助了50/50项目，以建立两个与VDF相关的项目：supra national和ligero。

VDF模型非常简单且非常重要。

VDF是可验证延迟功能的缩写。功能表示VDF是一个为每个输入提供唯一输出的功能。延迟可以由时间T（壁时间）表示，其在时间T计算，但不能通过小于时间T的并联加速度来计算。可验证要求延迟函数的输出非常容易验证。

壁挂时间，也称为真实世界时间或挂钟时间，是由计时器（例如时钟或挂钟）确定的经过时间。 （“墙”这个词最初是以对挂钟的引用命名的。）

对于VDF的功能，即“对并行加速的延迟”和“可验证的结果”，VDF必须包含用于计算结果的算法和用于验证结果的算法。同时，这种加密货币工具通常包括设置阶段以确定稍后需要使用的参数。因此，VDF被描述为三种算法的三重（Setup，Eval，Verify）。

每种算法定义如下：

1. 设置（λ，T）→pp =（ek，vk）接受安全参数λ和时间参数T，以生成每个人都能看到的公共参数。公共参数包含用于计算的参数ek和用于验证的参数vk。
2. Eval（ek，x）→（y，π）接受计算参数ek和输入x∈X，并计算输出y∈Y和证明π。
3. 验证（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 does not resist parallel computing acceleration and VDF resistance. In fact, PoW does not resist parallel computing acceleration is in line with Nakamoto's "one CPU, one vote" idea, and the nature of anti-parallel acceleration will only run counter to this purpose. VDF has almost no advantage over CPU-savvy calculators and single-CPU calculators.
2. For a fixed difficulty setting d, PoW can have many legal solutions, which is also a prerequisite for ensuring that the PoW consensus network has stable throughput and stimulating miners to compete. For a given input x, the VDF has a unique output (which is why it is called a function).

VDF has a wide range of applications, including enhancing the security of publicly verifiable random numbers, solving Nothing-at-stake Attack, and alleviating Long-range Attack. These can be found in Qiu Feijun's article "Understanding Verifiable Delay Function VDF". 。 This paper focuses on the application of VDF ideas in the expectation of consensus, proof of replication and proof of space and time.

The proof of copying is to prove that a unique copy of the data is stored on a server, which is different from the proof of storage. Ben Fisch pointed out in BPASE '18 that the Impossibility of Strongest Replication Definition cannot be achieved through cryptography, and then by introducing the concept of “rational enemies” and designing incentives to make the evil gains very low, and arbitrary The cost of switching to a “good” strategy at all times is very low, so there is no motivation to do evil. One idea of ​​copy proof is to use VDF's time-asymmetric coding scheme (that is, the coding is slow, but the decoding is fast). As shown in the following figure, if the server deletes the data, it will not be able to quickly respond to the challenge.

The basic idea of ​​space-time proof is to divide the space-time proof into multiple EPOCHS periods, each period must accept the challenge from a random beacon that outputs a challenge at regular intervals (for Filecoin, the blockchain acts as a random beacon ). The process of proof of time and space generation is as shown in the pseudo code below.

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

The verification process of space-time proof is shown in the following pseudo code.

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

VDF hardware can speed up the operation of VDF. In each "EPOCHS", a small fraction of the acceleration gain will result in a large time difference between the "total verification time" between the fastest and slowest verifiers. Filecoin refers to the difference between the fastest proof time and the average proof as the "VDF acceleration gap" and defines the VDF acceleration gap as (0-1). Since each cycle of space-time certification must accept challenges from random beacons, faster verifiers can accelerate the “VDF acceleration gap” during each EPOCHS, but not the “VDF acceleration gap” of the entire space-time proof. In other words, the fastest verifier cannot accumulate revenue during each EPOCHS because they have to wait for new challenges from random beacons.

The consensus agreement is a probabilistic Byzantine fault-tolerant agreement. At a high level, it works by conducting a leader node election every round, and the mathematical expectation of a leader node to submit a block number is 1. Based on the proof of time and space, it can be proved that the miner has X% of the total resources of the system, so the mathematical expectation of the miners with X% resources to dig up the number of blocks in any block cycle is X%. The X% resource is then divided into X shares, 1% each, for x1,…, xn different values. Then perform an independent random test on each X:

1. Ri = HASH(xi) (0,N)
2. The miner found R=Min(R1,…,Rn)

Then, an unpredictable challenge random number is obtained by x and the previous block, and the VDF calculation is performed by using the random number and the delay time T proportional to R as parameters.

Through examples of proof of replication, proof of time and space, and expectations of consensus, VDF demonstrates a fundamental, viable future of resource-based proof and latency-based consensus protocols, which will lay the ground for secure random numbers and more provable applications and algorithms.基金, as Boneh concluded in his groundbreaking paper "Verifiable Delay Functions":

Given its many interesting applications, we hope that this work will stimulate the new practical application of VDF and continue to study its theoretical construction. We still lack a theoretically optimal VDF, which consists of a simple intrinsic sequence function that requires a lower degree of parallelism to compute, but the validation is very fast (eg, logarithm). These requirements have spurred the exploration of new problems that have not traditionally been used in cryptography. Ideally, we hope that VDF is also post-quantum safe.

Fourth, summary

The Byzantine General and the Paxos algorithm have been proposed for nearly 40 years, and the real large-scale application has been the past 10 years. Bitcoin has been in existence for 10 years since its introduction in 2008, and its consensus mechanism PoW algorithm has been running stably for more than 10 years. The VDF function mechanism was proposed on June 12, 2018. It is just one year until June 12, 2018. From Paxos to PoW to VDF, the theoretical development of distributed systems has drawn a beautiful golden line. Behind this golden line is the basic problem of computer systems: time and space. When Newton thought that he understood all of this, Einstein smiled; when Einstein thought that he understood all of this, Heisenberg and Schrödinger laughed; when humans began to think about time and space, God smiled.

The introduction of VDF is a major technological breakthrough in the field of application of cryptography, distributed systems and blockchains, laying the groundwork for the feasibility of blockchain resource consensus, space-time certification, and leader election. Not only that, but as a kind of delay service and random beacon service, it can also be applied to other fields. Compared to Paxos, VDF retains the characteristics of the blockchain open system and supports Byzantine fault tolerance. Compared with PoW, VDF inherits its "workload" effect and resolves the power of electricity. So, the past decade has been a decade of paxos and pow, and the next decade will be a decade of VDF. Therefore, I propose to set up the VDF Chinese community to build a hardware and software ecosystem, research together, and explore new application areas.

VDF Chinese Community: https://github.com/taoshengshi/research/blob/master/vdf.md

References in this article:

Progress in Research on Paxos Consensus-Based Algorithms

评测 of the Byzantine System Technology Research

"CAP Theory and Distributed System Design"

"Overview of the Consensus Mechanism of Encrypted Digital Currency System"

Analysis and Optimization of Game Dilemma in PoW Consensus Algorithm

"The Academic Pedigree of Bitcoin"

"VDF is not a proof of workload"

"I understand the verifiable delay function VDF"

"Development Status and Prospects of区块链 Consensus Algorithm"

The Part-Time Parliament

Proof of Replication using Depth Robust Graphs – BPASE '18》

"Verifiable Delay Functions – 加密货币2018"

Time is fantasy

" For us who believe in physics, no matter how long the time is, the difference between the past, the present and the future is only a continual illusion. – Albert Einstein "

“The most valuable startups of the past 10 years have not raised funds, no employees, no caps, so that anyone can invest.” — Both Bitcoin and Uber were launched around 2009. Today, Bitcoin's market capitalization is about $138 billion; Uber's valuation is about $75 billion. Where will they go from here?

Source of this article: Bu Tian Stone (WeChat public number: butianys)

Author: tshi