登录 注册
Polkadot(波卡链)> Polkadot白皮书(第6.6-6.8章)

【译者:岳利鹏 lipeng@chainx.org

【版权所有:因特链社区,国内最具前瞻性的跨链技术社区,未经许可,禁止转载】 


6.6      跨链交易路由

跨链交易路由是中继链和其验证人的核心功能。这里管理着主要的逻辑:一个提交的交易(简言之为“提交”)是如何从一个来源(source)平行链的出口被强制地路由到另一个目标(destination)平行链里,而且无需任何信任人。

我们很小心地选择了上面的词语;在来源平行链里,我们无需一个明确约束这个提交的交易。我们模型里的唯一约束是:平行链必须尽力按照全部的出口能力打包,这些提交就是他们区块执行的结果。

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

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

l   收集人s:合约成员中的验证人V[n][S]。

l   收集人s:FOR EACH 小组s:确保合约里有至少一个验证人V[n][S]。

l   收集人s:FOR EACH 小组s:假设出口[n-1][s][S]是可用的(上个区块里所有对S提交的数据)

l   收集人s:为S构造候选块b:(b.header, b.ext, b.proof, b.receipt, b.egress)。

l   收集人s:发送证明信息proof[S] = (b.header, b.ext, b.proof, b.receipt, b.egress)。

l   收集人s:确保外部交易数据b.ext已经对于其他收集人和验证人可用了。

l   收集人s:FOR EACH 小组s:发送出口信息egress[n][S][s] = (b.header, b.ext, b.receipt, b.egress)给下个区块的接收方小组的验证人V[n+1][s]。

l   验证人v:预连接下一个区块的同一个组的成员:让N = Chain[n+1][V];连接所有的验证人使Chain[n+1][v] = N。

l   验证人v:收集这个块所有的入口数据:FOR EACH 小组s:检索出口egress[n-1][s][Chain[n][V]],从其他验证人v获得使Chain[n][v] = Chain[n][V]。可能是通过随机性地选择其他验证人的证明数据。

l   验证人v:为下个块接收候选块的出口数据:FOR EACH 小组s,接收egress[n][s][N]。对区块出口的有效性投票;在意向验证人间重新发布使Chain[n+1][v] = Chain[n+1][V]。

l   验证人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:

l   sub0:如果 Mdest ∈ {2,3} ,那么sendTo(2),否则保留

l   sub1:如果 Mdest ∈ {2,3} ,那么sendTo(3),否则保留

l   sub2:如果 Mdest ∈ {0,1} ,那么sendTo(0),否则保留

l   sub3:如果 Mdest ∈ {0,1} ,那么sendTo(1),否则保留

阶段1,对于每个消息M:

l   sub0:如果 Mdest ∈ {1,3} ,那么sendTo(1),否则保留

l   sub1:如果 Mdest ∈ {0,2} ,那么sendTo(0),否则保留

l   sub2:如果 Mdest ∈ {1,3} ,那么sendTo(3),否则保留

l   sub3:如果 Mdest ∈ {0,2} ,那么sendTo(2),否则保留

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

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


6.7      平行链的验证

验证人抵押了大量的保证金,他们的主要目标就是校验平行链区块是否有效,包括但不限于:状态转换、囊括外部交易、执行等待在入口队列的提交、执行出口队列的最终状态。这个过程本身是比较简单的。验证人一旦完成了前一个区块的打包,他们就可以自由地为后面的几轮共识准备平行链的候选块。

验证人一开始通过平行链收集人(下面介绍)或他的某个副验证人找到一个平行链区块。平行链候选块的数据包含区块头、前块头、外部数据输入(对于以太坊和比特币,这些数据被称为交易,然而他们也可能是任意结构、任意目的)、出口队列数据、状态转换有效性的内部证明数据(对于以太坊,这可能是用来执行每个交易的很多状态/存储树节点)。实验性的证据显示对于目前的以太坊区块,这个数据集最多有几百K字节(KiB)。

如果校验没有完成,验证人会尝试从前一个块的转换中获取相关信息,从前一个块的验证人开始,之后到所有签名了这个数据的验证人。

一旦一个验证人接收到了这么一个候选块,他们就在本地验证它。验证过程包含在平行链这个大类的验证人模块里,这个需要共识的软件模块必须写在所有的Polkadot实现里(原则上可以在多个实现里共享一个C ABI的库,但这会降低安全性,因为他们只是单一实现的引用)。

这个过程会提取前块头,然后用刚达成共识的中继链区块中记录的哈希值来检验。一旦父块头的有效性得到了验证,就会调用平行链类中特定的验证函数。这是个会接收很多数据项(大概就是目前给出的几种)的函数,返回值是对于区块是否有效的简单判断。

大多数这种验证函数都将首先检查头部的数据项,这些数据都可以直接从父块衍生出来(例如父块哈希、高度)。之后为了处理交易或提交,他们会尽力填充内部数据结构。对于以太坊这样的区块链,需要执行全部的交易才能往梅克尔树填充这么大量的数据。其他类型的区块链可能有其他的处理措施。

一旦完成验证,入口提交和外部交易(或代表的其他)都会根据链的规则而被固定。(一个可能的默认方式是需要所有入口提交都在服务外部交易之前处理,然而这应该由平行链的逻辑决定)。通过这个规定,一系列的出口提交都会被创建,而且确实符合收集人的候选块要求。最终会一起检查合理填充的块头和候选块头。

验证人完成了对候选块的校验后,就对块头哈希进行投票,并发送必要的验证信息给小组里的其他副验证人。


6.7.1      平行链收集人

平行链收集人不需要交押金,他们完成的是类似目前区块链网络里矿工的任务。他们属于特定的平行链。为了开展工作,他们必须要有完全同步的中继链和平行链。

完全同步的精确含义取决于平行链的种类,尽管它们都包含平行链入口队列的当前状态。在以太坊这个例子中,它还至少要有最近一些块的梅克尔树数据库,但也可能包含非常多的其他数据结构,例如证明账户存在的Bloom过滤器、遗传(familial)信息、日志输出、和对应高度区块的分叉回退表单。

为了保持两条区块链的同步,他们必须维护一个交易池来“钓取”(fish)交易,并接收公网上正确验证的交易。有了链和交易池,收集人就可以为每个块的被选验证人(由于同步了中继链所以知道他们身份)打包新的候选块,再附属一些必要信息(例如从节点网络来的有效性证明等),然后提交给验证人。

他们收集所有交易的手续费作为回报。这里有很多经济激励手段。在一个激烈竞争的市场中,如果收集人有富余的话,还可以跟平行链验证人分享手续费,以激励他们打包特定收集人的区块。同样地,一些收集人可能提高所需支付的手续费,使区块对于验证人更有吸引力。在这种情况下,正常的市场机制会使那些更高手续费的交易跳过队列,并能更快地打包到链里。


6.8      网络设计

以太坊和比特币等传统区块链中的网络设计需求一般比较简单。所有的交易和区块都未受引导地用gossip广播。同步模块中牵涉到的东西会更多一点,以太坊就可以根据不通类别做出不同的响应,但现实中这更多是节点的策略,而不是协议本身的内容。

以太坊基于devp2p协议改进了目前的网络协议,支持在单一节点连接中进行多个子协议的多路复用,因此同时支持多个p2p协议,但以太坊的协议仍然相对比较初级,而且它还没有完成例如支持QoS等重要功能。当初创造一个无所不在的“web3”协议的愿望基本上失败了,只剩下从以太坊众筹出来的几个项目。

Polkadot的需求更加根本。相比于一个完整的统一网络,Polkadot有很多种参与方,每方都有不同的需求,参与方需要有很多不同的网络信道来交换数据。从本质上讲,这意味着需要一个能支持更加层级化的网络结构的协议。另外为了促进更多新类型的区块链来扩展网络,也需要有一个新的层级结构。

对于网络协议更深层面的探讨不在本论文范围内,我们需要更多的需求分析。我们可以把网络参与者分为两类(中继链、平行链),每个都有三小类。每条平行链的参与方之间相互通信,而不和其他链通信:

l   中继链参与方

l   验证人:P,为每条平行链分割成多个子集P[s]

l   可用性保证人:A(在基础协议里由验证人代替)

l   中继链客户端:M(每条平行链的成员)

l   平行链参与方:

l   平行链收集人:C[0],C[1],…

l   平行链钓鱼人:F[0],F[1],…

l   平行链客户端:S[0],S[1],…

l   平行链轻客户端:L[0],L[1],…

通常我们认为网络成员和他们的设置间会发生如下几种通信:

l   P | A <-> P | A:为了达成共识,验证人/保证人必须连接。

l   P[s] <-> C[s] | P[s]:每个作为平行链成员的验证人会和其他成员连接来发现区块并分享区块,例如收集人。

l   A <-> P[s] | C | A:每个可用性保证人将需要从验证人那里收集签过名的共识相关的跨链数据;收集人可以广播给保证人来优化对他们区块的共识。一旦完成,数据会广播给其他保证人来促进共识。

l   P[s] <-> A | P[s’]:平行链验证人将需要从前一个验证人或可用性保证人集合收集额外的输入数据。

l   P[s] <-> A:当需举报时,钓鱼人公告给任何参与方。

l   M <-> M | P | A:中继链客户端输出数据给验证人和保证人。

l   S[s] <-> S[s] | P[s] | A:平行链客户端输出数据给验证人和保证人。

l   L[s] <-> L[s] | S[s]:平行链轻客户端从全客户端获取数据。

如果为了保证高效的传输,那种每个节点无差异的平层网络(类似以太坊devp2p)就不再适应了。协议里很可能扩展引入一个合理的节点选择和发现机制,还可能计划一些前瞻性的算法,保证节点的顺序在适当时候是“偶然”连接的。

各类不同参与方节点的具体策略会不一样:对于一个能伸缩的多链系统,收集人要么需要持续地重新连接被选的验证人,要么连接一个验证人小组来保证他们永不断线,即使大多数时间他们对于自己是无用的。收集人也会保持和可用性保证人集合的一个或多个稳定连接,来确保需要共识数据的快速传播。

可用性保证人将保持相互连接,还要保持与验证人(为了共识和需共识的平行链数据)、一些收集人(为了平行链数据)、一些钓鱼人和一些全节点(为了缺失的信息)的稳定连接。验证人倾向于寻找其他验证人,特别是那些在同一个小组里的,还有那些可以提供平行链区块的收集人。

钓鱼人和一般中继链或平行链客户端会倾向于和验证人或保证人保持一个连接,但和他们相似的很多节点却不这么做。平行链轻客户端除了连接其他轻客户端外,也会连接一个平行链全客户端。


6.8.1      节点轮换的问题

在基础协议的预案里,每个块的验证人小组随机变换,验证人被随机分配去验证某条平行链的交易。如何在不相关的节点间传递数据会是一个问题,这就必须依赖一个全分布式并且连接良好的节点网络,才能保证所需的跳跃距离(最坏的延迟)只按照网络规模(一个类似的Kademlia的协议会有帮助)的log级别增长,要么就必须延长区块时间,来支持必要的连接谈判,建立能够满足该节点当前通信需求的节点集合连接。

这些都不是好的方案:强迫变成更长的出块时间会让网络无法支持一些特定的程序或区块链。即使是一个完美公平的网络连接也会导致带宽浪费,因为要推送大量数据给不相关的节点,所以会影响到网络的伸缩功能。

然而这些方向都会促进问题的解决,一个可以降低延迟的优化方案是降低平行链验证人集合的易变性,在一段区块后才重新分配(比如15个区块,如果是4s的区块时间,那么只需要每分钟才重新连接),或者一段时间内只轮换一个验证人(例如如果有某条平行链分配了15个验证人,那么平均情况是一分钟内才全部轮换)。通过提高平行链局部的可预测性,来降低节点轮换的次数,并仍然保证连接的优势,我们就可以保证节点间连接的随机性。


6.8.2      通往高效网络协议的路径

最高效和合理的开发方向是专注于改造一个现有协议而不是自己从头开发一个。我们将会探讨的几个点对点协议包括:以太坊的devp2p、IPFS的libp2p、GNU的GNUnet。关于这些协议的全面介绍、以及其中关于如何打造一个能支持特定结构的模块化节点网络、动态节点转换、可扩展子协议等内容,本文也不做过多介绍,但这会是实现Polkadot的重要一步。


关于我们

“因特链” 致力于打造国内最具前瞻性的区块链和跨链技术社区目前主要讨论的公有链项目有Cosmos、Polkadot、EOS、IPFS、Dfinity、Plasma、0xproject、KyberNetwork等。

公司

 联系我们

 浙江-杭州

 lipeng@chainx.org

【浙ICP备17025508号-1】