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
|
Return-Path: <bram@bittorrent.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 9B4E6B2F
for <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 03:07:09 +0000 (UTC)
Received: by mail-it0-f51.google.com with SMTP id 203so160474796ith.0
for <bitcoin-dev@lists.linuxfoundation.org>;
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 <bram@bittorrent.com>
Date: Wed, 22 Feb 2017 19:07:08 -0800
Message-ID: <CA+KqGkqXmWgyU+4ZaR9w7e3xVBUyWwAixVAEzT9hT8V_1kwnuw@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
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 <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 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
<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On W=
ed, Feb 22, 2017 at 5:15 PM, Peter Todd via bitcoin-dev <span dir=3D"ltr">&=
lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blan=
k">bitcoin-dev@lists.linuxfoundation.org</a>></span> wrote:<br><blockquo=
te class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc so=
lid;padding-left:1ex"><br>
With that, notice how proving the soundness of the proofs becomes trivial: =
if<br>
validation is deterministic, it is obviously impossible to construct two<br=
>
different proofs that prove contradictory statements, because a proof is si=
mply<br>
part of the data structure itself. Contradiction would imply that the two<b=
r>
proofs are different, but that's easily rejected by simply checking the=
hash of<br>
the data.<br></blockquote><div><br></div><div>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.</div><div><br></div><div>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?</div><div><br=
></div><div>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.</div></div></div></div>
--001a114401829b44c9054929e8d0--
|
