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
|
Return-Path: <bram@bittorrent.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 714AFB44
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 23 May 2017 06:06:10 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f48.google.com (mail-wm0-f48.google.com [74.125.82.48])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id CAFC6AD
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 23 May 2017 06:06:09 +0000 (UTC)
Received: by mail-wm0-f48.google.com with SMTP id 7so12637677wmo.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 22 May 2017 23:06:09 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=bittorrent-com.20150623.gappssmtp.com; s=20150623;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to
:cc; bh=Q6/qBtuGOQYic7dBfbowIgcycFalUxE35/T+rCeNGS8=;
b=g/8mo/VPDND8oRswle8gBAZQHtqqbQP3F2iVneWbpv/NuX2DmHlsKYFP9FXrDro7T2
yssKDi/n6I97jQemH5jeX8vFNZIsdrw00LuMujWeu9JJsgw0w7oWr7nNnYqF92XzbROX
S3gguaqB5klZP849Q78KkVFp2fCtib9ljRG2x0Qh5/G4aNJtzS1vnQ/54ZL0UU9uXfhF
MWLb+fHF72UO2YG6hsKtHUgPLsN1JCZMnFcX2mVIV74wXdAJUDEPr/P1F1henrOgk9pY
lPbALlYf+l02X9mk3FMLM1kZbgurjLnnywg7LIqw5997yIZO7TlMv4puVIiTj0FZtKVL
jf2w==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:in-reply-to:references:from:date
:message-id:subject:to:cc;
bh=Q6/qBtuGOQYic7dBfbowIgcycFalUxE35/T+rCeNGS8=;
b=cR/5fFKLNC9TzIO6+g2gLg8zs/0hT5j2tPJV6sMa5STDlBzaNycc3FS1OC6EbYKdJH
0810MzyTS7oB+elg75tN2bubWShHy/2Ke5WVPG/bgvBd/Y/wliaG88cYbCJ6Qojpd3tG
6Hz3yhvQ5HeHQI9pK8jgVi+B1aRTme0DTT9mhHQ7/cxv3nFZxitpbtlPV032dVmxUnjU
n21Zcvk6yWJdIpfx3F4lRfvRDhFSXRr6PQiuk29g+Twd6KuJJss8BaMxEh/zRtBCTIBl
pb4uFI+CGub8Q9MLK8MaDs0jIkVfnOfnA0bhbC/go0inpqohEfMVeQxZdgfGWlbIfaXu
nWFQ==
X-Gm-Message-State: AODbwcCBWmtd9YnQYbHVe4lhcITYlwLbJpRH7j4q9rJEt7H/Xbf3unf0
Zj8anJ/0PU6UDkJUwj7vip6yiuQTkkDm
X-Received: by 10.28.109.29 with SMTP id i29mr804522wmc.113.1495519568420;
Mon, 22 May 2017 23:06:08 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.223.170.201 with HTTP; Mon, 22 May 2017 23:06:07 -0700 (PDT)
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"
X-Spam-Status: No, score=-1.4 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, HTML_MESSAGE, RCVD_IN_DNSWL_NONE,
RCVD_IN_SORBS_SPAM autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] A Method for Computing Merkle Roots of Annotated
Binary 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: Tue, 23 May 2017 06:06:10 -0000
--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'Connor via bitcoin-dev <span di=
r=3D"ltr"><<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" targ=
et=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>></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 -> 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're building a Merkle Trie tha=
t'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'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'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--
|
