Consider treating namespaced padding as blobs or sequences

[evan-forbes]

With the non-interactive defaults, we introduced padding between messages. Per the original specs Caveats section of Message Layout Rational, these are described as

[Namespaced padded shares] have a value of zero and a namespace ID equal to the preceding message's. Since their value is known, they can be omitted from NMT proofs of all shares of a given namespace ID.

We should consider updating the implementation and specs to treat the each section of padding as individual messages. This will prepend an info byte along with a length delimiter.

edit: While the added bytes would break the second property,

Since their value is known, they can be omitted from NMT proofs of all shares of a given namespace ID.

this might mean that light clients could skip these shares entirely when parsing a namespace.

[musalbas]

Afaik this would only break the second property for the first padding share, as it has different message lengths. However, the length of the padding should also be transmitted in the p2p layer regardless of this change, so I think it doesn't break the second property at all.

[rootulp]

this might mean that light clients could skip these shares entirely when parsing a namespace.

In order for this to be the case, additional metadata must be added to the share so that a client can differentiate between a sequence of namespaced padding shares and a sequence of shares with 0 data. See #1136

[musalbas]

Assuming that all padding shares have a start indicator of 1, and data len of 0, then shouldn't you be able to differentiate padding shares from non-padding shares, because only padding shares can have a start indicator of 1 and data len of 0?

[rootulp]

Good point. celestia-app denies blob sizes of 0 here so it is possible to treat a share with a sequence start indicator of 1 and a sequence length of 0 as a namespaced padding share.

Pros:

• an additional reserved bit is not needed

Cons:

• prevents us from writing a sequence length for the number of padding bytes that follow to the first namespaced padded share. I briefly considered that option so that clients could read the first namespaced padded share and learn how many padding shares followed and potentially skip downloading them. An alternative optimization with similar benefit may be possible because a namespaced padded share has a variable namespace id and constant contents.

[musalbas]

prevents us from writing a sequence length for the number of padding bytes that follow to the first namespaced padded share. I briefly considered that option so that clients could read the first namespaced padded share and learn how many padding shares followed and potentially skip downloading them. An alternative optimization with similar benefit may be possible because a namespaced padded share has a variable namespace id and constant contents.

I think they can learn that using the method described in: #1136 (comment) (cc @adlerjohn)

Consider a model where a full storage node does not send padding shares to a rollup light node over the wire, but simply tells them "hey, shares between index x to y are padding, and here's the sub-tree root of those shares". The light node can then recompute the sub-tree root of those padding shares itself, to authenticate that statement.