Mind the Bitcoin Address Gap
Bitcoin holders who self custody have to worry about a variety of ways that their keys could be stolen or lost. But what's less known is that it's possible to lose track of your bitcoin even though you still have the keys that can be used to spend it!
Historical Background
In the early days bitcoin wallets were "just a bunch of keys" meaning that they would randomly generate keys as needed and try to keep a certain number of unused keys available at any point in time. The downside to this was that every time the wallet generated a new key, the user would need to perform a new backup. Naturally, wallets would not inform users of this fact and thus people ended up permanently losing access to funds due to not backing up their wallet frequently enough.
Liam Frost
Hierarchical Deterministic wallets were developed to make backups a simple one-time process. However, HD wallets have introduced a new issue.
If you import / recover a key pool based wallet, it is quite simple - the keys that you import are what you have and that's it. With HD wallets, your wallet seed is the portal to a nearly unlimited number of keys. Since we don't want to spend an unlimited amount of time generating keys from a seed, the wallet import now has to follow a discovery process that includes sane limits on when to stop generating keys and searching for funds. Given a seed phrase, redeem script parameters, and a derivation path, a wallet should traverse the standard account child paths until it hits a large gap of addresses that have never received funds. This number is referred to as the "address gap limit."
As noted in BIP 44 and BIP 45, the recommended address gap limit is 20 and only on the external receive path, not the change address path. Note BIP 44's section:
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.
Wallet software should warn when the user is trying to exceed the gap limit on an external chain by generating a new address.
Sadly, few wallets follow the BIP 44's advice to warn users about address gaps.
When you Assume...
All of the issues raised in this article are the result of assumptions that don't always hold true. What are the assumptions?
- No user will create 20 addresses in a row without receiving a deposit
- Change address derivation paths will never have gaps
Falling into the Gap
The first time I ran into an address gap issue was back in 2016:
mycelium-com
The issue I hit was due to a long chain of unconfirmed transactions for which a parent transaction was malleated, thus invalidating all the child transactions. What are other edge cases than can trigger address gaps?
- You generated 20+ receive addresses while messing around / testing to which you did not receive funds, then you received funds to addresses generated after that.
- You generated a lot of addresses to whitelist at different third party services for withdrawal purposes but didn't end up withdrawing funds to them.
- 20+ invoices were generated on your web store / BTCPay server that didn’t get paid. This is kind of a DoS vector because it generally doesn’t cost much to go through a checkout process and get a merchant to generate an invoice.
- You run a service that accepts deposits, like an exchange, and you assign unique deposit addresses for each user. If 20 users sign up for an account but never make a deposit, you surpass the gap limit.
- You have the same wallet running on different devices that don't sync with each other and you generate many addresses on one device but not the others.
- You have a watch-only (receive only) wallet running on a device that doesn't sync with the wallet software you use for spending. If you generate many addresses on the watch only wallet, the spender wallet won't be listening for deposits on those addresses.
- You could run into change path address gap issues by signing multiple proposed transactions but not broadcasting them, and then broadcasting a transaction you create later.
Potential Solutions
Preventative:
- Limit receiving address generation: At Casa we don't allow the app to generate a new address until the current address has received funds. This can result in frustrating UX for users who want to generate many deposit addresses, but we consider it a safety feature.
- Add logic to your Bitcoin wallet that goes back and re-allocates unused addresses. This has the potential to cause confusion for merchants if someone pays an invoice that has been expired and the address recycled. It may even be impossible for services that assign addresses to long-lived accounts. You could argue that such services should be incrementing the ‘account’ path for this purpose, but you’d inevitably run into look-ahead issues along a different part of the derivation path.
- Add a cost to the user for address generation. This need not be a financial cost, but some sort of hoop they need to jump through to disincentivize spammers. If someone can simply write a script or refresh a page a bunch of times to generate a thousand addresses in your wallet, you're going to have a bad time.
Restorative:
- Manually fill in gaps by sending small amounts of BTC to them. This is both costly and a waste of scarce block space.
- Increase the gap limit in your wallet's configuration. Not all wallets support this, but some such as Electrum and Ledger Live do.
Electrum's gap limit configuration must be done in the console:
wallet.change_gap_limit(100)
wallet.storage.write()
Recovering Missing Funds
I've lost count of how many times I've had to help people recover funds that "mysteriously disappeared" when they tried to restore a wallet from their backup. My go-to solution is to recreate the wallet in Electrum (preferably by loading the seed onto a hardware device) and then using the console to quickly generate a ton of addresses:
for x in range(1000): wallet.create_new_address(False)
for x in range(1000): wallet.create_new_address(True)
In the bottom left of the Electrum window you should see it say “Synchronizing…” for a few seconds and then hopefully your missing balance and transactions will show up! Now you should be able to spend them normally.
Thankfully for BTCPay Server users, they have built-in a rescan tool that sets a default gap limit to 10,000 - this is the only wallet software I've come across that makes it as easy as clicking a button.
A Hand-On Example
If you want to get a feel for what it's like to search for missing money, install Electrum and set up the following watch-only wallet.
- Run: electrum --testnet
- Create New Wallet
- Select "Standard Wallet"
- Select "Use a master key"
- Paste the following extended public key: vpub5VbqiMAitbLcBPBLVaHWTudEfwaBwcAR4naUaM54kGTDqFFB9bTU5sAwD3SoM7pD2JVVqTuojBRcQcauBeiswgm8QL1x2qrpxuPwsLjtU2W
See if you can find the entire balance of the wallet: 20 TBTC
Other Ramifications
If you're using a Simplified Payment Verification (SPV) wallet with a huge gap limit, you could hit some gnarly issues. Exceeding BIP 37's bloom filter max size of 36,000 bytes - which would be equivalent to a filter of 20,000 addresses - would cause a node to reject your request. Also, as the size of the bloom filter nears 20,000 addresses the false positive rate will approach 0.1%. It’s generally agreed that bloom filters are terrible for privacy and enterprises should be running their own full nodes with a UTXO indexing solution for fast lookups.
Address gaps can even be weaponized into ransom attack vectors!
TheCharlatan
A Hidden Footgun
Address gaps are the type of low level issue with which Bitcoin users should never have to concern themselves. However, until all popular Bitcoin wallet software handles this edge case more gracefully, it will continue causing nightmares for those who encounter it.
