Better tests for transaction conflict handling.

[evanlinjin]

Describe the enhancement

This continues on the work suggested in ticket #985 and implemented in #964.

However, I realized that it is tedious to construct TxGraph histories, making it difficult to test multiple scenarios without an overwhelming amount of code. I suggested a TxTemplate structure in #964 (comment):

struct TxTemplate<'a, K> {
    pub tx_name: &'a str,
    pub spends: &'a [(&'a str, usize)], // (tx_name, vout)
    pub outputs: &'a [TxOutTemplate<K>],
    pub anchors: &'a [(u32, BlockId)],
    pub last_seen: Option<u64>,
}

struct TxOutTemplate<K> {
    pub value: u64,
    pub owned_spk: Option<(K, u32)>, // some = derive a spk from K, none = random spk
}

fn init_graph<'a, K: 'a>(
    descriptors: HashMap<K, Descriptor<DescriptorPublicKey>>,
    tx_templates: impl IntoIterator<Item = TxTemplate<'a, K>>,
) -> (
    IndexedTxGraph<ConfirmationHeightAnchor, KeychainTxOutIndex<K>>,
    HashMap<&'a str, Txid>,
) {
    todo!()
}

Alongside this, we need a Scenario structure to describe the specific scenario we are testing, and the expected results of various calls to bdk_chain structure methods (this is how we should that the final state is expected).

struct Scenario<'a> {
    /// Name of the test scenario
    name: &'a str,
    /// Transaction templates
    tx_templates: &'a [TxTemplate],
    /// Names of txs that must exist in the output of `list_chain_txs`
    exp_chain_txs: HashSet<&'a str>,
    /// Outpoints of UTXOs that must exist in the output of `filter_chain_unspents`
    exp_unspents: HashSet<(&'a str, u32)>,
    /// Expected balances
    exp_balance: Balance,
}

Scenarios

• 2 unconfirmed txs with different last_seens conflict. The most recent tx should be the only tx that appears in the list methods.
• 3 unconfirmed txs with different last_seens conflict. The most recent tx should be the only TX that appears in the list methods.
• An unconfirmed tx U conflicts with a tx anchored in orphaned block O. O has higher last_seen. O should be the only tx that appears in the list methods.
• An unconfirmed tx U conflicts with a tx anchored in orphaned block O. U has higher last_seen. U should be the only tx that appears in the list methods.
• Multiple unconfirmed txs conflict with a confirmed tx. None of the unconfirmed txs should appear in the list methods.
• B and B' conflict. C spends B. B' is anchored in best chain. B and C should not appear in the list methods.
• B and B' conflict. C spends B. B is anchored in best chain. B' should not appear in the list methods.
• B and B' conflict. C spends both B and B'. C is impossible. Try this with only B confirmed vs only B' confirmed vs none confirmed.

Further work

Our current structures do not handle unconfirmed conflicts properly when the conflicting transactions have the same last_seen timestamp (thanks to @rajarshimaitra for pointing this out).

bdk/crates/chain/tests/test_indexed_tx_graph.rs

Lines 692 to 695 in fe7bba1

	// FIXME: Currently both the mempool tx are indexed and listed out. This can happen in case of RBF fee bumps,
	// when both the txs are observed at a single sync time. This can be resolved by checking the input's nSequence.
	// Additionally in case of non RBF conflicts at same `seen_at`, conflicting txids can be reported back for filtering
	// out in higher layers. This is similar to what core rpc does in case of unresolvable conflicts.

I propose we deal with this as follows:

When two unconfirmed txs conflict, but have the same last_seen, we can check the input's sequences (using RBF rules). Otherwise, we sort by feerate (if possible). We fallback to lexicographical sorting of txids.

[evanlinjin]

@LagginTimes is currently still working on this.

[danielabrozzoni]

When two unconfirmed txs conflict, but have the same last_seen, we can check the input's sequences (using RBF rules).

Why would you look at the input sequence? Are you trying to understand which tx got broadcasted first, and assuming that people are signing with fee sniping protections?
I think we should just look at the feerates, that's the only thing that matters in the end. #mempoolfullrbf