Loading
Settings

PBS censorship-resistance alternatives

crLists

High-level idea:

We want to make it so proposers are able to combat censorship by forcing inclusion of some transactions, but we don’t want to do it in a way which is bandwidth-intensive (i.e. can often result in redundant gossiping and/or block inclusion of transactions), which disadvantages altruistic proposers by requiring them to sacrifice MEV or which gives sophisticated proposers some power that they can exploit to extract more MEV than unsophisticated ones. When builders are not censoring, it would be ideal if the protocol would essentially behave as in the regular PBS proposal, with the proposers just choosing the most profitable block, and minimal overhead

The key to do this is to understand what censorship looks like after 1559, given a view of the mempool: we suspect a builder is censoring if there is blockspace which could be allocated to currently eligible mempool transactions and is instead left empty, i.e. if blocks are not as full as they could be given the current mempool. Obviously there is some degree of subjectivity given by the view of the mempool, but what we can do is let the proposer impose their view (or a slice of it) in advance, so that we can distinguish censorship from simple divergence of views of the mempool.

Rather than allowing proposers to directly force inclusion of their chosen transactions, we instead allow them to force builders to fully utilize the available blockspace: if they cannot do so, they must use the unused space for the proposer-selected transactions

Cost of censorship

For an overview about how the cost of censorship changes with PBS, if we don’t assume the bribing model (where the whole validator set is bribable), see Vitalik’s State of research post

crLists + EIP 1559 change this dramatically:

Design goals from Vitalik’s post

Original basic scheme

  1. Proposer broadcasts crList, a list of transactions that the proposer sees that deserve to be included (ie. they have the correct nonce, sufficient balance and maxFeePerGas >= basefee). The crList can only contain one transaction per sender. The proposer also signs and broadcasts a crListSummary, which includes the tx.sender and tx.gaslimit for every tx in the crList.
  2. Builder makes a proposed body only if all transactions in crList are valid, and the body must include the crListSummary
  3. Proposer accepts winning header
  4. Builder publishes body. Verification of the body requires checking that for each (sender, gaslimit) in crListSummary, either block.gasused + gaslimit > block.gaslimit or sender is the sender of some transaction in the block

Notes:

Refined versions with no free data-availability given by the gasLimit field

Interactive
Validity-proof-based

One way to do it without any interactive component would be for the proposer to sign a merkle commitment to the (sender, gaslimit) list, ordered by ascending gaslimit, ties broken by sender. The block would then contain:

The builder would also have to include a bitfield marking which transactions are from crList, so that anyone can reconstruct the first part of the list, i.e. the (sender, gasLimit) pairs which precede the explicitly included one that is proven to be contained in the list.

(Doesn’t quite work because you also need to prove inclusion of the whole list, and in the worst case you might need to include as much as twice as many (sender,gaslimit) pairs as there are in the list, so that a whole subtree can be reconstructed and a single merkle branch for it can be provided. What we can do instead is to have the merkle commitment be to a list of hashes of sublists. Say the ordered list of pairs is (p1,p2,p3…). We commit to (h1,h2,h3…) where hi = hash(p1,…,pi). Moreover, we commit to (p1,p2,p3…). With the second commitment we only prove the inclusion of the “next” pair, as before, and with the first commitment we prove the inclusion of the whole sublist which precedes it. Is there a simpler way which doesn’t require hashing all these sublists?)

Builders punishing proposers for publishing crLists

Key remaining issues

The second and third problem are due to the same underlying cause:

In the next section we explore a way to resolve this availability issue, at first in a way which enables SSLE and smoothing compatibility, but which only utilizes one crList proposer

Using attestations to vote on availability

Inspired by the mechanism of MEV smoothing, we could attempt to use attestations to enforce a subjective condition which cannot be enforced by validity conditions. In this case, it would be as follows:

Some relevant points:

Possible downsides:

Version with multiple crList proposers

Issues:

Possible improvement:

crList released with header, on-chain mempool

Notes:

Incentivization

To best possible incentive system for crLists would be one where proposers are guaranteed a payment for each transaction which they include. Some notes about this:

Data-txs and crLists

In general, the issue with any scheme which does not rely on the proposer to check availability out of self-interest is that requiring availability sampling from the whole committee means having higher consumption of “availability resources” than what we allow in a slot. If we allow X MBs of data, we might need to do sampling for X + Y, with the crList being capped at Y MBs of data. If crList has very low resource caps because it is just for censorship-resistance, that’s probably ok. If it is meant to be used for fast confirmations, then heavily limiting its resources also heavily limits its usefulness (makes it expensive/unusual to get fast confirmations). A potential solution is to adjust the “slack multiplier” between target and max consumption of sharded data to account for the real max given by crList, but that means reducing the normally available supply of sharded data.

In either case, the proposer effectively gets some dedicated availability resources when sharded data is maxed out. They’re not equivalent resources of course, since there’s no immediate execution.

Notes:

Multidimensional EIP-1559 to the rescue

With multidimensional EIP 1559, this is less of an issue, if burst limit for sharded data >> target. Say it is 6x the target. We could restrict it to 5x, and still be able to process blocks where the limit is hit AND we need to guarantee the availability of a crList with sharded data up to target, or restrict it to 3x and be able to deal with availability of a crList with 3x target etc… Ideally, we set a lower burst limit which still has the property that it is hit only in a negligible percentage of blocks, and such that the remaining slack (real burst limit - burst limit we set, which is a limit on crList) is sufficient to provide fast confirmations (through crList and on-chain mempool) to all but a negligible percentage of transactions (i.e. such that only a negligible percentage of blocks has more includable shard data than what fits in crList). For example, if burst-limit/2 is sufficient for all but a negligible fraction of blocks, it would work as the limit we set

Not only it less of an issue in terms of availability resources, it is also much less of an issue in terms of proposer economics. Yes, proposers may at times control some extra availability resources, but crucially this would only be the case when the burst limit we set is reached.

Secondary auctions

As should be evident, this is pretty similar to the two crList schemes which use attestations to vote on availability. There is however some important differences:

Exec body partitioning

A natural question is how the exec body would be partitioned. Would we have n equal exec bodies, 1 main and n-1 secondaries? Would we instead have the main body totalling 1/2 of the available gas, and the secondary bodies filling up the rest? Is this going to lead to more centralization because the only way to control the whole block is to be in control of choosing the whole sequence of bodies?

I think a solution which avoids having to decide on some arbitrary partitioning of the block, and also prevents further centralization vectors, is to allow the main body to take up the whole block, and to allow secondary bodies to be as small as they want, but capping their maximum number. This way, we get these properties:

Sources of secondary bodies

Where will secondary bodies come from? Who is going to be taking the risk of including transactions which might already be included in previous bodies? Will there be secondary bodies only when there’s censorship, making them easy targets?

Generally, what makes great secondary builders is having a constant stream of transactions which are not available to all builders, because these can be safely published. These frequent builders can also include censored transactions when there’s a need for that (though how to incentivize them to do this is not straightforward. Vitalik showed there’s at least a profitable strategy for including censored transactions when there are only two builders, but the multi-builder scenario needs further analysis). Potential secondary builders are therefore:

I think it’s hard to imagine a world in which users don’t have a lot of options for how to submit their transactions, besides the public mempool. This is already a reality today, and I think it will be work more and more that way as MEV increases and off-chain competition for transactions intensifies, through incentives for end users.

EIP 1559 basefee updates

How do we update the basefee since the actual gas used is only known to the chain after the main body of the next slot is published?

One natural option would be to have the update happen in the main body of the following slot, after the execution of all previous secondary slots. The only downside is that the update cannot be known with certainty by users when they are submitting transactions. Most of the time, all secondary bodies should be published on time, and one can be almost sure that any accepted main body would have the expected basefee.

Splitting views by publishing partially available data

Say a secondary builders only publishes data on some subnets, enough to reconstruct the block and to pass some availability checks but not enough to pass all availability checks, so that some committee members would require this body to be included in the next main body and some wouldn’t. Can this be a cheap way to split views?

Enabling widespread mempool-privacy and minimization of exploitative MEV

Until there’s cryptographic primitives which allow for transactions’ content to be private prior to inclusion, it should be expected that users will want to rely on trusted parties to provide frontrunning protection as a service (ex. Flashbots Protect). Moreover, transactions (and their orderflow/MEV) are valuable, and users will want to not only minimize exploitation but to maximize the value they get for their transactions, essentially by auctioning them off. Users can therefore greatly benefit from a competitive market for transactions, by foregoing the public mempool and sending their transactions to whoever provides the most value to them.

On the other hand, foregoing the public mempool, or generally limiting accessibility of one’s transactions, comes with the trade-off of increasing time to inclusion: if there’s many builders and I only send my transaction to one of them, I’ll have to wait for them to win a block to get included. If I send it to 5 of them, I’ll likely get included much faster but perhaps not by the builder which provides most value. Even worse, I am now trusting 5 builders to not frontrun me.

If the trade-off is bad enough, users will rather circulate their transactions widely, even at the cost of some value. If most users do that, “friendly” builders don’t have any edge in the PBS auctions, and will lose more often that not to exploitative builders. We therefore should try to make it so being picky about who gets your transactions does not impact time to inclusion very much

With many bodies being includable per slot, we can enable many private mempools to coexist without much impact for the time-to-inclusion of their users

Last changed by  
 
Francesco
7560

Read more

PeerDAS fork-choice

Written by Francesco, Luca and Roberto The goal of this document is to deepen our understanding of the interactions between the fork-choice and the data availability layer after introduction of data availability sampling (DAS), with the aim of mitigating potential attacks that arise. To achieve this, we first identify potential attacks under the current fork-choice specification and suggest strategies to counter them. This analysis assumes familiarity with the current fork-choice and known attacks, and with PeerDAS. Distribution phase and sampling phase Recall that in PeerDAS, each blob is individually extended horizontally, stacked vertically and subdivided in NUM_COLUMNS columns, which are used as the sampling unit. PeerDAS comprises two phases: a distribution phase and a sampling phase. In the distribution phase, columns are allocated among subsets of validators, with each subset tasked with the custody of one or more columns (CUSTODY_REQUIREMENT). Subsequently, in the sampling phase, validators request samples to verify data availability. These samples, or columns, are acquired from peers through a request/response mechanism. The distribution phase can also serve as a kind of preliminary sampling phase, enabling a validator to consider data available if all the columns it's required to custody are available, even before completing the actual sampling phase. This proves especially valuable when employing a trailing fork-choice function, a concept explaned further below. Tight fork-choice Ideally, almost all honest validators would ever only vote for blocks that are fully available, without needing to download all of the data. To achieve this, we can require a sufficiently high amount of sampling to be completed before ever voting for a block. We refer to this as the tight fork-choice. In PeerDAS, this would mean that validators are required to perform peer sampling immediately upon receiving a block, and cannot vote for it without completing it. This gives us a useful property, which we call $\delta$-safety of sampling, for some $\delta \in [0,1/2]$ dependent on the amount of sampling ($\delta \to 0$ as number of samples increases)

Mar 14, 2025
Annotated Electra Spec -- The Beacon Chain

Notice: This document is a work-in-progress for researchers and implementers. Table of contents Introduction Constants Misc Withdrawal prefixes Domains

Aug 6, 2024
PeerDAS design progress at the interop

Some meaningful changes in the PeerDAS design have been discussed, and agreed upon, at the interop: Do not use the tight fork-choice in the first iteration of PeerDAS Increase custody requirement and subnet count Introduce validator custody Take peer sampling completely out of the critical path of consensus In my opinion, they represent both a huge simplification and an increase in robustness of the design. Let's break down what these points mean and why that is the case. Trailing fork-choice instead of tight fork-choice

May 28, 2024
PeerDAS fork-choice part 2

This post follows a previous one on the fork-choice of PeerDAS, incorporating changes stemming from the recent developments in the design of PeerDAS. Roles of peer sampling Peer sampling for full nodes: transaction confirmation The first role of peer sampling concerns full nodes, in particular the security of transaction confirmations. Still, we do not need to use peer sampling for the safe head rule, because this already relies on an honest majority assumption, which, if satisfied, would already guarantee availability. Instead, as far as transaction confirmation is concerned, we only need to use peer sampling to ensure availability of finalized checkpoints. Peer sampling for attesters: resistance to supermajority attacks As discussed in the interop update on PeerDAS, peer sampling is not necessary in order for consensus to function, as long as we have a sufficiently high custody requirement. In other words, as long as we have enough subnet sampling to ensure that at most a small percentage of the validators can ever vote for something unavailable. Still, peer sampling can play a role in improving a validator's response to supermajority attacks which invole the justification or finalization of an unavailable block. In such a situation, we would like to ensure two things:

May 24, 2024
Read more from Francesco
Published on HackMD