bdk Clearly define and document `stop

When reviewing #1225 I noticed that the definition of stop_gap we currently use is different from the one I had in mind. In any case, we should clearly define it and document it.

The PR fixes a bug and then adds a gap limit test. In the test, we generate 10 spks, and then we send sats on the 4th one (spks[3]). What is the minimum gap limit we should use in order to see the transaction?

The test currently doesn't find any transaction with stop_gap = 2, but does find a transaction with stop_gap = 3. I think this is wrong. If we define the stop gap as "the maximum number of consecutive unused addresses" (as electrum does https://electrum.readthedocs.io/en/latest/faq.html#what-is-the-gap-limit) (and also btcpayserver, it seems? https://docs.btcpayserver.org/FAQ/Wallet/#the-gap-limit-problem), I think stop_gap = 3 shouldn't find the tx, but stop_gap = 4 should:

With stop_gap = 3, we search spk0, spk1, spk2, none of this contain a tx, and since 3 is the maximum number of consecutive unused addresses, we stop
With stop_gap = 4 we search spk0, spk1, spk2, spk3, we find the transaction, and then we continue searching until we stop at spk7 (included)

Also, with this definition, stop_gap should be always nonzero I think? As, if you use stop_gap = 0 and check spk0 and it doesn't have any tx, you have checked one unused address, and violated the definition (0 should be "the maximum number of consecutive unused addresses" ).

Does this make sense?

Nov 24 '23 12:11 danielabrozzoni

Concept ACK. This is indeed what my mental model of the stop gap is; I didn't know it wasn't what was in the code.

Nov 24 '23 20:11 thunderbiscuit

Yes Concept ACK. Most likely the implementer was trying to do this but made an off-by-one error.

Nov 27 '23 04:11 LLFourn

I added this to alpha.4 since it should be a small fix.

Dec 05 '23 03:12 notmandatory

I'm in favor of this suggestion https://github.com/bitcoindevkit/bdk/pull/1225#discussion_r1403327497. To quote @danielabrozzoni:

let past_gap_limit = if let Some(i) = last_active_index {
    last_index >= i.saturating_add(stop_gap as u32)
} else {
    // If the last active is None, last_index + 1 is the number of spks we searched
    // If we searched `stop_gap` or more spks without finding a tx, then we're past
    // the gap_limit
    last_index + 1 >= stop_gap as u32
};

I might even tweak this slightly to rename past_gap_limit to gap_limit_reached to indicate we want to break once the gap limit is reached and not go further, but that's a minor point.

Dec 17 '23 05:12 ValuedMammal

@nondiremanuel assign me :)

Mar 01 '24 12:03 storopoli

Clearly define and document `stop_gap`