Vitalik: Fragmentation + Data Availability Sampling
Author | Vitalik Buterin
Author | Vitalik Buterin"In addition to Proof of Stake, another significant change in the design of eth2 is sharding. This proposal introduces a limited form of sharding, "data sharding", based on"A rollup-centric roadmap
In order to avoid the burden of nodes downloading all the data themselves, these two techniques can be superimposed on each other to verify the availability of large amounts of data: 1) Proof by a randomly sampled committee; 2) Data availability sampling (data availability sampling, DAS) .
first level title
Vernacular "random sampling committee"
Let's say you have a lot of data, say 16 MB, this is how much the eth2 chain (at least initially) can handle per slot. We represent this data as 64 blobs, each of size 256 kB. Suppose we also have a PoS system with around 6400 validators. How do we verify this data without 1) requiring anyone to download all of it, and 2) not giving an attacker running a handful of validators an opportunity?
The first problem, we can solve by division of labor: verifiers 1-100 need to download and verify the first blob, verifiers 101-200 download and verify the second blob, and so on. The validators in each sub-set (committee) only need to sign to prove that they have verified the corresponding blob, and then the entire network can accept the blob after receiving the signature of the majority of validators in the corresponding committee.
But this leads to a problem: what if an attacker takes control of a contiguous set of validators (e.g. 1971-2070)? If this is the case, even if the attacker controls only about 1.5% of the entire validator set, they can control a single committee (in the above case, they can control 70% of validators 2001-2100 in committee 20), so the attack The operator is able to add invalid/unusable blobs to the chain.
The RNG (Random Number Generator) is seeded after validators deposit, and each validator's index is fixed, so an attacker cannot try to get all validators into the same committee. An attacker might get lucky, but only if they control more than 1/3 of all validators.
first level title
Vernacular "Data Availability Sampling"
In some respects, data availability sampling is the mirror image of random sampling committees. Sampling still occurs because each node ends up downloading only a fraction of all data, but the sampling happens in the client and per blob, not across blobs.
Each node (including client nodes not participating in staking) checks each blob, instead of downloading the entire blob, they privately choose N random indices from it, and then try to download data at those locations.
This mechanism is efficient because a client only needs to download a small portion of the data in each blob to verify its availability. This mechanism is also highly secure because even a 51% attacker cannot trick a client into accepting an unusable blob.
erasure coding
text
In order to avoid situations where an attacker provides 50-99% of the available data (which could cause some clients to reject a blob and then be accepted by others), we use a technique called erasure coding. . Erasure coding allows us to encode blobs in such a way that if more than half of the data in a blob has been published, anyone in the network can reconstruct and publish the remaining data.
Once the republished data has been broadcast, clients that initially rejected the blob converge to accept (note that there is no time limit for accepting a blob, each time a client receives a response for all of its sampled indices, it accepts an available blob ).
The easiest mathematical analogy to understand erasure coding is "two points are always enough to recover a line": if I have four points in the form ((1, 4), (2, 7), (3, 10), (4, 13)) to create a "file", each point is on a line, then as long as you have the coordinates of two of the points, you can reconstruct the line and calculate the remaining two points ( We assume that the x-coordinates 1, 2, 3, 4 are fixed parameters of the system, not a choice of the file creator).
Using higher order polynomials, we can extend this idea to create 3 out of 6 files, 4 out of 8 files, or generally speaking n out of 2n files if you have n out of files points, the remaining points in 2n can be calculated.
We use polynomial commitments, specifically Kate commitments rather than Merkle roots as printers for data blobs, because polynomial commitments allow us to easily prove that a given value is actually polynomial to a certain degree n in the The correct estimate at the coordinates is required. Otherwise, we would have to prove (e.g. using SNARKs) that the Merkle root encodes a low-degree polynomial, or rely on fraud proofs to broadcast if the encoding is incorrect (which adds high complexity and more synchronicity assumptions ).
first level title
Is Data Availability Sampling still needed with a committee mechanism?
If you only rely on the committee, there may be the following disadvantages:
➤ The defense is weaker in the event of a 51% attack. On current (non-scalable) blockchains, a 51% attack can only roll back transactions or censor them, and cannot add invalid blocks to the chain. Committee-based systems lose this guarantee.
What's more, it would be very difficult to effectively penalize 51% attackers, since they have only a very small amount of deposits (deposits participating in that particular committee) that can be proven to be related to malicious behavior and punished based on that.
➤ DAS is slightly easier than committee mechanisms to resist quantum attacks (may require post-quantum aggregated signatures).
first level title
Is there still a need for a committee mechanism with data availability sampling?
If only DAS is used, the following problems may arise:
➤ DAS is an untested new technology, the core of which (see here) was actually developed only last year. Therefore, it is advisable to use the committee to provide protection in the event of a DAS crash or an unexpected extension of the development time.
➤ DAS has higher latency than committees.
➤ DAS has more edge cases that committees can assist with. One example is that in a DAS-only system, it is difficult to avoid the beacon block proposer being the first to initiate a DAS request to verify blob availability.
This increases the risk of an attacker publishing an unusable blob and responding only to the proposer's request. This will not cause other nodes of the network to accept unusable blobs, but may make other attacks easier, causing beacon blocks built by honest proposers to be rejected and forked from the main chain. The Commission can remedy this.
➤ The forward compatibility of the committee mechanism is stronger, making it possible to add execution functions to shards in the future.
The importance of data availability? What is the challenge?
This has been discussed elsewhere so I won't post it here, but I recommend reading:
➤A note on data availability and erasure coding (initial introduction to data availability)
➤ A paper by Alberto Sonnino, Mustafa Al-Bassam, and Vitalik Buterin expands on the concept
➤ The Dawn of Hybrid Layer 2 Protocols discusses game theory in data availability
➤ Base Layers and Functionality Escape Velocity, based on the above concepts, the data scalability part is described
➤ The Data Availability Problem (Ethereum Silicon Valley Meetup), a video discussion on the data availability problem
To be clear, BitTorrent and IPFS and similar systems do not solve the data availability problem. Although BitTorrent is a good scalable data distribution technology, it cannot reach a consensus on whether data is available, which provides the possibility of an "extreme case" attack. When a piece of data is released, nodes may Disagreement occurs, making the hybrid Layer 2 protocol ineffective. In order to reach consensus on data availability, the more robust techniques described in this document need to be used.
How does sharding work on the P2P layer?
In order to achieve the scalability purpose of sharding, we need a P2P system so that every node does not need to download all the data. Fortunately we already have a form of P2P layer sharding in Phase 0. Specifically, 64 subsets have been used to demonstrate aggregation. Each validator only needs to exist in the main "global subnet" and their own attestation aggregation subnet, without fetching any data from the other 63 aggregate attestation subsets.
In the committee + DAS type sharding, we extend it to a "grid" architecture, with 2048 horizontal subnets (horizontal subnets), that is, there is a subset in each shard-slot pair of each epoch, And 2048 vertical subnets (vertical subnets), that is, there is a subset of each index in each blob.
In each slot, we elect a proposer per shard. Each proposer has the right to propose a blob: an arbitrary block of data up to 512 kB (which we can understand as a collection of "samples" of about 512 bytes), with erasure coding extensions and additional proofs that Each part in the blob is verified independently.
Structure of a blob The structure of a blob
The "body" structure of a blob consists of the original data, the extension data, and the proof (if desired, the extension data can be omitted for data efficiency, since each node receiving the blob can reconstruct it relatively quickly).
A blob's "header" contains its corresponding Kate commitment, along with some other data (slot, shard, and proof of length) and the proposer's signature.
Blob Broadcasting Process
When a blob is broadcast, its header is broadcast to the global subnet, and the body is broadcast to the horizontal subnet corresponding to the slot and shard ID.
In practice, there will be 2048 horizontal subnets, so that there is one horizontal subnet for each shard-slot pair in each epoch. This is done to ensure that each validator can join a horizontal subnet, and they will only receive blobs corresponding to their committee (excluding the small number of vertical subnets they participate in sampling).
Each validator needs to join the following subnets:
➤ Global subnet
➤ A vertical subnet, corresponding to the index it is assigned to (computed using a private seed per validator)
broadcast block
text
A blob proposer can distribute samples to all subnets, but does not have to be part of a subnet. The process is as follows:
➤ Publication: The proposer publishes the blob in the correct horizontal subnetwork, each sample comes with a proof
➤ Direct sample distribution: other participants in the horizontal subnet publish blocks to each vertical subnet they are in
➤ Indirect sample distribution: The proposer announces to peers several vertical subnets it is in. Thus, each participant in the horizontal subnetwork can also see the vertical subnetwork its peers are in, and broadcast the corresponding block to those peers
Assuming a data block size of 512 bytes and a data blob maximum of 512 kB (excluding erasure coding), which is about 1 MB when erasure coding is included, there are 2048 vertical subnets. If each node exists in 15 private vertical subnets, 5 public vertical subnets and has 50 peers, assuming worst case 128 members in each horizontal subnet (committee only), then Subnet members alone will be directly distributed to 128 * 20 = 2560 subnets (approx. 1461 after removing redundant publishing), and if peer nodes are added, it will increase to 128 * 4 * 50 = 25600 subnets.
Note that it is theoretically possible for malicious block proposers to publish samples to vertical subnets without publishing full blocks. To address this situation, we added a process where incompletely published blocks (meaning 50% and above available, but not 100% available) are able to "self-heal". The process consists of three basic steps:
1. Reverse distribution: Same distribution process as above, except in this case peers on a vertical subnet propagate the sample from that vertical subnet to the horizontal subnet corresponding to the blob to which the sample belongs.
3. Distribution: Repeat the above distribution steps
first level title
How does the beacon chain work?
In each slot, we randomly select a proposer for each of the 64 shards. The proposer has the right to create a shard blob, broadcast it through the above process, and broadcast the ShardHeader of the blob to the global subnet. ShardHeader can be packaged into the same slot on the beacon chain, and can also be included in any subsequent slot in the same/next epoch.
The beacon chain keeps track of the list of PendingShardHeader objects. The PendingShardHeader stores: 1) key information in the ShardHeader (shards and slots, the blob's commitment and its length); 2) a bitfield that tracks which validators in a randomly selected committee signed the blob (actually, the phase 0 already introduced committees). The AttestationData structure is extended to include a shard_header_root, the root hash of the ShardHeader on which validators are selected to vote. Provers can also vote on an empty root hash if they do not see a valid and usable shard blob that has been assigned to their shard-slot pair.
If the ShardHeader is attested by 2/3 of the validators in the committee, it will be confirmed immediately. If at the end of the next epoch the shardheader has more support from the committee than any other shardheader, it is confirmed at the end of that epoch.
Fork Choice Rules
The fork selection rules were changed so that a block is only valid if all blobs or their ancestors are confirmed in that block to pass availability checks. This is called tight coupling: if a chain points to (acknowledged) an invalid blob, the entire chain is considered invalid. This is the main difference from the "sidechain" structure: in a sidechain, the sidechain can fail while the mainchain remains valid.
Here's a further exploration of tight coupling and why it's valuable.
When the number of validators is low
If there are less than 262144 validators (32 slots * 64 shards * 128 minimum committee size), then instead of choosing a proposer for all shards, we choose a proposer for a limited subset and loop through the shards. piece. For example, if there are 32 * 128 * 50 validators, and the starting shard at slot N is 0, then slot N will assign a proposer to shards 0-49, and slot N+1 will assign a proposer to shards 50- Shards 63 and 0-35 will assign a proposer, slot N+2 will assign proposers to shards 36-63 and 0-21, and so on. This is done to ensure that even when participation is low, the size of the committee remains adequate.
Added a mechanism similar to EIP-1559, billing shard data by byte, and adjusted the price: if the average capacity of the block exceeds 50%, the fee will be increased, and vice versa. Therefore, the indicator is 50% of the average block size.
first level title
security assumption
Data blob-only sharding is powerful because it relies less on safety assumptions than other sharding schemes. In particular it avoids honest majority assumptions (since DAS can detect unusable blobs issued by a majority) and timing assumptions (which, unlike earlier DAS mechanisms, use Kate commitments rather than fraud proofs and thus do not rely on on the assumption that fraud proofs need to be broadcast extremely quickly).
The main new assumption is the "honest minority DAS assumption": there is a sufficiently large sample of nodes that an attacker must publish more than half of the block. If there are 2048 samples in a blob, 1024 samples need to be recovered (considering that some clients will sample the same points, so 2048 * ln(2) ~= 1419), and each client does 20 samples, the system can be considered secure if approximately more than 70 clients per shard are sampling.
first level title
The sharding design that only supports data blobs is forward compatible with many scenarios that add execution in sharding in the future. In particular, we can modify the scheme so that the blob contains pre- and post-state roots, and we can also use fraud proofs or ZK-SNARKs to verify that the state transitions in the blob are correct. Note that no matter which approach is chosen, ensuring the correctness of sharding execution does not depend on any honest majority assumption.
Official Account: ETH Chinese Station
other resources
Protolambda’s work-in-progress implementation
Original link:https://hackmd.io/@HWeNw8hNRimMm2m2GH56Cw/sharding_proposal
ECN's translation work aims to deliver high-quality information and learning resources for the Chinese Ethereum community. The copyright of the article belongs to the original author, and the source of the original text and the ETH Chinese website must be indicated when reprinting. For long-term reprinting, please contact eth@ecn.co for authorization.
Official Account: ETH Chinese Station
Website: ethereum.cn
