Deterministic namespace ID based on blob content

[rootulp]

Context

@nashqueue shared an interesting idea over Slack that I wanted to preserve for future consideration

Imagine if we enforce a specific rule. Every Namespace will only have one blob. The PFB commitment of this blob equals to the namespace of this blob. Now we can find any blob by commitment and not by index or understanding the PFB state logic. We have no woods attack on a namespace. The PFB does not need to include the index anymore.

My understanding of this proposal is that blobs would be content addressable. In other words, a user would not submit a namespace along with a PFB and instead the blob content of the PFB would determine the namespace.

In order for this proposal to be considered, the namespace number of bytes may need to increase from 8 => 32 to avoid hash collisions. Additionally, since rollups can no longer rely on a consistent namespace ID, they may need to provide their own block sync/header gossip.

[evan-forbes]

In order for this proposal to be considered, the namespace number of bytes may need to increase from 8 => 32

I think with the new 16, it could be sufficient.

after thinking about it though, what is the benefit of doing this over just using a single, or picking a random, namespace and gossiping the headers after the fact? cc @nashqueue

[nashqueue]

after thinking about it though, what is the benefit of doing this over just using a single, or picking a random, namespace and gossiping the headers after the fact?

Same benefit as picking a random namespace and sending it. The nice feature of this is just that it is self-referencing. Another fact is that you can do very lightweight exclusion proofs, because if the namespace does not exist then the data does not exist as well.

[musalbas]

This kind of defeats the point of a namespace as a way to only need to read your namespace to get your rollup blocks tho, with this you have to scan the whole chain to execute your rollup's fork choice rule

[rootulp]

with this you have to scan the whole chain to execute your rollup's fork choice rule

Why does a roll-up light node need to scan the whole Celestia chain? Instead of scanning the whole chain, can the roll-up light node fetch the relevant namespace IDs and block heights from an honest roll-up full node and then only query for those blobs from Celestia?

[musalbas]

Because they don't know what the namespace IDs as they are not deterministic as they depend on future blobs in that rollup. The rollup light node can fetch from full nodes, but the full nodes executing the fork-choice rule directly can't

[Wondertan]

@musalbas, why forward syncing with fork-choice rule is necessary for Rollup FN? Why can't a RFN backward sync over already committed fork choices?

[musalbas]

The rollup may not be fork-free like Tendermint BFT

[Wondertan]

You can always choose a tip of the fork of interest and sync backward. Maybe I don't see the use case though.

[musalbas]

If you sync backwards you'd have to trust the tip of the fork as being the correct chain after the execution of the fork-choice rule. It only seems practical to trust a third party to tell you the correct tip if the chain is fork-free (because of double signing evidence) and/or a weak subjectivity assumption.

RFNs will need a way to re-execute the fork choice rule from genesis anyways as they may not have a weak subjectivity assumption for the rollup itself

And even if they did have a weak subjectivity assumption, they'd need to be able to download all block data when sycning new rollup headers to execute the fork-choice rule in the first place, otherwise there's a "chicken and egg" problem (how do you know what the tip of chain is if no one executed the fork-choice rule?)

[rootulp]

with this you have to scan the whole chain to execute your rollup's fork choice rule

One idea for roll-ups to avoid scanning the whole Celestia chain is for a roll-up to specify some prefix of the namespace ID that all future blocks of the roll-up must be published to. In this way, roll-ups can constrain the domain available from the entire namespace ID space to a subset (i.e. namespace IDs that start with []byte("sovlabs")). Then roll-up full nodes can search this subset of the namespace for relevant blobs.

Note: In practice, roll-up sequencers may need need to add a nonce to their blob and perform some amount of PoW to generate a blob that when hashed results in a namespace ID with the prefix described above. Roll-ups that don't need a consistent namespace ID prefix don't need this additional PoW step.

[musalbas]

Yeah that could work. However can't blobs also be content addressable by specifying their index in the tree along with their hash? Or would that not achieve the desired use case (which is what?)?

Note: In practice, roll-up sequencers may need need to add a nonce to their blob and perform some amount of PoW to generate a blob that when hashed results in a namespace ID with the prefix described above. Roll-ups that don't need a consistent namespace ID prefix don't need this additional PoW step.

I don't think they need to do any PoW to choose the namespace ID, they could just reserve [:4] for the nid prefix for example, and then [4:] for the actual truncated hash.

[rootulp]

I should clarify that the proposal for PoW is if namespace ID is entirely deterministic based on blob content. So something like this Go playground. If namespace ID is still exposed as a parameter in PayForBlob then a roll-up could reserve some amount of prefix like you mentioned.

Or would that not achieve the desired use case (which is what?)?

Good question. I like this proposal because it simplifies the public API. Instead of:

celestia-appd tx blob PayForBlobs [hexNamespace] [hexBlob]

users could publish blobs via

celestia-appd tx blob PayForBlobs [hexBlob]

which is comparable to ipfs add.

@nashqueue mentioned other potential benefits which maybe he can expand upon:

1. self-referencing
2. exclusion proofs

[rootulp]

Notes from lunch convo with @c-node, @Wondertan, @vgonkivs:

If namespace IDs are determinstic:

• roll-up full nodes need to be Celestia full nodes because they must scan the entire Celestia block for blobs that are relevant to their roll-up
• PFBs that contain duplicate blob data can be ignored
• an actor can no longer Woods attack a particular namespace

If namespace IDs are specified by blob submitter:

• this is useful for roll-ups that want Celestia to handle their fork-choice rule (e.g. the blob with the lowest index in a namespace is the canonical roll-up block for that height). Contrastingly, roll-ups that want to use Celestia for data availability and not consensus may not need a blob submitter specified namespace ID because they can agree on the canonical roll-up block for a height outside of Celestia.