关于分片开销与最终化时间的总体框架及提议

unitimes.media

全球视角,独到见解

“Vitalik关于分片模型的最新构想。”

总体而言,“第4阶段”与分片链是紧密耦合(tightly coupled)的,其工作原理如下:

1. 生成分包(通过某种机制)

* 此处“分包”,原文为collation,意为“整理、分包”,因其本质是分片内的区块,故译“分包”。译者注。

2. M个经随机抽样产生的公证者构成集合(“委员会”),该集合负责校验分包的数据可用性,并以某种方式投票表明该分包可用。

3. 分包头以及支持该分包的委员会投票被包含在主链内(主链验证者会验证投票的有效性,可能也会验证分包本身的数据可用性证明)。此时,主链和分包是“紧密耦合的”:如果由于某种原因,分包不可用——哪怕它得到投票支持——那么整个主链区块也必须被客户端拒绝。

所以它的传递结构是:

从左到右依次为:“产生分包”、“委员会同意该分包”、“分包头在主链‘内部最终化’”

在第1到3阶段中,尽管缺乏紧密耦合,但我们也可以用任何一种协议内机制(in-protocol mechanism)来替代这种耦合关系。在这个机制中,如果由多数验证者构成的集合认为不可用的区块被包含在链内,那么他们有权执行回滚操作。

我们用以下符号来表示特定变量:

• N:分片的数量

• M:随机抽样的规模

• T:每个分片内的分包的时间间隔(即分片中的区块时间)

• C:一个分包结构的大小(参考T知,即分片中区块的大小)

• R:同一张公证者投票支持的不同分包的数量

• F:内部最终化(即紧密耦合)的耗时

在分片1.1规范中,这些变量的值分别为:

• N:100

• M: ~25

• T: 70 秒

• C: 1 MB

• R: ~25

• F: 70 秒 * ~25 ~= 30 分钟

请注意,分片1.1规范中虽然没有明确声明“委员会规模”,但却隐含了相关信息。当一个分包者被分配到一个分片时,他们只会检查链上的最后M个分包,并遵从加密经济学强制满足“最小值为25”的硬底。因此,如果一个分包得到25个确认,它基本不会再被检查,所以M = 25。而R = 25,是因为分叉也是一种投票;基于头部继续加入分包的行为意味着该分包已经得到其头部以及最近25个祖先分包的认可。最终化比较主观,但由于在25个分包之后不会再有进一步的验证流程,所以我们可以合理地认为在25个周期以后,最终化已经实现。

但除了分叉以外,还有其他形式的投票。例如,分包彼此独立,但每个分包可能包含一个位阈(bit field)用于表示分包者认为最近的25个分包当中,哪一个是可用的。我们也可以用一个无需分叉的方案:分包要进入主链必须已经获得25张支持票,这也意味着该分包已经最终化。本文的其中一个目标,就是尝试分析这类方案。

我们可以计算主链的开销,得:

(N∗M)/(T∗R)

计算结果的推导如下:

• N是分片数,M是每个分片的委员会规模。由于每个分包头都拥有M个签名,所以N个分包头在链上的开销为N * M。

• 上述情况每T秒发生一次。

• 如果一个签名能同时代表多个含义,则上述开销将会减少,因此我们可以将R添加到分母中。

另一类重要的开销是公证者突发开销(notary burst overhead):当公证者被要求对一个或多个分包进行投票时,他们会得到一个截止日期——在该截止日期前必须提交签名——并且他们需要下载所有数据以在特定时间内检查其可用性。我们可以计算公证者突发开销,得到:

(C∗R)/F

计算结果的推导如下:

• C是每个分包的大小。 R是他们必须检查的分包数量。

• 内部最终化(即紧密耦合)需要查看公证者的签名,因此,无论供公证者下载数据的时间有多长,内部最终化都至少需要等待这段时间。

在这个框架内,我们可以计算一下几类方案的效率:

• 1.1分叉模型(forkful model):主链开销=(100 * 25)/(70 * 25)≈1.41,分包者突发开销(collator burst overhead)=(106 * 25)/ 1750≈14286字节/每秒。需要注意的是,实际上分叉模型的效率要比这个理想值低得多,因为前瞻分包(the lookahead)只有3个而不是25个周期,所以验证者突发开销是(106 * 25)/210≈119047字节/每秒。

• 将分包区块时间提高到1750秒,分包大小提高为25 MB,要求分包必须经过委员会的批准,否则立即拒绝。此时主链开销=(100 * 25)/1750≈1.41,分包者突发开销=(25 * 106)/1750≈14286字节/每秒。

注意,这两个模型花费的成本似乎完全相同,就连最终化时间(1750秒)也一样,但第二个模型更简单。那为什么还要考虑第一个模型呢?答案是:基于较小分包结构大小的模型可以更快地给出部分确认的指示。 25个确认意味着已经实现了最终化,但即使只有3个确认通常也能令人相信:交易是有效的,并且会被包含进主链。

如果我们观察一下计算开销的等式,我们能够得到一些显然的折衷:

• 主链开销与公证者开销为1:1的折衷。你可以将主链开销减半,但与此同时,公证者开销R也会相应翻倍。

• 公证者突发开销和最终化时间1:1的折衷。你可以通过加倍最终化时间来将公证者突发开销减半(或者,也可以通过将R加倍来节省主链开销)。

• 你可以始终依据相同的比例同时减少C和T,并通过以相同的比例增加R来抵消其对主链和公证者突发开销的影响。

这更普遍地表明,我们可以通过应用某些技巧使单一签名表示多重含义来减少T,并尝试提供更快的部分信息。但除了分叉之外,还有其它技巧吗?这些技巧效果如何?

首先,让我们先把注意力从分叉转向分包提议和公证均为独立功能的模型。也就是说,每个阶段都会有一个分包头被提议,但随后会有一组独立的公证者参与投票来敲定它们。例如,分包提议者可以从存在于特定分片中的集合内随机抽样选出,从而允许他们保持该分片的状态,并且不需要玩“分包者–提议者(collator-proposer games)”游戏。我们不妨把注意力从“分叉即投票(forking-as-voting)”模型转到一个明确的模型:每个时期,每个分片选择k个公证者,这些公证者必须尝试下载最新的M / k个分包,并通过位阈(即像11110111001111111011101这样的字符串)对每个分包的可用性进行裁决。在分包产生以后,经过p个周期,分包将拥有p * k张投票,从而提供部分确认的证据。这使得我们不必再局限于每个分片每个周期的投票单元,把k = 1(类似于1.1分叉模型)和k = M(分包会在一个回合内被验证,并且该验证过程在下一个分包产生之前会完成)之间的参数空间全部释放。

公证过程是遵从加密经济学的:你可以投票支持多个分包,一旦这些分包被接受,你将得到奖励;但如果你投票支持某个分包,你有责任证明分包体是正确的,如果你做不到,那么你会损失你的押金。

为了让公证者突发开销达到最小,前瞻分包需要等于M / k,这样的话,公证者就可以一到达分片就着手下载和检查分包。然而,这里有一个巧妙的方法可以提高此方案对抗半自适应对手的安全性:我们不在一个分片内的一系列周期数字上垂直检查其数据可用性,而是使用对角检查,检查每个周期中不同分片内的分包。决定某个时期公证者检查哪个分片的随机结果将延迟到该时期再公布,从而实现零前瞻透明度(zero lookahead transparency)。这一方式使得该方案在多数诚实的假设下都是安全的——除非面临强大的自适应对手,因为他们可以在单一周期内对特定节点发动攻击。

总而言之,在这种对角方案中,我们需要在时期p内选定公证者,并要求公证者在p到p + M / k范围内的每个时期内验证来自某个分片的分包。在最后一个时期,公证者将提交一份签名,该签名包含公证者对特定范围内每个分包的意见,这个签名将作为一个位阈。依据这种方式,我们可以:

• 取消提案者/分包者分离功能,因为这一功能现在已经被提案者/公证者分离功能取代。

• 达到更高的公证者突发开销效率(或者将部分效率增益用于将M从25提高到更安全的100-200)

• 事先获知哪些公证者在总计M / k个分片中处于活跃状态,但无法获知在某个时期开始之前,哪个公证者会被分派到哪个分片进行公证。

• 避免在交易数据被包含在主链之前,某些节点利用交易费用或竞价来贿赂分包者的情况,因为投票职能由公证者实行。

• 消除在分叉链内拥有另一条分叉链的复杂性。

• 主链开销和以前基本相同。

• 有关部分确认的信息程度仍然跟以前一样。

原创作者:Vitalik Buterin

翻译:喏呗尔

https://ethresear.ch/t/a-general-framework-of-overhead-and-

finality-time-in-sharding-and-a-proposal/1638

国际金融科技新媒体和社区平台

UNITIMES

网址 : unitimes.media

新浪微博:@Unitimes

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20180424G1NT6I00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券