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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
|
Return-Path: <roconnor@blockstream.io>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id B1585B1B
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 7 Sep 2017 15:44:16 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ua0-f170.google.com (mail-ua0-f170.google.com
[209.85.217.170])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 8DBDD127
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 7 Sep 2017 15:44:14 +0000 (UTC)
Received: by mail-ua0-f170.google.com with SMTP id k23so143682uaf.4
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 07 Sep 2017 08:44:14 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=blockstream-io.20150623.gappssmtp.com; s=20150623;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to
:cc; bh=ZhWPf13OMuxlFQ0T5h4M0j/bE+ZGhXuu9T3iL/hHKEk=;
b=LBDc5kjwrNtZoCyQvwMkW7xVXfRsQHnuindNITP7yWKPkRL0k9X8YI+cTkHCf74lUq
7tQJcGuPIiyMGz8TbDNXUMW7Yu6XmPUAsnXKyKeJHNK/G6IVUdRpHNHONKoYpQ6LI7c4
Kk4oj5DIG7+IO8StKTE4E4G25JY436BCJOuhHTM4W8icvhoFruURXwZEmuAOvh23PZTd
HeEIAcREXJZf655O1hyniZxZZKAONAN86KLHmseJWesb5TLjnrAi6TbxJrAYEl6u455O
HbYGuhyspfYmKQrSDzPySORoivXcTY0l8Y9BFKhbkliLo1W22Iwd2HbUc9Oq6tjAQNFz
Csmg==
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:cc;
bh=ZhWPf13OMuxlFQ0T5h4M0j/bE+ZGhXuu9T3iL/hHKEk=;
b=V+nsnyfcfIvaTCyqS8WZjhADUK6YEeKkL9VO/yTarzRB+MbjmMdmFntEHZqyprhWUQ
sTE/isn7v54kM2hZiTNnnt2YG4kl0I4K9vUffL+P9n4y9xrcg6o1EjQua+6Xh/IcUcVp
ro45qPSFGlVeYu+VwI38F6Lbkr6YxdopuOwcH+etOIac02F5bc/00li7OOevhdq/8U2e
B3Z4Z3e83N3E9df/8h/V9XaxolJNzrdFEjRZN4v+7bnp1QixK6vRJEI4we+p3yZ6PD2h
bhHYEWjcA2C0RYWDSqURjUjXgrGdzBiCX9bTEe1bNPmpAFf0fiqFjAmg09OjRCSNmPqv
Oenw==
X-Gm-Message-State: AHPjjUjQuy6BF4oKtPuPp6Lp9na3wLxhixjW+Dq9ehNVwhrdxjWmEnpI
f5XBMeeRAnxhNvrgZZ7omPqTqFt1uZzH
X-Google-Smtp-Source: ADKCNb6YlESXt9lf8PpSvrn1u7lvf3pzfhYcxT0qnjoNAqmNyc4kWRgT6YHyHKWsPBOORpE65VnYDUvG9PYDO3ETVBI=
X-Received: by 10.159.50.7 with SMTP id x7mr1864990uad.50.1504799053508; Thu,
07 Sep 2017 08:44:13 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.176.90.142 with HTTP; Thu, 7 Sep 2017 08:43:52 -0700 (PDT)
In-Reply-To: <F1D041D0-FC5A-425C-835D-37E7A9C0CFC5@friedenbach.org>
References: <CAMZUoKmD4v4vn9L=kdyJNk-km3XHpNVkD_tmS+SseMsf6YaVPg@mail.gmail.com>
<F1D041D0-FC5A-425C-835D-37E7A9C0CFC5@friedenbach.org>
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Thu, 7 Sep 2017 11:43:52 -0400
Message-ID: <CAMZUoKmhN=m4TFwJi7u1bibLJ6mYvpnkddWTZZWdHn7+mVcJvw@mail.gmail.com>
To: Mark Friedenbach <mark@friedenbach.org>
Content-Type: multipart/alternative; boundary="001a11455f0a0b5e6d05589b55c2"
X-Spam-Status: No, score=0.5 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
HTML_MESSAGE,RCVD_IN_DNSWL_NONE,RCVD_IN_SORBS_SPAM autolearn=disabled
version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Fast Merkle Trees
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, 07 Sep 2017 15:44:16 -0000
--001a11455f0a0b5e6d05589b55c2
Content-Type: text/plain; charset="UTF-8"
In that case, you may as well remove all references to leaves and double
SHA-256 from your BIP since your design has no method for distinguishing
between internal nodes and leaves.
I think that if this design stands, it will play a role in some future
CVEs. The BIP itself is too abstract about its data contents to
specifically say that it has a vulnerability; however, I believe it is
inviting vulnerabilities.
For example, I might agree with a counterparty to a design of some sort of
smart contract in the form of a MAST. My counterparty has shown me all the
"leaves" of our MAST and I can verify its Merkle root computation.
After being deployed, I found out that one of the leaves wasn't really a
leaf but is instead a specially crafted "script" with a fake pubkey chosen
by my couterparty so that this leaf can also be interpreted as a fake
internal node (i.e. an internal node with a right branch of 0x8000...100).
Because the Fast Merkle Tree design doesn't distinguish between leaves and
internal nodes my counter party gets away with building an Inclusion Proof
through this "leaf" to reveal the evil code that they had designed into the
MAST at a deeper level.
Turns out my counterparty was grinding their evil code to produce an
internal node that can also be parsed as an innocent script. They used
their "pubkey" to absorb excess random data from their grinding that they
cannot eliminate.
(The counterparty doesn't actually know the discrete log of this "pubkey",
they just claimed it was their pubkey and I believed them).
Having ambiguity about whether a node is a leaf or an internal node is a
security risk. Furthermore, changing the design so that internal node and
leaves are distinguishable still allows chained invocations.
Arbitrary data can be stored in Fast Merkle Tree leaves, including the
Merkle root of another Fast Merkle Tree.
Applications that are limited to proof with paths no longer than 32
branches can still circumvent this limit by staging these Fast Merkle Trees
in explicit layers (as opposed to the implicit layers with the current
design).
By storing a inner Fast Merkle Tree root inside the (explicit) leaf of an
outer Fast Merkle Tree, the application can verify a Inclusion Proof of the
inner Fast Merkle Tree Root in the outer Fast Merkle Tree Root, and then
verify a second Inclusion Proof of the desired data in the inner Faster
Merkle Tree Root. The application will need to tag their data to
distinguish between inner Fast Merkle Tree Roots and other application
data, but that is just part of the general expectation that applications
not store ambiguous data inside the leaves of Fast Merkle Trees.
On Wed, Sep 6, 2017 at 10:20 PM, Mark Friedenbach <mark@friedenbach.org>
wrote:
> This design purposefully does not distinguish leaf nodes from internal
> nodes. That way it chained invocations can be used to validate paths longer
> than 32 branches. Do you see a vulnerability due to this lack of
> distinction?
>
> On Sep 6, 2017, at 6:59 PM, Russell O'Connor <roconnor@blockstream.io>
> wrote:
>
> The fast hash for internal nodes needs to use an IV that is not the
> standard SHA-256 IV. Instead needs to use some other fixed value, which
> should itself be the SHA-256 hash of some fixed string (e.g. the string
> "BIP ???" or "Fash SHA-256").
>
> As it stands, I believe someone can claim a leaf node as an internal node
> by creating a proof that provides a phony right-hand branch claiming to
> have hash 0x80000..0000100 (which is really the padding value for the
> second half of a double SHA-256 hash).
>
> (I was schooled by Peter Todd by a similar issue in the past.)
>
> On Wed, Sep 6, 2017 at 8:38 PM, Mark Friedenbach via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Fast Merkle Trees
>> BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a
>> Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree
>>
>
--001a11455f0a0b5e6d05589b55c2
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>In that case, you may as well remove all references t=
o leaves and double SHA-256 from your BIP since your design has no method f=
or distinguishing between internal nodes and leaves.</div><div><br></div><d=
iv>I think that if this design stands, it will play a role in some future C=
VEs.=C2=A0 The BIP itself is too abstract about its data contents to specif=
ically say that it has a vulnerability; however, I believe it is inviting v=
ulnerabilities.</div><div>For example, I might agree with a counterparty to=
a design of some sort of smart contract in the form of a MAST.=C2=A0 My co=
unterparty has shown me all the "leaves" of our MAST and I can ve=
rify its Merkle root computation.</div><div>After being deployed, I found o=
ut that one of the leaves wasn't really a leaf but is instead a special=
ly crafted "script" with a fake pubkey chosen by my couterparty s=
o that this leaf can also be interpreted as a fake internal node (i.e. an i=
nternal node with a right branch of 0x8000...100).</div><div>Because the Fa=
st Merkle Tree design doesn't distinguish between leaves and internal n=
odes my counter party gets away with building an Inclusion Proof through th=
is "leaf" to reveal the evil code that they had designed into the=
MAST at a deeper level.</div><div><br></div><div>Turns out my counterparty=
was grinding their evil code to produce an internal node that can also be =
parsed as an innocent script.=C2=A0 They used their "pubkey" to a=
bsorb excess random data from their grinding that they cannot eliminate.</d=
iv><div>(The counterparty doesn't actually know the discrete log of thi=
s "pubkey", they just claimed it was their pubkey and I believed =
them).</div><div><br></div><div><br></div><div>Having ambiguity about wheth=
er a node is a leaf or an internal node is a security risk. Furthermore, ch=
anging the design so that internal node and leaves are distinguishable stil=
l allows chained invocations.</div><div>Arbitrary data can be stored in Fas=
t Merkle Tree leaves, including the Merkle root of another Fast Merkle Tree=
.</div><div>Applications that are limited to proof with paths no longer tha=
n 32 branches can still circumvent this limit by staging these Fast Merkle =
Trees in explicit layers (as opposed to the implicit layers with the curren=
t design).</div><div><br></div><div>By storing a inner Fast Merkle Tree roo=
t inside the (explicit) leaf of an outer Fast Merkle Tree, the application =
can verify a Inclusion Proof of the inner Fast Merkle Tree Root in the oute=
r Fast Merkle Tree Root, and then verify a second Inclusion Proof of the de=
sired data in the inner Faster Merkle Tree Root.=C2=A0 The application will=
need to tag their data to distinguish between inner Fast Merkle Tree Roots=
and other application data, but that is just part of the general expectati=
on that applications not store ambiguous data inside the leaves of Fast Mer=
kle Trees.<br></div><div><br></div></div><div class=3D"gmail_extra"><br><di=
v class=3D"gmail_quote">On Wed, Sep 6, 2017 at 10:20 PM, Mark Friedenbach <=
span dir=3D"ltr"><<a href=3D"mailto:mark@friedenbach.org" target=3D"_bla=
nk">mark@friedenbach.org</a>></span> wrote:<br><blockquote class=3D"gmai=
l_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left=
:1ex"><div dir=3D"auto"><div>This design purposefully does not distinguish =
leaf nodes from internal nodes. That way it chained invocations can be used=
to validate paths longer than 32 branches. Do you see a vulnerability due =
to this lack of distinction?<br></div><div><div class=3D"h5"><div><br>On Se=
p 6, 2017, at 6:59 PM, Russell O'Connor <<a href=3D"mailto:roconnor@=
blockstream.io" target=3D"_blank">roconnor@blockstream.io</a>> wrote:<br=
><br></div><blockquote type=3D"cite"><div><div dir=3D"ltr"><div><div>The fa=
st hash for internal nodes needs to use an IV that is not the standard SHA-=
256 IV. Instead needs to use some other fixed value, which should itself be=
the SHA-256 hash of some fixed string (e.g. the string "BIP ???"=
or "Fash SHA-256").<br><br></div>As it stands, I believe someone=
can claim a leaf node as an internal node by creating a proof that provide=
s a phony right-hand branch claiming to have hash 0x80000..0000100 (which i=
s really the padding value for the second half of a double SHA-256 hash).<b=
r><br></div>(I was schooled by Peter Todd by a similar issue in the past.)<=
br><div><div><div><div><div><div><div class=3D"gmail_extra"><br><div class=
=3D"gmail_quote">On Wed, Sep 6, 2017 at 8:38 PM, Mark Friedenbach via bitco=
in-dev <span dir=3D"ltr"><<a href=3D"mailto:bitcoin-dev@lists.linuxfound=
ation.org" target=3D"_blank">bitcoin-dev@lists.<wbr>linuxfoundation.org</a>=
></span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0=
0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Fast Merkle Trees<br>
BIP: <a href=3D"https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4e=
e0a" rel=3D"noreferrer" target=3D"_blank">https://gist.github.com/maaku/<wb=
r>41b0054de0731321d23e9da90ba4ee<wbr>0a</a><br>
Code: <a href=3D"https://github.com/maaku/bitcoin/tree/fast-merkle-tree" re=
l=3D"noreferrer" target=3D"_blank">https://github.com/maaku/bitco<wbr>in/tr=
ee/fast-merkle-tree</a><br></blockquote></div></div></div></div></div></div=
></div></div></div>
</div></blockquote></div></div></div></blockquote></div><br></div>
--001a11455f0a0b5e6d05589b55c2--
|
