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 1Y2LKH-0007s1-PD for bitcoin-development@lists.sourceforge.net; Sat, 20 Dec 2014 14:48:13 +0000 Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of petertodd.org designates 62.13.148.101 as permitted sender) client-ip=62.13.148.101; envelope-from=pete@petertodd.org; helo=outmail148101.authsmtp.com; Received: from outmail148101.authsmtp.com ([62.13.148.101]) by sog-mx-1.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1Y2LKF-0000Vl-KW for bitcoin-development@lists.sourceforge.net; Sat, 20 Dec 2014 14:48:13 +0000 Received: from mail-c237.authsmtp.com (mail-c237.authsmtp.com [62.13.128.237]) by punt18.authsmtp.com (8.14.2/8.14.2/) with ESMTP id sBKEm565046100 for ; Sat, 20 Dec 2014 14:48:05 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 sBKEm1iQ075759 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO) for ; Sat, 20 Dec 2014 14:48:04 GMT Date: Sat, 20 Dec 2014 09:48:01 -0500 From: Peter Todd To: bitcoin-development@lists.sourceforge.net Message-ID: <20141220144800.GA26284@savin.petertodd.org> References: <20141212090551.GA8259@muck> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="17pEHd4RhPHOinZp" Content-Disposition: inline In-Reply-To: <20141212090551.GA8259@muck> User-Agent: Mutt/1.5.21 (2010-09-15) X-Server-Quench: 3411be74-8857-11e4-9f74-002590a135d3 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVJwpGK10IU0Fd P1hXKl1LNVAaWXld WiVPGEoXDxgzCjYj NEgGOBsDNw4AXQV1 JB0aXVBSFQF4ABgL AhYUUh08cABYeX95 e0RnX25aWkVlcE56 XU8aVh99EDphMQEf V0VfcgoacgFMfBsL aVR+VSFYZmEabnJl QEpqZj1teGRRd3gQ GllXcANKSB9QQzJn USMoHCkkGkwDAik+ MREiLUYZEUANBw0O MVZpQ18cOgMTDQtF H0BVSCVUO0YMSixj NRldWkBbFzMYeTpW BhwjKwNJBTowEiNe CANsTQ0OThlISC1B WX56SCQmCFUyTwAA X-Authentic-SMTP: 61633532353630.1024: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: 1Y2LKF-0000Vl-KW Subject: [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: Sat, 20 Dec 2014 14:48:13 -0000 --17pEHd4RhPHOinZp Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Gregory Maxwell recently pointed out to me in private conservation that there potentially existed a fundemental disagreement between him and I on our philosophical approaches to blockchains, in that he prioritised the notion of the blockchain as an anti-replay oracle, and I prioritised it as a publication layer. Here I'll talk about the differences and simularities between those two approaches. What's Anti-Replay? =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D We have some action - perhaps spending a txout - and we only want it to be possible for that action to happen once; we don't want it to be possible for that action to be replayed again. This is inherently not possible with cryptography alone as cryptography is just math and any mathematical calculation can be repeated with different parameters. What's an Anti-Replay Oracle? =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D We need the following primitives operating on message m, pubkey p, and a valid signature sig1 for m, p: AntiReplaySign(m, p, sig1) -> sig2 VerifyAntiReplaySig(m, p, sig2) -> True or False Additionally once AntiReplaySign() has been used once for a given pubkey it is impossible to re-run the primitive on a different message m'. This is of course impossible to implement with math alone, but we can implement it with a trusted third party. For instance Carol can perform the AntiReplaySign operation and make the promise that she will only ever perform it once for any given (m,p) tuple. Maxwell points out in CoinWitness=C2=B9 that the anti-replay oracle is sufficient to implement a digital currency. So long as the trusted oracle, or majority of a federation of trusted oracles, is honest coins cannot be double-spent and can be securely passed from owner-to-owner with an ever-growing transcript=E2=81=B1 proving each valid spend. i) The transcript is needed in this model only because the oracles do nothing more than promise to never sign a message twice; it can be removed if the oracles additionally validate transactions in some way. The Blockchain as an Anti-Replay Oracle =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D In Bitcoin miners act as a trusted anti-replay oracle. If they follow the Bitcoin protocol faithfully for any given txout one and only one valid scriptSig will ever be accepted into the blockchain. Thus the spend of a txout is a valid anti-replay-protected signature, and the validity of that signature can be verified by SPV clients with a merkle path to the block headers. Using proof-of-publication to prove non-replay =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D Given a secure proof-of-publication=C2=B2 system we can prove non-replay. We define a valid signature as both being published on that system, as well as there existing no other valid signature. (proof-of-non-publication) An attempt to fraudulently create a second signature will either fail the first test - not being published at all - or will fail the second test - not being able to prove no other valid signature exists. Thus we see that proof-of-publication can be used to securely audit the honesty of an anti-replay oracle, resulting in secure anti-replay protection without the requirement of trust. However the converse is not possible: anti-replay cannot be used to implement proof-of-publication. Knowing that no conflicting message exists says nothing about who be in posession of that message, or indeed, any message at all. Thus anti-replay is not sufficient to implement other uses of proof-of-publication such as decentralized exchange=C2=B3. Anti-replay in place of proof-of-publication to secure audit logs =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D The author's proof-of-concept Uniquebits=E2=81=B4 allows Alice to prove to = Bob that some set of records R_i that she has given to Bob is the same set of records she has given to everyone else - that is no R_i' exists. Secondly Alice can update the records producing R_{i+1}, and Bob can determine if such an update exists. Currently Uniquebits uses proof-of-publication via the Bitcoin blockchain directly for both guarantees. It could however make use of the anti-replay function provided by Bitcoin to satisfy the first requirement with the following protocol: 0) Alice publishes record set R_i such that H(T_i + n_i) is committed in R_i, where T_0 is a txout she controls, and n_i is a nonce. 1) Alice creates T_{i+1}, another txout that she controls, and nonce n_{i+1} 2) Alice creates R_{i+1} which commits to H(T_{i+1} + n_i) 3) Finally to publish R_{i+1} she spends T_i in a transaction X_{i+1} that commits to R_{i+1} (e.g. in an OP_RETURN output, or with pay-to-contract=E2=81=B5/sign-to-contract) This process can be repeated again indefinitely, starting at step #1. When Alice wants to prove to Bob - who has R_i - she simply gives him a SPV proof that transaction X_{i+1} exists in the blockchain along with n_i. This proves that T_i was spent, which can only happen once, and that it committed to R_{i+1}. As the output can only be spent once it is not possible to create a valid-looking R_{i+1}' However to prove to Bob that R_{i+1} is the most recent set of records Alice still needs to use proof-of-publication, by showing him txout T_{i+1} is unspent. Case study: Fidelity-bonded Ledgers/Federated Sidechains =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D The author's Fidelity-Bonded Ledgers=E2=81=B6 and the more general idea of Federated Sidechains=E2=81=B7 both describe the notion of a trusted third p= arty, possibly implemented as a federated majority set, who guarantees the correct maintenance of some financial ledger according to some set of rules. Coins can be moved to/from the ledger by payment to a specific set of scriptPubKey's. Federated sidechains proposes that the scriptPubKey simply be a n-of-m multisig; fidelity-bonded ledgers proposes new opcodes that allow redemption via proof-of-fraud. In any case someone relying on a transaction within the ledger itself still needs to be able to audit that their view of the ledger is the same view everyone else sees; in short that there do not exist double-spends on the ledger. The author's fidelity-bonded ledgers paper proposed that the ledger be made available over a Tor-accessible website to prevent selective censorship. The federated sidechains proposal is mute on this issue. As the state of the ledger is a specific instance of the more general set of records problem that Uniquebits solves as can use the same principles for fidelity-bonded ledgers/federated sidechains. The third party periodically publishes the ledger state to the Bitcoin blockchain allowing anyone to detect if their copy of the ledger is incomplete; if not there may be double-spends in it. Finally proof of such double-spends can trigger the destruction of a fidelity-bond=E2=81=B8 and/or return funds to their rightful owners. (with appropriate opcodes=E2=81=B7) Censorship of the ledger state publications is an issue, however in the case of financial ledgers with pegged funds we can use the pegged funds themselves in the publication. Censoring those publications by preventing the designated txouts from being spent then becomes equivalent to blacklisting funds. This requires a majority of hashing power supporting the blacklist, and is a highly politically charged issue=E2=81=B9 in the Bitcoin community. References =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D 1) Really Really ultimate blockchain compression: CoinWitness, Gregory Maxwell, Aug 19th 2013, Accessed 2014-12-20, https://bitcointalk.org/index.php?topic=3D277389.msg2961736 2) Setting the record straight on Proof-of-Publication, Peter Todd, Dec 12th 2014, http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/ms= g06570.html 3) Decentralized digital asset exchange with honest pricing and market dept= h, Peter Todd, Feb 9th 2014, http://www.mail-archive.com/bitcoin-development%40lists.sourceforge.net/= msg03892.html 4) Uniquebits, Peter Todd, Accessed 2014-12-20, https://github.com/petertodd/uniquebits/tree/b9213f6769d80305bdd192925e8= bd7bd04239d1b 5) Homomorphic Payment Addresses and the Pay-to-Contract Protocol, Ilja Gerhardt and Timo Hanke, Dec 13th 2012, http://arxiv.org/abs/1212.3257 6) Fidelity-bonded ledgers, Peter Todd, Feb 25th 2013, http://www.mail-archive.com/bitcoin-development%40lists.sourceforge.net/= msg01786.html 7) Enabling Blockchain Innovations with Pegged Sidechains, Blockstream, Oct 22nd 2014, SHA256: 680c71aef9ed578720e25c58fd50de5cdbee755c3800e7601dad9a745ca65cf3, http://www.blockstream.com/sidechains.pdf 8) Fidelity-bonded banks: decentralized, auditable, private, off-chain paym= ents, Peter Todd, Feb 23rd 2014, https://bitcointalk.org/index.php?topic=3D146307.0 9) WARNING: Bitcoin Address Blacklists have been forced into the Gentoo Lin= ux bitcoind distribution by Luke-jr against the will of other core devs. Ge= ntoo maintainers are clueless and not reversing the change. Boycott Gentoo= now., historian1111, Oct 10th 2014, Accessed 2014-12-20, https://www.reddit.com/r/Bitcoin/comments/2ityg2/warning_bitcoin_address= _blacklists_have_been/ --=20 'peter'[:-1]@petertodd.org 000000000000000001eeaba4cdadaf5b8338cb1b2ae0cf969de77437dd83faac --17pEHd4RhPHOinZp Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- iQGrBAEBCACVBQJUlYwcXhSAAAAAABUAQGJsb2NraGFzaEBiaXRjb2luLm9yZzAw MDAwMDAwMDAwMDAwMDAwNmIwZjA5NzllZGQ4MDlmZDNmODBhNDE2YjE0ODVhMTg4 NzRhZGIyNWU4NGQxYjcvFIAAAAAAFQARcGthLWFkZHJlc3NAZ251cGcub3JncGV0 ZUBwZXRlcnRvZC5vcmcACgkQJIFAPaXwkfuCbQf/Xk1BVL5/5rUfCjYDRxJLLRAy v1RYNFI4yNgsUA9Sm4JUs2+SV2eviW7qElG4ybH8CrVlGLCE7BkFgy7aY8bdaMu9 IQOOuecQpZ0wssD/S0/UL/xE6oPcYMlCIi3e90StMY8vVUs4oGTZBLSpNF1i+2// cJJvQnRwqy2yYliCyUuPHEeL8YJSa8z5qzbEvQkqqSOoUGM+/jqbeVWXXWcQn7FL Wh+CU6QiSyeVtIRQnG4rhbzHSYsA0JqOvFDvws4Icd2CEWCnixAR7Z1r+7htoGcw SXppIy8WorDLP0Ow2MHK1OLm5EvMj04UhiiW2yCkQcsR7GCw3hocgy7CgNnJBA== =0y7h -----END PGP SIGNATURE----- --17pEHd4RhPHOinZp--