原文标题：《夜影：NEAR 协议中的分片设计》
撰文： Alexander Skidanov、Illia Polosukhin，均为 NEAR 联合创始人
翻译：Marco@Buildlinks

众所周知，以太坊作为迄今为止最广为使用的通用区块链，主网每秒只能处理不到 20 笔交易。在以太坊网络流行后，由于这个局限，导致了高昂的以太坊 gas 价格（gas 是以太坊网络上执行交易的费用）和过长的确认时间。尽管在撰写该文的时候，以太坊平均每 10 到 20 秒可以产出一个新块，然而根据 ETHGas 监测站的数据，一笔交易实际上要花 1.2 分钟才能加到链上。低产能，高费用和长延迟，都导致了以太坊不适合运行大规模使用的链上服务。

以太坊低产能的主要原因是，每个节点都要处理全网的每一笔交易。开发者们提出了许多解决方案，试图在协议层面解决这个问题。这些方案主要分为两类：一类是把所有的计算工作交给数量有限的强力节点；另一类是让网络中的每个节点只做所有计算工作的一部分。前一种方案的例子是 Solana，系统中的每个节点通过细致的低层优化和 GPU 的使用，来支撑每秒几十万笔简单的支付交易。Algorand，SpaceMesh，Thunder 都可归入这一类；他们通过改进共识以及区块结构本身来超过以太坊的 TPS，虽然有一定的效果，但仍然受制于单台机器的处理能力。

后一种方案，即把工作分给所有的参与节点。这种方法叫做分片。这也是当前以太坊基金会打算的扩展方案。撰写本文时，以太坊的分片规范还未定稿，最新的规范可以 点击查看。

NEAR 协议基于分片搭建。NEAR 团队的成员包括：多位世界级电脑竞赛获奖者；若干前 MemSQL 工程师，负责构建分片、跨分片交易以及分布式的 JOIN；9 位前谷歌、脸书员工，他们在构建分布式系统方面等有着丰富的行业经验。

本文重点阐述了区块链分片的通用方法，以及需要解决的主要问题，包括状态有效性和数据可用性问题。本文还提出了 NEAR 协议创新的夜影方案。

关于分片的基础知识

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

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

验证节点分区和信标链

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

这就带来第二个问题：谁负责为每个分片选择验证节点？如果 5.1% 的验证节点被攻破，但也只有在这些验证节点正好处于同一个分片时才有威胁。如果验证节点不能自主选择去验证哪个分片，那么一个控制了 5.1% 验证节点的参与者是很难让他控制的所有验证节点都在同一个分片的。这也就就大大降低了他破坏系统的能力。

当今几乎所有的分片系统都依赖给分片随机分配验证节点。区块链上的随机性本身就是一个极富挑战的话题，它超出了本文讨论的范畴。现在，让我们假设有这样一个可用的随机性。我们会在 2.1 节介绍验证节点分配的更多细节。

随机性和验证节点分配都要求计算工作与任意分片之间不存在对应关系。目前对于分片计算而言，几乎所有设计都使用一个额外的独立区块链，来执行维护整个网络所需要的操作。除了随机数生成和给分片分配验证节点外，这些操作通常还包括了接收分片更新以及执行分片快照，处理 POS 中的质押和取消验证节点资格，以及在支持再平衡功能的分片系统上进行分片的再平衡。这种独立链的名称，以太坊上叫信标链，波卡上叫中继链，Cosmos 上叫 Cosmos Hub。

本文统一将其称为信标链。信标链的存在引出了下面一个有趣的主题，即二次方分片。

二次方分片

分片经常被视为一种可以随着网络中节点数的增加而无限扩展的方案。虽然从理论上看，人们是有可能设计出这种方案的，但任何使用信标链概念的方案都不可能无限扩展。为了理解其原因，我们要意识到，信标链要做一些记账的计算工作，例如给分片分配验证节点，或快照分片链区块，而这些都与系统中的分片数量成比例关系。因为信标链本身只是一条单独的链，计算量受限于运行节点的算力，因此分片数量自然就受到了限制。

然而，分片网络的结构确实对节点的改进产生了倍增的效果。想象一下这样一个场景，对网络中节点效率作出一定量的改进，从而使得节点处理交易的时间缩短。

如果节点（包括信标链中的节点）运行网络的速度提高了四倍，那么，每个分片都可以处理原先交易量的四倍多，而信标链也可以维持原先分片数量的四倍多。整个系统吞吐量的将提升：4 × 4 = 16 倍，这就是二次方分片名称的由来。

当前，对于究竟能支持多少分片，很难提供精确的度量。但是，在可以预见的未来，区块链用户的吞吐量需求不太可能超过二次方分片的能力。运行如此众多的分片所需要的节点数，可能比当今所有区块链节点数的总和还要高出几个数量级。

状态分片

目前为止，我们还未准确定义当网络切割成分片后，究竟什么被分割开，什么没有被分割出去。尤其要注意，区块链中的节点需执行三个重要任务：1）执行交易，2）把经过验证的交易和构建完成的区块中继给其他节点，3）存储整个网络账本的状态和历史。三个任务中的每一个都对运行网络的节点提出了不断增加的需求：

• 随着需要处理的交易量的增加，执行交易的必要性导致更高的算力需求；
• 随着需要中继的交易量的增加，中继交易和区块的必要性导致更高的网络带宽需求；
• 随着状态数据的增长，存储数据的必要性导致更大的存储需求。重要的是，不像算力和网络需求，存储要求是持续增长的，即使交易速率（TPS）保持恒定。

上面的列表可能让人觉得，存储需求是最急迫的，因为它是唯一一个随着时间持续增长的因素（即使每秒交易量不变）。但实际上，当前最急迫的需求是算力。撰写本文时，以太坊的全网状态大小是 100GB，大部分的节点都可以轻松应对。而以太坊的每秒可处理交易量在 20 笔左右，比许多实际应用场景的需求低了好几个数量级。

Zilliqa 是最广为人知的对交易处理而不是存储进行分片的项目。对处理分片相对容易：因为每个节点都有完整的状态，意味着一个合约可以自由调用其他合约，从链上读取任何数据。为了确保对状态同一部分进行更新的多个分片不会产生冲突，还需要一些细致的技术工作。从这方面来说，Zilliqa 的方法有些简单 (2)。

尽管之前有提出过对存储分片但不对处理分片的方案，但这是极不寻常的情况。在实践中，对存储分片，也就是状态分片，几乎总是隐含了对处理分片和网络分片。

实际上，状态分片中，每个分片中的节点都在构建他们自己分片的区块链，这条链仅包含那些对被分配给该分片的全局状态的本地部分产生影响的交易。因此，分片的验证节点只需要存储全局状态的本地（分片）部分，也仅仅执行和中继那些影响到这些本地状态的交易。这种分区线性地减少了所有包括算力、存储、带宽的需求。但是这也带来了新的问题，例如数据可用性和跨分片交易的问题。这两个问题我们会在下文阐述。

跨分片交易

迄今为止，我们描述的分片模型还不是很有用。如果单个分片不能跟其他分片互相通信，整个系统不过就是多个独立的区块链而已。甚至在分片技术还不可用的今天，不同区块链之间的互操作性依然是一个巨大的需求。

现在，让我们只考虑简单支付交易，每个参与者仅在一个分片上拥有账户。如果有用户希望在同一分片内从一个账户转账到另一账户，这笔交易可以由本分片的验证节点全权处理。然而，如果分片 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 和波卡实际上都属于这种系统。

恶意行为

这一节，我们将回顾，如果恶意验证节点想破坏一个分片，会采用什么样的行为。我们将在 2.1 节回顾那些防止分片破坏的经典实现方法。

恶意分叉

一部分恶意验证节点也许试图创建一个分叉。需要注意的是，无论底层共识是否是 BFT，买通足够数量的验证节点就都可能创建一个分叉。

相对来说，最可能发生的是买通一个分片中的 50% 以上（的验证节点），而不是买通整个链的 50% 以上（的验证节点）（我们将在 2.1 节详细阐述这些可能性）。正如 1.4 节中所讨论的，跨分片交易牵涉到多个分片中的某些状态改变，这类分片中应用这些状态变化的相应区块要么全部确定（即出现在对应分片被选中的分支上），要么全部成为孤块（即不出现在对应分片被选中的分支上）。一般意义上看，分片被破坏的可能性是不可忽视的，即使分片验证节点之间已经达成了某种拜占庭共识或是包含状态变化的块之上已经产出许多区块，我们也不能假设不会发生分叉。

这个问题有多种解决方案，最常用的一种是将分片链上最新的区块偶尔交叉连接到信标链上。分片链上的分叉选择规则相应变化为总会优选那些交叉连接的链，并且只对最后一个交叉连接之后产生的区块使用分片特定的分叉选择规则。

审批无效块

一些验证节点也许会尝试创建一个包含了不正确状态转换函数的区块。例如，从 Alice 有 10 枚通证、Bob 有 0 枚通证的状态开始，区块可能包含包含一笔 Alice 转给 Bob10 枚通证的交易，但是最终状态如图 3 所示，Alice 有 0 枚通证，Bob 却获得了 1000 枚。

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

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

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

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

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

状态有效性和数据可用性

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

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

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

验证节点轮替

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

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

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

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

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

状态有效性

看一下图 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 的区块，因此无法检测到那个恶意区块。正确解决状态有效性问题有两个主要方向：渔夫与密码学计算证明。

渔夫

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

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

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

简洁的非交互知识论证

第二种应对多分片贿赂的方案是使用某种密码学的措施，允许一个人证明某个计算（比如从一系列交易中算出区块）被正确执行了。这种措施确实存在，比如 zk-SNARKs、zk-STARKs 等技术，经常用在当今隐私支付领域的区块链协议中，其中最知名的是 ZCash。那些方案的主要问题是计算起来非常慢。例如，Coda 协议，专门使用 zk-SNARKs 证明链上的所有区块都是有效的，在一次访谈中表示，为了创建一个证明，每笔交易要花费 30 秒时间（目前这个数字可能要小些）。

有趣的是，证明未必需要一个可信实体进行计算。因为证明不仅能证实它的目标计算的有效性，还能证实其自身的有效性。因此，这种证明的计算工作可以分配给一系列参与者，与必须执行某些无需信任的计算相比，显著降低了冗余。它也允许计算 zk-SNARKs 的参与者运行在特殊的硬件上，同时不会减低系统的去中心化程度。

除了性能外，zk-SNARKs 面临的挑战还有：

• 依赖于鲜有研究和缺少时间验证的密码学基元 （primitives）；
• 「有害废弃物」-- zk-SNARKs 依赖于一个可信的设置过程，其中一组人执行某种计算，并丢弃该计算的中间值。如果该过程的所有参与者互相勾结，保留了中间值，则就能创建虚假证明；
• 系统设计引入额外的复杂性；
• zk-SNARKs 只适用于所有可能计算的一个子集。所以，支持图灵完备的智能合约语言的协议将不能使用 SNARKs 证明链的有效性。

数据可用性

我们遇到的第二个问题是数据可用性。一般来说，运行特定区块链的节点分为两种：全节点，指那些下载每一个完整区块并验证每一笔交易的节点；和轻节点，指那些仅下载区块头、并对其关注的部分状态和交易应用默克尔证明的节点。参见图 11。

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

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

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

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

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

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

托管证明

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

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

纠删码

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

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

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

波卡对数据可用性的实现

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

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

长期数据可用性

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

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

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

夜影分片协议

从分片链到分片段

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

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

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

共识

当今区块链共识的两个主流方法是：最长（或最重）链共识，指由最多工作量或权益打造的链被认为是正统链；以及 BFT 共识，指对于每个块，都由一批验证节点在其中达成一个 BFT 共识。

在最近提出的协议中，后一种共识的实现更加流行一些。因为它提供了即时的确定性，而在最长链规则中，需要更多的区块创建在目标区块之后，才能确保确定性。通常，为了达到一个严谨的安全等级，需要小时级别的时间才能有足够数量的区块（在目标区块之后）创建出来。

对每个块使用 BFT 共识，也有些缺点，例如：BFT 共识涉及相当多的通信量。尽管最新进展允许以参与者达成共识的时间与网络参与者的数量形成线性关系（见 [4]），但这个工作量对每个块来说仍然是不可忽视的；

所有网络参与者都参与每个块的 BFT 共识是不现实的，因此通常仅有一个参与者的随机样本子集参与达成共识。一个随机的样本集合，原则上是可能受到自适应攻击的，因此理论上分叉是会出现的。系统在设计上要么需要为这种情况做好准备（因此，除了 BFT 共识，依然还要有分叉选择规则），要么就要在这种情况下关闭。值得一提的是，某些设计，例如 Algorand [5]，已大大降低了自适应攻击的可能性。

最重要的是，如果 1/3 或更多的参与者掉线，系统将中止。因此，任何临时的网络小故障或一个网络分裂就会使系统完全瘫痪。理想情况是，系统必须能够继续运行，只要至少一半的参与者在线（基于最重链的协议，甚至能在少于一半参与者在线的情况下继续运行，但是这个特点是否必要在社区内还有不少争论）。

在一个混合模型中，共识使用的是某种最重链规则，但是周期性的对一些块使用 BFT 确定性工具来实现其确定性。这样就同时保有了两种共识模型的优点。这种 BFT 确定性工具有用于以太坊 2.0 (1) 的 Casper FFG [6]、Casper CBC 和用于波卡的 GRANDPA 。

夜影使用最重链共识。尤其当一个出块人产生一个区块时（参见 3.3 节），他们可以从其他出块人和验证节点中收集签名，作为对前一个区块的证明。参见 3.8 节对于如何积累如此大量签名的详细介绍。一个区块的权重就是所有那些在区块中签了名的签名者积累的抵押权益。而一个链的权重就是区块权重的和。

在最重链共识之上，我们使用一个确定性工具，利用证明确定区块。为了减低系统复杂度，我们使用的确定性工具在任何情况下都不影响分叉选择规则，而只是引入额外的罚没质押通证条件。这样一来，一旦一个区块被确定性工具确定下来，就不可能出现分叉，除非占总权益极大百分比的权益都被罚没了。

Casper CBC 就是这样一种确定性工具，我们在设计时有参考 Casper CBC。

我们也在研究一个独立的 BFT 协议，叫做 TxFlow。撰写本文时，尚不清楚 TxFlow 是否会用来取代 Casper CBC。然而，我们注意到，确定性工具的选择在很大程度上与设计的其余部分无关。

出块

夜影中有两种角色：出块人和验证节点。设系统有 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 个分片，（设 s w=40，则每分片有 s w W/n= 4 个出块人）。 在周期开始前，出块人下载所指派分片的状态，然后在整个周期中收集影响该分片的交易，并把它们应用到状态上。

对于主链上的每个块 b，和每个分片 s，都有一个指定给 s 的出块人负责生产 b 上有关该分片的区块部分。这个部分被称为分片段，包含了 b 中有关该分片的交易列表，以及结果状态的默克尔树根。b 最终只包含该分片段的一个很小的段头，也就是所有应用交易的默克尔树根（具体信息参见 3.7.1 节），和最终状态的默克尔树根。

本文剩余部分，我们通常把在特定时间为特定分片创建分片段的出块人称为出段人，出段人一定是出块人之一。

出块人和出段人根据一个固定的安排轮换每个块。出块人有个顺序并依序重复出块。例如，如果有 100 个出块人，第一位出块人负责创建块 1、101、201 等，第二位出块人负责 2、102、202 等。

创建分片段与创建区块不同，需要维护状态。而且对每个分片来说，仅仅 s w W/n 位出块人维护着每个分片的状态，相应的也就只有这 s wW/n 位出块人轮换创建分片段。例如，按照上面的常量设定，一个分片指定了 4 个出块人，每个出块人每四个块创建一次分片段。

确保数据可用性

为了确保数据可用性，我们使用了跟 2.5.3 节描述的波卡类似的方式。一旦一个出块人创建了一个分片段，就创建该分片段的一个纠删码版本，纠删码参数为 (w, ⌊w/6 + 1⌋)，然后发送该段纠删码的每一片（我们称这样的码片为段颗粒 chunk parts，或者就叫颗粒 parts）给每个出块人。

我们计算出一棵默克尔树，其中每个颗粒都是叶子，并在每个段的头部都包含该默克尔树的根。这些颗粒通过单颗粒消息（onepart message）发给验证节点。每条这种消息包含该段的段头、颗粒序号以及颗粒内容。消息中还包含创建该段的出块人的签名，以及证明该颗粒对应头部且由正确的出块人创建的默克尔路径。

一旦一个出块人收到一个主链的块，他首先检查自己是否有该块包含的每个段的单颗粒消息。如果没有，该块就不被处理，直到获取到缺失的单颗粒消息。

一旦所有的单颗粒消息收全了，这个出块人从其他出块人那里拿来剩余部分并重建他们为之持有状态的那些段。

出现以下情况时，出块人不会处理主链区块：如果区块中至少有一个分片段的对应单颗粒消息未收到；或如果他负责维护状态的分片中至少有一个分片无法重建出对应的完整段。

若要一个特定的分片段可用，只要有⌊w/6⌋+1 的出块人持有并能提供相关的颗粒即可。因此，只要作恶者的数量不超过⌊w/3⌋，就不会让一个超过半数出块人（在线）的链含有无效的分片段。。

处理懒惰的出块人

如果一个出块人遇到一个缺失了一条单颗粒消息的块，他可能仍然会签名。因为如果这个块最终上链了，就能使该出块人的利益最大化。而且这对出块人没有风险，因为过后无法证明这个出块人没有那条单颗粒消息。

为了解决这个问题，我们让每个出段人在创建段的时候为后面经过编码的段的每个颗粒选择一个颜色（红或蓝），并在编码前将所选颜色的掩码存入段中。每条单颗粒消息都包含该颗粒指定的颜色，这个颜色也用来计算编码颗粒的默克尔根。如果出段人违反协议，将被轻易检测出来。因为，要么默克尔根对不上单颗粒消息，要么匹配了默克尔根的单颗粒消息中的颜色与段的掩码不匹配。

当出块人签名一个区块时，他将收到的该块中所有段的红色颗粒做成掩码放在签名中。发布一个不正确的掩码是一种可罚没质押通证的行为。如果一个出块人没有收到某条单颗粒消息，是无法知道其颜色的，因此尝试盲签区块就有 50% 的可能性会被惩罚。

状态转换的执行

出段人创建段时，只是选择哪些交易要放在段中，而不会执行状态转换。相应的，段头部包含执行该段交易之前的默克尔状态的默克尔根。仅当一个包括该段的完整区块得到处理时，这些交易才会执行。而一个参与者仅在以下条件达成时处理区块：

• 前一个区块已经接收并得到处理；
• 对于不维护状态的那些段，参与者见到了单颗粒消息；
• 对于需要维护状态的那些段，参与者拥有完整的段。

一旦区块得到处理，对于那些需要维护状态的每个分片，参与者执行交易并计算交易执行后的新状态。之后，如果被分配到任何分片，参与者就准备好创建下个区块的对应段，因为他已经有了新默克尔状态的默克尔根。

跨分片交易和收据

如果一笔交易不止影响一个分片，就需要在不同的分片中连续独立执行。完整的交易发给第一个相关的分片。一旦该分片的段中包含了该交易，且在该段被包含进区块之后被执行，就会产生一笔收据（receipt）交易。该收据被路由给下一个需要执行该交易的分片。如果跨分片交易需要更多的步骤，则当执行收据交易的时候，会产生一笔新的收据交易，如此循环。

收据交易生命周期

理想的情况是，收据交易在产生收据的块的下一个块中立刻被执行。只有在维护源分片的出块人接收并执行了前一个块后，收据交易才会生成。并且，需要在目的分片的出块人为下一个区块创建段之前被其知晓。因此，在这两个事件间的一段短时间内，收据必须由源分片通信到达目的分片。

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

应对过量的收据

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

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