2018年3月20日
Zilliqa联合创始人贾瑶琪发表于《Bitcoin Magazine》
Rita译
译者按
《Bitcoin Magazine》由Vitalik和他人共同创建于2012年，是区块链领域时间最长、最具权威、技术含量最高的杂志之一。
在区块链领域应用分片技术，首次是由Zilliqa团队成员、新加坡国立大学师生Prateek Saxena和Loi Luu于2015年在CCS会议上发表题为“A Secure Sharding Protocol For Open Blockchains”的论文提出的，因此Zilliqa也被称为“分片之王”或“分片之父”。此后，全球多个项目如以太坊2.0等也展开了有关分片的研发，但每个项目侧重不同，例如Zilliqa侧重研究交易分片和网络分片，而以太坊2.0侧重研究状态分片等。Zilliqa将在2018年3月底推出1.0版公开测试网络，这将是全球首个将分片技术落地的项目。通过此文，您将深入了解分片技术的原理、分类以及其面临的机遇和挑战。
作者简介
贾瑶琪，Zilliqa联合创始人兼技术总监、区块链和信息安全技术专家。新加坡国立大学博士，曾任该校研究员，重点研究领域是：可扩展和隐私保护的分布式网络。有多篇学术论文发表于CCS,、USENIX Security、PETS、RAID、ESORICS等国际顶级安全会议，曾获W2SP (2014)和ICECCS (2014)最佳论文奖。其研究成果CVE-2014-7948 for Chrome和CVE-2015-5907 for Safari分别被谷歌和苹果公司采纳，并得到了业内知名媒体Dailydot、Gizmodo、Techspot等的广泛报道。
正文
任何一个开发dApp的程序员都应该认识到了当前公有区块链的局限性。区块链局限性最突出的体现就是网络吞吐量有限，也就是说每秒处理的交易数有限。为了使dApp的吞吐量满足实际需求，区块链就必须具有可扩展性。
解决区块链可扩展性问题的一个重要的办法就是分片技术(sharding)。分片承诺，通过改变网络验证区块的方式来增加网络的吞吐量。在所有的链上(on-chain)扩展解决方案中，分片技术是独一无二的，因为它带来的扩展是横向的，也就是说，网络吞吐量随着矿工节点数量的增加而增长。正是因为分片的这种特性，它很可能成为推动区块链技术迅速普及的理想动力。
本文首先将简要介绍现有区块链平台的扩展性问题，当然这部分只是简单介绍，因为相信大多数读者对此已经耳熟能详了。之后我将重点阐释，为什么说分片技术以及它的不同形式是扩展性问题极佳的解决方案。本文还将谈及，实现分片技术的一些理论和实践上的挑战，以及如何克服这些挑战。
现有区块链的可扩展性问题
当前，公有区块链面临的最大问题之一是可扩展性。因此，所有主流的区块链平台都在努力交易速率，但实际上，比特币和以太坊网络每秒平均仅可处理7-10笔交易，这些数字远远低于VISA这样的中心化的支付处理器，后者平均每秒处理大约8千笔交易。
网络拥堵、交易速率低下带来的一个主要问题是，使区块链难以使用实时支付类的应用。支付需要处理的时间越长，用户们使用就越不方便。这也是为什么PayPal和Visa等信用卡支付方式更受欢迎的主要原因之一。随着越来越多复杂的dApp加入网络，交易速率低下带来的问题只会更加严重。
从技术角度来看，所有的区块链共识协议都具有局限性的原因是：网络中的每个完全参与的节点都必须验证每一笔交易，并且要与其他节点达成一致。因为，这正是区块链技术创建分布式账本并确保它安全性的根本组成部分。
在比特币和以太坊之类的大多数区块链平台中，节点就是公众。虽然去中心化的共识机制提供了诸如容错、安全性、政治中立性、真实性等重要优势，但当前这种验证区块的方法却是以可扩展性为代价的。随着区块链网络的不断增大，区块链的验证工作将需要越来越多的算力，这将成为这些网络的瓶颈，并会影响新应用程序的加入。
分片:分而治之(Divide and Conquer)
分片是一种扩展技术，它受传统数据库分片概念的启发，就像数据库被切分成几部分放置在不同的服务器上一样，在公有区块链中，交易被划归到不同的分片（shard）上同时进行处理，而这些数量众多的分片又是由整个网络切分得来的。也就是说，每个节点只处理整个网络中一小部分的交易，并且这个处理过程是与整个网络中的其他节点同时进行的。这就意味着，加入网络的节点越多，分片的数量也越多，整个网络能够同时处理的交易也越多。也就是说，网络规模越大，交易速率越高。这种属性也被称为“横向扩展”。
我们可以打个比方来理解分片技术。假设，现有的区块链像繁忙的高速公路一样，车辆为了通过高速路必须经过收费站，而收费站只有一个收费亭。所以，当车辆过收费站时，必然得排队结果就造成了堵车。基于分片的区块链就相当于，在收费站增加了20或更多个收费亭，这将显著地提高车辆通过速度。分片就是以这种方式极大地提高交易速率，从而给区块链的发展产生巨大的影响。
分片技术将给公有区块链带来许多好处：一方面，分片将彻底改变用户体验，让使用更加便捷。在使用分片后，区块链每秒将处理数千笔甚至更多的交易，交易吞吐量和支付效率将显著提高，所以用户数和应用程序数都将增加，这将给矿工带来更多利润，所以会有越来越多的节点加入网络，这也将反过来进一步提升网络效率，使整个区块链发展进入良性循环。另一方面，分片可以降低交易费用。因为验证单个交易需要的节点数更少，所以每个节点验证交易的计算处理量也极大地减少了，因此即使收取相对较少的费用，节点依然有利可图。
网络的高效率和支付的低费用相结合，公有区块链将变得越来越具有吸引力，将更加适应当前世界的需求。随着这些积极趋势的发展，我们将会看到加密货币和区块链应用越来越普及。
分片策略
网络分片和交易分片就是，将区块链网络上的所有节点分割成不同的分片，每个分片处理一部分交易并就该交易达成共识。通过这种方式，毫无关联的交易可以同时被不同的分片处理，这将显著地把交易吞吐量提高好几个数量级。
另一方面，在当前主流的公有链上，存储交易、智能合约和各种状态的工作是由所有节点承担的，所以为了维持节点在区块链上的操作，储存空间可能花费高昂。一种可能的解决方法被称为状态分片。这个技术的关键是将整个存储分成不同的部分，让不同的分片去存储这些部分。因此，每个节点只负责存储自己所在分片的数据就行，而不是存储整个区块链的状态。
分片的复杂性
尽管各种形式的分片听着都很直白简单，但其实际的复杂性和面临的挑战是巨大的。通过对技术细节的分析，我们可以知道，有一些困难相对来说容易克服，但另一些则不尽然。整体上来讲，网络分片和交易分片更容易些，状态分片更复杂些。接下来，让我们针对不同的分片机制，探讨他们的可行性和挑战。
1、网络分片
分片技术的首要任务是创建分片，也就是说，需要先开发一种机制决定将哪些节点划分到哪个分片，这种机制必须足够安全，以避免在特定分片中有人取得控制权从而发动可能的攻击。在绝大多数情况下，保证安全的最佳方法都是创造随机性。网络随机抽取节点组成分片，从而防止恶意节点控制单个分片。
那么，随机性从何而来?公开随机性最便捷的来源是，区块中Merkle树的交易根。区块中的随机性是可公开验证的，并且可以用随机抽样器(randomness extractors) 从中提取出(近乎)均匀随机二进制数字。
然而，仅仅通过一个随机机制将节点划分给分片是不够的，还须确保网络同意分片中的成员组成。这则可以通过执行工作量证明之类的共识协议来实现。
2、交易分片
交易分片并不像听起来那么简单。如果，我们在比特币之类的没有智能合约的系统中引入交易分片机制，其中系统的状态是用UTXO定义的。假设，现在网络已经划分好分片了，并且已有一个用户发送了一笔交易，交易有两个输入和一个输出。那么，怎么把这笔交易分配到一个分片上呢?
最直观的方法是，根据交易哈希值的最后几位二进制数字决定。例如，这个网络只有两个分片，如果哈希值的最后一位是0，那么交易分配给第一个分片，否则分配给第二个分片。这就使得这笔交易在一个分片上验证就够了。但是，如果用户是恶意的，他想制造双重花费的情况，那么他可能会创建另外一个具有相同的两个输入但一个不同输出的交易。由于第二笔交易的哈希值肯定跟第一笔不同，那么结尾也可能不同，所以这比交易就可能被分到不同的分片上，所以不同的分片就会分别验证这两笔交易，而忽略这笔交易正在“双花”的问题。所以，为了防止双花，交易在验证过程中必须进行分片之间的沟通。由于双花交易可能被分配在任何分片中，所以接受交易的分片必须跟其他所有分片通信。但其实，这种通讯代价高昂，是与交易分片的整个初衷相违背的。
而实际上，当我们有一个基于账户的、无智能合约的系统时，问题就更容易解决了。每笔交易都包含有发送人的地址，然后根据发送人的地址将交易分配给分片。这确保了双重花费的交易将在同一个分片中被处理，因此在没有任何跨分片通信的情况下也能轻松检测到双花的情况。
3、状态分片
状态分片带来了一系列新的挑战。事实是，状态分片是截止目前所有分片方案中最具挑战性的。
让我们继续使用刚刚提到的基于账户的、不引入智能合约的系统模型。在状态分片的区块链中，特定的分片只保存一部分存储状态。例如，如果我们有两个分片并且只有Alice和Bob两个用户账户，每个分片只保存一个用户的余额信息。
假设，Alice要给Bob转一笔账。交易首先由第一个分片处理，处里完成后，第一个分片要与第二个分片也就是Bob的分片沟通Bob的新余额信息。如果两个交易频繁的账户分别由不同的分片储存，那么这可能需要频繁的跨分片通信和状态交换。而跨分片沟通的成本和收益孰高孰低，仍是一个不确定的待研究问题。
一种降低跨分片通信开销成本的方式是，禁止用户进行跨分片交易。还拿刚刚的例子来说，这意味着不允许Alice与Bob进行交易。如果Alice非要与Bob进行交易，那么她就得在Bob的分片中也持有一个账户。虽然这种方法避免了任何跨分片通信，但将极大地影响平台的使用体验。
状态分片的第二个挑战是数据有效性。假设，出于某种原因某个分片被攻击了并掉线了。由于系统的状态并未跨所有分片复制，因此网络无法再验证已经分配给掉线分片的交易。结果，区块链网络可能大程度不可用。解决这个问题的方法是进行归档或备份节点，让网络即使在遭遇攻击掉线的情况下也能恢复数据继续运转。然而，这就意味着一些节点要存储全网的状态，这就面临着中心化不安全的风险。
在包括状态分片的所有分片机制中，都要考虑的另外一点是，为了确保分片能够防御攻击、垮掉等问题，网络不能是静止的，而是要保持流动性。也就是说，网络必须接受新节点并以随机的方式将它们分配给不同的分片，即网络必须时不时重新洗牌。
然而，在状态分片中，处理重新洗牌非常棘手。由于每个分片只保存一部分状态，因此想要一次性彻底重新洗牌，换掉所有节点可能因为新分片节点尚未同步的问题，导致网络中断，直至所有同步完成整个网络才可以继续使用。为了防止中断，网络必须慢慢地、逐步地洗牌，以确保在一个分片中，在所有节点替换前，有足够的旧节点维持该分片正常运行。
同样地，在一个新节点加入一个分片时，就必须确保该节点有足够的时间与分片的状态进行同步，否则新加入的节点将可能完全拒绝所有交易。
结论
分片无疑是令人兴奋且有十分有前景的区块链技术，它将解决区块链目前面临的可扩展性的问题，同时不会牺牲去中心化和透明性。然而，毫无疑问地，在设计层面和实施层面，分片特别是状态分片，在执行上是很难做到的。
处理分片必须小心谨慎，此外我们需要更多地研究状态分片的可行性，因为它可能不是存储问题的灵丹妙药。研究和开发人员目前正在积极寻求替代解决方案。也许，答案就在眼前。
原文和链接
链接：
https://bitcoinmagazine.com/articles/op-ed-many-faces-sharding-blockchain-scalability/
原文：
Any programmer who has ever sat down to build a DApp at one point has had to think about the limits of current public blockchains, the most important and obvious one being their limited throughput, i.e., the number of transactions processed per second. In order to run a DApp that can handle real-world throughput requirements, blockchains must become scalable.
One answer to blockchain scaling is sharding. Sharding promises to increase the throughput by changing the way blocks get validated by the network. The key feature of sharding that makes it unique among all (on-chain) scaling solutions is horizontal scaling, i.e., the throughput increases as the mining network expands. This particular characteristic of sharding may make it the ideal fuel to spur rapid adoption of blockchain technology.
This article will briefly discuss the scaling issues with existing blockchain platforms — briefly only, because most readers must already be familiar with it. It will then discuss how sharding and its different forms can be a promising solution to the scaling problem. It will also touch upon some of the theoretical and practical challenges to implementing sharding and how some of these challenges can be overcome.
Scalability Issues With Existing Blockchains
One of the biggest problems that public blockchain platforms face today is scalability. All popular platforms are struggling to handle a larger number of transactions per second. In fact, today the public Ethereum and Bitcoin networks can handle 7-10 transactions per second on average. These figures are far inferior to those of centralized payment processors like Visa, which processes roughly 8,000 transactions per second on average.
Slow transaction processing creates a major problem because they choke up the networks, making it difficult to use the blockchain for applications such as real-time payments. The longer a payment takes to be processed, the more inconvenient it becomes for the end user; this is one of the main reasons why payment methods like PayPal and credit cards like Visa are still much more attractive. As more complex DApps start to rely on the same network, the problems caused by slower transaction speed will only compound.
From a more technical standpoint, all blockchain consensus protocols have a challenging limitation: Every fully participating node in the network must validate every transaction and must seek agreement from other nodes on it, and this is the component of blockchain technology that creates distributed ledgers and makes it secure.
In most chains like Bitcoin and Ethereum, nodes are run by the public. While the decentralized consensus mechanism provides some vital advantages such as fault tolerance, security, political neutrality and authenticity, this method to verify chains comes at the cost of scalability. It will take more and more processing power to verify these public blockchains as they get larger, and this may create bottlenecks in these networks and slow down the creation of new applications.
Sharding: Divide and Conquer
Sharding is a scaling technique that was inspired by a traditional concept of database sharding, whereby a database is partitioned into several pieces and placed on different servers. In the context of a public blockchain, the transaction load on the network would be divided into different shards comprising different nodes on the network. As a consequence, each node would process only a fraction of incoming transactions, and it would do so in parallel with other nodes on the network. Breaking the network into shards would result in more transactions being processed and verified simultaneously. As a result, it becomes possible to process more and more transactions as the network grows. This property is also referred to as horizontal scaling.
We could imagine that existing blockchains operate like a busy highway with one toll station operating on only one toll booth. The result would be a traffic jam as people wait in long lines to pass the toll station. Implementing a sharding-based blockchain is like adding 15 or 20 toll booths to the highway. It would dramatically improve the rate at which traffic can progress through the stations. Sharding would make a tremendous amount of difference and dramatically improve transaction speed.
The implementation of sharding-based blockchains could have various benefits for public blockchains. First, thousands of transactions or even more could be processed every single second, changing the way people feel about the efficiency of cryptocurrencies as payment methods. Improving transaction throughput will bring more and more users and applications to decentralized systems, and this will, in turn, advocate further adoption of blockchains, making mining more profitable and attract more nodes to public networks, creating a virtuous cycle.
Furthermore, sharding could help bring down transaction fees since less processing will be needed to validate a single transaction; nodes can charge smaller fees and still be profitable to run. Coupling low fees with high transaction processing capability, public chains will become increasingly attractive to real-world use cases. The more these positive trends continue, the more mainstream adoption we’ll see of cryptocurrencies and blockchain applications in general.
Sharding Strategies
This is the basic concept, but there are more granular ways to implement sharding strategies like network and transaction sharding, and state sharding. With network and transaction sharding, the network of blockchain nodes is split into different shards, with each shard formed to process and reach consensus on a different subset of transactions. This way, unconnected subsets of transactions can be processed in parallel, significantly boosting the transaction throughput by orders of magnitude.
On the other hand, on today’s mainstream public blockchains, the burden of storing transactions, smart contracts and various states is borne by all public nodes, which could make it prohibitively expensive in terms of required storage space to maintain ongoing operations on the blockchain.
One potential approach, called state sharding, has been proposed to resolve this issue. The crux is to divide the entire storage into pieces and let different shards store different parts; thus every node is only responsible for hosting its own shard’s data instead of the complete blockchain state.
Complexities Underlying Sharding
While all the different forms of sharding may be very intuitive, unspooling the technical details can reveal the complexity of the approaches and the underlying challenges. Some of these challenges are easy to overcome, while others not quite so. Generally speaking, network and transaction sharding are easier to accomplish while state sharding is much more complicated. Below, for the different sharding mechanisms, we categorically discuss some of these challenges and how feasible are they to be overcome.
Network Sharding
The first and foremost challenge in sharding is the creation of shards. A mechanism will need to be developed to determine which nodes reside in which shard in a secure way in order to avoid possible attacks from someone who gains a lot of control over a particular shard.
The best approach to beat an adversary (at least in most of the cases) is through randomness. By leveraging randomness, it should become possible for the network to randomly sample nodes to form a shard. Random sampling prevents malicious nodes from overpopulating a single shard.
But, where should the randomness come from? The most readily available source of public randomness is in blocks, for instance, the Merkle tree root of transactions. The randomness available in blocks is publicly verifiable and (close to) uniform random bits can be extracted from it through randomness extractors.
However, simply having a randomized mechanism to assign nodes to a shard is not sufficient. One must also ensure that the network agrees on the members in a shard. This can be achieved through a consensus protocol like proof of work, for example.
Transaction Sharding
Transaction sharding isn’t as simple as it may sound. Consider introducing transaction sharding in a Bitcoin-like system (without smart contracts), where the state of the system is defined using UTXOs. Let us suppose that the network is already composed of shards and a user sends out a transaction. The transaction has two inputs and one output. Now, how should this transaction be assigned to a shard?
The most intuitive approach would be to decide on the shard based on the last few bits of the transaction hash. For instance, if the last bit of the hash is 0, then the transaction is assigned to the first shard, else it is assigned to the second shard (assuming we have only two shards). This allows the transaction to be validated within a single shard. However, if the user is malicious, he may create another transaction with the same two inputs but a different output — yes, a double spend. The second transaction will have a different hash and, hence, the two transactions may end up in different shards. Each shard will then separately validate the received transaction while being oblivious of the double-spend transaction being validated in the other shard.
In order to prevent the double spend, the shards will have to communicate with each other while the validation is in progress. In fact, since the double-spend transaction may land in any shard, a given shard receiving a transaction will have to communicate with every other shard. The communication overhead may, in fact, defeat the entire purpose of transaction sharding.
On the other hand, the problem is much simpler to solve when we have an account-based system (without smart contracts). Each transaction then will have a sender’s address and can then be assigned to a shard based on the sender’s address. This ensures that two double-spend transactions will get validated in the same shard and hence can be easily detected without any cross-shard communication.
State Sharding
With the promises of state sharding come a new set of challenges. As a matter of fact, state sharding is the most challenging of all sharding proposals so far.
Continuing with our account-based model (let us not bring in smart contracts for the moment), in a state-sharded blockchain, a specific shard will only maintain a portion of the state. For instance, if we have two shards and only two user accounts, say for Alice and Bob, respectively, then each shard will keep the balance of one single user.
Imagine that Alice creates a transaction to pay Bob. The transaction will be handled by the first shard. Once the transaction is validated, the information about Bob’s new balance must be shared with his shard. If two popular accounts are handled by different shards, then this may entail frequent cross-shard communication and state exchange. Ensuring that cross-shard communication will not outweigh the performance gains from state sharding is still an open research problem.
One possible way to reduce the cross-shard communication overhead is to restrict users from making cross-shard transactions. With our example, this would mean that Alice would not be allowed to transact directly with Bob. If ever Alice has to transact with Bob, she will have to hold an account in that shard. While this does eliminate any cross-shard communication, it may limit the usability of the platform somewhat.
The second challenge with state sharding is data availability. Consider a scenario where, for some reason, a given shard is attacked and goes offline. Since the state of the system is not replicated across all shards, the network can no longer validate transactions that have dependency on the offline shard. As a result, the blockchain may become largely unusable. A solution to this problem is to maintain archival or backup nodes that can help the network troubleshoot and recover from data unavailability.
However, those nodes will then have to store the entire state of the system and hence may introduce centralization risks.
Another point to consider in any sharding mechanism (certainly not specific to state sharding) is to ensure that shards are not static for resilience against attacks and failures; the network must accept new nodes and assign them in a random manner to different shards. In other words, the network must get reshuffled once in a while.
However, reshuffling in the case of state sharding is tricky. Since each shard only maintains a portion of the state, reshuffling the network in one go may render the entire system unavailable until some synchronization is completed. To prevent outage, the network must be reshuffled gradually to ensure that every shard has enough old nodes before a node is evicted.
Similarly, once a new node joins a shard, one has to ensure that the node is given ample time to sync with the state of the shard; otherwise the incoming node will reject outright every single transaction.
Conclusion
In conclusion, sharding is definitely an exciting and promising direction for blockchains to pursue in order to solve scalability problems without compromising decentralization and transparency. However, there is no doubt that sharding, particularly state sharding, is notoriously difficult to do right both at the design level and at the implementation level.
Sharding should be handled with care. Also, more research needs to be done to establish the viability of state sharding as it may not be the silver bullet to storage problems. Researchers and developers are actively seeking alternate solutions at this moment. And perhaps, the answer is just right around the corner.
This is a guest post by Dr. Yaoqi Jia, head of technology at Zilliqa. Views expressed are his own and do not necessarily reflect those of BTC Media or Bitcoin Magazine.
- END -
我们很高兴地邀请您加入我们的社区，与技术专家、金融业者和加密数字货币爱好者们一同探讨！您可以通过以下方式关注我们的进展：
微信公众号：ZilliqaCN
Zilliqa中文社区联盟:http://www.zilliqa.com.cn
关注我们的推特：https://twitter.com/Zilliqa
通过邮箱订阅我们的新闻：http://zilliqa.us16.list-manage.com/subscribe?u=52acaef93d75cf69065e355ff&id=11f0b30bdd
关注我们的博客：https://blog.zilliqa.com/
Reddit:https://www.reddit.com/r/zilliqa
Slack：https://invite.zilliqa.com/
Gitter：https://gitter.im/Zilliqa/
网友评论