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
|
Return-Path: <mark@friedenbach.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id D1986486
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 7 Sep 2017 02:20:08 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-pg0-f49.google.com (mail-pg0-f49.google.com [74.125.83.49])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 50C3B1E5
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 7 Sep 2017 02:20:08 +0000 (UTC)
Received: by mail-pg0-f49.google.com with SMTP id 188so15160704pgb.2
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 06 Sep 2017 19:20:08 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=friedenbach-org.20150623.gappssmtp.com; s=20150623;
h=mime-version:subject:from:in-reply-to:date:cc
:content-transfer-encoding:message-id:references:to;
bh=O99owo4VeAG8qGCck0PX8f7UNn60b2znQ2XeDqHaeZk=;
b=kst5S6SGpMa41QWwqy04OF+UL59HX2LSLo6kB3Ep/Me8S4Rm/HRohBLVxj1BYRPM+w
HKNzGFuO9J1HVOMKhjKwDgJ3U0RBHS/WEBcQGeruvF5L+UBkj1pug9WA1FyHchJxWv4i
FYLbiNVQEC9OpXoJckGL0VcS+ZskHCBaBHitUMQm94cEmys5diVGym6eGKiZKfO4bbxb
6niCY8nQiggQ0dJNiYbB4/lc18CekjypV2hv/GIyjURZPacwBi/iQoSloD200kmtuFSj
6HDRdip0uDlGaipnlvchyRg0cg+4a76qDp+1LL7qFtIww/ivw1+hQ0UTXx43lgXcJ8HW
YU/A==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc
:content-transfer-encoding:message-id:references:to;
bh=O99owo4VeAG8qGCck0PX8f7UNn60b2znQ2XeDqHaeZk=;
b=IxLkafmiLvKzwqfOnxtyTaNEwnlAx+zsB7Ol6PZWJ1cKILbtC2GMciEWjBtBdfJ1F0
LBnisElrJnuN6o0fWs9Eu+miPQKDFO15nqmMVDytpGkdJhy52jWTVfSp6y6x74dErufk
TJRYE+dTSk5+pHUU6z4Y4zIy8QjNQrSg2nltiTPT1THmfAqCsxU54X2R5f+HD/IUnYOe
RUPSABMPGFuc8n5RyRgeG3ZNNCTbSa6PG2TkIjOJ4y+Co/x6x0gCabH+3dVYV2WwaJ0B
CBgbIBIm6yGXbSR3wMVKAiRzJZKuxJubFh9hipqRcVtsKSFlz6DgqwHOUkMZHjgGprVf
wYXw==
X-Gm-Message-State: AHPjjUhtJFvTHNB7tZdUjJlqc9OEy0/dWUdfTSo1V8X7fL60CTWaNz4h
PJSXlkdSyU1IPO7YWBvFSA==
X-Google-Smtp-Source: ADKCNb5mjegnFJ6zJIttXxlC0WDzrQCOyeo4KAlKrBQ/RWD/+dVdNnBy+XGTQ/upRWBlmVJ90AhEQQ==
X-Received: by 10.98.17.156 with SMTP id 28mr1155647pfr.83.1504750807670;
Wed, 06 Sep 2017 19:20:07 -0700 (PDT)
Received: from ?IPv6:2601:646:8080:1291:9c8f:a514:978d:a19a?
([2601:646:8080:1291:9c8f:a514:978d:a19a])
by smtp.gmail.com with ESMTPSA id
x28sm1162743pgc.91.2017.09.06.19.20.06
(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
Wed, 06 Sep 2017 19:20:06 -0700 (PDT)
Content-Type: multipart/alternative;
boundary=Apple-Mail-6D4C8F99-E208-40D8-86E3-84CAF12792B7
Mime-Version: 1.0 (1.0)
From: Mark Friedenbach <mark@friedenbach.org>
X-Mailer: iPhone Mail (14G60)
In-Reply-To: <CAMZUoKmD4v4vn9L=kdyJNk-km3XHpNVkD_tmS+SseMsf6YaVPg@mail.gmail.com>
Date: Wed, 6 Sep 2017 19:20:06 -0700
Content-Transfer-Encoding: 7bit
Message-Id: <F1D041D0-FC5A-425C-835D-37E7A9C0CFC5@friedenbach.org>
References: <CAMZUoKmD4v4vn9L=kdyJNk-km3XHpNVkD_tmS+SseMsf6YaVPg@mail.gmail.com>
To: Russell O'Connor <roconnor@blockstream.io>
X-Spam-Status: No, score=0.0 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
HTML_MESSAGE,MIME_QP_LONG_LINE,RCVD_IN_DNSWL_NONE autolearn=disabled
version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Thu, 07 Sep 2017 05:24:13 +0000
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 02:20:08 -0000
--Apple-Mail-6D4C8F99-E208-40D8-86E3-84CAF12792B7
Content-Type: text/plain;
charset=us-ascii
Content-Transfer-Encoding: quoted-printable
This design purposefully does not distinguish leaf nodes from internal nodes=
. That way it chained invocations can be used to validate paths longer than 3=
2 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> wro=
te:
>=20
> The fast hash for internal nodes needs to use an IV that is not the standa=
rd SHA-256 IV. Instead needs to use some other fixed value, which should its=
elf be the SHA-256 hash of some fixed string (e.g. the string "BIP ???" or "=
Fash SHA-256").
>=20
> As it stands, I believe someone can claim a leaf node as an internal node b=
y creating a proof that provides a phony right-hand branch claiming to have h=
ash 0x80000..0000100 (which is really the padding value for the second half o=
f a double SHA-256 hash).
>=20
> (I was schooled by Peter Todd by a similar issue in the past.)
>=20
>> 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
--Apple-Mail-6D4C8F99-E208-40D8-86E3-84CAF12792B7
Content-Type: text/html;
charset=utf-8
Content-Transfer-Encoding: quoted-printable
<html><head><meta http-equiv=3D"content-type" content=3D"text/html; charset=3D=
utf-8"></head><body dir=3D"auto"><div>This design purposefully does not dist=
inguish leaf nodes from internal nodes. That way it chained invocations can b=
e used to validate paths longer than 32 branches. Do you see a vulnerability=
due to this lack of distinction?<br></div><div><br>On Sep 6, 2017, at 6:59 P=
M, Russell O'Connor <<a href=3D"mailto:roconnor@blockstream.io">roconnor@=
blockstream.io</a>> wrote:<br><br></div><blockquote type=3D"cite"><div><d=
iv dir=3D"ltr"><div><div>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 v=
alue, 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 s=
omeone can claim a leaf node as an internal node by creating a proof that pr=
ovides a phony right-hand branch claiming to have hash 0x80000..0000100 (whi=
ch is really the padding value for the second half of a double SHA-256 hash)=
.<br><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 bitcoi=
n-dev <span dir=3D"ltr"><<a href=3D"mailto:bitcoin-dev@lists.linuxfoundat=
ion.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>></sp=
an> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;b=
order-left:1px #ccc solid;padding-left:1ex">
Fast Merkle Trees<br>
BIP: <a href=3D"https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee=
0a" rel=3D"noreferrer" target=3D"_blank">https://gist.github.com/maaku/<wbr>=
41b0054de0731321d23e9da90ba4ee<wbr>0a</a><br>
Code: <a href=3D"https://github.com/maaku/bitcoin/tree/fast-merkle-tree" rel=
=3D"noreferrer" target=3D"_blank">https://github.com/maaku/<wbr>bitcoin/tree=
/fast-merkle-tree</a><br></blockquote></div></div></div></div></div></div></=
div></div></div>
</div></blockquote></body></html>=
--Apple-Mail-6D4C8F99-E208-40D8-86E3-84CAF12792B7--
|
