区块链分片技术解析（多图）
文库划重点：分片技术的概念要比区块链技术早得多，最早是在传统的数据库领域里面提出的，主要用于大型商业数据库的优化。其概念就是将大型数据库中的数据划分成很多数据分片（shard），再将这些数据分片分别存放在不同的服务器中，以减小每个服务器的数据访问压力，从而提高整个数据库系统的性能。简单来说，分而治之是分片技术的核心思想。
面对公有链目前存在的低吞吐量的性能瓶颈，许多公有链项目都提出了不同的扩容方案。从方向上来说，可以分为链上扩容和链下扩容两个方向，分片技术是属于链上扩容的一种方案。
分片技术（Sharding）作为以太坊未来扩容方案的一部分，引起了广泛的市场关注。同时也有多个主打分片技术的新公有链项目加入了竞争，比如Zilliqa, Rchain, Quarkchain等，使这项技术在行业中的热度越来越高。
这篇文章作为区块链分片技术研究的第一部分将会介绍分片技术的概念。
一、什么是分片
分片技术的概念要比区块链技术早得多，最早是在传统的数据库领域里面提出的，主要用于大型商业数据库的优化。其概念就是将大型数据库中的数据划分成很多数据分片（shard），再将这些数据分片分别存放在不同的服务器中，以减小每个服务器的数据访问压力，从而提高整个数据库系统的性能。
简单来说，分而治之是分片技术的核心思想。
而把分片技术运用到区块链网络中的思想是将拥有许多节点的区块链网络划分成若干个子网络，每个子网络中包含一部分节点，也就是一个“分片”（shard）。同时网络中的交易也会被划分到不同的“分片”中去处理，这样每个节点只需要处理一小部分传入的交易，不同的节点可以并行处理交易，即可增加交易处理和验证的并发度，从而提升整个网络的吞吐量。
传统的老牌公有链大部分都是单链结构，所有矿工都在相互竞争去延伸下一个区块。由于产生区块的平均时间是固定的，例如比特币平均每10分钟产生一个区块，随着越来越多的矿工加入挖矿行列，挖抗难度得到提升，以保证每10分钟产生一个区块。但是，随着投入更多的矿机，整个系统的吞吐量并没有得到提升。比特币处理交易过程如下图所示：
在引入分片技术之后，随着整个网络算力的线性提升（即节点数增加），分片的数量也会增加，进而提高了交易处理的并发度，整个网络的吞吐量也会线性提升。这个特点被称为可扩展性，又被称为水平扩容属性。分片网络处理交易过程如下图所示：
分片技术给区块链网络带来了如下好处：
1.从理论上讲，分片技术可以提高交易处理和确认的并发度，进而可以对整个网络的吞吐量提高几十倍甚至上百倍；
2.吞吐量成倍的增加，使得交易拥堵的问题得以有效的解决，有助于转账手续费的降低；
3.整个网络的吞吐量大幅提升，改变了人们对于加密货币支付效率低的看法，这将很大程度上促进dApp的发展，使得更多的dApp在分片网络上运行。虽然单笔交易手续费降低了，但是总体会提升挖矿收益，从而形成良性循环。
4.经典的以太坊公链状态信息都存储在区块链上，每个节点将保存全部的状态信息，这使得它的存储空间变得非常昂贵。状态分片具有很好的存储空间可扩展性，它的实现将极大地解决存储空间昂贵的问题。
二、网络分片、交易分片、状态分片
分片技术根据不同的分片机制可以划分为三种：网络分片（network sharding），交易分片（transaction sharding），状态分片（state sharding）。
1.网络分片
网络分片是最基础的一种分片方式，就是将整个区块链网络划分成多个子网络，也就是一个分片。网络中的所有分片并行处理网络中不同的交易。
这里主要涉及到的问题是哪些节点应该被分配到哪些分片当中。
⑴通过VFR来生成随机性
由于网络分片的特点是多个分片并行处理，提高并发度的代价是每个分片处理的交易之间没有冗余或者只有较少的冗余，一个分片中的处理结果将很可能决定了整个网络的处理最终结果。因此如果一个分片中的大量节点被一些人控制，那么这些被控制的大量节点完全可以左右这个分片的处理结果，从而威胁到整个网络的安全性。
因此，开发者需要一个合适的机制来对网络节点进行划分，以确定哪些节点可以安全地保留在哪些分片中，从而避免那些控制大量特定分片的人所发起的攻击 。
而防止一些人控制大量特定分片的最好方式就是建立随机性。在区块链领域建立随机性的方式主要是利用可验证随机函数（VFR, Verifiable Random Function），即一种非对称加密算法中的hash函数。利用随机性，网络可以随机抽取节点形成分片。这样一种随机抽样的方式可以防止恶意节点过度填充单个分片。
⑵ 可通过传统共识算法在分片中达成共识
然而，仅仅使用随机机制将节点分配给分片是不够的，我们还必须要确保网络的一个分片中不同成员意见的一致性，即如何达成共识。达成共识的算法可以选择我们熟知的POW、POS、pBFT等共识机制。 为了在分片的同时不失去去中心化特性，开发者需要尽可能地提高每个分片中节点的数量。
2.交易分片
由于网络分片是其他所有分片的基础，因此交易分片的前提是先进行网路分片。交易分片主要涉及的问题是哪些交易应该按照特定的属性被分配到哪些碎片当中。
⑴ 基于UTXO的账本系统
在基于UTXO的账本系统中，一笔交易可能由多个输入和多个输出构成，我们没有办法按照地址进行交易分片来有效地避免双花问题。比较直观的交易分片方式是按照交易的hash值最后几位进行分片。
假设我们有4个分片，那么我们就按照交易hash值的最后两位比特进行分片。例如，一笔交易的hash值最后两位是10，则我们将该交易分配到第3个分片中进行处理（两位比特的值00，01，10，11分别对应于第1、2、3、4分片区）。
而如果这个时候交易的发起者同时又发起了另一笔交易，和之前的交易具有相同的输入，但是输出却不同，而该交易hash值的最后两位是00，那么该交易则被分配到了第一个分片中进行处理。
如果不采取任何措施，这两笔交易将同时在两个分片当中进行处理和验证，这将导致一笔双花交易。
为了防止双花交易，分片1和分片3不得不进行通信，来达到信息的交互。而实际过程中，这种交易的hash值是随机的，系统必须保证每个分片之间都进行信息的交互。而实际上，这种相互之间的通信可能会破坏交易分片的整个目的。
⑵基于账户系统
在基于账户系统中，上述问题可以得到很好的解决。即一笔交易只有一个输入，而输入的地址将被记录在账户系统中。该账户系统在交易分片的每个分片中是全局可见的，因此我们只需要将交易按照发送者的地址进行分片，即可保证同一个账户发出的多笔交易将被在同一个分片当中被处理，这样该分片可以有效的检测双花交易而不需要复杂的跨分片的通信。
3.状态分片
在所有的分片当中，状态分片是最具挑战的分片方式。状态分片的关键是将整个存储区分开，让不同的分片存储不同的部分，每个节点只负责托管自己的分片数据，而不是存储完整的区块链状态。状态分片可以减少状态的冗余存储，使得整个区块链网络具有存储的可扩展性。
⑴ 跨分片信息通信不可避免
在账户型系统中，状态分片是按照账户的地址进行分片的，并且一个特定的分片只会保留一部分状态，而不像是交易分片那样每个节点都保存整个网络中的所有状态。
假设A创建了一笔交易，将支付B一笔钱。这笔交易将由第一个分片进行处理，一旦该笔交易被验证，关于B的新余额的信息就必须与他所在的分片进行共享。如果这两个帐户由不同的分片进行处理，那么这可能需要进行频繁的跨分片通信和状态交换。跨分片通信可能又会降低状态分片的性能。
⑵数据的可用性是必须考虑的问题
状态分片的第二个挑战是数据的可用性。我们必须考虑这样的场景：由于某种特定的原因，一些特定的分片遭到了攻击而导致其脱机。由于分片并没有复制系统的全部状态，所以网络不能再验证那些依赖于脱机分片的交易。
解决此问题的方法是维护存档或进行节点备份，这样就能帮助系统进行故障修复以及恢复那些不可用的数据。但是，这样就使得一些节点将不得不存储系统的整个状态，同时这还会引发一些中心化的风险。
⑶网络节点调整需要逐步进行
任何分片机制中需要考虑的另一个要点是，确保分片在抵御攻击和失败时是具有弹性的，网络分片必须接受新的节点并以随机的方式将这些分配给不同的分片。简而言之，网络必须能够在一段时间内进行节点的重新分配。
在状态分片的情况下，重新分配节点是非常困难的。由于每个分片只保留了状态的一部分，所以在一次重新调整网络的过程中，必须要防止调整过大而导致在同步完成前可能会出现的整个系统失效的问题。为了防止系统的中断，我们必须对网络进行逐步调整，以确保每个分片在所有节点被清空前仍有足够多的旧节点。
而新节点在加入分片之前，需要等待同步完该分片中的状态信息之后才可以正式加入分片并提供算力。
值得注意的是，一条公链可能会同时使用多种分片技术，它们之间并不互相矛盾。从网络分片到交易分片再到状态分片，在技术实现难度上来看，它们的难度依次递增。我们在描述一条公链所采取的分片技术的时候，往往以它用到的最难的技术作为其标签。
三、采用分片技术的公有链：以太坊 vs Zilliqa
1.以太坊分片概述
为了解决可扩展性问题，以太坊2.0的分片引入了链上状态分区（on-chain state partition）的概念来获得更高的吞吐量。以太坊2.0将以太网络分为两层，上层为现有的以太坊主链，基本保持不变；下层为分片链，主要用于分片运算。不同层次的对象区别如下：
可以简单地这么认为，分片中的交易都会被装入“校对快” （collation）。 与侧链类似，校对器（collator）只有一小部分会被记录到主链：
1) 分片链上的交易处于自己独立的空间中，分片验证人（shard validator）只需要验证他们所关注的分片。
2) 分片链通过 POS 机制依附于主链，以获得更高层次的共识（higher level of consensus）。
具体过程就是分片中包含多个节点，即分片验证人，他们可以通过POS机制在分片中完成交易的验证，验证之后产生一个校对块，而这个校对块的一头部信息被加入到主链上面，具体的交易并不保存在主链上面。
一方面，以太坊2.0通过引入独立分片，赋予了整个网络的并行处理能力，提升了整个系统的吞吐量；另一方面，每个分片只保存一部分的历史状态数据，主链不需要保存具体的交易信息，可以大大降低节点的存储压力。
2.Zilliqa分片概述
Zilliqa通过Pow算法完成网络节点的划分过程：选出1个Boss分片和多个工作分片，每个分片有不低于600个节点。其设计思想来源于谷歌提出的Map-reduce编程模型的思想。它的分片分为两个阶段：
1) Map：网络上的每一笔交易会根据发送者的地址被映射到工作分片中，工作分片通过pBFT共识算法在各自的分片当中验证交易，最终形成当前工作分片中的子区块。
2) Reduce（Merge）：工作分片将子区块发送到Boss分片，Boss分片将多个子区块进行验证、打包，合并生成最终区块，保存在各个节点当中。
Zilliqa分片技术，是属于网络分片和交易分片的范畴，网络的节点是运作在同一个空间。网络中的所有节点都工作在主链上，并且每个节点都保存着所有的历史记录。综上，Zilliqa通过网络切分，多个工作分片并行工作，能够极大提升系统的吞吐量，但是每个节点依然保持所有历史记录，并没有解决存储空间的扩展性问题。
3.以太坊与Zilliqa分片技术对比
四、总结
在本文中我们讲解了分片技术概念的起源以及其在区块链网络中的应用，然后介绍了分片技术的三种形式：网络分片、交易分片、状态分片，最后介绍了以太坊与Zilliqa所采用的分片技术的异同。在区块链分片技术研究的第二部分，我们将详解分析和讲解一些采用了分片技术的区块链项目。
参考文献：
【1】Yaoqi Jia, “Op Ed: The Many Faces of Sharding for Blockchain Scalability,” BitcoinMagazine.com, March 20, 2018.
收录于哈希力量，手机站省略本文固定网址
