How To Traverse Bitcoin Addresses in HD Wallet

Question

It appears that there are many way to traverse Bitcoin addresses. I am looking best practice, and I am also looking for the documented logic of how common wallets do it so I can replicate their behaviour.

For example, Trezor creates the first address at this location: m/49'/0'/0'/0/0, and then the next address will be m/49'/0'/0'/0/1, and so on. So, it appears that it would be easy to just use an iterator over the last digit.

But, when you spend from m/49'/0'/0'/0/0, it moves the leftover to m/49'/0'/0'/1/0 . So, suddenly, I not only have to iterate over the last digit, I also have to iterate over the penultimate digit. I could have said "second last", but I said penultimate because it sounds more intelligent.

Is there standard practice for traversing addresses? Something like, keep traversing over addresses until you hit an address with no transactions? Or possibly say three addresses in a row with no transactions? Or is this really the wild west and we just do whatever we feel like?

Answer 1

Most (but not all) wallets will follow what is specified in BIPs 32, 44, and 49.

BIP 32 defines what derivation paths are and what they mean. It is the standard for deriving all of the keys in a HD wallet.

BIPs 44 and 49 specify derivation paths that wallets should use. BIP 44 defines a standard derivation path format: m / purpose' / coin_type' / account' / change / address_index. It also defines the purpose for non-segwit Bitcoin keys.

When a wallet is deriving the keys, the path for external keys, i.e. those keys which you get by clicking "New Receive Address" (or similar) is m/44'/0'/0'/0/i and i is just incremented for new keys.

For internal keys, i.e. keys for change addresses, the derivation path will set the change field to 1, so the path will be m/44'/0'/0'/1/i and i is incremented for each new change address that is needed.

Since that change field is essentially a boolean, there is no need to iterate through any indexes other than 0 and 1.

BIP 49 specifies the purpose for keys used for P2SH nested segwit addresses. It just sets the purpose field to be 49, so the derivation paths will be m/49'/0'/0'/k/i where k is the change field and i is the address_index. The change and address_index fields remain the same as defined in BIP 44.

---

It is important to keep in mind that not all wallets follow BIPs 32, 44, and 49. For example, Armory uses its own HD wallet algorithm which predates BIP 32, although BIP 32 support for Armory is currently in the works. Other wallets such as Bitcoin Core and MultiBit HD do not follow BIP 44. Instead they use different derivation paths. For Bitcoin Core it's m/k'/i' where k is change (same definition as with BIP 44) and i is address_index (same definition as with BIP 44).