Quadratic Pricing for Namespaces

Research
1

Motivation

The need to ration block space into namespaces in Celestia, and the ability for anyone to submit arbitrary messages to any namespace even if invalid, as long as they have enough TIA, presents unique challenges in regards to incentives alignment and DoS/spam issues.

While rollup specific attacks like Woods Attack can be mitigated via out-of-protocol mechanics, there always remains an issue that a well-resourced attacker can simply spam a namespace with invalid data to price out a rollup from a block.

For rollups that have small state or where the aggregator’s income from settlement fees has low margins, this can allow an attacker to price out the finalization of a rollup’s block for long periods of time.

Furthermore, if the point of Celestia is to support many rollups rather than ending up in a state where 1-3 large rollups monopolize the entire block space, pricing inclusion of a message in a namespace proportional to the fullness of that namespace aligns incentives better with Celestia’s goals.

Pricing Scheme

Extending one of the Woods Attack mitigation ideas proposed by @nusret1996, on top of limiting the number of shares for a particular namespace id to \sqrt{n} where n is the number of total shares a block can support, the following pricing formula would be applied as a charge for message inclusion:

msg\_cost = p*k^{2*d}

With p being the base cost of share inclusion, and k being the number of shares included in a namespace. d is a dampening factor whose value can be a point on a curve with range (0, 1] that is generated from the size of the last block compared to the block’s size limit.

This mechanic would make it such that an attacker has to spend far more to keep a namespace full than a rollup would pay when acting honestly and submitting valid blocks.

The attacker might try to spam messages with random namespace IDs to get around this, but then they would be competing on cost with the entirety of the network’s users, and as such would require far more resources.

An additional effect of this scheme is that by exponentially increasing the cost that a rollup with large state would pay when committing to the chain, it prevents pricing out use have less time-sensitive extractable value.

Rollups that try to sidestep this scheme by using many different namespaces would take on performance and latency penalties in terms of P2P topic discovery, block validation, and DoS/spam resistance.

In the case of persistent attacks, a variant of the above scheme suggested by @decanus could be applied which increases the cost of inclusion relative to the fullness of namespaces in the previous blocks, with sliding window cooldown.

6 Likes
2

Not that I have given the formula much thought of exactly the best method to price. But I’d consider something like:

msg\_cost = (p*k^2) + (2^{log(l)})

Where l is the last msg\_cost of the last block.

3 Likes
3

If an adversary has fixed funds, e.g. F, and we would like it to be able to reserve at most \sqrt{n} number of shares for a namespace ID (while it was previously spamming n shares), it would suffice to have a linear cost rather than quadratic. With a quadratic or exponential cost, it should be possible to reduce the spammed shares to a cube-root or logarithm of the total number of shares.

4

I like the idea of having quadratic pricing of fees per namespace, as this potentially allows fees per namespace to model fees of blocks more closely.

Rollups that try to sidestep this scheme by using many different namespaces would take on performance and latency penalties in terms of P2P topic discovery, block validation, and DoS/spam resistance.

I’m not sure that these penalties are significant in practice. P2P topic discovery and block validation could probably be optimized to be as efficient as having a single namespace, and DoS resistance might not be an issue with this mitigation.

2 Likes