以太坊是最大的工程化的区块链“计算机”。它同时做到了数字资产交易和合约的上链，但由于交易记账和智能合约应用的性能要求不同，经常出现“道窄车多”的问题，扩容就成了当前基础公链技术的主要拓展方向。本期嘉宾兰荣坚将围绕“如何用分片技术对区块链扩容”，进行详细的解读。
主讲嘉宾
讲座内容
【项目简介】Harmony是基于分片等技术的新一代高性能区块链，专注于为去中心化经济提供可信，可靠，高效的基础设施。Harmony的设计思维来源于一片名为Omniledger的学术研究。
一、现有区块链的扩容问题
现有区块链比如比特币和以太坊的交易处理速度非常慢，比特币大概每秒处理5笔交易，而以太坊也仅能处理大概12笔交易。这使得很多应用场景无法实现，比如比特币最开始的设计是要作为一个交易系统，而因为低速度以及伴随的高交易费问题，现在只能作为价值存储媒介。
以太坊上的一些应用，比如去年红极一时的cryptokitties，一度使整个以太坊瘫痪长达几天时间，今年FCoin的新式上币规则，产生了大量交易，也是以太坊网络吃不消；之前的Fomo3D游戏也是因为以太坊容易阻塞的问题，让黑客钻了空子，拿到了最终大奖。总之，现有的区块链急需提高速度，也就是扩容。
那么为什么比特币和以太坊这么慢呢？原因是其背后的POW共识算法非常慢，POW是最长链共识机制，每笔交易需要全网验证，理论上POW的速度不可能高于一个节点的处理能力，并且为了避免分叉，全网数据需要尽量同步，所以区块间隔不能太短，这就是为什么比特币是十分钟一个块的原因。
现有的一些解决方案在不同程度上增加了共识过程的TPS(每秒交易处理量）。比如对POW的改进，包括Bitcoin Cash, 将区块大小从1MB提高到了8MB，这样在同样时间内，可以被处理的交易数量也能提高大概同样的倍数。
Segwit （隔离见证）也是在同样的数据大小上做文章，把一笔交易内的签名数据提出来单独放置，这样每笔交易的体积就变小了，每个区块能包含的交易数量就得到了提高，进而提高TPS。这类解决方案的问题是，数据量变大之后，全网更不容易同步，所以更容易产生分叉。
POS把POW算力证明用持币数量来替代，期待在不用计算哈希值的情况下，达到POW同样的效果，但POS现阶段有两个重要问题没有很好地解决。
1.nothing-at-stake attack：是指用同样的代币去押注不同的分叉，这样会导致更多的分叉；2.long-range attack：因为POS不需要任何物理上的资源，所以很容易在私下算出一条很长的链出来，甚至超过大家共识的链。
DPOS取消了全网随机选取出块者的过程，取而代之的是通过链下拉票的方式，人工选出少数节点让大家达成共识，很像是人民代表大会制度。因为共识节点数显著减少，所以达成共识的速度提升很多，但问题是几十个节点组成的共识网络的安全性，不能让人放心，如果其中一些节点合谋作恶怎么办！
DAG的方案是用有向无环图取代区块链的数据结构，让多个区块可以同时被提出，但问题是不同区块链的数据一致性很难保证，数据中会存在很多冗余的交易。
最后一类解决方案诉诸于链下扩容，比如状态通道和侧链技术，他们虽然可以大量的提高TPS，但是问题是安全性上存在风险，因为交易没有得到全网验证，只有少数节点在验证，如果一旦出问题，交易者必须自己去链上讨回公道。
二、怎么用分片技术来实现扩容
说了这些提高TPS，或者说扩容的解决方案，那么到底什么是扩容问题？在传统的分布式系统中的定义是，系统的性能会随着某个因素的增加而提高。
其中分为两类，一类是纵向扩容，是指通过增加服务器的处理性能来提高整体系统的性能，第二类叫做横向扩容，是指通过添加更多服务器，通过并行处理的办法，提高系统的处理速度。
我们刚才所述的几个解决方案，理论上都是纵向扩容。他们是在共识算法的性能上做文章，以提高一次共识的效率来提高整体的TPS。
但在区块链领域有这不可能三角这个理论，意思是所有共识算法都只能在速度，安全性和去中心化中三选二，三方面都完美实现是不可能的。他们都是在降低安全性，或者减少去中心化程度之后达到提高TPS的目的。并且目前这些解决方案最多也只能达到几千的TPS。
然而，很多应用场景，比如去中心化交易所，高交互性的游戏，和去中心化的交易市场，都需要上万甚至上百万的TPS，我们比如里面横向扩容，也就是分片技术，才有可能达到这么高的TPS。
刚才我们提到，在没有分片的区块链系统中，每笔交易都需要全网每个节点的验证，并且每个节点都存储着整个区块链的数据。
而在一个基于分片的区块链系统中，比如Omniledger的设计，每个节点是被分配到不同的分片里的（network sharding)，并且每个分片单独做共识，只处理一部分的交易(transaction sharding)，而且只存储一个分的区块链数据(state sharding)。而且只存储一个“部分”的区块链数据(state sharding)。
那么我们怎么可以安全的把节点分配到不同的分片呢？
在单一分片里，怎么达成共识？
同时片和片之间怎么实现交易呢？
首先，节点需要“随机”地被分配到不同的分片，这是为了保证每个分片内的恶意节点比例和全网预期的比例是一致的，这样单一分片就不容易被恶意节点所攻击。
意思是他们的占比不会超过安全范围，比如33%或50%）。为了达到这个比例的一致性，每个分片的节点数也要尽量多，这样统计上，这两个比例才会更接近。
左边是没有完全随机的分片，可以看到恶意节点可以通过某种方式，集中到某一个分片，占领大部分节点，从而控制整个分片，让其变得不可信，这样整个网络也不可信。
相反，右边采用完全随机的过程分片，每个分片的恶意节点的比例和全网的比例一样，依然在安全范围，全网也是安全的。
那么问题来了！怎么随机的分配节点呢？这个随机的来源从哪儿获得呢？依赖一个节点产生的随机数肯定是不行的，因为这个节点可以通过影响随机数，来影响最后分片的结果。
我们需要一个不可预测、不可干扰，同时又可以验证的随机数，答案就是用MPC 多方计算的办法。具体讲就是从全网中选择一部分节点，比如500个，让他们跑这个MPC的过程，每个人都贡献一部分的随机数，最后产生的随机数，是公平公正的，没有任何一个人，或者少数几个人人可以左右这个结果。
现在我们有了一个安全的分片机制，每个分片都可以保证恶意节点数量不会过高，那么如果在分片之后，某一个分片的节点被坏人收买或者攻破了怎么办？那个分片不也就变坏了么？
答案是我们需要定期的对分片的节点进行打散，踢出旧的节点，加入新的节点。这个期限叫做Epoch，它的长短是一个全网的参数，具体多长需要看预期坏人攻破一个分片的大部分节点所需要的时间。
如果需要一天时间，那么这Epoch就需要设置为小于一天。在Epoch开始时，进行分片，之后分片结构不变，每个分片进行正常的共识，直到Epoch结束，重新分片。
刚才说到需要有新节点加入，那么哪些节点可以加入呢？这要说到Sybil Attack，意思是一个坏人可以在网络中分身出无数多的身份，占据你的系统，在这里我们用跟其他区块链类似的解决方案，就是POW或者POS来验证身份，只有成功做过POW或者POS的节点才可以加入新的Epoch。
每一个Epoch内合法节点的身份我们用一个Identity Chain的链进行存储，每一个Epoch有一个Identity Block里面存了所有新节点的信息，以及刚才讲的随机数，和最后分片的结构。这样网络中每个人都知道自己在哪个片，片里同伴有谁，其他片是什么结构，以方便消息认证。
三、怎么安全的实现节点的分片
关于分片内如何达成共识，我们用的是改进的PBFT算法。传统的PBFT的消息复杂度是O(n^2)，所以最多只能支持20个左右的节点，并且它只可以容忍33%的恶意节点。但PBFT没有分叉的风险，并且每个块一经共识，就立即被确认，不需要等待，这使得整个分片系统可以更快的达成数据一致性。
之前我提到，每个分片如果想要足够安全，需要尽量多的节点数才行，为什么呢？在PBFT33%的恶意节点阈值下，我们假设全网恶意节点的比例在25%，那么每一个分片的节点选择，就类似于一个随机抽样过程。
恶意节点的概率是p=25%，在抽样次数为600时，恶意节点数量超过200（33%) 的概率遵循binomial cumulative distribution,概率大概为0.000003,这个数字意味着一百年分片才有可能出现一次问题。
既然我们需要600+个节点达成共识，PBFT又只能支持20个节点，我们于是需要对PBFT进行改进，使它能够支持600+个节点。做法是采用Schnorr多重签名，每个节点的签名投票信息可以被压缩打包成一个多重签名的大小。
这样省去了每个节点去广播自己投票的消息，只需要通过leader广播多重签名，就可以达到同样的效果，但是复杂度已经从O(n^2)降到了O(n)。
具体为什么要用Schnorr多重签名，是因为传统的ECDSA的签名算法是非线性的，所以多个签名的数据没法被加和到一起进行验证，需要分别验证，这里面没有任何工作量的减少。但Schnorr签名是线性的，多个签名可以被结合为一个签名大小的多重签名，并且可以一起验证，提高效率。
四、怎么实现跨片的交易
在片和片之间做交易方面，假设我在片1和片2里各有一个币，如果我想把他们一起转到片3，我怎么能保证这两个币可以同时花掉，而不会有中间状态，比如一个花了，另一个没花。解决方案就是需要用锁定的机制。具体步骤如下：
首先，我把我的交易广播给片1和片2。
他们收到交易后，验证其合法性，并且锁定我要转的币，并且达成共识，把共识的证明发回给我。这个证明根据验证情况，可以是接受或者拒绝处理。
当我收到两个分片的证明后，根据证明的内容（是否存在拒绝证明），我可以继续交易，或者撤销交易。
如果有任何一个分片认为我的交易它不能处理的话，我收到的证明里会包含它的拒绝证明，有了这个证明，我可以通过广播它和其他证明，让所有片安全的把我的币解锁，也就是Rollback我的交易。
如果一切顺利，片1和片2都认为我的交易他们可以处理，那我会收到两个肯定的证明，我通过广播这两个证明，片3就可以放心的转入(生成)我的两个币，片1和片2也可以安全的解锁我的币，并且把他们转出(删除）。
【补充】提高交易延迟（结算速度）的方法
我们基于PBFT的共识算法已经可以快速结算，但也要等大概5-10秒的时间，对于一些小额快速的交易，比如去星巴克买杯咖啡，这个处理速度还是略慢，我们希望交易处理延迟能在1秒内完成。
解决办法就是进行optimistic verify，意思是先通过几个少数节点进行验证，一切通过，就立即返回确认，这样用户的延迟会大大降低。
但这样会存在少数节点作恶的风险，所以交易之后还需要发到片内的所有节点做共识，在那之后，交易才会上链，如果交易没有通过大部分节点验证，那么说明之前的几个节点有问题，那么我们会对他们进行相应的惩罚。
问答&交流
M：怎么分的片,没看明白,有一个主链+一堆片吗?怎么解决double-spending（双花）?
兰荣坚：简单说就是随机分片，每个片有600个节点，有一个Identity链，类似于主链，但它不需要处理交易，只作为reference。double spending是通过片内PBFT的共识和片间的atomic transaction来防止的。
W：有没有状态分片，和Zilliqa 相比，有何不同？
兰荣坚：每个分片存储不同的数据，所以是状态分片，zilliqa每个分片存储全网数据，不是状态分片，并且zilliqa的分片随机数是用的POW哈希值，我们会用多方计算的安全随机数。
M：目测片内pbft与片间atomic trans防止不了double spending，我在片1花费的,片2怎么知道呢?除非有个全局状态账本
兰荣坚：因为是状态分片，所以片1花钱，只是花片1的钱，跟片2没关系，片2不需要知道片1的内容，（你在片1的钱 只能在片1花一次，你去片2是花不了片1的钱的）只有在片间转钱时，才需要片和片的沟通，用atomic transaction可以保证片和片间的交易没有问题。
M：也就是,我只能在片1内活动?片不是会打乱重新分么?另外mpc与随机数也没看懂,mpc一般用于zero knowledge
兰荣坚：打乱重分的是节点，目的是防止作恶，但是数据（状态）是不会重分的，因为没有必要，也不应该随便打乱。MPC只是大意上的概念，任何需要多方参与的计算过程 都可以归为MPC.这里我们用的是RandHound随机数生成算法，里面用到了VSS (verifiable secret sharing).
M：那有几种token呢? 数据(状态)就是ledger吧? 不重分也就能理解了，一种token,怎么判断我在哪个片里?
兰荣坚：链本身就一种token，对状态就是ledger，你的token可以在多个分片里，比如片1有5个，片2有8个 ...因为是状态分片，所以如果交易涉及的内容都在一个片内存在，就不需要和其它片沟通，只有当交易涉及到多个分片的数据时，才需要他们协调处理。
M：我原始的token怎么得到? 又是如何分到不同的片里的？pow是挖的,pos是创世一次出来,然后各种方式'分发
兰荣坚：这个具体我们还没有确定。对于POW，当然是片内的挖矿者在片内 得到币。POS的话，币可以均匀分布在每个片。可以这么理解，状态分片基本上就是协同合作的多个链，但重点是需要保证每一个分片的链都能安全，并且全局网络也安全。
M：用签名的方法改进pbft，看上去通信量变成o（n），但是实际的时延也是o（n），比普通的pbft还要大，o（n）还需要网络的拓扑可控。
兰荣坚：O(n)是指网络传输复杂度，并不是时间复杂度，PBFT的时间复杂度要看critical path, 相对比较难衡量。但网络传输量减少时，算法速度自然也会有提升。O(n)是理论上的计算，具体部署到网络中肯定有影响，但是理论上肯定是比传统PBFT快很多的。
W：节点随机划分的话，就会缺少局部性、内聚性，可能会频繁跨链沟通，这个性能是很差的，有考虑过这个问题吗？还有每隔一个时间打乱节点，那它存储的原来分片的数据咋办，直接丢切？新加入的直接下载？
兰荣坚：是的，这是基于分片的区块链的一大难题，分片间的沟通是非常低效的，所以我们会尽量让数据间的dependency不跨片，如果必须跨片的话，我们也会采用网络路径上的优化，比如用Kademlia routing来提高沟通速度。
数据同步也是一个很重要的问题，我们会通过一些优化，比如先同步状态，再同步历史，使得节点可以快速进入验证状态。同时节点根据存储量可以自行选择是否丢掉之前的片的数据。
