Decide on a mechanism to pick square size and communicate that to the app

[evan-forbes]

Summary

We need to decide on exactly where and how the square size is determined, along with how that size communicated between celestia-core and celestia-app. This is necessary for the app to arrange messages in the in the square.

Problem Definition

Per the spec, users actually sign over multiple SignedTransactionDataPayForMessage when they want to submit a single message. The reason being that the commitments to the message that the transaction is paying for could change depending on the square size for the block. The user therefore submits multiple signatures for different potential square sizes in order to ensure that one will be valid for whatever the square size ends up being for the upcoming block.

The app has to have a way of knowing the square size for a block so that it can pick which signature, and which version of SignedTransactionDataPayForMessage, should be passed back to celestia-core during PreProcessTxs.

This is a bit more complicated than it sounds, as optimally selecting the size and filling the square would require access to the mempool and being aware of the scheme mentioned in the first paragraph. celestia-core has access to the mempool, but is completely unaware of the types of transactions (staking, transfers, SignedTransactionDataPayForMessage, etc), let alone the scheme described in the above paragraphs, whereas the app is aware but doesn’t have direct access to the mempool.

While celestia-core should at least be able to estimate how many transactions could fit in the largest square size, it would have to be very conservative in that estimate as the current PreProcessTxs method has no way of knowing which transactions have and have not been processed. This could become a bigger issue when using non-interactive defaults, as more padding space will be necessary to accommodate large transactions.

Proposal

Modify PreProcessTxsRequest to include the square size

message RequestPreprocessTxs {
  repeated bytes txs = 1;
  uint64 square_width = 2;
  uint64 cursor = 3;
}

Modify PreProcessTxsResponse to include unprocessed Txs

message ResponsePreprocessTxs {
  repeated bytes            txs      = 1;
  tendermint.types.Messages messages = 2;
  repeated bytes   unprocessed_txs   = 3;
  uint64 cursor = 4;
}

This way, celestia-core only has to know if it has enough transactions in the mempool to probably justify using the largest square. If not, then select a smaller square size. Whatever square size is chosen by celestia-core is passed to the app via PreProcessTxsRequest, and let the app process messages using the provided square size. If there are leftover transactions, the app returns unprocessed transactions that can be re-inserted into the mempool. If there are no left over transactions, then celestia-core can reap more transactions and repeat the process (first described here #77).

An implementation of this proposal would also close #77

edit: A major con of taking this approach is that it makes this fork's version of the ABCI less general, along with deviating further from tendermint

Implementation

If this proposal is approved, the celestia-core and celestia-app portions should likely be developed in tandem due to their tight coupling.

[liamsi]

Wow, thanks for this! We should think this through carefully (also in the light of that abci++ will land eventually in tendermint, there Block.Data is passed in and returned) but this issue is exemplary.

[evan-forbes]

relevant proposal #7750

[evan-forbes]

this was completed in celestiaorg/celestia-app#224 and celestiaorg/celestia-app#231