Adopt Reaping from the mempool to max square size

liamsi commented 3 years ago

Summary

Current mempool.ReapMaxDataBytes logic doesn't seem like the right approach for LL core as we need to reap as many Tx as shares would fit into the max square size.

Problem Definition

The current mechanism needs to be based on the max square size instead of gas only: https://github.com/lazyledger/lazyledger-core/blob/6d99bdda1b59d1b1e5b6c83635ad879bfdffb19e/state/execution.go#L103-L110

Proposal

One rough idea @adlerjohn and I talked about is the following approach:

reap as many tx from the mempool that would definitely fit into the max square size and then
figure out a smallest square that fits all shares
if it doesn't fit (because of padding), double the square size and try again

This probably terminates after one or two iterations but it would be could if can formalize this a bit further and have small proof for the upper bound of iterations.

ref: https://github.com/lazyledger/lazyledger-specs/pull/79

liamsi commented 3 years ago

In this context we also need to reserve space for the intermediate state roots: Copied from: https://github.com/lazyledger/lazyledger-core/pull/83#discussion_r513535480

evan-forbes commented 2 years ago

relevant proposal #7750

evan-forbes commented 7 months ago

the current approach to this is do reap more txs than can fit in the block assuming that most of them are still valid, so I think we can close this issue

celestiaorg / celestia-core