Inconsistent KeychainTxOutIndex state after db reload

[buffrr]

Describe the bug

In wallets with slightly larger derivation gap, outputs spent at a higher derivation index are recognized inconsistently. After loading the wallet from sqlite, a spent output may be incorrectly reported as unspent leaving the wallet in unusable state. This appears to happen because KeychainTxOutIndex isn't consistently persisted/restored from the sqlite backend.

To Reproduce

Tricky to reproduce! Here's a test using the higher level Wallet which consists of two transactions:

1. tx1 creates some outputs with different gaps
2. tx2 spends an output with a larger gap.
3. Initially, wallet ignores the output with the larger gap, and it doesn't track its spend in tx2.
4. After calling Wallet::load, the wallet recognizes that output (it didn't previously). It's also incorrectly marked as unspent (because it didn't initially track the spend in tx2).

#[test]
fn test_inconsistent_last_revealed_index_after_reload() {
    let mut conn = Connection::open_in_memory().expect("memory db");
    let mut wallet = Wallet::create(
        "tr(tprv8ZgxMBicQKsPd3krDUsBAmtnRsK3rb8u5yi1zhQgMhF1tR8MW7xfE4rnrbbsrbPR52e7rKapu6ztw1jXveJSCGHEriUGZV7mCe88duLp5pj/86'/1'/0'/0/*)",
        "tr(tprv8ZgxMBicQKsPd3krDUsBAmtnRsK3rb8u5yi1zhQgMhF1tR8MW7xfE4rnrbbsrbPR52e7rKapu6ztw1jXveJSCGHEriUGZV7mCe88duLp5pj/86'/1'/0'/1/*)",
    )
        .network(Network::Regtest)
        .create_wallet(&mut conn)
        .expect("wallet");

    // Create some outputs with different gaps
    let funding_tx = Transaction {
        version: bitcoin::transaction::Version::TWO,
        lock_time: LockTime::from_consensus(1),
        input: vec![],
        output: vec![
            TxOut {
                value: Amount::default(),
                script_pubkey: wallet.peek_address(KeychainKind::External, 1).script_pubkey(),
            },
            TxOut {
                value: Amount::default(),
                script_pubkey: wallet.peek_address(KeychainKind::External, 45).script_pubkey(),
            },
            TxOut {
                value: Amount::default(),
                script_pubkey: wallet.peek_address(KeychainKind::External, 6).script_pubkey(),
            },
            TxOut {
                value: Amount::default(),
                script_pubkey: wallet.peek_address(KeychainKind::External, 20).script_pubkey(),
            },
        ],
    };

    // Spend second output
    let spending_tx = Transaction {
        version: bitcoin::transaction::Version::TWO,
        lock_time: LockTime::from_consensus(1),
        input: vec![TxIn {
            previous_output: OutPoint {
                txid: funding_tx.compute_txid(),
                vout: 1,
            },
            ..Default::default()
        }],
        output: vec![TxOut::NULL],
    };

    let block = Block {
        header: Header {
            version: Default::default(),
            prev_blockhash: genesis_block(&params::REGTEST).block_hash(),
            merkle_root: TxMerkleNode::all_zeros(),
            time: 0,
            bits: Default::default(),
            nonce: 0,
        },
        txdata: vec![funding_tx, spending_tx],
    };

    wallet.apply_block(&block, 1).expect("apply block");
    wallet.persist(&mut conn).expect("persist");
    let unspent_before = wallet.list_unspent().count();
    println!("last revealed index before: {:?}", wallet.spk_index().last_revealed_index(KeychainKind::External)) ;


    // Reload wallet
    let wallet = Wallet::load()
        .load_wallet(&mut conn)
        .expect("wallet found")
        .expect("load wallet");

    let unspent_after = wallet.list_unspent().count();
    println!("last revealed index after: {:?}", wallet.spk_index().last_revealed_index(KeychainKind::External)) ;

    assert_eq!(
        unspent_before,
        unspent_after,
        "Unspent output count should be the same before and after reload"
    );
}

Output

last revealed index before: Some(20)
last revealed index after: Some(45)

Unspent output count should be the same before and after reload
Left:  3
Right: 4

Expected behavior

As the test shows, the wallet should at least consistently ignore it. If it's not tracking it initially, it shouldn't track it after reload.

[ValuedMammal]

I haven't fully grokked where the issue might have originated, but I'm a little confused about the use of peek_address though I realize this is a slightly simplified example. I assume under normal operation you are revealing addresses before receiving a payment right?

[buffrr]

I assume under normal operation you are revealing addresses before receiving a payment right?

I was thinking there may have been large gaps from handing out too many addresses but I just checked, and the largest gap in that wallet was only 3 addresses.

I haven't fully grokked where the issue might have originated

I suspect the logic assumes txs are included following the order of derivation index, but that’s not always true. Sorting outputs by chain position confirms this (derivation indexes are not sequential and have larger gaps confusing the wallet perhaps).

Interestingly, if you modify the test to reorder txouts by derivation index, the issue disappears.

[notmandatory]

Can this be reproduced with a non-memory, db file persistence? Sqlite has some strange behavior when using the memory store.

[buffrr]

I first encountered this issue with db file persistence, but the test uses an in-memory db for convenience. Same test also reproduces with file db