Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of petertodd.org
	designates 62.13.149.95 as permitted sender)
	client-ip=62.13.149.95; envelope-from=pete@petertodd.org;
	helo=outmail149095.authsmtp.com; 
Date: Fri, 6 Jun 2014 12:46:39 -0400
From: Peter Todd <pete@petertodd.org>
To: Adam Back <adam@cypherspace.org>
Message-ID: <20140606164639.GB14891@savin>
References: <20140606081933.GA29458@savin>
	<20140606084852.GA30247@netbook.cypherspace.org>
	<20140606090441.GA19256@savin>
	<20140606104543.GA31085@netbook.cypherspace.org>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
	protocol="application/pgp-signature"; boundary="l76fUT7nc3MelDdI"
Content-Disposition: inline
In-Reply-To: <20140606104543.GA31085@netbook.cypherspace.org>
User-Agent: Mutt/1.5.21 (2010-09-15)
Cc: bitcoin-development@lists.sourceforge.net
Subject: Re: [Bitcoin-development] Bloom bait
Precedence: list


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

On Fri, Jun 06, 2014 at 12:45:43PM +0200, Adam Back wrote:

(changed subject line as this discussion has nothing to do with
NODE_BLOOM)

> As I recall prefix brute forcing was a bit twiddle saving, ie searching f=
or
> EDH key that has the users public prefix.  That does not improve privacy
> over an explicit prefix, it saves a byte or so at the expense of average =
128
> EDH exchanges to send and provides also some probably relatively ineffect=
ive
> plausible deniability by enabling the transaction to be indistinguishable
> from some other (not very common) types of transaction.

I think you should re-read my original proposal; there's a whole host of
misunderstandings above, for instance I have no idea where you got the
idea that it has anything to do with "saving a byte" came from, or where
the number 128 came from.

> >don't do that they have privacy equal or better than bloom filters, but
> >with better scalability.
>=20
> either its full node only where prefixes are not used, which is less
> scalable than bloom; or prefixes are used explicitly or implicitly
> (brute-force) and either way privacy is weakened by the extra correlation
> hook provided by elimination from the network graph of payments with
> mismatched prefixes.

Again, you have a misunderstanding. Both bloom filters and prefix
filters are just ways of giving a peer a probabalistic filter to match
transactions against. Where they differ is that bloom filters has O(n)
scaling, where n is the size of a block, and prefix filters have O(log n)
scaling with slightly(1) higher k. Again, if you *don't* use brute forcing
in conjunction with prefixes they have no different transactional graph
privacy than bloom filters, but the better scalability lets you do
things like split your queries across multiple peers that give you
better protection against hostile nodes.  Additionally prefix filters
are compatible with future miner committed indexes to make the data
authenticated.

1) see Amir's experience implementing prefix lookup in Obelisk

> We need to consider the two types of privacy involved.  Privacy from the
> full node an SPV client is relying on to find its payments, vs privacy fr=
om
> analysis of the public transaction graph.

Agreed

> The latter is more damaging.

Maybe! If adversaries are operating a significant fraction of the peers
you are connecting to the current design of bloom filters + HD wallets
results in situations where those adversaries have better transactional
graph information than the alternative.

> Better to design for privacy against future analysis of
> public info, than
> privacy by argument to select non-hostile nodes.  Tor has changed recently
> to account for the fact that chosing fresh random nodes is actually
> worse. ie you have a probability of identity/address identification
> per route/node,
> and repeatedly selecting routes/nodes just cumulatively increases the cha=
nce
> you'll be identified.  Better to pick a random node, identify it and stick
> to it and hope you chose well.

That's basically what Electrum and Obelisk already do - by default you
connect to a relatively small set of blockchain data servers operated by
well known people and use the same server repeatedly.

Applying that to the P2P network however is tricky as there is a huge
amount of churn in the nodes:

    #bitcoin-dev/14/06/14-06-06.log:11:18 < hearn> bitcoinj can't use
    [service bits] as it relies on DNS seeds and that is unlikely to change
    any time soon due to the general churn rate in the network making it
    hard to bootstrap quickly using just remembered sets of IPs.

> Maybe other simpler, but yes there was the proof of concept that the math
> exists in the form of the weil pairing.
>=20
> https://bitcointalk.org/index.php?topic=3D431756.new

I know, where can I find running code? Remember that a bug can easily
lose thousands of dollars worth of Bitcoins.

--=20
'peter'[:-1]@petertodd.org
00000000000000001d2af1653c415b7801ce4c9b18ac7e87bef597e652b203e6

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

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

iQGrBAEBCACVBQJTkfBrXhSAAAAAABUAQGJsb2NraGFzaEBiaXRjb2luLm9yZzAw
MDAwMDAwMDAwMDAwMDAxNzhhZDVlNmY3YjM1MzVjNjEwNmI3YzZmMGJkZWI4MzFk
YmQ4OWM2NDJiNmYyNzEvFIAAAAAAFQARcGthLWFkZHJlc3NAZ251cGcub3JncGV0
ZUBwZXRlcnRvZC5vcmcACgkQJIFAPaXwkfuJywf/Rj4CXObu9DlW4CvmhSsaa9jr
Q8wcaI2VK7zSDoZFn5XsmyL4rXRov8y9s/VtPrja98aSErxLY8BGjiJVM5fh2kbS
XZ02Hi8VxwKevNexVQW3XzKM1wj7vbm4JXn+cHkfj+NDKzR+QcZqgx95LB3XvRK4
fSnkWakzDrpvrR5PC/XGOiAYhpg1HWXYAvaflmeiO33Y/82Bj3yrjxq14RbkHjo/
262LAZJ0SHD7d3S0B/53Jg9qHM79HkJEmIu8q/qAOdczv6VDhYnWQRuYBPoNip2c
j/bFC8qI4QfqqFuZpadpHjNLivGIB1vw/szCpBwds6E5Janm2LMdCROezaj00w==
=wJw+
-----END PGP SIGNATURE-----

--l76fUT7nc3MelDdI--