AddressIndex improvements: LastUnused, FirstUnused, and get_batch_unused_addresses()

[nickfarrow]

Description

• Change AddressIndex::LastUnused to look back further than current_index
• Add AddressIndex::FirstUnused
• Add get_batch_unused_addresses

Notes to the reviewers

Builds upon https://github.com/bitcoindevkit/bdk/pull/522

Currently BDK supports address indexing via LastUnused, which will return the address with current_index if it is unused, otherwise it will return a New address.

With this current logic, if you get two new addresses A1 and A2 and use A2, then LastUnused will give you a New address rather than the unused A1.

In order to more consistently utilize unused addresses i've added a new function get_unused_key_indexes(keychain) which returns a vector of indexes for the unused addresses in that keychain. Making use of this function, LastUnused now returns the most recent address that has not yet been used, and New if all addresses have been used.

In some cases it may be desirable to utilize unused addresses that reside earlier in the keychain. i.e. AddressIndex::FirstUnused in this PR.

FirstUnused has the same caveat as LastUnused: that if the wallet has not yet detected an address has been used, it could return a used address.

Additionally a new public function get_batch_unused_addresses allows for retrieval of N unused addresses at once. Prioritizing unused addresses first, then populating the remaining with New addresses (like FirstUnused).

For example: if a wallet builds a transaction involving many New internal addresses but that transaction is never broadcast, then all of these addresses can now easily be used in a later transaction via get_batch_unused_addresses.

Checklists

All Submissions:

• [X] I've signed all my commits
• [X] I followed the contribution guidelines
• [X] I ran cargo fmt and cargo clippy before committing

New Features:

• [X] I've added tests for the new feature
• [X] I've added docs for the new feature
• [X] I've updated CHANGELOG.md

[LLFourn]

approach ACK. Needs rebase.

[notmandatory]

Code changes look great but you'll need to do another rebase and can you add a signing key to Github and sign your commits when you do the rebase also?

[nickfarrow]

force push updated CI

[notmandatory]

Hi, please rebase to pickup changes in #596. Thanks!

[rajarshimaitra]

@nickfarrow also try to rebase on top of master instead of fetching and merging specific commit next time.. :) That makes the commit history much cleaner and also applies your changes on top of current master.. just do git rebase master from the PR branch..

[notmandatory]

I had to push this PR to the next release so the team can focus on #593, and after that one you'll probably need to rebase again. But then I promise we'll work on getting this one in. :-)

[nickfarrow]

Yep I think this one needs some bigger discussion first around whether it is worthwhile to mark used addresses directly in the database as @rajarshimaitra suggested.

If this were the case, this could be simplified to a function get_unused_addresses that (quickly) gets an iterator over unused addresses in the database up to the current addressindex. With FirstUnused and LastUnused addresses at either ends.

This PR's get_batch_unused_addresses (currently fetches n) would be superseded by get_unused_addresses where the user gets all the unused addresses and handles them how they desire.

Not sure what changed with old commits, possible I added signoff lines to the previous commits by mistake which may have updated them sorry. Will take care with next.

[rajarshimaitra]

Upon further thoughts on this I have this rough idea of how it can be done:

• Add a new column in the script_pubkey table named used. Which will have binary value 0/1, defaulting to 0.
• At each sync when we add utxos to the Utxo table, mark the pubkey as used too in the script_pubkey table.
• Make a generic get_batch_unused() that will return a list of unused addresses, checking the used flag in the database.
• Make FirstUnused as the front pop of the list, and LastUnused as the back pop of the list..

Pro: Much more scalable than transaction list scanning for wallets with large list of transactions.

Cons: This is going to change the DB structure and the BatchDatabase API.

I am willing to work on fleshing an impl out if this has Approach Acks..

[afilini]

Keep in mind we also have the key/value db, we don't have tables and columns there. We can add a flag to mark a script as used (similarly to how I suggested adding a flag for scripts that we've already setup rather than relying on just the derivation index), but getting the list of unused addresses will still require scanning

[rajarshimaitra]

ACK on @LLFourn that this can go in as it is without much further changes.. I will check the behavior once again.. If this lands through bdk_core eventually then we might not wanna do the DataBase way for now, and just keep things simple..

[notmandatory]

Is this one OK to add this to the 0.22.0 milestone? looks like it's about ready and I don't want it to be overlooked.

[LLFourn]

IMO this PR is suboptimal because of #701. I think it should be fixed first to make the code in this PR make sense. @nickfarrow?

[nickfarrow]

Yep agree it may as well wait for improvements to fetch_index, that function is relied upon a few times here

[danielabrozzoni]

Hey, we are in the process of releasing BDK 1.0, which will under the hood work quite differently from the current BDK. For this reason, I'm closing all the PRs that don't really apply anymore. If you think this is a mistake, feel free to rebase on master and re-open!