形式化验证 Gasper 共识机制的终局性

2020-07-21 10:19 栏目:经验之谈 来源:网络整理 查看()

Gasper是一个抽象的权利证明协议层,由信标链协议(即将到来的以太网2.0网络的底层协议)实现。Gasper的关键部分是一套终结机制,用来保证事务的持久性和系统的不间断运行不会被攻击破坏。

我们很高兴地宣布,运行时验证(Runtime Verification)和以太网基金会(Ethereum Foundation)之间长期合作的另一个里程碑是取得了圆满成功:我们开发了一个模拟和验证信标链协议的正式框架,并成功地正式证明了其正确性);加斯珀的终结;此外,我们还使用这些结果来证明信标链的Gasper抽象实现也具有这些属性。模型和证明脚本都可以在这里找到。

在本文中,我们将介绍这一成果的第一部分:验证Gasper的属性。那么,什么是加斯伯?如何对其属性进行正式验证?这种形式验证的意义是什么?

廉价香烟

信标链协议是一套新的权限认证协议,是未来重大升级的以太网2.0的核心。在信标链协议中,所有参与节点(或“验证者”)在系统中都有存款(以ETH的形式)。验证者验证该块的有效性,并通过向网络提交“见证消息”来对其多个属性进行投票。信标链协议本身包含各种工具,帮助验证者就区块链的最新状态达成共识。

Gasper对信标链协议中的终结小工具提出了一套抽象但准确的描述,并定义了分叉选择规则。终结性工具用于确定哪些块应该被参与者确认和不可改变,分叉选择规则用于确定当链产生分叉时哪个分叉是主链。最后定稿Gasper概括了起源于《Casper Friendly Finality Gadget (Casper FFG)》论文的概念,并使“最终性”获得了更一般的形式。

合理化和定稿(理由和定稿)

终结性的概念仅与“检查点块”(也称为“纪元边界块”,即位于纪元开始处的块)相关。见证消息的一部分被称为“理性投票”,验证者在理性投票中将源检查点块与后面的目标检查点块相关联,这直观地表明发起见证消息的验证者认为“我们可以从源检查点的状态移动到目标检查点的状态。”事实上,合理的投票表明:(1)发起投票的验证者;(2)源检查点及其对正高度;(3)目标检查点及其对正高度。

当且仅当满足以下条件:(1)源检查点B0已被合理化;(2)大多数人(即至少三分之二的验证者)也投票支持B0-B1源-目标对;然后目标检查点B1通过源检查点B0合理化。

当且仅当大多数验证器将B0与其K代后代检查点Bk相关联时,B0获得K阶终结性(k 0),并且B0和Bk之间的所有检查点被终结。请注意,创新板块本身被认为是理性的和最终的。下图说明了Gasper中的合理化和最终化概念。

形式化验证 Gasper 共识机制的终局性

惩罚条件(斜线条件)

如果验证者试图偏离协议的要求并提交矛盾的选票,验证者将受到惩罚:他的大部分保证金将被扣除。Gasper定义了两个条件(也称为惩罚条件)来定义矛盾投票的含义:

1.双重投票:验证者发出两个完全不同的投票,但是两个投票的目标高度是相同的。

2.包围投票:与验证者发出的一张选票相关联的两个检查点在验证者发出的另一张选票的两个检查点的高度范围内。

形式化验证 Gasper 共识机制的终局性

发起双重投票的验证者被认为违反了第一个惩罚条件;发起轮投票的验证者违反了第二个惩罚条件。在这两种情况下,违反规则的验证者将被扣除一大笔押金。

准确性属性(正确性属性)

像其他拜占庭容错(BFT)协议一样,Gasper协议的一个关键潜在假设是大多数验证者(超过2/3,由裕量定义)是诚实的,并且将遵守协议的要求。在这个假设下,Gasper有两个基本属性:

可问责的安全性:除非至少三分之一的验证者(就保证金金额而言)被没收,否则属于不同分支的两个区块不会被最终确定;

似是而非的活跃度:不管区块链过去发生了什么,该地块的最终确定过程永远不会陷入僵局。

此外,在验证者集将动态改变的环境中(因为验证者将离开网络,新的验证者将加入,并且活动的验证者集可能改变),第三个属性量化了当有人违反协议规则时可以被没收的存款量:

可砍价的界限:只要协议外的条件可以用来控制验证者的激活和退出参数条件,就可以证明可以没收的保证金金额有一个下限(当证券被破坏时)。

动态验证者集合(即,通过信标链协议实现)引入了另一个具有挑战性的问题:系统不再能够可靠地惩罚恶意验证者,因为他们可能在犯罪之后并且在存款被实际没收之前离开网络。惩罚下限的属性使得可以调整主动验证者集的可变范围并保持最低的责任。

验证Gasper的终结性

Gasper旨在为终结性提供一个数学和精确的描述,可以用来正式证明其正确性;这种正确性也是证明信标链协议安全性的关键。以太网平台越来越多地被用作大型金融交易系统的股票价格,这凸显了安全保障的前所未有的重要性。

在以太网基金会的合作下,我们利用Coq证明辅助工具,在动态验证集的一般条件下,形式化了Gasper的终结机制。在此条件下,我们指出并证明了Gasper的三个关键属性:责任安全性、可能性活动和惩罚下限;所有的证明都使用相同的Coq模型。

协议的演绎论证给了我们对相关权利要求的正确性和安全性的极大信心,因为演绎论证保证没有未指明的假设和无效的演绎推理步骤。它还澄清了支持论点所需的所有假设。形式化过程还可以反馈协议的描述,使协议的描述更加准确和完整。

这里我们只对这一成就做一个简单的描述。可以看到完整的细节:

1.项目技术报告

2.项目的Github代码库

建模和验证方法

第一步是开发一个协议模型,这样我们就可以表达我们想要正式指出和证明的所有关键属性。这个模型是基于我们之前验证卡斯珀FFG的安全性和活动性的工作(之前的模型已经定义了早期版本的加斯珀终结机制)。

该模型有三个主要结构模块:

验证器和quorums。验证器被抽象地表示为一个有限类型的成员(成员的数量是有限的并且可以被枚举),并且被写成验证器: finType。每个验证者都有押金;这一事实被建模为一个无法解释的函数,stack : { fmap Validator-NAT },它存储验证器与其存款金额(一个自然数)之间的映射。此外,给定一个验证者集合,其权重wt被定义为该集合中所有验证者余量的总和:

形式化验证 Gasper 共识机制的终局性

\sum是sum运算符;木桩。[st_fun v]给出对应于验证者V的裕量(st_fun假设每个验证者在系统中必须有裕量)。

wt函数的几个属性是从它的定义中导出的。例如,空验证器集的权重必须是0,两个不相交集的组合的权重是它们各自权重的总和。当涉及到对惩罚下限属性中的权重进行推理时,这些属性就派上了用场。

此外,因为我们想要模拟动态验证器集,也就是说,活动验证器集可能随着块而改变,所以我们声明了一个抽象(有限)映射vset : { fmap hash-{ set validator } },它在块处给出活动验证器集。现在,使用vset和wt,我们可以定义什么是绝对多数集:

形式化验证 Gasper 共识机制的终局性

在某个块,如果活动验证集的子集的权重超过整个集的权重的2/3,则该子集是绝对多数集。

积木树。我们使用有限类型的块散列来模拟具有:finType的块。此外,创世纪是用来代表创作块。我们使用h1 ~ h2等符号来表示块的父子关系(h1是h2的父级),以便模拟检查点块树。

接下来,我们用h1 ~* h2来定义祖先关系,h1是h2的祖先,h2是h1的后代(h1和h2可以是同一个块)。至于祖先关系的属性,例如,祖先的祖先也是祖先,这类似于父子关系的属性。

全球状况。sTAte可以表示为由合理投票组成的有限集合,投票形式为(v,s,t,s_h,t_h),其中v是发起投票的验证者,s和t是ta支持的源块和目标块,s_h和t_h是它们的见证高度。某个投票是否已经启动可以通过布尔成员断言来确定:

形式化验证 Gasper 共识机制的终局性

示例规范

基于这些定义及其相应的属性,我们定义了模型中的所有其他结构和属性,包括没收条件、法定交叉属性、合理化和终结性。例如,在违反协议的情况下,没收某个组的属性可以通过使用以下抽象成员约束来定义:

形式化验证 Gasper 共识机制的终局性

该命题指出,没收一个组意味着在一些块bL和bR中有两个绝对多数组vL和vR,并且这两个组的交集是被没收的验证者的完整集合(谁发起双重投票或轮投票)。请注意,在主动验证集总是固定的特殊条件下,这些绝对多数集的交集的权重至少是所有余量的1/3。

另一个例子是最终分歧的定义(即违反安全的情况):

形式化验证 Gasper 共识机制的终局性

这个命题指出两个冲突的块b1和b2已经被最终确定(因为b1和b2不是彼此的祖先)。这两个模块可以在任何合理的高度通过任何长链来完成。

这些定义和结果集用来指出和证明三个定理:责任安全性、可能性活动和惩罚下限。为了清晰起见,我们还用以下公式重新定义了责任安全定理的表达式:

形式化验证 Gasper 共识机制的终局性

这个定义很简单,只是说:如果安全性被破坏(有任何最终的分歧),它一定意味着某一组验证者将被没收。这一证明将Gasper给出的非正式论证机械化了,并说明了为什么最终分歧意味着两个绝对多数群体必须违反了没收条件之一,因此它们的交集可以被没收。

我们的技术报告描述了形式化过程和这些属性的证明,而我们的项目代码库提供了完整的细节。继续

在本文中,我们解释了运行时验证和以太网基金会之间的合作成果的第一部分。第一部分是形式化Gasper,并证明其三个关键属性:责任安全性、可能性活动和惩罚下限。我们成果的第二部分(本文中未涉及)是展示如何将这些结果替换成更精细的模型(用K框架编写),并给出信标链状态转换函数的抽象版本。我们将在稍后的另一篇文章中展示这一成就。

这一里程碑的完成也意味着我们朝着这一合作的最终目标迈出了重要的一步(正式证明信标链协议满足所有三个关键属性,并且可以清楚地声明非常接近协议细节的抽象版本所需的所有假设)。

我们期待着在这项工作中继续与埃瑟伦基金会合作。在这次接触中,我们非常感谢来自以太博物馆基金会的几位专家:丹尼瑞安、卡尔比凯岑、马丁伦德法尔、严章和阿迪雅阿斯高恩卡。

微信二维码
售前客服二维码

文章均源于网络收集编辑侵删

提示:币友交流QQ/WX群请联系客服加入!

郑重申明:资讯文章为网络收集整理,官方公告以外的资讯内容与本站无关!
虚拟币开发,虚拟币交易平台开发,山寨币交易平台开发 Keywords: 虚拟币开发 虚拟币交易平台开发 山寨币交易平台开发