Best way to find list of UTXO related to xpub

Question

Apparently the way to find a list of UTXO related to an xpub is to derive all addresses from the master private key and query a node with each and every one of them.

It is possible to generate 4294967296 addresses from a single extended key.

How should a wallet proceed to manage this in an efficient way?

I guess that in an ideal situation, addresses are generated in a sequential order... but my intuition tells me that nothing prevents a wallet from doing otherwise.

Answer 1

The balance checks are cut short based on a gap limit.

A gap limit is usually set to 20, and is defined as a consecutive block of addresses with no transactions.

Since HD wallets only give out a new address on explicit request, or automatically when the previously issued address has been used, it is assumed that someone will not leave a block of 20 consecutive addresses unused.

Wallet software will generate a short list of maybe addresses when you load an xpub or other form of seed. It will then check through that, and if it doesn't find 20 consecutive unused addresses, it will generate another short list (so the first list might cover 0-100, then 100-200, etc). until it finds the block of unused addresses.

This assumption naturally falls apart if you are running an exchange, payment service, or other wallet set up where it is very likely that you will have many hundreds of unused addresses. Those systems generally keep track of assigned addresses out of band, and have specialized indexer systems that can track many millions of addresses.

Answer 2

Not all wallets are the same, but a good wallet should always follow standards. A standard for address-generation generally accepted is BIP44. In this way, you could scan the first consecutive addresses that a BIP44-compliant wallet would create. If the wallet supports Segwit, then you should look at BIP49 and BIP84 as well.

As Raghav Sood pointed out in his answer, most wallets scan a certain amount of unused addresses before they decide to stop scanning for funds. Most of them use 20 as the gap limit (maximum gap in between unused addresses).

Now, to answer your question, you are totally right. Nothing prevents a wallet from not complying with BIP44 standard or with any other standard whatsoever. That is why it is important to know the wallet you are dealing with. However, a well defined protocol/standard helps with the fund-discovery process which is super important for any kind of wallet, for which it is almost certain that every wallet out there possesses a standard for address creation (either BIP44 or one of their own).

Just find out the standard that the wallet you're dealing with is following for address creation, and that would lead you to find the most efficient way to find the UTXO associated to the xpub.

Answer 3

An electrum wallet (legacy, testnet)

C# code for below windows application that returns 10 addresses from one XPUB using NBitcoin

var pubkey = ExtPubKey.Parse(textBox1.Text, Network.TestNet);
                    

        for (uint i=0; i < 10; i++)
        {
            var Address = pubkey.Derive(0).Derive(i).PubKey.GetAddress(ScriptPubKeyType.Legacy, Network.TestNet);
            richTextBox1.AppendText(Address.ToString());
            richTextBox1.AppendText("\n");
           
        }

The gap limit is the maximum number of consecutive unused addresses in your deterministic sequence of addresses. Electrum uses it in order to stop looking for addresses. In Electrum, it is set to 20 by default, so the client will get all addresses until 20 unused addresses are found.

Electrum will generate new addresses as you use them, until it hits the gap limit. Addresses beyond the gap limit will not automatically be recovered from the seed. To recover them will require either increasing the client’s gap limit or generating new addresses until the used addresses are found. If you wish to generate more than one address, you can use a “for” loop. For example, if you wanted to generate 50 addresses, you could do this: [wallet.create_new_address(False) for i in range(50)]

https://electrum.readthedocs.io/en/latest/faq.html#gap-limit

If I run the above code with i < 50 in for loop I get 50 addresses from the XPUB

Gap limit can be changed with: wallet.change_gap_limit(50)

Now I see 50 addresses instead of 20 (excluding change addresses) in electrum wallet same as returned by the code above: