Content-Type: multipart/alternative;
	boundary=Apple-Mail-6D4C8F99-E208-40D8-86E3-84CAF12792B7
Mime-Version: 1.0 (1.0)
From: Mark Friedenbach <mark@friedenbach.org>
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>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Fast Merkle Trees
Precedence: list


--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 &lt;<a href=3D"mailto:roconnor@blockstream.io">roconnor@=
blockstream.io</a>&gt; 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">&lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundat=
ion.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt;</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--