improved-stealth-addresses.md

Improved Stealth Addresses

This is a scheme for stealth addresses which requires less computational overhead for the recipient. It builds upon 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 hashmap. Further it's possible to batch all lookups required to scan a block.

Details

• Recuring payments: After sender and recipient have established a shared secret once for their first transaction they can derive more keys from that first secret.
• 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.
• A simple directory results from OP_RETURN outputs for sender key registration. Alternatively, keys could be registered in taproot outputs.