The Hitchhiker ‘s Guide to Ethereum (Part 1)

The main points

  • Ethereum is the only major protocol designed to scale and unify the settlement and data availability layers.
  • Rollups expand computing power while leveraging the security of Ethereum.
  • All roads ultimately lead to centralized block generation, decentralized and trustless block verification, and censorship resistance.
  • Innovations such as block producer-block packer separation and weak statelessness result in a separation of power (creation and verification) to achieve scalability without sacrificing security or decentralization.
  • MEV (Miner Captured Value) is now centrally important — many designs are designed to mitigate its harm and prevent its tendency to centralize.
  • Danksharding combines multiple avenues of cutting-edge research to provide the scalable base layer needed for Ethereum’s rollup-centric roadmap.
  • I do look forward to Danksharding in our lifetime.

     


introduction

I’ve been skeptical about the timing of the merger since Vitalik said that people born today have a 50-75% chance of living to 3000, and he wants to live forever. But whatever, let’s have some fun and look forward to Ethereum’s ambitious roadmap.

The Hitchhiker 's Guide to Ethereum (Part 1)

This is not a quick essay. If you want a broad yet nuanced look at Ethereum’s ambitious roadmap, give me an hour and I’ll save you months of work.

There’s a lot to like about Ethereum research, but it’s all ultimately woven into an overarching goal — scalable computing without sacrificing decentralized verification .

While the letter “C” is scary in blockchain, Vitalik still admits in his famous Endgame essay that some centralization is needed to scale. We just need to control this centralized power through decentralization and trustless verification without compromise.

Certain actors will build blocks for L1 and L1-based stuff. Ethereum maintains incredible security with simple decentralized verification, while rollups inherit their security from L1. Ethereum provides both settlement and data availability to allow rollup scaling. All of the research in this post is ultimately about optimizing the two roles of settlement and data availability, while making it easier than ever to fully verify a blockchain.

Part 1: The Road to Danksharding

Hopefully you’ve heard that Ethereum has moved to a rollup-centric roadmap, which no longer has to perform sharding, but will be optimized for rollups that require large amounts of data. This will be achieved through Ethereum’s planned data sharding or Celestia’s planned large blocks.

The consensus layer does not interpret sharded data, it has only one task, which is to ensure data availability (Data Availability).

Next I will assume that you are familiar with basic concepts like rollups, fraud proofs, zero-knowledge proofs, and assume you understand why data availability is so important.

Original data sharding design (sharding 1.0) – independent block producers

The designs described in this section no longer exist, but are still valuable content. For simplicity, this is called “Shard 1.0” .

Each of the 64 shard blocks has its own independent block producer and committee, and they are assigned to each shard block by rotation in the validator set, and they each verify that their shard data is available, so initially this Relying on an honest majority in each shard validator set to download data in its entirety is not the data availability sampling used today.

The original design brought unnecessary complexity, worse user experience, and attack methods, and it was cumbersome to rearrange (rotate) validators between shards.

Without introducing a very tight synchronization assumption, it is difficult to guarantee that voting will be done within a single time slot. Beacon Block producers need to collect votes from all independent committees, which may be delayed.

The Hitchhiker 's Guide to Ethereum (Part 1)

Unlike sharding 1.0, Danksharding is completely different. Validators do data availability sampling to confirm that all data is available (no more separate shard committees) – a dedicated creator creates a large block with beacon blocks and puts all shard data together confirm. Therefore, Proposer-builder Separation (PBS: Proposer-builder Separation) is a necessary condition for Danksharding to remain decentralized (building large blocks together takes a lot of resources).

The Hitchhiker 's Guide to Ethereum (Part 1)

Data Availability Sampling

Rollups publish a lot of data, but we don’t want it to burden nodes with downloading all the data. High resource demands hurt decentralization.

However, data availability sampling allows nodes (even light clients) to easily and securely verify that all this data is available without having to download it.

  • Naive solution: Check out a bunch of random blocks of data from the block. If there is nothing wrong with these blocks, you can check them out. But what if you missed that transaction that gave all your ETH to Sifu? Then the funds are no longer safe.
  • Clever solution: Erasure-encode the data first, expand the data with Reed-Solomon codes, ie the data is interpolated as a polynomial and then evaluated at some other location. It’s a mouthful, so let’s decipher it.

Start with a simple math lesson:

A polynomial is any finite number of

The Hitchhiker 's Guide to Ethereum (Part 1)

A summation expression of terms of the form whose order is the highest exponent, e.g.

The Hitchhiker 's Guide to Ethereum (Part 1)

. is a third-order polynomial. You can reconstruct any polynomial of order d from any polynomial containing d + 1 coordinates.

As a concrete example: we have four data blocks (

The Hitchhiker 's Guide to Ethereum (Part 1)

arrive

The Hitchhiker 's Guide to Ethereum (Part 1)

), these data blocks can be mapped to the value of the polynomial f(X) at a given point, e.g. f(0) =

The Hitchhiker 's Guide to Ethereum (Part 1)

, now you have found the smallest order polynomial running through these values, which means based on these four blocks we can get a third order polynomial. We can then add another four values ​​that lie on the same polynomial (

The Hitchhiker 's Guide to Ethereum (Part 1)

arrive

The Hitchhiker 's Guide to Ethereum (Part 1)

) to expand the data.

The Hitchhiker 's Guide to Ethereum (Part 1)

The key property of a polynomial is that we can reconstruct it through any four points, but not limited to the four blocks of data we originally used.

Now let’s go back to data availability sampling – we just need to make sure that an arbitrary 50% (4/8) of the erasure-encoded data is available so that the entire block can be reconstructed.

Because of this, an attacker would have to hide more than 50% of the blocks in order to successfully fool the data availability sampling node into thinking the data is available when it is not.

After many successful random samplings, the probability of data availability <50% is very small. If we successfully sample the erasure coded data 30 times, the probability of availability < 50% is

KZG promise

Now we’ve done a bunch of random sampling of data availability, and the data is available. But there is one more question – is the data properly erasure encoded? Otherwise, it is possible that the block generator only adds 50% of useless data when expanding the block, then our sampling is meaningless. In this case, we cannot reconstruct the data.

Often, we just commit a large amount of data by using a Merkle root, which is very efficient for proving that some data is contained within a set.

But what we also need to know is that all the original and extended data lie on the same low-order polynomial, and Merkle roots cannot prove this. So if the Merkle root scheme is used, fraud proofs are also required to prevent false validation.

The Hitchhiker 's Guide to Ethereum (Part 1)

Developers are approaching this problem in two directions:

  1. Celestia went the fraud proof route. The route needs to be observed by someone who will submit a fraud proof to alert everyone if a block is incorrectly erasure coded. This requires the standard honest-minority assumption and synchronization assumption (i.e., in addition to someone sending me a fraud proof, it needs to be assumed that I am connected to the network and will receive this fraud proof for a limited time).
  1. Ethereum and Polygon Avail are taking a new route – KZG commitments (also known as Kate commitments), which remove the need for honest minority and synchronization assumptions for fraud proof security.

Of course other solutions exist, but they are not actively used. For example, zero-knowledge proofs can be used, but are currently computationally impractical, however it is expected to be greatly improved in the next few years, so it is likely that Ethereum will move to STARKs in the future, as KZG promises not to It has the ability to resist quantum computing attacks.

The Hitchhiker 's Guide to Ethereum (Part 1)

Going back to KZG commitments, they are a polynomial commitment scheme.

A commitment scheme is just a cryptographic way of provably promising some value. The best analogy is to put a letter in a locked box and hand it to someone else. The letter will not change once it is in, but it can be opened with a key to prove that there is such a letter. You make a promise to this letter, and the key is the proof.

In our case, we map all the original and extended data onto an X,Y grid and then find the smallest order polynomial that runs through them (this process is called Lagrange interpolation). This polynomial is what the prover promises:

The Hitchhiker 's Guide to Ethereum (Part 1)

Here are the main points:

  • We have a “polynomial”  f(X)
  • The prover makes a “commit” to the polynomial  C(f) 
    • This relies on elliptic curve cryptography with trusted settings
  • For any “value”  y = f(z) of this polynomial, the prover can compute a “proof”  π(f,z)
  • Given a commitment C(f), proving that π(f,z), any position z, and the value y of the polynomial at z, the verifier can prove that indeed f(z)=y
    • That is, the prover hands these bits and pieces to an arbitrary verifier, who can verify that the value at a point (representing the source data) is correctly on the promised polynomial
    • This proves that the original data was expanded correctly, since all the values ​​lie on the same polynomial
    • Note that the verifier does not need the polynomial f(X)
  • Important properties – have O(1) commitment size, O(1) proof size, and O(1) verification time. Even for the prover, the commitment and proof generation are only O(d) (where d is the order of the polynomial).
    • That is, even if n (the number of values ​​in X) increases (i.e. the dataset grows with the size of the shard blob), the size of the promise and proof remains the same and the amount of work required to verify is constant
    • Both the commitment C(f) and the proof π(f,z) are just an elliptic curve element on the pairing friendly curve (BL12-381). In this case they are only 48 bytes each (really small)
    • So the large amount of original and extended data committed by the prover (represented as many values ​​on the polynomial) is still only 48 bytes, and the proof will be only 48 bytes too
    • All in all, is highly scalable

A KZG root (a polynomial commitment) will be similar to a Merkle root (a vector commitment):

The Hitchhiker 's Guide to Ethereum (Part 1)

The original data is the value of the polynomial f(X) at positions f(0) to f(3), which we then extend by computing the value of the polynomial at positions f(4) to f(7). All points f(0) to f(7) are guaranteed to lie on the same polynomial.

In summary, data availability sampling allows us to check that erasure-encoded data is available. The KZG promise proves to us that the original data is correctly scaled, and promises the data over all polynomials.

The Hitchhiker 's Guide to Ethereum (Part 1)

Well, that’s it for today’s algebra.

KZG Promise vs. Fraud Proof

Now that we have seen how KZG works, let’s compare the two methods.

The disadvantage of KZG is that it is not quantum resistant and requires a trusted setup. These are not worrisome, as STARKs provide a quantum-resistant alternative, whereas trusted setups (which are open to participation) only require an honest participant.

The advantage of KZG over fraud proof scenarios is that it has lower latency (GASPER will not have fast finality anyway), and it ensures that proper for erasure coding.

However, considering that Ethereum still re-introduces these assumptions in block refactorings, it does not actually eliminate the impact of these assumptions. The data availability layer, always needs to plan for the case where blocks are initially available but are then rebuilt as nodes need to communicate with each other. This refactoring requires two assumptions:

  1. There are enough (light or full) nodes sampling the data that they collectively have enough data to piece together. It’s a fairly weak, unavoidably honest minority assumption, so it’s not a big deal. 
  1. The synchronization assumption is reintroduced to enable nodes to communicate within a certain period of time in order to put this data back together.

Ethereum validators in the original Danksharding scheme (Proto) need to download the entire shard binary data block (Blob: binary large object), while in Danksharding they only perform data availability sampling (download specified rows and columns), Celestia requires validators to download the entire block.

It is important to note that refactoring in either case requires synchronization assumptions. If the block is only partially available, full nodes must communicate with other nodes to piece the block together.

If Celestia wants to move from requiring validators to download full data to only performing data availability sampling (although this transition is not currently planned), then the latency benefits of KZG will become apparent. Then they also need to fulfill the KZG commitment, because waiting for a fraud proof means that the block interval will be significantly increased, and it means that the risk of validators voting for a wrongly coded block will be particularly high.

For a deep dive into how KZG promises work, I recommend the following readings: (see link at the end of the article)

  • [1] (relatively easy to understand) Introduction to Elliptic Curve Cryptography
  • [2] Exploring Elliptic Curve Pairing – Vitalik 
  • [3] KZG Polynomial Commitment – Dankrad 
  • [4] How the trusted setup works – Vitalik 

     

In-protocol block producer-block packer separation

Block Producer-Builder Separation (PBS: Proposer-Builder Separation)

Today’s consensus nodes (miners) and merged consensus nodes (validators) serve two roles: they build blocks and then submit them to consensus nodes that will validate the blocks. Miners build on the previous block to “vote”, and after merging, validators will directly vote on whether the block is valid.

PBS splits this process, which explicitly creates a new in-protocol block packer role. Specific block packers put blocks together and bid on block producers (validators) to choose their blocks. This counters the centralized power of MEVs.

Review Vitalik’s Endgame – all roads lead to centralized block generation based on trustless and decentralized verification. PBS encodes this. We need an honest block packer to serve the liveness and censorship resistance of the network (both to maintain an efficient market), and the set of validators requires an honest majority assumption. PBS makes the role of block producers as simple as possible to support the decentralization of validators.

Block packers get preferential fee tips and can withdraw any MEV. In an efficient market, competitive block packers will bid for the full value they can extract from the block (minus their amortized costs, such as powerful hardware, etc.). All of this value permeates into a decentralized set of validators – which is exactly what we want.

The exact PBS implementation is still under discussion, but a two-slot PBS might look like this:

The Hitchhiker 's Guide to Ethereum (Part 1)

  1. The block packer commits to the block header along with his bid
  1. The beacon block producer selects the winning block header and bid, and will receive the winning bid unconditionally, even if the block packager fails to generate the block body.
  1. Witness committee confirms winning block header
  1. Block packer discloses the winning block
  1. Different committees of authenticators elect the winning block (if the winning block packer does not present the block, the vote will prove that the block does not exist)

Block producers are selected from the validator set using the standard RANDAO mechanism, followed by a commit-disclosure scheme that ensures that the full block body is not revealed until the block header is confirmed by the committee.

The commitment-disclosure scheme is more efficient (sending hundreds of full blocks may exceed the bandwidth of the p2p layer) and also prevents MEV theft. If a block packer commits their full block, another block packer can observe and figure out a strategy to merge with it, quickly publishing a better block. Also sophisticated block producers can inspect and replicate the MEV strategy used without compensating block packers. If this MEV theft becomes an equilibrium, it will incentivize block packers and block producers to merge. That’s why we avoid this with a commitment-disclosure scheme.

After the block producer has chosen the winning block header, it is confirmed by the committee and fixed in the fork choice rule. The winning block packer then publishes their winning full “block packer block” body. If the announcement is timely, the next committee will certify the “block packager block”; if the announcement is not timely, the block packager still needs to pay the full price to the block producer (and lose all MEV and fees). This unconditional payment no longer requires block producers to trust block packers.

Latency is a disadvantage of this “dual slot” design. The merged block will have a fixed 12 seconds, so if we don’t want to introduce any new assumptions here, then I need a full block time of 24 seconds (two 12 second slots). 8 seconds per slot (16 second block time) seems like a safe compromise, but research is ongoing.

Censorship Resistance List (crList)

Unfortunately, PBS enhances the ability of block packers to censor transactions. Maybe block packers just don’t like you, so they ignore your transactions; maybe they’re so good at work that other packers give up their jobs; maybe they’re going to charge a lot for blocks just because it’s really cheap do not like you.

The Hitchhiker 's Guide to Ethereum (Part 1)

The anti-censorship checklist checks these powers. The exact implementation is still an open design space, although “Hybrid PBS” seems to be the most popular, where block producers specify a list of all eligible transactions they see in the storage pool, and block packers will Force them to be included (unless the block is full):

The Hitchhiker 's Guide to Ethereum (Part 1)

  1. The block producer publishes a censorship resistant list and a summary of the censorship resistant list containing all eligible transactions
  1. Block packers create a proposed block and submit a bid that includes the hash of the censorship-resistant manifest summary to prove they have seen the proposed block
  1. The block producer accepts the bid and block header of the winning block packer (the block producer has not seen the block body at this time)
  1. Block packers publish their block and a proof that they have included all transactions in the censorship-resistant list or that the block is full, otherwise the block will not be accepted by the fork-choice rule
  1. Authenticators check the validity of the published blocks

There are still some important issues to sort out here, for example the prevailing economic strategy based on this situation is for block producers to submit an empty list so that whoever bids the highest wins, even censorship creators win bid. There are a few ideas to address this and a few others, but here’s just to stress that design isn’t set in stone.

2D KZG scheme

We already know how KZG commitments allow us to commit data and prove that it is scaled correctly, however I simplified what Ethereum actually does: a block will use many KZG commitments, since there is no way to make a single KZG commitment All data is promised in the promise.

We already have dedicated block packers, so why not just let them create a huge KZG commitment? Because this requires a powerful supernode to refactor. We can accept supernode requirements during the initial build phase, but we need to avoid refactoring assumptions. We need lower resource entities to handle refactorings, and splitting these refactorings into many KZG commitments makes it feasible. Refactoring may even be fairly common, or in a design for that given amount of data, refactoring is the base case assumption in that design.

To make refactoring easier, each block will consist of m shard blobs encoded into m KZG commitments . Although doing this would result in a lot of sampling, i.e. you would perform data availability sampling on each shard blob to know it’s all available (in m*k samples, k is the number of samples per blob).

But Ethereum will use a two-dimensional KZG scheme, again using Reed-Solomon encoding to expand m commitments to 2m commitments:

The Hitchhiker 's Guide to Ethereum (Part 1)

We make it a two-dimensional scheme by adding an additional KZG commitment (256-511 here) on top of the same polynomial as 0-255. Now we just need to perform data availability sampling on the table above to ensure that all data across shards is available.

The Hitchhiker 's Guide to Ethereum (Part 1)

Two-dimensional sampling requires ≥75% of the data to be available (instead of the previous 50%), which means more fixed sampling is required. As mentioned earlier, 30 samples of data availability sampling are required in a simple one-dimensional scheme, but 75 samples would be required in a two-dimensional scheme to ensure the same probability of reconstructing an available block.

Shard 1.0 (which has a one-dimensional KZG commitment scheme) requires only 30 samples, but if you want to check full data availability for all 1920 samples, you need to sample 64 shards, each sample is 512 B, so This is required.

(512 B x 64 shards x 30 samples) / 16 seconds = 60 KB/s bandwidth

In reality, validators are rotated and do not check all shards one by one. Now, the block combined with the two-dimensional KZG commitment scheme makes checking full data availability a breeze, requiring only 75 samples of a unified block:

(512 B x 1 block x 75 samples) / 16 seconds = 2.5 KB/s bandwidth

Posted by:CoinYuppie,Reprinted with attribution to:https://coinyuppie.com/the-hitchhiker-s-guide-to-ethereum-part-1/
Coinyuppie is an open information publishing platform, all information provided is not related to the views and positions of coinyuppie, and does not constitute any investment and financial advice. Users are expected to carefully screen and prevent risks.

Like (0)
Donate Buy me a coffee Buy me a coffee
Previous 2022-06-08 10:28
Next 2022-06-08 10:30

Related articles