From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194] helo=mx.sourceforge.net) by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1W9mvo-0007G3-Ni for bitcoin-development@lists.sourceforge.net; Sun, 02 Feb 2014 02:37:12 +0000 Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of petertodd.org designates 62.13.149.112 as permitted sender) client-ip=62.13.149.112; envelope-from=pete@petertodd.org; helo=outmail149112.authsmtp.co.uk; Received: from outmail149112.authsmtp.co.uk ([62.13.149.112]) by sog-mx-4.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1W9mvm-0001Aw-Tg for bitcoin-development@lists.sourceforge.net; Sun, 02 Feb 2014 02:37:12 +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 s122b0PA001222; Sun, 2 Feb 2014 02:37:00 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 s122auIM001894 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Sun, 2 Feb 2014 02:36:59 GMT Date: Sat, 1 Feb 2014 21:36:51 -0500 From: Peter Todd To: Adam Back Message-ID: <20140202023651.GA18666@savin> References: <20140124090218.GA15398@savin> <20140124154235.GA3741@netbook.cypherspace.org> <20140124161330.GA31233@petertodd.org> <20140125161901.GA17457@netbook.cypherspace.org> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="k1lZvvs/B4yU6o8G" Content-Disposition: inline In-Reply-To: <20140125161901.GA17457@netbook.cypherspace.org> User-Agent: Mutt/1.5.21 (2010-09-15) X-Server-Quench: e419984a-8bb2-11e3-b802-002590a15da7 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR aAdMdgAUHlAWAgsB AmIbW1ZeU1t7XGo7 bAxPbAVDY01GQQRq WVdMSlVNFUsrAB4D V1tnLxlydg1PfDBz YEZmXT4OWEVzfE55 E1NcRz8EeGZhPWMC AkhYdR5UcAFPdx8U a1UrBXRDAzANdmIj BwY4MnF5MDtRKS9U TwcRZUgfXF0CFDox DxkOES9nA0wMDzo+ LhhuMlcdBkcXPQ0T G3ZpGWgVYX1aOSdf A0pKASkcK1QfSi4s FQZXW1IrWBdUQDsU DBoyagVFHydbUC5V TEJJRwsCEDhIS2gg 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: 1W9mvm-0001Aw-Tg Cc: Bitcoin Development Subject: Re: [Bitcoin-development] (space) efficient reusable addr via weil pairing IBE (Re: 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: Sun, 02 Feb 2014 02:37:12 -0000 --k1lZvvs/B4yU6o8G Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Sat, Jan 25, 2014 at 05:19:01PM +0100, Adam Back wrote: > I think I figured out a proof of existance for a space efficient way to do > better than bloom filters/prefix/bloom-bait. (Must have been dreaming on= it > as I woke up with the idea following Peter's suggestion to try prove inst= ead > if its possible or not:). >=20 > I wrote up the details here: >=20 > https://bitcointalk.org/index.php?topic=3D431756.new One of the main reasons I post to the bitcoin-development mailing list rather than the forum is because the mailing list is archived by many different, independent, parties. The forum is not - as an example archive.org didn't have that URL until I manually told it to archive it. So I'm taking the liberty of reposting your two posts there below: [quote author=3Dadam3us link=3Dtopic=3D431756.msg4729682#msg4729682 date=3D1390660452] So have been talking with Greg Maxwell, Peter Todd, Jeremy Spillman, Mike Hearn, Bytecoin and others about reusable addresses. There is a summary of the situation here http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03= 792.html and I had posed th question of whether it was possible to do better at all with Peter Todd: [quote author=3Dadam3us on bitcoin-dev] Now while it would be clearly a very nice win if reusable addresses could be made SPV-like in network characteristics and privacy, but we dont have a plausible mechanism yet IMO. Close as we got was Greg's enhancement of my/your "bloom bait"/"prefix" concept to make multiple candidate baits to provide some ambiguity (still allows elimination, just slightly less of it). If we can find some efficient crypto to solve that last one, we could even adopt them generally if it was efficient enough without needing interactive one-use address release [/quote] and Peter proposed also the related problem of proving something about that existence or not of a solution to that problem. I think I have a proof-of-concept solution that proves by example we can do better in space efficiency, linkability defense and non-interactivity than my bloom bait, Peter Todds related prefix; and Greg Maxwell's extended bloom bait described http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03= 705.html. So the idea is to use an IBE scheme as a building block in analogous way to my 1996 problem statement for NIFS and 1998 observation that a novel use for an IBE scheme can provide a generic solution to NIFS, and the arrival in 2001 of the first efficient / sensible trapdoor steepness (*) IBE with the introduction of the Weil Pairing problem by Dan Boneh and Matt Franklin described here http://en.wikipedia.org/wiki/Boneh%E2%80%93Franklin_scheme. Greg summarized IBE as follows on IRC: [quote] (for those who may) not be familar with IBE stuff: The idea is that the user has a master private key, which results in a master public key. Anyone can take a prior block hash and combine it with the master public key to get a session pubkey which could be used to encrypt a chaincode included in an OP_RETURN. Using the master private key the user can derrive the session private key, which can then be used to recognize transactions using the same session key. In IBE (identity based encryption) this is all used a bit differently: the master keys are held by a CA, and the session ID is your email address, and now anyone can make a public key for you=E2=80=94 but you need= the CA's help to get your private key) [/quote] Basically as Greg said your public key is your address (an email address, a block hash, whatever is convenient and unique) and from that and the master public key of the IBE server, the server can compute a private key corresponding to that. The master public is usually considered to be a system-wide domain parameter. Naturally enough because a side effect of this is that the IBE server can decrypt everyones email people were never too excited about the prospect. However my 1998 NIFS observation is by acting as your own IBE server (each user creates their own master public server key) they can create a sequence (NIFS) or set (bitcoin reusable address) of public keys with interesting and publicly derivable properties! It is my conclusion from 1996 that to solve this with DL directly at least in the NIFS case appears to be not possible. So basically the reusable address becomes an IBE public key, the existing public derivation via DH or EC Elgamal/ECIES or whatever variant (bytecoins, mine, Peter Todd/Amir Taaki's) arrives at a factor that can be recovered. So with my variant (random sender generated multiplication factor encrypted with ECIES) you could encrypt the factor with a pub=3DIBE-extract(master pub, id=3Dprevious block hash) using the previous block hash as the "identity" and the users own self-owned IBE "server". For Bytecoin & Peter Todd/Amir Taaki EC DH version using input or auxilliary addresses to save space its not even necessary to send the factor, its already sent. So then you send a separate message to do with secure delegatable filtering, a more secure/more space efficient bloom filter/prefix replacement, and this is a more flexible structure. So the secure delegatable filter is you separately add an encrypted bloom bait Greg suggested (eg 1byte prefix communicated with public address.) And you can even combine that with Greg's extended bloom bait above to add anonymity set within the block. Consequently you can now securely and very network/space efficiently securely delegate searching a block by computing the private key for the IBE pub key that any sender would use for that block, and sending it as a query to a random (or node-capture defended random selected node). The node can decrypt the encrypted bloom baits with it, but remains powerless to correlate with bloom baits to other payments received by the same user in bother blocks. (In practice you might need an epoch not block or overlapping test because the user does not have full assurance of their tx ending up in the pending block). About weil pairing, and new hardness crypto risk, this is also the hardness assumption under some ZK-SNARKs as I think used in zerocash, and while ZK-SNARK introduces its own complexity/crypto system risk on top; in my view weil pairing is slightly lower assurance/review not so widely used relative to EC DL problem. Anyway the interesting thing to say about that is in the event this scheme got broken in the future it falls back to the scheme that is being proposed using prefix. Ie its no worse than that from linkability and likely would retain some cost even if broken-- asymmetric crypto breaks are usually somewhat gradual. This looks more expensive and non-indexable though I didnt look to see if there is any ciphertext only or batch precomputation that could be squeezed out of it. Obviously its more CPU intensive and some eg fee mechanism to prevent node DoS could be nice, but it seems to demonstrate a proof by existence that it is possible to do better. Finally I think it maybe within possibility to do further than this because it is not technically necessary to delegate decryption, only to delegate filtering, which can be a simpler requirement. Adam (*) There was an earlier scheme by Maurer et al if I recall, but to get a 1024-bit security margin you had to perform a discrete log attack on a 512-bit prime, so the key generation cost was immense, hence "sensible trapdoor steepness" thats very shallow in tems of work difference between setup cost and crypto system strength. [/quote] ------ [quote author=3Dadam3us link=3Dtopic=3D431756.msg4732503#msg4732503 date=3D1390669542] [quote author=3DMike Hearn link=3Dtopic=3D431756.msg4730986#msg4730986 date=3D1390664867] You would need epochs for another reason. Recall that with Bloom filtering the remote node is asked for blocks in batches of 500 at a time and the remote end handles updating the filter as transactions are matched. This is to avoid the performance hit of a network round-trip for every block. [/quote] I see I dont think I realized that aspect of how bloom query works. So you then with IBE-based filtering could send multiple keys, one for each block; but you are implicitly linked by being in one query, so you'd just as well mark your key with your preferred epoch size and sender uses epoch number in the query. I think Greg is pointing out on IRC that by having a fairly small epoch you can choose later to go down to that epoch size or scale up by sending multiple epoch keys in a batch, a privacy/network round-trip trade off. Re my other problem with epochs ("In practice you might need an epoch not block or overlapping test because the user does not have full assurance of their tx ending up in the pending block") I think that maybe fixable, if the blocknumber is chosen by the sender, and communicated in enough bits to be mostly unambiguous in the message. Then the node can index them by sen block num and no ambiguity. It could be that another way to partly obscure ownership of queries would be to relay queries and responses and mix other peoples queries with your own in a batch, however as we are considering the SPV client case relaying other peoples queries seems hard to gather query traffic on demand and to use more bandwidth than it saves relative just issuing smaller batches. You could have relaying in the network eg using the embedded Tor but waiting for queries to mix with adds latency, and suffers flood attacks on mix-nets (send fake encrypted query traffic to flush out a tx, that has no-anon set vs the person doing the flooding who can distinguish their own queries). Adam [/quote] --=20 'peter'[:-1]@petertodd.org 000000000000000075829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0 --k1lZvvs/B4yU6o8G Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.14 (GNU/Linux) iQGrBAEBCACVBQJS7a9CXhSAAAAAABUAQGJsb2NraGFzaEBiaXRjb2luLm9yZzAw MDAwMDAwMDAwMDAwMDA3NTgyOWY2MTY5Yzc5ZDdkNWFhYTIwYmZhOGRhNmU5ZWRi MjM5M2M0Zjg2NjJiYTAvFIAAAAAAFQARcGthLWFkZHJlc3NAZ251cGcub3JncGV0 ZUBwZXRlcnRvZC5vcmcACgkQJIFAPaXwkfvI5wf/UuajE9MNJROmCUtrdCzE5MaZ n9Y/UK8QcHq1pcqSNazdFsV4KNHnBh/COYbgNcga2a8jrvCs4a+67rBB2LCejJXU RQJ0I5oHTTDV+cDaL2VLZ+zWFD16tVac7zM0Dp0IF+IzTRX4bBAFrX+iTsEZqMjf FRaedRg11gARCi4R2dkeNpug+CGXw4frc3B9btztX9QKfAPYhOaO82ErlRFRX7sb jeUKZxpvmKFJPO41+YmuzZFjjlqaaJDxGtQRXS+0Rn42xj62S+8X/wUtSRfnbeFW JBdqS4ZEGMj9QyChZYcGaQzyR5pmujLxl0AXwuic0he6b8BeN/mjDHoCPYa7mg== =OTmA -----END PGP SIGNATURE----- --k1lZvvs/B4yU6o8G--