Fast-failure for redundant transactions in the mempool

[nfrisby]

The design of the TxSub mini protocol would be simplified if it were effectively costless for the mempool to reject redundant transactions.

This task is to ensure that in the MEMPOOL rule.

[nfrisby]

This PR from Esgen captures some initial measurements IntersectMBO/ouroboros-consensus#1358; showing that some txs take milliseconds to be rejected when they are already in the mempool.

[nfrisby]

My current plan:

1. Talk with Ledger to discuss the rules checking for TxIn presence/absence ASAP. (Esgen broke the ice with this Slack message in the ledger channel which has so far been unanswered.
2. If not and/or in the meantime, short-circuit to a synthetic error (ie a BadInputsUTxO predicate failure for each TxIn) when the tx is already in the mempool.

[nfrisby]

Early discussions (in that same Slack thread) indicate that Ledger is open to the idea. Their initial feedback was that:

• the Ledger rules currently report all failures, not just the first (which is useful for txs received over the local node-to-client connection, but probably overkill otherwise)
• in a short-circuiting mode (eg for reapply), it'd be an involved effort for Ledger to move the UTxO lookups to the first stage of the validation (which is relevant since that's the only way "redundant" txs are invalid)

[nfrisby]

In light of that response from Ledger (conceptual approval, but changing the implementation would be laborious), me, Esgen, Karl, and Marcin have adopted this plan for this Issue.

• Restrict the UTxO set down to just the transaction's necessary UTxO before validating each transaction. Note that this is exactly what UTxO HD is physically required to do (and so the Ledger already exposes the appropriate function from transaction to Set TxIn).
• If that restriction fails, short-circuit with the BadInputsUTxO predicate failures.
• If the restriction fully succeeds, use the ledger state with that restricted UTxO map to validate the transaction, thereby avoiding duplication of the lookup costs.

cc @lehins

[lehins]

@nfrisby This plan is not exactly accurate.

The reason why it is not accurate is because the set of required UTxO is dependent on the validity of the transaction. Whenever transaction is flagged as invalid with respect to 2-phase validation then it is totally ok not to have all of the inputs or reference inputs.

In any case I would advise against duplicating ledger logic in consensus in order to work around some issue. I'd suggest us trying to come up with the solution for this problem in ledger rules instead.

[nfrisby]

After our discussions, @lehins , I think we agree that this fast-fail rule is sound, and it should be implemented in the MEMPOOL ledger rule (if any of the transaction's TxIn are missing, immediately fail with just those "missing txin" PredicateFailures).

So I'm transferring this Issue to the cardano-ledger repo.