Address Gap Limit vs. Privacy Strategy

[yyforyongyu]

Context

HD Wallets (BIP 44) face a fundamental trade-off between Privacy (avoiding address reuse) and Safety (the Gap Limit problem).

• Privacy: Requires issuing a new address for every request ("Always New").
• Safety: Requires ensuring that the "Gap" (number of consecutive unused addresses) does not exceed the scanning window of a restored wallet (typically 20).

Currently, btcwallet defaults to the "Always New" strategy. If a user or application generates >20 addresses without receiving funds, a subsequent wallet restoration will fail to discover funds sent to the 21st address.

Detailed Problem Example

Consider a backend service using btcwallet to accept deposits, with the default gap limit of 20.

1. Initial State:

   • Last Used Index (On-Chain): 100
   • Next Issued Index: 101
   • Gap: 0

2. High Volume Address Generation:

   • The service generates 25 deposit addresses for new user signups.
   • Each signup triggers a NewAddress call (Indices 101 to 125).
   • Crucially: None of these users deposit funds immediately. The addresses remain empty on-chain.

3. State After Generation:

   • Last Used Index (On-Chain): 100
   • Next Issued Index: 126
   • Current Gap: 26 (Indices 101-126 are empty on-chain).

4. The "Lost" Funds Scenario:

   • User Implement better sendmany RPC extension. #25 finally makes a deposit to Address New secure hierarchical deterministic wallet address manager. #125.
   • The transaction confirms on the blockchain.
   • Disaster: The service operator needs to restore the wallet from seed (e.g., due to hardware failure).
   • The restored wallet scans addresses 0...100 (finds funds).
   • It scans 101...120 (the default lookahead of 20). It finds nothing.
   • The wallet stops scanning, assuming no further addresses are used.
   • Address New secure hierarchical deterministic wallet address manager. #125 (with the deposit) is never checked. The wallet reports a balance of 0 for that user.

This "Always New" strategy is brittle in automated environments. Services often generate addresses that aren't immediately used, easily exceeding the default gap limit.

Proposed Solutions

We propose a hybrid strategy that maintains privacy by default but enforces safety boundaries.

1. Track "Issued" vs "Used" Gap

Instead of blindly issuing new addresses, the wallet must track the gap explicitly.

• Used Index: The highest index found in the UTXO set (e.g., 100).
• Issued Index: The highest index found in the Addresses table (e.g., 125).
• Gap: Issued Index - Used Index.

2. Configurable Gap Enforcement

When a new address is requested, check the Gap against a configured GapLimit (default 20, recommended 100+).

• If Gap < Limit:

  • Issue new address (Index + 1).
  • (Privacy Preserved).

• If Gap >= Limit:
  The behavior should be configurable based on the user's preference for Safety vs. Privacy:

  • Option A (Strict Safety - Reuse): Return the oldest unused address (e.g., Index 101).

    • Pros: Guarantees funds are discoverable (Safety). Service continues without interruption.
    • Cons: Privacy leak (address reuse/linkability).

  • Option B (Strict Privacy - Error): Return an error (ErrAddressGapExceeded).

    • Pros: Guarantees no address reuse (Privacy).
    • Cons: Service disruption. User must manually intervene (fund an address or increase limit).

  • Option C (Lenient - Warning): Log a warning and issue the address anyway.

    • Pros: No disruption.
    • Cons: High risk of "lost" funds during restore.

3. Increase Default Lookahead

To reduce friction, we should increase the default lookahead window in the scanner from 20 to a safer baseline (e.g., 100 or 1000).

• Pros: Drastically reduces the probability of accidental fund loss.
• Cons: Increases initial sync time and resource usage during rescans.

Implementation Strategy (Query-Based)

This logic relies on efficient queries rather than new schema columns:

1. Issued Index: Query MAX(address_index) from the addresses table (scoped by account/branch).
2. Used Index: Query MAX(address_index) from the utxos table (joined with addresses).
3. Manager Logic:
   • Calculates Gap = MaxAddressIndex - MaxUtxoIndex.
   • Enforces the policy before calling NextAddressIndex.

This approach keeps the schema normalized and relies on the database's indexing for performance.

[GustavoStingelin]

How were we thinking about storing the lookahead addresses? If we keep them only in memory and persist them only when we detect transactions or when the user explicitly derives an address, this seems both safe and privacy-preserving.

Example flow:

• An account is created with zero addresses.
• NewAddress is requested, so we create a new address row. This implies the user intends to use it, for example to sign a transaction or share it, so this address becomes dirty.
• In memory, we keep the addresses already stored in the database plus a derivation gap of N addresses, such as 20 or 100.
• If a new transaction is found within that gap, we persist the relevant addresses to the database and then recalculate the gap.

Does this model make sense, or am I missing something?

[Roasbeef]

How were we thinking about storing the lookahead addresses?

This doesn't help with the recovery case.

Stepping back, in practice we just use a very large gap limit for recovery (something like 50k addrs). If a user believes they didn't recover all their funds, then they can increase this value.

[GustavoStingelin]

So, in the example flow I mentioned, we could increase the lookahead gap to something like 50k addresses and make this value configurable by the user. From my point of view, this would work, but I am not fully understanding why this would not be sufficient. Could you clarify what I am missing?

[yyforyongyu]

We are talking about the recovery state tho - as the gap will only matter when we perform a rescan or resync.

If a new transaction is found within that gap, we persist the relevant addresses to the database and then recalculate the gap.

I think that's the current logic, when a spend is found, we will expand our look ahead gap by deriving the configured num of addresses.

we could increase the lookahead gap to something like 50k addresses and make this value configurable by the user.

This can work, but with a tradeoff - the larger the gap, the longer it takes to sync the wallet. For a wallet that's offline long, this can take a very long time to sync, which was an issue in lnd.