As I was pondering all the potential ways an adversary might abuse the fact that finding a good chunking/linearization can take time (even if it’s polynomial), the following idea struck me: why don’t we allow/expect someone submitting a cluster of transactions that conflicts with some mempool txns (RBF) or that improves the mempool diagram (CPFP) to show this improvement themselves by also submitting a chunking/linearization of all affected txs?
While we have been discussing in this thread that it is absolutely possible to calculate an optimal chunking in reasonable time, it might still be a burden to do this for every adversarially submitted tx on low spec hardware. But most txns don’t need this at all, and for those that do, Core could offer to do it locally and then forward this linearization with the txns. Checking if it really improves the status quo should be possible in linear time and in particular shouldn’t be harder than what is checked now.
There are surely encodings for such chunkings that add negligible space overhead to the transactions themselves.