When we can agree on a mempool sorting order, we can just confirm first n-transactions (or 80% of transactions) that are at least 10 minutes old. Then, we can transfer (broadcast) the block header and a hash to the set of all confirmed transactions.
Just consider this as an aggressive version of BIP152, compact blocks.
This kind of method will work for transactions of any size; both confirming 10 transactions and 1 million transactions are the same.
What's missing? Why are we not doing 'confirmation' like this?
For example, if we have 1000 transactions in a mempool (sorted), 900 transactions are at least 10 minutes old, and we're confirming the first 720 transactions.
This may not be a perfect or complete solution, but we just need to find,
- Sort order; fee, size, etc.
- Transaction age; say, 10 min
- Confirm size; say, confirm first 80%
Note: Sort order is based on f(trxn-meta-data; fee, input, output, etc.), transaction age is used as a filter. Another filter is first x% of the set.