diff options
| author | Peter Todd <pete@petertodd.org> | 2017-12-05 05:15:51 -0500 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2017-12-05 10:16:02 +0000 |
| commit | e05a44306807461b45d8018efc074da82ed0bcf3 (patch) | |
| tree | 09c9c249abf0a1b681906a0940f9ac9e7e8267b8 | |
| parent | 2e8f4b513a9cd344332b01f75fc1a968322ad5f2 (diff) | |
| download | pi-bitcoindev-e05a44306807461b45d8018efc074da82ed0bcf3.tar.gz pi-bitcoindev-e05a44306807461b45d8018efc074da82ed0bcf3.zip | |
[bitcoin-dev] Scalable Semi-Trustless Asset Transfer via Single-Use-Seals and Proof-of-Publication
| -rw-r--r-- | e4/e237c8d3db045f087635f0417265bdbf8b1dd7 | 373 |
1 files changed, 373 insertions, 0 deletions
diff --git a/e4/e237c8d3db045f087635f0417265bdbf8b1dd7 b/e4/e237c8d3db045f087635f0417265bdbf8b1dd7 new file mode 100644 index 000000000..5277027bc --- /dev/null +++ b/e4/e237c8d3db045f087635f0417265bdbf8b1dd7 @@ -0,0 +1,373 @@ +Return-Path: <pete@petertodd.org> +Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org + [172.17.192.35]) + by mail.linuxfoundation.org (Postfix) with ESMTPS id 74375138D + for <bitcoin-dev@lists.linuxfoundation.org>; + 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 <bitcoin-dev@lists.linuxfoundation.org>; + 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 <bitcoin-dev@lists.linuxfoundation.org>; + 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 <bitcoin-dev@lists.linuxfoundation.org>; + 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 <bitcoin-dev@lists.linuxfoundation.org>; + 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 <pete@petertodd.org> +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 <bitcoin-dev.lists.linuxfoundation.org> +List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> +List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> +List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> +List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> +List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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-- + |