摘要
点对点通信网络最成功的应用之一是在区块链协议上下文中，用中本聪自己的话说，这种协议依赖于“信息易于传播和难以抑制的特性”。在过去的十年中，人们投入了大量的精力来分析这些协议的安全性，而众所周知的最长链中本式共识的安全性论证总是使用这一原则的理想化。不幸的是，区块链协议所使用的peer-topeer -绯闻风格网络的现实实现依赖于许多特别的攻击缓解策略，这在区块链的正式安全参数中假设的理想通信层与真实世界之间留下了明显的差距，在现实世界中已经展示了大量的攻击。
在这项工作中，我们通过为区块链协议提出一个拜占庭弹性网络层来弥补这一差距。我们第一次在区块链安全模型的背景下量化了网络层攻击的问题，并开发了一种阻止资源受限对手的设计。重要的是，我们将重点放在权益证明设置上，因为它容易受到拒绝服务(DoS)攻击，这种攻击源于众所周知的缺陷(与工作量证明设置相比)，即无利害关系。
提出了一种拜占庭弹性八卦协议，并在通用合成框架下对其进行了分析。为了证明其安全性，我们给出了关于随机图的展开子性质的新结果。重要的是，我们的八卦协议可以基于任何给定的双边功能，该功能确定了网络层中两个“相邻”对等体之间的期望交互，并演示了如何使用应用程序层信息使网络层对攻击具有弹性。尽管表面上是圆形的，我们演示了如何在给出八卦网络功能的情况下证明一个nakamoto风格的最长链协议的安全性，因此，我们建设性地演示了如何在仅给出基本的点对点网络、大多数诚实的利害关系和可验证的随机函数的情况下，跨协议层获得可证明的安全性。
1、介绍
1.1 八卦协议和拜占庭攻击者
流言协议。八卦协议[12,18]提供了一种将信息分发给大量当事人的有效机制。这类算法的关键特征是它们的点对点操作，这种操作负载平衡了信息传播的工作量，使单个节点在为整个网络范围的消息传递做出贡献时只投入了很少的工作量。
作为多方密码学的通信基础设施，八卦协议最近在区块链协议的背景下得到了广泛的应用，特别是随着比特币区块链[26]的引入。除此之外，区块链参与者使用八卦协议来传播新发现的区块。
用中本的话说，区块链协议依赖于“信息容易传播、难以抑制的特性”，强调了八卦作为底层通信层的相关性。八卦协议的“安全性”。将八卦协议部署为区块链协议的通信层为其设计增加了一个至关重要的新维度:“安全性”。
至少，区块链底层的流言协议必须处理这样一个事实：每个对等体的资源（如网络带宽、计算时间和空间）是有限的，用尽这些资源将导致拒绝服务（DoS）攻击。因此，前面提到的使每个对等体的复杂性保持较小（在总参与者的数量中为亚线性，最好为常数）的考虑，不仅与效率有关，而且对安全也至关重要。
由于这个原因，目前在实践中使用的八卦协议包含了一系列(通常是特别的)措施来保护信息传播免受DoS攻击。特别是在区块链协议的设置中，这种DoS缓解的最显著特征是对手是有资源限制的(例如，在比特币协议的上下文中具有有限的哈希能力，或在利益证明协议的上下文中具有有限的哈希能力)，而对等体可以利用这一点来管理网络范围内的消息传播。技术包括拒绝以前看到的工作量证明消息和跳过不会导致本地状态更新的内容下载(例如，当块报头指示不能基于客户机的本地状态采用块内容时，跳过下载块内容)。
应该强调的是，这些措施远非完美，正如已经描述的一些攻击所证明的那样，包括eclipse攻击[17]和路由攻击[2]。此外，权益证明设置带来了额外的困难，因为可能重用密钥来发出许多相互冲突的消息[27]，而且权益证明验证工作需要整个涉众集合，这与只需当前难度级别的工作证明形成鲜明对比。
然而，安全问题远远超出了每个对等点的复杂性。最关键的是，用于闲聊的覆盖层的设计、设置和维护必须能够抵抗拜占庭式攻击者——这种攻击者会使参与者主动、恶意地偏离规定的协议，从而在网络中指挥大量对等体。尽管有以上所有的缺点，在实践中，区块链协议部署的网络层的信息传播保证通常被假定为足以使高级协议保持其安全性和正确性。
在理论方面，区块链共识协议——无论是中本式的(例如，[11,26])，还是受拜占庭容错计算的启发(例如，[7])，基于工作量证明(PoW)或利益证明(PoS)——都非常依赖于协议消息(块、投票等)的可靠和及时传递，以实现活跃性，而且许多协议也是安全的。然而，尽管所有这些协议的共识层得到了相当多的关注，其中一些协议实现了可证明的安全性，以对抗拜占庭攻击者，网络层的设计和安全性通常是最好的事后考虑。
具体地说，所有先前的PoS协议的正式安全分析(例如，[7,10,11])都使用(过度)理想化的消息传递抽象，这些抽象在本质上承诺诚实的消息在合理的延迟窗口内不受干扰地分发给所有诚实的方，而忽略了这些抽象必须在现实世界中实现的事实。
更广泛地说，令人惊讶的是，很少有发表的工作考虑将拜占庭弹性扩展到区块链或一般的八卦协议的通信层的问题。
上述情况突出了所采取的方法在理论和实践上的严重缺陷，也表明两者之间存在着重大差距。考虑到八卦是任何无许可分布式账本协议协议栈的一个关键部分，缺乏对其属性的彻底的、正式的安全处理是理解这些协议安全性的一个关键缺陷。这是本文的主要研究动机。
1.2我们的研究结果
这项工作采用了一种系统的、有原则的方法来缓解上述问题，并为PoS区块链协议环境下的拜占庭弹性八卦提供了一种新颖的设计。结果在通用可组合性框架[5]中给出。
区块链的拜占庭弹性网络层。这项工作的第一个主要贡献是在PoS区块链共识的参与者之间全球“同步链”的协议。该协议被设计成在一个标准的、类似互联网的网络上工作，具有(有限制延迟的)消息传递。
至关重要的是，网络层的安全是基于与共识层相同的假设，即系统中的大部分股份由诚实的各方控制。乍一看，这似乎是循环的，因为网络层的正确运行取决于对股权分配的一致意见。打破这种“循环”的方法如下:通常，中本式PoS区块链无论如何都将共识协议的执行拆分为epoch，并在epoch i - 1结束时使用股权分布SDi−1作为epoch i +1的共识基础(假设epoch期间的股权漂移有界)。对于网络层也可以采用相同的方法，即SDi−1支持网络层在epoch i + 1中的执行。具体来说，在新协议中，各方使用可验证随机函数(VRF)来基于SDi−1创建一个利益加权随机图覆盖，其中各方的程度在参与者数量中是恒定的。vrf的使用允许各方拒绝来自不应该在其邻居集中的参与者的连接请求。3由于网络协议中的节点度是恒定的，(自适应的)攻击者很容易通过破坏组成该利害关系的所有邻居来隔离利害关系的(有界的)部分。为此，图中的边有一个过期时间，在这个时间点上对替换点进行采样。除了帮助各方从日食中恢复，这也允许覆盖逐渐适应不断变化的股权分配。
现在简单地在上述覆盖层上执行普通的区块八卦似乎很诱人。然而，这种方法似乎不适合（至少）中本聪区块链。例如，要求各方保留所有收到的区块是不切实际和不安全的设计，因为其中许多区块在PoS设置中可能是对抗性的（攻击者原则上可以随心所欲地生成许多区块，特别是作为槽头）。因此，在区块流言中，一方应该删除区块，除非它们扩展了其当前的本地链。然而，在分叉事件中，一方可能需要先前删除的区块，而这些区块的闲话已经 “结束”。" 如果一方错过了区块，例如由于日蚀，类似的问题也适用。一般来说，某一方需要哪些区块来与系统同步，在很大程度上取决于该方的本地状态。
因此，无状态解决方案，即邻居不共享状态的解决方案，似乎不是很适合，也不会产生dos弹性和可伸缩的区块链协议。
一种更合适的方法是让每一对邻居运行双边链同步(链同步)协议，这允许它们互相通知各自的本地首选链。当一方在其中一个chainsync实例中发现了一个更好的链，或者当它产生了一个更好的链时，它会通知所有当前的chainsync实例该新链。
这项工作将这种双边链同步抽象为Fbilateral功能。这种协议的实际实现超出了本工作的范围，与本工作无关。需要注意的是，链同步是有状态的，它的实例需要时间在现实世界中建立(建立连接，初始同步块，等等)。因此，双边链同步旨在在双方之间运行较长(尽管是有限的)时间。Fbilateral捕获了这些事实，因为初始同步延迟δinit，它可能比设置了链同步实例后发生的延迟δsync大得多。
最后，请注意，特别是在区块链上下文中(但也通常如此)，必须防止攻击者中断任何特定消息的传播;否则，攻击者可以，例如，阻止诚实的链更新通过网络传播。不幸的是，在高效的八卦协议中，节点的度数是恒定的，(自适应的)攻击者可以简单地破坏block leader的所有邻居，从而停止传播。
因此，不可避免地要考虑攻击者的破坏请求在一定时间后才生效的模型。
理想的全局链同步功能。上述协议的安全保证由Fsync功能捕获，这是本工作的第二个主要贡献。与之前工作中假设的网络功能类似，Fsync在一定时间范围内提供全局链“传播”(sync)。然而，由于Fsync是实现的而不是假设的，因此有几个重要的区别。•Fsync允许攻击者“遮蔽”各方，并将其排除在提供的担保之外，只要遮蔽的股权的比例不超过一定的界限。注意，允许对手是“移动的”w.r.t.，其中的一方被遮蔽，也就是说，每一方都可能在协议执行期间的某个时刻被遮蔽。注意，在Fsync中有一个eclipse delay ξecl≥∆sync。这确保了攻击者不能停止特定链的传播。
•由于使用了链同步，Fsync的保证比之前工作中假设的网络功能提供的保证略弱:与通过∆中的网络“传播”的特定链C不同，Fsync还可以交付不同的链C’，这些链C并不比C差(即长度相等或更长)。
安全证明。为了证明新的网络协议安全地实现了理想的功能Fsync，本文在扩展图上得到了一个新的结果:考虑由协议各方组成的利益加权随机图。然后，即使去掉图中的所有损坏节点，留下诚实赌注的某个分数α，仍然存在一个诚实当事人的子图，即骨干图，它至少对应于总赌注的(α−β)-分数，对于某个β，这个骨干图是一个扩展图(具有压倒性的概率)。最重要的是，即使攻击者在完全了解整个图的情况下选择删除哪些节点，结果也会保持不变。扩展器的特性保证了主干中的直径很小，因此可以在主干中进行及时的链“传播”。
完全拜占庭弹性PoS:作为最后的贡献，这项工作演示了如何在利益证明协议的上下文中利用同步功能。具体来说，[11]用于说明结果。首先，要注意最初的分析是不充分的:尽管[11]的网络模型允许拜占庭式对手控制少数股份的事实，Fsync允许“移动”掩盖战略，这将耗尽对[11]对手的直接削减的对抗预算。
为了规避这个问题，提出了一种改进的分析，表明自适应重叠不会干扰[11]的forkabble -string分析，可以恢复该分析，以证明即使面对利用Fsync对抗接口的增强功能的对手，协议仍然是安全的。这就产生了在对抗性环境下对[11]的一种新的分析，在这种环境下，除了党派腐败，还允许某种程度的消息压制。
1.3相关工作
在分布式系统环境中使用八卦或流行算法在[13]中被提出，并在网络系统[20]和理论角度[19]中进行了详细的探索。
有界度网络中拜占庭容错的研究始于[14]，并在[29]中进一步细化，在[29]中表明，如果对手分别被O(n/log n)或O(n)所界，则存在有利于广播的有界度图。
就总通信而言，已知拜占庭广播的通信复杂度为Ω(n2)，在腐败模型中假设某种类型的延迟是打破次线性[1]通信复杂度障碍的必要条件。
在区块链的点对点网络环境中，可以使用点对点网络组织中的“结构化”方法来进一步降低通信复杂性，但代价是自适应安全[28]。
从多方计算的角度来看，我们的协议表现出一种 “通信定位性”，这在一般安全多方计算的背景下也被更广泛地研究过[6]。我们还注意到，信息压制作为一种增强的对抗能力，也在一般安全MPC设置中的 "遗漏破坏 "的背景下被研究过[30]。
最后，与我们的工作同时且独立地，[24,25]在一组参与者中研究了相关的无状态洪水问题，部分也是受到区块链设置的激励。他们的泛洪协议让对等体连接到一个有限大小的、随机选择的邻域，用于每次消息传输。这可以看作是为每条消息创建一个单独的随机图。
然而，如上所述，无状态泛洪在实践中不适用于区块链协议。此外，他们的协议没有使用任何机制对对手进行资源绑定(例如，作为VRF)，因此没有任何缓解措施可以防止诚实的一方被对手的消息淹没。
2、初步和标记
加州大学的安全。在通用可组合性(UC)框架[5]中描述并证明了协议的安全性。在UC中，通过比较协议的实际执行和用理想功能替换协议的理想执行来捕获特定协议的安全性。粗略地说，协议π安全地实现了功能F，如果对于每个现实世界的攻击者a攻击π，存在一个理想世界的模拟器S攻击F，这样，真实和理想的实验对所有环境变得不可区分Z.5A协议(在现实世界中)本身可能调用所谓的混合功能。这些混合功能既可以用于模型假设(例如下面的Fnet)，也可以由协议本身实现。UC框架是指当混合协议被实现混合协议的协议替换时，保证协议的安全性。
圆形结构。所有功能/协议都以轮(不是显式的)方式进行，并假定能够访问当前时间(表示为t)。通常，轮结构是这样的:各方首先使用fetch类型的命令检索信息，然后使用send/set类型的命令分发信息。
攻击者和损坏延迟。被考虑的攻击者是多项式有界的，可以破坏各方，从而了解其内部状态，使其任意偏离规定的协议。攻击者是自适应的，也就是说，它可以在协议执行过程中根据观察到的所有信息来选择要破坏的对象。但是，存在ξcorr的破坏延迟，即攻击者发出的破坏请求只有在ξcorr轮的延迟后才生效。
底层网络。这项工作考虑使用所谓中继的P方，通过其IP地址IP进行标识。让实际的节点(持有关键材料)通过中继建立防火墙是常见的做法，作为防御入侵攻击的第一道防线
中转站之间的通信是由功能Fnet（参见图1）来模拟的，它捕获了一个简单的、类似互联网的网络。各方可以为他们的中继站获得（唯一的）IP地址。Fnet保证了任何两个中继之间的有界延迟的信息传输。攻击者可以看到所有发送的消息，并可以代表被破坏的一方所拥有的任何中继IP发送消息；然而，它不允许干扰诚实的中继之间的消息传输（除了诱发有界延迟）。
主索引。主索引MI由以下部分组成:•网络目录ND，它由元组(P, IP,v)组成，其中P是一方ID, IP是IP地址，v是VRF公钥(见下文);•股权分布SD，由元组(P， α)组成，其中α∈(0,1]表示P的股权比例;•一个种子值R。
如果(A)在ND和SD中出现相同的一方，且每一方最多出现一次，(b)值IP和v在ND中只出现一次，©值α在SD中的和为1，则主索引有效。本工作中出现的所有主索引默认都是有效的。
注意，上文定义的MI格式限制双方只能有一个IP地址。这种选择是为了简单;主索引以及所有协议和功能的定义可以很容易地调整，以允许每一方有多个IP地址，因此建模的事实是，在实践中，各方通常有多个中继。
参数说明:δnet:最大延时。
变量:该功能跟踪以下变量，初始化为以下值:array IPs[P]:=∅:P方拥有的IPs集合;数组M[mid]:消息记录(IP, IP '， t, M)，根据消息id (mid)进行索引。
IP地址:当(getIP)来自P时:输出(getIP, P)到S，并向S请求一个唯一的地址IP。添加IP到IP [P]，输出(getIP, IP)到P。
恶意IP注册:on (regIP, IP) from S:如果IP唯一，则添加到IPs[S]中。
消息发送:当(send, IP, IP’，m) from P with IP∈IPs[P]:选择一个唯一的mid并存储m [mid]:= (IP, IP’，T, m)。输出(send, mid, IP, IP’，m)到S。
恶意消息发送:当(send, IP, IP’，m)来自S，其中IP∈IPs[S]或IP∈IPs[P]已损坏的P:选择一个唯一的中间并存储m [mid]:= (IP, IP’，∞，m)。输出(send, mid)到S。
读取:当(fetch, IP) from P with IP∈IPs[P]:(1)向S输出(fetch, P, IP)并向S请求一组M的mid。
(2)设M’为t−t≥δnet的记录(·，IP, t，·)对应的mid集。
(3)让￣M:= M[M∪M ']并设置M[M∪M ']:=⊥。
(4)输出(fetch，￣M’)到P，其中￣M’是每个元组中删除了时间戳的集￣M。
可验证的随机函数。可验证的随机函数（VRF）是一种加密基元，它允许一方P创建由秘密评估密钥和公共验证密钥组成的密钥对，这样。(a) 通过秘密密钥，P可以在任何输入x上评估VRF，得到一个看起来很随机的输出y和一个证明π；(b) 给定P的公开密钥，任何人都能够使用π验证y确实是对应于x的输出。重要的是，即使是一个恶意的P也不能在任何特定的输入x上偏袒VRF的输出（对于任何固定的公开密钥）。
变量:该功能跟踪以下变量，初始化为以下值:(1)一个数组键[P]:=∅:P拥有的键的集合;(2)数组T [v, x]:=⊥，其中v是键值，x是域值:pair (y, S)，其中y是区间值，S是证明集π;(3)集合E:=∅:包含三元组(v, x, y)，以跟踪所有VRF的评价。
键:当(getKey)从P:输出(getKey, P)到S，并向S请求一个唯一的键v，添加v到键[P]和输出(getKey, v)到P。
注册键:当(regKey, v) from S:如果v是唯一的，将它添加到键[S]。
求值:当(Eval, v, x) from P with v∈key [P]:输出(Eval, P, v, x)到S，当从S获得(Eval， π):(1)如果π不是唯一的，退出该过程。
(2)如果T [v, x]未定义，则在值域内均匀随机选取y，设S:=∅;否则，令(y, S):= T [v, x]。
(3)集合T [v、x]: = (y S∪{π})并添加(v, x, y) E。
(4)输出(Eval, y， π)到P。
•情况1:存在一个v∈key的未损坏的P [P]:如果(y, S):= T [v, x]被定义，返回(Eval, y)到S;否则，什么都不做。
•情形2:存在一个损坏的P，其中v∈Keys[P]或v∈Keys[S]:如果T [v, x]没有定义，则在值域内均匀随机选取y，设S:=∅，设T [v, x]:= (y, S);否则，令(y, S):= T [v, x]。返回(Eval, y)到S。
•其他:什么都不做。
验证:当(Verify, v, x, y， π)来自任意ITI时:发送(Verify, v, x, y， π)到S，当从S接收(Verify， φ)时:•如果定义v∈Keys[·]和T [v, x] = (y, S):(1)如果π∈S，设置f:= 1。
(2) Else，如果φ = 1且π是唯一的——即,如果(v ’ x '), (v, x)和T (v’,x ′] = (·, ,π<年代T [v、x ']: = (y S∪{π})和f: = 1。
否则，设f:= 0。
•否则，设置f:= 0。
输出(Verify, f)到P。
对抗性泄漏:当(泄漏)从S处:返回(泄漏，E)到S处。
图2:VRF功能。
上述保证由一个理想化的功能Fvrf抽象(cf.图2)。Fvrf提供的主要命令是(i) (getKey)，对于一个(对路选择的)理想公钥v，由(getKey,v)回答，(ii) (eval,v, x)，由(eval,y， π)回答，以及(iii) (Verify,v, x,y， π)，其中φ∈{0,1}表示π是否是公钥v下输入/输出对(x,y)的有效证明。
3、拜占庭弹性网络
3.1概述
这项工作的主要贡献之一是定义和实现了一个同步功能Fsync，可以被利益证明(PoS)共识层的参与者用于全局同步他们的区块链。Fsync的一个最关键的特性是，它可以在与构建在它之上的共识协议相同的假设下实现。
粗略地说，支持实现Fsync协议的思想如下:每个共识参与者P基于可验证随机函数(VRF)的输出以基于利益的方式采样ΘP·d邻居;d是一个小常数，ΘP是一个乘数，它取决于P本身的持股数量。VRF的使用保证了各方可以验证它们是否确实应该被其他参与者选择为邻居。
一旦对邻居进行采样，链就会由与所有邻居进行双边链同步的每一方进行全局同步。由于产生的通信覆盖实际上是一个随机图，使用扩展器理论，可以显示即使删除了所有对抗节点，仍然有一个直径小的大连接骨干。这使及时同步(TS)成为可能，这对许多共识协议的安全性至关重要。
当然，在邻居数量恒定的情况下，不可避免的是，一些政党最终只与腐败的政党联系在一起，这意味着它们会黯然失色。因此，Fsync将不得不授予对手的重叠能力，只能保证TS的非重叠方。
功能Fsync将从一个功能Fbilateral(参考第3.4节)实现(参考第3.2节)，它模拟了双边链同步，以及从网络功能Fnet(参考第3.4节)实现。
第2节)和(标准)功能Fvrf(参考第2节)。
3.2 双链同步
功能Fbilateral(参见图3)模拟了A和b两方之间的双边链同步。在Fbilateral中，每一方都有一个本地链，该功能允许它们在对方链的演进过程中了解其链。一方的局部链通过使用setC命令进化，其限制条件是局部链只能被“更好的”链取代，该链由严格的部分顺序prefer(·，·)决定，其中prefer(C,C ')(也表示为C > C ')当且仅当C严格优于C ';7 prefer是功能的一个参数。
双方都被告知其对手的本地链的变化，延迟最多为δsync。然而，最初，即直到双方至少使用了一次setC（从而表明他们已经准备好开始链式同步），延迟可能高达δinit；这模拟了一个事实，即在现实中，链式同步在刚刚建立连接的双方之间可能需要大量时间。
参数:δinit:初始延迟;δsync:同步延迟;Prefer(·，·):严格部分顺序。
当事人和会话ID:涉及A和B两个当事人。下面，当P∈{A, B}时，P’指的是另一方。双方使用sid = (A, IP, B, IP '， t, j)作为会话ID(对于某些t和j)。
变量:对于双方当事人P∈{A, B}和所有回合t，该函数跟踪以下变量，初始化为以下值:(1)C[P, t]:=⊥:第t回合P的局部链;(2) Ptr[P]:=−∞:P变为C的时间指针[P '，·];(3) tstartP:最小t使C[P, t]，⊥。
(1)向S输出(Fetch, P)并向S请求时间指针Ptr < T。
(2)如果T−马克斯{tstart [P], tstart [P ']} <δinit, d: =∞;否则，设置d:= δsync。
(3)令Ptr[P]:= max{Ptr, Ptr[P]， T−d}。
(4)输出(fetch, C[P '， Ptr[P]])到P。
设置本地链:Upon (setC, C) from P: if prefer(C, C[P, T−1])，设置C[P, T]:= C。
图3:双边链同步功能。
这一工作保留了实现Fbilateral开放的确切机制，并简单地假设Fbilateral是一个混合体。一般来说，实现Fbilateral的方法是沿着以下路线进行的:在建立连接之后，双方首先确定其本地链的分歧点;89随后，他们将本地链的更改通知对方。
在实践中，为了进一步提高同步时间，使用了高度优化的Fbilateral实现。有关此类实现的示例，请参见[9]和[8，第3.7节]。
3.3同步功能
功能Fsync的实现是本工作的主要重点，它允许各方将自己的链与其他参与者同步。它由初始延迟∆init、同步延迟∆sync、eclipse延迟ξecl≥∆sync、“回看”参数µ≥∆sync以及重叠诚实赌注量的上限λ进行参数化。
请注意，双方必须就开始使用Fsync的整数达成一致。为了方便起见，在本节中，Fsync的初始化在round -∆init中开始，各方实际上在第0轮中开始使用Fsync。
IP和密钥管理。由于Fsync是通过Fnet和Fvrf实现的，所以Fsync还提供了IP注册和密钥注册的接口。
这些没有被抽象出来的原因是IPs和VRF密钥必须被(更高级别的)共识协议所知道(例如，为了生成生成块)。掌握索引和设置。如前所述，在同步协议中，各方将根据其利害关系对邻居进行采样。
然而，权益分布是一个来自共识层的对象，而共识层本身依赖于同步功能。这个明显的循环被打破如下:Fsync期望每一方在一开始通过命令设置在主索引上输入自己的观点(cf.第2节)，Fsync只提供保证如果(a)所有诚实的各方(i)同意主索引和(ii)来自同一起源块的输入链，(b)所有诚实的各方在他们输入的主索引MI = (ND, SD, R)中表示;如果一方的一个IP地址IP和一个密钥v出现在ND中，即(P, IP,v)∈ND，则用MI表示。
当上述所有条件都满足时，Fsync有效设置。如果设置无效，则关闭Fsync。注意，共识协议(即扩散上下文中的环境)有责任确保设置是有效的。这通常是通过最初的起源块(假设所有方都可用)来实现的，随后基于协议的跨时代共识属性。关于这种关系的更多细节将在第5节中提供。
黯然失色。由于在实现Fsync的实际可行和可扩展的协议中，每一方只连接到所有参与者的一小部分，因此不可避免的是，对手可能通过(自适应地)破坏所有邻居来掩盖某些诚实的方。因此，Fsync提供了一个eclipse命令，通过这个命令，攻击者可以将任何诚实的一方排除在TS保证之外(见下文)。
攻击者使用eclipse命令有两个限制。第一个是，eclipse命令只有在ξecl的延迟后才生效。第二个限制基于以下无t方的概念:定义3.1。一个无t的政党是一个诚实的政党，在t−1、t−2轮中没有被掩盖……， t−µ。
eclipse的限制是在任何时刻t, t-非自由诚实方所对应的股权比例不得超过参数λ。
以这种方式制定食言限制，可以防止攻击者在每一轮中食言一个完全不同的子集，因为在第t轮中被食言的一方基本上封锁了与攻击者的食言预算λ中的股权相对应的μ个槽。然而，请注意，对手绝对有可能在无限长的时间内吃掉某一方。这必须由使用Fsync的高层共识协议来处理。
参数:∆init:初始延迟;∆sync:同步延迟;ξecl≥∆sync: eclipse延迟;µ≥∆sync:非自由回视参数;λ:非自由诚实股权的最大比例;Prefer(·，·):严格部分顺序。
===
管理变量:该功能跟踪以下变量，对所有方P和轮询t初始化为以下值:(1)IPs[P]:=∅:P拥有的IPs集合;(2)键[P]:=∅:P拥有的键集合;(3) C[P, t]:=⊥:圆t中P的局部链;(4) E[P, t]:= false:圆t中P的日食状态;(5) MI[P]:= P所见的主指数;回想一下MI = (ND, SD, R)(参见第2节)。
设置:当(Setup, MI, C) from P (in round -∆init):设置C[P， < 0]:= C和MI[P]:= MI。
IP地址:当(getIP)来自P时:输出(getIP, P)到S，并向S请求一个唯一的地址IP。添加IP到IP [P]，输出(getIP, IP)到P。
当(getKey)从P:输出(getKey, P)到S，并向S请求一个唯一的键v。
添加v到键[P]，输出(getKey, v)到P。
===
获取和设置获取链:当(获取)从P:(1)输出(获取，P)到S，并向S请求一组D的链。
(2)对于任何C，其中C[P '， T−∆sync] = C对于某些T-核心节点P ':如果P是一个T-核心节点，并且对于D中所有背书的链C '更倾向于(C, C[P, T−1])以及更倾向于(C, C ')，则将C添加到集合D '。
(3)输出(取，D∪D ')到P。
设置本地链:Upon (setC, C) from P: if prefer(C, C[P, T−1])，设置C[P, T]:= C。
===
对敌重叠:来自s的(重叠，P)在所有诚实的参与者在当前轮T中设置了主指数之后:如果在本轮T中重叠P将导致(T + ξecl + 1)-非自由股权剩余在λ以下的部分，则设置E[P, T + ξecl]:= true。
注册IPs: on (regIP, IP) from S:如果IP唯一，则添加到IPs[S]中。
注册键:当(regKey, v) from S:如果v是唯一的，将它添加到键[S]。
===
概念表示:如果(P, IP, v)∈ND对IP∈IPs[P]和v∈Keys[P]表示P。
重叠:如果E[P, t] = true，则P在圆t中重叠。
核心党和自由党:P党是t-核心党。
t-free party)如果它没有在轮t-∆同步中被重叠，……， t−1 (resp。T−µ，…， t−1)。
有效设置:如果(a)所有诚实的一方使用(i)来自同一起源块的链和(ii)相同的MI的设置，并且(b)所有诚实的一方都被表示，Fsync具有有效设置。
如果Fsync的设置无效，它将停止。
===
主操作和及时同步(TS)。与Fbilateral类似，一方使用setC根据谓词偏好将其本地链切换到严格更好的链(参见第3.2节)。此外，各方使用fetch是为了接收关于其他参与者的链的信息。
Fsync提供的TS保证基于t-core的以下概念:定义3.2。t-core政党是一个诚实的政党，在t- 1轮、t- 2轮、……， t−∆同步。
因此，t核心的概念与无t方的概念非常相似，只是“回看”较少(∆sync≤µ)。1 TS保证现在如下:假设一个诚实的政党P集当地一些链链在时间t C。然后,通过t +∆同步,提供P (t +∆同步)生水,以下适用于P (t +∆同步)生水起各方“,•P”已经转变了当地连锁C”,或•fetch命令返回C”,C '在哪里与¬喜欢连锁(C, C”),也就是说,无与伦比的或比C。
3.4同步协议
概述。协议π同步(参见图5)，在Fnet、Fvrf和Fbilateral的混合模型中实现了Fsync，遵循3.1节中概述的利益加权随机图方法。该协议使用一个VRF来确定随机图，并确保诚实的一方只接受来自他们在图中的邻居的连接。一方与每个邻居运行Fbilateral实例，以跟踪它们的本地链。每当一方了解到一个有效的链C“比他们当前的本地链更好，他们就会切换到C”。然而，正如下面所阐述的，有效性检查和切换决策发生在环境中;因此，π同步只能在(非常合理的)有限的环境中实现Fsync。
管理。协议π同步处理对ip和密钥的请求，只需将它们分别转发给Fnet和Fvrf，然后将后续的响应返回给环境。
当从环境接收(setup, MI '，C)时，π同步将这些值存储在内部以备以后使用。
覆盖。π同步最关键的部分是建立和更新随机图叠加。一方P最初为每个时间戳t =−(d−1)r，−(d−2)r，对ΘP邻居进行采样…，−r, 0独立且基于它们的权益，其中ΘP是一个乘数，依赖于P本身的权益αP;具体来说，ΘP:=⌈αP /αmin⌉， 对于某个参数αmin。
参数:d:度参数;R:刷新参数;αmin:最小核心方股权;Prefer(·，·):严格部分顺序。
混合:Fnet:网络功能;Fvrf: VRF功能;Fbilateral:双边链同步功能。
===
管理变量:从一方P的角度描述协议;(1) IPs:=∅:P拥有的IPs集合;(2)按键:=∅:P拥有的按键集合;(3) Clocal:=⊥:P的局部链;(4) MI:=⊥:主指数;回想一下MI = (ND, SD, R)(参见第2节)。
(5)(隐式)涉及P的f双边实例。
设置:当(Setup, MI '， C)从P(第0轮之前):设置Clocal:= C和MI:= MI '。
令IP和v为P在ND中的IP和VRF键，即(P, IP, v)∈ND。
IP地址:on (getIP) from Z: Output (getIP, P) to Fnet, receive (getIP, IP) from Fnet, add IP to IPs, Output (getIP, IP) to Z。
key: on (getKey) from P: Output (getKey, P) to Fnet, receive (getKey, v) from Fvrf, add v to Keys, Output (getKey, v) to Z。
===
Fetch & Set Fetch chain: on (Fetch) from Z: (1) Let D:=∅。对于Fbilateral的所有实例:输出(fetch)到Fbilateral，接收(fetch, D’)从Fbilateral;在D后面加上D '。
(2)设Dpref全部C∈D，其中preferred (C, Clocal)。
输出(fetch, Dpref)到Z。
设置本地链:Upon (setC, C) from Z: If prefer(C, Clocal)，设置Clocal:= C。对于所有Fbilateral实例，输出(setC, C)到Fbilateral。
===
Overlay Management Multiplier: P的度数乘数定义为ΘP:=⌈αP /αmin⌉，其中αP是P根据SD的权益。
初始化:(作为setup命令的一部分运行)对于t =−(d−1)r，−(d−2)r，…，−r, 0和j = 1，…， ΘP，运行SamCon(t, j)。
刷新操作:(作为fetch命令的一部分运行)当T是r的正倍数时:停止具有T时间戳的已过期的双边实例(即T−T = dr)。对于j∈1，…， ΘP:执行SamCon(T, j)。
SamCon(t, j):按照以下步骤进行:(1)输出(eval, v, R| |t | |j)到Fvrf，从Fvrf接收(eval, y， π)。
(2)令(P '， IP '):= pick(y)，令IP为(P, IP，·)∈ND的IP。使用Fnet发送消息(P, IP, P '， IP '， t, j, y， π)到IP '。
以sid = (P, IP, P '， IP '， t, j)启动双边实例。
程序选择(y):使用y作为随机硬币，按其在SD中的赌注比例选择一方P’。
输出(P '， IP ')，其中IP '满足(P '， IP '，·)∈ND。
处理传入连接:(作为fetch命令的一部分运行)(1)设IP是(P, IP，·)∈ND的IP。
(2)从Fnet中获取消息。对于每个消息(P '， IP '， P, IP, t, j, y， π):(a)检查t是否过期(即，t−t < dr)，并且不是来自未来或非正的(即，t≤t不确定t≤0)。
(b)校验j∈{1，…， Θp '}。
©输出(verify, v '， R| |t | |j, y， π)到Fvrf，其中(P '，·，v ')∈ND，并检查Fvrf与(verify, 1)对应。
检查pick(y) = (P, IP)
如果所有检查都通过，运行Fbilateral instance with sid = (P '， IP '， P, IP, t, j)
图5:协议π同步，实现功能Fsync。
===
dr插槽后，与邻居的连接到期;因此，在r的倍数的每一轮中，采样的新邻居为ΘP。以这种方式更新覆盖层可以帮助各方从实际的日食事件中恢复过来;然而，在此工作的背景下，这里考虑的自适应攻击者可能只是破坏一方的所有新邻居。因此，面对如此强大的对手，对于特定政党而言，日食的持续时间没有上限(当然，除非对手耗尽其腐败预算)。此外，刷新邻居还允许覆盖层逐渐适应变化的股权分布。
由P方执行的实际抽样被描述为图5中的SamCon(t, j)过程，其中t是时间戳，j = 1，…， Θp。该程序使用一个子程序pick(y)，它使用VRF输出的y作为随机硬币，按其在SD中的赌注比例选择一方P’。注意，VRF的输入(除了P的公钥)是随机随机数R (MI的一部分)、t和j。
在上述采样之后，P通过Fnet向P '发送一个连接请求，并立即开始相应的Fbilateral实例。相反，P '将在接收到连接请求时启动实例(在执行明显的检查之后)。
链管理。在从环境接收(setC,C)时，如果C优于P的当前本地链，P将相应的变量和输入(setC,C)更新到所有正在运行的Fbilateral实例。
P从环境接收(fetch)后，向所有正在运行的Fbilateral实例发送(fetch)，并在集合D中收集应答链;D中优于P当前本地链的所有链都返回到环境中。
链有效性和切换。考虑到区块链共识的应用，可以观察到在π同步(或者，在理想的情况下，是Fsync)的上下文中没有“链有效性”的概念。这是一个来自高层共识层的概念。因此，π同步(Fsync)不可能检查链的有效性并“自动”切换到最佳有效链。因此，这项任务落在了环境的肩上。
在这一点上，还必须注意到，通过网络成功的链“传播”在很大程度上取决于环境——在每一轮中使用setC使各方切换到目前为止接收到的最佳有效链。为了避开“有效性”概念的特定于应用程序的性质，使用了以下代理:
定义3.3。在执行π同步(或Fsync)时，如果环境在某一点上代表诚实方P输入(setC,C)，则链C被认可。
背书链的概念允许定义一类环境Z w.r.t，其中π同步必须实现Fsync:定义3.4。如果在每轮t中，每个诚实的参与方P输入(setC,C)一条链C，这是P在第t轮内通过fetch接收到的所有认可链中最大的w.r.t偏好，那么环境Z就是h -改善的。
通过以上，最终得到以下主要定理:定理3.5。设•n∈n，•α > β > 0， δ > 0, cmin, cmax是满足0 < cmin < 1 < cmax且(α−β)/2≥β + cmin/n且•r∈n的常数。
然后,足够大的d,存在一个常数γ> 0,这样协议π同步(d + 1, r, cmin / n]ε安全地实现Fsync(∆init,∆同步、µξecl,λ)的{Fnetδ净,Fvrf, Fbilateral(δinit,δ同步)}混合模型关于H-improving环境(1)输入MI与n方中任何一方拥有超过cmax / n的一部分股份,(2)腐败最多一个α一部分股份,(3)竞选最多L轮,在•∆init =δ净+δ,•∆同步= 8ℓℓ:=⌈−log1 +γ(2 cmin / n) + 1⌉,•∆同步≤ξecl≤min(ξ。柯尔,r)•µ= r•δinit≤r•λ= 2(β+ cmin)和•ε= L / r·e−δn。
言论。一个简单的Chernoff边界可以用来说明，如果不存在小利害关系节点(利害关系小于cmin/n)，则所有各方的程度都是恒定的。当小节点较多时，大节点的度数大于常数。然而，我们可以证明，通过让小风险节点统一挑选它们的对等节点(而不是基于风险)，所有节点的度数都再次回到常数。
安全误差ε在参与方n的数量中呈指数小。当然，在实践中，以适当的方法确保有足够多的参与方是重要的。实现这一目标的一种可能方法是设立所谓的股权池运营商(SPOs)，各方可以将股权委托给他们，运营区块链，并使用激励机制来控制SPOs的总数。
此外，在定理3.5中也有几种方法来实施最大利益限制。在有spo的系统中，可以在共识级别上限制最大委托权益。
或者，可以再次设置激励机制，使spo吸引的股份不超过一定数量。有关更多信息，请参见[4]。
===
4 .安全证明
本节给出同步协议πsync的安全性证明(参考3.4节)。
安全性论证中最关键的部分是基于利益的扩展器图的新结果。具体来说,给定一个图G中每个顶点v已经分配给它一些股份α∈(0,1],˝vα= 1,和每个顶点选择邻国stakebased时尚协议采用π同步,4.1节中的结果表明,即使把所有敌对节点从G,至少留下一些α分数诚实的股份,存在一个诚实的“骨干”持有至少α−β,β,这样的骨干是一个扩张器图。
如第4.2节所示，上述转换为π同步实现了Fsync，大约有一个β-分数的诚实利害被重叠，13，而由于主干的扩展器特性，其余的诚实当事方的“核心”彼此之间的距离最多为O(log n)跳，其中n为当事方的总数。需要注意的是，这个核心只近似对应于上面的骨干，原因是(a)骨干不能有效地计算(因此，必须使用近似)，(b)桩基小于cmin/n的骨干节点需要从核心中排除(因为扩展器属性不能用于限制它们与骨干中其他节点的距离)。
4.1膨胀器抵抗顶点删除
一个众所周知的事实是，随机图——具有各种各样的边缘分布——具有高概率形成扩展器，因此具有小直径和其他理想的特性。本节展示了协议生成的随机图具有如此强的属性，即使允许完全了解图的对手删除节点的恒定部分。
如上所述，我们表明，对于任意两个常数α > β > 0，存在一个度参数d，对于这个度参数d，只要在对抗性删除后仍保留α部分的节点，就存在一个由α - β部分节点组成的子集(“骨干”)，它是一个强扩展器。通常，我们会选择β < α，这样骨干就几乎包括所有剩余的顶点。
这些结果是由经典的Upfal[29]定理驱动的，该定理使用不同的方法建立了Ramanujan图的相似性质(得到固定常数α和β)。因此，我们的结果通过(i)处理随机图，(ii)建立任何常数都可以通过适当选择d来实现。在过渡到技术调查之前，最后一个注释:我们还直接处理加权图(与权益对应的权重)，因此我们可以定义和处理“权益加权”展开的自然概念。
我们的协议直接激发了下列随机有向图的分布族。
定义4.1。设d和n为正整数，设d为[n]上的一个概率分布，其性质是dv = ndD(v)对于每个顶点v是一个整数。设Gn,d; d表示v = [n]的有向多图上的概率律，通过选择，对于每个v, dv的出邻域w1，…， wdv根据D独立，并定义有向边的多重集E = - v - dvi=1(v, wi)。1我们让Gn,d表示当d是均匀分布的特殊情况，在这种情况下dv = d对所有v。
我们希望表明，Gn,d; d是典型的“桩扩展器”:也就是说，集合S⊂V有一些在它们外面的邻居，或离开它们的边，与它们的总桩成比例。
定义4.2。设G = (V, E)是一个有向图。对于子集S⊂V，我们将S的(外)边界定义为∂(S) = {w < S |∃S∈S: (S, w)∈E或(w, S)∈E}。
设D是集合V和γ >上的一个分布。我们说G是(D，γ)展开式如果对于顶点S⊂V的每个子集D(S)≤1/2,D(∂(S))≥γ D(S)我们用符号D(S)表示“S∈S D(S)”
定理4.3。设α > β >和δ >为正常数，设cmin和cmax为满足cmin < 1 < cmax的正常数。对于足够大的d，存在常数γ > 0，其中d是V = [n]上的一个分布，其中cmin/n≤d (V)≤cmax/n, dv≜ndD(V)是每个V∈V的整数。考虑G = (V, E)根据Gn,d; d。那么，除了pfail概率≤e−δn外，对于每个D(H)≥α的子集H⊆V，都有一个子集H’⊂H，其D(H’)≥α−β，由H’诱发的子图是一个(D’，γ)膨胀子图，其中D’是分布D乘以1/D(H’)。
证明见附录A。
的话。定义4.1和定理4.3中ndD(v)对于所有v都是整数的条件仅仅是为了方便，以便每个顶点的出度将是一个固定的整数dv。我们也可以定义dv =⌈ndD(v)⌉。这将改变每个玩家的有效赌注1±O(1/d)。事实上，我们只需要每个顶点的赌注上限，因为我们可以把所有赌注非常低的顶点交给对手(参见引理A.5)。
4.2同步协议安全
本节使用4.1节的结果最终证明了协议π同步的安全性。
仿真基础。模拟器S在内部模拟协议和混合Fnet、Fvrf和Fbilateral的实例，以及对手A(充当与环境的接口);在下面，这个集合被称为模拟真实世界(SRW)。具体来说，S在从Fsync接收消息时的反应如下:•当(setup, P, MI,C):在SRW中，代表P输入(setup, MI,C)。
•on (getIP, P):在SRW中，输入(getIP)代表P;等待接收(getIP, IP)代表P;返回IP到Fsync。
•on (getKey, P):在SRW中，代表P输入(getKey);等待接收(getKey,v)代表P;返回v到Fsync。
•在(fetch, P)时:在SRW中，代表P输入(fetch);wait to receive (fetch，￣D);return ~ D to Fsync。
•on (setC, P,C):在SRW中，代表P输入(setC,C)。
•on (regIP, IP):输入(regIP, IP)到Fsync。
•Upon (regKey,v):输入(regKey,v)进行Fsync。
符号。确定诚信方一开始输入的主索引MI = (ND, SD, R);回想一下，n表示MI中各方的数量。在下面，对于MI中各方的子集S，用αS表示:= SD(S) S中各方所持有的股份数量。
决定遮盖谁。S的一个关键部分是确保在处理获取命令时，Fsync不会强制执行与SRW相冲突的交付保证。为此，S决定哪些诚实的一方被“掩盖”，并将这一信息转发给Fsync。回想一下，Fsync不会为非核心方提供任何担保，当且仅当一个方在第t轮处于核心时，它没有在第t - 1轮、第t - 2轮中被遮盖……， t−∆同步。
为了理解哪一方在特定的t时刻被取代，考虑MI中所有各方形成的图G和在t时刻使用VRF所暗示的连接，但忽略最近刷新期间添加到图中的边(即，在最大的轮t '≤t中，它是r的倍数)。该图遵循分布Gn,d;SD。
设H表示时刻t的诚实方集合。根据定理4.3，存在一个集合H '⊆H，且αH '≥αH−β，这样由H '诱发的G的子图是(SD '，γ)膨胀子图，其中SD '是SD乘以1/αH '。这个扩展器属性允许将H '中各方之间的直径与一定的最小股份绑定，这一事实用于显示:权利要求书4.4。如果每一方的H′中SD的利害关系至少为cmin/n，那么最多可以在ℓ步内达到(αH−β)/2以上的诚实利害关系。
证明。考虑一个参与方P∈H '，其权益为αP≥cmin/n。其根据SD′的股权等于αP /αH′≥cmin αH′n。
如果cmin αH ’ n (1 + γ)ℓ’ > 1 2，则通过H '上的扩展子性质，可以在ℓ’步骤中从P(根据SD ')到达H '中的1/2以上的桩。
这是满足ℓ’:= ?log1 +γ?αH ’ n 2cmin ?+ 1 ?≤?log1 +γ?N 2cmin ?+ 1 ?=ℓ。
H′根据SD′的极值达到一半，即根据SD的极值达到αH′2≥αH−β 2。□由于定理4.3中的安全参数是非建设性的，因此不清楚是否能有效地确定集合H’。相反，考虑集合It:= {h∈h |可以从h}在ℓ步内达到β + cmin/n HS，其中HS代表“诚实的赌注”。只要从上下文清除，下标就从I中删除。
4.5要求。αI≥αH−β−cmin。
证明。首先，观察到(α h−β)/2≥(α−β)/2≥β +cmin/n，其中最后一个不等式通过假设得到。根据权利要求4.4,H’中持有至少cmin/n股权的所有各方因此都属于i。接下来的权利要求观察到，总股权中最多cmin由持有超过cmin/n股权的各方持有。□与H′诱导的子图一样，I诱导的子图也有有界直径:权利要求4.6。I中任意两方之间的路径长度不超过4ℓ。
证明。根据I的定义，从I中的任何节点出发，在ℓ步内可以在H中至少达到β + cmin/n的入股，因此，在H '中至少可以达到cmin/n入股。权利要求4.4证明中的论证表明，在H '中任何两个节点之间的桩值至少为cmin/n的路径长度不超过2ℓ。有人得出结论，i中任意两个节点之间必须有一条长度不超过4ℓ的路径。□鉴于上述，S的遮盖策略是，在每一轮t中，使用(遮盖，P)遮盖所有P < It的方。然而，由于Fsync的重叠延迟特性，S被迫在时间t−ξecl时或之前根据It设置重叠状态。然而，这是可能的:•由于ξecl≤r和在最近一轮t '≤t中添加的是r倍数的边被忽略，所以在第一轮t中G的拓扑由回合t−ξecl可知。
•由于ξcorr≥ξecl，那么哪些一方是诚实的，哪些一方是腐败的，也称为回合t - ξecl。
绑定同步时间。证明的下一步包括争论Fsync从来没有添加任何链C设置D '在某个轮t中由P方获取调用。
为此，首先假设{t−4ℓ中没有r的倍数，……， t−1}，即底层图G在此周期内不发生变化。因此，It−4ℓ⊇It−(4ℓ−1)⊇…⊇It−1，其中元素随时间从I中删除的唯一原因是腐败。
现在考虑第t轮中P的取回命令。回想一下，只有当(i)在第t−∆同步中C由某个诚实的方P’持有，(ii)在第t−1轮中P和P’都没有被重叠时，链C才被添加到D’中，， t−∆sync， (iii) C优于轮t−1中P’持有的链和集合D中的所有链(在获取调用期间)。
观察∆sync≥4ℓ;因此，(ii)成立的事实(即S事先没有对轮t−1的P或P’发出eclipse命令，…， t−∆sync)表示在第t−1轮中，双方P和P '都在第I组，……， t−4ℓ。
因此，根据集合I的单调性，P '和P之间存在一条长度不超过4ℓ的路径，结合Z是h -递增的，且(再次)∆同步≥4ℓδ同步的情况，意味着到时间t时，P的局部链已经被设置为t时集合D中的C '咿咿咿C的链，或者是集合D中的C '咿咿咿C的链。
最后，对于包括对G的变化在内的间隔，观察到自从∆sync = 8ℓ以来，在对G的变化之前或之后至少有4个ℓ轮。
非自由股权金额。根据权利要求4.5，非自由木桩的数量保持在λ = 2(β + cmin)以下，注意到对于包含r倍数的∆同步大小区间，需要额外的因子2。
定理3.5的证明。为了完成基于上面的证明，请注意，仍然只是对所有刷新周期(长度为r)应用联合边界。
5 .完全确保pos共识
本节讨论在链同步功能Fsync之上运行PoS共识协议的应用。具体来说，这里考虑的协议是Ouroboros Praos[11]，它是一个最长链的中本式区块链PoS协议，首先进行描述。然后比较[11]和Fsync中使用的“扩散”功能Fdiff。在此基础上，提出并讨论了恐蛇安全证明的变化;特别地，作为可能独立的贡献，提供了所谓forkablestring分析的一般化版本。
5.1衔尾蛇
Ouroboros Praos(或者，简单地说，Praos)在所谓的槽中前进。在每个插槽中，每一方P首先检查它是否“收到”了比其当前本地链更长的有效链;如果是，它会切换到其中最长的一个。随后，根据当前epoch使用的股权分布，P检查自己是否是槽头。这一确定是基于VRF的输出y(除P的键外)评估槽号和所谓的历元随机性;如果y最终低于某个阈值，该阈值是P的赌注的单调递增函数，则P是槽位领先者。因此，它创建了一个新的块，扩展它当前的本地链C;该块由C的最后一个块的散列、槽位号、P的标识、VRF输出和VRF证明、一个数据有效负载以及一个签名组成。由此产生的链C’随后被“发送给每个人”。
5.2扩散vs.同步
在[11]中，各方共享一个扩散函数Fdiff，由数值∆参数化，具有一个简单直观的性质，即诚实方通过Fdiff扩散的任何链将“到达”所有其他诚实方，其延迟不超过∆槽。
现在考虑使用Fsync，以便“同步”而不是“扩散”链。图6包含使用Fsync的(static-stake) Praos协议的描述。协议还使用了混合Fvrf进行槽领导，以及以下两个混合，它们只在本节的背景下在高级别上进行了描述:更准确地说，各方最初向Finit发送诸如密钥、ip等信息，然后Finit生成初始主索引和起源块。
•Fkes是一种理想化的密钥演化签名功能，特别是允许各方创建密钥以及发布和验证签名。
由于它是由协议实现的，而不仅仅是假设，Fsync提供的保证在以下几个方面是较弱的:•总权益的λ部分可能会被掩盖，相应的当事人被排除在及时同步(TS)保证之外。
•与Fdiff提供的TS属性相比，Fsync的TS属性较弱:与通过∆槽内的网络“传播”的特定链C不同，Fsync可以交付不同的链C’，这些链C并不差(即长度相等或更长)。
•为了通过其实现取代Fsync，环境必须是h - improvement(参考章节3.4)。
下一节详细介绍如何更新Praos的安全证明，以处理这些较弱的Fsync保证。
参数:k:普通前缀参数;Prefer(·，·):严格部分顺序。
混合:Finit:生成初始主索引和生成块;Fvrf:用于确定槽位领导权;Fkes:用于密钥演化签名;Fsync:允许同步链。
===
管理和初始化变量:从一方P的角度描述协议;它跟踪以下项目，初始值如下:(1)Clocal:=⊥:P的局部链;(2) η:=⊥:VRF盐值。
初始化:P初始化过程如下:(1)通过Fsync获取IP地址和网络(VRF)密钥。
(2)使用Fkes获取签名公钥。
(3)使用Fvrf获取VRF密钥(用于槽位领导)。
(4)将上述值传递给Finit，得到初始主指标MI、成因链Cgenesis、历元随机性η′;设置Clocal:= Cgenesis和η:= η '。
(5)输入(setup, MI, Cgenesis)进行Fsync。
===
在每个槽位s≥1时，执行以下操作:Fetch chains:输入(Fetch)进行Fsync，获取一组D的链。在有效链C '∈D with prefer(C '， Clocal)中选取一个最大(w.r.t. prefer)链，并设置Clocal:= C ';如果不存在这样的链C’，保持Clocal不变。如果(1)与Clocal具有相同的起源块，(2)所有散列都正确，(3)块的槽数严格增加，(4)所有VRF值y和证明π都有效，且y小于签发方的阈值，(5)所有签名都有效，则一个链是有效的。
链扩展:发送(eval, v， η∥s)到Fvrf，其中v为P的VRF键(存储在起源块中)，得到VRF值y和证明π。如果y低于P的领导阈值，则创建块B = (h, s, P, y， π， d， σ)，其中h是Clocal中最后一个块的哈希值，d是数据负载，σ是通过Fkes在(h, s, P, y， π， d)上获得的签名。设置Clocal:= Clocal∥B。
链同步:输入(setC, Clocal)到Fsync。
分类账:输出Clocal中深度至少为k的块中包含的所有数据d的拼接作为分类账。
===
5.3 Praos的更新证明5.3.1特征字符串和叉。在Praos安全性证明(具有Fdiff功能)[11]的核心是特征字符串、分叉和边距的概念，它们捕获关于Praos执行中事件的安全相关信息。特征字符串表示协议执行过程中所选领导人的相关信息。分析表明，一致性违反可以通过以下方法来控制:(i)将给定的领导人选举序列(由特征字符串决定)可能出现的块树族提取为一个称为裕度的单一数字度量;(ii)分析支配特征字符串的生成和裕度的结果行为的随机过程。最后的结果被表述为一个大偏差边界的裕度，建立了高概率的一致性。在本节中，我们将讨论如何通过更细粒度的网络和块交付视图来适应我们的设置。
Praos中的特征字符串具有w = w1w2的形式。并记录执行中关于槽位领导的信息。字符串中的每一个字符都是一个符号wi∈{a, H，⊥}，其中wi =a如果i号槽位有一个对手或多个首领，H如果i号槽位有一个诚实的首领，则是⊥，如果i号槽位没有首领。
对于特征字符串w, A∆-fork F是一个有向的、有根的树，旨在表示在执行Praos过程中观察到的所有链的拓扑结构:F的每个顶点v对应于特定链中的一个块，并具有标签ℓ(v)∈N，记录块的槽号。起源块由树的根表示。fork的边缘被指向“远离”根，因此从根到任何顶点都有唯一的指向路径。
根据Praos的描述，很容易看出一个fork满足以下属性:
(i) 根r∈V的标签ℓ®=0，被认为是诚实的。
(ii) 沿着任何有向路径的标签ℓ(-)的序列是严格增加的。理由是：这是由协议强制执行的。
(iii) 如果wi = H，有一个唯一的顶点v，对它来说ℓ(v) = i。
理由是：诚实的一方不会创建多个区块。
(iv) 对于任何一对诚实的顶点v,v′（即wℓ(v) = wℓ(v′) = H），且ℓ(v) + ∆ ≤ ℓ(v′)，它们的长度（即与根的距离）len(v)和len(v′)满足len(v) < len(v′)。理由是。根据Fdiff的保证，在ℓ(v ′)槽中创建顶点v ′对应的块时，v对应的块是可以建立的，因为它是在ℓ(v)槽中创建的，它至少比v ′早∆个槽；因此，len(v ′)必须严格大于len(v)。
分析通过定义一个fork的边界概念继续进行，它反映了fork中存在的路径(链)对，这些路径(链)在特定槽之前发散，并超过了最深的诚实块的长度。直观地说，这样的路径对对应于一致性故障，实际上，精确的裕度定义确保了在存在这种一致性故障时，数量恰好为正。这个概念通过最大化与字符串一致的所有分叉扩展到特征字符串。然后，分析表明裕度满足特征字符串(对应于协议的执行)的递归关系，最后，观察到正裕度的概率很小。
5.3.2重叠方的核算。显然，上面的∆-fork形式没有考虑以下情况:(a)龙头不同步，可能无法在某个最长的链条C上构建，该链条的最后一个区块比∆槽老，或者(b)龙头的区块比∆槽长，才能到达下一个龙头;自然，日食事件可以引起(a)和(b)。在下面，一个诚实的领导者没有(a)被称为电流，一个诚实的领导者没有(b)被称为中继。一个诚实的领导者，既受人欢迎又受人欢迎，被称为同步的。
为了更新可寻字符串分析以考虑到非中继方，对其进行了以下更改。首先，特征串现在是在一个字母wi∈{A, CR, C, R，⊥}，其中wi =A，如果i号槽位有一个对抗性或多个leader, CR如果i号槽位有一个同步leader, C如果i号槽位有一个当前leader, R如果i号槽位有一个中继leader，如果i号槽位没有leader，⊥。
其次，对fork的条件(iv)进行如下修正:(iv)对于任意一对v,v '， wℓ(v)∈{R, CR}和wℓ(v ')∈{C, CR}，其中ℓ(v) +∆≤ℓ(v ')，其长度(即到根的距离)len(v)和len(v ')满足len(v) < len(v ')。
保证金的定义在分叉的新定义中基本没有变化。然而，递归行为依赖于这些更丰富的特征字符串符号的新语义，并显示出一些相当有趣的属性:特别是，C和R符号的效果取决于最坏情况边界当前是负的还是正的。我们将在附录B中详细讨论这一点。
5.3.3替代链和h改善。很容易看出(1)如果在∆同步槽后交付的不是链C非劣链C’，而(2)Praos是一个有利于Fsync的h - improvement环境，则不会违反分叉的条件(iv)。
5.4多时代普拉斯
有两种方法可以在具有演进的权益分布的多epoch设置中使用Fsync运行Praos:(a)在每个epoch中使用不同的Fsync实例，或者(b)定义一个允许改变权益分布的Fsync版本。
当然，概念上更简单的方法是(a)。其思想是，在每个epoch结束之前，开始一个新的Fsync实例。
此时，将在新时代中使用的主索引(包括网络目录、股权分布和随机性)就被确定了。1采用方法(a)将意味着随机覆盖在每个新纪元完全重新采样。实际上，这可能构成一笔不可接受的间接费用。使用方法(b)避免了这个问题，但是使Fsync的定义、实现和证明更加繁琐。
要注意的是，无论在哪种情况下，都必须妥善处理那些被遗忘了一个多时代的诚实的一方。
这些参与方的问题是，一旦它们被掩盖的时间足够长，以致其主索引过时，它们将面临重新连接到网络的困难，因为通过VRF选择的邻居是基于最新的股权分布。文章来源：https://www.toymoban.com/news/detail-783814.html
虽然在实践中这种情况不太可能发生，因为随机图覆盖的演变性质，理论上自适应攻击者可以持续腐蚀一方的邻居，直到耗尽其腐败预算，从而使其在很长一段时间内被掩盖。这个问题可以通过假设一个检查点功能(通过一些轻客户机基础设施实现)来缓解，该功能在一个时代开始之前足够早地向各方提供相关的主索引。文章来源地址https://www.toymoban.com/news/detail-783814.html
到了这里，关于【论文阅读】The Generals’ Scuttlebutt: Byzantine-Resilient Gossip Protocols的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
