Special Thanks to Aditya Saraf from Cornell Tech for initial conversations that led to this post.

A nice new paper called Price of Censorship: Censorship Resistance and Throughput under Rational Concurrent Proposers caught my attention a couple of weeks ago and I have been thinking about it ever since. Saraf et al. derived the cost to effectively censor transactions in Multiple Proposer Protocols and bounds under different transaction fee mechanisms (TFMs). Given my current interest in Sybils, I thought that it would be a good idea to look into how the bounds change in the existence of Sybil nodes and how it changes the conclusion of the paper.

First, Some Background

Taking things literally from the paper, assume that there are concurrent proposers and a total block capacity of . Each proposer constructs a subblock containing at most

transactions, where the paper assumes that divides (I think the notation was something like ).

The shared mempool contains transactions with tips

The final block is the union of the proposed subblocks. So we see that a transaction may appear in several proposals but it is executed only once in the final block.

For each transaction , let

denote the probability that an individual proposer includes it. In the symmetric equilibrium studied by the paper, every proposer uses the same marginal inclusion probabilities

subject to

Before we move further, the paper model assumes that proposers observe the same mempool, act simultaneously, randomize independently across proposers, maximize their individual expected revenue, get outside user tips not in their control and most importantly, do not collude.

Transaction Fee Mechanisms (TFMs)

We will look at the different TFMs that the censorship cost bounds were constructed under. Let (would have been nicer to denote as but I guess its in use) be the number of proposers that include transaction .

Duplication-penalizing TFM

If exactly one proposer includes transaction , that proposer receives the entire tip . If more than one proposer includes it, no proposer receives the tip and the transaction pays no auction fee.

The aggregate proposer revenue from transaction is

Even-split TFM

If proposers include transaction , each includer receives

Therefore, aggregate proposer revenue is

and finally

Collective TFM

The tips of all included transactions are pooled and divided equally among the proposers, irrespective of which proposer included which transaction.

Aggregate revenue from transaction is again

SIDEWAYS: We notice that the collective and even-split mechanisms have the same aggregate revenue from a fixed union of transactions, although they vary in distribution of that revenue among proposers. I suspect that the welfare of proposers in the two TFMs are also different, with one being more unfair than the other.

SIDEWAYS: Also the mechanism may also charge a base fee which is burned rather than being paid to proposers.

Core Results

Recall initially, proposers, each selecting transactions, with total capacity . Now if each proposer includes transaction with probability , its final inclusion probability is

Normalized throughput is therefore

Duplication lowers throughput because repeated inclusions consume capacity without adding new transactions. I suspect this would benefit from further analysis that falls under the umbrella of spam transactions and the many works in that area.

Symmetric proposer equilibrium

The expected marginal reward from including transaction is

and

Because these rewards decrease with , equilibrium equalizes marginal rewards. The paper proves that there exists a unique symmetric marginal probability vector

where is the common equilibrium marginal reward and is the clipped inverse of .

For duplication-penalizing and collective,

The even-split inverse is computed numerically. The equilibrium itself can be found by binary search over .

Censorship Cost Theorem

Suppose an attacker wants transaction censored with probability at least . Independence implies

so the target equilibrium inclusion probability must be

Remove and solve the equilibrium for the remaining transactions using residual capacity . Let denote the resulting marginal reward.

The paper’s cut-and-paste theorem gives the minimum unconditional bribe per omitting proposer:

Since each proposer omits with probability , expected total expenditure is

For the three TFMs, this becomes

and

For complete censorship, , so

and

Economic Censorship Resistance

The paper defines economic censorship resistance as the attacker’s expected expenditure relative to the transaction’s payment:

For even-split and collective,

For duplication-penalizing,

The paper’s simulations find that eCR grows approximately linearly with the number of proposers. Duplication initially reduces throughput but throughput eventually plateaus while censorship resistance continues to increase.

Greater congestion and fee burning reduce eCR, while the duplication-penalizing TFM generally achieves the highest throughput and censorship resistance among the three mechanisms studied.

This is where the paper’s model ends and our analysis begins. I suspect that the linear scaling is not going to hold under Sybils but let us look at it more formally.

Censorship under Sybils and Proposer Collusion

The original model contains independent proposers. Let us look at the case where these proposers collude and thus are partitioned among disjoint groups:

The three benchmark cases are

and

For coalition , we will denote the utility from deviating from censorship and including target transaction as

where is its optimal payoff while omitting and is its optimal payoff when it may include holding all other coalitions to censorship.

The minimum payments needed to sustain complete censorship are therefore

This gives the new computation

where is the transaction’s payment conditional on inclusion.

Notice that this definition does not automatically increase when one proposer creates more keys/identities.

No collusion (Benchmark)

When all proposers act independently, the paper’s original bounds apply. To censor with probability , its equilibrium inclusion probability must satisfy

The resulting expected bribe expenditures are

and

For complete censorship, :

and

The approximately linear dependence on relies on the proposers being independent economic actors.

Partial collusion

Let denote ’s opportunity cost of making room for under mechanism .

For duplication-penalizing and even-split, a coalition can include exactly once and collect the full tip. Hence

The corresponding censorship costs are

and

Under the collective TFM, suppose coalition controls identities and therefore receives fee share

Its utility from causing to enter the common pool is only , giving

and

So this is probably the most interesting case out of the three. It mostly hinges on . I imagine that will be sensitive to coupled utilities of other honest proposers in the setting.

SIDEWAYS: How can we figure out the best way to derive ? Maybe it’s a coupled utility function with other (honest) agents in the system? Maybe it can be approximated as a bound of utilities that can be derived from different quantities of ? Open work here.

Full collusion

Now suppose all proposers form a full sybil collusion with total capacity .

For all three TFMs, including a transaction exactly once produces aggregate proposer revenue , while duplication cannot increase aggregate revenue and consumes capacity. The coalition therefore selects the highest tip transactions exactly once.

Let

Its optimal revenue is

If target belongs to the top , censoring it replaces it with transaction :

Thus, for every TFM,

Consequently,

Since an optimally coordinated coalition includes exactly once, its conditional payment is . Therefore,

Interestingly, this bound does not grow linearly with the number of proposers.

Under heavy congestion, may be close to , making censorship cheap. If an equally valuable substitute exists, then

Comparison Between Censorship Bounds

For complete censorship, the central expressions are:

TFM	No collusion	Partial collusion	Full collusion
Duplication-penalizing
Even-split
Collective

We have to be careful before we assign a universal ordering under partial collusion because the values and differ across mechanisms.

I do think I can make some points though. Duplication-penalizing performs strongly without collusion but coalitions can avoid its duplication penalty through coordination. On the other hand, even-split does not destroy the user’s payment under duplication but it is vulnerable to Sybils. Finally collective sharing creates weaker inclusion incentives and greater free riding.

So technically under full collusion, all three mechanisms collapse to the same aggregate censorship bound.

SIDEWAYS: It is tempting to conjecture that

But as I said, I would be careful in doing so.

Addendum: All Sybil Versus Single Proposer

Aditya in our meeting mentioned that the full Sybil case simplifies down to the single proposer case. Let us try it out.

Suppose one operator controls every MCP proposer. Its aggregate capacity is

Because it coordinates all subblocks, it chooses exactly the same allocation as a single proposer with capacity : the highest tip transactions and each once.

Therefore,

Likewise,

Hence proved.

Thanks for reading. Reach out to talk more. I have been Abhimanyu Nag.