MIME-Version: 1.0
In-Reply-To: <20170907055557.GA12638@fedora-23-dvm>
References: <CAMZUoKmD4v4vn9L=kdyJNk-km3XHpNVkD_tmS+SseMsf6YaVPg@mail.gmail.com>
	<20170907055557.GA12638@fedora-23-dvm>
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Thu, 7 Sep 2017 11:51:14 -0400
Message-ID: <CAMZUoKk=00AJbtq602P=MWtGhWUY_7oCrWEUj+K7xp_+DOOTYg@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>
Content-Type: multipart/alternative; boundary="001a11c000445f4b7b05589b6f38"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Fast Merkle Trees
Precedence: list

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

On Thu, Sep 7, 2017 at 1:55 AM, Peter Todd <pete@petertodd.org> wrote:

> On Wed, Sep 06, 2017 at 09:59:54PM -0400, Russell O'Connor via bitcoin-dev
> 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").
>
> Note that in general, designs should *not* create new hash functions by
> using
> custom IVs, but rather use bog-standard SHA256, and make a fixed first
> block.
> That allows unoptimised implementations to just hash a block with the
> second
> initialization value, and optimized implementations to start with the fixed
> midstate.


I 100% agree.

With SHA256 every final state is also a valid midstate.  Therefore, using a
custom IV of the SHA256 hash of some fixed string results in a hash of data
that is functionally equivalent to prefixing the data with the padded
version of the fixed string and using a regular SHA256 hash of the combined
data.  This is important and I should have explicitly pointed it out.

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

<div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><div class=3D"gmail_quo=
te">On Thu, Sep 7, 2017 at 1:55 AM, Peter Todd <span dir=3D"ltr">&lt;<a hre=
f=3D"mailto:pete@petertodd.org" target=3D"_blank">pete@petertodd.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"><span class=3D"">On Wed, =
Sep 06, 2017 at 09:59:54PM -0400, Russell O&#39;Connor via bitcoin-dev wrot=
e:<br>
&gt; The fast hash for internal nodes needs to use an IV that is not the<br=
>
&gt; standard SHA-256 IV. Instead needs to use some other fixed value, whic=
h<br>
&gt; should itself be the SHA-256 hash of some fixed string (e.g. the strin=
g<br>
&gt; &quot;BIP ???&quot; or &quot;Fash SHA-256&quot;).<br>
<br>
</span>Note that in general, designs should *not* create new hash functions=
 by using<br>
custom IVs, but rather use bog-standard SHA256, and make a fixed first bloc=
k.<br>
That allows unoptimised implementations to just hash a block with the secon=
d<br>
initialization value, and optimized implementations to start with the fixed=
<br>
midstate.</blockquote><div><br></div><div>I 100% agree.</div><div><br></div=
><div>With SHA256 every final state is also a valid midstate.=C2=A0 Therefo=
re, using a custom IV of the SHA256 hash of some fixed string results in a =
hash of data that is functionally equivalent to prefixing the data with the=
 padded version of the fixed string and using a regular SHA256 hash of the =
combined data.=C2=A0 This is important and I should have explicitly pointed=
 it out.<br></div></div></div></div>

--001a11c000445f4b7b05589b6f38--