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 9B4E6B2F for ; Thu, 23 Feb 2017 03:07:09 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-it0-f51.google.com (mail-it0-f51.google.com [209.85.214.51]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 1D3C417F for ; Thu, 23 Feb 2017 03:07:09 +0000 (UTC) Received: by mail-it0-f51.google.com with SMTP id 203so160474796ith.0 for ; Wed, 22 Feb 2017 19:07:09 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bittorrent-com.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=qdzw2UxkP/Iy4plXD1GoQOPmt93YceuMd0RmPl01/yk=; b=MVCDNkeSx0NU7YZc3jpIknEse6gIqjHcsygN/Gr7pxkWrD6ocLvqee89RVkCW7CIub plcjiaR/brO957PUzw71sUaQ8MDDrdUZEy+bQbT3yLgCVeGhUIiV5Yx96Djxv4hDG+O3 qhAECCtv+SAQ3BfP2eABrHwIYGE4XWLhhvH+e2mShxOwfjDnsQbxuOe75DV4992drUK3 Vyuqew7jDiOkAWNMruN8YjKnq+GRfoqvY9MIP4WskT+BPwlDswxN9FyoOTZVO1T68P5o 2Y/aBGf1CWO6JCu/IuAZB3XrS68nKGaVuM57nQEfc+5K5JIwNYgE1GNOR12Zr0uzsDbL +YUg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=qdzw2UxkP/Iy4plXD1GoQOPmt93YceuMd0RmPl01/yk=; b=oCHEwoeqKCMyGZfELrpHcAKsu3vje2tXgYgAaFxPqFSdww4XLjqB5+JbBvWhxpAIwa E4xVqpUiwuY6u6Ht/Db5g8FVFiHyVfh8UiKZ6DeAwckRSAFrgQLap/pfgyuBlN/BOMfX 1At4tmyuaqrPHI3TTLaNQhx8VRVnQHwMM7iBXK+uPE5M/6UyQ+fuYJveIoAR0+uV/JU1 tnJtyt4mKLd+zYSq6MILavwU8VSavr+pDRn2gN1ZYvHDGT/jh+yZuqjiQPRXfgLdmIqa 56iuDD7MWDNikABSGIikdrw2etVclxQYHg6gKz908ClQh86DCbIAvIORqexKmCovu2Pp 6fgg== X-Gm-Message-State: AMke39lQerb4CpszENEjZIm7UMK+42menp/71RCFsR7gE/uFrjvVwBr1KzsP5/gDuiNaK6T7eUUCcLrFr/WZty6L X-Received: by 10.36.25.83 with SMTP id b80mr1271651itb.98.1487819228519; Wed, 22 Feb 2017 19:07:08 -0800 (PST) MIME-Version: 1.0 Received: by 10.36.73.150 with HTTP; Wed, 22 Feb 2017 19:07:08 -0800 (PST) In-Reply-To: <20170223011506.GC905@savin.petertodd.org> References: <20170223011506.GC905@savin.petertodd.org> From: Bram Cohen Date: Wed, 22 Feb 2017 19:07:08 -0800 Message-ID: To: Peter Todd , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary=001a114401829b44c9054929e8d0 X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, HTML_MESSAGE, RCVD_IN_DNSWL_LOW, RCVD_IN_SORBS_SPAM autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org 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 03:07:09 -0000 --001a114401829b44c9054929e8d0 Content-Type: text/plain; charset=UTF-8 On Wed, Feb 22, 2017 at 5:15 PM, Peter Todd via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > > With that, notice how proving the soundness of the proofs becomes trivial: > 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 two > proofs are different, but that's easily rejected by simply checking the > hash of > the data. > 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. I'm not sure what you mean by MMRs though. Are you talking about MMRs where 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? 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. --001a114401829b44c9054929e8d0 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
On W= ed, Feb 22, 2017 at 5:15 PM, Peter Todd via bitcoin-dev &= lt;bitcoin-dev@lists.linuxfoundation.org> wrote:

With that, notice how proving the soundness of the proofs becomes trivial: = if
validation is deterministic, it is obviously impossible to construct two different proofs that prove contradictory statements, because a proof is si= mply
part of the data structure itself. Contradiction would imply that the two proofs are different, but that's easily rejected by simply checking the= hash of
the data.

My code works this way. Proof= s are serialization of a subset of the tree, and to validate a proof you as= k a single function whether a particular value is included in that tree sub= set, and it answers yes or no, so obviously it's impossible for a singl= e value to both validate and not validate. The proof code was quite terrify= ing 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 proof= s of multiple inclusions and exclusions in the same serialization of a subs= et 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.

I'm not sure what you me= an by MMRs though. Are you talking about MMRs where each mountain is a set = of diffs to the old things and are periodically consolidated? Or do later m= ountains refer to internals of earlier ones? Or do they have 'maybe'= ; values which mean that the earlier mountain should be referred to? Are th= ese patricia tries or something flatter and more fixed depth?
My code doesn't keep track of tree size, by the way. It wou= ld 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 ov= er sending that data in a side channel.
--001a114401829b44c9054929e8d0--