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-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1Y2qbH-0005fM-Ai for bitcoin-development@lists.sourceforge.net; Mon, 22 Dec 2014 00:11:51 +0000 Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of petertodd.org designates 62.13.148.108 as permitted sender) client-ip=62.13.148.108; envelope-from=pete@petertodd.org; helo=outmail148108.authsmtp.net; Received: from outmail148108.authsmtp.net ([62.13.148.108]) by sog-mx-1.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1Y2qbF-0007bk-ER for bitcoin-development@lists.sourceforge.net; Mon, 22 Dec 2014 00:11:51 +0000 Received: from mail-c235.authsmtp.com (mail-c235.authsmtp.com [62.13.128.235]) by punt15.authsmtp.com (8.14.2/8.14.2/) with ESMTP id sBM0Ben1008621; Mon, 22 Dec 2014 00:11:40 GMT Received: from savin.petertodd.org (75-119-251-161.dsl.teksavvy.com [75.119.251.161]) (authenticated bits=128) by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id sBM0BbEI026263 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Mon, 22 Dec 2014 00:11:39 GMT Date: Sun, 21 Dec 2014 19:11:37 -0500 From: Peter Todd To: bitcoin-development@lists.sourceforge.net Message-ID: <20141222001136.GA10165@savin.petertodd.org> References: <20141212090551.GA8259@muck> <20141220144800.GA26284@savin.petertodd.org> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="cWoXeonUoKmBZSoM" Content-Disposition: inline In-Reply-To: <20141220144800.GA26284@savin.petertodd.org> User-Agent: Mutt/1.5.21 (2010-09-15) X-Server-Quench: 1a54f6f9-896f-11e4-b396-002590a15da7 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR aAdMdAAUHFAXAgsB AmIbW1ReUVx7XWM7 bA9PbARUfEhLXhtr VklWR1pVCwQmQm58 BmxMJ2BydQNEfn0+ ZEVjWnAVXRV/cRB7 FEdJHWQAM3phaTUb TRJbfgVJcANIexZF O1F6ACIKLwdSbGoL NQ4vNDcwO3BTJTpY RgYVKF8UXXNDIj4x DwoPGTwzHEoDXCUy N1QsJ0IDEUsXUA0K K1wmVxcfPVoqFwda HkpEHC5eIREIQSZj JAVGXAskHSVZSDYU JQchKRtFGVQI X-Authentic-SMTP: 61633532353630.1023:706 X-AuthFastPath: 0 (Was 255) X-AuthSMTP-Origin: 75.119.251.161/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: 1Y2qbF-0007bk-ER Cc: Andrew Miller Subject: Re: [Bitcoin-development] The relationship between Proof-of-Publication and Anti-Replay Oracles 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: Mon, 22 Dec 2014 00:11:51 -0000 --cWoXeonUoKmBZSoM Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Sat, Dec 20, 2014 at 09:48:01AM -0500, Peter Todd wrote: Andrew Miller asked me to publish the following to the mailing list on his behalf: (https://twitter.com/socrates1024/status/546819355565391872) One of the main points in this note is that you can use a "proof-of-publication" system to implement an "anti-replay" system. However this isn't true - at least not given the description of proof-of-(non)-publication in 2) and the definition of "anti-replay" given here. In 2), proof-of-*non*-publication allows you to prove that *some specific message* has never been published. You can imagine having a function ProveNotPublished(m), which proves "message m was not published." However, the anti-replay mechanism is about proving that *no* message satisfying some property has been published. Hence VerifyAntiReplaySig(m, p, s) checks that "for all possible messages m' (distinct from m), AntiReplaySign(m', p) has not been called." This isn't *just* splitting hairs, this distinction is actually relevant for analyzing several cryptocurrency designs. You can imagine extending the definition of proof-of-(non)-publication to take in some predicate P, so that you can prove "no message m such that P(m) holds has ever been published." However, to do this efficiently requires anticipating some classes of P and building some appropriate indices. - As a baseline, as long as you have the whole blockchain available, you can scan through the entire blockchain and evaluate P for every transaction, but this is pretty inefficient. - Other tradeoffs are available if you are willing to trust some (quora of) servers to maintain indices for you - Bitcoin's UTXO set effectively supports a predicate for each txout, where P(x) =3D "x is a valid tranasction that spends " - Ethereum contracts, in a sense, allow for general purpose contracts to 'build-your-own" index. On the other hand its key-value store doesn't support range queries, so it's not necessarily "universal" or as expressive as SQL, for example. But the point isn't to argue about design choices and tradeoffs in this thread. The main point I want to make is: *Indexes and Validation Matter!* The classic "proof-of-publication" system is to embed opaque data (as far as bitcoin miners are concerned) in transactions using OP_RETURN. A significance of establishing "proof-of-publication" as a universal underlying primitive is that this OP_RETURN trick is then sufficient for anything you might want. But part of what Bitcoin provides is indexing and validation/exclusion, and this is important for supporting efficient anti-replay proofs. Proof-of-(non)-publication alone isn't sufficient for this. --=20 'peter'[:-1]@petertodd.org 00000000000000000a7b40becd0babbd64ec49b8b34823fb4f4b081c95188b66 --cWoXeonUoKmBZSoM Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- iQGrBAEBCACVBQJUl2GzXhSAAAAAABUAQGJsb2NraGFzaEBiaXRjb2luLm9yZzAw MDAwMDAwMDAwMDAwMDAwYTdiNDBiZWNkMGJhYmJkNjRlYzQ5YjhiMzQ4MjNmYjRm NGIwODFjOTUxODhiNjYvFIAAAAAAFQARcGthLWFkZHJlc3NAZ251cGcub3JncGV0 ZUBwZXRlcnRvZC5vcmcACgkQJIFAPaXwkfs5oAf/TQKr5Sj6WrJk0XTiJ6kg3pkg SN23qomrdBPC1JDU5wsOgw3XUeZ013N+kGz0+uft+w3jksQxPyCVfpS2aUt8s2+i PO2LfiC9mDDBnBbwfIoJyMDymJWppEtC2xw0jpjl4APC73NNGQrU9dox+/xW1w/D 2IzjQYz3c8NqxgqyYYIYAsj+0LI2Q4joyEhr1JQYDdg9iZBXDBsXLV48x50zgcV6 Dm+XIykqT/EWeYvvB6kh6NkNBy5mGdM+XuhoJhH+xHhFbTFTkd3pJgyU96vXVxDo 2PKhU4l9ZchqLzPwJh/0vq1s0Dybbju2Ibc3Dl5GOy2M5aIIONFbPX7IgViUKw== =dCDQ -----END PGP SIGNATURE----- --cWoXeonUoKmBZSoM--