了解夜影协议：突破限制的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%的概率猜错颜色从而被惩罚。
投资有风险，本文观点和意见仅代表作者本人，并不构成任何建议。