DFINITY技术概论系列 共识系统

美SEC再次递交信函望就Ripple案与外国监管机构联系

据U.Today消息,美SEC再次向美国地方法院法官Sarah Netburn递交信函,为其与外国监管机构联系的决定辩护。SEC表示其正在与外国监管机构联系,以确定Ripple是否会影响XRP的表现,而从外汇中获取日内交易数据是确定这一点的唯一方法。

DFINITY技术概论系列 共识系统

DFINITY技术概论系列共识系统

Rev.1

Timo Hanke, Mahnush Movahedi and Dominic Williams


摘要

Dfinity区块链计算机提供了安全、高效和灵活的共识机制。尽管 最初被定义为许可制参与模式,但共识机制本身可以与任何抵 御女巫(Sybil)攻击的方法(例如PoW工作量证明或PoS权益证 明)相结合来创建一个开放的参与模式。Dfinity最大的优势体 现在景富有挑战性的PoS权益证明情况中。

Dfinity的核心包含一个去中心化的随机数灯塔,作为可验证 随机函数(VRF),会随着时间的推移产生一个输出流。灯塔背 后的新技术依赖于具有唯一确定性、非交互式、分布式密钥生成 (DKG)友好的阈值签名方案。这种方案的唯一已知例子是基 于配对的,并且来源于BLS [3,10]

Dfinity区块链构建于Dfinity灯塔之上,并使用该灯塔作为领 导者选择和领导者排名的随机性来源。基于提议区块的领导者 的排名,链被赋予权重,在互相竞争的多条链中,该权重将决定 哪条链胜出。 通过一种公证环节,Dfinityg块链被进一歩强 化,该环节极大地缩短了达成最终共识的时间,消除了 “无利害 关系’问题和“自私挖矿攻击”问题。

通过由随机数灯塔驱动的仲裁组的连续选择机制,Dfinity的 共识算法得以实现高可扩展性。在实践中,Dfinity可以达到几秒 的出块时间,并且只需两次确认便可达成交易的最终性。该系统 能从容处理包括网络割裂在内的暂时网络不同步问题,并且如果 在同步的情况下,它能够被证明是安全的。

1前言

DFINITY是一个去中心化的网络设计,其协议生成一个可靠的” 虚拟区块链计算机”运行在对等网络之上,可以安装软件,并且 可以在智能合约的防篡改模式下运行。目标是使虚拟计算机快 速完成计算(通过使用较短出块时间,且只需少量区块作为”确 认”),提供可预测的性能(保持确认之间的时间近似恒定),以 及随着服务需求的增加,计算与存储能力可以随之无限扩展( 通过使用我们其他论文中讨论的新型验证机制和分片系统)。这 些协议必须足够安全以抵御小于某个关键比例的节点的恶意控 制,必须产生密码随机性(这是高级去中心化应用程序所要求 的),并且随着其数量增长到数百万个节点,也必须保持去中心 化的性质。

Dfinity将在一系列技术概论中被介绍,每一篇概论都强调了 Dfinity的一项自主创新,如共识骨干、智能合约语言、虚拟机、并 发合约执行模型、守护进程合约、对等网络和安全广播、治理机 制和扩展技术。本文将重点讨论共识骨干和密码随机性。

Dfinity在其协议的核心内置了一个公正的“可验随机函数” (VRF)VRF不仅推动了共识,而且还将成为分片、验证塔等扩 展技术的基础。此外,由共识层产生的VRF可用于应用层,即用 于智能合约与虚拟机。如此一来,共识骨干就与许多其他课题交 织在了一起。

2介绍

Dfinity的共识机制有四个层次,如图1所示。第一层提供经注册 的和可抵御女巫攻击的客户端身份(ID) 0第二层是一个去中心 化的随机数灯塔。在第三层的是由随机数灯塔驱动的区块链,随 机数灯塔逋过概率机制进行领导者排名。在第四层是一个去中 心化的公证机制,提供时间戳与发布担保,并設终对近乎即时最 终性负责。Dfinity的共识层与共识机制的其他关键方面可归纳为 以下几个主要类别。

DFINITY技术概论系列 共识系统

第一层:ID与注册。Dfinity网络中的活跃参与者称为客户端。Dfinity中的所有客户端都是经注册的,即具有永久的匿名 身份。客户端注册比典型的基于工作量证明机制的区块链有优 势,在工作量证明区块链中,将不同的块连接到同一个矿工身上 是不可能的。例如,如果注册要求安全保证金,那么作恶的客户 端将丧失其全部保证金,而矿工在典型的工作量证明区块链中 只会在作恶期间损失出块奖励。因此,对注册身份后的作恶行为 的惩罚,可能会远大于对未注册身份时的作恶行为的惩罚。这点 尤为重要,因为这样区块链就可承载超过其原生代市总价值的 外部价值,而不受限于原生代帀的体量。此外,Dfinity通过提供 协议来注册新客户端以支持开放会员资格,该切议通过带有锁 定期的权益保证金注册新客户端。这是第一层的责任。

第二层:随机数灯塔。第二层中的随机数灯塔是由注册客户 端共同生成的公正的可验随机函数(VRF)。直到即将被每个人 都可以使用之前,VRF的每个随机输出都是不可预测的。这是 Dfinity系统的一个关键技术,它依赖于具有睢一性和非交互性 的阈值签名方案。BLS签名方案是唯一可以提供这些特性的实用 方案1,Dfinity具有特别优化的内置BLS实现[2,11]。使用阈值 机制创造随机性解决了关键的遗后一个参与者”问题。任何 去中心化协议在没有阈值机制的情况下产生公共随机性都会遇 到这样的问题:即该协议中的最后一个参与者知道下一个随机 值并可决定中止协议。

第三层:区块链与分叉决认第三层部署了 “概率插槽协议“ (PSP)。该协议针对每一个区块高度对客户端进行排序,此排 序由该区块高度时随机数灯塔的公正输出决定。然后将权重按 照提议者排序等级分配给区块提案,使得来自列表顶部客户端 的区块得到较高权重。分叉间题通过支持拥有“最重的”累积区 块权車的链条得到解决-与传统的工作量证明共识基于最高累 积工作量非常相似。PSP协议的第J个优点是,排名是即时可用 的,这使得可预测的、恒定的出块时间成为可能。第二个优点是 总有一个排名最高的客户端,这允许了均匀同质的网络带宽利 用。相反,客户端之间的竞争则会偏向于爆发式使用。

第四层:公证与近乎即时的最终性。J个特定交易的最终性 意味着一个系统范围内的共识,即一个特定的交易已经被不可 逆转地执行。尽管大多数分布式系统需要快速的交易最终性,但 现有的区块链技术并无法提供。Dfinity在其第四层部署了新的 区块公证技术来加速最终性的达成。公证是由注册客户端共同 创建的某个区块下的一个阈值签名。只有经过公证的区块才可以 包含在链中。在所有提交给客户端进行公证的区块候选者中,客 户端只为排名最高者提供公证,该排名是基于由随机数灯塔驱 动的公开的可验证算法进行的。

需要强调的一点是,公证不是共识,因为由于不利的时机,在 一个给定的高度上可能会有一个以上的区块被公证。这是明确可 以容忍的,并且这是与其他每个区块都使用完整拜百庭协议的权 益证明提议的重要区别。Dfinity之所以能达到高速与极短出块 时间,恰恰是因为其公证并非完全共识。然而,公证可被看作是 乐观共识,因为通常只有一个区块会得到公证。是否只有一个区 块被公证可以在一个后续区块加上一个中继时间之后被检测到( 参见定理9.3) o因此,只要广播网络工作正常,在经过两次公证 的确认加上一个网络遍历时间之后,一个交易在Dfinity共识中便 达成了最终性。

 我们要强调的是,Dfinity的公证不是主要的有效性保证,而是 -个时间戳加上发布证明。公证步骤使得作恶者无法秘密建立 并维系一串互相连接的、经过公证的区块。出于这个原因,Dfin- ity不会受到*自私挖矿攻击” [4]和“无利害关系”问题彰响。

 阈值接力和网络可扩展性。Dfinity的共识是为了在数百万客户 端的网络上运行而设计的。为了在这个范围内实现可扩展性,随 机数灯塔和公证协议被设计为可以被安全有效地委派给一个委 员会。委员会是所有注册客户端的随机抽样子集,它们部署了一 个阈值机制(为了安全),而且是非交互的(为了效率)。

Dfinity中,活跃的委员会是定期更换的。在代表所有客户端 临时执行协议之后,该委员会将执行过程传递给另一个预先配 置好的委员会。我们在Dfinity中称此技术为“阈值接力”。

 一致性与可用性。值得注意的是,Dfinity可以隐式检测到网络 分化,并且迸行保守处理。这是随机抽样选取委员会造成的后 果。如果网络分化成大小几乎相同的两半,则这将自动使随机数 灯塔在几个区块内暂停,从而两边都无法继续。一旦网络重新连 接,随机数灯塔将自动恢复。如果网络分化的一部分明显大于半 个网络,则该协议可能会继续在该部分中运行,但是将在所有其 他部分中暫停。

 网络分化不仅在通信中断时发生。另一个重要的甚至更现实的 情况是,当Dfinity客户端有多个实现时,他们由于代码岀错而无 法达成一致。Dfinity可以从容地处理这种情况。如果有两个客户 端都被均匀地广泛使用,而且他们开始不一致,那么这两个客户 端都将被暂停。如果有多个均匀分布的客户端,并且其中一个开 始与所有其他客户端不一致,那么网络可能会继续,而只有被孤 立的客户端才会暂停。这正是在该给定情况下所需的行为。其他 区块链不能很好地处理这种情况,而这神事件的发生对他们构 成了真正的威胁。原因是这些链条过于强调可用性而非一致性。

文章结构。第3节介绍了协议的高层概览。第4节详细说明了我 们的系统、通信与威胁模型,并介绍了相关的符号°第5-7节详细 描述了概率插槽协议和随机数灯塔协议。第8.1节介绍了阈值接 力技术,该技术允许协议由预先配置的委员会安全地执行,而非 由所有副本执行。第8.2节描述了允许成员随时间推移加入和退 出协议的开放参与模式。最后,第9节提供了Dfinity协议的安全 性和正确性证明。

3共识协议的高层概览

角色。Dfinity的对等网络由通过广播网络连接的客户端组 成,他们可以通过这个网络向所有人发送消息。客户履行三个主 动功能:(a)参与去中心化的随机数灯塔,(b)参与去中心化的 公证,(c)提议区块。客户端还会观察区块,并建立自己眼中的 最终链。

委员会和阈疽接力。为了提高可扩展性,随机数灯塔与公证 由一个委员会管理。在一个小规模网络中,委员会可以是所有客 户端的集合。在一个大规模网络中,委员会比所有客户端的集■合 小,并且在每一轮(即每个区块)都会更改。一轮中的随机数灯 塔输出根据第8」节中描述的阈值接力技术选择下一轮的委员 会。委员会规模是根据失败概率计算来配置的(见第4.2.4节)。

区块排名。如果我们抽象出随机数灯塔与公证的去中心化方 面,那么共识协议便如图2所示。该协议按轮次进行,使得轮次 与链中位置(称为高度)之间存在一对一的対应关系。在第「轮开 始时,随机数灯塔产生一个新的可验证的随机值并将其广播到 网络中(图2,步骤1) °r轮的随机数灯塔输出,由侦表示,确定 了所有注册客户端的优先级。任何客户端都可提议一个区块,但 是客户端的优先级越高意味着该区块得到公证的机会就越高, 并且下一轮的出块者将会建立在该区块之上。

公证。一旦一个客户端看到一个有效的手,它就会将从用户处 收集的交易集中到一个候选区块中,并将其发送给公证人(图步骤2) °公证人等待一个特定的恒定时间(出块时间)来接收 提议的区块。然后,公证人运行基于随机数灯塔的排序机制,选 择排名最高的区块,并对其进行签名和广播(图2,步骤3)。一旦 客户端收到一个已公证区块,他们就会用它来扩大他们的区块 链副本,从而在各自的视图中结束第r轮。最后,随机数灯塔广播 &r+l,标志着新一轮的开始。

去中心化随机数灯塔。随机数灯塔协议是完全去中心化的, 由委员会的所有客户端一起运行。然而,从外部看(即只看产生 的输出和输出的时间),灯塔表现得像一个值得信赖的第三方。 我们强调了委员会不需要为灯塔产生的每个输出运行拜占庭协 议。

 

DFINITY技术概论系列 共识系统

 

 相反,由于我们的阈值签名方案的唯一性,对每个灯塔的输出会 自动达成一致。这解释了随机数灯塔如何能以如此高的速度运 行,从而使Dfinity区块链可以实现如此低的出块时间°

去中心化公证”正如随机数灯塔的情况一样,公证是完全去中 心化的,并由委员会的所有客户端共同管理,其整体行为可等同 于可信的第三方。然而,与随机数灯塔不同的是,公证寻求在实 时输入(一个区块)上达成一致,而不是在伪随机数上。此处没有 可用的“廣法”密码术,所以一个完整的拜占庭共识协议将是唯 一选择。但是,Dfinity的公证机制没有这样做,而是只运行一个 乐观协议,它可以在“正常运行”情况下达成共识,虽然有时每轮 可能会公证一个以上的区块。如果发生这神情况,Dfinity的链条 排名算法将会处理这个分叉,并且最终性可在随后的正常轮次中 得以实现。乐观协议是非交互式和快速的,因此公证可以以与随 机数灯塔相同的速度运行。

4模型与准备工作

4.1系统模型

4.1.1副本。从现在开始,我们把客户端称为副本,并把它们分 别添加标记1,2, … £ NoU为所有副本的有限标签集合,

称为总体。每个副本i € U有一个公钥/私钥对(pkz, sk/) o我们 假设集合{pki I惟叫是已知的并且被所有的18同意2

4.L.2认证。每个协议消息都由发布该消息的副本签名。只有一 个消息由sk;,/e u中的一员签名的时候,副本才会接受该消息并 随之行动。

4.」.3组。在任何给定时间,一些或所有i € U被排列成一个或多 个子集G1,G2, … € U,称为组.其中的一组,即委员会,将积极 推动进展,并确保达成共识。我们假设所有组G具有相同的大小 no数字n是一个称为组大小的系统参数。

4.1.4同步性。对于Dfinity的实际应用,我们假设一个半同步网 络,我们的意思是网络遍历时间可以用一个概率分布已知的随机 变量丫

来模拟。然后,Dfinity协议根据Y的分布和系统的安全参数 选择两个系统范围内的超时常量BlockTimeT.在第9节的正式 安全分析中,我们给出了同歩情况的证明,其中丫的上限△是已知 的。

这两个常量分别负责活跃度(BlockTime)和系统的安全性(T)。超 时时钟基于本地事件被触发,即接收的消息。该协议不依赖于全 球时间,也不假定副本之间有同步时钟。

该系统按轮次演化。副本基于事件进入到下一轮。不同副本间的 的轮次不会同步。

4.2威胁模型

421拜占庭副本。忠实地遵循该协议的副本被称为“诚实”, 所有其他副本都被称为“拜占庭”。拜占庭的i£U可能出现任意行 为,例如,它可能拒绝参与协议,也可能与其他副本合谋对系统 发起协同攻击。

4.2.2对抗§堇度。对于任何G c U,f (G)表示G中的拜占庭 副本。

假设1.有这样的8>2

lUl>Bf(U).(4.1)

描宏新为说够家在实践中,假设1是通过经济激励与抵御 Sybil攻击3的一种形式来实现的。

4.2.3诚实组。n是组的大小。那么一个组G被称为诚实的, 如果

n>2f(G).(4.2)

5-7节中描述的协议依赖于

假设2.系统中使用的每个组G都是诚实的。

4.2,4随机样本。基于假设1,总体U是诚实的。系统中使用 的每个组G £ U是从U中抽取的大小为n的随机样本。给定n,概 率Prob[G honest]可以如下计算:

命题4.1.CDWx, n, M, N)表示超几何概率分布的累积分 布函数,其中N是总体大小,M是成幼次駛,n是样本大小,x是 每个样本允许的最大成功次数.那么

Prob[G/7O6sA=CDFhg(M/2i—(4.3)

给定一个可接受的关败槪率Q,我们可以求解(4.3)最小组大 小n = n(色Q, |苗),

Prob[G honest] > 1 – p

对于每个随机样本GqU且|。|=爪 示例值I S=104的结果. 与赋予Q和13不同值的结果,如下图3所示。

DFINITY技术概论系列 共识系统

随着总体规模增加到无穷大,超几何分布收敛于二项分布。因 此,当1圳增加到无穷大,我们得到

命题4.2CDFbinom(xnp)表示二项式概率分布的累积分 布函数,其中p是每次抽取的成功概率,n是样本大小,x是每个 样本允许的最大成功次数。那么

Pmb[Ghonesf > CDFbinomf -1, n, 1/冏.(4.4)

给定Q,我们可以求解(4.4)得到。,并得到最小的组大小门心

动,使得对于IS的所有值,Ng n[B,prU] 0

Q和8取不同值的结果如图4所示。可以看出,在Q所取的范围 内,组的大小在-1。。2 Q上近似线性。所得到的组大小对于本文 描述的协议是切实可行的。5

 

DFINITY技术概论系列 共识系统

425自适应作恶者。我们假设作恶者是轻度自适应的。这意味 著作恶者可能会自适应地破坏组,但这种破坏所需时间比组的活 动周期要长。

4.3密码学原语

4.3」哈希函数。假设我们有一个抗碰撞散列函数其搞要的 比特长度为/,且其中与安全参数湘匹配。

4.3.2伪随机数。假设我们还有一个加密安全的伪随机数发生 

PRG,它将一个种子秉换为一组值的序列PRG(。/),其中/- 0,L….

4.3.3 伪随机排列。序列PRG&, i)可用作Fisher-Yates shuffle [9,算法3.4.2P]的输入来生成U的随机排列。结果是一个双射映 射{1 U}-U,我们用PermU 表示。

4.3.4Diffie-He!!mono我们假设恶意攻击者的计算是有界 的,并且Diffie-Hellman的计算问题对于参考文献[2]中有配对 的橢圆曲线是有难度的。

4.4 Dfinity的区块链

我们现在正式定义中个区块链的概念。

4.4」区块

定义4.3.—个区块是一个特殊的创世区块或是一个元组(Q£ Z, do),其中q e {0, I}1是前一个区块的哈希引用,「丘N是轮次,z € {0, 1?是对前一个区块的公证,d € {0, 1}*是数据有效负载

(“交易”和“状态”),准U是创建者(或“所有者”)。公证是 一个由“公证大’创建的上一个区块的签名。对于一个区块8=(Q r,z,d,&我们定义

prv B:= p, nt B := z, rd B:= r, dot B:= d, own B:= o.

我们强调,一个区块包含它所引用链中前一个区块的验证z

4.42 

定义4.4,C的意思是,一组有限序列的区块Br},

对于所有i,Bi=i]对于所有Q prv Bi= H”),并且对于所 有,>0,8-的一个有效签名。第一个区块伽是创世区块。

最后一个区块&被称为C的头部。我们定义

lenC:= r+ ], genC:= Bo, headC:= Br.

由于链中的区块通过加密哈希链接,所以一条链是一个经过 验证的数据结构。一条链完全由它的头部决定,根据

命题4,5.生成两条链C^C 且headC= headC’,这在计 算上是不可行的的。

定义我们把唯一定义的链演为。(钧,且headC= 8。 给定两个链C, C’,如果C是b的前綴,我们则写C<C

假设从现在开始,所有链都有同一个创世区块B0

定义4.7对于任意区块非空集合我们把所有链C(B)BES的最 大公共前缀表示为C (S) °

C (S)之所以被定义,是因为每个C (B) , B6S,都包含创世区 块。对于任意区块集合$, T,SCT,我们有C⑴<C (S)。假设 prvS := (prv B | B € S  {BO}} 0 .那么

                      C(prvS) < C[S)                   (4.5)

5概率插槽协议与公证

如在第3节中所解释的,每个协议轮都会经过如下步骤,生成随 机数灯塔输出⑴,生成区块提议(2),以及生成区块公证⑶* 由于不止一个区块可能会被公证,只经过上述步骤本身并无法提 供共识。此时便需要概率插槽协议(PSP)

基于区块权重,PSP允许副本决定当他们提议新区块时,要选 择建立在哪条链上。随着时间的推移,这导致了对链前缀的槪率 共识,在这种情况下,一条链的权重越大,则达成最终一致性的 可能性越大。这与工作量证明的链相似,即某条链上的的工作量 越大,则达成最终一致性的的可能性越大。然而,Dfinity并没有 在此停留,也不依赖于这种概率性的最终性决策。PSPR是用来 指导区块提议者。至于最终性,Dfinity通过使用公证协议有更快 的方法。

在此部分,我们假设随机数灯塔滇后在第7节中介绍)正常工 作且无失败,并为所有副本在每轮r开始时提供一个新的无偏差 随机值图5显示了协议如何在扩展区块链和扩展随机数灯塔 链之间交替,并演示了随机数灯塔、区块提议者与公证如何按部 就班地前进。

然而,对于本节的阐述而言,随机数灯塔的去中心化本质与精 确的内部工作原理是无关紧耍的。因此,我们只需简单地把序列 夂视为已知,而不作进J步的假设。

关于威胁模型,我们对所有组作岀假设(4.2),如在假设2中所 述。不过,对于公证协议的描述与理解而言,可以假设只存在一 个组,它由副本U的总体组成,并且

U>2f[U}.(5.1)

为了说明简单,我们采用这种观点。那么很明显,本节所述的 协议可以委托给任何诚实的委员会或一序列诚实的委员会。

5.1区块排名与链的权重

基于5,协议为每个芷峪配一个排名,并且提议者的的排名定 义了该区块的的权重.如下所示。

定义5」(副本排名)。r轮排名的的排列定义为〃r:= PermU (0)。第r轮中i£U的排名定义为77•侦7

定义5.2 (区块排名)。区块8的排名定义为rk8 :=m(own 8),其 中r= rd Bo如果rkfi < rk S’,我们则说BB’有更高的的优先 级。

DFINITY技术概论系列 共识系统

DFINITY技术概论系列 共识系统

如果一个作恶者模棱两可,那么会在同一轮出现相同排名的多 个区块。

我们假设协议已经定义了一个单调递减函数”。特别是.对于 Dfinity,我们将w实例化为网启=2%

定义5.3 (区块权重)。一个区块8的权重定义为wt8:=w(kB)

定义5.4 (链的权重)。一条链C =(B0,•…,Br)的权重定义为 wtC £;=o :=wt&,。如果wtOwtC’,我们则说。比另一条 链C,重。

5.2区块提议

在每一轮,每一个副本都可以提议一个区块。为了这样做,在第「 + 1轮,副本选择最重的有效&链公在它视野中len C=「(参见图 6) o然后,副本会考虑从用户处接收到的所有新交易。新提议的 区块躬Ehead净由选定的交易构成。该副本会广播位,以获 取公证委员会的公证。

6区块的有效性在走义5.5之后解释。一条链是有效的.当且仅当它的所有区块都 是有效的。

5.3区块公证

公证的目标是为了确保链条只是由发布于各自轮次中的区块建 立起来的,而不包含之后的的区块。换句话说,公证可以防止作 恶者建立一条私有的冲突链,并在以后公布。公布得太迟的区块 不能再被公证,由此,区块提议的及时发布得以确保实施。所以, 一次公证被视为一个时间戳,同时也是一种发布证明。

该协议保证对本轮多个提议的链头中的至少一个进行公证。 它试图每一轮正好公证一个链头,但无法保证这一点。因此,公 证并不意味着共识,也不需要共识。

 当参与公证协议时,副本只关心能否延长至少一条有效的链, 而不关心哪条链取胜(这是第6节最终性讨论的主题)。

  定乂55区块8的公证是由U的大多数子集在消息B上的一个集 合签名。如果一个区块已经接收到至少一个签名,我们便称它为 已签名的,如果它已经接收到一个公证,则将其称为已公证的区 块。一个已公证的的区块是一个与自身的公证连接在一起的区 块。

  如下面的AIQ.1所述,每轮中的每个副本「从所有副本(包括自 己)处收集所有有效的出块提议,该过程在在一段固定的时间內 进行,即所谓的BlockTime。一个被提议的区块B被认为在第「轮 是有效的,如果rd B = r,并且存在一个有效的区块B,,满足

(l)prv8=”(B‘)rd B’=rd B- 1,

(2)nt B8’的一个公证,

(3)datB是有效的7

BlockTime之后,副本为其接收到的当前轮次所有最高优先级 的的区块签名,并将该区块的签名消息广播给整个网络。

 不止一个区块可以具有最高的优先权,但只有在出块者模棱两 可的情况下才会出现。在这种情况下,所有模棱两可的区块提议 都会被签名。这不是一个问题,因为下一轮的每个诚实出块者都 将只会建立在其中一个区块上。

7dot B设立有效性标准是可选的,并且不是共识协议所必须的.例如,根据区块 键的应用,只有在dot B表示有效的交易并且是从dat B’转换的有效状态时,才可 以将dat BES为有效。从共识协议的角奁来看,dat B是任意数据。

副本在BlockTime之后收到更多区块提议,它继续为所有最高 优先级的区块提议签名。当观察到当前轮次的验证时,副本则前 进到下一轮。

Algorithm 一 Block Notarization

Goal: Notarize at least one block for the current round.

1 Initialize chain with the genesis block

2 r«-1- initialize round number

3 while true do

4 Wah(BlockTime)

5: while no notarization for round r received do

6 B *- set o^ all valid round-r block proposals so far

7 for All £ – B with minimal rk B do

8if B not already signed then

9o •- Sign

10Broadcast^)

11:end if

12 end for

13: end while

14 r r + 1

15 end while

5-4公证的属性

5.4.1活跃度。从上面的描述可以清楚地看出,算法1不能死锁- 即使有作恶者存在也是如此。每一个副本继续为最高优先级的 区块提议签名,直到观察到当前轮次的公证,这样便足以保证在 当前轮次至少有一个区块被公证。这终将会发生,因为(5.1)在 此成立,并且排名为这些区块提议确定好了顺序。在观察到当前 这一轮的第一个公证后,副本可以安全地停止签名,因为被观察 到的公证会被重新广播,并最终将到达所有诚实的副本处。因 此,所有诚实的副本将前进到下一轮。


  上述观点依赖于对区块提议和公证的传播假设。我们将详细 分析这些内容,包括涉及到的中继策略,并在第9节中为活跃度 提供正式的证明。

5.4.2诚实签名的区块

定乂 5.6 一个区块被称为被诚实地签名,如果它已经从一个 诚实副本处接受到至少一个签名。

注意,一个诚实的副本ZR在下述情况中才会为8签名,即只有 在一个轮次中BlockTime过后的某一时间点,当樓魂野中的最 高优先级的区块提议时。诚实签名区块的概念是一个理论上的 概念,它是用来讨论公证协议的安全属性的。我们无法知道一个 给定的签名是由一个诚实的副本还是拜占庭副本发岀的。因此, 签名的区块是否是一个诚实的签名区块是不可观察的。

5.4.3及时发布

定乂5.7第1轮的一个产物是及时发布的(0轮内),如果在它被 广播时,至少有一个诚实的副本在本轮次

一般来说,诚实的副本会重新广播他们签名的每个区块。因 此,

只有及时发布的区块才可以被诚实地签名。(5.2)

 给定一个已签名的区块,我们不可能知道该区块是否是及时发 布的,因为无法判断它的签名是否诚实。这与我们接下来会解释 的已公证区块不同。

5.4.4公证扣留。根据(5.1),任何副本的大多数子集包含至少 一个诚实副本。因此,我们有

           只有被诚实地签名的区块才能被公证。(5.3)


 我们强调指出,作恶者可以在一个诚实签名的区块下扣留自己 的签名,这可能导致一个诚实签名的区块在公众看来未被公证。 然而,作恶者可以使用自己的签名在之后的任意时间点来生成和 公布公证。

545强制发布。根据(5.3)(5.2),

只有及时发布的区块提议才能被公证。(5.4)

 然而,尽管(5.4)成立,公证依旧可以被扣留。为了表明扣留公 证是无害的,我们引入另一个理论上的概念:

定义58 一个公证z是被引用的,如果存在一个已公证的区块nt B= Zo

请注意,发布区块應味着发布前一个区块的公证nt B,因为nt B包含在B中。因此,(5.4)意味着

只有在1轮内及时发布的公证才能被引用。(5.5)

显然,在一条幸存的链中,所有的公证都被引用。因此,出块提 议与公证的发布都被确保强制执行了。一个作恶者无法建立一条 私有链,因为一条链只能在下列情况下才能存活:

•它的所有区块都被及时发布。

・它的所有公证都在1个轮次内被及时发布。

5.4.6共识.如上所述,一条链只有在它的所有公证都在1个轮次 内被及时发布才能存活。这意味着正在观察第r轮公证的副本可 以将自己限制于一定的时间窗口内。在此窗口之后接收到的所有 关于r轮的公证对于幸存链来说都是不相关的。这个事实对于下 面第6节介绍的最终一致性算法来说至关重要。参见图7示例。

该事实有多种方式可以使共识达成。注意,对达成共识而言, 在一轮中只有一个区块被公证,或只有一个单一的公证可以被引 用都不是必要条件。对共识来说,在时间窗口内接收到的所有公 证都(间接)引用一轮(或多轮)前的同一区块便已足够。

5.4.7正常运行。

定义59如果在一轮中只有一个区块得到了验证,那这一轮在 正常运行。

算法1致力于通过实行BlockTime的等待时间,和通过给予最 高优先级区块优先权来实现正常运行。

如果最高优先级出块者是诚实的,且BlockTime足够大,那么 最高优先级区块提议将在BlockTime到期之前到达所有的诚实 副本。这意味着只有一个区块可以在这一轮被验证。因此,假设 引ockTime被选择正确,算法1将在每个最高优先级出块者是诚 实的轮次中实现正常运行。

我们会把广播网络的内部工作,比如接力政策,纳入考虑,然 后详细分析BlockTime “足够大”是什么意思(见第9节)。我们 将展示如果网络的逼历时间是以△为界,那么在BlockTime3Zk Alg.l是正确的。(推论9.16,命题9.24,命题9.27)

请注意,每个正常运行的轮次都会产生共识。该共识出现在唯 一的,在该轮次被验证了的区块上。然而,因为验证扣留的可能 性的存在,正常运行是一个无法被观察到的理论概念。幸运的 是,正如我们在5.4.6节中所见,正常运行并不是共识的必要条 件。

6达成最终一致性

副本会用在Alg.2中描述的达成最终一致性的过程来识别出共识 点。对于这个过程,仅仅观察已验证的区块就足够了。换言之,区 块提议下和其下的个人签名可以被忽略。达成最终一致性的协议 是被动的,并且独立于验证协议。由于它可以由任何能够访问已 验证区块的人(在副本之外)来执行,我们在这一节会用观察者 而非副本表述。

6.1说明

算法2做出以下假设:在已经收到了第「轮的第一次验证之后,观 察者会收到所有第E轮的能够在时间泛前被引用的验证。此 假设等同于Alg.2的正确性.并且被定理9.18证明适用于所有副

0

Alg.2的大意如下:我们持续地收集所有经过验证的区块并且按 照他们的轮次数将其归入不同的bucket里。令M为第「轮所有已 验证区块的buckets

多个bucket可以被同时填充。就比如即使当M +1已经不是空的 T,第二个区块依旧可能会进入M。然而,除非知道它的前任区 块,不然一个区块是不能被验证的。因此,我们假定对于每一组 互相引用的区块,前任区块会首先被处理。这样的结果是”必须 在M+1之前收到它的第一个区块。

通过我们最初的假设,对于每个厂轮来说,都存在一个时刻,在那 -刻我们不再为N『接收更多已验证的,可以被引用的区块。那时 我们便能使第盗“达成最终一致”,因为我们知道M已经包含了 所有能够在厂轮后依旧存在的链端。因此,我们可以输出最长的 通用前缀C (N「)作为结束。

DFINITY技术概论系列 共识系统

t> 

6.2达成最终共识的属性

我们需要强调:在使用BlockTime和元间是有一些显著的差异 存在的。BlockTime是在协议规范中协定的,且它是协议规范的 -部分。而每个观察者可以指定自己的7;公证协议只需^Block- Time,不需要7■。达成最终一致性协议只需要7;不需^Block- Time

以下关于Alg.2的假设。也被称为正确性假设:

FINALIZE (丹正在被执行时,Nh包含所有可被

引用的轮次力的区块。(6

命题6」假设(6.1)成立。那么Alg.2中的链C是只可附加的。 该断言证明我们可以认为在Alg.2中的链已达成最终一致性。

证明:在一次执行Alg.2中,令6, E,分别成为Finalize (h)Finalize (h+1)反馈的链。令可;表示t时刻的集合 显然,M可以随着t增长而增长。设to,七分别为Finalize (h) , Finalize (h+1)被调用的时间。由(6.1)可知,所有在to之后添加到 Nh中的区块都不能被引用。换句话说,无论Nz在何时被考虑我 1′『都有

我们将会展示如果网络遍历时间是以△为界,那么当,则 (6.1)成立(定理98,命题9.25)。值得注意的是,这个结果没 有对BlockTime做出任何假设。换言之,即使公证人选择了一个 错误的BlockTime值,这个结果依旧成立。

在另一个版本的Alg.2中,参数T不是必须的。在第10行,另一 版本即刻就可以调用Finalize (r-2),而不是在距离现在T的时间 调用Finalize (r-1) 0这杨同样能按照推论9.19来确保(6.1),不 过它需要一个被公证人使用的BlockTime值的假设。

7去中心化的随机数灯塔

去中心化的随机数灯塔协议(DRB)允许副本对可验证随机函 数(VRF)达成共识,并在每一个轮次共同产生一个新的VRF的 输出。我们说VRF是一个确定的、伪随机序列(盘r.M的特征值。 在已知所有先前的输出如. . .,的条件下,每一个输出的女都 是不可预测的,并且每一个殮岀的正确性都是可以被任何一个 人拿来与特征值进行公证的。特别是由于其确定的、伪随机性的 本质,VRF的输出是无偏差的。在我们的去中心化协议中,在至 少一个诚实副本前进到第「轮之前,输出的聽不能被恶意攻击 者所预测的。

关于威胁模型,我们对所有的组进行(4.2)中的假设,就 如假设 2里提到的一样。为了简化说明,我们会先描述单个组 G, G=nn>2f(。,的随机数灯塔协议。然后该协议可以适 应于被变动的组所执行,如下面第8.1节所述。

我们的DRB协议使用了唯一的,由组從I]造的4。”阈值签名 (见7.1小节)来作为其随机性的来源。如果恶意攻击者是不 能预测这样一个签名的输出的。如果攻击者则不能阻止 这个签名的产生。如果恶意攻击者可以通过阻止一个签名被创建 来中止协议,那么任何重启或回退机制将不可避免地把偏差引入 到输出序列里%我们平等地对待这两种失败(预测和中止)°以 此,我们要求te[f+J, n-f]0需要注意的是如果我们设n=2t-l, 那么这两个条件都会相当于恁t-

DRB协议中使用的阈值签名方案被设置成使用分布式密钥生 成机制(见7」.4),该机制不依赖于被信任方。下面,我们 首先介绍关于我们使用的阈值加密技术的一些重要背景资料。

7.1阈值加密技术的背景介绍

7.U阈值签名。在仃,门)阈值签名方案中,。个参与方共同设 置一个公钥(组公钥),每个参与方保留一份个入秘密(密钥份 额)。在此设置之后,。个参与方中的今参与方是创建一个经由 组公钥可验证签名(组签名)的充分且必要条件。

7丄2非交互性.如果对于吩参与方中的每一方米说,创建组签 名的过程只涉及一轮单向的沟通,那么一个阈值签名方案可以被 称为非交互的。通常在非交互的方案中,每个参与方使用其个人 秘密创建一个签名份额,并将此签名份额发送给一个第三方。一 旦第三方收到盼有效的份额,它就可以在无需进一步交互的情 况下还原组的签名。举例来说,ECDSA可以被变成一个阈值签名 方案(凶),但它并不具有非交互性。

ZL3一性。如果对于每个消息和每个公钥来说,只有一个签 名可以验证成功,那么这个签名方案被称为唯一的。该属性同时 适用于单个签名方案和阈值签名方案。但对于阈值方案来说,它 有额外的要求,即签名必须不能依赖于参与创建签名的年参与 方的子集。换句话说,在一个唯一的阈值签名方案里,不管谁签 名,由此产生的组签名将永远是一样的。

“唯一性”是一个比“确定性”苛刻得多的属性。一个签名方 案可以被称作确定的,如果它的签名函数不涉及随机性。请注 意,“唯一性”是一个验证函数的属性,而“确定性”是一个签 名函数的属性。唯一意味着确定性的存在,但反之则不成立。例 如,DSAECDSApJ以通过重新定义签名函数使它们变得确 定。方法就是通过消息中的加密哈希函数,夕卜加密钥,使函数确 定地导出所谓的“随机鶴”,而不是随机选择这个顧。但是, 这种技术不能使DSAECDSA唯一,因为不能将k值暴露给验证 函数。

7.L4分布式密钥生成(DKG)。对于给定的仃,ri)阈值签名方 案,一个DKG协议允许■个参与方的集合共同生成该方案所需的 密钥(即,组公钥和个人密钥份额),而无需一个信任方的帮助。

请注意,DKG协议不仅仅是一个秘密共享协议。在秘密共享协 议中,秘密份额可以用来还原组的秘密,但这只能使用一次。在 所有人都知道组秘密之后,这些份额便不可重复使用。但是在一 个DKG中,份额可以被无限数量的组签名重复使用,并且组密钥 不需要被明确地还原。

DKG协议对于基于离散对数的密码系统来说是相对直截了当 的。DKG通常应用多个可验证的秘密共享协议(VSS)的实例。 如[7]中所述,Dfinity使用的是如[刀中所描述的MJoint-Feld- manB DKG9

8—些现有文献中的提议会因为单一方案止协议而容易产生偏差。例如,Algorand [8. §5.2]描述了一种不可避免地带来偏差的回退机制。RANDAO卩]依靠博 弈论激励法来防止恶意行为春中止协迅 然而,在实践中,悪意行为者向随机性中 引入偏差所荻得的收益是无界限的,而对中止的惩罚是髙界限的。

9从[句中可以知道,恶意攻击者可以使由J1 nt-FeldmanDKG生成的公制分配产 生偏差。但是,这种偏差一般不会减弱已生产的公钥的DLP的硬度([& §5])。因 此,为了使我们的协议简単.我们还是使用了原始的,未经修改的」oint-Feldman DKG”更是有改进存在使其可以避鱼偏差。

7.2 BLS签名方案

在已知的签名方案中,唯一具有唯一性及非互动性阈值版本 的,同时又允许一个实用、高效的DKG的,只有源自BLS的基于配 对的方案[3]BLSBoneh, LynnShocham发明于2003年, 与它相关的信息可以在[10]中找到。我们会在本文中使用原始的 BLS方案。

7.2.7BLS函数。假设我们已经生成了一对密钥/公钥(sk, p- Q ,BLS提供以下功能:

⑴签名(m, sk):用密钥sk签署消息m并返回签名

(2)验证(m, pk3 ct):用公钥PK验证消息m的签名。,并反馈 真或假。

在幕后,BL&使用非退化的双线性配对

e : Gi X G2 – Gr

这个配对在合适的椭圆曲线点的循环子群G, G2之间,并取 值于一组单位G冲。我们会在本文中把所有组用乘法写出来。对 于每个组,我们确定一个任意的发生器g2£G2,。正Gr. 我们也假设一个哈希函数間:{。,1}* – Gi,G中取值。

密钥是标量,公钥是G2的要素,签名是G1的要素。函数 Sign(msk)用于计算函数Verifyfm, pk,可用于测试 e(a g沪或pk)是否成立。

722阈值BL5。我们将BLS的阈值版本称为TBLS。为BLS定义的 函数SignVerify也也适用于TBLS中的密钥/签名份额与组密钥/ 签名。我们假设在(t, n) -DKG中的所有参与方被编号1

在像(7.1.4)中描述的一样运行DKG后,(t, n) -TBLS额外提 供了以下函数:

⑴ Recover”:,…, it, an ait):从签名份额ui/[j= 1,.. .,t)中还原组签名5其中67是由参与方代(1 用提供的。

由于唯一性,Recover的输出不取决于来自于组的哪个粉额 被用作ItA. RecoverG1中的点计算”拉格朗日插值33。索引 数组。 疗必须两两不同,Recover函数才可成功。

7.3随机性生成

随机性的生成包括:a) 一个一次性的设置,DKG在其中运行, 和b) 一个重复的签名过程,该过程会产出输出。DKG是缓慢的, 且需要协议,与其相反,重复签名是非互动且快速的。

73/设置。在设置阂值签名方案时,我们不想依赖任何可信任 的第三方。因此,组供为BLS运行DKG,从而在区块链系统的初 始化阶段设置组公钥和密钥份额。阈值t是一个设置的参数。

-旦DKG成功完成,它会输出一个公开的验证矢量Vg£ G2t, 并且给每个副本/ € G留下它的密钥份额京&尸验证矢量Vg被提 交并记录在区块链中,例如记录在创世区块中。 令Vg = (v0, vt-1)。组公钥是pkG =v°£ G2a 与pkG对应的 密钥狄G不会被G中的任何人明确地知道,但可以通过skG,被间 接地使用。验证矢量VG可以用来还原与sksM应的公钥份额 pkG,MG2,逋过哆项式”替换

t-1

p^j=€ g2.

k=0

因此,i生产的所有签名份额都可以与信息Vgi进行公开验 证。组公钥pkG可以用于验证Recover函数的输出。

7.3.2签名流程。回想一下,当看到第E轮的第一次公证,一个 副本就会进入第r轮。在它的第「轮的开始,副本i£G计算签名份 额

C=$ign(r|| sks,/],

其中A是第「T轮的随机值。作为引导,我们设切代表一个空 袖数,例如字符串“Dflnity”的哈希值。然后,副本广播

如上面7.3.1所述,任何接收这些数据的副本都可以通过公共 信息VG验证网)。如果验证有效,那么副本会储存并且重新广 播(1只要一个副本已经收到至少t个不同的、有效的签名份

额,它就会运行函数Recover(/7, …. it, (Jr,a st)来计算 组签名CTGJ。最后,第I■轮的随机输出侦被计算为<7G,的哈希值。

我们强调签名流程是非交互式的。任何第三方都可以在与足够 多的份额进行单方面的沟通之后完成还原。

8可扩展性

8.1阈值接力

出于可扩展性的原因,第5-7节中的公证和随机数灯塔协议将由 多个规模为n的组去执行,而不是由U里所有的副本去执行。否则 的话,随着总体副本数量的增长,消息的复杂性将没有界限。 这些组,在这里又被称作11委员会“,是来自于整个总体U的大 小为n的随机样本。组的大小n是-个系统参数,该参数是根据 4.24节中的失效概率分析来选择的。一个足够大的组规模确保 T,在一个可接受的失效概率内,系统中使用的每个组都是诚实 的(假设2).

Dfinity随机采样副本并将其分组,安排这些组为阈值操作做准 备,选择现任的委员会,并从一个委员会传递到下一个。这样的 -整套机制被称为阈值接力。

8.1.1组的派生。设n是组的大小。该 组是从随机种子&派生出来的,其中第i个派生组是

Grouplf,/) := Permll (PRG(f,/))((!削.(8.1)

在系统开始时,我们选择一个数字m和一个神子&来形成组

Gj:= Groupffz/), j= ]m. (8.2)

每个G运行小节兀3中所描述的DKG来创建组密钥pkGi,然后 OkG将被存储在创世区块中。

82委员会的选择。序列(早通过定义显的初始值来自举。然 后,在第『轮中.我们选择

:= Gj, i: = &mod m(8.3)

来作为第r轮的委员会。同一个委员可以被用于同一轮的公证和 随机数灯塔协议。

在随机数灯塔协议中,G”丿的成员联合生成输出侦,然后用它来选 择下一个委员会G”珂。由于活动从一个组传递到下一个组,我 们把这个机制称为“阈值接力”。

8.2开放的参与

去假设在协议的开始所有副本的集合就已知是不切实际的,尤其 是在Dfinity的公链中。本节将阐述Dfinity的协议如何采纳一个 开放参与的模型,在这个模型里,新的副本可以加入系统,现有 的副本则可以离开系统。

82】纪元(epochs) P我们把这些轮次分成长度为幽不重叠 的纪元。/是系统参数并且是固定的。在每个纪元的第一轮产生的 区块是一个注册表区块(也称为关键帧),它包含一个摘要。这个 摘要记录了所有在上一个刚结束的纪元中新注册和撤销注册的 副本。请注意,此摘要是上一个纪元中所有区块的一个确定性的 结果,它使得关键帧的出块者没有机会去审查注册。第一个纪元 的第一轮是DFINITY的创世区块,同时它也是一个关键帧。

8.22副本的注册。一个副本可以通过提交一个特殊交易来请 求加入网络(即注册)或离开网络(即撤销注册)该交易被提交 给现有的副本,它像任何其他用户交易一样被包含在链中。一个 注册交易包含新副本的公钥外加一个认可,即证明这个新副本是 被允许创建的。取决于底层的抵御sybil攻击方法,这个认可,可 以是一个锁定的权益保证金证明,可以是工作量证明益智塔的答 案,或是来自中央的的、可信任的权威机构的证书。

823组的注册。在一个纪元e电第一轮的随机数灯塔输出定 义了所有在这个纪元被允许新进入系统的组的构成。一个系统参 数mmox管辖着在一个纪元中能有多少个不同的组可以形成。

I■成为纪元e的第一轮。对于每个jwmmax来说,第j个候选组 将被定义为G = Groups G组的成员运行J个DKG来建立 一个组公钥如果这个DKG成功,那么组成员为G创建一个 注册交易,该交易包含元组x = (e, /xG的绝对多数

签名后,任何成员都可以提交x来加入区块链。x的签名的有效性 是公开可证的,因为可以根据区块链上已有的信息进行验证,比 如,活跃的副本池U和定义了这个组的随机数灯塔输出払只有在 它包含在一个纪元e中的区块里的时候,一个注册交易x才有效。

如果DKG或者x未能从G那里获得绝对多数签名或者x不包含 在纪元e内的区块链中,那么G不能注册。一个恶意攻击者可以导 致注册失效。比方说,如果绝对多数被定义为总数的2/3,那么一 个控制着>1/3G的恶意攻击者就可以拒绝x之下的签名。但是, 由于差异,这只会发生在一些候选组之中。例如,一个控制着小 于1/3U的恶意攻击者,将会在至少一半的组里有着小于1/3的控 制。

在几个固定的纪元后,组会过期并且自动撤销注册。这个固定纪 元数量由一个系统参数定义。

824延迟的激活。如果一个新身份(副本或组)的注册被包括在 纪元e的链中,那么这个新注册的客户端将在纪元e+2中激活。 因此,在一个新客户端的注册和其第一个活动之间,总是有至少 I轮的差距。这一系列事件如图8所示。

这个差距确保了只有当所有新客户端的所有注册达成最终一致 性之后,他们才允许对随机数灯塔有任何影响。I的最小值可以 从最终链的成长性中导出。最终链的成长性于下文命题9.24中被 证明。

Dfinity使用的/值远远大于最低要求,因为我们想限制关键帧产 生的速率,从而减少所谓观察“轻客户端”们的负担。

9安全性分析

在本节中,我们会展示Dfinity协议为我们提供了一个强大而快速 的分布式公共账本的抽象概念。任何账本必须满足以下两个基 本属性,我们将会这从9.4节的底层属性中推导出这两个基本属 性。

定义9.1 (账本的属性)。

。)延续性。一个交易一旦被纳入一个诚实副本的最终链里,它将 被包括在每一个诚实副本的最终链里。

b)活跃性。所有来自诚实方的交易在最后都会被包含在最终链 中。

Dfinity和其他账本的区别在于它有近乎即时最终性。该属性由以 下定义和定理形成。

定义9.2 (确认次数)。如果一个交易包含在一个经过公证的区块 X中,且存在有一条拥有形式为Br Br+n-l}公证区块的 链,那么我们说这个交易有n个确认。

请注意,该定义泛指任何被副本所知的公证区块,不一定只是达 成最终一致性的区块。

定理9.3 (主定理)。在第r轮正常运行下,对于每笔在第「轮区块 里的交易,都能在两个确认加最大网络往返时间2△之后达到最 终一致性。

从随机观察者的角度来看,主要定理意味着:假设一个观察者看 到一个交易x已经收到了两个确认,即第r轮的一个包含x的已公 证区块位,和另一个有着prv Be =疥的已公证区块位+為如果轮经历了正常的操作,那么在2△时,即在观察者收到了8s的公 证之后,最终确认的算法(Alg.2)将确保把&添加到观察者的 最终链上。我们在这里假设Alg.2里的T被设为2△。主定理的证 明会在下文9.3节中。

在网络遍历时间△的上限是已知的条件下,我们将为同歩模型提 供证明我们假设处理消息的时问被包含在了网络遍历时间中。

DFINITY技术概论系列 共识系统

9.1广播和处理

安全性分析必须考虑到广播网络的行为,广播网络执行一个 Gossip协议。尤其是被应用于消息传递的接力政策对于我们结 论的可证性是必不可少的。

 副本不断接收新的协议产物,例如区块提议,区块提议下的签名提议、公证、已公证的区块或是随机数灯塔输出。一旦产物 被决定是有效的,并且如果它遵循下面定义的接力政策,它会 立即被传递(gossiped)

到副本的节点那里。

定义9.4 (接力政策)。所有诚实的副本传递以下产物

a)对当前轮次:有效的区块提议和区块提议下有效的签名

b)对任意一轮:公证和已公证区块。

如果一■个产物已经被所有的诚实副本收到,那我们说一个产物 已经使网络饱和。

我们强调使网络饱和是一个全局的条件。它只是我们安全性论 证中的理论值。副本无法观察到产物是否饱和了网络。饱和网 络并不构成一个可靠的广播。

  产物可以不按顺序地被接收,换言之,一个签名或一个区块的 公证能在这个区块之前被接收。如果产物x在它引用的产物被接 收之前,就已经被接收了,那么X便不可被验证。为此,所有诚 实副本首先会使任何传入的产物X列队等待,直到所有被X引用 的产物都被接收了以后,对会被处理。特别指出的是,J个诚 实副本i只有在拥有了所有被X引用的产物时,它才传递产物X。 因此,一个i的同级ji那里收到x后,可以接着请求接收任何被 x引用的,且j还没有拥有的那些产物。这是一个产物同步的流 程。它是在后台透明地发生的,并且在j处理x之前就完成了。 因此,在整篇文章中,我们自然能认为如果一个产物x已经被接 收了,那么所有被x引用的产物也已经被接收了。

  区块提议下的签名在后台处理中被收集。一旦多数签名可被用 于某个给定的区块提议,这些签名便会被汇总为一个验证,然 后它会被当作是从外部接收的一样。区块提议和验证是在后台 被收集并提供给Alg.l2的。

 我们的接力政策和网络假设(见下文第9.2.1)节确保了以下特性:

任何属于b)并由一个诚实副本处理的产物将最终使网

络饱和。(9.1)

 属性(9.1)不适用于根据政策。)传递的产物。因为在广播路径的 上的一个副本可能已经前进到了下一轮。在这种情况下,产物将 被视作过于陈旧,就会被丢弃。

假设一个诚实副本i已经处理了一个区块提议B并且认为它是有 效的。那么i必须拥有8和一个Q” 8.的公证。我们强调,在这 种情况下诚实副本会重新广播这个已公证区块Q”位由(9.1)得 岀,这个行为可以确保:

如果一个区块B被诚实地签署,那么经过公证的区块

Q” 8最终会使网络饱和。位.2)

属性(9.2)不适用于际身或其下的个人签名,因为这些产物不属 于定义9.4中的神类b) °

9.2时间和进度

  本部分将陈述发生于不同副本中的事件的相对时间。我们对任 何一轮都不做正常运作的假设,因此不得不考虑多重公证ZrN七 …在同一轮r中被创建和广播的可能性。

921导言。我们假设有一条消息被一个诚实副本在t时广播。它 在t+△之前(即在<t+△时)传达到了每个诚实副本。由于处理时 间不在我们分析的范围之内,我们假设所有的处理时间为零。这 一点适用于创建所有的消息以及对其的验证:包括区块提议,签 名,公证,随机数灯塔份额,和随机数灯塔输出。举个例子来说 就是,当一个副本it时收到一个随机数灯塔输出韻,它会在同 -时间t广播对于第「轮的区块提议。或者是当一个随机数灯塔成 员it时收到一个第r轮的公证后,i立刻在同一时间t广播他在 第「+1轮的随机数灯塔份额。

  定义9.5。令「(A)表示副本i看到事件A的时间,其中A是以下之 一:一个随机数灯塔输出貝一个区块提议饥或一次验证仍我们 设口 :=口其中zii在第e轮收到的第一次验证。

因此,T/(r)是副本i进入第「轮的时间。为了研究第一个或最后一 个诚实副本在何时看到一个事件,我们定义:

定义9.6

DFINITY技术概论系列 共识系统

举例来说就是,T (「)是当第一个诚实副本进入第r轮的时间,

是当最后一个诚实副本进入第「轮的时间。最后,我们也注 意到了一个事件是可以首先被恶意攻击者看到或者构建的这一 点。所以我们定义:

DFINITY技术概论系列 共识系统

DFINITY技术概论系列 共识系统

DFINITY技术概论系列 共识系统

DFINITY技术概论系列 共识系统

DFINITY技术概论系列 共识系统

DFINITY技术概论系列 共识系统

DFINITY技术概论系列 共识系统

DFINITY技术概论系列 共识系统

DFINITY技术概论系列 共识系统

DFINITY技术概论系列 共识系统

DFINITY技术概论系列 共识系统

DFINITY技术概论系列 共识系统

DFINITY技术概论系列 共识系统

DFINITY技术概论系列 共识系统

DFINITY技术概论系列 共识系统

参考文献

|1] RANDAO: A DaO working as RNGcf Ethereumi. https-//github-Corn/randco/ ran- daof2017.

[2] J.-L. Beuchat,丄 E- Gonzdlez-Dfaz, S. Mitsunarl E. Okamioto, F_ Rodrfguez- Hen- riqueZz andT.Teruya. High-Speed Software Im pl erne ntotion of the Optimal Ate Pairing over Barreto-Naehrig Curves. Pairing, 6487:21-39^ 2010.

|3] D. Boneh, B. Lynn, and H. Shacham. Short Signatures from the Weil Pairing. In Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology. ASIACRYPT J 0L pages 5*14-532, London, UK. IJK, 20Q1. Springer-Vgrlag.

[4] I. Eyal and E. G. Sirer. Majority 15 not enough: Bitcoin mining 15 vulnerable. In International conference on financial cryptography and data security, pages 436-454 Springer, 2Q14.

[5] J. Garayf A. Kiayias. and N. Leonardos. The Bitcoin Backbone Protocol with Chains of Variable Difficulty. In Annual International Cryptology Conference, pages 291-323- Springer, 2017.

[6] R. Gennaro, S. Goldfeder.and A. N a ray a nan. Th re s hold- o ptimal DSA/ECDS A signatures and an application to Bitcoin wallet security. In Internotional Con – fere nee on Applied Cryptography and Network Security, pages 156-174. Springer, 2。】6.

7] R. Gennaro. S. jareckL H. Krawczyk. andT. Rabin. Advances in Cryptology — EUROCRYPT ’99: International Conference on the Theory and Application of Cryp- to- graphic Techniques Prague, Czech Republic May 2-6. 1999 Proceedings/ chapter Secure Distributed Key Generation for Discrete-Log Based Cryptosystems, pages 295-310. Springer Berlin Heidelberg, Berlin, Heidelberg. 1999.

[8] Y. Gilad, R- Hemo. S. Miceli, G- Vlachos, and N.Zeldovich. Algorand Scaling Byzantine Agreements for Cryptocurrencies-

19] D. E. Knuth. The art of computer programming, volume 1 Fundamental algorithms. volume 2:Seminumerical algorithms. Bull. Amer. Math. Soc, 1997.

[10] B. Libert. M_ Joye, and M. Yung. Born and raised distributfvely Fully distributed non-intercctive odopti^ely-secure threshold signatures with short shares. Theo- ret- icai Computer Science, 645:1-24,2016.

|11] S. Mitsunari. Barreto-Naehrig curve implemientation and BLS. http5//github. com/dfinity/bn,. 2017.

加密货币新用户正在进场:我们从数据入手找到了这 7 个证据加密货币新用户正在进场:我们从数据入手找到了这 7 个证据
Crust VS Filecoin,波卡生态分布式存储会更胜一筹吗?

原文标题:《新人入场加密货币?市场给出了这 7 大证据!》 撰文:布劳克琴 我们都知道,本轮牛市,企业机构已跑步入场。根据 Bitcoin Treasuries 的数据统计,目前已经有超过 50 家企业机构对外公开持有比特币,总持有量约为 1,427,573 …

Click to rate this post!
[Total: 0 Average: 0]

人已赞赏
名家说小白百科每日优选

DFINITY,一件豪华的过渡期奢侈品

2021-5-1 15:24:39

名家说小白百科每日优选

Dfinity挖矿与数据中心

2021-5-1 15:28:37

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
有新消息 消息中心
搜索