MIME-Version: 1.0
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Wed, 6 Sep 2017 21:59:54 -0400
Message-ID: <CAMZUoKmD4v4vn9L=kdyJNk-km3XHpNVkD_tmS+SseMsf6YaVPg@mail.gmail.com>
To: Mark Friedenbach <mark@friedenbach.org>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="001a114db88c4a779c05588fd215"
Subject: Re: [bitcoin-dev] Fast Merkle Trees
Precedence: list

--001a114db88c4a779c05588fd215
Content-Type: text/plain; charset="UTF-8"

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
>

--001a114db88c4a779c05588fd215
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div 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 fi=
xed value, which should itself be the SHA-256 hash of some fixed string (e.=
g. the string &quot;BIP ???&quot; or &quot;Fash SHA-256&quot;).<br><br></di=
v>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 ha=
ve hash 0x80000..0000100 (which 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 clas=
s=3D"gmail_extra"><br><div class=3D"gmail_quote">On Wed, Sep 6, 2017 at 8:3=
8 PM, Mark Friedenbach via bitcoin-dev <span dir=3D"ltr">&lt;<a href=3D"mai=
lto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@li=
sts.linuxfoundation.org</a>&gt;</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/<wbr>bitcoin/tr=
ee/fast-merkle-tree</a><br></blockquote></div></div></div></div></div></div=
></div></div></div>

--001a114db88c4a779c05588fd215--