improved-stealth-addresses.md

Improved Stealth Addresses

This is a scheme for stealth addresses which requires little computational overhead for the recipient to scan the chain. It builds upon many previous ideas. It reduces the overhead for scans from O( #TXs ) to O( #users ).

Protocol

• All senders register on their first send a public key in a public directory.
• Recipients perform a DH key exchange with each sender key in the directory to derive all their potential receive addresses.
  • Sender key: A = aG
  • Recipient key: B = bG
  • Shared secret: s = abG
  • Recipient stealth address: B' = B + sG

Complexity Analysis

This scheme requires per recipient

• Group operations to derive all their stealth addresses: O(#senders)
• Space to store the addresses: O(#senders)
• Lookup time per output when checking each output in a block: O(1) when using a hash map. Further it's possible to batch all look-ups required to scan a block.

Additional Details and Improvements

Recurring payments

After sender and recipient have established a shared secret once for their first transaction they can derive more keys from that first secret.

Wallet Compatibility

• It is not required that the spending wallet is compatible with this scheme. Senders can use a separate tool to register and manage a key to derive addresses for recipients.
• Not even the recipient wallet has to be compatible with this scheme. They can use an external tool as well. It is only required that the recipient can sign taproot-like outputs: To receive coins, a recipient publishes a key pair (B_scan, B_spend) instead of just a single key. A 'scan key' and a 'spend key' allows to decouple scanning from spending. Modifications:
  • Shared secret: s = a * b_scan * G
  • Recipient stealth address becomes: B' = B_spend + sG.
  • This can be reformulated to match the structure of a taproot tweak, which is compatible with many existing wallets:
    • B' = B_spend + H(B_spend | s) * G
    • This way it becomes possible to import UTXOs into, e.g., a Bitcoin Core Wallet with descriptors and spend them with any hardware wallet that supports Taproot keyspends.

Directory

A simple directory results from OP_RETURN outputs for sender key registration. Alternatively, keys could be registered in taproot outputs. Another alternative is to use Ordinals-like storage in witness data to enable cheaper mass-registrations. This reduces the minimal cost of registration per key to about 32vbytes -> 8 sats. Payable off-band, for example, via Lightning payments.

Light Client Support

This scheme can be used in combination with a block filter for light clients to check efficiently if a block contains an incoming transaction.

• As 'block filter' simply use a list of the first 5 bytes of each address occurring in a block.
• Match those address prefixes against your directory.
• Filter size: 25kB for 5000 recipients per block. It can be further compressed by sorting the list.

Credit card-like Account Number

This scheme can be combined with reusable phone number-like accounts.

For example: "My Bitcoin Account is 326681/625/43", which describes in which block, and in which transaction, and in which position the recipient's keys were registered in the blockchain.