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-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1Vu3Ld-0008VW-JQ for bitcoin-development@lists.sourceforge.net; Fri, 20 Dec 2013 16:54:49 +0000 Received-SPF: pass (sog-mx-4.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-4.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1Vu3Lc-0003Lh-02 for bitcoin-development@lists.sourceforge.net; Fri, 20 Dec 2013 16:54:49 +0000 Received: from mail-c237.authsmtp.com (mail-c237.authsmtp.com [62.13.128.237]) by punt17.authsmtp.com (8.14.2/8.14.2/) with ESMTP id rBKGsgUb048437 for ; Fri, 20 Dec 2013 16:54:42 GMT Received: from petertodd.org (petertodd.org [174.129.28.249]) (authenticated bits=128) by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id rBKGsYhG079089 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO) for ; Fri, 20 Dec 2013 16:54:37 GMT Date: Fri, 20 Dec 2013 11:54:34 -0500 From: Peter Todd To: bitcoin-development@lists.sourceforge.net Message-ID: <20131220165434.GA23932@petertodd.org> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="XsQoSWH+UP9D9v3l" Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) X-Server-Quench: 69410a28-6997-11e3-94fa-002590a135d3 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVJwpGK10IU0Fd P1hXKl1LNVAaWXld WiVPGEoXDxgzCjYj NEgGOBsDNw4AXQV1 JB0aXVBSFQZ4ABoL AxoUUR48dgJCZn9y bFhgVm5ZWE1lcE56 XU8aVx99EiQJMBcf V0lYfwoacQBKdhcL bFl7VXNcY20aYHNp QEpqZj1qeGQDJi0Q GllXcANKSB9QQzJn UTsPGy4oB1YFRj12 NRE9K0UAFUAaPw0s MFJpRVMdPhsVAQ4W FFtcGDNeb1cGXWIm CAlXUUITHHVWRiFH DxszPwQqSidDQTZV AVAt X-Authentic-SMTP: 61633532353630.1024:706 X-AuthFastPath: 0 (Was 255) X-AuthSMTP-Origin: 174.129.28.249/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 0.0 URIBL_BLOCKED ADMINISTRATOR NOTICE: The query to URIBL was blocked. See http://wiki.apache.org/spamassassin/DnsBlocklists#dnsbl-block for more information. [URIs: petertodd.org] X-Headers-End: 1Vu3Lc-0003Lh-02 Subject: [Bitcoin-development] Censorship-resistance via timelock crypto for embedded consensus systems 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, 20 Dec 2013 16:54:49 -0000 --XsQoSWH+UP9D9v3l Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Embedded consensus systems such as Mastercoin face the risk that the data they need to embed in the host consensus system will be subject to censorship. This censorship can take two forms: whitelists and blacklists. The former we can't do anything about, however the latter requires someone to identify the data-carrying transactions that are to be blacklisted. Embedding data steganographically in transactions is known to be possible in ways that can-not be detected. Even if P2SH^2 (1) is implemented data can be hidden in pubkeys in P2SH scriptSigs, either by using unused pubkeys in CHECKMULTISIG transactions with a simple transform(2) to turn arbitrary data into valid-looking pubkeys, or with some ECC math even usable pubkeys can have data hidden in them.(3) However these methods are unsuitable if the data needs to be provably made public; without the encryption key the data is securely hidden. Almost all consensus systems rely on proof-of-publication(4) and even if the encryption keys are later made public - perhaps by broadcasting them on a P2P network - we've only shifted the problem to proving that the keys were released. Of course, if we then publish them via our host consensus system, *that* act of publishing can itself be censored! Timelock cryptography offers a solution to this problem. Let S(n, k) be a sequential-hard strengthening function that takes key k and number of rounds n, outputting k'. A suitable S() might be the scrypt function. Let E(d, k) be a symmetric encryption algorithm. Finally let H(m) be a cryptographic hash function. To hide data D in a transaction we set k to some random and publicly known value in the transaction and compute k'=3DS(n, k) and D'=3DE(D, k') Then D' is hidden in the transaction, perhaps in an unused pubkey of a CHECKMULTISIG scriptPubKey. Our intended audience can also calculate k' from the public data, and thus recover D in time ~t, thus we know that after time ~t has elapsed all participants in the system can reliably come to consensus. However miners and other parties who may wish to censor D face a dilemma: If they repeat the calculation for every transaction that may be hiding data they delay all transactions for all users. In addition miners have a financial incentive to defect and mine transactions without checking for hidden data. Practical Considerations =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D Efforts should be made to limit the scope of possible transactions as much as possible to reduce the computation required, e.g. by restricting the search space to only transactions with scriptPubKeys starting with some short prefix. This is a balance between computation and censorship resistance. Consideration needs to be made as to how the data will be validated as part of the embedded consensus system, for instance via a checksum or cryptographic signature. Participates in the embedded consensus system should share k' keys among each other to reduce overall effort. This ties back to validation: it must not be possible to distribute a fake k' undetectably. Picking n, and thus the time taken, is a balance. Also there should be some mechanism to update n as technological improvements warrant. Along those lines this method works best when t can be large and immediate consensus is not required. A suitable use-case could be a key-value consensus system for name information where mappings are infrequently changed. The source of k should be such that k' can be computed in advance, however only by the sender. For instance simply using the first txin hash allows the attacker to compute k' in advance themselves. A better choice would be the first (real) pubkey in a scriptPubKey, a value we can both compute in advance, yet is not known publicly. Censorship resistant voting =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 With due care the scheme can be used to allow for censorship-resistant voting. While previously it was believed that miners would inevitably be able to censor any voting scheme - with the exception of certain special cases(5) - provided that the financial incentive to collect fees outweighs the incentive to not count votes we have strong censorship resistance with strong consensus in a fixed amount of time. 1) Gregory Maxwell, [Bitcoin-development] To prevent arbitrary data storage in txouts =E2=80=94 The Ultimate Solution, https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/m= sg01987.html 2) Peter Todd, Re: MasterCoin: New Protocol Layer Starting From =E2=80=9CThe Exodus Address=E2=80=9D, https://bitcointalk.org/index.php?topic=3D265488.msg3377058#msg3377058 3) ByteCoin, Untraceable transactions which can contain a secure message are inevitable, https://bitcointalk.org/index.php?topic=3D5965.0 4) Peter Todd, [Bitcoin-development] Disentangling Crypto-Coin Mining: Timestamping, Proof-of-Publication, and Validation, http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/ms= g03307.html 5) John Dillon, Proposal: We should vote on the blocksize limit with proof-= of-stake voting, https://bitcointalk.org/index.php?topic=3D230864.0 --=20 'peter'[:-1]@petertodd.org 0000000000000001cdaabe80320d14ab5907997ec6ad12eaaa304941c34fc8bd --XsQoSWH+UP9D9v3l Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) iQEcBAEBCAAGBQJStHZKAAoJEBmcgzuo5/CFkhcIAMAfGk6DoYKg6wT67pTNF8y2 je8dpJnarQNpWxW+bsFlpGnhnZ4Go5j2oijkmUFvovgGrx1jmwPHwSalR4FIyeat v5KcGayTHXRraxXqPseXA99/7ac8FFRUKtdIWOHXQ7m2QvTNhcyFObYHGarr3FMW gVXW12eqgVoHWRst/V4fughp3Ch2XaNhjnoMA9pUwivwFQskSTvrlOJ9fD0lHzbV 1HEnc4XJyDr+yt3oxzgrSKum6TS8vKAXkOISx+csOf1P/NNmb0MYlp/3OUYWDy6D rYu3Bw90brzNpsZbJo/h+kt8WJMXW15yz5jmVPdA8tQLIHP1uoKqnjgUpTdL/2Y= =Dsf+ -----END PGP SIGNATURE----- --XsQoSWH+UP9D9v3l--