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.