On Mon, Jan 13, 2014 at 04:15:01PM -0500, Alan Reiner wrote:
> > I don't know if stealth addresses are the best solution to address
> > this use case, but AFAIK the only current solution to this use case is
> > to store a long-lived Bitcoin address in the addresss book.
> >
> > roy
> >
> 
> Fair enough.  I haven't spent much time thinking about that use case. 
> Though, I question the feasibility of anything that requires O(N) EC
> multiply operations/sec, where N is the total volume of transactions
> moving over the network.  But I guess if the prefix is big enough, the
> scanning operations will remain feasible forever.

Well that's the thing: the cost to find all stealth-address-using
payments to you isn't O(n) transaction volume, it's O(n) anonymity set
size. I think we can make a pretty good argument that the anonymity set
people need is mostly fixed in size and has nothing to do with overall
tx volume, so really we've got O(1) scaling.

There is a catch however: if you need the prefix to be against
H(scriptPubKey) rather than scriptPubKey directly the sender needs to
grind the OP_RETURN output at 2^len(prefix) cost. Fortunately that
grinding can be done with hash operations rather than ECC - even if we
needed 32-bit prefixes eventually computing 32-bit hash collisions is
plausible, and more reasonable 8-bit is quite doable now.

-- 
'peter'[:-1]@petertodd.org
00000000000000013f56c73dbb82447ba01e303648109b2e7ea0adf6ca53a7ff