PFB signer namespace

[cmwaters]

Update

This issue is superseded by two byproduct issues which propose new changes to address the original problems outlined in this issue:

• https://github.com/celestiaorg/celestia-app/issues/3315
• https://github.com/celestiaorg/celestia-app/issues/3316

Summary

Replace the PFBNamespace with a PFBSignerNamespace that keeps a map of blobs to signers so rollups can easily verify the author of the blob which is often part of the fork choice rule.

Problem Definition

Currently we have two reserved namespaces in use TxNamespace and PFBNamespace. The PFBNamespace is where all PFBs are placed. The reason for separating them out is that rollup SDKs and libraries want to be able to work out the signer/author of the PFB as part of validating a blob.

For example, at Sovereign the way this works is as follows:

• Query all the blobs from the rollup namespace via RPC
• For each blob, reconstruct the blob commitment.
• Fetch the PFB namespace
• Parse the PFB namespace and create a mapping from blob commitment -> PFB
• (In zero-knowledge) Accept the list of all rollup blobs and the list of relevant PFBs as inputs
• (In zero-knowledge) Verify that the claimed list of blobs matches the block header using the namespaced merkle tree
• (In zero-knowledge) For each blob, find the PFB with the matching commitment and check that the sender is correct.
• (In zero-knowledge) For each relevant PFB, check that the bytes provided match the namespaced merkle tree

There are a couple of problems that have emerged from the separation:

• A sdk.Tx that has a PFB is not allowed any other sdk.Msg
• PFBs can not use authz
• PFBs are ordered behind non PFBs thus they are dropped first instead of the lowest priority transaction
• The reshuffling messes with nonces making it difficult to have multiple transactions by the same sender in a single block.

Proposal

There are two proposals:

1. Introduce a new SignerNamespace which acts like a secondary index providing efficient lookup between signers and their blobs (map[string][]uint64 // signer -> slice of share indexes for each blob ). Rollups can find the enshrined sequencer then request all the blobs posted by share index, or alternatively, find all the blobs by a namespace and retrieve all the signers by looping through and matching any of the starting share indexes that match the location of the blob. Note that this doesn't change the size of the block but will make the square slightly bigger.
2. Add the signer field to each blob which gets encoded at the start of the first share. That way rollups need only query all the blobs for the affiliated namespace to also know the author of each blob. This option has more overhead as the signer may be repeated multiple times for each blob. This becomes more redundant in a world dominated by shared sequencers where only a handful of addresses publish most of the blobs.

Option 2 breaks the way blobs are encoded whereas Option 1 is less breaking as it uses a new namespace.

For Admin Use

• [ ] Not duplicate issue
• [ ] Appropriate labels applied
• [ ] Appropriate contributors tagged
• [ ] Contributor assigned/self-assigned

[evan-forbes]

both proposed solutions make sense

on one hand, adding some metadata to the blob #1172 would be very convienient for rollups since they already have to download the rollup namespace, and it provides a simple and immediate mechanism for filtering blobs.

that being said, if they download an index first, then it would be easy for rollups to implement arbitrary mechanisms for avoiding having to download all blobs in a namespace. That could be very useful in the case of a woods attack, or simply for being efficient.

ultimately, which mechanism is best I think would be highly dependant on how the fork choice rule for a rollup is proved. we might need to go through all known fork choice rules and walk through that process. cc @nashqueue @S1nus

[nashqueue]

With Option 1, do we add new things to the square, or do we add it to the state?

PFBs are ordered behind non PFBs; thus they are dropped first instead of the lowest-priority transaction

We can change that ordering so they are ordered first

PFBs can not use authz

Maybe not on topic here but why is that ?

[cmwaters]

With Option 1, do we add new things to the square, or do we add it to the state?

It's added to the square, not to state or to the block

We can change that ordering so they are ordered first

We could but then we have the same problem with nonPFBs (that a transaction with a higher priority could be dropped in favour of transactions with relatively lower priority)

Maybe not on topic here but why is that ?

Because you can't wrap the PFB tx with the MsgExec - we simply don't allow it. We hesitated on adding it although it would be possible, it would just break how people are used to parsing the PayForBlobNamespace

[cmwaters]

ultimately, which mechanism is best I think would be highly dependant on how the fork choice rule for a rollup is proved.

This is more concretely a question of whether we imagine rollups will have enshrined sequencers or they will be base / permissionless rollups

[cmwaters]

I think I'm slightly more in favour of option 1

[rootulp]

Thinking out loud: given option 1, if a malicious validator includes an incorrect entry in the SignerNamespace, what does a fraud proof for this behavior look like? I infer there are a few different types of malicious behavior:

Share indexes (or signer) in SignerNamespace != share indexes (or signer) in PayForBlobNamespace. A fraud proof for this behavior must include:

1. The share(s) in the SignerNamespace with the incorrect entry
2. The share(s) in the PayForBlobNamespace with the relevant PFB

Signer in SignerNamespace doesn't exist in the square. A fraud proof for this behavior must include:

1. The share(s) in the SignerNamespace with the incorrect entry
2. The entire PayForBlobNamespace

I think it's feasible to construct these fraud proofs and they are bounded in size.

[musalbas]

Thinking out loud: given option 1, if a malicious validator includes an incorrect entry in the SignerNamespace, what does a fraud proof for this behavior look like? I infer there are a few different types of malicious behavior:

Share indexes (or signer) in SignerNamespace != share indexes (or signer) in PayForBlobNamespace. A fraud proof for this behavior must include:

1. The share(s) in the `SignerNamespace` with the incorrect entry

2. The share(s) in the `PayForBlobNamespace` with the relevant PFB

Signer in SignerNamespace doesn't exist in the square. A fraud proof for this behavior must include:

1. The share(s) in the `SignerNamespace` with the incorrect entry

2. The entire `PayForBlobNamespace`

I think it's feasible to construct these fraud proofs and they are bounded in size.

When considering fraud proofs, we should try to avoid the need for every new protocol addition to require a unique type of fraud proof, but consider how this can fit into a generalized fraud proof system where there is only one type of state transition fraud proof. I think by introducing a tx index in the data root rather than the state root, option 1 may potentially break that.

Also how would the tx index actually be structured?

[musalbas]

Option 2 would involve making a new namespace version so wouldn't necessarily be breaking.

As part of this, we may want to create a new and improved namespace version with more metadata, with consultation from rollup teams

[cmwaters]

Also how would the tx index actually be structured?

It wouldn't be the tx index but the share index of the first share exactly as we have it now with the IndexWrapper that wraps the PFBs and includes an array of share indexes

[cmwaters]

Option 2 would involve making a new namespace version so wouldn't necessarily be breaking.

That's a good point, we could have blobs that include the signer and blobs that don't, so the rollups that have enshrined sequencers would use the namespace version of the blobs that include the signer

[preston-evans98]

Hey @cmwaters, sorry I'm late to the party here.

Regarding option 1, I see three pain points that we'll run into

1. Lack of domain separation: We would need to think about domain separators and whether it's possible to parse a single entry out of the SignerNamespace at random. This is important for efficiency in the zk context. Ideally, you want the prover to say, "here's the offset where your data starts, go parse it for yourself" - but without proper domain separation this is insecure.
2. (Potentially Sovereign-specific) The index you suggest is the opposite of the one that would be most convenient for us. What we care about is, "Given a blob in our namespace, who is the sender" but the index says, "given a sender, have they published any blobs in the relevant namespace". This means that rollup nodes need to download the full index and reverse it locally, which is doable but not ideal.
3. Rollups need to query two namespaces and have parsers for two different data formats. That's not a big deal, but it is a bit inconvenient.

Option 2 looks ideal from our perspective.

[nashqueue]

Add the signer field to each blob which gets encoded at the start of the first share. That way rollups need only query all the blobs for the affiliated namespace to also know the author of each blob. This option has more overhead as the signer may be repeated multiple times for each blob. This becomes more redundant in a world dominated by shared sequencers where only a handful of addresses publish most of the blobs.

Can we still create the commitment deterministically before submission? Can we create the commitment just from the blob?

[rootulp]

Great questions! For option 2:

Can we still create the commitment deterministically before submission?

Yes because the share commitment is still deterministic. It would involve adding the signer as a param to CreateCommitment.

Can we create the commitment just from the blob?

No because the signer would be needed to create the share commitment.

[nashqueue]

What is stopping the Rollup Protocol / Sequencer from putting the signer themselves as metadata into the blob? (Or any other metadata for that matter) . What are we gaining from Celestia doing it in Protocol?

[musalbas]

They might put a fake signer.

[nashqueue]

So you are getting the additional guarantee with the honest majority assumption of Celestia verifying that this blob was signed by a certain key.

[Wondertan]

What's the benefit of encoding the signer into the first share(option 2) compared to an improved API that always returns all the needed PFB metadata along the blob when a blob is requested? What if the signer is not the only thing that needs to be provided along the blob, and would the solution to that be extending the first share again?

On benefits of abstracting this separation away on the API level:

• no duplicate metadata in square(signer in this case)
• all the metadata available(not only signer)
• less majority assumptions -> less fraud proofs.

[musalbas]

This is for use cases that need some proof that the metadata is correct - eg it signed by the validator set. An API could lie about the correct metadata.

[Wondertan]

Based on ADR 11 the API would prove the inclusion of PFB and its metadata.

[musalbas]

It would require extra ZK circuitry to parse the PFBs and verify those proofs for ZK rollups, which is one of the reasons why Sovereign Labs for example is advocating to include signer directly in metadata, as they want to avoid parsing PFBs and protobuf structs inside ZK programs entirely

[Wondertan]

Wouldn't that still be necessary once we migrate to Blob inclusion proving through PFB inclusion proving? Basically blob proof will be PFB proofs. This is the direction the node team had in mind about blob improvements basing on ADR 11

Cc @nashqueue

[cmwaters]

So my understanding currently is there are two categories of users:

1. Rollup full nodes which must process all blobs on a namespace
2. Rollup light nodes which would want to verify the inclusion of their transaction in a blob. Note that with shared sequencing a rollup light node may only which to verify the inclusion of one or two shares rather than the entire blob.

For 2. we can prove blob inclusion via pfb inclusion. Is this somehow better than blob inclusion proofs? i.e. is it smaller? Is it still smaller if we only need to prove the inclusion of one or two shares?

This change is predominantly targeting case 1 whereby the fork choice rule needs to be applied and depends on knowing who the author of the blob is. There may be other data that the honest majority may validate (like gas price) but I'm not sure.

I'm now thinking that we may want to wait for further feedback that this additional information is valuable before creating a new blob version. Hence I'd propose creating a CRC/CIP for metadata that could be validated by the validator set for the rollups fork choice rule.

I think a lot of attention has been focused towards the addition of the signer field in the blob (or something to that affect) and not the first part of this proposal which is to actually remove the PFB Namespace and return to a single namespace for all txs. The reasons being:

A sdk.Tx that has a PFB is not allowed any other sdk.Msg PFBs can not use authz PFBs are ordered behind non PFBs thus they are dropped first instead of the lowest priority transaction The reshuffling messes with nonces making it difficult to have multiple transactions by the same sender in a single block.

The point is that these can be split out. We can still look to remove the PFB Namespace and implement the signer field in the blobs at a later point

[rootulp]

PFBs are ordered behind non PFBs thus they are dropped first instead of the lowest priority transaction

Based on square.Build I don't think this is the case. The lowest priority transactions should be dropped first because the list of txs passed to square.Build should be ordered by priority. If I interpret square.Build correctly, whether a transaction is PFB or non-PFB should not impact whether it is dropped.

[cmwaters]

I just had a look now and you might be right. Perhaps this was from before when we split the transactions and would process all non-pfbs before pfb transactions. It seems like square.Build adds the transactions in order that they are provided. If that is the case, I believe there is still an open issue that we can close

[cmwaters]

Update

Summarising the conversations from within this issue (and a few outside this issue), I have split this issue up into two new issues that I think better capture the two changes that have been discussed:

• https://github.com/celestiaorg/celestia-app/issues/3315
• https://github.com/celestiaorg/celestia-app/issues/3316

[rootulp]

IMO we can close this as won't do in favor of these issues:

• https://github.com/celestiaorg/celestia-app/issues/3315
• https://github.com/celestiaorg/celestia-app/issues/3316