How Do HD Wallets Keep Track of all accounts?

Question

If a HD Wallet generates 1,000 accounts for example.

How would they keep track of all of the account's balances, if someone for example, paid into the 455th account, they would want to update the wallet balance.

I imagine that storing all of the accounts would not be efficient, and querying the blockchain or an API for all 1,000 would not be efficient either.

Using an isolated use case:

If an API HD wallet generates 1,000 addresses, it cannot query all 1,000 each time the user starts up the phone, and it cannot do it periodically because with everyone hitting the same endpoint, it would be a bottleneck.

I do remember blockchain.info allowing you to query with your extended public key, I imagine that they iterate through the accounts the same way using the gap limit.

Answer 1

In general, HD Wallets use the following logic for how many addresses to query, and when to stop:

1. Start with account 0, generate gap limit number of addresses (usually 20)
2. Check for any transactions in those addresses
3. If there are no transactions, stop searching for new addresses and accounts
4. If there are transactions, generator gap limit more from the index of the last address with transactions on it. Additionally, also do this process for account 1 (you only check for n+1 accounts if Account n has transactions

The general idea is that no accounts will exist if the previous account is unused, and that no addresses in an account will be used after a single, consecutive block of gap limit number of unused addresses.

Companies like BitGo who offer HD wallet services to exchanges etc. where you can easily have thousands of unused addresses in a row, and then addresses with transactions, generally ignore the gap limit. They instead maintain a list of all generated addresses and index them as individual addresses, not as an HD wallet.

On the API side of things, wallets generally try to keep a running index. They will maintain a cache of known transactions, and keep appending to it. This way, when you start it up, it only scans for transactions in the new blocks since the last time it scanned. This allows even light clients such as Electrum or Ledger/Trezor wallets to serve thousands of users with just a handful of nodes, since each wallet will not requery for previous transactions it alread knows about.

Naturally, if you import a frequently used HD wallet to a new wallet or delete the cache, the initial sync can take very long. However, subsequent syncs of the wallet will be much faster.

In addition to this, HD wallets will often rely on a full node (such as Bitcoin Core) or a system such as ElectrumX or Insight. All of these are capable of maintaining a full index. Bitcoin Core maintains only a running index across known addresses (which is why you need to rescan when you import an address). ElectrumX and Insight maintain an augmented index which keeps track of all transactions, and can quickly return data for any given address.

HD Wallets do continue to check for transactions across all used addresses. They simply don't rescan the entire chain every time. But for every new block, every tx in that block will be checked for every address in the HD wallet. This check can be done quickly via bloom filters or preindexed data such as from Electrum or Insight, without reaching a bottleneck.