1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
Return-Path: <g.andrew.stone@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 6B58E415
for <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 18:28:21 +0000 (UTC)
Received: by mail-wm0-f52.google.com with SMTP id v77so37472119wmv.1
for <bitcoin-dev@lists.linuxfoundation.org>;
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>
<CAAcC9ys5sUxVfOjogFiF3gzk51D_L=QQkOYevTH=qbh_RkA3Hw@mail.gmail.com>
<20170223181929.GA6268@savin.petertodd.org>
From: "G. Andrew Stone" <g.andrew.stone@gmail.com>
Date: Thu, 23 Feb 2017 13:28:18 -0500
Message-ID: <CAHUwRvs=f4=4cQPQoNa2ESJAydztZ3VRQg+SOY66UgDDB5i03w@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
Peter Todd <pete@petertodd.org>
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 <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: 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
> > <bitcoin-dev@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 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
<p dir=3D"ltr">Can an insertion ordered MMR allow an efficient nonexistence=
proof?</p>
<div class=3D"gmail_quote">On Feb 23, 2017 1:20 PM, "Peter Todd via bi=
tcoin-dev" <<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org=
">bitcoin-dev@lists.linuxfoundation.org</a>> wrote:<br type=3D"attributi=
on"><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-lef=
t:1px #ccc solid;padding-left:1ex">On Thu, Feb 23, 2017 at 09:53:58AM -0800=
, Chris Priest wrote:<br>
> On 2/22/17, Peter Todd via bitcoin-dev<br>
> <<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-d=
ev@lists.<wbr>linuxfoundation.org</a>> wrote:<br>
> > Reposting something that came up recently in a private discussion=
with some<br>
> > academics:<br>
> ><br>
> > Concretely, let's define a prunable MMR with the following gr=
ammar. This<br>
> > definition is an improvement on whats in the python-proofmarshal =
by<br>
> > committing<br>
> > to the number of items in the tree implicitly; an obvious max-log=
2(n)-sized<br>
> > proof-of-tree-size can be obtained by following the right-most no=
des:<br>
><br>
> What problem does this try to solve, and what does it have to do with =
bitcoin?<br>
<br>
See the discussion on TXO commitments for how MMR's could be used; a be=
tter MMR<br>
makes for a better TXO commitment.<br>
<br>
--<br>
<a href=3D"https://petertodd.org" rel=3D"noreferrer" target=3D"_blank">http=
s://petertodd.org</a> 'peter'[:-1]@<a href=3D"http://petertodd.org"=
rel=3D"noreferrer" target=3D"_blank">petertodd.org</a><br>
<br>______________________________<wbr>_________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
<wbr>linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wbr>org=
/mailman/listinfo/bitcoin-<wbr>dev</a><br>
<br></blockquote></div>
--001a113c895c040798054936c797--
|
