How does a wallet make sure that it restores all the keys from mnemonic phrases?

Question

I am building a wallet that complies with BIP32, BIP39, BIP44, and EIP55.

It should be easy to restore keys if a wallet owner generates keys in sequence, but in my understanding, they can create a parent key and then derive a child key of it from anywhere in the tree structure.

Then how do we make sure that we restore all the keys?

Should we traverse the tree, check the balance of each address and then generate keys for the ones with some ETH(or tokens) in them?

My concern is that some people might own an address with zero balance after some transactions though. In this case, should we check transactions for all the addresses and then generate keys accordingly?

This process doesn’t seem to be beautiful and I might have some wrong assumptions here. I’d appreciate it if you could let me know the best practice. If there were any library that can help me to implement this, that even better.

Answer 1

In BIP-0044 they gave some recommendations you my want to follow in Account Discovery section.

When the master seed is imported from an external source the software should start to discover the accounts in the following manner:

1. derive the first account's node (index = 0)
2. derive the external chain node of this account
3. scan addresses of the external chain; respect the gap limit described below
4. if no transactions are found on the external chain, stop discovery
5. if there are some transactions, increase the account index and go to step 1

Also read the next section Address gap limit

Address gap limit is currently set to 20. If the software hits 20 unused addresses in a row, it expects there are no used addresses beyond this point and stops searching the address chain. We scan just the external chains, because internal chains receive only coins that come from the associated external chains.

Answer 2

The app would need to save the users actions. (See MetaMask). When I add a new account, MetaMask saves this action and shows the new action the very next time I log in to their Chrome extension.

When I restore MetaMask to a new computer or even a new Chrome User Profile, MetaMask only shows the first account upon successful seed importation.

Simply, they leave it to the user to add a new account. Which will deterministically create the 2nd account that they previously already created the first time.

Your wallet could, in theory, upon a successful restore, create the next account, ping etherscan for any previous transactions, and if true - save progress, and check the account. Repeat till it finds an empty account that hasn't be used before.