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 32C0788A for ; Wed, 22 Jun 2016 11:10:18 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from outmail149081.authsmtp.net (outmail149081.authsmtp.net [62.13.149.81]) by smtp1.linuxfoundation.org (Postfix) with ESMTP id CF370123 for ; Wed, 22 Jun 2016 11:10:14 +0000 (UTC) Received: from mail-c232.authsmtp.com (mail-c232.authsmtp.com [62.13.128.232]) by punt22.authsmtp.com (8.14.2/8.14.2/) with ESMTP id u5MBADdY011279 for ; Wed, 22 Jun 2016 12:10:13 +0100 (BST) 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.14.2/8.14.2/) with ESMTP id u5MBABlw081146 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Wed, 22 Jun 2016 12:10:12 +0100 (BST) Received: from [127.0.0.1] (localhost [127.0.0.1]) by petertodd.org (Postfix) with ESMTPSA id 1F3044012C for ; Wed, 22 Jun 2016 11:08:08 +0000 (UTC) Received: by localhost (Postfix, from userid 1000) id CF68420217; Wed, 22 Jun 2016 07:10:09 -0400 (EDT) Date: Wed, 22 Jun 2016 07:10:09 -0400 From: Peter Todd To: bitcoin-dev@lists.linuxfoundation.org Message-ID: <20160622111009.GA10956@fedora-21-dvm> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="J2SCkAp4GZ/dPZZf" Content-Disposition: inline User-Agent: Mutt/1.5.23 (2014-03-12) X-Server-Quench: e3de001d-3869-11e6-829e-00151795d556 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVJwpGK10IU0Fd P1hyKltILEZaQVBf Ri5dBBEKBAw1ADwr dVUTOktfYFU0Glt1 UkhIREJTFg9pARYA BFAbUAd3aQROfWBx Z0Z9XHVEXQo/cDsP MzwIUm0OZGZkbi4e VkdYfk0Bc1cffh9E Pk18XHUEfGQGM3x9 T1ViMnVpZWwCcXsE Hw1QcAwEakIMBTMw DysPFDFnJkAZXG06 KRBuFkQBAEZZFkQp LUBpV1UCezUfFhFT BQl1Gi5HLlIQDyMt AUtxUEgFFydGQSZE YFUSLwRJGSBbXCFV bAAA X-Authentic-SMTP: 61633532353630.1037: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] Closed Seal Sets and Truth Lists for Better Privacy and Censorship Resistance 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: Wed, 22 Jun 2016 11:10:18 -0000 --J2SCkAp4GZ/dPZZf Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable At the recent coredev.tech meetup in Zurich I spent much of my time discuss= ing anti-censorship improvements with Adam Back, building on his idea of blind symmetric commitments[^bsc], and my own ideas of client-side verification. = Our goal here is to combat censorship by ensuring that miners do not have the information needed to selectively censor (blacklist) transactions, forcing = them to adopt a whitelist approach of allowed transactions if they choose to cen= sor. Back's work achieves that by changing the protocol such that users commit to their transaction in advance, in such a way that the commitment doesn't con= tain the information necessary to censor the transaction, although after commitm= ent all transactional information becomes available. Here we propose a similar scheme with using "smart contract" state machine tooling, with the potential for an even better Zerocash-like guarantee that only a subset of data ever becomes public, without requiring "moon math" of uncertain security. # The Closed Seal Maps To implement Single-Use Seals we propose that miners attest to the contents= of a series of key:value maps of true expressions, with the keys being the expressions, and the values being commitments, which along with (discardabl= e) witnesses make up the argument to the expression. Once an expression is add= ed to the closed seal map, the value associated with it can't be changed. Periodically - perhaps once a year - the most recent map is archived, and t= he map is started fresh again. Once archived a closed seal map is never change= d. Miners are expected to keep the contents of the current map, as well as the most recent closed seal map - the contents of older maps are proven on dema= nd using techniques similar to TXO commitments. A single-use seal[^sma] implemented with the closed seal maps is then identified by the expression and a block height. The seal is open if the expression does not exist in any closed seal maps between the creation block height and the most recent block height. A witness to the fact that the seal has been closed is then a proof that the seal was recorded as closed in one= of the closed seal maps, and (if needed) proof that the seal was still open in= any prior maps between its creation and closing. Similar to the logic in Bitcoin's segregated witnesses proposal, separating= the commitment and witness arguments to the seal expression ensures that the witness attesting to the fact that a given seal was closed does not depend = on the exact signature used to actually close it. Here's a very simple example of such a seal expression, in the author's Dex[^dex] expression language, for an application that can avoid reusing pubkeys: (checksig (hash )) This desugars to the following after all named arguments were replaced by explicit destructuring of the expression argument, denoted by the arg symbo= l: (and (checksig (cdr arg) (digest (car arg)))) The arguments to the expression are the closed seal map's commitment and witness, which are our committed value and signature respectively: ( . ) ## The Truth List We implement an expression validity oracle by having miners attest to the validity of a perpetually growing list of true predicate expressions, whose evaluation can in turn depend on depend on previously attested expressions = in the truth list. SPV clients who trust miners can use the truth list to skip validation of old history. Similar to TXO commitments, we expect miners to have a copy of recent entri= es in the truth list, perhaps the previous year. Older history can be proven o= n an as-needed basis. Unlike TXO commitments, since this is a pure list of valid expressions, once an item is added to the list it is never modified. As the truth list can include expressions that reference previously evaluated expressions, expressions of arbitrary depth can be evaluated. For example, suppose we have an extremely long linked list of numbers, represen= ted as the following sexpr: (i_n i_n-1 i_n-2 ... i_1 i_0) We want to check that every number in the list is even: (defun all-even? (l) (match l (nil true) ((n . rest) (if (mod n 2) false (all-even? rest))))) In any real system this will fail for a sufficiently long list, either due = to stack overflow, or (if tail recursion is supported) due to exceeding the anti-DoS limits on cycles executed in one expression; expressing the above = may even be impossible in expression systems that don't allow unbounded recursi= on. A more subtle issue is that in a merkelized expression language, an express= ion that calls itself is impossible to directly represent: doing so creates a c= ycle in the call graph, which isn't possible without breaking the hash function.= So instead we'll define the special symbol self, which triggers a lookup in the truth map instead of actually evaluating directly. Now our expression is: (defun all-even? (l) (match l (nil true) ((n . rest) (if (mod n 2) false (self rest))))) We evaluate it in parts, starting with the end of the list. The truth list = only attests to valid expressions - not arguments - so we curry the argument to = form the following expression: (all-even? nil) The second thing that is appended to the truth list is: (all-even? (0 . #)) Note how we haven't actually provided the cdr of the cons cell - it's been pruned and replaced by the digest of nil. With an additional bit of metadat= a - the index of that expression within the trust list, and possibly a merkle p= ath to the tip if the expression has been archived - we can show that the expression has been previously evaluated and is true. Subsequent expressions follow the same pattern: (all-even? (1 . #)) Until finally we reach the last item: (all-even? (n_i . #)) Now we can show anyone who trusts that the truth list is valid - like a SPV client - that evaluating all-even? on that list returns true by extracting a merkle path from that item to the tip of the list's MMR commitment. # Transactions When we spend an output our goal is to direct the funds spent to a set of outputs by irrovocably committing single-use seals to that distribution of outputs. Equally, to validate an output we must show that sufficient funds = have been directed assigned to it. However, our anti-censorship goals make this difficult, as we'll often want to reveal some information about where funds being spend are going immediately - say to pay fees - while delaying when o= ther information is revealed as long as possible. To achieve this we generalize the idea of a transaction slightly. Rather th= an simply having a set of inputs spent and outputs created, we have a set of _input splits_ spent, and outputs created. An input split is then a merkle-= sum map of nonces:values that the particular input has been split into; the transaction commits to a specific nonce within that split, and is only vali= d if the seal for that input is closed over a split actually committing to the transaction. Secondly, in a transaction with multiple outputs, we don't want it to be immediately possible to link outputs together as seals associated with them= are closed, even if the transaction ID is known publicly. So we associate each output with a unique nonce. Thus we can uniquely identify a specific transaction output - an outpoint -= by the following data (remember that the tx would usually be pruned, leaving j= ust the digest): (struct outpoint (tx :transaction) (nonce :digest)) An transaction output is defined as: (struct txout (value :int) ; value of output (nonce :digest) (authexpr :func)) ; authorization expression An input: (struct txin (prevout :outpoint) ; authorization expression (split :digest) ; split nonce (value :int)) ; claimed value of output spent And a transaction: (struct transaction ; fixme: need to define functions to extract sums and keys (inputs :(merkle-sum-map (:digest :txin)) (outputs :(merkle-sum-map (:digest :txout)) ; and probably more metadata here) ## Spending Outputs Our single-use seal associated with a specific output is the expression: ( . arg) When the seal is closed it commits to the merkle-sum split map, which is indexed by split nonces, one per (tx, value) pair committed to. This means that in the general case of an spend authorization expression that just che= cks a signature, the actual outpoint can be pruned and what actually gets publi= shed in the closed seal set is just: ( #> . arg) Along with the commitment: # With the relevant data hidden behind opaque digests, protected from brute-forcing by nonces, external observers have no information about what transaction output was spent, or anything about the transaction spending th= at output. The nonce in the seal commitment prevents that multiple spends for = the same transaction from being linked together. Yet at the same time, we're s= till able to write a special-purpose spend auth expressions that do inspect the contents of the transaction if needed. ## Validating Transactions When validating a transaction, we want to validate the least amount of data possible, allowing the maximum amount of data to be omitted for a given recipient. Thus when we validate a transaction we _don't_ validate the outp= uts; we only validate that the inputs spent by the transaction are valid, and the sum of (split) inputs spent is correct. We only need to validate outputs wh= en they're spent - until then an invalid output is of no relevance. We also do= n't need to validate any outputs other than the ones we're trying to spend - the merkle sum tree guarantees that regardless of what's going on with other outputs, the funds we're spending are uniquely allocated to us. This means our function to check that a transaction is valid won't check the outputs of the transaction itself, but will check outputs of previous transactions: (defun valid-tx? (tx) (map-reduce tx.inputs (lambda (txin) (and (valid-output? txin.prevout))))) # Censorship Resistant Usage To make use of the separation between seal closure and validation we need to pass transaction information from peer to peer. Let's look at what happens = when Alice pays Bob: 1. Alice picks one or more inputs to spend. 2. For each input she constructs a split, paying part of the funds to a per-input fee transaction with no outputs, and committing part of the funds= to the transaction paying Bob. If she has change left over she'll construct a third transaction with just that change as an input. 3. She signs each input, creating valid signatures for the corresponding output's seal's authorization expression. 4. She broadcasts the subset of data corresponding to just the fee paying transactions and related signatures individually, with a time delay between each one. All other data is pruned, leaving just opaque digests. 5. Once all inputs are confirmed, she gives Bob the data corresponding to h= is transaction, including the relevant parts of the merkle trees, and relevant closed seal witnesses. At this point, a whole bunch of seals have been closed, but there's absolut= ely nothing on chain that links them together. Now let's suppose Bob pays Charl= ie, using the funds Alice gave him, and a different input to pay mining fees: 1. Bob constructs a fee paying transaction, splitting some funds from a previously revealed output, and depending on the seal for the output Alice = gave him, but without spending any of that output's funds. 2. Bob broadcasts the above publicly. Miners have to add both seals to the closed seal set to collect the fees. 3. Once confirmed, Bob gives Charlie the corresponding transaction informat= ion for his output, as well as the still-private information it depends on to p= rove that the output Alice created for Bob is itself valid. Again, nearly none of the information related to the transaction is public,= yet the funds have moved twice. ## Pruning Old History Over time the proofs that a coin is valid will grow as each additional transaction adds more data. We shorten these proofs by publishing some of t= he data in the form of additions to the truth list of valid expressions, specifically the is-valid-tx? expressions that determine whether or not a transaction (and prior transactions) are valid. This allows SPV clients who trust miners to stop validating once they reach that old history. Secondly, with transaction history linearization[^sma] we can avoid ever revealing most of the transaction data, greatly improving privacy. Only one input per transaction needs to be proven, so all data related to other inpu= ts can be discarded permanently; in practice this will lead to either one or t= wo public inputs, including the input made public to pay mining fees. # "Smart Contracts" Privacy aside, the combination of single-use seal and true expressions list enables all known "smart contract" applications, such as the ones Ethereum currently targets. After all, the accounts-based Ethereum architecture can always be simulated with a series of single-use seal's that explicitly keeps track of of an account balance based on actions taken. # Open Questions 1. How does the above architecture interact with scaling proposals, like sharding? Fraud proofs? 2. How does the statistical inflation protection of transaction history linearization work in a real economy, e.g. if people use it gamble with the= ir funds? 3. PoW isn't a perfect random beacon; how do we take that into account when designing linearization? 4. How do wallets pass proof data between each other, e.g. offline? 5. How do wallets backup proof data? (similar problem that Lightning has) # References [^bsc]: "blind symmetric commitment for stronger byzantine voting resilienc= e", Adam Back, May 15th 2013, bitcoin-dev mailing list, https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-May/00= 2600.html [^sma]: "Building Blocks of the State Machine Approach to Consensus", Peter Todd, Jun 20th 2016, https://petertodd.org/2016/state-machine-consensus-building-blocks https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-June/0= 12773.html [^dex]: "Dex: Deterministic Predicate Expressions for Smarter Signatures", Peter Todd, May 25th 2016, https://github.com/WebOfTrustInfo/ID2020DesignWorkshop/blob/master/= topics-and-advance-readings/DexPredicatesForSmarterSigs.md --=20 https://petertodd.org 'peter'[:-1]@petertodd.org --J2SCkAp4GZ/dPZZf Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- iQEcBAEBCAAGBQJXanIOAAoJEGOZARBE6K+ytWkH/1yGxUt2RdAULF4PyFAe/Scf 5dmM+CGWz7kQQCihdfZ5lChYdJXXu49Q6yVBSc31UvmNG98Q1bO5bH0y589Emvyc Cn40XKLKENRTikNL21wnldPfZTj2Cpio0A+JeN7uV0ziCJutpvzW6zrTopyxwoHa fMy9f9D/n9hZe8fz8EIxq9WLziFA5PHkjh2kM/iyj+kROaZrcwcPkHuerAOjivnI V8jQFhEk+9R3zHajg9RZ07vUAtqusPljRYa5DBy6oAI7h0UrCkHsulAh/cIUiQ3Y K32ia1a/PpJNBaugbwVTlzYQmamwOzesFw2WVQxWY+rrpb2l9txrFl3xkiEDVsU= =CnTr -----END PGP SIGNATURE----- --J2SCkAp4GZ/dPZZf--