Demystifying the Technical Properties of Sharding: Why it is Great

Special thanks to Dankrad Feist and Aditya Asgaonkar for review Sharding is the future of Ethereum scalability, and it will be key to helping the ecosystem support many thousands of transactions per second and allowing large portions of the world to regularly use the platform at an affordable cost. However, it is also one of the more misunderstood concepts in the Ethereum ecosystem and in blockchain ecosystems more broadly. It refers to a very specific set of ideas with very specific properties, but it often gets conflated with techniques that have very different and often much weaker security properties. The purpose of this post will be to explain exactly what specific properties sharding provides, how it differs from other technologies that are sharding, and what sacrifices a sharded system has to make to achieve these properties. not The Scalability Trilemma The best way to describe sharding starts from the problem statement that shaped and inspired the solution: . the Scalability Trilemma The scalability trilemma says that there are three properties that a blockchain try to have, and that, . The three properties are: if you stick to "simple" techniques, you can only get two of those three : the chain can process more transactions than a single regular node (think: a consumer laptop) can verify. Scalability : the chain can run without any trust dependencies on a small group of large centralized actors. This is typically interpreted to mean that there should not be any trust (or even honest-majority assumption) of a set of nodes that you cannot join with just a consumer laptop. Decentralization : the chain can resist a large percentage of participating nodes trying to attack it (ideally 50%; anything above 25% is fine, 5% is definitely fine). Security not Now we can look at the three classes of "easy solutions" that only get two of the three: - including Bitcoin, pre-PoS/sharding Ethereum, Litecoin, and other similar chains. These rely on every participant running a full node that verifies every transaction, and so they have decentralization and security, but not scalability. Traditional blockchains - including the DPoS family but also many others. These rely on a small number of nodes (often 10-100) maintaining consensus among themselves, with users having to trust a majority of these nodes. This is scalable and secure (using the definitions above), but it is not decentralized. High-TPS chains - this refers to the general concept of "scaling out" by having different applications live on different chains and using cross-chain-communication protocols to talk between them. This is decentralized and scalable, but it is not secure, because an attacker need only get a consensus node majority in one of the many chains (so often <1% of the whole ecosystem) to break that chain and possibly cause ripple effects that cause great damage to applications in other chains. Multi-chain ecosystems A sharded blockchain is: Sharding is a technique that gets you all three. : it can process far more transactions than a single node Scalable : it can survive entirely on consumer laptops, with no dependency on "supernodes" whatsoever Decentralized : an attacker can't target a small part of the system with a small number of resources; they can only try to dominate and attack the whole thing Secure The rest of the post will be describing how sharded blockchains manage to do this. Sharding Through Random Sampling The easiest version of sharding to understand is sharding through random sampling. Sharding through random sampling has weaker trust properties than the forms of sharding that we are building towards in the Ethereum ecosystem, but it uses simpler technology. The core idea is as follows. Suppose that you have a proof of stake chain with a large number (eg. 10000) validators, and you have a large number (eg. 100) blocks that need to be verified. No single computer is powerful enough to validate of these blocks before the next set of blocks comes in. all Hence, what we do is we . We randomly shuffle the validator list, and we assign the first 100 validators in the shuffled list to verify the first block, the second 100 validators in the shuffled list to verify the second block, etc. A randomly selected group of validators that gets assigned to verify a block (or perform some other task) is called a . randomly split up the work of doing the verification committee When a validator verifies a block, they publish a signature attesting to the fact that they did so. Everyone else, instead of verifying 100 entire blocks, now only verifies 10000 signatures - a much smaller amount of work, especially with . Instead of every block being broadcasted through the same P2P network, each block is broadcasted on a different sub-network, and nodes need only join the subnets corresponding to the blocks that they are responsible for (or are interested in for other reasons). BLS signature aggregation Consider what happens if each node's computing power increases by 2x. Because each node can now safely validate 2x more signatures, you could cut the minimum staking deposit size to support 2x more validators, and so hence you can make 200 committees instead of 100. Hence, you can verify 200 blocks per slot instead of 100. Furthermore, could be 2x bigger. Hence, you have 2x more blocks of 2x the size, or 4x more chain capacity altogether. each individual block We can introduce some math lingo to talk about what's going on. Using , we use " " to refer to the computational capacity of a single node. A traditional blockchain can process blocks of size . A sharded chain as described above can process blocks in parallel (remember, the cost to each node to verify each block indirectly is because each node only needs to verify a fixed number of signatures), and each block has capacity, and so the sharded chain's total capacity is . This is why we call this type of sharding , and this effect is a key reason why we think that in the long run, sharding is the best way to scale a blockchain. Big O notation O(C) O(C) O(C) O(1) O(C) O(C2) quadratic sharding Frequently Asked Question: How is Splitting into 100 Committees Different From Splitting into 100 Separate Chains? There are two key differences: . In a 100-chain multichain ecosystem, the attacker only needs ~0.5% of the total stake to wreak havoc: they can focus on 51% attacking a single chain. In a sharded blockchain, the attacker must have close to ~30-40% of the stake to do the same (in other words, the chain has ). Certainly, they can wait until they get lucky and get 51% in a single shard by random chance despite having less than 50% of the total stake, but this gets exponentially harder for attackers that have much less than 51%. If an attacker has less than ~30%, it's virtually impossible. The random sampling prevents the attacker from concentrating their power on one shard entire shared security There is a social contract (and in later sections of this document we describe some ways to enforce this technologically) that a chain with even one bad block in even one shard is not acceptable and should get thrown out as soon as it is discovered. This ensures that from the point of view of an application the chain, there is perfect security: contract A can rely on contract B, because if contract B misbehaves due to an attack on the chain, that entire history reverts, including the transactions in contract A that misbehaved as a result of the malfunction in contract B. Tight coupling: if even one shard gets a bad block, the entire chain reorgs to avoid it. within Both of these differences ensure that sharding creates an environment for applications that preserves the key safety properties of a single-chain environment, in a way that multichain ecosystems fundamentally do not. Improving Sharding With Better Security Models One common refrain in Bitcoin circles, and one that I completely agree with, is that . If there is a 51% attack on such a blockchain, then the attacker can do nasty things, like reverting or censoring transactions, but they cannot insert invalid transactions. And even if they do revert or censor transactions, users running regular nodes could easily detect that behavior, so if the community wishes to coordinate to resolve the attack with a fork that takes away the attacker's power they could do so quickly. blockchains like Bitcoin (or Ethereum) do NOT completely rely on an honest majority assumption some . Such chains do not, and cannot, have a culture of regular users running nodes, and so the major nodes and ecosystem players can much more easily get together and impose a protocol change that the community heavily dislikes. Even worse, the users' nodes would by default accept it. After some time, users would notice, but by then the forced protocol change would be a fait accompli: to reject the change, and they would have to make the painful decision to revert a day's worth or more of activity that everyone had thought was already finalized. The lack of this extra security is a key weakness of the more centralized high-TPS chains the coordination burden would be on users Ideally, we want to have a form of sharding that avoids 51% trust assumptions for validity, and preserves the powerful bulwark of security that traditional blockchains get from full verification. And this is exactly what much of our research over the last few years has been about. Scalable Verification of Computation We can break up the 51%-attack-proof scalable validation problem into two cases: : checking that some computation was done correctly, assuming you have possession of all the inputs to the computation. Validating computation : checking that the inputs to the computation themselves are stored in some form where you can download them if you really need to; this checking should be performed actually downloading the entire inputs themselves (because the data could be too large to download for every block). Validating data availability without Validating a block in a blockchain involves both computation and data availability checking: you need to be convinced that the transactions in the block are valid and that the new state root hash claimed in the block is the correct result of executing those transactions, but you also need to be convinced that enough data from the block was actually published so that users who download that data can compute the state and continue processing the blockchain. This second part is a very subtle but important concept called the ; more on this later. data availability problem Scalably validating computation is relatively easy; there are two families of techniques: and . fraud proofs ZK-SNARKs The two technologies can be described simply as follows: are a system where to accept the result of a computation, you require someone with a staked to sign a message of the form "I certify that if you make computation with input , you get output ". You trust these messages by default, but you leave open the opportunity for someone else with a staked deposit to make a (a signed message saying "I disagree, the output is Z"). Only when there is a challenge, all nodes run the computation. Whichever of the two parties was wrong loses their deposit, and all computations that depend on the result of that computation are recomputed. Fraud proofs deposit C X Y challenge are a form of proof that directly proves the claim "performing computation on input gives output ". The proof is cryptographically "sound": if does equal , it's computationally infeasible to make a valid proof. The proof is also quick to verify, even if running itself takes a huge amount of time. See for more mathematical details on ZK-SNARKs. ZK-SNARKs cryptographic C X Y C(x) not Y C this post Computation based on fraud proofs is scalable because "in the normal case" you replace running a complex computation with verifying a single signature. There is the exceptional case, where you do have to verify the computation on-chain because there is a challenge, but the exceptional case is very rare because triggering it is very expensive (either the original claimer or the challenger loses a large deposit). ZK-SNARKs are conceptually simpler - they just replace a computation with a much cheaper proof verification - but the math behind how they work is considerably more complex. There is a class of semi-scalable system which scalably verifies computation, while still requiring every node to verify all the data. This can be made quite effective by using a set of compression tricks to replace most data with computation. This is the realm of . only rollups Scalable Verification of Data Availability is Harder A fraud-proof cannot be used to verify the availability of data. Fraud proofs for rely on the fact that the inputs to the computation are published on-chain the moment the original claim is submitted, and so if someone challenges, the challenge execution is happening in the exact same "environment" that the original execution was happening. In the case of checking data availability, you cannot do this, because the problem is precisely the fact that there is too much data to check to publish it on chain. Hence, a fraud-proof scheme for data availability runs into a key problem: someone could claim "data X is available" without publishing it, wait to get challenged, and only publish data X and make the challenger appear to the rest of the network to be incorrect. computation then This is expanded on in : the fisherman's dilemma The core idea is that the two "worlds", one where V1 is an evil publisher and V2 is an honest challenger and the other where V1 is an honest publisher and V2 is an evil challenger, are indistinguishable to anyone who was not trying to download that particular piece of data at the time. And of course, in a scalable decentralized blockchain, each individual node can only hope to download a small portion of the data, so only a small portion of nodes would see anything about what went on except for the mere fact that there was a disagreement. The fact that it is impossible to distinguish who was right and who was wrong makes it impossible to have a working fraud-proof scheme for data availability. Frequently asked question: so what if some data is unavailable? With a ZK-SNARK you can be sure everything is , and isn't that enough? valid Unfortunately, mere validity is not sufficient to ensure a correctly running blockchain. This is because if the blockchain is but all the data is not , then users have no way of updating the data that they need to generate proofs that any block is valid. An attacker that generates a valid-but-unavailable block but then disappears can effectively stall the chain. Someone could also withhold a specific user's account data until the user pays a ransom, so the problem is not purely a liveness issue. valid available future There are some strong information-theoretic arguments that this problem is fundamental, and there is no clever trick (eg. involving ) that can get around it. See for details. cryptographic accumulators this paper So, how do you check that 1 MB of data is available without actually trying to download it? That sounds impossible! The key is a technology called . Data availability sampling works as follows: data availability sampling Use a tool called to expand a piece of data with N chunks into a piece of data with 2N chunks such that of those chunks can recover the entire data. erasure coding any N To check for availability, instead of trying to download the data, users simply (eg. 30 positions), and accept the block only when they have successfully found the chunks in the block at of their selected positions. entire randomly select a constant number of positions in the block all Erasure codes transform a "check for 100% availability" (every single piece of data is available) problem into a "check for 50% availability" (at least half of the pieces are available) problem. Random sampling solves the 50% availability problem. If less than 50% of the data is available, then at least one of the checks will almost certainly fail, and if at least 50% of the data is available then, while some nodes may fail to recognize a block as available, it takes only one honest node to run the erasure code reconstruction procedure to bring back the remaining 50% of the block. And so, instead of needing to download 1 MB to check the availability of a 1 MB block, you need only download a few kilobytes. This makes it feasible to run data availability checking on block. See for how this checking can be efficiently implemented with peer-to-peer subnets. every this post A ZK-SNARK can be used to verify that the erasure coding on a piece of data was done , and then Merkle branches can be used to verify individual chunks. Alternatively, you can use (eg. ), which essentially do erasure coding proving individual elements correctness verification all in one simple component - and that's what Ethereum sharding is using. correctly polynomial commitments Kate (aka KZG) commitments and and Recap: How are we Ensuring Everything is Correct Again? Suppose that you have 100 blocks and you want to efficiently verify correctness for all of them without relying on committees. We need to do the following: Each client performs on each block, verifying that the data in each block is available, while downloading only a few kilobytes per block even if the block as a whole is a megabyte or larger in size. A client only accepts a block when all data of their availability challenges have been correctly responded to. data availability sampling Now that we have verified data availability, it becomes easier to verify correctness. There are two techniques: We can use : a few participants with staked deposits can sign off on each block's correctness. Other nodes, called (or ) randomly check and attempt to fully process blocks. Because we already checked data availability, it will always be possible to download the data and fully process any particular block. If they find an invalid block, they post a that everyone verifies. If the block turns out to be bad, then that block and all future blocks that depend on that need to be re-computed. fraud proofs challengers fishermen challenge We can use . Each block would come with a ZK-SNARK proving correctness. ZK-SNARKs In either of the above cases, each client only needs to do a small amount of verification work per block, no matter how big the block is. In the case of fraud proofs, occasionally blocks will need to be fully verified on-chain, but this should be extremely rare because triggering even one challenge is very expensive. And that's all there is to it! In the case of Ethereum sharding, the near-term plan is to make sharded blocks ; that is, the shards are a "data availability engine", and it's the job of to use that secure data space, plus either fraud proofs or ZK-SNARKs, to implement high-throughput secure transaction processing capabilities. However, it's completely possible to create such a built-in system to add "native" high-throughput execution. data-only purely layer-2 rollups What are the Key Properties of Sharded Systems and What are the Tradeoffs? The key goal of sharding is to come as close as possible to replicating the most important security properties of traditional (non-sharded) blockchains but without the need for each node to personally verify each transaction. Sharding comes quite close. In a traditional blockchain: because validating nodes notice that they are invalid and ignore them. Invalid blocks cannot get through because validating nodes fail to download them and ignore them. Unavailable blocks cannot get through In a sharded blockchain with advanced security features: because either: Invalid blocks cannot get through A fraud proof quickly catches them and informs the entire network of the block's incorrectness, and heavily penalizes the creator, or A ZK-SNARK proves correctness, and you cannot make a valid ZK-SNARK for an invalid block. because: Unavailable blocks cannot get through If less than 50% of a block's data is available, at least one data availability sample check will almost certainly fail for each client, causing the client to reject the block, If at least 50% of a block's data is available, then actually the entire block is available, because it takes only a single honest node to reconstruct the rest of the block. Traditional high-TPS chains without sharding do not have a way of providing these guarantees. Multichain ecosystems do not have a way of avoiding the problem of an attacker selecting one chain for attack and easily taking it over (the chains share security, but if this was done poorly it would turn into a de-facto traditional high-TPS chain with all its disadvantages, and if it was done well, it would just be a more complicated implementation of the above sharding techniques). could are highly implementation-dependent, but they are typically vulnerable to either the weaknesses of traditional high-TPS chains (this is if they share miners/validators), or the weaknesses of multichain ecosystems (this is if they do not share miners/validators). Sharded chains avoid these issues. Sidechains . Notably: However, there are some chinks in the sharded system's armor . That is, if the adversary has the ability to hack into (or just shut down) any set of nodes of their choosing in real time, then they only need to attack a small number of nodes to break a single committee. Furthermore, if an adversary (whether an adaptive adversary or just an attacker with 50% of the total stake) does break a single committee, only a few of their nodes (the ones in that committee) can be publicly confirmed to be participating in that attack, and so only a small amount of stake can be penalized. This is another key reason why data availability sampling together with either fraud proofs or ZK-SNARKs are an important complement to random sampling techniques. Sharded chains that rely on committees are vulnerable to adaptive adversaries and have weaker accountability only that they collectively make enough data availability sampling requests that the responses almost always overlap to comprise at least 50% of the block. In practice, this means that (and this number increases the higher the ratio of the capacity of the system to the capacity of a single node). This is a - generally quite trustworthy, but certainly not as robust as the 0-of-N trust that nodes in non-sharded chains have for availability. Data availability sampling is only secure if there is a sufficient number of online clients there must be a few hundred clients online few-of-N trust model ; if the network is too slow, nodes could accept a block as finalized before the fraud-proof comes in showing that it is wrong. Fortunately, if you follow a strict rule of reverting all invalid blocks once the invalidity is discovered, this threshold is a user-set parameter: each individual user chooses how long they wait until finality and if they didn't want long enough then suffer, but more careful users are safe. Even still, this is a weakening of the user experience. If the sharded chain relies on fraud proofs, then it relies on timing assumptions Using ZK-SNARKs to verify validity solves this. , increasing the risk of failures under extreme networking conditions. Small amounts of data are easier to send (and easier to , if a powerful government attempts to censor the chain) than larger amounts of data. Block explorers need to store more data if they want to hold the entire chain. There is a much larger amount of raw data that needs to be passed around safely hide Sharded blockchains depend on sharded peer-to-peer networks, and . The mitigates this because there is some redundancy between subnets, but even still there is a risk. each individual p2p "subnet" is easier to attack because it has fewer nodes subnet model used for data availability sampling These are valid concerns, though in our view they are far outweighed by the enabled by allowing more applications to run on-chain instead of through centralized layer-2 services. That said, these concerns, especially the last two, are in practice the real constraint on increasing a sharded chain's throughput beyond a certain point. There is a limit to the quadraticness of quadratic sharding. reduction in user-level centralization Incidentally, the growing safety risks of sharded blockchains if their throughput becomes too high are also the key reason why the effort to extend to has been largely abandoned; it looks like keeping quadratic sharding quadratic really is the happy medium. super-quadratic sharding just Why Not Centralized Production and Sharded Verification? One alternative to sharding that gets often proposed is to have a chain that is structured like a centralized high-TPS chain, except it uses data availability sampling and sharding on top to allow verification of validity and availability. This improves on centralized high-TPS chains as they exist today, but it's still considerably weaker than a sharded system. This is for a few reasons: . Censorship detection requires either (i) being able to see transaction and verify that there are no transactions that clearly deserve to get in that inexplicably fail to get in, or (ii) having a 1-of-N trust model in and verifying that no blocks fail to get in. In a centralized high-TPS chain, (i) is impossible, and (ii) is harder because the small node count makes even a 1-of-N trust model more likely to break, and if the chain has a block time that is too fast for DAS (as most centralized high-TPS chains do), it's very hard to prove that a node's blocks are not being rejected simply because they are all being published too slowly. It's much harder to detect censorship by block producers in a high-TPS chain every block producers If a majority of block producers and ecosystem members tries to force through an unpopular protocol change, users' clients will certainly it, but because they would need to spin up a new set of very expensive high-throughput nodes to maintain a chain that keeps the old rules. detect it's much harder for the community to rebel and fork away . The high throughput of the block-producing nodes makes them very detectable and easier to shut down. It's also politically and logistically easier to censor dedicated high-performance computation than it is to go after individual users' laptops. Centralized infrastructure is more vulnerable to censorship imposed by external actors , increasing the risk that the entire chain will be run within 1-3 companies' cloud services, and hence risk of the chain going down because of many block producers failing simultaneously. A sharded chain with a culture of running validators on one's own hardware is again much less vulnerable to this. There's a stronger pressure for high-performance computation to move to centralized cloud services Properly sharded systems are better as a base layer. Given a sharded base layer, you can always create a centralized-production system (eg. because you want a high-throughput domain with ) layered on top by building it as a rollup. But if you have a base layer with a dependency on centralized block production, you cannot build a more-decentralized layer 2 on top. synchronous composability for defi Also Published . Here

Demystifying the Technical Properties of Sharding: Why it is Great

Too Long; Didn't Read

Coins Mentioned

@Vitalik

RELATED STORIES