EPIC: Intra-namespace blob priority

[evan-forbes]

We want to add some validator imposed priority to blobs within the same namespace. This would allow for a celestia block producer to contribute to a rollup's fork choice rule, along with adding a builtin prevention against the woods attack.

While we could simply imply this priority by using the order of the blobs of a namespace, without the adoption of ADR013, we don’t want this priority to be implied by the order of the blobs because then we can no longer pack the blobs within a namespace tightly.

If we don’t adopt ADR013, then we could still add an option for the celestia block producer to include some priority metadata that would select the blob. If we go down this route, where we put that metadata has slightly different outcomes with different trade-offs.

The first option is to stick the priority metadata with the other metadata added to each PFB to determine the start share index of each blob. This is currently easy to implement, but would increase our reliance on the wrapper that contains the metadata. That is undesirable as the wrapper is something we want to eventually remove, due to the complexity it adds to the implementation, and because it interferes with compact blocks (gossiping hashes during consensus instead of entire txs).

Simply adding the priority to the metadata is desirable because we rollups that are already creating an inclusion proof to a given PFB will already prove the inclusion of some metadata provided by the block producer. That being said, if for some reason the rollup must compare many different priorities/metadata before looking at blobs, then they have to parse and prove the metadata to each PFB individually.

The second option would be to include all of the priority metadata into its own share(s) (clarifying edit: metadata specific shares). Then rollups could download and prove all of the metadata at once. This would allow rollups to compare priorities, but would require separate inclusion proofs. One to all of the metadata, and then a second to the actual PFB. This method might also be desired, because we could separate all block producer added metadata to their own shares. Rollups interested in that meta data would have access to all of it, and then we could remove the metadata wrapper that is currently added to all PFBs.

[musalbas]

This is currently easy to implement, but would increase our reliance on the wrapper that contains the metadata. That is undesirable as the wrapper is something we want to eventually remove, due to the complexity it adds to the implementation, and because it interferes with compact blocks (gossiping hashes during consensus instead of entire txs).

It should be noted that after mainnet, we won't be able to easily change the PFB format without breaking rollups that rely on it. We may be able to add a new PFB format in a different reserved namespace via new share versions, but potentially not remove historical formats. Do we plan to do this before mainnet?

The second option would be to include all of the priority metadata into its own share(s).

I don't think that's possible as validators can't malleate blobs as that will change their commitment.

[evan-forbes]

The second option would be to include all of the priority metadata into its own share(s).

I don't think that's possible as validators can't malleate blobs as that will change their commitment.

by its, I mean separate reserved shares just for all metadata, not the shares that the blob uses

Do we plan to do this before mainnet?

We could maybe squeeze it in before incentivized testnet if we make a decision quickly, but it is a very good point that the window to change things easily is closing quickly.

[cmwaters]

along with adding a builtin prevention against the woods attack.

What's the woods attack?

We want to add some validator imposed priority to blobs within the same namespace.

What does the priority map to exactly? That one blob gets executed before another blob, or gets executed instead of another blob?

That is undesirable as the wrapper is something we want to eventually remove

I think it's quite difficult to remove the wrapper if it remains important that the PFB includes where in the square the blob should be which as I understand it is important for fraud proofs.

We may be able to add a new PFB format in a different reserved namespace via new share versions

SDK messages can and should be versioned. The state machine should be able to handle processing of different PFB versions. Adding metadata to the IndexWrapper shouldn't have to affect how shares a constructed though

[musalbas]

What's the woods attack?

https://forum.celestia.org/t/woods-attack-on-celestia/59

What does the priority map to exactly? That one blob gets executed before another blob, or gets executed instead of another blob?

Gets executed before another blob. Rollups might also want to impose a maximum blob limit, eg say 10 blobs, and all blobs after that are ignored.

SDK messages can and should be versioned. The state machine should be able to handle processing of different PFB versions. Adding metadata to the IndexWrapper shouldn't have to affect how shares a constructed though

Part of this is that we might want to not even use protobuf for a new PFB format, as eg it might not be very friendly for some zk environments.

[rootulp]

along with adding a builtin prevention against the woods attack.

Another proposal that would build in prevention against the woods attack is #1377

While we could simply imply this priority by using the order of the blobs of a namespace

To clarify: roll-ups would interpret the order of blobs in a namespace as the order those blobs should be executed on the roll-up. If that's the case, they can start doing that today without any Celestia protocol change.

add an option for the celestia block producer to include some priority metadata that would select the blob

Where do we expect block producers to source this priority metadata? When would it be different than the in-protocol specified fee associated with a PFB tx?

[musalbas]

To clarify: roll-ups would interpret the order of blobs in a namespace as the order those blobs should be executed on the roll-up. If that's the case, they can start doing that today without any Celestia protocol change.

Yes, but as mentioned in OP, this would force validators to decide between efficient packing vs ordering the highest paid blobs, which isn't ideal.

Where do we expect block producers to source this priority metadata? When would it be different than the in-protocol specified fee associated with a PFB tx?

The block producers can choose the priority, creating an implicit fee market where more fees -> more priority. But the block producers might not abide by this (unless you have some MEV infra), in which case you'd need to enforce the priority to be based on gas fee

[rootulp]

efficient packing vs ordering the highest paid blobs

Assuming a block proposer is incentivized to maximize profit, they can do so by efficiently packing blobs in the data square. Since there is no consensus critical rule that states blobs in a namespace must be ordered by priority fee (or any other heuristic), I expect a profit maximizing block proposer to arrange as many fee paying blobs in the data square as possible. If a block proposer wants to contribute to a roll-up's fork choice rule by prioritizing certain blobs, they may do so by including those blobs at a low index while packing the remainder of the namespace efficiently. I see the tradeoff.

If the primary hesitation around index implied priority is intra-namespace padding then I agree we should explore ADR 13.

Alternatively a block proposer could indicate priority for certain blobs via the order of PFB txs in the PFB txs reserved namespace. Since data in this reserved namespace is packed compactly, there is no padding between subsequent PFB txs.

in which case you'd need to enforce the priority to be based on gas fee

If such a rule were enforced in-protocol, then a block proposer and blob submitter can collude via out of protocol refunds to subvert non-colluding blob submitters.

One other question I have is: if we introduce a new non-fee based priority mechanism for PFBs, how do we expect that to interact with the existing fees associated with Tendermint transactions?

[rootulp]

Per two onsite meetings, this issue seems resolvable. We concluded that we'd like to move forward with adopting ADR 13 which should make it extremely unlikely that validators rearrange blobs in a namespace to minimize padding. Given that we don't expect validators to arrange blobs within a namespace, roll-ups are able to infer the priority of a blob based on its location in a namespace (i.e. lowest index = highest priority).

[musalbas]

I don't think this issue can be closed though, because the core of the issue is about implementing some kind of prioritization to prevent woods attacks, which has not been done.

[rootulp]

ADR-20 refactored square construction to be deterministic so block proposers can't tamper with the ordering.

PFB transactions in the PFB namespace are ordered by priority (a.k.a gas price) and blobs within a namespace are also ordered by priority (a.k.a gas price). See here and here. Can you please clarify what additional prioritization mechanism is needed?

From my perspective, if a roll-up wants to combat the Woods attack, they need to submit PFB txs with a higher gas price than spam PFB transactions attacking their namespace. The roll-up can then selectively read the blobs in their namespace with a gas price >= the threshold they deem that filters out spam transactions.

[musalbas]

Oh ok, yeah if blobs are currently ordered within namespaces by gas paid then I'd consider the woods attack addressed. Is this enforced in a consensus critical way?

[rootulp]

Is this enforced in a consensus critical way?

Yes because if a consensus node attempts to tamper with the order of blobs, the resulting data root will conflict with an honest validator's data root. This will fail in process proposal here.

[evan-forbes]

Is this enforced in a consensus critical way?

by default the validators reap from the mempool via gas price, but we don't check if the txs are sorted by gas price in a consensus critical way. Proposers could for order blobtxs however they see fit in the namespace. it is correct that square construction is deterministic, so given a protobuf encoded version of the block data (the thing the proposer proposes), there is only one valid square.

[evan-forbes]

reopening for now, but if it doesn't make sense to add this we can re-close the issue

[rootulp]

Ahh I see what you're saying. Given:

pfbTxA with gas price 10 and namespace 1
pfbTxB with gas price 100 and namespace 1

the proposer by default will reap these transactions from the mempool in the order {pfbTxB, pfbTxA} but if they submit a proposal where Data.Txs = {pfbTxA, pfbTxB} then the order in namespace 1 will be A then B. So we do need a consensus critical rule to enforce that a proposer's Data.Txs is ordered by gas price.

Related: #3164