From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191] helo=mx.sourceforge.net) by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1W6cem-00046k-Ci for bitcoin-development@lists.sourceforge.net; Fri, 24 Jan 2014 09:02:32 +0000 Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of petertodd.org designates 62.13.149.56 as permitted sender) client-ip=62.13.149.56; envelope-from=pete@petertodd.org; helo=outmail149056.authsmtp.com; Received: from outmail149056.authsmtp.com ([62.13.149.56]) by sog-mx-1.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1W6cej-0001D7-Re for bitcoin-development@lists.sourceforge.net; Fri, 24 Jan 2014 09:02:31 +0000 Received: from mail-c235.authsmtp.com (mail-c235.authsmtp.com [62.13.128.235]) by punt17.authsmtp.com (8.14.2/8.14.2/) with ESMTP id s0O92NNg087303; Fri, 24 Jan 2014 09:02:23 GMT Received: from savin (76-10-178-109.dsl.teksavvy.com [76.10.178.109]) (authenticated bits=128) by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id s0O92ImY046753 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Fri, 24 Jan 2014 09:02:20 GMT Date: Fri, 24 Jan 2014 04:02:18 -0500 From: Peter Todd To: Gregory Maxwell Message-ID: <20140124090218.GA15398@savin> References: MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="/04w6evG8XlLl3ft" Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) X-Server-Quench: 3be9c4fa-84d6-11e3-b802-002590a15da7 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR aAdMdAYUElQaAgsB AmIbW11eUF97W2I7 bAxPbAVDY01GQQRq WVdMSlVNFUsrAWMI BGdDOxl2cQJDezBx YkViWj5YDhFzJkIr E1NcETkAeGZhPWMC AkhYdR5UcAFPdx8U a1UrBXRDAzANdhES HhM4ODE3eDlSNilR RRkIIFQOdA4hFz8g Dx4FB301EFAeTi83 IlQvJlIGEV0KP15a X-Authentic-SMTP: 61633532353630.1023:706 X-AuthFastPath: 0 (Was 255) X-AuthSMTP-Origin: 76.10.178.109/587 X-AuthVirus-Status: No virus detected - but ensure you scan with your own anti-virus system. X-Spam-Score: -1.5 (-) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain -0.0 SPF_PASS SPF: sender matches SPF record X-Headers-End: 1W6cej-0001D7-Re Cc: Bitcoin Development Subject: Re: [Bitcoin-development] Bait for reusable addresses X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 24 Jan 2014 09:02:32 -0000 --/04w6evG8XlLl3ft Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Wed, Jan 15, 2014 at 05:23:04PM -0800, Gregory Maxwell wrote: > It also has a downside of not being indexable for the server, the > server must do O(clients * reusable-address-txn) work and the work > includes an ECC multiply. >=20 > An idea that Adam Back had originally proposed was including optional > "bloom bait", a small token=E2=80=94 say 8 bits=E2=80=94 that distinguish= ed > transactions which allowed an anonymity set vs filtering trade off. > Such a bait would be indexable, enabling faster lookup too. >=20 > But bloom bait has privacy problems more severe than the current SPV > bloom filtering. While you leak information to your SPV servers today > if you use bloom filtering the leak usually goes no further. So a > compromise requires both a statistical attack _and_ using SPV servers > that log data against your interest. With bloom bait the whole > network can see the relation. That is unfortunate. Yes, but remember I proposed prefixing in my blockchain data query paper because it's a trade-off between theoretical good privacy and brittleness. The real world experience is that users, or to be exact wallet authors, turn down SPV privacy parameters until bloom filters have almost no privacy in exchange for little bandwidth usage. (though load on the server is unchanged of course) The brittleness comes in because the moment you connect to a malicious, data-collecting peer, the contents of your wallet are all revealed. Frankly that'd be a disaster for CoinJoin too, and I think it'd be a bigger disaster than the poor specificity patterns leaked by prefix usage. If anyone wants to deanonymize CoinJoin there will be a lot of incentives to do so, and you only need wallet content data to do that. > I suggest instead that with optional bait is included in an address > that the sender compute H(nonce-pubkey) and then pick one byte at > random out of the first 16 and xor it with the specified bait and > store the result in the transaction. An SPV server can now index the > bait as it comes in by extracting 16 8-bit keys from each transaction > (the 16 bytes xored with the bait in the transaction). When the > client wants to search for transactions it can give the server a list > of keys its interested in=E2=80=94 including their real key and number of > random number of cover keys. >=20 > I didn't give any though into the parameters 8-bits and 16 dimensions. > Some reasoning should be done to fix the parameters in order to make > them the most useful: e.g. >=20 > Systems derived from more complex linear codes might give better > performance, e.g. two secret bloom baits, two prefixes in the > transaction bait0^random_char[0-8], bait1^random_char[0-8], server > extracts 16 keys.. and returns to the client transactions which have > at least two key matches with their list. >=20 > Obviously whatever is used needs to be easy to implement, but schemes > loosely based on fountain codes should only require picking some > things and xoring... so they should be simple enough. Well, that's the big question: How much extra data do we need and what's the chance that this will get turned into miner-committed indexes? Or even just provided at all? We keep on saying that miner-commitments may next happen at all because of performance issues, and adding n extra indexes doesn't exactly help that situation. I really suspect that the moment that gets implemented we'll see wallet software use that for simple security reasons, so plan ahead for that. In the short term without miner-commitments it's just a question of how much extra load we subject servers to. Again, getting people to even implement prefixes isn't a trivial argument to make, yet bloom has some serious scalability problems. (though does do roughly what you're proposing) In any case, your "bait" proposal is stealth address specific - how would you propose applying the same principle to all addresses? Again, it's a tradeoff between brittleness - connecting to a malicious peer reveals your wallet - and blockchain stats data. --=20 'peter'[:-1]@petertodd.org 0000000000000001315c71472fdce344f85f794a7135e25554f2b51dfa6b83c4 --/04w6evG8XlLl3ft Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.12 (GNU/Linux) iQGrBAEBCACVBQJS4iwZXhSAAAAAABUAQGJsb2NraGFzaEBiaXRjb2luLm9yZzAw MDAwMDAwMDAwMDAwMDFkOGI5ZDQzOGMxOGU4NTY3MzVkZGFlNWIxZDkxODQxNjAx MDM1MGQxOTc5NGFhYjYvFIAAAAAAFQARcGthLWFkZHJlc3NAZ251cGcub3JncGV0 ZUBwZXRlcnRvZC5vcmcACgkQJIFAPaXwkfspBwf9E4EBKjZ8IiwEVyo8JTXhn5kM pzCKrc/FqX1sU6bisHQwAXxA5nERZL6EIdvWvv4h6Se2BMlBsWD5FZptYCjVjwYd PM6KBy39QzJnfr7t+YitBUPiG/zVXstqtaCgvBdDPTfsVeNmWAwjNFVwKThjmp0l uvfpN6c+j8kiS5qNGRc3InosdnxUV/zJXDu9r9nm6H2J40r8LGtgc15+IKRBM7hQ dLV4qGE7O8ED49HVQJ37FXKgUv5N+lDf8j48GtkdxbPHPubMafgEYudPHpIbLIpo celEi2lPTh8lI/qLkg1HesKMRpMp7Qc/HON670sbAmancEU7SNwPvNMaM00lyA== =XwWj -----END PGP SIGNATURE----- --/04w6evG8XlLl3ft--