MIME-Version: 1.0
In-Reply-To: <CAMZUoK=f3hXHkqJBDfiLGSrgXi_ppgyH6+XWD9W54EYFWLm1+Q@mail.gmail.com>
References: <CAMZUoK=f3hXHkqJBDfiLGSrgXi_ppgyH6+XWD9W54EYFWLm1+Q@mail.gmail.com>
From: Bram Cohen <bram@bittorrent.com>
Date: Mon, 22 May 2017 23:06:07 -0700
Message-ID: <CA+KqGkprA9XvaymW5VcpkcBQDp8s_M37r1K_9mbYScxMpV7cfQ@mail.gmail.com>
To: "Russell O'Connor" <roconnor@blockstream.io>
Content-Type: multipart/alternative; boundary="001a11478866a181f505502ac810"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] A Method for Computing Merkle Roots of Annotated
 Binary Trees
Precedence: list

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

On Mon, May 22, 2017 at 12:05 AM, Russell O'Connor via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> The SHA256 compression function takes two inputs:
>
> 1. A 256-bit value for the previous chunk in a chain, or an initial vecto=
r
> in the case of the first chunk.
> 2. A 512-bit chunk of data.
>
>     sha256Compress : Word256 =C3=97 Word512 -> Word256
>
> In total, the SHA256 compression function compresses 768-bits into
> 256-bits.  The Merkle roots of two branches occupy 512 bits, and this
> leaves another 256-bits of space available for tags.
>

Ya know, when you're building a Merkle Trie that's exactly the primitive
you need.

In my own construction the assumption is that the values are already hashed
down to 256 bits when they're passed in, and the tags (which are currently
done by sacrificing bits instead of using tags, that needs to be fixed)
include three states for either side: empty, unary, or middle. Three of
those possibilities are unreachable (empty/empty, empty/unary, unary/empty)
so there are 6 possible tags needed. This approach essentially skips doing
the unary hashes, a further performance improvement. There doesn't appear
to be any downside in leveraging this trick as long as tags are cheap.

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

<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On M=
on, May 22, 2017 at 12:05 AM, Russell O&#39;Connor via bitcoin-dev <span di=
r=3D"ltr">&lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" targ=
et=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt;</span> wrote:<b=
r><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:=
1px #ccc solid;padding-left:1ex"><div dir=3D"ltr">The SHA256 compression fu=
nction takes two inputs:<br><br>1. A 256-bit value for the previous chunk i=
n a chain, or an initial vector in the case of the first chunk.<br>2. A 512=
-bit chunk of data.<br><br><span style=3D"font-family:monospace,monospace">=
=C2=A0=C2=A0=C2=A0 sha256Compress : Word256 =C3=97 Word512 -&gt; Word256<br=
></span><br>In total, the SHA256 compression function compresses 768-bits i=
nto 256-bits.=C2=A0 The Merkle roots of two branches occupy 512 bits, and t=
his leaves another 256-bits of space available for tags.<br></div></blockqu=
ote><div><br></div><div>Ya know, when you&#39;re building a Merkle Trie tha=
t&#39;s exactly the primitive you need.</div><div><br></div><div>In my own =
construction the assumption is that the values are already hashed down to 2=
56 bits when they&#39;re passed in, and the tags (which are currently done =
by sacrificing bits instead of using tags, that needs to be fixed) include =
three states for either side: empty, unary, or middle. Three of those possi=
bilities are unreachable (empty/empty, empty/unary, unary/empty) so there a=
re 6 possible tags needed. This approach essentially skips doing the unary =
hashes, a further performance improvement. There doesn&#39;t appear to be a=
ny downside in leveraging this trick as long as tags are cheap.</div><div>=
=C2=A0</div></div></div></div>

--001a11478866a181f505502ac810--