Repeat Payment Derived Key/Addresses

[apbendi]

Recap

Currently, each sender chooses a random number R and uses it with the receiver's public key Pk to generate a stealth address S, such that only the receiver can generate the stealth address' private key. The sender announces R on-chain encrypted with an ephemeral key derived via ECDH from Pk such that only the receiver can decrypt it. To find stealth payments intended for them, each receiver must attempt to decrypt every Announcement in the contract. Until attempting to decrypt it, the user's software has no intuition whether a payment is intended for them.

Proposal

For repeat payments, from a known sender to the same receiver, we could opt to use a deterministic function, H(R0, n), to derive subsequent "random" values after the first one R0, used to generate the stealth addresses when paired with a monotonically increasing nonce n, such that:

R0 = CSPRNG()
R1 = H(R0, 1)
R2 = H(R0, 2)
R3 = H(R0, 3)
...

Alternatively, the function, H'(RN) could derive R of N recursively from the previous value of R:

R0 = CSPRNG()
R1 = H'(R0)
R2 = H'(R1)
R3 = H'(R2)
...

With some minor implementation tradeoffs, both seem roughly equivalent to me.

Some obvious prior art here is BIP32 HD wallets, and a deeper dive into that spec is warranted. It might be worthwhile adopting that spec outright.

But Why

By calculating subsequent R values deterministically, receiving user's software can pre-calculate a list of stealth addresses it expects it might receive to if a previous payer sends a repeat payment. (Presumably, in situations like salaries and e-commerce, repeat payments between entities will be quite common).

When a user returns to Umbra to scan announcements, they can first search for any payments to pre-computed stealth addresses they might receive a repeat payment to. Scanning for the presence of given addresses is (likely) an order of magnitude faster than attempting a decryption of the Announcement payload, so these payments can be recognized and available for withdrawal much faster.

Downsides

User's software now has to keep track of the initial R0 (in the case of H) to derive subsequent values RN.

Because the deterministic R values are still available via decryption according to the standard protocol, users are at no risk of losing funds if they lose R0, and in fact, R0 itself could always be recovered from the initial announcement.

However, if R0 is ever compromised, i.e. leaked in some way, all payments between that sender and receiver would lose privacy protections. Funds would not be at risk unless the user also leaks their private key pk. Also, if the sender and receiver are aware R0 is leaked, they can simply restart the derivation with a new R0' on the next payment. (Privacy is still lost for all payments made in the interim).

One final comment: because it's essentially "backwards compatible" with the existing architecture, a scheme like this need not be implemented in the core protocol. It could, instead, be built and adopted "on top" of it, in conjunction with #30, where part of the payload in the initial payment is used to signal a derivation scheme to the receiver's software.

[seresistvanandras]

Even though this does not solve the initial O(n) scanning overhead (n is the number of all Umbra stealth transactions) of recipient for the very first transaction, this would be quite a nice and necessary improvement. This proposal allows the recipient to have a constant scanning time for repeat payments, which will be super important as soon as Umbra will (hopefully) become widely used.

IMO the first construction is probably better than the second because in the second the client would need to essentially store all R1, R2, R3, etc. values. This would give a linear-space requirement for clients. On the other hand the first construction would allow a direct access to any repeat payment, i.e. only by storing R0 all subsequent repeat payment addresses are computable. Though, in the second proposal this is only possible by either storing the Ri values or recomputing a few hashes.

[apbendi]

A thought coming back to this: is there any downside to keeping this extremely simple, like literally as simple as incrementing R by one for each subsequent payment?

[seresistvanandras]

Would not be that broken privacy-wise? I suppose here that everyone knows the public keys corresponding to an address. This certainly holds whenever funds are redeemed, since it is possible to obtain the public key from an ECDSA signature. Let's say recipient's public key is sG and then the first stealth address is RsG. One could link the next stealth address (R+1)sG to RsG by verifying whether RsG+sG=(R+1)sG holds. You could just try to brute-force every recipient (ENS) public key sG and check which one satisfies this equality. So privacy is lost in this construction.