I’m returning to this (after quite some time), just because I’m thinking about a similar problem for another project. Here’s some (hopefully correct) high-level analysis of three approaches. I’m seeking fast discovery of addresses, over billions (or maybe trillions) of trial attempts, where the cost of performing repeated hashes would be non-negligible. I’m not sure how many trial attempts this EIP expects (will there be thousands / millions / billions of stealth addresses?).
I tweaked the notation to help my brain. I also had to be a little lax with notation, because this forum doesn’t support latex.
(The . is a scalar multiplication. Capital letters are points. Lower-case letters are scalars).
Original approach (1 byte tag)
K = k.G - ethereum keypair.
V = v.G - viewing keypair
E = e.G - ephemeral keypair. E is published.
S = e.V = v.E - shared secret
h = hash(S) - secret hash
tag = h.slice(0, 1) - tag. tag is published.
P = K + h.G - stealth public key
stealth_addr = hash(P).slice(-20)
Operations to discover a match:
1 mul, 1 hash to derive the tag. Or mul + hash if you’ll forgive the disgusting notation.
False positives will occur roughly once every 2^8 = 256 trials, on average, due to a collision with the 1-byte tag. With each false-positive, you need to derive the stealth address to be sure you own it, resulting in some extra operations: 1 mul, 1 add, 1 hash to derive the stealth address, and then a check to see whether this address has a nonzero balance.
So the expected discovery time, on average, allowing for false positives, is:
mul + hash + (1 / 256) * (mul + add + hash + "an ethereum balance lookup")
Double-hash approach
K = k.G - ethereum keypair
V = v.G - viewing keypair
E = e.G - ephemeral keypair. E is published.
S = e.V = v.E - shared secret
h = hash(S) - secret hash
tag = hash(h) - tag. tag is published.
P = K + h.G - stealth public key
stealth_addr = hash(P).slice(-20)
Operations to discover a match:
1 mul, 2 hash to derive the tag. Or, if you’ll again forgive the disgusting notation:
mul + 2 * hash
False positives are infeasible.
Tag keypair approach
K = k.G - ethereum keypair
V = v.G - viewing keypair
T = t.G - tagging keypair
E = e.G - ephemeral keypair. E is published.
tag = (e.T).serialise() = (t.E).serialise() - tag. tag is published. serialise() takes the x-coord and the sign, to compress the tag.
S = e.V = v.E - shared secret
h = hash(S) - secret hash
P = K + h.G - stealth public key
stealth_addr = hash(P).slice(-20)
Operations to discover a match:
1 mul to derive the tag. Or, if you’ll again forgive the disgusting notation:
mul
False positives are infeasible.
I don’t have concrete figures for the relative speeds of mul, hash and add. Nor do I know how many stealth addresses are expected to exist. If it’s only thousands of addresses, then the asymptotics aren’t worth exploring. If it’s billions, then they probably are.