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
134
135
136
137
138
|
Return-Path: <roconnor@blockstream.io>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 9C8148A1
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 7 Sep 2017 15:51:36 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-vk0-f45.google.com (mail-vk0-f45.google.com
[209.85.213.45])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 24ED3E5
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 7 Sep 2017 15:51:36 +0000 (UTC)
Received: by mail-vk0-f45.google.com with SMTP id v203so191037vkv.3
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 07 Sep 2017 08:51:36 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=blockstream-io.20150623.gappssmtp.com; s=20150623;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to
:cc; bh=yhW5TkRJYpw1j14Klg4E2S8EKIs7dyXSIYXDdQa8Tyw=;
b=gr7EHSZban3HYW35uKd5nMGHceoHTEu3OhlHwfuFNV0yIG+IxztAD34Eym6AOUl+ra
RbPtP7cVuKREiCmh7yPlaaz3wz2pXjxuOeUi6vBbGHQPYwk4431uVoGL4nyKxBsCPvjc
ToIkb/DQC6VtD5B42ZykN48gH5iY/704xPHUKeaVEye3m5fI11U63i4DG8n4ClUe6ZN/
XV0M/3H4LI3e9rClX/C9AysSH2b6oAI3eCFkjoBgoXfGnebk3Rs+K5B1cujnqwkeBmmL
DsVpUKYNZenTnCfnjGPhBUiErZSksX+R75tyinbJZVi77yB+3/KF3j1z8dzP7GIBXsX/
XBIA==
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=yhW5TkRJYpw1j14Klg4E2S8EKIs7dyXSIYXDdQa8Tyw=;
b=SRYKzX6vfw8MUZ1ZGKS7nQs/QYVoZEBkmk3edwE0GZcLPx8bsFrqxkzxrS/QMcAnwi
0AvKZhMQs0KsAJLljh5O6+Vyms2x8zg3HbyuYLZ74nxRcdnB8sMqrQLWjfWuUt5jRTgD
d3qbxuvXoY1meF1Fty7ZV7mudZTiVYTztsCoz1qTBEWxFa7ykxYsWA6jPpzpw6TpME+B
Lj2MnwFitWDwyC2Sv9bb3RyhT4ZjpUeMX1A8aNfI79eNQW8jbjBlXzxEBT/KiYJyU18q
jha1lpwODb+L0bkaV+/EvSGHTLvRFFmEJGrjsV8HpCEZRoKoL7U2ifSsO4CnRz50XWt4
rZYg==
X-Gm-Message-State: AHPjjUihMt9l3bfK8F3L41w7lY/OcAQKemFAFEBc9XYy3o2MAFPTscyw
o41JcM9DnYhyHp+AZiV+Y0VSBBKy+95c
X-Google-Smtp-Source: ADKCNb6xdL/3VZKGULfrz2sP1IDsdOXW++fvkCs3m+sHUCKfL8+n2woybs0eFm9GvhNbUPGqgDheVqUAIM32aa5Glw8=
X-Received: by 10.31.33.87 with SMTP id h84mr1761132vkh.105.1504799495236;
Thu, 07 Sep 2017 08:51:35 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.176.90.142 with HTTP; Thu, 7 Sep 2017 08:51:14 -0700 (PDT)
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"
X-Spam-Status: No, score=0.5 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
HTML_MESSAGE,RCVD_IN_DNSWL_NONE,RCVD_IN_SORBS_SPAM autolearn=disabled
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] Fast Merkle 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: Thu, 07 Sep 2017 15:51:36 -0000
--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"><<a hre=
f=3D"mailto:pete@petertodd.org" target=3D"_blank">pete@petertodd.org</a>>=
;</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'Connor via bitcoin-dev wrot=
e:<br>
> The fast hash for internal nodes needs to use an IV that is not the<br=
>
> standard SHA-256 IV. Instead needs to use some other fixed value, whic=
h<br>
> should itself be the SHA-256 hash of some fixed string (e.g. the strin=
g<br>
> "BIP ???" or "Fash SHA-256").<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--
|
