Withdrawal in HD wallet with very large gap of unused addresses

[vicknick]

I’m building a site where each signup users will have a permanent bitcoin address assigned to them. I am thinking of using HD wallet with extended private key to generate many bitcoin addresses for those users. Since I already have the extended private key, I don’t need to store the individual private keys for each address, making key management very simple.

However, most users don’t deposit to these addresses. As such, there could be a large unused address before a user finally make a deposit to an address, say at the millionth address. If so, will it affect how the wallet function? For example, when I’m trying to withdraw using my extended private key, can the wallet withdraw normally in this situation. If not, then what are the ways to handle this issue? I know that you can increase the ‘gap limit’ so that the wallet keeps on scanning, but is there a better way to withdraw in this case?

Side questions:
1. If there are deposits to addresses where there are multiple large gaps in between these addresses, when I try to query for balance with extended private key, will the gap limit affect the balance shown to me? Because I’m think the wallet will stop at some point, even though there are bitcoin in the addresses subsequent after that.

2. Is it possible to combine bitcoin from different addresses when withdrawing? Say there is one bitcoin in 1st address and there is one bitcoin in the 1,000,000th address. If I want to withdraw 2 BTC, will the wallet able to combine the bitcoin from two addresses in a single transaction?

[PrimeNumber7]

I believe when you say "withdraw" you mean "spend".

1. If your gap limit is set to 20, your wallet software will look at 20 consecutive addresses that have no transactions before stopping to look at additional addresses. So if you have a transaction in the 15th address, your wallet software will look at the 16th through 36th address for transactions before it will stop if none of any of the 16th through 36th addresses have any transactions.

2. Yes, it is common to spend coin in multiple different addresses in the same transaction. You can either choose which addresses you wish to spend from (based on the inputs) or can let your wallet software choose automatically based on your preferences.

There is no limit as to the number of addresses a HD wallet can have. However, at one point, you will start to experience performance issues once the number of addresses (used and unused when accounting for your gap limit) reaches a certain size. You can address this by having a hard limit to the number of addresses your wallet will generate, once you hit this limit, you can create a new HD wallet on a different machine. Once you have created an arbitrary number of HD wallets, you could depreciate the deposit addresses associated with the oldest wallet, and tell your customers to click a button on your website while logged in to trigger you to generate a new address to be associated with their account.

[vicknick]

You could assign each user with their own address index and only assign it when user want to see the bitcoin address for deposit to reduce workload of the wallet software.

Code:

m / purpose' / coin_type' / account' / change / address_index

2. Is it possible to combine bitcoin from different addresses when withdrawing? Say there is one bitcoin in 1st address and there is one bitcoin in the 1,000,000th address. If I want to withdraw 2 BTC, will the wallet able to combine the bitcoin from two addresses in a single transaction?

Yes, it's possible.

No possible with our site service. Each users must have an address upon signing up. And also, that doesn’t really answer the question of having many unused addresses.

[Abdussamad]

Side questions:
1. If there are deposits to addresses where there are multiple large gaps in between these addresses, when I try to query for balance with extended private key, will the gap limit affect the balance shown to me? Because I’m think the wallet will stop at some point, even though there are bitcoin in the addresses subsequent after that.

yep gap limit does factor into it. you can modify it but the performance of the wallet software may suffer. you haven't told us what wallet you intend to use? if it's electrum then you may need to run your own electrum personal server and bitcoin core at the backend so that it can handle all the queries your wallet generates. you won't be able to rely on public servers.

another option is bitcoin core alone but you'll have to manually import the private keys for each address. bitcoin core's native derivation scheme uses hardened addresses which means you can't derive them using the xpub. so that's why you'll have to manually derive and import private keys corresponding to the derivation scheme you are using on your site.

2. Is it possible to combine bitcoin from different addresses when withdrawing? Say there is one bitcoin in 1st address and there is one bitcoin in the 1,000,000th address. If I want to withdraw 2 BTC, will the wallet able to combine the bitcoin from two addresses in a single transaction?

yes and that's what a wallet does automatically.

[HeRetiK]

2. Yes, it is common to spend coin in multiple different addresses in the same transaction. You can either choose which addresses you wish to spend from (based on the inputs) or can let your wallet software choose automatically based on your preferences.

2. Is it possible to combine bitcoin from different addresses when withdrawing? Say there is one bitcoin in 1st address and there is one bitcoin in the 1,000,000th address. If I want to withdraw 2 BTC, will the wallet able to combine the bitcoin from two addresses in a single transaction?

yes and that's what a wallet does automatically.

Caveat: A wallet will only do this automatically if the two addresses are within the gap limit. Otherwise it won't know the coins are there.

In addition to increasing the gap limit you could (1) keep track of the generated addresses in a separate database and use application logic to check for incoming / outgoing transactions or (2) send small amounts of coins just within your gap limit (e.g. if your gap limit is set to 100, you could reserve every 100th address for internal purposes and send a small token amount there to bridge the gaps).

Unfortunately I couldn't find anything on how large you can sanely set a gap limit. Maybe you can set it to 100k and it works just as well.

[PrimeNumber7]

In addition to increasing the gap limit you could (1) keep track of the generated addresses in a separate database and use application logic to check for incoming / outgoing transactions or (2) send small amounts of coins just within your gap limit (e.g. if your gap limit is set to 100, you could reserve every 100th address for internal purposes and send a small token amount there to bridge the gaps).

Your wallet will need to keep track of every address starting from the first address up to the last address in your gap limit after the last address that received a transaction (that your wallet is aware of). Sending dust to every 100th address will be very expensive and will not save much in other resources because the number of fewer addresses your wallet will need to monitor will decrease only by the amount of the smaller gap limit.

I would not implement this solution.

Unfortunately I couldn't find anything on how large you can sanely set a gap limit. Maybe you can set it to 100k and it works just as well.

This will be a function of how many addresses your wallet can monitor without encountering performance issues.

The desired gap limit should be an estimate as to how many empty addresses the OP expects to have between depositing customers.

[Abdussamad]

In addition to increasing the gap limit you could (1) keep track of the generated addresses in a separate database and use application logic to check for incoming / outgoing transactions

keeping a list of all generated addresses is one thing although it could be simplified to one number i.e. the index of the last address you generated. monitoring utxos is the job of the wallet. if you started doing that in your app you'd be duplicating the work of a wallet. instead it would be better to  derive all the private keys upto that index you have stored in your db and import them all into bitcoin core. let core figure out which addresses have utxos.

[HeRetiK]

In addition to increasing the gap limit you could (1) keep track of the generated addresses in a separate database and use application logic to check for incoming / outgoing transactions or (2) send small amounts of coins just within your gap limit (e.g. if your gap limit is set to 100, you could reserve every 100th address for internal purposes and send a small token amount there to bridge the gaps).

Your wallet will need to keep track of every address starting from the first address up to the last address in your gap limit after the last address that received a transaction (that your wallet is aware of). Sending dust to every 100th address will be very expensive and will not save much in other resources because the number of fewer addresses your wallet will need to monitor will decrease only by the amount of the smaller gap limit.

Good point! The intention was less about increasing performance but more about making absolutely sure that no balances are overlooked. However you're right in that it probably makes more sense to simply increase the gap limit as necessary.

Unfortunately I couldn't find anything on how large you can sanely set a gap limit. Maybe you can set it to 100k and it works just as well.

This will be a function of how many addresses your wallet can monitor without encountering performance issues.

Are you aware of any benchmarks or do you have any practical experience regarding performance degradation caused by large gap limits? I'm genuinely curious as I'm lacking the intuition for this particular use case.

In addition to increasing the gap limit you could (1) keep track of the generated addresses in a separate database and use application logic to check for incoming / outgoing transactions

keeping a list of all generated addresses is one thing although it could be simplified to one number i.e. the index of the last address you generated. monitoring utxos is the job of the wallet.

You are of course correct about monitoring transactions being the job of the wallet, but OP was inquiring about an edge case where said monitoring may fail ie. balances in addresses beyond the gap limit.

[PrimeNumber7]

Are you aware of any benchmarks or do you have any practical experience regarding performance degradation caused by large gap limits? I'm genuinely curious as I'm lacking the intuition for this particular use case.

I am not.

You could create a new wallet, set the gap limit to 1, measure the amount of memory your wallet software is using, then set the gap limit to say 10,000 and measure memory use again. This should give you an idea as to how much memory each address being monitored uses. The gap limit should monitor both receiving and change addresses.

[PrimeNumber7]

Are you aware of any benchmarks or do you have any practical experience regarding performance degradation caused by large gap limits? I'm genuinely curious as I'm lacking the intuition for this particular use case.

I am not.

You could create a new wallet, set the gap limit to 1, measure the amount of memory your wallet software is using, then set the gap limit to say 10,000 and measure memory use again. This should give you an idea as to how much memory each address being monitored uses. The gap limit should monitor both receiving and change addresses.

I wonder why you only mention memory? I/O and CPU might be concern if you use local database. Percentage of non-empty address also might change memory, I/O and CPU usage significantly.

Resource consumption will be a function of both total number of addresses being monitored and the total number of transactions.

The list of addresses that need to be monitored needs to be kept in memory. I would presume that I/O and CPU would be a function of how often the OP's customers would query their balance, and the OP may want to keep a separate database with each customer's balance if his customers will be spending some of their deposits off-chain.

Using electrum, the memory usage by electrum, as reported by my operating system increased from about 110 MB to about 230 MB when I changed the gap limit from 20 to 10,000. After my wallet finished syncing, electrum would take around 18% of one of my 1.8 GHz cores, up from about 2% with a gap limit of 20.

I don't think electrum is really designed to be handling transactions associated with very large numbers of addresses, and another wallet software might be more appropriate.