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
|
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 080B42C
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 27 May 2017 22:07:10 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ua0-f173.google.com (mail-ua0-f173.google.com
[209.85.217.173])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 4D3AEE4
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 27 May 2017 22:07:09 +0000 (UTC)
Received: by mail-ua0-f173.google.com with SMTP id u10so20882377uaf.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 27 May 2017 15:07:09 -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;
bh=+KLbk+pyKKoIMEDqGUTba48W5YNnlp6fC8xpOheUfcw=;
b=s/OSyLgubgTBUVcxsBG95ZFonyOIEyofT1HwXGQK3vAV/3e7NQoUzfeJ5Z6o/VPh/b
4tPvMH/2JQM1uFbKXsBhfu8d61rE2rEQkcL6gAorubrRKdORLbKASK8kXuAZYKW69osR
4v5SewkerTUv6kNkXANhGjuH1A+oTFMIPebRaqztQQ1giayn9qz1lO+VtEk4Zwq8+ZPl
h6KGChIJrnalHoeITKxKob5XwgFRWum2LXbzwJvow8ytK3gcPpp8HqqicoUtlhHUAoCM
neuntqr06g3A8BDOSnyCnTOb480gEvNmpBK7xV01GYcpVqlTssakJIwiREHWQpcsfiXq
rNLg==
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;
bh=+KLbk+pyKKoIMEDqGUTba48W5YNnlp6fC8xpOheUfcw=;
b=V2rHgzNKJ4rsl+xxA/c0WTbjvCnX23oJIFoqCZV29c5vn7G/QBTj8CNBSAzVlxERbc
q6a99FvwIw8igih+POHUl7lP7AVTU8y5CLQyXJ9v4pXJa4hij6UmW2YN2PcSHiWvv0z4
04omr3xcETkS+J8cn+bwpoD5qNK2+rZ1poZ9CVa8WZGzHRIhVEVvUt5NQ5xJkMnxLzy7
UR2L+EMNk0GrVX7pKHFll+imfqF8SKxiLU2TO5xRiH8WNy+lHgXLzXYCmwvbx40QW577
ZlMNCBsuc6P5NX4/3HiYfw1FuzfgSmlpkJ3nq0w4DhQ88odYy2rc03HcCvqYNsl1NdDH
a1jg==
X-Gm-Message-State: AODbwcDgyuB50Lx9eYkPQiDPYNVcsBSJQb0IpFukWv0NGhu0vk0E6gih
0MSOnvMEC6ln/ltbGPPNYsXbnYWrCHTFfhA=
X-Received: by 10.159.41.130 with SMTP id s2mr4255386uas.44.1495922828412;
Sat, 27 May 2017 15:07:08 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.176.95.90 with HTTP; Sat, 27 May 2017 15:07:07 -0700 (PDT)
Received: by 10.176.95.90 with HTTP; Sat, 27 May 2017 15:07:07 -0700 (PDT)
In-Reply-To: <CAMZUoKkS8azx7Gooo3D+H_gdGdTNiNtwwNVbvU0u7HzOfdUSBg@mail.gmail.com>
References: <CAMZUoK=f3hXHkqJBDfiLGSrgXi_ppgyH6+XWD9W54EYFWLm1+Q@mail.gmail.com>
<20170522140548.GA17732@fedora-23-dvm>
<CAMZUoKk1fxOLgBfuxqXpxG-M5ZCPHZBb62_LZF7H4syQ-L7tCg@mail.gmail.com>
<20170527174138.GA7610@fedora-23-dvm>
<CAMZUoKkS8azx7Gooo3D+H_gdGdTNiNtwwNVbvU0u7HzOfdUSBg@mail.gmail.com>
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Sat, 27 May 2017 18:07:07 -0400
Message-ID: <CAMZUoKmAsxZFaLoOeAQT-YwCJBZ4z+qWJtRHPOXKTyqG7EAsfw@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="001a114c1e92cc98da055088ac4d"
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.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: Sat, 27 May 2017 22:07:10 -0000
--001a114c1e92cc98da055088ac4d
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
On May 28, 2017 06:09, "Russell O'Connor" <roconnor@blockstream.io> wrote:
On May 28, 2017 03:16, "Peter Todd" <pete@petertodd.org> wrote:
On Mon, May 22, 2017 at 06:32:38PM -0400, Russell O'Connor wrote:
> On May 22, 2017 23:05, "Peter Todd" <pete@petertodd.org> wrote:
>
> On Mon, May 22, 2017 at 03:05:49AM -0400, Russell O'Connor via bitcoin-de=
v
> wrote:
> > MerkleRoot :=3D SHA256(SHA256(LeftRoot =E2=8B=85 RightRoot))
> > sha256Compress : Word256 =C3=97 Word512 -> Word256
>
> To be clear, what math operations do you mean by "=E2=8B=85" and "=C3=97"=
?
>
>
> By "=E2=8B=85", I usually mean concatenation (though I also use it for fu=
nction
> composition in one instance). By "=C3=97", I mean the Cartesian product=
.
Cartesian product can mean a lot of things.
What specifically do you mean by "cartesian product" here?
Oops, I forgot to reply all. Below is my reply.
Given two types A and B, then A =C3=97 B is the type of pairs of A and B in=
the
sense of type theory as used in Standard ML or Haskell or other typed
languages.
To follow up, by "sha256Compress : Word256 =C3=97 Word512 -> Word256" I mea=
n
that sha256Compress is a function that takes two arguments, the first being
a 256 bit word and the second being a 512 bit word, and returns a 256 bit
word (or equivalently sha256Compress is a function that takes a pair as
input, the first component being a 256 bit word and the second component
being a 512 bit word, and returns a 256 bit word).
sha256Compress is meant to be the compression function defined by the
SHA256 standard, though nothing here depends on anything more that its type
signature.
--001a114c1e92cc98da055088ac4d
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"auto"><div><br><div class=3D"gmail_extra"><br><div class=3D"gma=
il_quote">On May 28, 2017 06:09, "Russell O'Connor" <<a hr=
ef=3D"mailto:roconnor@blockstream.io" target=3D"_blank">roconnor@blockstrea=
m.io</a>> wrote:<br type=3D"attribution"><blockquote class=3D"m_83073273=
10890922742quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;pad=
ding-left:1ex"><div dir=3D"auto"><div class=3D"m_8307327310890922742elided-=
text"><div><br><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">On=
May 28, 2017 03:16, "Peter Todd" <<a href=3D"mailto:pete@pete=
rtodd.org" target=3D"_blank">pete@petertodd.org</a>> wrote:<br type=3D"a=
ttribution"><blockquote class=3D"m_8307327310890922742m_8560565873969694775=
quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1=
ex"><div class=3D"m_8307327310890922742m_8560565873969694775elided-text">On=
Mon, May 22, 2017 at 06:32:38PM -0400, Russell O'Connor wrote:<br>
> On May 22, 2017 23:05, "Peter Todd" <<a href=3D"mailto:pe=
te@petertodd.org" target=3D"_blank">pete@petertodd.org</a>> wrote:<br>
><br>
> On Mon, May 22, 2017 at 03:05:49AM -0400, Russell O'Connor via bit=
coin-dev<br>
> wrote:<br>
> >=C2=A0 =C2=A0 =C2=A0MerkleRoot :=3D SHA256(SHA256(LeftRoot =E2=8B=
=85 RightRoot))<br>
> >=C2=A0 =C2=A0 =C2=A0sha256Compress : Word256 =C3=97 Word512 -> =
Word256<br>
><br>
> To be clear, what math operations do you mean by "=E2=8B=85"=
and "=C3=97"?<br>
><br>
><br>
> By "=E2=8B=85", I usually mean concatenation (though I also =
use it for function<br>
> composition in one instance).=C2=A0 =C2=A0By "=C3=97", I mea=
n the Cartesian product.<br>
<br>
</div>Cartesian product can mean a lot of things.<br>
<br>
What specifically do you mean by "cartesian product" here?</block=
quote></div></div></div></div></div></blockquote></div></div></div><div dir=
=3D"auto"><br></div><div dir=3D"auto">Oops, I forgot to reply all.=C2=A0 Be=
low is my reply.</div><div dir=3D"auto"><br></div><div dir=3D"auto"><div cl=
ass=3D"gmail_extra"><div class=3D"gmail_quote"><blockquote class=3D"m_83073=
27310890922742quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;=
padding-left:1ex"><div dir=3D"auto"><div dir=3D"auto">Given two types A and=
B, then A=C2=A0<span style=3D"font-family:sans-serif">=C3=97 B is the type=
of pairs of A and B in the sense of type theory as used in Standard ML or =
Haskell or other typed languages.</span></div></div></blockquote></div></di=
v></div><div dir=3D"auto"><br></div><div dir=3D"auto">To follow up, by &quo=
t;<span style=3D"font-family:sans-serif">sha256Compress : Word256 =C3=97 Wo=
rd512 -> Word256" I mean that sha256Compress is a function that tak=
es two arguments, the first being a 256 bit word and the second being a 512=
bit word, and returns a 256 bit word (or equivalently sha256Compress is a =
function that takes a pair as input, the first component being a 256 bit wo=
rd and the second component being a 512 bit word, and returns a 256 bit wor=
d).</span></div><div dir=3D"auto"><span style=3D"font-family:sans-serif"><b=
r></span></div><div dir=3D"auto"><font face=3D"sans-serif">sha256Compress i=
s meant to be the compression function defined by the SHA256 standard, thou=
gh nothing here depends on anything more that its type signature.</font></d=
iv></div>
--001a114c1e92cc98da055088ac4d--
|
