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 4E31B957 for ; Thu, 23 Feb 2017 07:41:44 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from outmail149084.authsmtp.net (outmail149084.authsmtp.net [62.13.149.84]) by smtp1.linuxfoundation.org (Postfix) with ESMTP id E7194F4 for ; Thu, 23 Feb 2017 07:41:42 +0000 (UTC) Received: from mail-c247.authsmtp.com (mail-c247.authsmtp.com [62.13.128.247]) by punt22.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v1N7feoZ000873; Thu, 23 Feb 2017 07:41:40 GMT 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 v1N7fcPZ054166 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Thu, 23 Feb 2017 07:41:39 GMT Received: from [127.0.0.1] (localhost [127.0.0.1]) by petertodd.org (Postfix) with ESMTPSA id 6F0C240576; Thu, 23 Feb 2017 07:41:38 +0000 (UTC) Received: by localhost (Postfix, from userid 1000) id B298D20245; Thu, 23 Feb 2017 02:41:37 -0500 (EST) Date: Thu, 23 Feb 2017 02:41:37 -0500 From: Peter Todd To: Bram Cohen Message-ID: <20170223074137.GA3395@savin.petertodd.org> References: <20170223011506.GC905@savin.petertodd.org> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="4Ckj6UjgE2iN1+kY" Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.23 (2014-03-12) X-Server-Quench: 836c82fa-f99b-11e6-bcdf-0015176ca198 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR aAdMdAEUHlAWAgsB AmEbW1NeVFx7XWM7 bghPaBtcak9QXgdq T0pMXVMcUgQWBkpS ZnQeVx1zcQMIeX5z bEAsVnNdD0x4Ixdg FEddR3AHZDJmdTJM BBZFdwNVdQJNeEwU a1l3GhFYa3VsNCMk FAgyOXU9MCtqYA0d aAwRMV8ICWMuJHYQ Sh4DGzQzHEoDLwAA 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 Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] A Better MMR Definition 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: Thu, 23 Feb 2017 07:41:44 -0000 --4Ckj6UjgE2iN1+kY Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Wed, Feb 22, 2017 at 07:07:08PM -0800, Bram Cohen wrote: > On Wed, Feb 22, 2017 at 5:15 PM, Peter Todd via bitcoin-dev < > bitcoin-dev@lists.linuxfoundation.org> wrote: >=20 > > > > With that, notice how proving the soundness of the proofs becomes trivi= al: > > if > > validation is deterministic, it is obviously impossible to construct two > > different proofs that prove contradictory statements, because a proof is > > simply > > part of the data structure itself. Contradiction would imply that the t= wo > > proofs are different, but that's easily rejected by simply checking the > > hash of > > the data. > > >=20 > My code works this way. Proofs are serialization of a subset of the tree, > and to validate a proof you ask a single function whether a particular > value is included in that tree subset, and it answers yes or no, so > obviously it's impossible for a single value to both validate and not > validate. The proof code was quite terrifying before I made this change > (which I did on your suggestion), and it's much cleaner and simpler now. = It > also in principle supports compact proofs of multiple inclusions and > exclusions in the same serialization of a subset of the tree because the > upper branches won't have to be repeated. I haven't written code for > generating those, but the validation code will happily accept them. That's an improvement, but I think we can do even better if we think of mis= sing pruned data as analogous to virtual memory: pruned data is the same as a pa= ge that has been swapped to disk, with the magical property that hashing allow= s us to swap it back in from an untrusted source. Thus a proof should actually be whatever data we expect our counterparty to have flushed, ranging from none at all, to 100% (modulo a root hash). An implementation should then do operations as normal, using parts of the proo= f on an as-needed basis where pruned data is encountered. Thus if you have a key-value map and do a get() operation, you'd expect the proof to *not* be what the get operates on, but rather be a *context* argum= ent to the get() operation. The other way around is actually an example of doing computations on untrusted data, and bad API design! > I'm not sure what you mean by MMRs though. Are you talking about MMRs whe= re > each mountain is a set of diffs to the old things and are periodically > consolidated? Or do later mountains refer to internals of earlier ones? Or > do they have 'maybe' values which mean that the earlier mountain should be > referred to? Are these patricia tries or something flatter and more fixed > depth? I'm talking about these MMR's: https://github.com/proofchains/python-proofm= arshal/blob/master/proofmarshal/mmr.py Notably I'm talking about an insertion ordered list, indexed by position, t= hat supports append and update operations, but *not* insertions; this is differ= ent than what you've recently published re: UTXO commitments. That's a full key-value map, something MMR's are delibrately are not doing. Draw out a MMR based on the formal definition you're replying too and you'll see the new structure. > My code doesn't keep track of tree size, by the way. It would be trivial = to > add that functionality to the library, and including it in the hashing > creates complexity and doesn't seem to have any benefit over sending that > data in a side channel. Like I say above, you're solving a different problem than MMR's solve. --=20 https://petertodd.org 'peter'[:-1]@petertodd.org --4Ckj6UjgE2iN1+kY Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- iQEcBAEBCAAGBQJYrpIsAAoJECSBQD2l8JH7rQ8IAIJmliLfyft94QZH4qr04L3i IGQZAlJ545ZXXIaojIpPqUxEDA3+BzYcbtM83ToEdlAeBi1fy4X+mERzDkTV7sXm 741iX2g0a/IDxADYCxhubUAeHqmxrJuxZ3JbvoNruAOeCGhIpWXI4OwLbJCa03Kg zaOEdIZzIkoq5tY1agyd5Fp+CbmrYOC2DUaDL0Y1HukxhmyiVztL663tSGyVVb8W S2XjO8hDJPdo0VEZNPVJYpYVfhKsg2TAoo9UNm0b+OObQsEd9gwMslfxxa/ZkByi 2PYIrADOu0pJtO0q4N3stt+4qZeOFwS7a3Z3cp9NO4oiggrOUev8XRjmP7w727A= =fW3l -----END PGP SIGNATURE----- --4Ckj6UjgE2iN1+kY--