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
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
|
Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194]
helo=mx.sourceforge.net)
by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from
<SRS0=nh6BJu=HM=godofgod.co.uk=matthewmitchell@eigbox.net>)
id 1TCDYW-0003PD-PE for bitcoin-development@lists.sourceforge.net;
Thu, 13 Sep 2012 17:50:24 +0000
Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of eigbox.net
designates 66.96.188.16 as permitted sender)
client-ip=66.96.188.16;
envelope-from=SRS0=nh6BJu=HM=godofgod.co.uk=matthewmitchell@eigbox.net;
helo=bosmailout16.eigbox.net;
Received: from bosmailout16.eigbox.net ([66.96.188.16])
by sog-mx-4.v43.ch3.sourceforge.com with esmtp (Exim 4.76)
id 1TCDYV-0005vp-Po for bitcoin-development@lists.sourceforge.net;
Thu, 13 Sep 2012 17:50:24 +0000
Received: from bosmailscan08.eigbox.net ([10.20.15.8])
by bosmailout16.eigbox.net with esmtp (Exim) id 1TCDYQ-0003lu-Hb
for bitcoin-development@lists.sourceforge.net;
Thu, 13 Sep 2012 13:50:18 -0400
Received: from bosimpout02.eigbox.net ([10.20.55.2])
by bosmailscan08.eigbox.net with esmtp (Exim)
id 1TCDYQ-00030U-13; Thu, 13 Sep 2012 13:50:18 -0400
Received: from bosauthsmtp11.eigbox.net ([10.20.18.11])
by bosimpout02.eigbox.net with NO UCE
id yhpv1j00J0EKspE01hpvqi; Thu, 13 Sep 2012 13:49:55 -0400
X-Authority-Analysis: v=2.0 cv=V8rKJ5bi c=1 sm=1
a=Vnyysazsc9gF4v5jbSvB8A==:17 a=Goz4v7xpImgA:10 a=JhU9KSwl1l8A:10
a=RmqW3wxksLsA:10 a=eGitJVp2AAAA:8 a=-aUnnjAAwhoA:10 a=pGLkceISAAAA:8
a=wqI5gXztqGSwXhhk5iEA:9 a=CjuIK1q_8ugA:10 a=MSl-tDqOz04A:10
a=HraHw9EmjoyJ3M4Frn0A:9 a=_W_S_7VecoQA:10
a=anyYG9rjTBM1sAjEBQ8Cew==:117
X-EN-OrigOutIP: 10.20.18.11
X-EN-IMPSID: yhpv1j00J0EKspE01hpvqi
Received: from [109.175.173.27]
by bosauthsmtp11.eigbox.net with esmtpsa (TLSv1:AES128-SHA:128)
(Exim) id 1TCDY2-0003n4-PP; Thu, 13 Sep 2012 13:49:55 -0400
From: Matthew Mitchell <matthewmitchell@godofgod.co.uk>
Content-Type: multipart/alternative;
boundary="Apple-Mail=_1431EAE0-F143-4154-BECE-76E80F9BB9D4"
Message-Id: <A1DC7DE8-F355-4B61-AF18-94F07DF6421E@godofgod.co.uk>
Mime-Version: 1.0 (Mac OS X Mail 6.0 \(1486\))
Date: Thu, 13 Sep 2012 18:49:49 +0100
References: <2104FC7F-0AE0-4C55-9987-B20EFCE19FC3@godofgod.co.uk>
<CAAS2fgSymOJ=cQnNwK9+nvRYszHHH4vtUpoQYWNNYoVaYB5Gpg@mail.gmail.com>
<19ED4257-0BCA-41C5-A533-B0AB9B500181@godofgod.co.uk>
<CAAS2fgRfXBrsFm_zdNFe7Z4FN7uQ5zSg++scng=hNrHZZV93VQ@mail.gmail.com>
<CANEZrP0HHhSXyN9pWODtTxHMfRB4B0w-eSdvNHH13WwLVgECrw@mail.gmail.com>
<FC0AF926-2CBD-49BA-A3B7-AF9D70A83CE4@godofgod.co.uk>
<CAAS2fgSd6t038Yzb-Vy34J61xob+kVqA8pK+w1+ZwJ6XtQRJww@mail.gmail.com>
<2B95CF41-4304-4D2A-9ABF-198D97B7449B@godofgod.co.uk>
<CAAS2fgQi8QFwU2M=wLiDodt3SmO48vUV5Sp3YCb1OmGJ5m=E7Q@mail.gmail.com>
To: Gregory Maxwell <gmaxwell@gmail.com>,
"bitcoin-development@lists.sourceforge.net"
<bitcoin-development@lists.sourceforge.net>
In-Reply-To: <CAAS2fgQi8QFwU2M=wLiDodt3SmO48vUV5Sp3YCb1OmGJ5m=E7Q@mail.gmail.com>
X-Mailer: Apple Mail (2.1486)
X-EN-UserInfo: c68a83c59c94ef03b40bb4bc312c51e4:dffc0a9b4c8a0435ad832ff5852cab82
X-EN-AuthUser: godofgod@godofgod.co.uk
Sender: Matthew Mitchell <matthewmitchell@godofgod.co.uk>
X-EN-OrigIP: 109.175.173.27
X-EN-OrigHost: unknown
X-Spam-Score: -0.7 (/)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
sender-domain
-0.0 SPF_PASS SPF: sender matches SPF record
-0.5 RP_MATCHES_RCVD Envelope sender domain matches handover relay
domain 1.0 HTML_MESSAGE BODY: HTML included in message
0.3 AWL AWL: From: address is in the auto white-list
X-Headers-End: 1TCDYV-0005vp-Po
Subject: Re: [Bitcoin-development] Segmented Block Relaying BIP draft.
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Thu, 13 Sep 2012 17:50:24 -0000
--Apple-Mail=_1431EAE0-F143-4154-BECE-76E80F9BB9D4
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
charset=us-ascii
On 13 Sep 2012, at 16:51, Gregory Maxwell <gmaxwell@gmail.com> wrote:
> I thoroughly understand the value of tree hashes. That wasn't what I
> was asking about.
>=20
> If you're validating a block you need all the transactions, once you
> have them or their hashes you can build the tree without transferring
> more, e.g. what a fully validating node needs. If you're checking a
> single transaction to need the path from the transaction to the root
> (what a SPV nodes need, for example).
>=20
> Can you spell out the 'end user'ish application for fetching a tree =
level?
A merkle tree root is found by hashing the two children together and =
those children are found the same way until you get to the greatest =
level down the tree. This means you can validate children as being =
correct as long as they hash together to form the root. This means you =
do not need all the transaction hashes to validate segments of the =
block, you only need the root hashes for all the segments you want. =
Let's say there are 8 transactions and you want to verify 4 segments (2 =
transactions each), The merkle tree looks like this (Might not work =
depending on the font):
Level 0: *
/ \
/ \
/ \
/ \
/ \
/ \
/ \
Level 1: * *
/ \ / \
/ \ / \
/ \ / \
Level 2: * * * *
/ \ / \ / \ / \
Level 3: * * * * * * * *
When you look at any non-leaf node you can see a separate merkle tree =
where the root can be found exactly the same as any other merkle tree. =
In this example you want four segments, so you ask for level 2. Now =
imagine a tree without level 3, you can validate the root with level 2. =
In fact you can validate that the root exists for any level. So you =
first check that the level 2 hashes do indeed calculate to the root. =
Once this is done you can now use these hashes to validate the segments. =
When you receive a segment, you check that segment against the segment's =
root. So you've validated the segment transactions for the segment root =
and the segment root was validated for the entire tree's root. You =
validate the segments for each segment root and this way you know all =
the transactions are valid for the four segments and thus are valid for =
the entire tree. This way you have downloaded 4 hashes instead of 8.=20
Downloading the transactions hashes are therefore not necessary only the =
level for the segment roots. You might for instance want to divide the =
block into two segments in which case you ask for level 1 and download 2 =
hashes.
I hope that made sense.
And yes the merkle tree is particularly useful for validating a single =
transaction exists in a block as that saves a large proportion of the =
data required. The redundant data removed in the proposal here is =
smaller as a proportion of the total data (Because most of the data is =
the actual transactions themselves), so you might argue it's not worth =
it but it's simple to implement.=
--Apple-Mail=_1431EAE0-F143-4154-BECE-76E80F9BB9D4
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
charset=us-ascii
<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html =
charset=3Dus-ascii"></head><body style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><font =
face=3D"Courier New"><br></font><div><div><font face=3D"Courier New">On =
13 Sep 2012, at 16:51, Gregory Maxwell <<a =
href=3D"mailto:gmaxwell@gmail.com">gmaxwell@gmail.com</a>> =
wrote:</font></div><font face=3D"Courier New"><br></font><blockquote =
type=3D"cite"><font face=3D"Courier New">I thoroughly understand the =
value of tree hashes. That wasn't what I<br>was asking about.<br><br>If =
you're validating a block you need all the transactions, once =
you<br>have them or their hashes you can build the tree without =
transferring<br>more, e.g. what a fully validating node needs. If you're =
checking a<br>single transaction to need the path from the transaction =
to the root<br>(what a SPV nodes need, for example).<br><br>Can you =
spell out the 'end user'ish application for fetching a tree =
level?<br></font></blockquote></div><font face=3D"Courier =
New"><br></font><div><font face=3D"Courier New">A merkle tree root is =
found by hashing the two children together and those children are found =
the same way until you get to the greatest level down the tree. This =
means you can validate children as being correct as long as they hash =
together to form the root. This means you do not need all the =
transaction hashes to validate segments of the block, you only need the =
root hashes for all the segments you want. Let's say there are 8 =
transactions and you want to verify 4 segments (2 transactions each), =
The merkle tree looks like this (Might not work depending on the =
font):</font></div><div><font face=3D"Courier =
New"><br></font></div><div><font face=3D"Courier New">Level 0: =
*</font></div><div><font =
face=3D"Courier New"> =
/ \</font></div><div><font face=3D"Courier =
New"> =
/ \</font></div><div><font face=3D"Courier =
New"> =
/ \</font></div><div><font face=3D"Courier =
New"> =
/ \</font></div><div><font face=3D"Courier =
New"> / =
\</font></div><div><font face=3D"Courier =
New"> / =
\</font></div><div><font =
face=3D"Courier New"> =
/ =
\</font></div><div><font face=3D"Courier New">Level 1: =
* =
*</font></div><div><font face=3D"Courier New"> =
/ \ =
/ \</font></div><div><font face=3D"Courier New"> =
/ \ =
/ \</font></div><div><font face=3D"Courier New"> =
/ \ =
/ \</font></div><div><font face=3D"Courier =
New">Level 2: * * * =
*</font></div><div><font face=3D"Courier =
New"> / \ </font><span =
style=3D"font-family: 'Courier New'; "> / \ =
</span><span style=3D"font-family: 'Courier New'; "> / \ =
</span><span style=3D"font-family: 'Courier New'; "> / =
\</span></div><div><font face=3D"Courier New">Level 3: * * =
</font><span style=3D"font-family: 'Courier New'; ">* =
* </span><font face=3D"Courier New">* * =
</font><span style=3D"font-family: 'Courier New'; ">* =
*</span></div><div><font face=3D"Courier =
New"><br></font></div><div><font face=3D"Courier New">When you look at =
any non-leaf node you can see a separate merkle tree where the =
root can be found exactly the same as any other merkle tree. =
In this example you want four segments, so you ask for level 2. Now =
imagine a tree without level 3, you can validate the root with level 2. =
In fact you can validate that the root exists for any level. =
So you first check that the level 2 hashes do =
indeed calculate to the root. Once this is done you can now =
use these hashes to validate the segments. When you receive a segment, =
you check that segment against the segment's root. So you've validated =
the segment transactions for the segment root and =
the segment root was validated for the entire tree's root. =
You validate the segments for each segment root and this way =
you know all the transactions are valid for the four segments and thus =
are valid for the entire tree. This way you have downloaded 4 =
hashes instead of 8. </font></div><div><font face=3D"Courier =
New"><br></font></div><div><font face=3D"Courier New">Downloading the =
transactions hashes are therefore not necessary only the level for the =
segment roots. You might for instance want to divide the block into two =
segments in which case you ask for level 1 and download 2 =
hashes.</font></div><div><font face=3D"Courier =
New"><br></font></div><div><font face=3D"Courier New">I hope that made =
sense.</font></div><div><font face=3D"Courier =
New"><br></font></div><div><font face=3D"Courier New">And yes the merkle =
tree is particularly useful for validating a single transaction exists =
in a block as that saves a large proportion of the data required. The =
redundant data removed in the proposal here is smaller as a proportion =
of the total data (Because most of the data is the actual transactions =
themselves), so you might argue it's not worth it but it's simple to =
implement.</font></div></body></html>=
--Apple-Mail=_1431EAE0-F143-4154-BECE-76E80F9BB9D4--
|
