Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of petertodd.org
	designates 62.13.148.161 as permitted sender)
	client-ip=62.13.148.161; envelope-from=pete@petertodd.org;
	helo=outmail148161.authsmtp.com; 
Date: Mon, 13 Jan 2014 16:27:52 -0500
From: Peter Todd <pete@petertodd.org>
To: Alan Reiner <etotheipi@gmail.com>
Message-ID: <20140113212752.GA9098@petertodd.org>
References: <op.w9kkxcityldrnw@laptop-air.hsd1.ca.comcast.net>
	<CABsx9T2G=yqSUGr0+Ju5-z9P++uS20AwLC+c3DnFMHtcQjQK6w@mail.gmail.com>
	<CAAS2fgTz0TaGhym_35V3N2-vHVzU9BeuV8q+QJjwh5bg77FEZg@mail.gmail.com>
	<20140113194049.GJ38964@giles.gnomon.org.uk>
	<CANAnSg30V01B_3LCJ09sTwcsYa4_WOg3sKd-=p6COZS6w0b-uA@mail.gmail.com>
	<52D4458C.6010909@gmail.com> <20140113201407.GB7941@petertodd.org>
	<52D44F86.1040407@gmail.com>
	<20140113210217.GO38964@giles.gnomon.org.uk>
	<52D45755.60402@gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
	protocol="application/pgp-signature"; boundary="G4iJoqBmSsgzjUCe"
Content-Disposition: inline
In-Reply-To: <52D45755.60402@gmail.com>
User-Agent: Mutt/1.5.21 (2010-09-15)
Cc: bitcoin-development@lists.sourceforge.net
Subject: Re: [Bitcoin-development] Stealth Addresses
Precedence: list


--G4iJoqBmSsgzjUCe
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

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
> >
>=20
> Fair enough.  I haven't spent much time thinking about that use case.=20
> 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.

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

--G4iJoqBmSsgzjUCe
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)

iQEcBAEBCAAGBQJS1FpYAAoJEBmcgzuo5/CF+AAIALfGJF/uIYAirWaoBBdJb1vF
i2W8gb5itjg9keCLvj7y1jdTq2inDA5CArPUlRoWEm56UAt1mGw7sbQQomPDJKlw
0N8xp//JlKLCXEdZqFgBGqx9BS7Akoihsu6zQEgtX7UbeoypnxbgMc0QJOdgfosy
hkYz38iUOCt0jBitQckKbbSniuGzAhjh41E/Tmv/pXxVJL734dIZvqlOBAsWEx1n
+qF7lQpcMJ1zE4u2CITN0AYxQZ7DRPsAiqKS8+wBx+fW0MaGWNcJM5OnDlu6wTcQ
tZHV8hVSwZhgYw3vssBlNG9HpZ5dvFm8oj8XY/R/UpE+bWRCObzXaIFHi2JKde0=
=BZgv
-----END PGP SIGNATURE-----

--G4iJoqBmSsgzjUCe--