[Bug] consensus: duplicate input detection missing in non-bitcoinkernel validation path

[R27-pixel]

Describe the bug

Duplicate inputs are handled differently depending on whether the bitcoinkernel feature is enabled.

With bitcoinkernel enabled, duplicate inputs are naturally rejected because spent UTXOs are removed from the map during script verification. However, in the default non-bitcoinkernel path, verify_transaction() validates inputs using get_utxo(), which only performs a .get() lookup and does not consume the entry.

This means the same OutPoint can be referenced multiple times within the same transaction and its value counted multiple times toward in_value.

---

Steps to Reproduce

1. Build Floresta without the bitcoinkernel feature enabled
2. Construct a transaction containing two identical inputs spending the same OutPoint
3. Pass the transaction through verify_transaction()
4. Observe that both inputs successfully fetch the same UTXO through get_utxo()

---

Expected behavior

Duplicate inputs should be rejected consistently across all build configurations, matching Bitcoin Core's CheckTransaction() behavior for duplicate input handling (CVE-2018-17144).

---

Build environment

master branch, non-bitcoinkernel build

---

Additional context

Relevant code paths:

Non-bitcoinkernel path:

let utxo = Self::get_utxo(input, utxos, txid)?;

match utxos.get(&input.previous_output)

bitcoinkernel path:

utxos.remove(&input.previous_output)

There are currently two possible approaches being discussed:

1. Add explicit duplicate input detection in check_transaction_context_free()
2. Change the non-bitcoinkernel path to consume UTXOs with .remove() instead of .get()

This was identified and discussed in PR #979.

[jaoleal]

@R27-pixel Thanks! Much appreciated for describing the problem.

This issue made me remember that our unit tests are not extensive as our integration tests are, perhaps we could introduce integration tests for each feature combination ? cc @Davidson-Souza @csgui

Also, im not sure if we have anything exercising double input spend, perhaps that could be introduced together with the fix for this problem ?

[R27-pixel]

Thanks @jaoleal !

Regarding duplicate input / double-spend coverage --PR #979 already includes a test_duplicate_inputs_rejected test which constructs a transaction with two identical inputs spending the same OutPoint and verifies it gets rejected.

The broader point about integration tests across feature combinations also makes sense. I’d be happy to help contribute there as well once the fix direction for this issue is decided.

[Davidson-Souza]

The solution proposed in #979 is to build a hash set with the inputs, and if we try to add something that's already there, it must be a duplicate. The problem with this approach is exactly having to build a whole hashset of inputs each block.

My suggestion was to move the UTXO removal out of the gated code. The only downside is that we would only get this check way down the line.

One thing that would be nice is to figure out how harder it wold be with the hash map, maybe it's fine and we don't need to worry about it, or maybe it's too expensive and we should avoid it. Rn we are working with abstracts and assumptions.

[R27-pixel]

The solution proposed in #979 is to build a hash set with the inputs, and if we try to add something that's already there, it must be a duplicate. The problem with this approach is exactly having to build a whole hashset of inputs each block.

My suggestion was to move the UTXO removal out of the gated code. The only downside is that we would only get this check way down the line.

One thing that would be nice is to figure out how harder it wold be with the hash map, maybe it's fine and we don't need to worry about it, or maybe it's too expensive and we should avoid it. Rn we are working with abstracts and assumptions.

I agree , i can try putting together a small Criterion benchmark for both approaches so we can compare the overhead more concretely.

[JoseSK999]

Question: shouldn't Utreexo proofs protect us from duplicate inputs as we can't remove it twice from the acc? @Davidson-Souza @luisschwab @jaoleal @moisesPompilio

Also in SwiftSync we verify non-duplication, but it's only checked at the very end. Ideally we reject these bad transactions early via the context-free check in SS, and also for the mempool. And it's nice to mirror Core's CheckTransaction.

Maybe a helper like this, and call it in check_transaction_context_free?

    fn has_duplicate_inputs(inputs: &[TxIn]) -> bool {
        match inputs.len() {
            1 => false,
            2 => inputs[0].previous_output == inputs[1].previous_output,
            _ => {
                let mut seen = HashSet::with_capacity(inputs.len());
                for input in inputs {
                    if !seen.insert(&input.previous_output) {
                        return true;
                    }
                }
                false
            }
        }
    }

It's crazy that over 80% of transactions have only one input (according to https://mainnet.observer/charts/transactions-1in/), and so doing the above check should cover ~90% of transactions cheaply without allocating a hashset.

[JoseSK999]

Benched the duplicate input check on my old computer, by iterating through all transactions in our two test blocks and calling has_duplicate_inputs:

Naive HashSet check

• Block 866,342 (normal-looking): ~595 µs
• Block 367,891 (many inputs): ~587 µs

Optimized check

• Block 866,342 (normal-looking): ~102 µs
• Block 367,891 (many inputs): ~536 µs

Adding a 3-input equality check saves only 6-7 µs, so doesn't seem to be worth it.

So we shouldn't expect this to slow down block validation by more than 0.5 ms in the worst case.

[R27-pixel]

Thanks @JoseSK999 for putting together the benchmark and the optimized helper .

The numbers look pretty good. Even in the worst case we're looking at roughly ~0.5 ms per block, and the common 1-input case doesn't need any allocation at all.

I also like the helper; it feels cleaner than the version I originally put in PR #979.

I'll wait for more thoughts from other maintainers on whether the preferred direction is the helper in check_transaction_context_free() or moving the UTXO removal out of the gated path.
@Davidson-Souza @jaoleal

[jaoleal]

@R27-pixel did you managed to provoke any double spend without the bitcoin kernel feature ?

[R27-pixel]

@R27-pixel did you managed to provoke any double spend without the bitcoin kernel feature ?

Not yet; I noticed the issue by reading the code paths but haven't made a standalone reproducer yet.

This week, I'll work on a concrete test case and report the results back in the issue.

[R27-pixel]

@R27-pixel did you managed to provoke any double spend without the bitcoin kernel feature ?

Not yet; I noticed the issue by reading the code paths but haven't made a standalone reproducer yet.

This week, I'll work on a concrete test case and report the results back in the issue.

Yes, I was able to reproduce the behavior with a concrete test.

Test setup:

• UTXO value: 1,000,000 sats
• Transaction: two inputs spending the same outpoint, one output of 1,999,999 sats

Without the duplicate-input check, the test fails because verify_transaction() accepts the transaction:

assertion failed: result.is_err()

The reproducer is:

#[test]
fn test_duplicate_inputs_double_counts_in_value() {
    let outpoint = dummy_outpoint();
    let utxo_value = 1_000_000;

    let mut utxos = HashMap::new();
    utxos.insert(
        outpoint,
        UtxoData {
            txout: txout!(utxo_value, ScriptBuf::new()),
            is_coinbase: false,
            creation_height: 0,
            creation_time: 0,
        },
    );

    let tx = build_tx(
        vec![txin!(outpoint), txin!(outpoint)],
        vec![txout!(1_999_999, ScriptBuf::new())],
    );

    let result = Consensus::verify_transaction(&tx, &mut utxos, 0, false, 0);

    assert!(result.is_err());
}

With the duplicate-input check reintroduced, the same test passes and the transaction is rejected:

test test_duplicate_inputs_double_counts_in_value ... ok
test test_duplicate_inputs_rejected ... ok

With both implementations tested:

• The original HashSet-based check from PR Duplicate input detection #979 rejects the transaction and both tests pass.
• @JoseSK999's optimized has_duplicate_inputs() helper also rejects the transaction and both tests pass.

[Davidson-Souza]

Benched the duplicate input check on my old computer, by iterating through all transactions in our two test blocks and calling has_duplicate_inputs:

Naive HashSet check

• Block 866,342 (normal-looking): ~595 µs
• Block 367,891 (many inputs): ~587 µs

Optimized check

• Block 866,342 (normal-looking): ~102 µs
• Block 367,891 (many inputs): ~536 µs

Adding a 3-input equality check saves only 6-7 µs, so doesn't seem to be worth it.

So we shouldn't expect this to slow down block validation by more than 0.5 ms in the worst case.

What's the baseline?

[JoseSK999]

What's the baseline?

I didn’t bench check_tx_context_free. My bench was for the added cost of has_duplicate_inputs per block. So whatever is the time for a full block check, add ~0.1 ms to it. We should bench it.