What is “Danksharding”?

On the evening of Valentine’s Day, February 14th, Beijing time, Ethereum founder Vitalik Buterin and Ethereum Foundation (EF) researcher Dankrad Feist held an educational seminar on the expansion solution “Danksharding”. If you want to understand how blockchain can achieve large-scale expansion while increasing the properties of “decentralization” and “security”, then this seminar is a good starting point.

Note: Regarding the significance of “Danksharding” to Ethereum, it is recommended that readers first read the article “Understanding Ethereum’s “Scaling Killer” Danksharding in One Article”.

The following content comes from the "Dude, what's the Danksharding situation‌ ? " PPT provided by Dankrad Feist. If you want to watch the full seminar video, you can visit the official youtube channel of the Ethereum Foundation‌.

Overview

1. What is old:

(1) Data sharding;

(2) Use the data availability promised by KZG;

(3) Use a separate sharding scheme to shard the original data;

2. What's new:

(1) Proposer-Builder (Data Generator) Separation (PBS);

(2) crList;

(3) 2D solution;

(4) Recommended architecture

3. Summarize the advantages and disadvantages

What is old

Data Sharding

Providing data availability (DA) for Rollup and other scaling solutions;

The meaning of the data is defined by the application layer;

1. Ethereum’s underlying consensus (full nodes and validators) bears no responsibility other than ensuring data is available;

2. Why is there no sharding? Compared to native execution, rollup layer 2 networks are 100 times more efficient, so it is hard to see why there would be a need for sharding;

Goal: Provide a data availability layer of approximately 1.3 MB/s and full sharding capabilities (10 times the current maximum data capacity and 200 times the normal capacity);

Data sharding has been a goal of Ethereum since late 2019;

Data availability sampling (DA sampling)

Want to know that O(n) data obtained through O(1) work is available;

Idea: Distribute data into n chunks;

Each node downloads k (randomly selected) chunks;

Erasure coding

1. Expand the data using Reed-Solomon coding (polynomial interpolation);

2. For example, at the coding rate r = 0.5, this means that any 50% of the blocks (d0 to e4) are sufficient to reconstruct the entire data;

3. Sampling is now efficient (e.g., querying 30 random blocks, if all are available, the probability that more than 50% are unavailable is 2 ^ (-30))

4. However, we need to make sure the encoding is correct;

KZG Commitments

Polynomial

Commitment C(f)

Evaluate y = f(z)

1. The prover can compute and prove π(f,z)

2. Using C(f), π(f,z), y and z, the verifier can confirm that f(z) = y

C(f) and π(f,z) are elliptic curve elements (48 bytes each)

KZG promises to serve as the root of data availability

Think of a “KZG root” as something like a Merkle root;

The difference is that the "KZG root" commits to a "polynomial" (all points are guaranteed to be on the same polynomial, while the Merkle root cannot guarantee this);

Split Sharding Proposal

what's new

Proposer-Builder (Data Generator) Separation (PBS)

Invented to counter the centralization trend caused by MEV;

MEV means that more sophisticated participants can extract more value than regular validators, which means advantages for large mining pools;

PBS “contains” this complexity/centralization in a separate role with an honest minority of assumptions;

1. Proposer = Validator, the honest majority assumption means a high degree of decentralization requirement;

2. Data Generator (Builder) = Single role, honest minority assumption, meaning decentralization only requires ensuring an honest (non-censorship) data generator;

Censorship Resistance Program – crList

1. Dangers of PBS: an efficient Builder can permanently censor some transactions (at a certain economic cost);

2. [Note: In today’s bribery model, the cost of censoring a transaction is the cost of permanently bribing all proposers not to include the transaction;]

3. crLists allows the proposer to specify a list of txs that the builder must include in order to restore the old balance;

crList (“hybrid PBS” design)

KZG 2d Solution

Why not encode everything in the KZG commitment?

1. A supernode (“builder”) is needed to build and rebuild in case of failure;

2. We wish to avoid this assumption of validity;

Goal: Encode m shard blobs in d KZG commitments;

1. If we do this naively, we would need m * k samples, which is too much data;

2. Instead, we can use Reed-Solomon encoding again to expand the m commitments to 2*m commitments;

KZG 2d scheme properties

All samples can be verified directly against the promises (no fraud proofs!);

A constant number of samples ensures probabilistic data availability;

If 75%+1 samples are available:

1. All data is available;

2. It can be reconstructed from a validator that only observes rows and columns;

3. There is no need for nodes to observe all situations;

The combination is Danksharding

The execution block and the shard block are built together;

1. We previously needed shard committees because each shard blob might not be usable individually;

2. Now, it is the responsibility of the data producer to make the execution block valid and all shard blobs available;

⇒ Validation can be aggregated;

Danksharding Honest Majority Verification

Each validator chooses s = 2 random rows and columns;

Only prove whether the assigned row/column is available for the entire epoch period;

An unavailable block (<75% available) cannot obtain more than 2^(-2s) = 1/16 proofs;

Danksharding Refactoring

Each validator should reconstruct any incomplete rows/columns they encounter;

In doing so, they should shift the missing samples to the orthogonal lines;

Each validator can transfer 4 missing samples between rows/columns (about 55,000 online validators to guarantee full reconstruction)

Danksharding DA sampling (Malicious Majority Safe)

Future upgrades

Each full node checks 75 random samples on the block matrix;

This ensures that the probability of an unavailable block passing is < 2^(-30);

Bandwidth 75*512 B / 16s = 2.5 kb/s;

Summarize the advantages and disadvantages

advantage

Simple Design:

1. No shard committee infrastructure is required;

2. No need to track shard blob confirmations;

3. No additional builder infrastructure (synchronous payments from the execution layer replace this)

4. Existing execution-level fee market infrastructure can be used;

Tight coupling between execution chains and shards:

1. Makes rollup design simpler;

2. Synchronous calls between zkRollup and the execution chain are possible;

The slices do not require separate PBS;

Increased resistance to bribery as data is immediately confirmed by 1/32 of the validator set (instead of 1/2048 in the old sharding scheme) and increases to the full validator set within one epoch.

Thanks to the 2d scheme, a full node (without running a validator) will be able to ensure data availability with 75 samples (2.5 kb/s) instead of 30*64=1920 samples (60 kb/s);

New challenges

Added data generator requirements:

1. Construct a KZG proof for 32MB of data (requires 100 cores, but CPU implementation is currently being researched)

2. A 2.5 GBit/s internet connection is required to distribute the samples;

Provides more power to data generators as they act as execution + data layer service providers;

1. Need to be mitigated by crList;