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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
|
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 3FC94B2B
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 1 Jun 2017 15:11:18 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ua0-f169.google.com (mail-ua0-f169.google.com
[209.85.217.169])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 9A58F193
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 1 Jun 2017 15:11:17 +0000 (UTC)
Received: by mail-ua0-f169.google.com with SMTP id u10so29302444uaf.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 01 Jun 2017 08:11:17 -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=JQkEYhLSgFQs5QMMQImNlqzKw1NvmsziJXjBLf6AvUw=;
b=eRh4iVYKLXGZK5SJ4/OkaXx6XuT8fGe2jqU7l7d9VfJi8u95GAJKWc3JhgDaeW2Xo+
QV+6vuW4Z8MtcXGPZ89t6BtZYlgZHTlRejMekgeKOf9yshMc/DA26IBJwRrMMqfQKTZc
L2FpFRexDognzI3ZU90uFhh1zBEmSYcHCWHuLB+1niTnlIgjI0PSaZn9fk9NMmU6oV88
NToCxqiy8xwsfRZLcarAk0jck0oFEy1lqapTfhMuZ0ooMGL1kOFWzlIDqomv24poaKAh
WQ3TetsQFLsdOnvo7/WEwHqymcQ86eVsqtAj4TihXPlHQwZCCJne/DFHJirdsRMjhH5a
EfmQ==
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=JQkEYhLSgFQs5QMMQImNlqzKw1NvmsziJXjBLf6AvUw=;
b=L+SMu7B6L2n8NOpbO/h/E/H5mhWZ7nXYY3+OBD06obF4ITVCdIADbkkNYehiyKxUEI
Rwb0mfNcKsl3QKvpCBYZG5UQRt4232alY0jM0HaIFWpM8FbQGVyrPAQKgxxvYX7Je/1d
1iDKZMeifPggCeXuqAxY+kYPBhmqvzuUVkhOjZ2msBXF5gPo7LBqJGYINfsS57jyUlfg
RTlxYLWRt6oj4iMGIOm1WnKiGLUFNTUx0Bu+MCrP4Xjyy97Udf69zwaC2vqrThG3pXLx
xSHggyaZbapP+3oBn1PXR+NwQ7NITPFTuIF3AUPhj/9Ho9UBryR4f7XCM1/aoniq/D1L
CUqw==
X-Gm-Message-State: AODbwcDQE6EWy2mrBdpeISzIdD/zwlZSdFRP4ewwHpihoPZZnfz/RmhC
KuhKBmDEaWycH+tE2fSiTSwTblNiEkjPHZs=
X-Received: by 10.159.35.197 with SMTP id 63mr1079609uao.134.1496329876628;
Thu, 01 Jun 2017 08:11:16 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.176.95.90 with HTTP; Thu, 1 Jun 2017 08:10:56 -0700 (PDT)
In-Reply-To: <20170529161059.GA7698@fedora-23-dvm>
References: <CAMZUoK=f3hXHkqJBDfiLGSrgXi_ppgyH6+XWD9W54EYFWLm1+Q@mail.gmail.com>
<20170528082624.GA14552@fedora-23-dvm>
<CAMZUoK=8xaVp2Qoc7kvx8FdPbpY0rEpSba8kQVRQGjX4p0haxg@mail.gmail.com>
<20170529161059.GA7698@fedora-23-dvm>
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Thu, 1 Jun 2017 11:10:56 -0400
Message-ID: <CAMZUoKm6Oh4fp3nK3sTkfX+cu2Nuf6gKRs87Cu4w9Tm+G5Jb5Q@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>
Content-Type: multipart/alternative; boundary="94eb2c03dfe6c381460550e772d4"
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: Thu, 01 Jun 2017 15:11:18 -0000
--94eb2c03dfe6c381460550e772d4
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
On Mon, May 29, 2017 at 12:10 PM, Peter Todd <pete@petertodd.org> wrote:
> On Mon, May 29, 2017 at 10:55:37AM -0400, Russell O'Connor wrote:
> > Some of this proposal can be salvaged, I think, by putting the hash of
> the
> > tags into Sha256Compress's first argument:
> >
> > merkleRoot : Tree BitString -> Word256
> > merkleRoot (Leaf (t)) :=3D sha256Compress(sha256(t),
> > 0b0^512)
> > merkleRoot (Unary (t, child)) :=3D sha256Compress(sha256(t),
> > merkleRoot(child) =E2=8B=85 0b0^256)
> > merkleRoot (Binary (t, left, right)) :=3D sha256Compress(sha256(t),
> > merkleRoot(left) =E2=8B=85 merkleRoot(right))
> >
> > The Merkle--Damg=C3=A5rd property will still hold under the same condit=
ions
> > about tags determining the type of node (Leaf, Unary, or Binary) while
> > avoiding the need for SHA256's padding. If you have a small number of
> > tags, then you can pre-compute their hashes so that you only end up wit=
h
> > one call to SHA256 compress per node. If you have tags with a large
> amount
> > of data, you were going to be hashing them anyways.
>
> Notice how what you're proposing here is almost the same thing as using
> SHA256
> directly, modulo the fact that you skip the final block containing the
> message
> length.
>
> Similarly, you don't need to compute sha256(t) - you can just as easily
> compute
> the midstate sha256Compress(IV, t), and cache that midstate if you can
> reuse
> tags. Again, the only difference is the last block.
>
Yes, either way would be fine.
> > Unfortunately we lose the ability to cleverly avoid collisions between
> the
> > Sha256 and MerkleRoot functions by using safe tags.
>
> I think a better question to ask is why you want that property in the fir=
st
> place?
>
> My earlier python-proofmarshal(1) library had a scheme of per-use-case
> tags,
> but I eventually realised that depending on tags being unique is a
> footgun. For
> example, it's easy to see how two different systems could end up using th=
e
> same
> tag due to designers forgetting to create new tags while copying and
> pasting
> old code. Similarly, if two such systems have to be integrated, you'll en=
d
> up
> with tags getting reused for two different purposes.
>
> Now, if you design a system where that doesn't matter, then by extension
> it'll
> also be true that collisions between the sha256 and merkleroot functions
> don't
> matter either. And that system will be more robust to design mistakes, as
> tags
> only need to be unique "locally" to distinguish between different
> sub-types in
> a sum type (enum).
>
I was looking to add the property mostly because it was free to do with my
original design when the set of tags was small and could make some
applications more robust and/or easier to debug.
--94eb2c03dfe6c381460550e772d4
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 Mon, May 29, 2017 at 12:10 PM, Peter Todd <span dir=3D"ltr"><<a h=
ref=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 Mon=
, May 29, 2017 at 10:55:37AM -0400, Russell O'Connor wrote:<br></span><=
span class=3D"">> Some of this proposal can be salvaged, I think, by put=
ting the hash of the<br>
> tags into Sha256Compress's first argument:<br>
><br>
>=C2=A0 =C2=A0 =C2=A0merkleRoot : Tree BitString -> Word256<br>
>=C2=A0 =C2=A0 =C2=A0merkleRoot (Leaf (t))=C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 :=3D sha256Compress(sha256(t),<br>
> 0b0^512)<br>
>=C2=A0 =C2=A0 =C2=A0merkleRoot (Unary (t, child))=C2=A0 =C2=A0 =C2=A0 =
=C2=A0 :=3D sha256Compress(sha256(t),<br>
> merkleRoot(child) =E2=8B=85 0b0^256)<br>
>=C2=A0 =C2=A0 =C2=A0merkleRoot (Binary (t, left, right)) :=3D sha256Com=
press(sha256(t),<br>
> merkleRoot(left) =E2=8B=85 merkleRoot(right))<br>
><br>
> The Merkle--Damg=C3=A5rd property will still hold under the same condi=
tions<br>
> about tags determining the type of node (Leaf, Unary, or Binary) while=
<br>
> avoiding the need for SHA256's padding.=C2=A0 If you have a small =
number of<br>
> tags, then you can pre-compute their hashes so that you only end up wi=
th<br>
> one call to SHA256 compress per node. If you have tags with a large am=
ount<br>
> of data, you were going to be hashing them anyways.<br>
<br>
</span>Notice how what you're proposing here is almost the same thing a=
s using SHA256<br>
directly, modulo the fact that you skip the final block containing the mess=
age<br>
length.<br>
<br>
Similarly, you don't need to compute sha256(t) - you can just as easily=
compute<br>
the midstate sha256Compress(IV, t), and cache that midstate if you can reus=
e<br>
tags. Again, the only difference is the last block.<span class=3D""><br></s=
pan></blockquote><div><br></div><div>Yes, either way would be fine.<br></di=
v><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 =
.8ex;border-left:1px #ccc solid;padding-left:1ex"><span class=3D"">
> Unfortunately we lose the ability to cleverly avoid collisions between=
the<br>
> Sha256 and MerkleRoot functions by using safe tags.<br>
<br>
</span>I think a better question to ask is why you want that property in th=
e first<br>
place?<br>
<br>
My earlier python-proofmarshal(1) library had a scheme of per-use-case tags=
,<br>
but I eventually realised that depending on tags being unique is a footgun.=
For<br>
example, it's easy to see how two different systems could end up using =
the same<br>
tag due to designers forgetting to create new tags while copying and pastin=
g<br>
old code. Similarly, if two such systems have to be integrated, you'll =
end up<br>
with tags getting reused for two different purposes.<br>
<br>
Now, if you design a system where that doesn't matter, then by extensio=
n it'll<br>
also be true that collisions between the sha256 and merkleroot functions do=
n't<br>
matter either. And that system will be more robust to design mistakes, as t=
ags<br>
only need to be unique "locally" to distinguish between different=
sub-types in<br>
a sum type (enum).<br></blockquote><div><br></div><div>I was looking to add=
the property mostly because it was free to do with my original design when=
the set of tags was small and could make some applications more robust and=
/or easier to debug.<br></div></div></div></div>
--94eb2c03dfe6c381460550e772d4--
|
