夜影:NEAR协议中的分片设计

区块链资讯NEAR中文社区2020-10-14 12:16:35  阅读 -评论 0

众所周知,以太坊作为迄今为止最广为使用的通用区块链,主网每秒只能处理不到20笔交易。在以太坊网络流行后,由于这个局限,导致了高昂的以太坊gas价格(gas是以太坊网络上执行交易的费用)和过长的确认时间。尽管在撰写该文的时候,以太坊平均每10到20秒可以产出一个新块,然而根据ETHGas监测站的数据,一笔交易实际上要花1.2分钟才能加到链上。低产能,高费用和长延迟,都导致了以太坊不适合运行大规模使用的链上服务。
以太坊低产能的主要原因是,每个节点都要处理全网的每一笔交易。开发者们提出了许多解决方案,试图在协议层面解决这个问题。这些方案主要分为两类:一类是把所有的计算工作交给数量有限的强力节点;另一类是让网络中的每个节点只做所有计算工作的一部分。前一种方案的例子是Solana,系统中的每个节点通过细致的低层优化和GPU的使用,来支撑每秒几十万笔简单的支付交易。Algorand,SpaceMesh,Thunder都可归入这一类;他们通过改进共识以及区块结构本身来超过以太坊的TPS,虽然有一定的效果,但仍然受制于单台机器的处理能力。
后一种方案,即把工作分给所有的参与节点。这种方法叫做分片。这也是当前以太坊基金会打算的扩展方案。撰写本文时,以太坊的分片规范还未定稿,最新的规范可以通过以下链接查看。
链接:
https://github.com/ethereum/eth2.0-specs.
NEAR协议基于分片搭建。NEAR团队的成员包括:多位世界级电脑竞赛获奖者;若干前MemSQL工程师,负责构建分片、跨分片交易以及分布式的JOIN;9位前谷歌、脸书员工,他们在构建分布式系统方面等有着丰富的行业经验。
本文重点阐述了区块链分片的通用方法,以及需要解决的主要问题,包括状态有效性和数据可用性问题。本文还提出了NEAR协议创新的的夜影方案。
1. 关于分片的基础知识
让我们从最简单的分片方法开始。举例来说,不同于运行一个链,我们运行多个链,每个链称为一个“分片”。每个分片有自己的验证节点集合。在下文里,不管是POW中挖矿的方式,还是投票机制,我们都会使用这个原生词汇“验证节点”,去指代那些进行交易验证和生产区块的参与者。同时,让我们先假设各个分片之间互不通信。
这一设计,虽然简单,但却足够概括早期分片面临的一些主要挑战了。
1.1 验证节点分区和信标链

假设一个系统包含10个分片。第一个问题是,由于每个分片有自己独立的验证节点,现在每个分片的安全性都只有原先整条链的十分之一了。如果一个包含X位的非分片链决定硬分叉成一个分片链,X位验证节点就会分布到10个分片上,每个分片现在仅有 X/10 位验证节点。攻击一个分片只需要买通5.1%(51% / 10)的验证节点(见图1)。

这就带来第二个问题:谁负责为每个分片选择验证节点?如果5.1% 的验证节点被攻破,但也只有在这些验证节点正好处于同一个分片时才有威胁。如果验证节点不能自主选择去验证哪个分片,那么一个控制了5.1% 验证节点的参与者是很难让他控制的所有验证节点都在同一个分片的。这也就就大大降低了他破坏系统的能力。
当今几乎所有的分片系统都依赖给分片随机分配验证节点。区块链上的随机性本身就是一个极富挑战的话题,它超出了本文讨论的范畴。现在,让我们假设有这样一个可用的随机性。我们会在2.1节介绍验证节点分配的更多细节。
随机性和验证节点分配都要求计算工作与任意分片之间不存在对应关系。目前对于分片计算而言,几乎所有设计都使用一个额外的独立区块链,来执行维护整个网络所需要的操作。除了随机数生成和给分片分配验证节点外,这些操作通常还包括了接收分片更新以及执行分片快照,处理POS中的质押和取消验证节点资格,以及在支持再平衡功能的分片系统上进行分片的再平衡。这种独立链的名称,以太坊上叫信标链,波卡上叫中继链,Cosmos上叫Cosmos Hub。
本文统一将其称为信标链。信标链的存在引出了下面一个有趣的主题,即二次方分片。
1.2 二次方分片
分片经常被视为一种可以随着网络中节点数的增加而无限扩展的方案。虽然从理论上看,人们是有可能设计出这种方案的,但任何使用信标链概念的方案都不可能无限扩展。为了理解其原因,我们要意识到,信标链要做一些记账的计算工作,例如给分片分配验证节点,或快照分片链区块,而这些都与系统中的分片数量成比例关系。因为信标链本身只是一条单独的链,计算量受限于运行节点的算力,因此分片数量自然就受到了限制。
然而,分片网络的结构确实对节点的改进产生了倍增的效果。想象一下这样一个场景,对网络中节点效率作出一定量的改进,从而使得节点处理交易的时间缩短。
如果节点(包括信标链中的节点)运行网络的速度提高了四倍,那么,每个分片都可以处理原先交易量的四倍多,而信标链也可以维持原先分片数量的四倍多。整个系统吞吐量的将提升:4 × 4 = 16 倍,这就是二次方分片名称的由来。
当前,对于究竟能支持多少分片,很难提供精确的度量。但是,在可以预见的未来,区块链用户的吞吐量需求不太可能超过二次方分片的能力。运行如此众多的分片所需要的节点数,可能比当今所有区块链节点数的总和还要高出几个数量级。
1.3 状态分片
目前为止,我们还未准确定义当网络切割成分片后,究竟什么被分割开,什么没有被分割出去。尤其要注意,区块链中的节点需执行三个重要任务:1)执行交易,2)把经过验证的交易和构建完成的区块中继给其他节点,3)存储整个网络账本的状态和历史。三个任务中的每一个都对运行网络的节点提出了不断增加的需求:
· 随着需要处理的交易量的增加,执行交易的必要性导致更高的算力需求;
· 随着需要中继的交易量的增加,中继交易和区块的必要性导致更高的网络带宽需求;
· 随着状态数据的增长,存储数据的必要性导致更大的存储需求。重要的是,不像算力和网络需求,存储要求是持续增长的,即使交易速率(TPS)保持恒定。
上面的列表可能让人觉得,存储需求是最急迫的,因为它是唯一一个随着时间持续增长的因素(即使每秒交易量不变)。但实际上,当前最急迫的需求是算力。撰写本文时,以太坊的全网状态大小是100GB,大部分的节点都可以轻松应对。而以太坊的每秒可处理交易量在20笔左右,比许多实际应用场景的需求低了好几个数量级。
Zilliqa是最广为人知的对交易处理而不是存储进行分片的项目。对处理分片相对容易:因为每个节点都有完整的状态,意味着一个合约可以自由调用其他合约,从链上读取任何数据。为了确保对状态同一部分进行更新的多个分片不会产生冲突,还需要一些细致的技术工作。从这方面来说,Zilliqa的方法有些简单 (2)。
尽管之前有提出过对存储分片但不对处理分片的方案,但这是极不寻常的情况。在实践中,对存储分片,也就是状态分片,几乎总是隐含了对处理分片和网络分片。
实际上,状态分片中,每个分片中的节点都在构建他们自己分片的区块链,这条链仅包含那些对被分配给该分片的全局状态的本地部分产生影响的交易。因此,分片的验证节点只需要存储全局状态的本地(分片)部分,也仅仅执行和中继那些影响到这些本地状态的交易。这种分区线性地减少了所有包括算力、存储、带宽的需求。但是这也带来了新的问题,例如数据可用性和跨分片交易的问题。这两个问题我们会在下文阐述。
1.4 跨分片交易
迄今为止,我们描述的分片模型还不是很有用。如果单个分片不能跟其他分片互相通信,整个系统不过就是多个独立的区块链而已。甚至在分片技术还不可用的今天,不同区块链之间的互操作性依然是一个巨大的需求。
现在,让我们只考虑简单支付交易,每个参与者仅在一个分片上拥有账户。如果有用户希望在同一分片内从一个账户转账到另一账户,这笔交易可以由本分片的验证节点全权处理。然而,如果分片1上的Alice想转账给分片2上的Bob,无论是分片1上的验证节点(他们无法把账存入Bob的账户),还是分片2上的验证节点(他们无法把账从Alice的账户取出),都不能处理整笔交易。
有两种跨分片交易的实现方案:
同步:无论何时,一笔跨分片交易需要执行时,所涉及分片上含有相关交易状态转移信息的区块都同时生成。这些分片的验证节点合作执行此类交易。
异步:影响多个分片的跨分片交易在其所涉及的分片上异步执行。贷记方的分片一旦有了充足的证据,表明借记方分片已经执行了借记那边的工作,就可以执行自己这边的贷记工作。这种方案更趋于流行,因为它比较简单,并且易于协同。这种系统被Cosmos、以太坊宁静、NEAR、Kadena等采用。这种方案有一个问题,如果区块是独立产生的,相关区块中的某个成为孤块的可能性总归存在,导致整个交易仅被部分执行。
想一下图2中描述的情况:两个分片都遭遇分叉。同时,一笔跨分片交易相应记录于块 A 和块X’ 中。如果链 A-B 和 链 V’-X’-Y’-Z’ 成为了各自分片的正统链,则跨分片交易完全确认。若 A’-B’-C’-D’ 和 V-X 成为正统链,则跨分片交易完全被遗弃,这也是可以接受的。但如果 A-B 和V-X 成为正统链,则跨分片交易的一部分确认,另一部分被遗弃,这会导致一个原子性错误。我们在第二部分中提出的协议里,会介绍该问题的解决办法,包括分片协议提出的分叉选择规则以及共识算法的变动。

值得注意的是,跨链通信不止在分片区块链有用。链间的互操作性是个复杂的问题,许多项目想要解决这个问题。在分片区块链中,该问题相对简单些,因为区块结构和共识在分片之间都是相似的,还有一个信标链可以用来做协调。所有的分片链都是大同小异的,然而全局的区块链生态体系中有许多不同的链,他们有不同的目标使用场景、不同的去中心化程度和隐私保证程度。
构建这样一个包含公共信标链,和一系列虽然拥有不同属性、但有一系列足够类似的共识和结构的区块链系统,可以实现一个有可用互操作子系统的异构区块链生态。这样的系统不太可能有验证节点轮替的功能,所以需要采取一些额外措施确保安全性。Cosmos和波卡实际上都属于这种系统。
1.5 恶意行为
这一节,我们将回顾,如果恶意验证节点想破坏一个分片,会采用什么样的行为。我们将在2.1节回顾那些防止分片破坏的经典实现方法。
1.5.1 恶意分叉
一部分恶意验证节点也许试图创建一个分叉。需要注意的是,无论底层共识是否是BFT,买通足够数量的验证节点就都可能创建一个分叉。
相对来说,最可能发生的是买通一个分片中的50%以上(的验证节点),而不是买通整个链的50%以上(的验证节点)(我们将在2.1节详细阐述这些可能性)。正如1.4节中所讨论的,跨分片交易牵涉到多个分片中的某些状态改变,这类分片中应用这些状态变化的相应区块要么全部确定(即出现在对应分片被选中的分支上),要么全部成为孤块(即不出现在对应分片被选中的分支上)。一般意义上看,分片被破坏的可能性是不可忽视的,即使分片验证节点之间已经达成了某种拜占庭共识或是包含状态变化的块之上已经产出许多区块,我们也不能假设不会发生分叉。
这个问题有多种解决方案,最常用的一种是将分片链上最新的区块偶尔交叉连接到信标链上。分片链上的分叉选择规则相应变化为总会优选那些交叉连接的链,并且只对最后一个交叉连接之后产生的区块使用分片特定的分叉选择规则。
1.5.2 审批无效块
一些验证节点也许会尝试创建一个包含了不正确状态转换函数的区块。例如,从Alice有10枚通证、Bob有0枚通证的状态开始,区块可能包含包含一笔Alice转给Bob10枚通证的交易,但是最终状态如图3所示,Alice有0枚通证,Bob却获得了1000枚。

在一个经典的非分片区块链中,这种攻击是不可能成功的,因为网络中所有参与者都会验证所有的区块。一个带有无效状态转换的区块,其他出块人和不出块的网络参与者都会拒绝。即使恶意验证节点继续在这个无效区块之上以相对诚实验证节点更快的速度堆积新的区块,使得包含无效区块的链更长,也没有关系。因为,不管出于何种目的使用这个区块链的参与者都会验证所有区块,并丢弃那些构建在无效区块之上的所有区块。
图4中有五个验证节点,其中三个是作恶者。他们创建了一个无效区块 A’ ,并继续在其上创建新的区块。两个诚实验证节点丢弃无效的 A’ ,并在最后一个在他们看来有效的区块上构建区块,导致了一个分叉。因为诚实验证节点的分叉中验证节点的数量更少,所以他们的链更短一些。然而,在经典的非分片区块链中,每个出于各种目的使用区块链的参与者都负责验证所收到的所有区块,并重新计算状态。因此,任何关注该区块链的人都能发现A’ 是无效的,并立即丢弃 B’ 、 C’ 和 D’ 。这样一来,链 A-B 就是当前最长的有效链了。

但是,分片区块链中, 任何参与者都无法验证所有分片上的全部交易。所以它们需要某种方法确认,链上任何分片的任何历史状态中,都不存在无效的区块。
需要注意的是,与分叉不同,交叉连接到信标链并不是该问题的一个充分的解决方案,因为信标链无法验证所有区块。它只能验证该分片中有足够数量的验证节点签名(并以此作为其正确性的证据)。
我们将在下面的2.2节讨论该问题的解决方案。
2. 状态有效性和数据可用性
分片区块链的核心思想是大部分操作和使用网络的参与者无法验证所有分片的区块。因此,任何时候,参与者需要与某个特定的分片互动时,他们一般都无法下载和验证该分片的完整历史状态。
然而,分片的分区属性,引起了一个显著的潜在问题:如果不下载和验证特定分片的完整历史状态,参与者无法确信他们互动的状态是某个有效区块序列的结果,而且也不能确信这个序列就是该分片的正统链。这个问题在非分片区块链上是不存在的。
首先,我们会呈现解决该问题的一个简单方案,许多协议中也提出过这个方案。然后分析如何破解该方案,以及为了防止破解进行了哪些尝试。
2.1 验证节点轮替
解决状态有效性一个比较简单天真的方案如图5所示:假设整个系统有数千位验证节点,其中不超过20%的是作恶者或会失效(比如掉线无法出块)。然后,如果我们取出200个验证节点作为样本,那么样本中超过1/3的验证节点会失效的概率在实际中可以视为0。

1/3是个很重要的阈值。有一个共识协议族,叫做BFT共识协议,可以保证只要少于1/3的参与者失效,不管是宕机或以某种方式违反了协议,整个系统还是能达成共识。
在这种诚实验证节点百分比的假设下,若某分片的当前验证节点集合提供了某个块,简单的方案就认为该块是有效的,且构建在这些验证节点开始验证工作时就认定的该分片的正统链上。这些验证节点从之前的验证节点集合中识别了正统链,而根据同样的假设,这些验证节点构建的区块就在正统链的前面。这样推导下去,整个链都是有效的。而且,既然任何时间节点的验证节点集合都没有产生分叉,这种简单的方案也确信当前链就是该分片的唯一链。观察图6可获得一个直观感受。

如果我们假设验证节点受到自适应攻击,这个简单的方案就失效了。这个假设并非不合情理。自适应攻击拥有1000个分片的系统中的一个分片,其成本远低于去收买整个系统。因此,协议的安全性随着分片数量的增加而线性降低。为了确信一个块的有效性,我们必须知道系统的所有分片在任何历史时间点上,其大多数验证节点都没有勾结在一起。然而这种自适应破坏导致我们不再可以确信块的有效性。正如在1.5节中讨论的,被收买的验证节点可以实行两种基础的破坏行为:创建分叉,以及创建无效区块。
恶意分叉可以通过向信标链交叉连接区块的方式解决。信标链通常在设计上就比分片链有明显更高的安全性。然而,创建无效区块显然是个更难解决的问题。
2.2 状态有效性
看一下图7的情况:分片1被攻破了,恶意行为人产生了无效的区块B。假设在这个区块B里,Alice的账户上凭空铸造了1000枚通证。恶意行为人接着在B后面创建了有效区块C(意思是C中的交易正确执行),从而掩盖了无效的区块B,并发起了一个到分片2的跨分片交易,内容是转账那1000枚通证给Bob的账户。此时,非法生成的通证反而驻留在分片2中一个完全有效的区块里。

以下是应对该问题的一些简单方法:
· 分片2的验证节点(跨分片)验证产生交易的那个区块。这个方法在上图的场景中都不起作用,因为区块C看起来是完全有效的。
· 分片2的验证节点(跨分片)验证交易所在区块之前的一大批前置区块。自然的,对于接收分片验证的任何区块个数N,恶意验证节点都可以在产出的无效区块上创建N+1个有效区块来应对。
解决该问题的一个可行的方法是:把分片排列成无向图,每个分片都与若干其他分片相连。并且只允许这些相邻分片之间的跨分片交易(例子有,这就是Vlad Zamfir的分片精要的做法(3),而且在Kadena的Chainweb中也用了相似的思想[1])。如果非相邻的分片需要一个跨分片交易,多个(相邻)分片路由的方式可以解决。在这个设计中,每个分片中的验证节点都要验证自己分片和相邻分片的所有区块。下图有10个分片,每个都有4个相邻分片,对于跨分片交易的两个分片之间最多仅需要两跳(见图8)。

分片2不仅验证自己的区块,还验证所有相邻分片,其中包括分片1。如果一个分片1上的恶意行为人试图创建一个无效区块B,在其上创建区块C并发起跨分片交易,则这样的交易无法成功。因为分片2会验证分片1的完整历史,由此识别出无效的区块B。
尽管只攻破单个分片不再是可行的攻击方法,攻破若干分片仍然是个问题。在图9中,一个对手同时攻破了分片1和2,使用来自无效区块B的资金,执行了到分片3的跨分片交易:

分片3验证了分片2的所有区块,但是并不验证分片1的区块,因此无法检测到那个恶意区块。正确解决状态有效性问题有两个主要方向:渔夫与密码学计算证明。
2.3 渔夫
第一种实现方法背后的思想是:一旦一个区块头 (header) 因为某种目的(比如交叉连接到信标链或跨分片交易)在链间传递,就有一个时间窗口让诚实的验证节点提交那个区块无效的证明。如今存在各种各样的设计,允许通过简洁的证明即可指认无效区块。对于接收节点来说,区块头的通信远比要接收整个区块小多了。通过这种方法,只要分片中至少有一个诚实验证节点,系统就是安全的。

这是当前提出的协议中主流的实现方法(除非假设这个问题不存在)。然而,这种实现有两大主要缺陷。一是质疑的时间窗口要足够长,让诚实验证节点可以识别产生的区块、下载并完全校验区块,并准备好在验证出无效区块时提出质疑。引入这么一种时间段会明显拖慢跨分片交易。
二是质疑机制的存在导致了一个新的攻击维度,作恶者用大量无效的质疑冲击系统。该问题的一个直接解决方案是让质疑者抵押一定量的通证,质疑有效才归还。但这也只是部分解决了问题,因为有可能对手(在抵押被没收的情况下)仍然能通过无效质疑获利。例如,以此阻止诚实验证节点的质疑获得通过。这种攻击被称为Griefing Attack(损人不利己)。处理后面这个问题的方法,参见3.7.2节。
2.4 简洁的非交互知识论证
第二种应对多分片贿赂的方案是使用某种密码学的措施,允许一个人证明某个计算(比如从一系列交易中算出区块)被正确执行了。这种措施确实存在,比如 zk-SNARKs、zk-STARKs 等技术,经常用在当今隐私支付领域的区块链协议中,其中最知名的是ZCash。那些方案的主要问题是计算起来非常慢。例如,Coda协议,专门使用zk-SNARKs证明链上的所有区块都是有效的,在一次访谈中表示,为了创建一个证明,每笔交易要花费30秒时间(目前这个数字可能要小些)。
有趣的是,证明未必需要一个可信实体进行计算。因为证明不仅能证实它的目标计算的有效性,还能证实其自身的有效性。因此,这种证明的计算工作可以分配给一系列参与者,与必须执行某些无需信任的计算相比,显著降低了冗余。它也允许计算zk-SNARKs的参与者运行在特殊的硬件上,同时不会减低系统的去中心化程度。
除了性能外,zk-SNARKs面临的挑战还有:
· 依赖于鲜有研究和缺少时间验证的密码学基元 (primitives);
· “有害废弃物”-- zk-SNARKs依赖于一个可信的设置过程,其中一组人执行某种计算,并丢弃该计算的中间值。如果该过程的所有参与者互相勾结,保留了中间值,则就能创建虚假证明;
· 系统设计引入额外的复杂性;
· zk-SNARKs只适用于所有可能计算的一个子集。所以,支持图灵完备的智能合约语言的协议将不能使用SNARKs证明链的有效性。
2.5 数据可用性
我们遇到的第二个问题是数据可用性。一般来说,运行特定区块链的节点分为两种:全节点,指那些下载每一个完整区块并验证每一笔交易的节点;和轻节点,指那些仅下载区块头、并对其关注的部分状态和交易应用默克尔证明的节点。参见图11。

如果大部分全节点互为勾结,他们可以创建有效或无效的区块,并发送其哈希值给轻节点,但从不暴露该区块的全部内容。有多种方式可以让他们从中受益。例如,图12的情况:

这里有3个区块:前置区块A,由诚实验证节点创建;当前区块B,由受贿的验证节点签发;以及接下来的区块C,也将由诚实验证节点创建(区块链描绘在图的右下角)。
假设你是个商家。当前区块B的验证节点从前代验证节点手里接收到区块A,接着计算出你收到钱的区块,并发送给你一个包括默克尔证明的该块区块头,显示拥有这笔钱的状态(或者是发送给你钱的有效交易的默克尔证明)。你确信这笔交易已确定,所以提供了相应服务。
然而,验证节点从未把区块B的全部内容分发给任何人。因此,构建区块C的诚实验证节点无法获取该区块,只能强制终止整个系统,或者在区块A上构建新块,同时剥夺你作为商家对那笔钱的所有权。
当我们把相似的场景放到分片上,全节点和轻节点的定义一般可以对应到每个分片上:每个分片的验证节点下载该分片的每个区块并验证其中的每笔交易,但是系统中的其他节点,包括那些快照分片链状态到信标链的节点,都只下载区块头。因此,分片验证节点对该分片来说,实际上就是全节点,而系统的其他参与者,包括信标链,就像一个轻节点那样运作。
为了让我们前面讨论的渔夫方案发挥作用,诚实验证节点需要能下载交叉连接到信标链的区块。然而,如果恶意验证节点交叉连接一个无效区块的头部(或使用它发起跨分片交易),但从不分发该区块,那么诚实验证节点就无法发起质疑。我们将介绍应对该问题的三种互补的解决方案。
2.5.1 托管证明
亟待解决的最直接问题是,区块一旦被发布是否就是可用的。一种想法是,使用被称为公证人(Notary)的角色,让其在分片中以比验证节点更快的频率轮转。他们唯一的工作是下载一个区块并证明他们有能力下载它。他们之所以能更频繁的轮转,是因为无需下载分片的整个状态,不像验证节点,后者每次轮转都要下载分片的状态,因此不能频繁轮转,如图13所示。

该想法不足之处在于,后面无法验证某个公证人是否真能下载那个区块。因此,一个公证人可以选择总是声称他们能下载那个区块,甚至不用尝试获取这个区块。一个解决方案是让公证人提供某种证据证明其下载了区块或质押一定数量的通证作为担保费。这里讨论了该类方案的其中一种:
https://ethresear.ch/t/1-bit-aggregation-friendly-custody-bonds/2236.
2.5.2 纠删码
当一个特定的轻节点收到一个区块哈希值时,为了提升节点对区块可用性的信心,它可以尝试下载该区块的一些随机碎片。这还不是一个完整的方案,因为除非轻节点联合下载完整区块,恶意出块人可以选择扣押区块中未被任何轻节点下载的那部分内容,因此仍可以使区块不可用。
一个解决方案是使用一种称为“纠删码”的措施,即使在只有区块的部分内容可用的情况下,也能恢复整个区块,如图14所示。

波卡和以太坊宁静都采用了基于这种思想的设计,为轻节点提供了一种方式,使其能确信区块是可用的。以太坊宁静的实现在参考文献2中有详细介绍[2]。
2.5.3 波卡对数据可用性的实现
和大部分分片方案一样,波卡每个分片(叫做平行链)快照它的区块到信标链(叫做中继链)。假设中继链有2f+1个验证节点。平行链的出块人叫做整理人.平行链区块一产出,整理人便计算该区块的一个纠删码版本,其中包含2f+1个部分,因此任意f个部分都能重建整个区块。
然后他们给每个中继链的验证节点分发一个部分。一个特定的中继链验证节点,只有在中继链验证节点拥有每个被快照至该中继链区块的每个平行链区块的专属部分,该验证节点才对该中继链区块签名。因此,如果一个中继链区块包含来自2f+1个验证节点的签名,且只要其中不超过f个验证节点违反了协议,那每个平行链区块都还是能从那些遵循了协议的验证节点手中重建出来。见图15。

2.5.4 长期数据可用性
值得注意的是,上述方案都只能证明一件事:已经发布一个区块且当前可用。一段时间后,由于以下各种原因,区块可能变为不可用:节点下线,节点故意删除了历史数据等。
对于该问题,Polyshard [3]的白皮书值得一提:使用纠删码确保区块在分片之间是可用的,即使一些分片完全丢失了他们的数据也无妨。不幸的是,他们的特定实现需要任一分片都下载其他所有分片的区块,成本过于高昂。
还好长期可用性问题并不太急迫,因为系统并不指望其参与者能验证所有分片上的所有链。所以,分片协议的安全性设计需要能够做到:即使一些分片的旧区块变得完全不可用,整个系统依然是安全的。
3. 夜影分片协议
3.1 从分片链到分片段
这种多个分片链加一个信标链的分片模型非常强大,但也相当复杂。特别的,分叉选择规则需要在每个链上独立执行,而且分片链和信标链的分叉选择规则一定要有区别的构建和独立的测试。
在夜影中,我们把系统建模成一个单一的区块链,其中每个块逻辑上包含所有分片的全部交易,以及改变所有分片的整个状态。然而,从物理的角度看,任何参与者都不会下载完整的状态或完整的逻辑区块。网络的每个参与者其实只是维护他们为之验证交易的分片上对应的状态。区块中的所有交易的列表都被分割成物理上的段,每个分片对应一个段。
在理想的条件下,每个(逻辑)块里,每个分片都正好有一个分段对应。这基本上对应到分片链模型中,分片链和信标链以相同的速度出块。然而,由于网络延迟,一些分段可能错过(出块),所以在实践中,每个(逻辑)块的每个分片对应着0个或1个分段。对如何出块的详细介绍参见3.3节。

3.2 共识
当今区块链共识的两个主流方法是:最长(或最重)链共识,指由最多工作量或权益打造的链被认为是正统链;以及BFT共识,指对于每个块,都由一批验证节点在其中达成一个BFT共识。
在最近提出的协议中,后一种共识的实现更加流行一些。因为它提供了即时的确定性,而在最长链规则中,需要更多的区块创建在目标区块之后,才能确保确定性。通常,为了达到一个严谨的安全等级,需要小时级别的时间才能有足够数量的区块(在目标区块之后)创建出来。
对每个块使用BFT共识,也有些缺点,例如:BFT共识涉及相当多的通信量。尽管最新进展允许以参与者达成共识的时间与网络参与者的数量形成线性关系(见[4]),但这个工作量对每个块来说仍然是不可忽视的;
所有网络参与者都参与每个块的BFT共识是不现实的,因此通常仅有一个参与者的随机样本子集参与达成共识。一个随机的样本集合,原则上是可能受到自适应攻击的,因此理论上分叉是会出现的。系统在设计上要么需要为这种情况做好准备(因此,除了BFT共识,依然还要有分叉选择规则),要么就要在这种情况下关闭。值得一提的是,某些设计,例如Algorand [5],已大大降低了自适应攻击的可能性。
最重要的是,如果1/3或更多的参与者掉线,系统将中止。因此,任何临时的网络小故障或一个网络分裂就会使系统完全瘫痪。理想情况是,系统必须能够继续运行,只要至少一半的参与者在线(基于最重链的协议,甚至能在少于一半参与者在线的情况下继续运行,但是这个特点是否必要在社区内还有不少争论)。
在一个混合模型中,共识使用的是某种最重链规则,但是周期性的对一些块使用BFT确定性工具来实现其确定性。这样就同时保有了两种共识模型的优点。这种BFT确定性工具有用于以太坊2.0 (1)的Casper FFG [6]、Casper CBC和用于波卡的GRANDPA 。
Casper CBC:
https://vitalik.ca/general/2018/12/05/cbc_casper.html
GRANDPA:
https://medium.com/polkadot-network/d08a24a021b5)。
夜影使用最重链共识。尤其当一个出块人产生一个区块时(参见3.3节),他们可以从其他出块人和验证节点中收集签名,作为对前一个区块的证明。参见3.8节对于如何积累如此大量签名的详细介绍。一个区块的权重就是所有那些在区块中签了名的签名者积累的抵押权益。而一个链的权重就是区块权重的和。
在最重链共识之上,我们使用一个确定性工具,利用证明确定区块。为了减低系统复杂度,我们使用的确定性工具在任何情况下都不影响分叉选择规则,而只是引入额外的罚没质押通证条件。这样一来,一旦一个区块被确定性工具确定下来,就不可能出现分叉,除非占总权益极大百分比的权益都被罚没了。
Casper CBC就是这样一种确定性工具,我们在设计时有参考Casper CBC。
我们也在研究一个独立的BFT协议,叫做TxFlow。撰写本文时,尚不清楚TxFlow是否会用来取代Casper CBC。然而,我们注意到,确定性工具的选择在很大程度上与设计的其余部分无关。
3.3 出块
夜影中有两种角色:出块人和验证节点。设系统有w个出块人,以及wv个验证节点 (v在这里指的是验证节点和出块人的比例),在我们的模型里w=100,v=100(此处v的定义原文中没给),wv=10000。作为一个权益证明(POS)系统,意味着出块人和验证节点把一定数量的内部货币(称为“通证”)锁定一段时间,且这段锁定期远超过他们用来执行构建和验证链的时间。
与所有的PoS系统一样,不一定w个出块人和wv个验证节点都是不同的实体,因为这是无法强制的。然而,w个出块人和wv个验证节点中的每一个节点都单独抵押权益。
系统包含n个分片,我们的模型中n=1000。正如3.1节提到的,夜影中没有分片链,取而代之的是,所有的出块人和验证节点共同构建单一的区块链,我们称之为主链。主链的状态被分到n个分片中。每个出块人和验证节点在任何时候都只在本地下载对应某个分片子集的状态子集,且只处理和验证影响这部分状态的交易。
要成为出块人,一个网络参与者锁定一大笔通证(一笔质押权益)。网络按周期(epoch)进行维护,一个周期是数天级别的时间长度。每个周期之初,质押权益最多的前w个参与者就是该周期的出块人。每个出块人指派给sw个分片,(设sw=40,则每分片有 swW/n = 4个出块人)。在周期开始前,出块人下载所指派分片的状态,然后在整个周期中收集影响该分片的交易,并把它们应用到状态上。
对于主链上的每个块b,和每个分片s,都有一个指定给s的出块人负责生产b上有关该分片的区块部分。这个部分被称为分片段,包含了b中有关该分片的交易列表,以及结果状态的默克尔树根。b最终只包含该分片段的一个很小的段头,也就是所有应用交易的默克尔树根(具体信息参见3.7.1节),和最终状态的默克尔树根。
本文剩余部分,我们通常把在特定时间为特定分片创建分片段的出块人称为出段人,出段人一定是出块人之一。
出块人和出段人根据一个固定的安排轮换每个块。出块人有个顺序并依序重复出块。例如,如果有100个出块人,第一位出块人负责创建块1、101、201等,第二位出块人负责2、102、202等。
创建分片段与创建区块不同,需要维护状态。而且对每个分片来说,仅仅 swW/n 位出块人维护着每个分片的状态,相应的也就只有这swW/n位出块人轮换创建分片段。例如,按照上面的常量设定,一个分片指定了4个出块人,每个出块人每四个块创建一次分片段。
3.4 确保数据可用性
为了确保数据可用性,我们使用了跟2.5.3节描述的波卡类似的方式。一旦一个出块人创建了一个分片段,就创建该分片段的一个纠删码版本,纠删码参数为(w, ⌊w/6 + 1⌋),然后发送该段纠删码的每一片(我们称这样的码片为段颗粒chunk parts,或者就叫颗粒parts)给每个出块人。
我们计算出一棵默克尔树,其中每个颗粒都是叶子,并在每个段的头部都包含该默克尔树的根。这些颗粒通过单颗粒消息(onepart message)发给验证节点。每条这种消息包含该段的段头、颗粒序号以及颗粒内容。消息中还包含创建该段的出块人的签名,以及证明该颗粒对应头部且由正确的出块人创建的默克尔路径。
一旦一个出块人收到一个主链的块,他首先检查自己是否有该块包含的每个段的单颗粒消息。如果没有,该块就不被处理,直到获取到缺失的单颗粒消息。
一旦所有的单颗粒消息收全了,这个出块人从其他出块人那里拿来剩余部分并重建他们为之持有状态的那些段。
出现以下情况时,出块人不会处理主链区块:如果区块中至少有一个分片段的对应单颗粒消息未收到;或如果他负责维护状态的分片中至少有一个分片无法重建出对应的完整段。
若要一个特定的分片段可用,只要有⌊w/6⌋+1的出块人持有并能提供相关的颗粒即可。因此,只要作恶者的数量不超过⌊w/3⌋,就不会让一个超过半数出块人(在线)的链含有无效的分片段。

3.4.1 处理懒惰的出块人
如果一个出块人遇到一个缺失了一条单颗粒消息的块,他可能仍然会签名。因为如果这个块最终上链了,就能使该出块人的利益最大化。而且这对出块人没有风险,因为过后无法证明这个出块人没有那条单颗粒消息。
为了解决这个问题,我们让每个出段人在创建段的时候为后面经过编码的段的每个颗粒选择一个颜色(红或蓝),并在编码前将所选颜色的掩码存入段中。每条单颗粒消息都包含该颗粒指定的颜色,这个颜色也用来计算编码颗粒的默克尔根。如果出段人违反协议,将被轻易检测出来。因为,要么默克尔根对不上单颗粒消息,要么匹配了默克尔根的单颗粒消息中的颜色与段的掩码不匹配。
当出块人签名一个区块时,他将收到的该块中所有段的红色颗粒做成掩码放在签名中。发布一个不正确的掩码是一种可罚没质押通证的行为。如果一个出块人没有收到某条单颗粒消息,是无法知道其颜色的,因此尝试盲签区块就有50%的可能性会被惩罚。
3.5 状态转换的执行
出段人创建段时,只是选择哪些交易要放在段中,而不会执行状态转换。相应的,段头部包含执行该段交易之前的默克尔状态的默克尔根。仅当一个包括该段的完整区块得到处理时,这些交易才会执行。而一个参与者仅在以下条件达成时处理区块:
前一个区块已经接收并得到处理;
对于不维护状态的那些段,参与者见到了单颗粒消息;
对于需要维护状态的那些段,参与者拥有完整的段。
一旦区块得到处理,对于那些需要维护状态的每个分片,参与者执行交易并计算交易执行后的新状态。之后,如果被分配到任何分片,参与者就准备好创建下个区块的对应段,因为他已经有了新默克尔状态的默克尔根。
3.6 跨分片交易和收据
如果一笔交易不止影响一个分片,就需要在不同的分片中连续独立执行。完整的交易发给第一个相关的分片。一旦该分片的段中包含了该交易,且在该段被包含进区块之后被执行,就会产生一笔收据(receipt)交易。该收据被路由给下一个需要执行该交易的分片。如果跨分片交易需要更多的步骤,则当执行收据交易的时候,会产生一笔新的收据交易,如此循环。
3.6.1 收据交易生命周期
理想的情况是,收据交易在产生收据的块的下一个块中立刻被执行。只有在维护源分片的出块人接收并执行了前一个块后,收据交易才会生成。并且,需要在目的分片的出块人为下一个区块创建段之前被其知晓。因此,在这两个事件间的一段短时间内,收据必须由源分片通信到达目的分片。
假设 A 是最后产生的区块,包含交易 t,而 t 产生了收据 r 。把下一个将产生的区块记为B (也就是说,这个块将 A 作为其前置区块),我们希望在 B 中包含 r 。假设 t 在分片a 中,而 r 在分片 b中。如图18中所述,收据的生命周期如下:产生和存储收据。分片 a 的出段人 cpa收到块 A , 执行交易 t ,并生成收据r 。cpa接着将所有生成的收据存储在它内置的持久化存储中,以源分片的id为索引。
分发收据。一旦cpa准备为块 B 创建分片a 的段,他获取到所有通过执行块 A 中分片 a 的相关交易时产生的收据,并将它们包含在块 B 对应分片 a 的段中。段生成后,cpa产生它的纠删码版本,和所有对应的单颗粒消息。cpa知道哪些出块人维护哪些分片的全状态。对一个特定的出块人 bp,cpa在发布区块 B 里对应分片 a 的段时,把一些收据放进单颗粒消息中,这些收据是执行块A中有关分片 a 的交易的结果,且这些交易的目的分片是 bp 去维护状态的(收据放进单颗粒消息的展示参见图17)。
接收收据。回忆一下,参与者(包括出块人和验证节点)不会执行块,除非他们有了块中每个分片段的单颗粒消息。因此,在任何参与者执行区块B 的时候,他们已经获得 B 中所有段对应的全部单颗粒消息,也就拥有了所有传入的收据,这些收据以参与者维护状态的分片为目的地。当执行一个特定分片的状态转换时,参与者既执行单颗粒消息中与该分片有关的收据交易,也执行该段自身包含的所有交易。

3.6.2 应对过量的收据
有可能指向一个特定区块的特定分片的收据的数量过大,超过了其处理能力。例如,图19的情况,每个分片的每笔交易都产生了一个指向分片1的收据。到下个区块时,分片1需要处理的收据数量已经与上个区块中所有分片合起来要处理的收据数量一样多了。

要解决这个问题,我们使用一个类似QuarkChain (2) 中使用的技术。特别的,对每个分片,最后的区块B中最后一条被执行的收据所在的分片s被记录下来。当新的段创建时,会首先从块B中遗留还未处理的收据开始执行,接着才是块B之后的区块,直到新的段被塞满为止。
在正常情况下,随着负载均衡,这个过程的结果是所有收据都被执行(因此每个段中记录的都是最后一个块的最后一个分片)。然而,当负载不均衡时,如果一个特定的分片收到了过多的收据,该技术也能允许这些收据在段中交易条数有限制的前提下被处理。
需要注意的是,如果这种负载不均衡持续了很长时间,则收据从创建到执行之间的延迟可能持续地无限增长。一种解决方式是,当收据指向的是处理延迟超过了某个常数(例如,一个周期)的分片时,该收据产生的交易会被丢弃。
考虑图20的情况。直到区块B时,分片4还没有处理完所有收据。它仅处理到来自区块A中分片3所产生的收据,并记录了下来。在区块C时,收据处理跟进到区块B的分片5,最后在区块D时,该分片赶上了进度,处理了区块B里所有遗留的收据和区块C里的全部收据。

声明:链世界登载此文仅出于分享区块链知识,并不意味着赞同其观点或证实其描述。文章内容仅供参考,不构成投资建议。投资者据此操作,风险自担。此文如侵犯到您的合法权益,请联系我们kefu@lianshijie.com

参与讨论 (0 人参与讨论)

相关推荐

谷燕西:终止运行的Quibi对区块链应用的启示

最近,Quibi因为缺少资金支持,宣布停止运行。Quibi产品于2020年4月正式发布。即使是在今天,Quibi的这些判断依然成立。而Quibi的商业运作策略导致了它的目前的终止运行。Quibi失败的经历同样值得区块链领域中的公司借鉴。

为什么Synthetix选择Optimism扩容方案?

它还将给出在主网实现OVM的Synthetix变体所需的治理过程设计,以及说明何种情况下另一种扩容技术可以替代Optimistic Ethereum。本文旨在确保就Synthetix迁移到Optimistic Ethereum,社区成员能有达成共识所需的信息。

慢雾:Harvest.Finance 被黑事件简析

2020 年 10 月 26 号,据慢雾区消息 Harvest Finance 项目遭受闪电贷攻击,损失超过 400 万美元。以下为慢雾安全团队对此事件的简要分析。

区块链技术赋能供应链金融的四类常见模式

重点分析下区块链技术能为供应链金融做些什么。常见的“区块链+供应链金融”模式大致有以下四种:基于实物资产数字化的采购融资模式这种模式主要应用在大宗商品行业,常见的如钢材的代采模式等。

既不能神化,也不要泛化区块链

既不能神化,也不要泛化区块链

"把区块链作为核心技术自主创新重要突破口,加快推动区块链技术和产业创新发展",虽然距离去年1024讲话已有一年时间,但是大众对区块链的热情并未减退。近日,央行数字货币研究所副所长狄刚在"打造区块链新引擎助力产业新升级论坛暨《读懂区块链》新书发布会"上表示,数字金融技术里面非常重要的就是区块链技术,目前我们对区块链的认识还处于发展的初级阶段,既不能神化,也不要泛化区块链技术。他认为,我们对区块链的认

分布式存储世界中的坚定逆行者—DxChain的新式架构和生态理念

分布式存储领域第一个采用DPoS共识机制的存储公链,DxChain或许给了我们一个可能。2018年8月,DxChain完成公募,DX正式登陆三家交易所,成为诸多交易代币中的一员。

中信银行打造“区块链”信用证结算!

中信银行打造“区块链”信用证结算!

科技不会改变金融的实质,但却能让金融服务更高效,能让资金供、需方信息不对称的问题更好地解决。近期,中信银行首个区块链项目——基于区块链的国内信用证信息传输系统(简称BCLC)(一期)成功上线,这是国内银行业第一次将区块链技术应用于信用证结算领域。 据中信银行国际业务部总经理助理张栩青介绍,将现在流行的区块链技术应用在国内信用证中,改变了银行传统信用证业务模式,信用证的开立、通知、交单、承兑报文

中国信息技术部门成立区块链研究实验室

中国信息技术部门成立区块链研究实验室

暴走时评:本月初,中国政府对国内的ICO和数字货币交易所的打击在世界范围内引起了强大反响,但政府已经多次声明不会将区块链与数字货币划等号,依然非常重视区块链技术在中国的发展。鉴于中国工业和信息化部成立了一个专门研究区块链的实验室,这一论调也得到了进一步的证实。 虽然中国政府最近在大力打击比特币交易所和ICO,但仍然致力于开发区块链在其他领域的潜力。 据财新网报道,中国工业和信息化部已经成立了一

麦妖榜
更新日期 2019-09-03
排名用户贡献值
1牛市来了30910
2BitettFan24187
3等待的宿命23810
4区块大康20369
5六叶树20310
6linjm122719429
7天下无双16192
8lizhen00215280
9让时间淡忘14586
10yelanyi050511349
返回顶部 ↑