From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 74375138D for ; Tue, 5 Dec 2017 10:16:02 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from outmail148098.authsmtp.com (outmail148098.authsmtp.com [62.13.148.98]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 2B66FF4 for ; Tue, 5 Dec 2017 10:16:00 +0000 (UTC) Received: from mail-c247.authsmtp.com (mail-c247.authsmtp.com [62.13.128.247]) by punt24.authsmtp.com. (8.15.2/8.15.2) with ESMTP id vB5AFxKc042579 for ; Tue, 5 Dec 2017 10:15:59 GMT (envelope-from pete@petertodd.org) Received: from petertodd.org (ec2-52-5-185-120.compute-1.amazonaws.com [52.5.185.120]) (authenticated bits=0) by mail.authsmtp.com (8.15.2/8.15.2) with ESMTPSA id vB5AFvAQ031050 (version=TLSv1.2 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO) for ; Tue, 5 Dec 2017 10:15:58 GMT (envelope-from pete@petertodd.org) Received: from [127.0.0.1] (localhost [127.0.0.1]) by petertodd.org (Postfix) with ESMTPSA id B197040147 for ; Tue, 5 Dec 2017 10:15:56 +0000 (UTC) Received: by localhost (Postfix, from userid 1000) id BF17C20355; Tue, 5 Dec 2017 05:15:51 -0500 (EST) Date: Tue, 5 Dec 2017 05:15:51 -0500 From: Peter Todd To: bitcoin-dev@lists.linuxfoundation.org Message-ID: <20171205101551.GA10265@fedora-23-dvm> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="GvXjxJ+pjyke8COw" Content-Disposition: inline User-Agent: Mutt/1.5.23 (2014-03-12) X-Server-Quench: 499b9866-d9a5-11e7-8106-0015176ca198 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVJwpGK10IU0Fd P1hyKltILEZaQVBf Ri5dBBEKBAw1ADwr dVUTOktdZ1U6ClZ1 UkhIRUJTFA9pBBYE DlAbUAd3aQROfWBx Z0Z9XHVEXQo8B0MM NAgldG0FZGdlaC4e UkRRcU1QeQoYdxdD bE0rXSIIfGQGM319 T1ZrYXVpZWwCcXsL SQhUfAIEek0CGjc2 Qx1KJjgqHAg5XTgo MxgrMUVUNV0KP1l6 DUEoX0kWPgVaFAxX V3pMBiBdKhw8XCdu Ng5TWVVWGTtRI29k GBovLFpPDHlqRyBc BUBMVxAIDUug X-Authentic-SMTP: 61633532353630.1038:706 X-AuthFastPath: 0 (Was 255) X-AuthSMTP-Origin: 52.5.185.120/25 X-AuthVirus-Status: No virus detected - but ensure you scan with your own anti-virus system. X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: [bitcoin-dev] Scalable Semi-Trustless Asset Transfer via Single-Use-Seals and Proof-of-Publication X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 05 Dec 2017 10:16:02 -0000 --GvXjxJ+pjyke8COw Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable I recently wrote this up for a client, and although the material has been covered elsewhere, I thought being a worked example it might be of interest, particularly while sidechains are being discussed again. As per (1) I've perhaps foolishly committed to making an even more fleshed = out example, so peer review here before it gets to an even wider audience would= be appreciated. :) 1) https://twitter.com/petertoddbtc/status/937401676042039296 tl;dr: We can do trustless with respect to validity, trusted with respect to censorship resistance, indivisible asset transfer with less than 5MB/year/t= oken of proof data, assuming token ownership is updated every two hours, at a ra= te of ~500,000 transfers per second. The scalability of this scheme is linear = with respect to update interval, and logarithmic with respect to overall transfer rate. ## Single-Use-Seal Definition Analogous to the real-world, physical, single-use-seals used to secure ship= ping containers, a single-use-seal primitive is a unique object that can be clos= ed over a message exactly once. In short, a single-use-seal is an abstract mechanism to prevent double-spends. A single-use-seal implementation supports two fundamental operations: Close(l,m) -> w_l Close seal l over message m, producing a witness w_l Verify(l,w_l,m) -> bool Verify that the seal l was closed over message m A single-use-seal implementation is secure if it is impossible for an attac= ker to cause the Verify function to return true for two distinct messages m_1, = m_2, when applied to the same seal (it _is_ acceptable, although non-ideal, for there to exist multiple witnesses for the same seal/message pair). Practical single-use-seal implementations will also obviously require some = way of generating new single-use-seals. Secondly, authentication is generally useful. Thus we have: Gen(p) -> l Generate a new seal bound to pubkey p Close(l,m,s) -> w_l Close seal l over message m, authenticated by signature s valid for= pubkey p Obviously, in the above, pubkey can be replaced by any cryptographic identi= ty scheme, such as a Bitcoin-style predicate script, zero-knowledge proof, etc. Finally, _some_ single-use-seal implementations may support the ability to prove that a seal is _open_, e.g. as of a given block height or point in ti= me. This however is optional, and as it can be difficult to implement, it is suggested that seal-using protocols avoid depending on this functionality existing. ## Indivisible Token Transfer With a secure single-use-seal primitive we can build a indivisible token transfer system, allowing the secure transfer of a token from one party to another, with the seals preventing double-spends of that indivisible token. Each token is identified by its genesis seal l_0. To transfer a token, the = most recent seal l_n is closed over a message committing to a new seal, l_{n+1}, producing a witness w_{l_n} attesting to that transfer. This allows a recip= ient to securely verify that they have received the desired token as follows: 1. Generate a fresh, open, seal l_{n+1} that only they can close. 2. Ask the sender to close their seal, l_n, over the seal l_{n+1} 3. Verify that there exist a set of valid witnesses w_0 .. w_n, and seals l_0 .. l_n, such that for each seal l_i in i =3D 0 .. n, Verify(l_i, w_i= , l_{i+1}) returns true. Since a secure single-use-seal protocol prohibits the closure of a single s= eal over multiple messages, the above protocol ensures that the token can not be double-spent. Secondly, by ensuring that seal l_{n+1} can be closed by the recipient and only the recipient, the receipient of the token knows that th= ey and they alone have the ability to send that token to the next owner. ## Divisible Asset Transfer In the case of a divisible asset, rather than transferring a single, unique, token we want to transfer a _quantity_ of an asset. We can accomplish this = in a manner similar how Bitcoin's UTXO-based transactions, in which one or more inputs are combined in a single transaction, then split amongst zero or more outputs. We define the concept of an _output_. Each output x is associated with a se= al l and value v. For each asset we define a set of _genesis outputs_, X_G, whose validity is assumed. To transfer divisible assets we further define the concepts of a _spend_ an= d a _split_. A spend, D, is a commitment to a set of outputs x_i .. x_j; the va= lue of a spend is simply the sum of the values of all outputs in the spend. A s= plit commitments to a set of zero or seal/value, (l_i,v_i), tuples, with the sum value of the split being the sum of a values in the split. Spends and splits are used to define a _split output_. While a genesis outp= ut is simply assumed valid, a split output x is then the tuple (D,V,i), commit= ting to a spend D, split V, and within that split, a particular output i. A split output is valid if: 1. Each output in the spend set D is a valid output. 2. The sum value of the spend set D is >=3D the sum value of the split V. 3. i corresponds to a valid output in the split. 4. There exists a set of witnesses w_i .. w_j, such that each seal in the s= pend set closed over the message (D,V) (the spend and split). As with the indivisible asset transfer, a recipient can verify that an asset has been securely transferred to them by generating a fresh seal, asking the sender to create a new split output for that seal and requested output amou= nt, and verifying that the newly created split output is in fact valid. As with Bitcoin transactions, in most transfers will also result in a change output. Note how an actual implementation can usefully use a merkle-sum-tree to com= mit to the split set, allowing outputs to be proven to the recipient by giving = only a single branch of the tree, with other outputs pruned. This can have both efficiency and privacy advantages. ## Single-Use-Seal Implementation An obvious single-use-seal implementation is to simply have a trusted notar= y, with each seal committing to that notary's identity, and witnesses being cryptographic signatures produced by that notary. A further obvious refinem= ent is to use disposable keys, with a unique private key being generated by the notary for each seal, and the private key being securely destroyed when the seal is closed. Secondly Bitcoin (or similar) transaction outputs can implement single-use-seals, with each seal being uniquely identified by outpoint (txid:n), and witnesses being transactions spending that outpoint in a specified way (e.g. the first output being an OP_RETURN committing to the message). ### Proof-of-Publication Ledger For a scalable, trust-minimized, single-use-seal implementation we can use a proof-of-publication ledger, where consensus over the state of the ledger is achieved with a second single-use-seal implementation (e.g. Bitcoin). Such a ledger is associated with a genesis seal, L_0, with each entry M_i in the ledger being committed by closing the most recent seal over that entry, producing W_i such that Verify(L_i, (L_{i+1}, M_i), W_i) returns true. Thus we achieve consensus over the state of the ledger as we can prove the contents of the ledger. Specifically, given starting point L_i we can prove that the subsequent led= ger entries M_i .. M_j are valid with witnesses W_i .. W_j and seals L_{i+1} ..= L_{j+1}. A proof-of-publication-based seal can then be constructed via the tuple (L_= i, p), where L_i is one of the ledger's seals, and p is a pubkey (or similar).= To close a proof-of-publication ledger seal a valid signature for that pubkey = and message m is published in the ledger in entry M_j. Thus the seal witness is proof that: 1. Entry M_j contained a valid signature by pubkey p, for message m. 2. All prior entries M_i .. M_{j-1} (possibly an empty set) did _not_ conta= in valid signatures. Finally, for the purpose of scalability, instead of each ledger entry M_i consisting of a unstructured message, we can instead commit to a merkelized key:value tree, with each key being a pubkey p, and each value being an alleged signature (possibly invalid). Now the non-publication condition is proven by showing that either: 1. Tree M_i does not contain key p. 2. Tree M_i does contain key p, but alleged signature s is invalid. The publication condition is proven by showing that tree M_j does contain k= ey p, and that key is associated with valid signature s. A merkelized key:value tree can prove both statements with a log2(n) sized proof, and thus we achieve log2(n) size scalability, with the constant fact= or growing by the age of the seals, the ledger update frequency, the rate at w= hich seals are closed, and the maximum size allowed for signatures. Note how a number of simple optimizations are possible, such as preventing = the creation of "spam" invalid signatures by blinding the actual pubkey with a nonce, ensuring only valid signatures are published, etc. Also note how it = is _not_ necessary to validate all entries in the ledger form a chain: the single-use-seals guarantees that a particular range of ledger entries will = be unique, regardless of whether all ledger history was unique. Proof-of-Publication ledgers are trustless with regard to false seal witnes= ses: the ledger maintainer(s) are unable to falsify a witness because they are unable to produce a valid signature. They are however trusted with regard to censorship: the ledger maintainer can prevent the publication of a signature and/or or withhold data necessary to prove the state of the seal. # Performance Figures Assume a indivisible token transfer via a PoP ledger using Bitcoin-based single-use-seals, with the ledger updated 12 times a day (every two hours). Assume each ledger update corresponds to 2^32, 4 billion, transfers. The data required to prove publication/non-publication for a given ledger update is less than: lite-client BTC tx proof: =3D ~1KB merkle path down k/v tree: 32 levels * 32bytes/level =3D 1KB key/value: 32 bytes predicate hash + 1KB script sig =3D ~1KB Total =3D ~3KB/ledger up= date * 356 days/year * 12 updates/day =3D 13MB/year Now, those are *absolute worst case* numbers, and there's a number of ways = that they can be substantially reduced such as only publishing valid signatures,= or just assuming you're not being attacked constantly... Also, note how for a client with multiple tokens, much of the data can be shared amongst each to= ken. But even then, being able to prove the ownership status of a token, in a trustless fashion, with just 13MB/year of data is an excellent result for m= any use-cases. With these optimizations, the marginal cost per token after the first one is just 1KB/ledger update, 4.4MB/year. --=20 https://petertodd.org 'peter'[:-1]@petertodd.org --GvXjxJ+pjyke8COw Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- iQEzBAEBCAAdFiEEFcyURjhyM68BBPYTJIFAPaXwkfsFAlomcdcACgkQJIFAPaXw kftSBwf+LzqUX145L2IFavZGUckFeYH5s1GdzsvSqzkVj+Mep0VzBs5NlbsZ5Qut UN9oOCPgUhUTF1VISPxLqJ6r3q6fGES98PIZ59PGYMioWTZzztrwXIxql4VLtl1k tzmgu/sQ6pCirgjHFZKgUMcfhUgGDr0ISeJUM2WQr6CX1xcvM45dwWW1T40WrziI Z9IJtU8h1TDVFpYEjNeUN+usnsh8AW9mU5om68ALDZBE7NDwqD/2rkRvPjOmpaEF cNJoV3m3UNmLagA0Dxku/iNcR0fL97QQvR4eQPZXe6PDRKGj/6CTNPC6N46vFxPW IZA9fdfHvGlq6mPD3HKcV23dyfKNog== =cVem -----END PGP SIGNATURE----- --GvXjxJ+pjyke8COw--