Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 6B58E415 for ; Thu, 23 Feb 2017 18:28:22 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wm0-f52.google.com (mail-wm0-f52.google.com [74.125.82.52]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 4421716E for ; Thu, 23 Feb 2017 18:28:21 +0000 (UTC) Received: by mail-wm0-f52.google.com with SMTP id v77so37472119wmv.1 for ; Thu, 23 Feb 2017 10:28:21 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=XvOS9i1Zj4i0+t4Lk5sOxjiJp3EAKiGqlK2VB0xJ9oE=; b=Cx9LtkBJh0uq+e191QFRgTohCpuw9UAEKYScMWqaS4BpsjU6X0vKdeiHResVuE0JOB uuEUcKmwvdxcY8ySuUV0kngvVChd0woQ286W5SWB6nypUMFEnzAGv5BFllRv0Y8ut0aX o3bCQlfGJsmYoBZQxcmkSSpJ6AcxML1jxoTStYz7r5j7cTMLCRg4OIjLtm42HWm2drUF 4eO9bPvccZj3G4xtL14yOi94cCoC4qs8G1N2mGalIfOw0r/ZRWG+QKebiuRCfJfVVyqU JAbF5yAws5N0nLAtkO2+hc2Cj8wVB59Ra1I3f8lvNNr3rVmlHsUvjD7V1TLX33JM7qqW EbWw== 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=XvOS9i1Zj4i0+t4Lk5sOxjiJp3EAKiGqlK2VB0xJ9oE=; b=qq27Eu4cx203MViqGau6LkQKIl1XN1k6d6kekD5sCBE3TBjPxxwFmrkpdMSAX69wXD r6hE9b9N8fxgDQVy+KFLyBdxzcNQL5cFGlPwbsttkCJ1/sSr1LJQF4PE3ukXYYJGZhA2 pOix7c4Etg8d7GhRmvNgBpyi3U+HZMtDUl3mH/04iUMts9EwfHLS7cimqhknX/q7eRF0 IaBqIUCwFPQ38ebI3UiH0eGFJPA514r6ZwrJ6GX3QkElclKuU6HWzWzBAGWozUOpJSoW sX2SUH/7uta1jpBOMAAi6OVw2+781z64ELqbeI/oya0KMx9mHmz7U+N06xq/lnyDt2ln rVdQ== X-Gm-Message-State: AMke39mutQcCIEFptreQ+Ygjii2tkCAI2aqgIZJVpFCSYPbHWZF3V4ulVBuQDk6zZuS2jqetadFbv0JuIEzkvg== X-Received: by 10.28.1.213 with SMTP id 204mr5831669wmb.70.1487874499536; Thu, 23 Feb 2017 10:28:19 -0800 (PST) MIME-Version: 1.0 Received: by 10.80.169.40 with HTTP; Thu, 23 Feb 2017 10:28:18 -0800 (PST) Received: by 10.80.169.40 with HTTP; Thu, 23 Feb 2017 10:28:18 -0800 (PST) In-Reply-To: <20170223181929.GA6268@savin.petertodd.org> References: <20170223011506.GC905@savin.petertodd.org> <20170223181929.GA6268@savin.petertodd.org> From: "G. Andrew Stone" Date: Thu, 23 Feb 2017 13:28:18 -0500 Message-ID: To: Bitcoin Protocol Discussion , Peter Todd Content-Type: multipart/alternative; boundary=001a113c895c040798054936c797 X-Spam-Status: No, score=-1.5 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE, RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM autolearn=no 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 18:28:22 -0000 --001a113c895c040798054936c797 Content-Type: text/plain; charset=UTF-8 Can an insertion ordered MMR allow an efficient nonexistence proof? On Feb 23, 2017 1:20 PM, "Peter Todd via bitcoin-dev" < bitcoin-dev@lists.linuxfoundation.org> wrote: > On Thu, Feb 23, 2017 at 09:53:58AM -0800, Chris Priest wrote: > > On 2/22/17, Peter Todd via bitcoin-dev > > wrote: > > > Reposting something that came up recently in a private discussion with > some > > > academics: > > > > > > Concretely, let's define a prunable MMR with the following grammar. > This > > > definition is an improvement on whats in the python-proofmarshal by > > > committing > > > to the number of items in the tree implicitly; an obvious > max-log2(n)-sized > > > proof-of-tree-size can be obtained by following the right-most nodes: > > > > What problem does this try to solve, and what does it have to do with > bitcoin? > > See the discussion on TXO commitments for how MMR's could be used; a > better MMR > makes for a better TXO commitment. > > -- > https://petertodd.org 'peter'[:-1]@petertodd.org > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > --001a113c895c040798054936c797 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

Can an insertion ordered MMR allow an efficient nonexistence= proof?

On Feb 23, 2017 1:20 PM, "Peter Todd via bi= tcoin-dev" <bitcoin-dev@lists.linuxfoundation.org> wrote:
On Thu, Feb 23, 2017 at 09:53:58AM -0800= , Chris Priest wrote:
> On 2/22/17, Peter Todd via bitcoin-dev
> <bitcoin-d= ev@lists.linuxfoundation.org> wrote:
> > Reposting something that came up recently in a private discussion= with some
> > academics:
> >
> > Concretely, let's define a prunable MMR with the following gr= ammar. This
> > definition is an improvement on whats in the python-proofmarshal = by
> > committing
> > to the number of items in the tree implicitly; an obvious max-log= 2(n)-sized
> > proof-of-tree-size can be obtained by following the right-most no= des:
>
> What problem does this try to solve, and what does it have to do with = bitcoin?

See the discussion on TXO commitments for how MMR's could be used; a be= tter MMR
makes for a better TXO commitment.

--
http= s://petertodd.org 'peter'[:-1]@petertodd.org

_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.= linuxfoundation.org
https://lists.linuxfoundation.org= /mailman/listinfo/bitcoin-dev

--001a113c895c040798054936c797--