feat: Add number of tail padding shares to the header

[evan-forbes]

There will usually be some number of tail padding shares included in the original data square mainly due to the fact that the square size is always a power of two. Since tail padding shares are already known, there's no reason for the light clients to sample these shares (or potentially rows).

We should therefore include either the number of non tail padding shares or the number of tail padding in the header, so that light clients can optimize sampling. This will require changes to the PrepareProposal method, along with keeping track of the number of tail padding shares when creating the square. There will also need to be an additional check in ProcessProposal, to ensure that the number included in the header is actually accurate.

Since we're adding a field to the header, and adding a block validity rule on that new field, this change is consensus breaking. It is a also a good opportunity to figure out how to preserve compatibility of old headers and new headers if we ever include this change in an upgrade to mamaki.

[adlerjohn]

Could the new field be added to the DAH instead of the header proper?

[evan-forbes]

We could, but do we need to include it in the header hash?

continuing our sync conversation:

could most of the benefit be implemented by the light client by hardcoding the row root for a row full of tail padding?

I think this is especially relevant if we don't include this tail padding number in the header hash, otherwise the light client cannot rely on it and has to check for the row roots themselves.

[adlerjohn]

Hm I see your point. That would allow entire rows that are padding to be elided by implementations. But it wouldn't work for rows that aren't entirely padding. Still could be pretty good.

[liamsi]

Could the new field be added to the DAH instead of the header proper?

Is the reason to include this in the DA header that it is a number per row actually instead of a total number of orig shares used? Or simply because it would be more orderly (as it belongs to the DA header in some sense).

[adlerjohn]

It's the total number of original shares used.

It's a suggestion mostly because it wouldn't involve changing the Tendermint header, but only the Celestia-specific DAH which already has modification logic.

Note that if we do include it in the DAH then any proofs against the data root would be required to provide that field.

[liamsi]

My intuition is that it's cleaner to include the field in the header instead but need to think this through 🤔

[evan-forbes]

could most of the benefit be implemented by the light client by hardcoding the row root for a row full of tail padding?

per a synchronous discussion, we think we can most of the benefit by hardcoding roots of full rows of tail padding for different square sizes in the light client, so I'm closing this for now.

pls reopen if we thing differently cc @liamsi