区块链 分片
进行区块链扩容的一个答案就是 分片技术 （Sharding）。分片技术承诺通过改变网络验证的方式来增加吞吐量。分片技术独特于其他解决扩容的链上技术的关键特性，就是它可以进行水平扩容，也就是说，网络的吞吐量随着挖矿网络的扩展而增加。这种特殊的特性可能使它成为推动区块链技术被快速采用的理想技术。
简单来说，分片技术就是一个 分散式并行系统 ，在保持主链完整稳定的同时，减少每个节点的数据储存量，从而达到扩容的效果。
现有区块链的扩容问题
公共区块链平台今天面临的最大问题之一就是可扩展性。所有主流的平台都在努力提高每秒的交易量。事实上，当今的公共以太坊网络和比特币网络平均每秒可以处理 7 -10 笔交易。这一数字远低于像 Visa 这样的集中支付处理器，后者平均每秒能处理约 8000 笔交易。
缓慢的交易处理造成了一个主要问题，因为大量的未完成交易阻塞了网络，使得那些诸如实时支付这样的应用程序很难在区块链上一展身手。随着确认支付的时间拉长，最终就会给用户带来诸多不便；这也是为什么像 PayPal 和 Visa 这样的信用卡支付方式仍然更具吸引力的主要原因之一。随着更多更复杂的 DApps 开始依赖于相同的一个区块链网络，迟缓的交易速度所导致的问题只会变得更加复杂。
从技术角度来看，所有区块链的共识协议都有一个具有挑战性的限制：网络中的每一个完全参与的节点都必须要验证每一笔交易，并且这些节点必须和它的其他节点保持一致，这是区块链技术的组成部分，它通过创建分布式的账本来保证区块链的安全。
在大多数像比特币和以太坊这样的区块链上，节点都是由公众进行运行的。虽然去中心化的共识机制提供了一些重要的优势，比如容错性、安全性、政治中立和真实性，但是这种验证链的方法是以降低可扩展性为代价的。当这些公共区块链变得更大时，它将需要越来越多的处理能力来验证这些公共区块链，这可能会在这些区块链的网络中造成瓶颈，从而减慢那些创建新应用程序的速度。
分片技术：分而治之
分片技术是一种基于数据库分片传统概念的扩容技术，它将数据库分割成多个碎片并将这些碎片放置在不同的服务器上。在公共区块链的情境中，网络上的交易将被分成不同的碎片，其由网络上的不同节点组成。因此，每个节点只需处理一小部分传入的交易，并且通过与网络上的其他节点并行处理就能完成大量的验证工作。将网络分割为碎片会使得更多的交易同时被处理和验证。因此，随着网络的增长，区块链处理越来越多的交易将成为可能。这种属性也称为水平扩容。
我们可以想象一下，现有的区块链就像一条繁忙的高速公路，这条高速公路的收费站只有一个收费口。这种布局的结果将是导致交通堵塞，因为人们将排着长队等待通过这唯一的收费站。实现一个基于分片技术的区块链就像在高速公路上增加 15 或 20 个收费口。它将极大地提高汽车通过收费站的速度。因此，分片技术将带来巨大的差异，并显著提高区块链的交易速度。
基于分片技术的区块链的实现对公共区块链有着不同的好处。首先，区块链上处理交易的速度变成了每秒上千笔甚至更多，这改变了人们对加密货币作为支付方式效率的看法。改善交易吞吐量将会给去中心化的系统带来使越来越多的用户和应用程序，而这将反过来促进区块链的进一步采用，也使挖矿变得更有利可图，同时也能吸引更多加入到公共网络上的节点，从而形成一个良性循环。
此外，分片技术可以帮助降低交易费用，因为验证单笔交易的处理量减少了；节点可以在依然盈利运营的同时收取较小的费用。在现实世界中，我们将低费用与高交易处理能力结合起来，会使公共链将变得越来越有吸引力。这些积极的趋势所持续的时间越长，我们就会越能看到更多的主流的加密技术和区块链应用程序的出现。
分片技术的策略
分片策略有网络分片和交易分片，以及状态分片等。通过网络和交易分片，区块链节点的网络被分割成不同的碎片，每个碎片都能形成独立的处理过程并在不同的交易子集上达成共识。通过这种方式，我们可以并行处理相互之间未建立连接的交易子集，通过提高数量级显著提高交易的吞吐量。
另一方面，在当今的主流公共区块链上，所有公共节点都承担着存储交易、智能合约和各种状态的负担，这可能使其在为了获得更大的存储空间而进行巨大的花费，以维持其在区块链上的正常运转。
为了解决这一问题，有一种可被称为状态分片的可行方法已被提出。这一技术的关键是将整个存储区分开，让不同的碎片存储不同的部分；因此，每个节点只负责托管自己的分片数据，而不是存储完整的区块链状态。
分片技术的复杂性
尽管所有不同形式的分片技术都可能非常直观，但通过对技术细节的解读，我们可以看到这一方法的复杂性和潜在的挑战。分片技术的其中一些挑战是很容易克服的，而另一些则不然。一般来说，网络和交易分片更容易实现，而状态分片则要复杂得多。下面，对于不同的分片机制，我们会明确地讨论它们所面临的一些挑战，以及它们的可行性。
1、网络分片：如何将全网节点划分到不同分片当中去
分片的第一个也是最重要的挑战是创建碎片。开发者需要开发一种机制来确定哪些节点可以按照安全的方式保留在哪些碎片中，这样就能避免那些控制大量特定碎片的人所发起的攻击 。
打败攻击者的最佳方法 (至少在大多数情况下) 就是建立随机性。通过利用随机性，网络可以随机抽取节点形成碎片。这样一种随机抽样的方式可以防止恶意节点过度填充单个碎片。
但是，我们如何建立随机性呢？最容易获得公共随机性的来源是区块，例如，交易的 Merkle tree root。在区块中所提供的随机性是可被公开验证的，并且可以通过随机提取器中提取统一的随机比特。
然而，简单地使用随机机制将节点分配给碎片仍是不够的。我们还必须要确保网络的一个碎片中不同成员意见的一致性。这可以通过像工作量证明这样的共识协议来实现。
2、交易分片：如何将全网交易划分到不同分片当中去
交易分片可听起来那么简单。考虑到在一个类似于比特币的系统中引入交易分片 (没有智能合同)，系统的状态是用 UTXOs 来进行定义的。我们假设网络已经由碎片所组成，用户发送一笔交易，每一笔交易有两个输入和一个输出。那么，该笔交易将如何分配给一个碎片呢?
最直观的方法是根据交易哈希值的最后几位来决定碎片。例如，如果哈希值的最后一个比特是 0 的话，那么交易将被分配给第一个碎片，否则它被分配给第二个碎片 (假设我们只有两个碎片)。这允许我们在单个碎片中验证交易。但是，如果用户是恶意的，他可能会创建另一笔具有两个相同输入但不同输出的交易——是的，就是一个双花交易。第二笔交易将有一个不同的哈希值，因此，这两笔交易就可能形成不同的碎片。然后，每个碎片将分别验证接收到的交易，同时忽略在另一个碎片中验证的双花交易。
为了防止双花问题，在验证过程中，碎片将不得不进行相互通信。事实上，由于双花交易可能会在任何碎片中出现，因此特定碎片所接收到的交易将不得不与其它的碎片进行通信。而实际上，这种相互之间的通信可能会破坏交易分片的整个目的。
另一方面，当我们有一个基于账户的系统 (没有智能合约) 时，问题就简单得多了。每一笔交易将会有一个发送者的地址，然后系统可以根据发送者的地址分配一个碎片。这确保了两笔双花交易将在相同的碎片中得到验证，因此系统可以很容易地检测到双花交易，而不需要进行任何跨碎片的通信。
3、状态分片：如何让各个节点只维护各自分片内的账本，但又不影响整个系统的安全性。
状态分片带来了新的挑战。事实上，状态分片是迄今为止最具挑战性的分片技术提案。
继续使用我们的基于账户的模型 (我们暂时不在我们的例子中引入智能合约)，在一个状态分片的区块链中，一个特定的碎片只会保留一部分状态。例如，如果我们有两个碎片和两个用户帐户，分别为 Alice 和 Bob，那么每个碎片将保留一个用户的余额。\
假设 Alice 创建了一笔交易，她将支付 Bob 一笔钱。这笔交易将由第一个碎片进行处理，一旦该笔交易被验证，关于 Bob 的新余额的信息就必须与他所在的碎片进行共享。如果两个受欢迎的帐户由不同的碎片进行处理，那么这可能需要进行频繁的跨碎片通信和状态交换。确保跨碎片通信不会超过状态分片的性能收益仍然是一个值得公开的研究问题。
减少跨碎片通信开销的一种可能方法，是限制用户进行跨碎片交易。以我们上面的例子来说，这就意味着系统不允许 Alice 直接与 Bob 进行交易。如果 Alice 必须与 Bob 交易的话，她将不得不在那块碎片中占有一个帐户。虽然这确实消除了任何跨碎片通信，但它可能会限制平台的可用性。
状态分片的第二个挑战是数据的可用性。我们可以考虑这样一个场景，由于某种原因，一些特定的碎片遭到了攻击而导致其脱机。由于碎片并没有复制系统的全部状态，所以网络不能再验证那些依赖于脱机碎片的交易。因此，在这样的情况下区块链基本上是无法使用的。解决此问题的方法是维护存档或进行节点备份，这样就能帮助系统进行故障修复以及恢复那些不可用的数据。但是，这样就使得节点将不得不存储系统的整个状态，因此这还可能会引发一些中心化的风险。
我们在任何分片机制 (当然不是特定于状态分片) 中需要考虑的另一个要点是，确保碎片在抵御攻击和失败时是具有弹性的； 网络必须接受新的节点并以随机的方式将这些分配给不同的碎片。换句话说，网络必须在一段时间内进行节点的重新分配。
然而，在状态分片的情况下，重新分配节点是非常棘手的。由于每个碎片只保留了状态的一部分，所以在一次重新调整网络的过程中，在同步完成前可能会出现导致使整个系统失效的问题。为了防止系统的中断，我们必须对网络进行逐步调整，以确保每个碎片在所有节点被清空前仍有足够多的旧节点。
类似地，一旦一个新节点加入了一个碎片中，系统就必须确保该节点有足够的时间与碎片状态进行同步；否则，传入节点将完全拒绝每一笔交易。
zilliqa 分片
开源地址：https://github.com/Zilliqa/Zilliqa
C++ 实现的
在亚马逊的 EC2 上面测试得到用 3600 节点实现了每秒 2488 笔交易
特点：分片技术、PoW+PBFT 混合共识机制
测试网络：https://explorer.zilliqa.com
Zilliqa 的设计构思 第 1 部分：网络分片
https://my.oschina.net/zilliqa/blog/2962501
Zilliqa 的设计构思 第 2 部分：共识协议
https://my.oschina.net/zilliqa/blog/2962504
Zilliqa 的设计构思 第 3 部分：使共识更有效
https://my.oschina.net/zilliqa/blog/2962511
Zilliqa 官方挖矿指南中文版
https://www.huoxing24.com/newsdetail/20181206173835283794.html
网络分片
假设我们有一个包含 1000 个节点的网络，将自动地把该网络分成 10 个、每个包含 100 个节点的分片，且所有分片可并行地处理交易。
由于分片架构能平行地处理交易，因此吞吐量可随着网络规模增加而线性增长。
每个分片现在都能独立处理交易并因此产生高吞吐量。
需要解决的关键问题
对女巫攻击的防御（Sybil Resistance）
创建分片、给分片分配节点和任务
分片大小
跨片交易
zilliqa 解决方法
防控女巫节点
使用 PoW。每个希望加入 Zilliqa 网络的新节点都必须先执行 PoW，网络中的现有节点验证新节点的 PoW 并授权其加入网络。
POW 工作量证明部分跟以太坊基本上是一样的，这要求你将上一个区块的哈希值、节点的 IP 地址和你的公钥一起进行哈希计算。
对应的难度是相匹配的，例如哈希值的前 100 位都是 0，如果你算出来的哈希值满足这个条件，就说明你完成了工作量证明。
根据工作量证明节点 ID 的最后几位，来决定分到哪一个分片上。对于一个新的节点来说，是无法通过自己的意志去加入某一个分片的，只能通过工作量证明，而工作量证明难度较高，因此可以避免出现新节点自己选择分片的情况。因此工作量证明的最后几位，就可以从数学上保证你的随机性是足够的。可以保证一些恶意节点不能直接加入到某一个分片。
自动创建分片
有一个单独的分片即 DS 委员会去整合每个分片的结果，收集不同分片里面交易哈希，进行一个共识协议，形成哈希的哈希，然后广播，其他节点验证签名。
在每个 DS Epoch 开始时，所有候选人都将运行工作证明（Ethash 算法）过程 300 秒窗口，以便竞争加入 Zilliqa 网络。
每个 DS Epoch（约 1.5 小时）内总共有 100 个 TX 时期（每个~1 分钟）。第 100 个 TX 时期被称为 Vacuous 时期。空白时期会处理 coinbase 交易（奖励机制）、升级机制（因为 pBFT 中没有分支）和持久状态存储（写入节点的 DB 而不是仅存储在内存中）。在这个时期，网络不会处理任何常规交易。
基于 POW 选举出 DS 委员会，使用先进先出策略定期移出一名 DS 委员会老成员、增加一名新成员，新进入委员会的节点是最快解决 PoW 的节点，任何时候 DS 委员会的大小都是固定的。DS 委员会一旦当选，便启动分片程序，网络中的所有其他节点立即执行另一个 PoW，其 PoW 由 DS 委员会验证，每个节点根据提交情况和随机性，被分配到特定的分片。PoW 提交的最后几位二进制数字决定了节点将被分配到哪个分片。
选择合适的尺寸
选择合适的分片大小对系统的安全至关重要。使用 PoW 创建分片相当于随机无差别地抽样一个节点集。
从 600 个节点开始，其包含三分之一的恶意节点的概率降至百万分之一。出于这个原因，Zilliqa 认为最小分片大小为 600。
避免跨片交易
因为跨片交易需要锁协议，因此其开销成本很高，在分片设计之初就尽量避免跨片交易的产生
原子提交协议技术方案
交易分片
每当交易到达网络时，它就被分配到一个特定的分片上。分配是由交易发送地址的前几位二进制数字决定的，这就叫做交易分片。
交易首先由分片打包，生成微块，然后上传给 DS 委员会，如果幸运，能被 DS 节点确认并签名，生成最终块。
每一个节点都可以收到最终的区块，这个区块的内容是很小的。同时，不同区块之间也会进行交换数据，从而分享最终区块内的这些交易。
整个系统有三层结构：第一层，是哈希的哈希；第二层，交易的哈希；第三层，真正的交易内容。通过这种三层结构来保证整个系统在每一步进行广播的时候，内容量都是相对比较小的。因此过了一段时间之后，你的不同分片里面，大家都可以获得这一段时间以来交易处理之后的一个共同状态。
交易分片按照交易发送者的账号地址来划分，来自同一发送者的所有交易都将在同一个分片中处理，允许每个分片成员检测其是否双花。通过每个交易中存在的随机数 nonce，可以轻松检测双重花费（或重放攻击）。
计算分片
分片还使计算执行和智能合约运行十分高效。例如，一部分分片可以充当映射器（mapper），其他部分分片可以充当归约器（reducer），并非常有效地执行映射 - 归约任务（map-reduce task），这也被称为计算分片。
共识协议
计算密集型的 PoW 需要大量的时间进行计算并且可能减慢共识协议，且它与网络中的节点数量无关，而是取决于网络的集体计算能力。不能很好地利用分片小的优势
实用拜占庭容错协议（Practical Byzantine Fault Tolerance, 简称为 PBFT）
Zilliqa 采用 PBFT 在每个分片中达成共识。该协议是由卡斯特罗和利斯科夫（Castro and Liskov）在 1999 年提出的。它是在这样的假设下运行的：在执行协议之前，假设每个分片中最多有 1 / 3 的节点是恶意的。
在 PBFT 中，一个共识组中（即一个分片中）的所有节点按顺序排列，它有一个主节点（领导者），其他节点被称为备份节点。每轮 PBFT 都有三个阶段：预备、准备、提交。
PBFT 与 Nakamoto 共识协议相比其他优点
交易最终性
一旦交易被提交到区块链，那么它就是最终的了且不会有临时分叉，因此不需要确认。
低能耗
Zilliqa 只使用 PoW 来防止女巫节点攻击、确认节点身份并进行分片，而不用于达成共识。现实中，每确认大约 100 个区块才需要做一次 PoW。
报酬差异小
Zilliqa 中参与共识协议的每个矿工都可以获得对应的奖励
PBFT 的挑战
一个主要缺点：只有当分片规模很小时（即小于 50）才高效。但是，正如我们前面的文章中所讨论的，出于安全原因，Zilliqa 的分片大小必须不少于 600 个节点。
PBFT 对于大型网络而言效率低下的主要原因是它有一个潜在的通信成本，即 分片中的每个节点都必须与所有其他节点通信，这就是通信成本二次方的原因。
使用数字签名而不是 MAC 将发送消息的数量从二次方数量级减少到线性，当 n 很大时这种减少会产生重要影响。以 600 个节点为例，其中传播的消息数量可以从 17.97 万减少到 599
使用多重签名的方法来降低通信成本，减少每个消息的大小
目前一种比较流行的多重签名方案是基于 Schnorr 数字签名技术
Zilliqa 使用了近期一些学术论文中的技术来提高经典 PBFT 协议的效率。