Polkadot:畅想一种异构的多链架构(第四部分)

本文译者:岳利鹏

6.5 中继链区块打包的改进

打包区块的方法确保着系统的正常运行,因为每条平行链的关键信息都要由超过三分之一的验证人来保证可用性,所以它并不能很好地伸缩。这意味着随着更多平行链的增加,每个验证人的工作也会增加。

在开放的共识网络中,如何保证数据的可用性还是个有待解决的问题,然而还是有一些方法可以缓解验证人节点的性能瓶颈。一个简单的方案是:其实验证人们只是负责验证数据的可用性,那他们就没必要自己真正地存储、通信和复制数据。第二个方案是数据隔离,这个方案很可能和收集人如何组织数据相关,网络可以对收集人有一定的利息或收入激励,让他们保证提供给验证人的数据是可用的。

然而,这个方案也许可以带来一点伸缩性,但仍没有解决根本问题。因为添加更多平行链通常需要增加验证人,网络资源的消耗(主要是带宽)以链总数的平方的速度增长,长期来看这是不可持续的。
最终,我们可能会思考对于保证共识网络安全的根本限制,网络对带宽的需求增长速度是验证人数乘以消息总进入数。我们不能信任那些将数据分开在不同节点存储的共识网络,因为这会将数据和运算分离。

6.5.1 延迟性介绍

简化这个规则的方法是先了解即时性的概念。33%+1的验证人最终(eventually)需要对数据的有效性进行投票,而不是立刻(immediately)投票,我们可以更好地利用数据指数级传播的特性,来帮助应对数据通信的峰值。一个合理的等式(尽管未证明):

(1) 延迟 = 验证人数 * 区块链数
在目前的模型下,系统的规模只有随着链的个数而伸缩,才能保证数据的分布式运算;因为每个链至少需要一个验证人,对于可用性投票的复杂度,我们把它降到了只和验证人个数呈线性关系。现在验证人数可以和链个数同样增长了,我们终结了:

(2) 延迟 = 数量2
这意味着随着系统增长,网络内带宽和延迟性的增长是可知的,但达到最终确定性所需的区块数目仍然是以平方增长。这个问题将会继续困扰我们,也可能迫使我们打造一个“非平层”(non-flat)的架构,也就是会有很多按层级结构排列的Polkadot链,通过一个树形的结构来路由消息。

6.5.2 公众参与

微意见(micro-complaints)系统是一种可以促进公众参与的方式。可以有一些类似于钓鱼人的外部参与方来监管验证人。他们的任务是找到提供了非可用数据的验证人。他们可以给其他的验证人提交一个微意见。这个方案需要用PoW或押金机制来防止女巫攻击,否则它会让整个系统失效。

6.5.3 可用性保证人

最终的一个方案是从验证人里提名出第二个小组作为可用性保证人(Availability Guarantors)。他们也需要和普通验证人那样交押金,而且有可能来源于同一个组(会在一个长周期里选择他们,至少也是一个会话)。和普通验证人不同的是,他们不需要在各条平行链间切换,而只需要形成一个单一的小组,监管所有重要跨链数据的可用性。
这个方案还有个优势是能缓解验证人数和链个数之间的等式关系。链个数可以最终增长(与原始链的验证人小组一起),然而各参与方仍可以保持次线性增长或常量增长,尤其是那些参与数据可用性验证的人。

6.5.4 收集人设置

系统需要保证的一个重要方面是:合理地选择那些制造平行链区块的收集人。如果一条平行链由某个收集人控制了,那么外部数据是否可用就会变得不那么明显,这个人就可以比较简单地发动攻击。

为了尽可能地广泛分配收集人,我们可以用伪随机的方法来人工衡量平行链区块的权重。在第一个示例中,我们希望验证人倾向于选择权重更大的候选块,这是共识机制的一个重要部分。我们也必须激励验证人找到最大权重的候选块,验证人可以把他们的奖励按比例分配给这些候选块。

在共识系统里,为了确保收集人的区块被选中的机会是平等的,我们用一个连接所有收集人的随机数生成器来决定每个候选块的权重。例如用收集人的地址和一些密码学安全的伪随机数做异或(XOR)运算来决定最优的块(获胜票)。这给了每个收集人(更准确地说是每个收集人地址)随机公平地打败别人的机会。

验证人通过女巫攻击来生成一个最接近于获胜票的地址,为了阻止这种情况,我们会给收集人的地址加上一些惰性。一个很简单的方法是需要他们的地址有基本的余额,另一个更优雅的方式是综合考虑地址的余额来计算获胜的概率。这里还没有完成建模,我们很可能会让很少余额的人也可以成为收集人。

6.5.5 区块超重

如果一个验证人集合被攻击了,他们可能会生成一个虽然有效但要花费大量时间来执行的区块。这个问题来源于一些特定的难解数据题,比如大质数因式分解难题等,验证人小组可能需要非常长的时间才能解出答案,如果有人知道一些捷径,他们的候选块就有巨大的获胜优势。如果一个收集人知道那个信息,而其他人都在忙着计算老的块,那么他就有很大的优势让他的候选块获胜。我们称这种叫超重(overweight)块。

为了防止验证人提交这些大幅超出普通区块的超重块,我们需要添加一些警告:因为执行一个区块要花费的时间是相对的(根据它超重的程度),所以最终可能的投票结果会有三种:第一种是这个区块绝对没有超重,超过2/3的验证人声明他们可以在一定时间内算完(例如出块时间的50%);另一种是这个区块绝对超重了,超过2/3的验证人声明他们无法在限定的时间内执行完这个区块;再一种就是意见分歧基本持平,这种情况下我们会做一些惩罚。

为了保证验证人能预测他们提交的区块是否超重,他们可能需要公布自己在每个块上的执行表现。经过一段时间后,他们就可以通过和其他节点的比较来评估自己处理器的性能。

6.5.6 收集人保险

还有一个问题留给了验证人:为了检查收集人区块的有效性,他们不能像PoW网络那样,而是必须自己计算里面的交易。恶意收集人可以填充非法或超重的区块给验证人,通过让他们受害(浪费他们的资源)来获取大量的潜在机会成本。

为了预防这个,我们为验证人提供了一个简单的策略。第一:发给验证人的平行链候选块必须要用有钱的中继链账户签名,如果不这么做,验证人会立即丢弃这个块。第二:会用组合算法(或乘法)对这些候选块进行排序,因素包括高于一定限额的账户余额、收集人过去成功提交的区块数(除去那些有惩罚的)、和获胜票的接近程度。这里的限额应该等于提交非法块的惩罚金。

为了警示收集人不要发送非法或超重的交易给验证人,任何验证人都可以在下一个区块中打包一个交易,指出那个非法的区块,并将那个收集人部分或全部的余额都转给那个受害的验证人。这种交易的优先级高于其他交易,使得收集人不能在惩罚之前转走他的余额。惩罚金额可能是动态决定的,也很可能是验证人区块奖励的一部分。为了阻止验证人任意没收收集人的钱,收集人可以对验证人的决定进行上诉,成立一个由验证人随机组成的陪审团,并交一些押金。如果陪审团发现验证人是合理的,那这笔押金就给陪审团了。如果是不合理的,押金退回给该收集人,而验证人要受到惩罚(因为验证人是核心角色,惩罚会比较重)。

6.6 跨链交易路由

跨链交易路由是中继链和其验证人的核心功能。这里管理着主要的逻辑:一个提交的交易(简言之为“提交”)是如何从一个来源(source)平行链的出口被强制地路由到另一个目标(destination)平行链里,而且无需任何信任人。
我们很小心地选择了上面的词语;在来源平行链里,我们无需一个明确约束这个提交的交易。我们模型里的唯一约束是:平行链必须尽力按照全部的出口能力打包,这些提交就是他们区块执行的结果。

我们用一个先进先出(FIFO)的队列组织这些提交。作为路由基准(routing base)的队列个数可能在16个左右。这个数字代表着我们可以直接支持的平行链性能,而不用采用多相(multi-phase)路由。Polkadot一开始会支持这种直接路由,然而我们也可能会采用一种多相路由操作(超路由hyper-routing)作为将来系统伸缩的方式。

我们假设所有参与方都知道下两个区块n,n+1的验证人分组情况。概括而言,路由系统有如下阶段:

收集人s:合约成员中的验证人V[n][S]。
收集人s:FOR EACH 小组s:确保合约里有至少一个验证人V[n][S]。
收集人s:FOR EACH 小组s:假设出口[n-1][s][S]是可用的(上个区块里所有对S提交的数据)
收集人s:为S构造候选块b:(b.header,b.ext, b.proof, b.receipt, b.egress)。
收集人s:发送证明信息proof[S] = (b.header, b.ext, b.proof,b.receipt, b.egress)。
收集人s:确保外部交易数据b.ext已经对于其他收集人和验证人可用了。
收集人s:FOR EACH 小组s:发送出口信息egress[n][S][s]= (b.header, b.ext, b.receipt, b.egress)给下个区块的接收方小组的验证人V[n+1][s]。
验证人v:预连接下一个区块的同一个组的成员:让N = Chain[n+1][V];连接所有的验证人使Chain[n+1][v] = N。
验证人v:收集这个块所有的入口数据:FOR EACH 小组s:检索出口egress[n-1][s][Chain[n][V]],从其他验证人v获得使Chain[n][v] = Chain[n][V]。可能是通过随机性地选择其他验证人的证明数据。
验证人v:为下个块接收候选块的出口数据:FOR EACH 小组s,接收egress[n][s][N]。对区块出口的有效性投票;在意向验证人间重新发布使Chain[n+1][v] = Chain[n+1][V]。
验证人v:等待共识。
egress[n][from][to]代表:在区块n里,从来源from平行链到目标to平行链的当前出口队列信息。收集人s是属于平行链S的。验证人V[n][s]是平行链s在区块n时的验证人小组。相反地,Chain[n][s]是验证人v在区块n所属的平行链。block.egress[to]是从平行链区块block发送给目标平行链to的出口队列。
收集人因为希望能够采纳他们出的块,所以收集(交易)手续费作为激励,并保证下一个区块的目标小组成员都能知晓当前块的出口队列。验证人的激励是达成中继链区块的共识,所以他们并不关心最终采纳哪个收集人的区块。一个验证人原则上可以勾结一个收集人,合谋减少采纳其他收集人的概率,然而因为平行链的验证人是随机分配的,所以这也很难得逞,而且还可能会遭到手续费减免,最终影响共识流程。

6.6.1 外部数据可用性

如果要在一个去中心化的系统里完成分布式的全部流程,一个长年的遗留问题是:如何确保一条平行链的外部数据都是可用的。这个问题的核心原因是:不可能生成一个关于可用性与否的非交互式证明。在一个拜占庭容错的系统内,我们需要依赖外部数据才能验证任意交易的有效性。假设我们能容忍的最多的拜占庭节点数为n,我们一共至少需要n+1个节点才能证明数据的可用性。

Polkadot是个希望可以伸缩的系统,这带来了一个问题:如果必须由一个固定比例的验证人来证明数据的有效性,并且假设他们真会存储这些数据来用于判断,那么我们如何避免随着系统的增长而带来的对带宽/存储空间等需求的增长。一个可能的答案是成立一个验证人小组(就是保证人),他们的数目随着Polkadot整体的增长而线性增长。这在6.5.3里提到了。

我们还有第二个技巧。收集人有内在的激励去确保所有数据的可用性,否则他们就不能再生产后续区块了,也就不能再获得手续费了。收集人也可以形成一个小组,成员复杂多样(因为平行链验证人成员的随机性),很难进入。允许最近的收集人(可能是最近几千个块)对某条平行链区块的外部数据发起挑战,来获取一点验证人的奖励。

验证人必须联系这些有明显进攻行为的小组,这些小组会举证、获取并返回数据给收集人,或者直接通过证明数据的非可用性来升级事态(作为原告方直接拒绝提供数据记录,不当行为的验证人会直接断开连接),并联系更多的验证人一起去测试。在后一种情况中,收集人的押金会被退回。

一旦超过法定个数的验证人都证明交易的非可用性,验证人小组就可以解散了,非法行为的收集人小组会被惩罚,区块被回退。

6.6.2 路由“提交”

每条平行链的头部都包含一个出口树根(egress-trie-root)。这个树根包含了一个路由信息的格子列表,每个格子里都有一个串行(concatenated)结构的出口提交。可以在平行链的验证人之间提供梅克尔树证明,这样就能证明某条平行链的区块对应着另一条平行链的出口队列。

在开始处理平行链区块之前,每条平行链指定区块的出口队列会被并入我们区块的入口队列。假设密码学安全的伪随机数(CSPR)能用来保证公平地对平行链区块进行配对。收集人计算新队列,并根据平行链的逻辑抽干出口队列。
入口队列的内容会被明确地写入平行链区块。这么做有两个目的:第一,平行链可以独立地进行非信任同步,而不用依赖其他链。第二,如果整个入口队列无法在一个块内处理完,那么这种方法可以简化数据逻辑;验证人和收集人可以继续处理下面的区块而不用再做数据引用了。

如果平行链的入口队列超过了区块处理的阈值,那么在中继链上就会被标记为已满,在队列清空之前不会再接收新的消息。使用梅克尔树来证明收集人在平行链区块里的操作是可信的。

6.6.3 弊端

这个架构的小瑕疵是可能发生后置炸弹攻击(post-bomb attach)。所有的平行链给另一个平行链发送最大数量的提交,这会瞬间塞满目标链的入口队列,不造成任何伤害地进行了Dos攻击。

正常情况下,假设有对于N条平行链和一系列正常同步的非恶意的收集人和验证人,那么总共需要N x M个验证人,每条平行链L个收集人,每个块可能的数据路径(data path)有:
验证人:M-1+L+L:M-1代表平行链集合里的其他验证人,第一个L代表每个收集人提供了一个平行链候选块,第二个L代表下一个块的全部收集人需要放入出口队列的前块数据。(后一种情况可能会更糟,因为收集人之间会分享这些数据)。

收集人:M+kN:M代表和每个平行链区块相关的验证人的连接数,kN代表着下一个区块播种(seeding)到每个平行链验证人小组的出口队列的负载(很可能是一些很受喜爱的收集人)。

因此,每个节点数据路径的可能性随系统的复杂度的增长而线性增长。这也是合理的,当系统伸缩到上百上千个平行链的时候,通信的延迟也会变大,进而降低复杂度的增长速度。在这种情况下,会用一个多级的路由算法来减少峰值期的数据路径,但需引入缓存和交易延迟。超方路由(Hyper-cube Routing)是一种可以建立在上面描述的基础路由方法上的一种新机制。对节点来说,他们的连接数从需跟平行链和节点小组数一起增长,变成了只跟平行链个数的对数增长。这样就可能需要经过多个平行链的队列才能最终传送“提交”。

路由本身是简单和确定性的。我们从限制入口/出口队列的格子数开始;平行链的总数目是routing-base(b),这个数字会随着平行链的改变而修正,增长为routing-exponent(e)。在这个模型下,我们的消息总量以O(be)增长,而数据路径保持为常量,延迟(或传递需要的块数)以O(e)增长。

我们的路由模型是一个e维的超方体,每个立方体的面有b种可能位置。对于每个块,我们围绕一个轴来路由消息。为了保证最坏情况下的e个块的传递延时,我们用round-robin fashion来轮换每个轴。

作为平行链处理的一部分,只要给定当前的块高度(路由维度),入口队列里外部范围的消息就会立即路由给合适的出口队列的格子。这个过程需要在传送路由上发送更多数据,然而这会是个问题,也许可以通过一些替代性的数据负载发送方式解决,比如只包含一个引用,而不是在提交树(post-trie)里包含全负载。

一个拥有4条平行链的超方路由系统示例,b = 2、e = 2:
阶段0,对于每个消息M:
sub0:如果 Mdest∈ {2,3} ,那么sendTo(2),否则保留
sub1:如果 Mdest∈ {2,3} ,那么sendTo(3),否则保留
sub2:如果 Mdest∈ {0,1} ,那么sendTo(0),否则保留
sub3:如果 Mdest∈ {0,1} ,那么sendTo(1),否则保留
阶段1,对于每个消息M:
sub0:如果 Mdest∈ {1,3} ,那么sendTo(1),否则保留
sub1:如果 Mdest∈ {0,2} ,那么sendTo(0),否则保留
sub2:如果 Mdest∈ {1,3} ,那么sendTo(3),否则保留
sub3:如果 Mdest∈ {0,2} ,那么sendTo(2),否则保留

这里的两个维度很容易看做是目标索引的前两位(bits)。第二个块处理低序的位。一旦全部发生(任意顺序),提交就会被路由。最大化随机性(Serendipity)。一个对基本提议的修改是把验证人数固定为c2-c个,每个小组c-1个验证人。摒弃原来每个区块时都在平行链间松散地分配验证人的方案,而改成对于每个平行链小组,在下一个区块时,会分配每个验证人到唯一的不同平行链小组。这导致了两个区块之间的不可变性,对于任意配对的平行链,都会有两个验证人调换他们的职责。然而我们不能用这个来确保绝对的可用性(单个验证人可能时常掉线,即使是非恶意的),但可以优化这个方案。

这个方案也会有后遗症。平行链需要重组验证人集合。进而验证人的数量会被绑定在平行链数量的平方级别,从很少开始最终快速增长,在50条平行链时就会变得无法承受。这些都不是什么本质问题,对于第一个问题,本来也需要频繁重组验证人集合,无论验证人集合的数量多少。当集合数很少的时候,多个验证人可能被分配到同一条平行链,那么对于全部平行链影响的因素是常量的。对于在很多平行链时的需要很多验证人的问题,可以用在6.6.3里讨论的这个多阶段的超方路由机制来缓解。

相关文章:

Leave a Reply

消息接收
avatar
500
wpDiscuz