Efficient solution to verify kernel uniqueness + better absolute timelocks

Following DM discussions with someone and @david, I want to speak about potential DOS vectors introduced by the kernel uniqueness scheme and the tx expiry it requires if we put a cap at consensus level on the maximum relative_height accepted.

As it was mentioned by @Tromp and @david, a first fix to DOS would be that one would need to make validating nodes refuse all txs that are broadcasted and that are about to expire (it can happen if the two signers set signature_block_height equal to a block height of the past, typicall close to current_block_height - relative_max) so that those txs don’t make it to the mempool and don’t make node crash because mempool has too much tx. This is very important as nodes crashing could result in particualar in some miners being unable to mine and could hence diminish network security quite a lot, which is really bad.
This fix fully fixes DOS vector introduced by txs expiring when blocks are not full.

However there might be DOS vector introduced by tx expiring more difficult to fix if blocks are full and that the blockchain is heavily used.

The reason for that is that an attacker could broadcast many txs with low fees (but just sufficiently high to be accepted to the mempool) such that he fills up something like 90% of the mempool. Honest people doing honest txs will set their tx with normal fees and those txs could occupy the top 10% of the mempool.
With a bit of luck, the cost of the DOS attack when blocks are full will be very low for the attacker as most of his txs will end up being refused due to top 10% being accepted and attacker’s transactions expiring after the two weeks.
This is not guaranteed to be cheap, since if the blockchain sees less usage in the coming two weeks, then all the DOS txs will end up on the blockchain and the DOS cost would be basically the same as a blockchain which doesn’t use expiring txs, but if usage continues to be massive, then the attacker might be able to have most of his txs not making it to the blockchain resulting in a very low cost DOS attack, which is not good.

The fix for this might be a slightly more complex mempool management, but I dont know yet how to exactly do that. @david thinks it is possible, but my naive intuition says that I don’t know if it can be done really clean and cover all cases such that DOS threat model becomes essentially the same to that one of a blockchain without tx expiry.

Otherwise, there is a full fix, as specified in an earlier post, where one could still use my scheme to check kernel uniqueness quite efficiently without having expiring txs (for this, as I mentioned, you need to get rid of the max relative_height allowed and accept all relative heights, and treat onchain kernels that have a large relative_height due to having waited a long time before making it to the blockchain in a separate list, likely very small, while applying the same uniqueness algorithm allowed by the scheme for kernels with relative_height smaller than the given fixed threshold (set by wallet))