Zilliqa blog posted on October 16, 2017, translated by Rita
Join our community, ask us questions and get the latest (and hopefully the best) news!
As mentioned in our previous article, Zilliqa is a new blockchain platform that can process thousands of transactions per second, so Zilliqa has the potential to rival traditional payment methods like VISA and MasterCard. More importantly, Zilliqa’s transaction throughput increases almost linearly with the size of the network.
Starting with this article, we will step through Zilliqa’s design ideas in a series of articles. This article introduces the core idea of Zilliqa’s extensibility — Sharding. Zilliqa sharding has many layers, including network sharding, transaction sharding, and computational sharding. The most important of these is network sharding, because all other sharding mechanisms are built on top of network sharding.
So what exactly is network sharding?
In fact, network sharding (which we will refer to as sharding for short in this article) is a mechanism for dividing the Zilliqa network into a series of groups with fewer nodes, each of which is called a shard. For example, when a network consists of 1000 nodes, we can divide the network into 10 shards of 100 nodes each.
The secret to Zilliqa’s true scalability is network sharding. Suppose we have a network of 1,000 nodes,
Zilliqa will automatically divide the network into 10 shards of 100 nodes each, all of which can process transactions in parallel. If each shard can process 10 different transactions per second, then all shards can process 100 transactions per second together. Because the sharding architecture processes transactions in parallel, Zilliqa’s throughput increases linearly with the size of the network.
The idea of sharding is certainly not new; in fact, it dates back to the world of databases, where it has been used to improve performance, scalability, and I/O bandwidth. However, the idea of sharding in A blockchain was first developed by members of Zilliqa’s team in 2015 in an academic paper co-authored by A
Secure Sharding Protocol For Open Blockchains (CCS 2016)
Is that it? Sounds simple enough!
While the idea sounds simple, it doesn’t work that way at work. To understand the challenges, let’s start with some of the key issues that sharding solves:
1. Sybil Resistance to witch attacks. Since Zilliqa is a public blockchain platform, anyone with a computer connected to the Internet can use it. Any public blockchain, including Zilliqa, requires a sufficient number of nodes to operate, making it difficult for a public blockchain to avoid malicious nodes. By definition, a malicious node attempts to damage the system by manipulating multiple nodes and influencing any decision process based on a plurality of nodes. These are commonly known as Sybil Attacks.
2. Create shards. Let’s assume that the witch attack problem is somehow solved, and assume that the network’s 1000 nodes are divided into 10 shards of 100 nodes each. So who decides which node gets assigned to which shard? This of course cannot be determined by a single node or set of nodes controlled by a Zilliqa team member, because if the Zilliqa team becomes malicious (hypothetically), they can compromise Zilliqa’s security by centring all the malicious nodes in a single shard. By the way, if you don’t know who is Zilliqa team members, welcome to check our team (www.zilliqa.com/team.html) link.
3. Fragment size. The question is simple, for example, can we have a small shard with 10 nodes? The answer, of course, is no! Of course it’s not that simple. In fact, if shards are small, it’s easier for an attacker to control them, and since these shards run some part of the Zilliqa protocol (such as consensus), we certainly don’t want a small shard (most likely containing only malicious nodes) to decide which transactions to accept or reject.
How does Zilliqa solve these problems?
Here is Zilliqa’s solution to these problems.
1. Prevent and control witch nodes. There are several possible ways a witch attack can be costly or difficult to carry out. For example, by requiring nodes to deposit a significant amount of money (or tokens) as collateral, or by requiring them to perform some computation-intensive task (also known as proof of work, or PoW). Zilliqa uses PoW. Each new node wishing to join Zilliqa’s network must first perform PoW, and existing nodes in the network verify the PoW of the new node and authorize it to join the network. PoW is the equivalent of a ticket to the Zilliqa network, and only nodes with valid tickets can join the network. PoW makes it difficult for any real-world individual to manipulate many nodes.
2. Automatically create shards. Using PoW in Zilliqa automatically provides a way to create shards: Zilliqa first elects a set of dedicated nodes of the Directory Service Committee (DS Committee) based on POW, and periodically removes one old DS committee member and adds a new one, in a specific interval known as the DS-Epoch. In this process, Zilliqa uses a first-in, first-out strategy, and the nodes that are new to the committee are the fastest to resolve the PoW, so the size of the DS committee is fixed at all times. Once the DS committee is elected, sharding is initiated, and all other nodes in the network immediately execute another PoW, whose PoW is verified by the DS Committee, and each node is assigned to a particular shard based on submission and randomness. The last few binary digits submitted by the PoW determine which shard the node will be assigned to.
3, choose the right size. Choosing the appropriate fragment size is very important for system security. Because the submitted PoW is generated using a hash function, creating a shard using the PoW is equivalent to sampling a node-set randomly and indiscriminately. The figure below shows the probability that at least one-third of the members of different shard sizes are malicious. Note that this probability is about 0.04 if the shard size is 100. Since we want to have an absolute majority of good nodes (for later consensus), 100 as a shard size is obviously not safe. The good news is that this probability decreases as the shard size increases. Starting with 600 nodes, the probability drops to one in a million. For this reason, Zilliqa thinks the minimum shard size is 600.
Probability table of malicious nodes in at least one-third of a given size shard.
Since we want to limit the number of malicious nodes, the smaller the probability, the safer Zilliqa will be. For sharding sizes of 100 nodes, this possibility is quite high.
In Zilliqa, we chose a shard size of 600, which has a one-in-a-million chance of containing one-third of the malicious nodes.
If you’d like to know how we calculated these probabilities, please read our fragmented paper at dl.acm.org/citation.cf… .
What does sharding bring?
As discussed at the beginning of this article, network sharding opens up new avenues for parallel processing of transactions — each shard can now process transactions independently, resulting in high throughput. In fact, every time a transaction arrives on the network, it is assigned to a particular shard. Allocation is determined by the first few binary digits of the address where the transaction is sent, which is called transaction sharding.
Sharding also makes computing execution and smart contract running very efficient. For example, some shards can act as mapper and others can act as reducers and very effectively perform map-reduce tasks, also known as computational shards.
conclusion
In fact, there can still be malicious nodes in sharding, because any malicious node (like an honest node) can do a PoW and join the network. It is therefore critical that, despite the limited number of malicious nodes in the shard, the shard must be able to agree on a new set of transactions and propose the next block.
How Zilliqa uses this sharding architecture to build secure and efficient consensus protocols is the subject of the next installment in this series.
We are happy to invite you to join our community and discuss with technologists, financiers, and cryptocurrency enthusiasts! You can follow our progress in the following ways:
Weibo: weibo.com/zilliqa
Wechat official account: ZilliqaCN
Zilliqa Chinese Community Alliance: www.zilliqa.com.cn
Follow us on Twitter at twitter.com/Zilliqa
Subscribe to our news via email: zilliqa.us16.list-manage.com/subscribe?u…
Follow our blog at blog.zilliqa.com/
Reddit:www.reddit.com/r/zilliqa
Slack：invite.zilliqa.com/
Gitter: Gitter. Im/Zilliqa /
Telegraph group: T. me/ Zilliqachat