了解夜影协议：突破限制的NEAR分片设计

分片是区块链扩容的一个重要方向。

传统的区块链如以太坊每秒仅能处理20个左右的交易。主要原因是以太坊中每个交易都要在每个节点上执行一遍, 单台机器的处理能力限制了以太坊的最大TPS。

分片的思路是把所有节点进行分组， 每个节点不再参与全部交易的验证，而是仅验证一部分的交易， 因此可以突破单台机器处理能力的限制。

 

 

今天这篇文章将会为大家介绍Near protocol提出的分片方案—夜影协议(Nightshade) 。

 

分片的基本设计

区块链依靠在所有节点复制所有交易来保证数据的正确性，每个节点如果只验证一部分，那就明显会降低安全性。

系统共有10个分片（shard chain）, 每个分片链由1/10的节点验证， 理论上TPS可以提升十倍，但安全性也会随之下降。

 

假设原始的区块链中有51%以上的恶意节点合谋了，才可以破坏整条链的状态，那么分片后只要有5.1% (51/100) 的恶意节点合谋就足够破坏某个分片上的状态。

 

大部分分片方案的应对思路是随机分配验证者，只要让恶意节点不在同一条分片链上，他们就无法合谋。

 

大多数方案选择用一条独立的链来实现管理分片， 处理POS（proof of stake）共识，生成随机数等等。

 

就比如以太坊2.0的Beacon chain、PolkaDot的Relay chain、Cosmos的Cosmos Hub。

 

而Nightshade也使用了一条这样的Beacon chain (信标链)。

 

一般来说区块链的节点会负责以下任务：

 

1.处理交易 。

2.Relay 合法的交易和区块给其他节点 。

3.保存整条链的状态和历史数据。

 

以上三点都会影响整个网络的处理能力。

 

从长远来看，状态存储的压力比较大，即使TPS一直保持在20左右，链的状态也会一直增长，但短期来看，区块链处理交易的能力才是更加重要的。

 

截止发稿，以太坊全状态大约为100G，大多数节点仍可以轻松处理，但是以太坊的TPS仅有20左右，很难满足实际需求。

 

Nightshade的分片也会分割以上提到的三点。 分片中的节点仅验证和传播与分片相关的交易，并且只存储和分片相关的状态。

 

 

在Nightshade的方案中，分片数量和计算、存储、网络等资源为线性关系。

 

Nightshade对Beacon chain和分片链进行了简化，在Nightshade中仅维护一条区块链，所有分片上的交易都会在这一条链上被确认。

 

一个块中的交易列表按照分片数量被分为多个chunks, 每个chunk对应一个分片，分片的验证者只需要下载和验证分片的chunk而不需要下载整个块，系统中没有节点会验证整个块的交易和状态。

 

现实中由于网络因素可能会导致chunks丢失，所以我们允许每个块中的分片可以对应一个或零个chunk。

 

出块

 

Nightshade中有两个角色共同维护协议： 出块者和验证者。

 

在系统中任何时间点都有w个出块者和wv个验证者，系统采用POS (proof of stake)，出块者和验证者都会质押一定的Token作为不遵守协议时的惩罚。

 

系统包含n个分片，每个出块者和验证者都仅下载和验证一部分的状态。

 

在本文所讨论的模型中w=100, wv=10000, n=1000。

 

系统的参与者可以通过质押大量的Token成为出块者，一个出块者会被分配到Sw个分片上（如果Sw=40, 那么每个分片就会有Sw*w/n=4个出块者）。

 

Nightshade中按照Epoch的概念选择验证者和出块者的分片，出块者需要在Epoch开始前下载分片的状态，并在整个Epoch中处理分片上的交易。

 

对于每个分片，都有一个出块者来负责生成chunk（和该分片相关的交易列表）， 在最终的块里只会包含交易列表的merkle root而不会包含完整的交易列表。

 

同一个分片上的出块者会轮流出块，如上面描述的，每个分片上有4个出块者，则每个出块者隔4 个块就要产生一次chunk。

 

跨分片交易

 

上文描述的分片方案中不同分片之间状态是完全隔离的，无法进行跨分片的交易。

 

举一个简单的例子，Alice想要转账给Bob，如果他们在同一个分片中，则交易可以正常处理。

 

但如果Alice和Bob在不同的分片，则每个分片的验证者都缺失了一部分状态，无法完成这笔交易的验证。

 

有两类方法可以支持跨分片交易：

 

一、同步。在同一个块进行与跨分片交易相关的多个分片的状态更新，验证者们通过与其他分片上的节点合作来处理交易。

 

二、异步。异步的完成跨分片交易的状态更新，比如某个分片先更新一部分状态，另一个分片再更新其余的状态。

 

这种方式非常简单并且易于协作，Cosmos、 Ethereum serenity (以太坊 2.0)、Near、Kadena等都采用的异步方案。

 

 

区块链或分片的互操作性在分片以外的场景也非常重要。 分片的场景下每个分片是同构的，且可以借助Beacon chain协调，所以跨分片的设计相比跨链会更容易一些。

 

Nightshade中则采用了收据交易的概念。发起跨链交易时首先在一个分片上执行交易，这个交易随后被打包在分片的chunk里，当chunk被打包到块中时，会生成一个收据交易。

 

验证者将这个收据交易发送到下一个需要更新的分片上执行。 如果这笔交易需要更新更多的分片上的状态，则会重复以上过程。

 

这个方案有可能会导致某个特定的分片成为热点，大量的收据交易需要发送到这个分片上，导致分片的处理能力不够。

 

为了解决这个问题Nightshade会在chunk中记录最后处理的跨链交易的进度：

 

块和分片以及处理到了哪个收据交易，下一个块的chunk就会继续处理接下来的收据交易。

 

如果待处理的收据交易数量实在太多，超过了一定限制的话，系统会禁止再发送新的跨链交易。

 

状态验证

 

分片的核心思想是验证者不用去下载和验证所有的状态。当节点与分片交互时，如何在不下载分片的情况下确定其状态是一个难题。

 

有个简单的方案：

 

假设整个系统总共有1000个验证节点，如果其中恶意节点不超过20%，那么当我们从中随机挑选200个节点组成分片时，恶意节点占比在1/3以上的可能性就几乎可以忽略。(恶意节点在1/3以下保证了分片可以使用BFT类共识)。

 

在这个简单的假设中，每个Epoch的验证者都会去询问之前的一组验证者，并获取到主链的信息。

 

而BFT类共识保证恶意节点在1/3以下时，块是合法的，且不会产生分叉。

 

因此我们只需从最初的状态去检查验证者的签名，就可以确定这条链的合法性。

 

 

简单方案只考虑了系统初始时有固定数量的恶意节点，但如果我们引入一个新的假设：

 

在系统运行时，诚实的验证者也可以被腐化为恶意节点，这个简单方案就无法正常工作了。

 

攻击者仅需腐化一个分片中2/3n+1的验证者就可以生成非法的状态。 这种安全性对于区块链来说显然太弱了。

 

Nightshade在BFT共识之上增加了挑战机制来提升安全性。任何的参与者检测到一个chunk包含非法状态时，都可以提供一个证明对chunk的出块者进行惩罚，同时获取奖励。

 

因为系统中大多数节点是没有非法chunk的分片状态的，所以证明中必须要包含足够的信息。

 

Nightshade要求在chunk中保存每一个交易执行后分片状态的merkle root，这样挑战者只需要找到第一个非法的状态，并从前一个状态进行验证就可以证明chunk是非法的。

 

 

Nightshade通过隐藏具体的验证者来进一步降低验证者被腐化的可能性。

 

这个想法类似于Algorand的方案，但需要注意的是，即使隐藏了验证者，一个攻击者仍能通过广播来倡议验证者进行合谋。

 

当诚实的验证者发现倡议合谋的广播消息时，可以下载攻击者想要攻击的分片并进行监控，这样即使合谋成功，诚实的验证者也可以立刻发送挑战来惩罚攻击者。

 

Nightshade用以下方法来隐藏验证者：

 

1.在每个Epoch开始前，验证者使用VRF（可验证随机方法）确定被分配到的分片，并在Epoch中负责验证这些分片。

 

2.所有的验证者都在区块上签名，而非在chunk上签名。

 

验证者有可能不去真正下载分片状态并执行验证，而是通过从网络中观察其他验证者的消息并进行重复来获利。

 

采用这种策略的验证者没有给网络带来任何额外的安全性。

 

为了防止这种行为，我们要求验证者首先提交一个承诺， 承诺中要么包含一条消息确定chunk的交易都是合法的，要么包含对某个非法状态的挑战。

 

验证者需要等待一定的时间后再去揭露实际提交内容，任何提交错误的验证结果，以及无法揭露承诺内容的验证者都会被惩罚。

 

数据可见性

 

数据可见性是区块链分片设计的另一个难题。即使有了复杂的验证和挑战机制，攻击者仍然有作恶空间。

 

 

同一个分片上的验证者还可以共谋作恶，只发布chunk header而不发布完整的chunk内容。

 

因为主链只会对chunk做确认而不会对其验证 （如果验证每个chunk，分片就没有意义了）。

 

所以主链的验证者无法判断chunk的内容是否被发布，出块者仍会把chunk包含在块中。

 

如果这些chunk包含了非法的状态，即使有诚实的节点对其产生怀疑，因为chunk的内容没有发布，节点也无法生成挑战证明。

 

NightShade的解决方案是选择引入了擦除码（Erasure Codes, 方案与PolkaDot和以太坊 2.0类似）， 擦除码允许我们在一部分数据不可见时仍能恢复整个区块。

 

我们对协议进行修改。当一个出块者生成了新的 chunk时，同时也要对chunk的内容生成擦除码。

 

 

Chunk的出块者把擦除码分割成w份（系统中出块者的数量），并用merkle tree计算每一个碎片，然后把merkle root保存在chunk header里。

 

Chunk的出块者随后通过onepart消息（用来发送擦除码的碎片）把擦除码碎片按照每人一份发送给所有出块者，消息包含：

 

chunk header、擦除码碎片的编号、擦除码碎片的内容、擦除码碎片的merkle proof以及出块者对这条消息的签名。

 

当主链的出块者收到块时，会检查是否已经收到了块中所有chunks的onepart消息， 如果没有则需要等待全部消息接受完成后再继续处理。

 

等到主链出块者确定每个chunks都收到了对应的onepart消息之后，就会向peers请求每个chunks其余的擦除码碎片，并重新构建chunks。

 

如果出块者无法成功构建chunks, 或者无法获取某个chunk的onepart消息的话，就会停止处理该块。

 

反之，如果出块者能够成功的构建出完整的chunks的话，则可以确定chunks的完整内容的确被发布了，Chunk header如果包含了非法状态，那么任何节点都可以对其生成挑战证明。

 

但是当前的协议仍有一个问题， 主链出块者有可能在收集完所有的onepart消息之前就进行了签名。

 

这样出块者仍会收到出块奖励，但不会受到任何惩罚，当大多数节点采取了这种策略时，数据可见性就无法得到保证了。

 

为了解决这个问题，chunk出块者需要对每个擦除码碎片分配颜色（红色或蓝色），并且将颜色保存为bitmask与chunk的内容一起编码成擦除码。

 

当chunk出块者发送onepart消息时同时也会附上碎片的颜色，并且擦除码碎片的merkle root也会同颜色一起计算。

 

主链出块者对块签名时，需要在签名中包含所有红色的chunks碎片组成的bitmask。

 

因为完整的bitmask只存在于擦除码中， 主链的出块者只有通过擦除码重新构造chunk内容和bitmask才能获取正确的颜色。

 

因此，主链出块者必须确保自己接收到了所有的onepart消息，且能正确构造所有chunks内容，才可以确保签名是正确的。

 

如果出块者没有收到某个onepart消息却仍然签名，则有50%的概率猜错颜色从而被惩罚。

 

投资有风险，本文观点和意见仅代表作者本人，并不构成任何建议。