FWIW, I lightly convinced myself that trying to find the best subset of a proposed package is probably too hard (ie, depends on the state of all affected clusters in the mempool, and if replacement is involved, there’s no nice greedy way of working out which part to try first).
So in that case, I think maybe something like this could work?
- Get a proposed package from a peer. Resolve any missing parents. Try adding it to your mempool atomically via the method described at the top of this thread – if it evicts something it shouldn’t, that’s fine – two steps forward, one step back still adds up to one step forward.
- Update your clusters, relinearise, do cheap optimisations.
- Relay the newly added transactions (individually) to your peers.
- If any of your peers ask for you to give them an “ancestor” package for a tx
T, find the chunk thatTis in, and give them a package containing all the txs in that chunk as well as all those txs’ in-mempool ancestors. (Then they do the same thing, and repeat)
I think that approach would minimise the spread of unnecessary-evictions, while also being fairly simple. Changing “ancestor” packages to “chunk” packages is a bit hand-wavy, but I don’t think requires different messages compared to the current bip 331 draft?
Push-relay of chunk packages might allow you to propagate hard-to-find optimal chunks across the network though. One way to get “infinite computation” might be to use the p2p network as a distributed system – each node picks a random cluster that’s near the top of the mempool to optimise every now and then, and if they find something good, they spread it out to everyone.