design and re-implement verification of transactions in a block

[noot]

with #137, we are now using the rust sequencer. however, the transaction verification was removed to be done with this task.

Summary:

• when pulling transactions from DA in the conductor, we need to be able to verify that these transactions were truly the ones included in their respective block (ie no extra/missing txs).
• the block header contains data_hash, which is a merkle root of all the transactions in a block.
• note that a sequencer transaction can contain multiple "actions", thus a single sequencer tx can act on multiple rollups.
• we want to separate and write each rollup's data to a different DA namespace, so the conductor doesn't need to pull the entire block's data to verify it.
• thus, we need to design a method which satisfies the above conditions, and ideally does not result in writing a lot of duplicate/extra data.

Possible solutions:

1. trivial solution is to force the conductor to pull the entire block's txs and reconstruct the merkle root to verify. not ideal.
2. write every tx that contains an action for "rollup A" to the namespace for rollup A and include a merkle proof of inclusion for each tx. not ideal, as it can result in duplicating data, for example in a tx contains data for rollup A and rollup B, then the tx will be written to 2 namepsaces. also too many merkle proofs + data there.
3. do the same duplication/sorting put on the block proposer side, inside the sequencer node, such that the txs that end up in a block are actually meta-txs, each of which contain all txs with data for a specific rollup. also can result in duplicate data, same case as above, but results in only 1 merkle proof per rollup instead of per tx.
4. do the sorting on the block proposer side, create a commitment to the batch of txs with data for a specific rollup, and put that as a special "transaction" type inside a block. then, the flow will be: a. conductor fetches batch of data for its rollup + the special "commitment transaction" + merkle proof of commitment tx inside data_hash b. re-calculates and verifies the commitment using its batch of data c. verifies that the commitment was included inside the block's data_hash this seems like a good solution, but we'll need to update the application validator logic to verify that the commitment txs are valid commitments before voting yes for that block.
5. we fork tendermint and add these commitments to the header structure, or we update the way data_hash is constructed - don't think we want to or need to go this route though

[joroshiba]

I see this problem as being fundamentally similar to once Celestia has had to solve: how do you prove that a portion of the data is all of that portion of the data.

Celestia has created namespaced merkle trees for this purpose, what we call a chainid is fundamentally what they call a namespace. It seems to me that given we have the same problem, the same basic solution is probably the correct way forward? I also think this is broadly similar to your idea #4.

We should sync with some Celestia folks on this, in the short term we might want to do the dumb #1 as holdover