BIP32 wallet sync with Bloom filters

Question

I'm working on my SPV library and I still have a hard time figuring how to approach the BIP32 + Bloom filters combination. Here's how I currently sync an existing HD wallet (after fast catch-up):

1. Generate a number of watched look-ahead addresses (say 10).
2. Load a Bloom filter with all used addresses plus look-ahead (N used + 10 look-ahead).
3. Download filtered blocks with getdata.
4. Mark watched addresses as used if they're found in any block transaction.
5. Ensure that the last watched address wasn't used in a transaction.
6. If so, generate new look-ahead addresses, reload the Bloom filter and download last block again to rematch it. By using a new receive address for each transaction we may have missed other transactions in the same block.
7. Otherwise, go back to 4 and download new blocks.

Now this sounds quirky and overcomplicated to me. Several discussions on the web talk about "scanning keys" when coming to wallet sync and I don't really understand if they assume a full node or a lightweight SPV node, because I have no idea of how to "scan keys" without a global UTXO database. Also the gap limit only seems to make sense for a full node.

I'm stuck, thanks.

Answer 1

The reason you pre-generate some forward keys is to avoid the situation you describe, if you only looked ahead one you risk missing a transaction in the current block (the order of the transactions in the block are unrelated to the order of your keys).

The term "gap limit" refers to a parameter of non bloomfilter SPV clients which do look ups by querying an address based index on a remote peer. The gap limit is the end stop of the current wallet state, when the scanning wallet sees 10 empty address results in a row they decide that's probably the last used address in the wallet and give up generating further. If there wasn't a gap limit in place they would search unused addresses until the end of time (or 2**128, which ever came first).