Cumulative, Non-Expiring Inclusion Lists

[Nerolation]

Cumulative, Non-Expiring Inclusion Lists

The following starts with a quick analysis of the current inclusion list (IL) design by Vitalik and Mike and is followed by a suggestion to better align it with the economic incentives of big staking pool operators such as Lido, Coinbase, Kraken or Rocketpool.

Get familiar with the current design here.

Special thanks to Matt for the great input.

Background

ILs are constraining.

ILs force a certain transaction to be included if there is still enough space in the block.
This means that builders are constrained by not being able to freely decide upon the content of their blocks but must align with the IL in order to produce a valid block.

Furthermore, by having an IL, the amount of value that can be extracted from a block can only become less as the set of possibilities a non-censoring builder has when constructing blocks shrinks.

A second effect that proposers using ILs (and their successors) could initially face is that certain builders might stop building for certain slots if the ILs force them to include, e.g., an OFACed transaction. This is cool as it provides non-censoring parties strong competitive advantages.

As a thought experiment: we should revive Martin’s Censorship-Detection contract. The contract allows the builder to claim some free MEV while sending 1 wei to the Tornado Cash Gitcoin Grants Donation contract. We can use/fund it to make sure that every single block contains a sanctioned interaction. Eventually, we may force censoring parties to entirely leave the block building market.

Notably, as pointed out by Barnabé, censoring builders wouldn’t be forced to exit if they can otherwise ensure that their block is full. Thus they would have an incentive to sponsor certain transactions for users just to fill up their blocks.

Same slot, next-slot, cumulative…

As a recap. Having proposers set ILs for their own blocks doesn’t make much sense and it relies purely on altruism to include censored transactions into one’s own blocks.

Having forward-ILs makes sense, allowing the current proposer to constrain the next proposer. This means that the current proposer could create an IL that either the current proposer itself or the next proposer must satisfy.

The problem with one-slot-forward ILs is that parties with multiple validators have an economic incentive to not constrain the next proposer in the case the next proposer is controlled by the same entity.

Party C has two consecutive slots and therefore leaves the IL empty in the third slot

This means, if I have two slots in a row, I would probably leave my ILs empty for my first proposer. Thereby I’d make sure to not constrain the builders in the next slot and thus act profit-maximizing. Centralization.

Assuming there is an OFACed transaction in every block then the number of consecutive slots a certain entity determines how often it can allow builders to work without constraints (=IL). Importantly, having no constraints doesn’t only mean being able to include some negligible TC transaction. It’s more about having access to the most profitable block builders in the ecosystem.

In the past month, censoring builders such as beaver, builder69 or rsync offered proposer payments of around 0.061 ETH. Titan Builder, the largest non-censoring builder had 0.05 ETH.

Potential Impact

Lido currently proposes blocks in around 30% of the slots. The chances of Lido having two consecutive slots are 9% (0.3**2). This can be confirmed by looking at the slots of the past month (2023-08-01 - 2023-08-28):

Lido had around 31% market share and the observed likelihood of consecutive slots of 9.5%.Assuming we have censored txs in every block and every honest validator puts them on their IL then 9.5% of the slots could have an empty ILs, potentially opening up the market for censoring builders.

How many slots would have empty ILs assuming that it’s economically rational for an entity to not constrain itself in consecutive slots?

Looking at data from the past month, it’s 10.5%, assuming the Lido Node Operators collude in order to maximize the profits for Lido as a whole.
Having the Lido Node Operators act independently and constrain each other with ILs, then only 1.9% of the slots would have empty ILs.

10% is very likely too high and an excessively large centralizing force.
2% is better but still not great as even every little advantage can have cascading effects and eventually harm decentralization.

The crux is, how to make sure that even those entities with consecutive slots are constrained and constrain others.

So, we need a way to have 100% filled ILs in the case that there is an e.g. OFAC sanctioned transaction paying enough to be included in the next block(s) (… and has not been included for xy seconds).

This can be achieved by having a cumulative Summary. The Summary, as described in the IL post by Mike and Vitalik, consists of pairs of addresses and gas amounts that tell the proposer which transaction they’d have to include in their block.

By removing the one-slot expiry and allowing summaries to merge, a more aggressive design can be achieved.

Forward-cumulative ILs

The construction of the cumulative IL would then also contain a third value which is the block number deadline. Transactions on the IL would be validated in the same way as in the original IL design post, but the gas must satisfy the block number deadline specified such that it is still paying enough to be included in a block at the specified deadline.
The base fee can increase by 12.5% per block. Thus, a transaction that should still be valid in, let’s say, 2 blocks.

As an example:

Increase per block d = 1.125.
Set of valid transactions tx \in txs.
Gas paid per transaction gas(tx_i).
Blocknumber deadline to include a tx k.
The basefee base(t_0).

So, in order to include a block k slots in the future, the block must at least pay base_{t+k} where base_{t+k} = base_{t0}*d^k, assuming the basefee increases in every block.

Thus, the maximum deadline k specified for each entry as a block number by the creator of the IL must satisfy the following:
gas(tx) \geq base_{t_0+k} for every transaction.

This ensures that the transaction can still cover the base fee even if it is included k slots in the future.

Of course, there’s a conflict between including a txs sometime in the future and strong inclusion guarantees. Wouldn’t you still feel censored if your tx gets included even though someone put it on their IL 32 slots earlier?
That’s why k must be kept small (thinking of something between 2 and 5).

Share	2 consecutive slots	3 consecutive slots	4 consecutive slots	5 consecutive slots
30%	9%	2.7%	0.81%	0.24%
25%	6.3%	1.6%	0.39%	0.097%

The probability that an entity with 30% validator share has 3 consecutve blocks is 2.7%, so may occur around 194 times a day. 4 consecutive slots occur 58 times a day and 5 consecutive slots occur 17 times a day.

Having forward-cumulative ILs with a k of 3 slots - thus the creator of the IL can have txs in its IL that must be included in slot n+k at the latest - would then bring the following adavantages:

• The IL doesn’t expire until the specified deadline of the entry is reached or the tx has been included
• More ILs because entities with consecutive slots can also constrain others further in the future if there’s a censored tx that pays enough.

This idea comes with one quite radical aspect. In the case that the Summary doesn’t expire but cumulates and aggregates over time, censoring validators with consecutive would be forced to miss their slot/get reored for their slots.

Let’s go through a quick example:

In this example, we deal with 5 different validators that are controlled by 4 different entities. The validators in slot n+2 and n+3 are controlled by the same entity.

• Validators can specify a deadline for a fromAddress (and a gas value) to be included.
• Entries in the IL do not expire until the tx is included or until it reached the specified deadline.
• Validators accumulate and merge ILs from previous validators with their own. The merging works by grouping the extended list of summaries and grouping it by fromAddress while taking the min deadline.

By doing so validators can be precisely targeted to include a certain tx and only in very exceptional cases, when validators have more than k slots where k is the number of slots in the future the validator is allowed to specify in its IL.

Conclusion

By spamming the mempool with censored transactions while having some kind of default client behavior that puts tx into an IL if they weren’t picked up by the previous validator (…or satisfy some other condition such as not being picked up for 5 blocks in a row), censoring validators would be completely kicked out of the ecosystem. For builders that stick to not building blocks that contain tx put on ILs, the landscape would change drastically because they would not be able to compete for most of the slots anymore. The same applies to relays that only allow blocks without certain txs.

[potuz]

@Nerolation

Notably, as pointed out by Barnabé, censoring builders wouldn’t be forced to exit if they can otherwise ensure that their block is full. Thus they would have an incentive to sponsor certain transactions for users just to fill up their blocks.

This assumes an IL design where the builder is allowed to not fulfill the IL if the block is full. You could instead cap the gas limit of the IL and force the builder to include it no matter what.

[Nerolation]

Oh yeah. I think both designes have their advantages and disadvantages.
If builders must strictly follow the ILs and cannot stuff their blocks with other transaction it would be even more drastic against censoring buinlers as there’s no escape hatch left for them.
Allowing stuffing blocks to circumvent an IL would mean that for determining the head of the chain - I guess - one would need to be able to determine if a block was truely full or if one of the IL entries’ txs could still have been included. This sounds more complex than just strictly enforcing the IL.

[potuz]

Fwiw with a group of EP fellows we are specifying this and will have a PoC hopefully working in the coming months. The spec is completely broken right now but it’s advancing at a good pace

minimal ePBS with forward inclusion lists and PTC

[mteam88]

I may be wrong about this, but doesn’t this rely on the assumption that there will be an honest proposer in the next k slots? Or else the proposer of slot n+k would essentially bear the burden of including the censored txns.

i.e. Proposer n creates an IL and the builders for slots n + (1…k) don’t include the censored txns (they are censoring builders) then the responsibility would fall on proposer n+k to include them. Isn’t the odds still XX% that proposer n+k is operated by the same pool operator?

Maybe I am missing something, but I believe there is a significant chance that node operators still constrain themselves unless a vast majority of proposers are honest. In my model, the node operators have the following chance of limiting themselves:

Let s = operator share, j = ratio of proposers who include all txns present in IL (even when they don’t have to):

P(\text{self constrain}) = s * (1-j)^{k-1} + s^k

because (1-j)^{k-1} is the probability that no proposers have already included the txns on the IL.

Here is a table with my findings when share is 30%:

k	j = 25\%	j = 50\%	j = 75\%	j = 85\%	j = 95\%
2	22.5%	15%	7.5%	4.5%	1.5%
3	16.875%	7.5%	1.875%	0.675%	0.075%
4	12.66%	3.75%	0.47%	0.10%	0.004%
5	9.5%	1.88%	0.12%	0.015%	0.0002%

Note: that this table doesn’t consider the possibility that the proposer is proposing for each consecutive block, so it isn’t complete. I left out the probability of producing every block (s^{k}) to show the difference between the current model. A complete table:

k	j = 25\%	j = 50\%	j = 75\%	j = 85\%	j = 95\%
2	31.5%	24%	16.5%	13.5%	10.5%
3	19.575%	10.2%	4.575%	3.375%	2.775%
4	13.47%	4.56%	1.28%	0.91%	0.814%
5	9.74%	2.12%	0.36%	0.255%	0.2402%

Extra note: as j approaches 100%, the above table approaches the current assumed values.

Just wanted to point out a pretty heavy reliance on honest proposers here.

I may be completely wrong about this, but would love some input! Please check my math

Further research: calculate EV of a staking pool node operator based on difference between censoring or not censoring with these percentages to see if creating an IL makes sense.

[Nerolation]

I think that’s exactly the point of having IL entries that are valid over a certain number of slots.

@mteam88

i.e. Proposer n creates an IL and the builders for slots n + (1…k) don’t include the censored txns (they are censoring builders) then the responsibility would fall on proposer n+k to include them.

In this case, the builder’s censored block would not be chosen by the proposer (and not even forwarded by the relay) as it doesn’t obey the IL and therefore can’t make it into the canonical chain. So a censoring builder would have to fill up their blocks or they would not be able to participate in that slot. Censoring validators would have to chose a censored-but-full block or miss their slot.

Let’s go through an example:
We have 5 slots, n, …, n+4.

• I’m the proposer in slot n.
• Censoring party X is the proposer of n+1, n+2, and n+3.
• Censoring party Y is the proposer of n+4

I put a to-be-censored (bc, f.e. sanctioned) on my IL in slot n but don’t include it in my block yet. (We assume that the tx pays enough gas to be included in slot n+4, despite the base fee increasing 4 slots in a row).

Scenario 1: No cumulative (thus expiring) IL:
If party X wants to censor in slot n+1 and thus not follow my IL entry, they can fill their block with other txs until it’s full. Then, for their proposer in n+2 the IL would be empty/expired so that the proposer in n+2 doesn’t have any constraints.
The proposer in slot n+2 would also not create an IL to not constrain the proposer in n+3, as this slot is also controlled by party X. The proposer in n+3 however would put something into its IL in order to constrain party Y in slot n+4.

Eventually, if there are not enough txs to fill up the block, party X would only miss one block but since the IL expired, they would still be able to propose (censored) blocks in n+2 and n+3.

Scenario 2: Cumulative, non-expiring IL:
Here, party X, with their proposer in slot n+1 can do the same as previously, which is filling up the block to not be forced to follow the IL.
For slot n+2 the IL would still be valid such that the proposer in n+2 would also have to fill up its block to avoid including the tx on the IL. The same applies for the proposer in n+3. This means that party X must either include the tx on the IL or make sure to fill up it’s blocks 3 times in a row and if it can’t, e.g. because there are not enough tx that pay at least the base fee, then they would have to miss their slot.

This means, by including a to-be-censored tx in my IL, I force the following proposers to either have full blocks, miss their slots, or obey my IL and include the respective tx.

Outcome:
As a consequence, my IL entry cannot simply expire after one slot. Censoring validators with consecutive slots that can’t fill up all their blocks and also don’t want to include sanctioned txs are forced to miss their slots. In the above example, assuming there aren’t enough tx to fill up blocks, party X would miss all of their 3 slots. Same for party Y.

Instead of proposing a block, the censoring parties would then have time thinking about if a censorship-resistant blockchain is the right place for them to participate or if they better move somewhere else.

In a scenario where there’re always some txs in the mempool that certain parties would like to censor, censoring parties are forced to produce full blocks or miss their slot. The latter would hurt them economically and these parties would not be able to compete for a high APY anymore.

[mteam88]

Thank you! This definitely clarifies. I was under the impression that it was optional to include the censored txns until the slot where they expire. This makes a lot more sense!