Transactions with nonce gaps are emitted by BestTransactions when there are too many incoming transactions

[kien-rise]

Describe the bug

The broadcast channel capacity is quite big, but not big enough under heavy workload:

// crates/transaction-pool/src/pool/pending.rs
let (new_transaction_notifier, _) = broadcast::channel(200);

When the channel is full, BestTransactions will fail to listen to some incoming transactions. Unfortunately, BestTransactions assume that the incoming transactions are gapless. This causes some txs are emitted although they are not independent yet.

Event sequence

1. A BestTransaction instance is created, and listening to the incoming transactions (i.e. .no_updates() is not called).
2. Too many transactions arrive, causing the broadcast channel to be full. This happens while the speed of calling BestTransactions::next() is too slow.
3. After missing some transactions, BestTransactions receives a new one. Because the tx parent is not found, BestTransactions considers it as an independent tx:

// crates/transaction-pool/src/pool/best.rs
if self.ancestor(&tx_id).is_none() {
    self.independent.insert(pending_tx.clone());
}

4. As a consequence, transactions with nonce gaps are emitted.

Steps to reproduce

1. Add the following test to crates/transaction-pool/src/pool/best.rs.

#[test]
fn test_independent_txs_from_updates() {
    let mut pool = PendingPool::new(MockOrdering::default());
    let mut f = MockTransactionFactory::default();

    // Must be relatively larger than the broadcast channel capacity.
    // See `crates/transaction-pool/src/pool/pending.rs`.
    let num_senders = 1000;

    let first_txs: Vec<_> = (0..num_senders) //
        .map(|_| MockTransaction::eip1559())
        .collect();
    let second_txs: Vec<_> =
        first_txs.iter().map(|tx| tx.clone().rng_hash().inc_nonce()).collect();
    let third_txs: Vec<_> =
        second_txs.iter().map(|tx| tx.clone().rng_hash().inc_nonce()).collect();

    for tx in first_txs {
        let valid_tx = f.validated(tx);
        pool.add_transaction(Arc::new(valid_tx), 0);
    }

    let best = pool.best();

    for tx in second_txs {
        let valid_tx = f.validated(tx);
        pool.add_transaction(Arc::new(valid_tx), 0);
    }

    for tx in third_txs {
        let valid_tx = f.validated(tx);
        pool.add_transaction(Arc::new(valid_tx), 0);
    }

    let drained: Vec<_> = best.map(|tx| tx.transaction_id).collect();
    let count_first_txs = drained.iter().filter(|tx| tx.nonce == 0).count();
    let count_second_txs = drained.iter().filter(|tx| tx.nonce == 1).count();
    let count_third_txs = drained.iter().filter(|tx| tx.nonce == 2).count();
    println!("{:?}", (count_first_txs, count_second_txs, count_third_txs));
    assert!(count_first_txs >= count_second_txs && count_second_txs >= count_third_txs);
}

2. Run the test. It will fail:

---- pool::best::tests::test_independent_txs_from_updates stdout ----
(1000, 0, 256)
thread 'pool::best::tests::test_independent_txs_from_updates' panicked at crates/transaction-pool/src/pool/best.rs:338:9:
assertion failed: count_first_txs >= count_second_txs && count_second_txs >= count_third_txs

3. Change num_senders to 10. Re-run the test. It will pass.

Node logs

No response

Platform(s)

Mac (Apple Silicon)

What version/commit are you on?

v1.1.0

What database version are you on?

N/A

Which chain / network are you on?

N/A

What type of node are you running?

Archive (default)

What prune config do you use, if any?

No response

If you've built Reth from source, provide the full command you used

No response

Code of Conduct

• I agree to follow the Code of Conduct

[kien-rise]

Related to #12286

I link this issue to 12286 because both BestTransactions and PendingPool share similarities:

1. Both are assuming that the incoming transactions are gapless (which is false under extreme circumstances).
2. Both use the same if statement to check if an incoming transaction is independent:

if self.ancestor(&tx_id).is_none() {
    self.independent.insert(pending_tx.clone());
}

3. Both issues cause "nonce too high" warnings, directly or indirectly.

[github-actions]

This issue is stale because it has been open for 21 days with no activity.

[github-actions]

This issue was closed because it has been inactive for 7 days since being marked as stale.