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

众所周知，以太坊作为迄今为止最广为使用的通用区块链，主网每秒只能处理不到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协议创新的的夜影方案。

关于分片的基础知识

让我们从最简单的分片方法开始。举例来说，不同于运行一个链，我们运行多个链，每个链称为一个“分片”。每个分片有自己的验证节点集合。在下文里，不管是POW中挖矿的方式，还是投票机制，我们都会使用这个原生词汇“验证节点”，去指代那些进行交易验证和生产区块的参与者。同时，让我们先假设各个分片之间互不通信。

这一设计，虽然简单，但却足够概括早期分片面临的一些主要挑战了。

1.1 验证节点分区和信标链

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

图 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 成为正统链，则跨分片交易的一部分确认，另一部分被遗弃，这会导致一个原子性错误。我们在第二部分中提出的协议里，会介绍该问题的解决办法，包括分片协议提出的分叉选择规则以及共识算法的变动。

图 2：异步跨分片交易

值得注意的是，跨链通信不止在分片区块链有用。链间的互操作性是个复杂的问题，许多项目想要解决这个问题。在分片区块链中，该问题相对简单些，因为区块结构和共识在分片之间都是相似的，还有一个信标链可以用来做协调。所有的分片链都是大同小异的，然而全局的区块链生态体系中有许多不同的链，他们有不同的目标使用场景、不同的去中心化程度和隐私保证程度。

构建这样一个包含公共信标链，和一系列虽然拥有不同属性、但有一系列足够类似的共识和结构的区块链系统，可以实现一个有可用互操作子系统的异构区块链生态。这样的系统不太可能有验证节点轮替的功能，所以需要采取一些额外措施确保安全性。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枚。

图 3：无效区块的一个例子

在一个经典的非分片区块链中，这种攻击是不可能成功的，因为网络中所有参与者都会验证所有的区块。一个带有无效状态转换的区块，其他出块人和不出块的网络参与者都会拒绝。即使恶意验证节点继续在这个无效区块之上以相对诚实验证节点更快的速度堆积新的区块，使得包含无效区块的链更长，也没有关系。因为，不管出于何种目的使用这个区块链的参与者都会验证所有区块，并丢弃那些构建在无效区块之上的所有区块。

图4中有五个验证节点，其中三个是作恶者。他们创建了一个无效区块 A’ ，并继续在其上创建新的区块。两个诚实验证节点丢弃无效的 A’ ，并在最后一个在他们看来有效的区块上构建区块，导致了一个分叉。因为诚实验证节点的分叉中验证节点的数量更少，所以他们的链更短一些。然而，在经典的非分片区块链中，每个出于各种目的使用区块链的参与者都负责验证所收到的所有区块，并重新计算状态。因此，任何关注该区块链的人都能发现A’ 是无效的，并立即丢弃 B’ 、 C’ 和 D’ 。这样一来，链 A-B 就是当前最长的有效链了。

图 4：试图在非分片区块链中构建无效区块

但是，分片区块链中， 任何参与者都无法验证所有分片上的全部交易。所以它们需要某种方法确认，链上任何分片的任何历史状态中，都不存在无效的区块。

需要注意的是，与分叉不同，交叉连接到信标链并不是该问题的一个充分的解决方案，因为信标链无法验证所有区块。它只能验证该分片中有足够数量的验证节点签名（并以此作为其正确性的证据）。

我们将在下面的2.2节讨论该问题的解决方案。

状态有效性和数据可用性

分片区块链的核心思想是大部分操作和使用网络的参与者无法验证所有分片的区块。因此，任何时候，参与者需要与某个特定的分片互动时，他们一般都无法下载和验证该分片的完整历史状态。

然而，分片的分区属性，引起了一个显著的潜在问题：如果不下载和验证特定分片的完整历史状态，参与者无法确信他们互动的状态是某个有效区块序列的结果，而且也不能确信这个序列就是该分片的正统链。这个问题在非分片区块链上是不存在的。

首先，我们会呈现解决该问题的一个简单方案，许多协议中也提出过这个方案。然后分析如何破解该方案，以及为了防止破解进行了哪些尝试。

2.1 验证节点轮替

解决状态有效性一个比较简单天真的方案如图5所示：假设整个系统有数千位验证节点，其中不超过20%的是作恶者或会失效（比如掉线无法出块）。然后，如果我们取出200个验证节点作为样本，那么样本中超过1/3的验证节点会失效的概率在实际中可以视为0。

图 5：验证节点取样

1/3是个很重要的阈值。有一个共识协议族，叫做BFT共识协议，可以保证只要少于1/3的参与者失效，不管是宕机或以某种方式违反了协议，整个系统还是能达成共识。

在这种诚实验证节点百分比的假设下，若某分片的当前验证节点集合提供了某个块，简单的方案就认为该块是有效的，且构建在这些验证节点开始验证工作时就认定的该分片的正统链上。这些验证节点从之前的验证节点集合中识别了正统链，而根据同样的假设，这些验证节点构建的区块就在正统链的前面。这样推导下去，整个链都是有效的。而且，既然任何时间节点的验证节点集合都没有产生分叉，这种简单的方案也确信当前链就是该分片的唯一链。观察图6可获得一个直观感受。

图 6：每个块都通过BFT共识确定的区块链

如果我们假设验证节点受到自适应攻击，这个简单的方案就失效了。这个假设并非不合情理。自适应攻击拥有1000个分片的系统中的一个分片，其成本远低于去收买整个系统。因此，协议的安全性随着分片数量的增加而线性降低。为了确信一个块的有效性，我们必须知道系统的所有分片在任何历史时间点上，其大多数验证节点都没有勾结在一起。然而这种自适应破坏导致我们不再可以确信块的有效性。正如在1.5节中讨论的，被收买的验证节点可以实行两种基础的破坏行为：创建分叉，以及创建无效区块。

恶意分叉可以通过向信标链交叉连接区块的方式解决。信标链通常在设计上就比分片链有明显更高的安全性。然而，创建无效区块显然是个更难解决的问题。

2.2 状态有效性

看一下图7的情况：分片1被攻破了，恶意行为人产生了无效的区块B。假设在这个区块B里，Alice的账户上凭空铸造了1000枚通证。恶意行为人接着在B后面创建了有效区块C（意思是C中的交易正确执行），从而掩盖了无效的区块B，并发起了一个到分片2的跨分片交易，内容是转账那1000枚通证给Bob的账户。此时，非法生成的通证反而驻留在分片2中一个完全有效的区块里。

图 7：来自一个无效区块的跨分片交易

以下是应对该问题的一些简单方法：

• 分片2的验证节点（跨分片）验证产生交易的那个区块。这个方法在上图的场景中都不起作用，因为区块C看起来是完全有效的。
• 分片2的验证节点（跨分片）验证交易所在区块之前的一大批前置区块。自然的，对于接收分片验证的任何区块个数N，恶意验证节点都可以在产出的无效区块上创建N+1个有效区块来应对。

解决该问题的一个可行的方法是：把分片排列成无向图，每个分片都与若干其他分片相连。并且只允许这些相邻分片之间的跨分片交易（例子有，这就是Vlad Zamfir的分片精要的做法(3)，而且在Kadena的Chainweb中也用了相似的思想[1]）。如果非相邻的分片需要一个跨分片交易，多个（相邻）分片路由的方式可以解决。在这个设计中，每个分片中的验证节点都要验证自己分片和相邻分片的所有区块。下图有10个分片，每个都有4个相邻分片，对于跨分片交易的两个分片之间最多仅需要两跳（见图8）。

图 8：一个跨分片的无效交易会在类chainweb系统里被检测到

分片2不仅验证自己的区块，还验证所有相邻分片，其中包括分片1。如果一个分片1上的恶意行为人试图创建一个无效区块B，在其上创建区块C并发起跨分片交易，则这样的交易无法成功。因为分片2会验证分片1的完整历史，由此识别出无效的区块B。

尽管只攻破单个分片不再是可行的攻击方法，攻破若干分片仍然是个问题。在图9中，一个对手同时攻破了分片1和2，使用来自无效区块B的资金，执行了到分片3的跨分片交易：

图 9：一个在类chainweb系统中检测不到的无效跨分片交易

分片3验证了分片2的所有区块，但是并不验证分片1的区块，因此无法检测到那个恶意区块。正确解决状态有效性问题有两个主要方向：渔夫与密码学计算证明。

2.3 渔夫

第一种实现方法背后的思想是：一旦一个区块头 (header) 因为某种目的（比如交叉连接到信标链或跨分片交易）在链间传递，就有一个时间窗口让诚实的验证节点提交那个区块无效的证明。如今存在各种各样的设计，允许通过简洁的证明即可指认无效区块。对于接收节点来说，区块头的通信远比要接收整个区块小多了。通过这种方法，只要分片中至少有一个诚实验证节点，系统就是安全的。

图 10：渔夫

这是当前提出的协议中主流的实现方法（除非假设这个问题不存在）。然而，这种实现有两大主要缺陷。一是质疑的时间窗口要足够长，让诚实验证节点可以识别产生的区块、下载并完全校验区块，并准备好在验证出无效区块时提出质疑。引入这么一种时间段会明显拖慢跨分片交易。

二是质疑机制的存在导致了一个新的攻击维度，作恶者用大量无效的质疑冲击系统。该问题的一个直接解决方案是让质疑者抵押一定量的通证，质疑有效才归还。但这也只是部分解决了问题，因为有可能对手（在抵押被没收的情况下）仍然能通过无效质疑获利。例如，以此阻止诚实验证节点的质疑获得通过。这种攻击被称为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。

图 11：默克尔树

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

图 12：数据可用性问题

这里有3个区块：前置区块A，由诚实验证节点创建；当前区块B，由受贿的验证节点签发；以及接下来的区块C，也将由诚实验证节点创建（区块链描绘在图的右下角）。

假设你是个商家。当前区块B的验证节点从前代验证节点手里接收到区块A，接着计算出你收到钱的区块，并发送给你一个包括默克尔证明的该块区块头，显示拥有这笔钱的状态（或者是发送给你钱的有效交易的默克尔证明）。你确信这笔交易已确定，所以提供了相应服务。

然而，验证节点从未把区块B的全部内容分发给任何人。因此，构建区块C的诚实验证节点无法获取该区块，只能强制终止整个系统，或者在区块A上构建新块，同时剥夺你作为商家对那笔钱的所有权。

当我们把相似的场景放到分片上，全节点和轻节点的定义一般可以对应到每个分片上：每个分片的验证节点下载该分片的每个区块并验证其中的每笔交易，但是系统中的其他节点，包括那些快照分片链状态到信标链的节点，都只下载区块头。因此，分片验证节点对该分片来说，实际上就是全节点，而系统的其他参与者，包括信标链，就像一个轻节点那样运作。

为了让我们前面讨论的渔夫方案发挥作用，诚实验证节点需要能下载交叉连接到信标链的区块。然而，如果恶意验证节点交叉连接一个无效区块的头部（或使用它发起跨分片交易），但从不分发该区块，那么诚实验证节点就无法发起质疑。我们将介绍应对该问题的三种互补的解决方案。

2.5.1 托管证明

亟待解决的最直接问题是，区块一旦被发布是否就是可用的。一种想法是，使用被称为公证人（Notary）的角色，让其在分片中以比验证节点更快的频率轮转。他们唯一的工作是下载一个区块并证明他们有能力下载它。他们之所以能更频繁的轮转，是因为无需下载分片的整个状态，不像验证节点，后者每次轮转都要下载分片的状态，因此不能频繁轮转，如图13所示。

图 13：验证节点需要下载状态而不能频繁轮转

该想法不足之处在于，后面无法验证某个公证人是否真能下载那个区块。因此，一个公证人可以选择总是声称他们能下载那个区块，甚至不用尝试获取这个区块。一个解决方案是让公证人提供某种证据证明其下载了区块或质押一定数量的通证作为担保费。这里讨论了该类方案的其中一种：

https://ethresear.ch/t/1-bit-aggregation-friendly-custody-bonds/2236.

2.5.2 纠删码

当一个特定的轻节点收到一个区块哈希值时，为了提升节点对区块可用性的信心，它可以尝试下载该区块的一些随机碎片。这还不是一个完整的方案，因为除非轻节点联合下载完整区块，恶意出块人可以选择扣押区块中未被任何轻节点下载的那部分内容，因此仍可以使区块不可用。

一个解决方案是使用一种称为“纠删码”的措施，即使在只有区块的部分内容可用的情况下，也能恢复整个区块，如图14所示。

图 14：建在纠删码数据上的默克尔树

波卡和以太坊宁静都采用了基于这种思想的设计，为轻节点提供了一种方式,使其能确信区块是可用的。以太坊宁静的实现在参考文献2中有详细介绍[2]。

2.5.3 波卡对数据可用性的实现

和大部分分片方案一样，波卡每个分片（叫做平行链）快照它的区块到信标链（叫做中继链）。假设中继链有2f+1个验证节点。平行链的出块人叫做整理人.平行链区块一产出，整理人便计算该区块的一个纠删码版本，其中包含2f+1个部分，因此任意f个部分都能重建整个区块。

然后他们给每个中继链的验证节点分发一个部分。一个特定的中继链验证节点，只有在中继链验证节点拥有每个被快照至该中继链区块的每个平行链区块的专属部分，该验证节点才对该中继链区块签名。因此，如果一个中继链区块包含来自2f+1个验证节点的签名，且只要其中不超过f个验证节点违反了协议，那每个平行链区块都还是能从那些遵循了协议的验证节点手中重建出来。见图15。

图 15：波卡的数据有效性

2.5.4 长期数据可用性

值得注意的是，上述方案都只能证明一件事：已经发布一个区块且当前可用。一段时间后，由于以下各种原因，区块可能变为不可用：节点下线，节点故意删除了历史数据等。

对于该问题，Polyshard [3]的白皮书值得一提：使用纠删码确保区块在分片之间是可用的，即使一些分片完全丢失了他们的数据也无妨。不幸的是，他们的特定实现需要任一分片都下载其他所有分片的区块，成本过于高昂。

还好长期可用性问题并不太急迫，因为系统并不指望其参与者能验证所有分片上的所有链。所以，分片协议的安全性设计需要能够做到：即使一些分片的旧区块变得完全不可用，整个系统依然是安全的。

夜影分片协议

3.1 从分片链到分片段

这种多个分片链加一个信标链的分片模型非常强大，但也相当复杂。特别的，分叉选择规则需要在每个链上独立执行，而且分片链和信标链的分叉选择规则一定要有区别的构建和独立的测试。

在夜影中，我们把系统建模成一个单一的区块链，其中每个块逻辑上包含所有分片的全部交易，以及改变所有分片的整个状态。然而，从物理的角度看，任何参与者都不会下载完整的状态或完整的逻辑区块。网络的每个参与者其实只是维护他们为之验证交易的分片上对应的状态。区块中的所有交易的列表都被分割成物理上的段，每个分片对应一个段。

在理想的条件下，每个（逻辑）块里，每个分片都正好有一个分段对应。这基本上对应到分片链模型中，分片链和信标链以相同的速度出块。然而，由于网络延迟，一些分段可能错过（出块），所以在实践中，每个（逻辑）块的每个分片对应着0个或1个分段。对如何出块的详细介绍参见3.3节。

图 16：一个（分片比较）模型，左边是分片链，右边是一个链将其区块分段

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⌋，就不会让一个超过半数出块人（在线）的链含有无效的分片段。。

图 17：每个块包含每个分片的0到1个段，每个段都经过纠删编码处理

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 中所有段对应的全部单颗粒消息，也就拥有了所有传入的收据，这些收据以参与者维护状态的分片为目的地。当执行一个特定分片的状态转换时，参与者既执行单颗粒消息中与该分片有关的收据交易，也执行该段自身包含的所有交易。

图 18：收据交易的生命周期

3.6.2 应对过量的收据

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

图 19：如果收据指向同一个分片，该分片可能无力处理它们

要解决这个问题，我们使用一个类似QuarkChain (2) 中使用的技术。特别的，对每个分片，最后的区块B中最后一条被执行的收据所在的分片s被记录下来。当新的段创建时，会首先从块B中遗留还未处理的收据开始执行，接着才是块B之后的区块，直到新的段被塞满为止。

在正常情况下，随着负载均衡，这个过程的结果是所有收据都被执行（因此每个段中记录的都是最后一个块的最后一个分片）。然而，当负载不均衡时，如果一个特定的分片收到了过多的收据，该技术也能允许这些收据在段中交易条数有限制的前提下被处理。

需要注意的是，如果这种负载不均衡持续了很长时间，则收据从创建到执行之间的延迟可能持续地无限增长。一种解决方式是，当收据指向的是处理延迟超过了某个常数（例如，一个周期）的分片时，该收据产生的交易会被丢弃。

考虑图20的情况。直到区块B时，分片4还没有处理完所有收据。它仅处理到来自区块A中分片3所产生的收据，并记录了下来。在区块C时，收据处理跟进到区块B的分片5，最后在区块D时，该分片赶上了进度，处理了区块B里所有遗留的收据和区块C里的全部收据。

图 20：延迟的收据处理

3.7 分片段有效性

一个特定分片的段（或在分片链模型中一个特定分片链的分片块）只能由那些维护其状态的参与者验证。他们可以是出块人、验证节点或仅仅是那些下载状态并对存有他们资产的分片进行验证的外部见证人。

本文中，我们假设大部分验证节点不会存储绝大部分分片的状态。然而值得一提的是，确实有一些分片链，是基于这样的假设设计的：大部分参与者都有能力存储和验证大部分分片的状态，例如QuarkChain。

因为仅有一部分参与者拥有能够验证分片段的状态，这就有可能对那些有状态的参与者进行自适应攻击，执行一个无效的状态转换。

在多个分片设计方案中，每隔几天就对验证节点采样。一天内，分片链中的任何块，只要获得了超过2/3的验证节点对该分片的签名，就立刻视为确定的块。通过这种方法，一个采用自适应攻击的对手只需贿赂一个分片链中 2n/3 + 1的验证节点，就能执行一个无效的状态转换。尽管这种攻击很难实现，但对于一条公链来说，这种等级的安全性还不够。

正如2.3节所讨论的，常见的方案是在出块后留出一个时间窗口，让任何持有状态的参与者（无论是出块人、验证节点还是外部观察者）质疑其有效性。这类参与者被称为渔夫。为了让渔夫能够质疑一个无效区块，必须确保区块对渔夫来说是可用的。夜影中数据可用性的讨论在3.4节。

夜影中，一个块产生后，（其中的）分片段除了实际的出段人，没人可以验证。特别是，发布区块的出块人自然不持有大部分分片的状态，并且无法验证分片段。当下一个区块创建时，会包含多个出块人和验证节点的证词（参见3.2节），但既然大部分出块人和验证节点都不持有大部分分片的状态，所以仅包含一个无效分片段的区块也能收集到超过半数的证词，并继续存在于最重的链上。

为了解决该问题，我们允许任何维持分片状态的参与者，对该分片产生的任何一个无效分片段，提交一个链上质疑。

3.7.1 状态有效性质疑

一旦参与者检测到一个特定的分片段是无效的，他们需要提供一个证实该段无效的证明。因为大部分网络参与者并不维护无效段所在分片的状态，证明中需要包含足够的信息证明无需持有状态即可确认该块无效。

我们设了一个门限Ls，代表单一交易所能累积读取或写入的状态数量上限（以字节为单位）。任何访问超过Ls 个状态量的交易都被视为无效。3.5节中说过，特定区块B 中的段只包括将被执行的交易，不包括新的状态根。区块 B 中该段包括的状态根是执行这些交易之前的状态根，是执行了区块B之前区块中同一个分片的最后一个段中交易的结果。一个作恶人想要执行一个无效状态转换，就要把一个错误的状态根放到区块B 中，这个状态根与执行前段中交易的结果状态并不对应。

我们把出段人放在分片段中的信息扩展一下。不再放置执行所有交易之后的状态，而是将交易分割成相邻集合，每个集合都总计读写了 Ls字节的状态。然后逐个集合的执行这些交易，存储这些连续交易集合的状态跟。有了这些信息，渔夫就可以创建一个错误状态转换的质疑挑战，找到第一个无效的状态根，在上一个带有默克尔证明的状态根（有效的）和当前带有默克尔证明的状态根之间发生的交易所影响到的Ls 字节状态放入。这样，任何参与者都可以验证这批交易，确认该分片段是无效的。

类似的，如果出段人试图把一个读写超过 Ls 字节状态的交易包含进来，对质疑来说，只要包括带有默克尔证明的、该交易访问的前Ls个字节即可。这已足够执行交易并证明在某个时刻，有过尝试读写超过 Ls 字节内容的情况发生。

3.7.2 渔夫和快速跨分片交易

正如2.3节中讨论的，一旦我们假设分片的段（在分片链模型中的分片区块）可能无效，并引入了质疑时间，就会对确定性以及跨分片通信有负面影响。尤其是在质疑结束前，任何跨分片交易的目的分片无法确认源分片的段或块是否确定（参见图21）。

图 21：在执行收据之前等待质疑时间

解决办法是，用某种方式让跨分片交易立即完成：对目的地分片，不等原分片交易发布后挑战结束，立即执行收据交易。如果后面发现源段或块无效，就目的分片和源分片一起回滚（参见图22）。对于夜影的设计来说，应用该方案很自然。因为分片链不是独立的，而是由分片的段一起，发布在同一个主链区块中。如果发现任何段是无效的，包含这个段的整个块、以及构建在其上的块都被视为无效。参见图23。

图 22：立即执行收据和当源链有无效区块时目的链的回滚

图 23：夜影中的渔夫挑战

假设整个质疑过程足够长，上面的方案就都具有原子性。我们采用后一种方案，因为在普通情况下提供快速的跨分片交易，相比目的分片回滚带来的不便，前者更重要。这种因某个源分片上无效的状态转换所导致的目的分片回滚，是极度罕见的事件。

3.7.3 潜伏的验证节点

质疑机制的存在已经显著降低了自适应攻击的可能性。因为确定一个含有无效状态转换的段并通过挑战时间，采用自适应攻击的对手需要贿赂所有维护该分片状态的参与者，包括所有（该分片的）验证节点。

预测发生这种事情的可能性是极端复杂的，因为当今活动的分片链都没有经历足够长的时间，让人尝试这种攻击。我们认为这种风险，尽管可能性很低，但对于一个预期要执行数百万笔交易和执行世界级金融操作的系统来说，还是足够高了。

这个判断来自两个主要原因：大部分POS链的验证节点和POW链的矿工主要受经济方面的激励。如果一个自适应攻击的对手提供的金钱超过诚实操作的预期回报时，可以预计许多验证节点会接受贿赂。许多做POS链验证的都是专业的实体，预计任何链上大部分权益抵押来自这种实体。这种实体的个数对一个自适应攻击的对手来说足够小，对手可以了解大多数实体，了解他们被贿赂的意向。

通过隐藏验证节点分配到分片的信息，我们进一步减少了自适应攻击的可能性。这个思想与Algorand[5] 隐藏验证节点的方法有些类似。

有一点需要重要指出的是，即使是Algorand或下文描述的方法，把验证节点隐藏了，自适应攻击还是存在理论上的可能性。尽管自适应攻击的对手不知道参与者会创建或验证一个区块或分片段，参与者自己却是知道他们将要做的任务，并有一个相关的密码学证明。

因此，作恶者可以广播他们贿赂的意图，并支付给愿意提供那个密码学证明的参与者。但是，我们注意到，因为作恶者不知道他们将要贿赂的分片上的验证节点，除了在整个社区里广播他们贿赂特定分片的意图外，别无他法。这是让任何诚实参与者都可以开启全节点去验证那个分片来获得经济利益的时机。因为在那个分片上出现无效区块的几率变大了，这就是创建质疑、获得相关奖励的机会。

为了不暴露特定分片的验证节点，做如下处理（参见图24）：

使用VRF进行分派。每个周期开始时，每个验证节点使用VRF得到指定分片的掩码。每个验证节点的掩码都将含有sw个比特位（参见3.3节对sw的定义）。接下来，验证节点获取相关分片的状态，并在整个周期内，对收到的每个块验证其中指派给自己的分片所对应的分片段。

对区块块签名而不是分片段。既然分片指派是隐藏的，验证节点就不能在段上签名，而是通常对整个块签名，这样就不会暴露他验证哪些分片。特别的，当一个验证节点收到一个区块并验证了所有的分片段后，他要么创建一条消息，证明他负责的所有分片（没有以任何方式表明是哪些分片）中所有的段都是有效的；要么在任意一个段无效时，创建一条消息，包含一个无效状态转换的证明。对如何聚合这些消息的详细介绍，参见3.8节。对如何防止验证节点照抄其他验证节点消息的详细介绍，参见3.7.4节。以及3.7.5节，详细介绍了当一个成功的无效状态转换质疑发生时，如何奖惩验证节点。

图 24：夜影中的验证节点隐藏

3.7.4 承诺生成(commit)-展示(reveal)

验证节点的一个常见问题是，他可以跳过状态的下载和对分片段和区块的实际验证，而是观察网络，看其他验证节点提交的内容并重复他们的消息。采用这种策略的验证节点并不能给网络带来任何安全的提升，只是获得奖励。

一个解决该问题的常见方案是，要求每个验证节点提供一个证明，证实他们确实验证了区块。例如，提供一个执行状态转换的独有痕迹，但是这种证明大大增加了验证的开销。

图 25：承诺生成-展示

与其我们让验证节点先承诺(commit)一个验证结果（要么是一条证明段有效的消息，要么是一个无效状态转换的证明），等待一段时间，之后才能展示(reveal)实际的验证结果，如图25所示。承诺阶段和展示阶段不会重叠，因此一个懒惰的验证节点无法抄袭诚实验证节点。此外，如果不诚实的验证节点承诺了一条证实所负责的分片段都有效的消息，而最终有一个段无效。只要这个段的无效性被公开，该验证节点就无法逃避惩罚。就如我们将在3.7.5节所展示的，那种情况下，唯一不被惩罚的方式就是（在展示阶段）呈现一条包含无效状态转换证明的消息，并与自己的（在承诺阶段的）的申明匹配。。

3.7.5 处理质疑

如上所述，一旦验证节点收到一个含有无效分片段的区块，他们先准备一个无效状态转换的证明（参见3.7.1节），然后提交这样一个证明（参见3.7.4节），再在一段时间后展示这个质疑。一旦块里包含一个被展示的质疑，接下来会：

从包含无效段的块开始，直到包含质疑展示的块为止，期间发生的所有状态转换都失效。包含质疑展示的块之前的状态回到包含无效段的块之前的状态。

在一段时间内，每个验证节点必须展示自己负责验证的区块的掩码。因为掩码通过VRF创建，如果他们被指派到发生了无效状态转换的分片，就无法绕过这个展示。任何没有成功展示掩码的验证节点都被认为是被指派到这个（含有无效状态转换的）分片的。

经过掩码展示阶段后，任何一个被指派到该分片的验证节点，如果当时提交的不是该区块包含无效的段，或者没有展示匹配他们提交的无效状态转换的证明，就被惩罚。每个验证节点重新指派分片，在一段足够验证节点下载对应状态的时间后，新的周期开启，参见图26。

图 26：处理质疑

要注意的是，因为验证节点的分片分派情况已公开，从验证节点公开他们所分派的分片开始，直到新周期开启，这段时间系统的安全性降低了。网络的参与者在该期间使用网络时，需要牢记这一点。

3.8 签名聚合

为了让一个拥有上千分片的系统安全运行，我们需要有上万级或更多的验证节点。如3.7节所述，我们想要每个验证节点在每个块都承诺某条消息并签名。即使承诺的消息是一样的，聚合出一个BLS签名并对其进行验证都是极度昂贵的。更不用说承诺和展示的消息在验证节点之间通常是不同的，所以我们需要某种别的方法来聚合这些消息和签名，以支持后面对它的快速验证。

我们使用的方法如下：验证节点关联出块人。因为周期开始前要留出下载状态的时间，所以在周期开始前的某个时刻，出块人就确定了。而且与验证节点不同，出块人不是隐藏的。每个出块人有v个验证节点槽位。验证节点提交链下请求给出块人，让自己成为其v个（关联）验证节点之一。如果出块人愿意关联该验证节点，就提交一笔交易，包括最初来自验证节点的链下请求和出块人同意其加入的签名。要注意，被指派给出块人的验证节点所验证的分片无需和其关联的出块人负责出段的分片一致。如果一个验证节点申请加入多个出块人，只有来自第一个出块人的交易会成功。

出块人收集提交信息。出块人始终收集来自验证节点提交和展示的消息。只要积累了一定数量的这些消息，出块人就计算这些消息的默克尔树，给每个验证节点发送默克尔根和各自的默克尔路径。验证节点验证路径并在默克尔根上签名。接着，出块人就在验证节点给的默克尔根（译者注：含有验证节点签名）上累积一个BLS签名，然后仅仅发布默克尔根和累积签名。

出块人也使用廉价ECDSA签名方式，签名保证前面那个多签的有效性。如果多签与提交的默克尔根不匹配，或者与验证节点的掩码不匹配，就是需要惩罚的行为。同步链时，参与者可以选择验证来自于验证节点的所有BLS签名（这个开销将极度昂贵，因为牵涉到聚合验证节点的公钥），或仅验证出块人的ECDMA签名，并且该出块人没有被质疑和惩罚。

使用链上交易和默克尔证明进行质疑。你会注意到，没有检测到无效状态转换时，展示验证节点的消息是没有价值的。只有那些包含无效状态转换实际证明的消息需要展示，也仅仅只有这些消息需要表现出自己与之前的承诺相匹配。展示消息有两个目的：

• 为了实际开启往无效状态转换之前时刻的链上回滚（参见3.7.5节）。
• 为了证明验证节点没有试图证明一个无效段是有效的。

对这两条，我们需要解决两个问题：链上并不包括承诺本身，有的只是它与其它消息聚合出的默克尔树根。验证节点需要使用出块人提供的默克尔路径和原始承诺来证明他确实进行了质疑。

有可能出现无效状态转换的分片的所有验证节点都正好被指派给审查他们的受贿的出块人。为了解决这个问题，我们允许验证节点提交自己的展示信息作为链上常规交易，并绕过聚合。

后一种机制仅允许用来证明无效状态转换。这种情况极其罕见，因此不会导致区块中的垃圾交易问题。最后一个要解决的问题是，出块人可以选择不参与消息聚合，或故意审查特定的验证节点。我们通过将出块人的奖励与关联的验证节点数量挂钩，使那种行为在经济上不可取。我们也注意到，因为周期之间的出块人有很大的交集（因为总是权益抵押最多的前w个参与者入选），验证节点可以很大程度上坚持与相同的出块人合作，也就降低了将其指派给曾对其进行审查的出块人的风险。

3.9 快照链

因为主链上出块非常频繁，下载全历史可能很快就变得昂贵。而且，因为每个块包含一个大批参与者的BLS签名，仅仅是聚合公钥来检查签名的开销就会变得过高。

最后，因为在可以预见的未来，以太坊1.0很可能依旧是最常用的区块链之一，需要一条重要的渠道能从NEAR往以太坊转移资产。而目前，通过验证BLS签名来确保NEAR区块在以太坊那一侧的有效性是暂时行不通的。

夜影主链上的每个块可选择是否在上一个包含Schnorr多签的区块的头部上包含一个Schnorr多签。我们称这样的块为快照块（snapshot block）。每个周期的头一个块必定是快照块。当处理这样一个多签时，出块人也必须积累上一个快照块上验证节点的BLS签名，并以3.8节描述的方法聚合他们。

既然整个周期中，出块人集合都是不变的，仅验证每个周期的第一个快照块就足够了。前提是没有发生大比例的出块人和验证节点相互勾结和出现一个分叉的情况。

周期的第一个块必须带有足以计算本周期出块人和验证节点的信息。我们把仅包含快照块的主链的子链，称为一条快照链。

创建Schnorr多签是个互动的过程， 但既然我们仅需要低频的执行它，那么不管多低效，任何过程都可以满足。Schnorr多签可以在以太坊上方面得到轻松验证，为安全的跨链通信提供了重要的基础。

为了同步NEARr链，只需要下载所有的快照块，并确认Schnorr 多签是正确的（也可以选择验证个别验证节点BLS签名），然后仅仅从最后一个快照块开始同步主链上的块。

结语

这篇文章中，我们讨论了构建分片区块链的方式，以及两个主要挑战和现存的应对方案，分别是状态有效性和数据可用性。然后我们提出了夜影，一个助力NEAR协议的分片设计。

设计工作还在推进中，如果有相关意见、问题或反馈，请前往 https://near.chat 。

参考文献

[1] Monica Quaintance Will Martino andStuart Popejoy. Chainweb: A proofof-work parallel-chain architecture formassive throughput. 2018.[2] Mustafa Al-Bassam, Alberto Sonnino, andVitalik Buterin. Fraud proofs: Maximising light client security and scalingblockchains with dishonest majorities. CoRR, abs/1809.09044, 2018.[3] Songze Li, Mingchao Yu, SalmanAvestimehr, Sreeram Kannan, and Pramod Viswanath. Polyshard: Coded shardingachieves linearly scaling efficiency and security simultaneously. CoRR,abs/1809.10361, 2018.[4] Ittai Abraham, Guy Gueta, and DahliaMalkhi. Hot-stuff the linear, optimalresilience, one-message BFT devil. CoRR,abs/1803.05069, 2018.[5] Yossi Gilad, Rotem Hemo, Silvio Micali,Georgios Vlachos, and Nickolai Zeldovich. Algorand: Scaling byzantineagreements for cryptocurrencies. In Proceedings of the 26th Symposium onOperating Systems Principles, SOSP ’17, pages 51–68, New York, NY, USA, 2017. ACM.[6] Vitalik Buterin and Virgil Griffith.Casper the friendly finality gadget. CoRR, abs/1710.09437, 2017.

翻译：Marco@Buildlinks审校：Homer，Steve Huang，Crypto Rose，Amos编辑：Homer