分片的理念与挑战，区块链分片悬而未决的问题

我们从更前沿的角度来看分片，包含分片尚未解决的两大挑战：数据有效性和数据可用性。简介区块链分片的核心是，大部分操作或使用网络的参与者，无法验证每一个分片中的区块；同样的，无论什么时候，参与者与特定分片进行交互，他们一般无法下载和验证该分片的整个历史记录。

然而分片的这一侧面有着极大的隐患：如果参与者无法下载和验证整个分片的历史纪录，就不能确保他们与之交互的结果是否已经被写入区块，同时这样的连续区块在分片中是否合法（这些问题在未分片的区块链中是不存在的）。

关于上述问题，我们先重温一个已经被许多协议提过的简易解决办法，接着分析这个办法的缺陷，及相关补救措施。

基于假设的简易解决办法关于数据有效性问题的解决办法最初如下：我们假设整个系统有数千个验证者，其中少于 20% 的验证者是恶意的或者会宕机（比如无法联机出块）。接着我们抽样出 200 个验证者，为了吻合实际意义，可以假设不可能超过 1/3 样本是恶意的。

1/3 是个重要的阈值。属于拜占庭共识（ BFT ）的一系列共识协议，都能保证只要少于 1/3 的参与者公识进程出错，不论发生节点崩溃或其他违反协议的情况，共识仍能完成。

假设诚实验证者占一定比例，如果分片中的验证者们提出某个区块，在验证开始前我们视该区块有效，并认为该区块建立在验证者认为当选的区块链（canonical chain，直译为“正统链”）上。当前验证者们会向上一阶段的验证者请求当选区块链（上一阶段出块过程符合假设，也接续当选区块链的头部、也就是最新的区块来出块）。经过递归查询整个区块链的有效性，而且没有任何验证者集合在过程中制造分叉的话，这种简易解决办法就能确定，目前的链在分片中的唯一性。

假设验证者能够在一定程度上被腐化（如，接受贿赂），这种简易解决办法就失效了。这并非是个无厘头的想法（想知道更多关于高效腐化验证者的方法，可见此处）。破坏 1000 个分片中的一个分片，明显比破坏整个系统成本小很多。因此，随着分片的数量增加，协议的安全性也跟着线性下降。为了确定某个区块的有效性，我们必须知道到在任何时间节点、任何分片中，大部分的验证者都没有彼此勾结；因此一旦存在灵活型敌手（adaptive adversaries），我们就无法确定区块的有效性。如同我们先前讨论的，验证者如果相互勾结，会造成两种恶意行为：产生分叉和生成无效区快。

恶意分叉的问题能够通过和信标链的交互连接（crossl-link）来解决，因为一般来说 Beacon chain 具有比分片更高的安全性。但是，无效区块问题处理起来就非常棘手了。

数据有效性在下图所示的情形中，分片 #1 被攻陷，恶意角色生成了无效区块 B （假设区块 B 中，Alice 的账户凭空多出 1000 个代币）。接下来，恶意节点紧接着区块 B 生成有效区块 C （换句话说，区块 C 中的交易被正确接受），借此掩盖无效区块 B；然后发起跨分片交易，将多出的 1000 代币发送到分片 #2 上 Bob 的账户。从此时此刻起，恶意创建的 1000 代币在分片 #2 中变得完全合法有效。

有些简单的方法处理这个问题：

要求分片 #2 的验证者，对发起跨分片交易的区块进行验证。这似乎无法解决上述问题，因为区块 C 貌似是完全正确的。

要求分片 #2 的验证者，验证发起跨分片交易的区块之前的若干（ N ）个区块。然而，对于任何要接受分片验证的 N 个区块，恶意验证者都可以在无效区块后面创建 N+1 个有效区块。要解决这个问题，比较有谱的办法是：将分片放入无向图，其中每个分片都与若干分片连接，并且只允许与相邻分片发起跨分片交易（ e.g. 这就是 Vlad Zamfir’s sharding 的大致内容，也与 Kadena’s Chainweb 的想法类似）。如果非互邻的分片需要发起跨分片交易，则这笔交易会通过多个分片进行路由。在这种设计下，分片中的验证者需要验证自身分片和相邻分片中的所有区块。下图中有 10 个分片，每个分片又有 4 个相邻分片，因而跨分片通信的中转次数必定不超过两次：

分片 #2 不只验证自己的区块链，也验证所有相邻分片的区块链（包括分片 #1 ）。如果分片 #1 中的恶意角色创建无效区块 B ，并在其上添加有效区块 C 试图发起跨分片交易，分片 #2 也不会接受该交易。因为分片 #2 会验证分片 #1 的历史纪录，进而发现区块 B 是无效的。

虽然破坏单分片不再是可行的攻击方式，但如果数个分片遭到破坏就成了问题。下图中，攻击者破坏了分片 #1 和 #2，并成功向分片 #3 发起跨分片交易，其中包含无效区块 B ：

分片 #3 会验证分片 #2 的所有区块而非分片 #1 的，所以无法察觉恶意区块的存在。正确解决数据有效性问题有两个主要方向：渔夫（ fisherman ）和密码学计算证明。

渔夫渔夫方法的核心思想是：无论何时、出于什么目的，只要在跨分片之间传递区块头信息（例如和 beacon chain 交互连接，或是发生跨分片交易），都设置一段时间间隔让诚实的验证者提供无效区块证明。有数种简明的结构能证明区块是无效的，因此接收这种证明的通信开销远小于接收整个区块。

只要分片中存在至少一个诚实的验证者，则系统就是安全的。

这是当今提出的协议中采用的主要方法（除了假装问题不存在的其他协议）。不过，这个方法存在两个缺点：

这个挑战窗口期必须足够长，使得诚实验证者能够察觉、下载、验证新产生的区块，并准备好在识别出无效区块时提出挑战。引入这样的挑战期会大大地降低跨分片交易速度。

挑战的存在会给攻击者带来新的武器，如发起无效挑战攻击。一个简单的解决办法是，让挑战者交一点押金，如挑战有效则退回。这只是个不成熟的办法，比如为了阻止诚实验证者提交有效挑战时，攻击者仍然乐于提交无效挑战（即使失去押金）；这种攻击又被称之为 Griefing Attack（损人不利己）。

在阻止无效区块方面，渔夫方法的两个缺陷都还未有令人满意的解决，不过仍聊胜于无。

简易的非交互知识论证关于多分片崩坏的第二个解决办法是使用特定的密码学结构，使得人们有办法证明某种计算被确切执行（比如通过一组交易来计算区块）。这种结构确实存在，比如 zk-SNARKs 、 zk-STARKs 等等，它们也被广泛用于今日的区块链协议中，像是我们熟知的 ZCash 。这类结构最令人诟病的是计算速度慢的令人发指，像是使用 zk-SNARKs 来证明所有链上区块有效性的 Coda 协议，据说每笔交易需要花 30 秒来创建一个证明（这个数字现在应该小了点）。

有意思的是，除了对计算的有效性作证，这种证明还能自证自己的有效性，不需要通过可信第三方。因此产生这种证明的计算量能够在一组参与者中进行分配，其冗余明显小于某些免信任型计算。 zk-SNARKs 允许参与者在特殊硬件上进行计算，不会降低系统的去中心化程度。

zk-SNARKs 除了性能方面的挑战，还包含：

其依赖的加密技术较少被研究及测试。

“冗余计算（ Toxic waste ）”—— ?zk-SNARKs 基于一种可信设置，要求一群人进行计算并舍弃中间值。如果所有参与者进行勾结并保留了中间值，则可能伪造证明。

在系统设计中加入额外的复杂性。

zk-SNARKs 仅适用于一部分计算，因此具有图灵完备智能合约语言的协议无法使用 SNARKs 方法来证明其链上区块的有效性。

虽然许多协议都考虑在将来使用 zk-SNARKs ，但除了 Coda 之外，我不知道还有没有其他的实行计划。

数据可用性我们在最初提到的第二个问题，是数据可用性问题。一般来说，操作某区块链的节点被分为两类：全节点，这种节点下载所有区块并验证每一笔交易；轻节点，这种节点只下载区块头，并只针对部分感兴趣的状态或交易使用 Merkle 证明。

如果大多数全节点勾结在一块儿，它们可以随意生成有效 or 无效的区块，并发送其哈希值给轻节点，而且不揭露该区块的内容。这些全节点能够以这种方式受益，如下图所示：

有三个区块：前一个区块 A 由诚实验证者产生；当前区块 B 由勾结的验证者产生；下一个区块 C 仍然由诚实验证者产生（右下角描绘了区块链的样子）。

假设你是个商人。当前区块 B 的验证者从前面的验证者处收到区块 A ，并计算出你应收到的钱，接着向你发送该区块头，其中包含你拥有这笔钱的状态（或“将钱发给你”的有效交易）的 Merkle 证明。你以为这笔交易无误，然后交付了服务或货品。

然而，验证者不会将区块 B 的内容发送给任何人。因此生成区块 C 的诚实的验证者收不到区块 B ，从而被迫继续接着区块 A 出块，这就变相夺走你作为商家所收到的钱。

当我们将同样的场景转移到分片，全节点和轻节点的定义仍然适用：每个分片中的验证者会下载并验证所处分片中的所有区块和交易，但系统中的其他节点（包含将分片状态快照到 beacon chain 的节点）只会下载区块头。因此对于某一条分片链来说，它的验证者就是全节点，其他系统参与者就是轻节点。

我们前面提到的渔夫方法，要求诚实验证者能够下载与 beacon chain 交互的区块。如果恶意验证者交互连接无效的区块头（或是使用无效区块头发起跨分片交易），然后不揭露区块内容，则诚实验证者就无法发起挑战。

关于这个问题，我们将介绍两个解决思路，它们是相辅相成的。

监管证明（Proof of Custody）我们要做的是避免区块一经发布就立即被使用。一种想法是让所谓的 “公证人（Notary）” 在分片之间轮转，它们唯一的工作就是下载区块，并 “证明这些区块能被下载”。公证人能够更快地在分片间进行轮转，因为相较于验证者，公证人不需要下载某个分片的完整状态。

这个方法天真之处在于，无法检查公证人是否真的尝试下载区块，所以公证人可以始终表明区块是可以下载的，却不进行尝试。其中的解决办法是要求公证人提出证明，或是抵押一些代币作为区块能下载的保证金，更多讨论详见此处。

修正码当特定轻节点收到区块哈希时，为了增加区块可用性的可信度，轻节点可以随机下载该区块的片段。这不是个圆满的解决办法，因为除非轻节点下载整个区块，不然恶意节点仍然能够选择部分未公开的区块内容提供给该轻节点，最后区块数据仍是不可用的。

解决办法是引入叫做“修正码”的结构，使得即便只有部分区块内容可用，也能还原出整个区块：

Polkadot 和以太坊 Serenity 都围绕这个想法进行设计，希望为轻节点提供一种方法，让他们能够确信这些区块是可用的。以太坊 Serenity 的设计详见此处。两方提出的办法都是基于挑战时间所设计的，因此唯一的潜在问题就是 griefing attack 。

长期可用性和结论提醒一下，上述方法都只能证明区块已经发布，且当前可用。可能出现以下情况使得区块在稍后的时间里变为不可用：节点掉线，节点故意抹去历史数据，等等。

关于这个议题， Polyshard 白皮书值得一看；即使出现数个分片丢失数据的情况， Polyshard 的修正码方案仍能保证分片之间的区块可用性。不过可惜的是，这个方法要求分片间要下载彼此的所有区块，使得成本非常高昂。

还好长期可用性并不是个迫在眉睫的事。因为系统中的参与者不被预期能够验证所有的分片链，所以分片协议应该按照这个思路设计：即使某些分片中的部分旧区块变得完全不可用，系统仍然能保证安全。

在设计安全协议时，数据有效性和数据可用性问题仍然没有完满的解决办法。我们会继续研究这些问题，请继续关注和更新我们的消息。

浏览过的版块