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
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
|
Return-Path: <pete@petertodd.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 2824E94F
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 07:23:16 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from outmail148098.authsmtp.com (outmail148098.authsmtp.com
[62.13.148.98])
by smtp1.linuxfoundation.org (Postfix) with ESMTP id 13AC314C
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 07:23:14 +0000 (UTC)
Received: from mail-c232.authsmtp.com (mail-c232.authsmtp.com [62.13.128.232])
by punt21.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v1N7NDgo038055
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 07:23:13 GMT
Received: from petertodd.org (ec2-52-5-185-120.compute-1.amazonaws.com
[52.5.185.120]) (authenticated bits=0)
by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v1N7NB6o090555
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO)
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 07:23:12 GMT
Received: from [127.0.0.1] (localhost [127.0.0.1])
by petertodd.org (Postfix) with ESMTPSA id D7BD940123
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 07:23:10 +0000 (UTC)
Received: by localhost (Postfix, from userid 1000)
id 115DA20245; Thu, 23 Feb 2017 02:23:10 -0500 (EST)
Date: Thu, 23 Feb 2017 02:23:10 -0500
From: Peter Todd <pete@petertodd.org>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20170223072310.GA3122@savin.petertodd.org>
References: <20170223011147.GB905@savin.petertodd.org>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="17pEHd4RhPHOinZp"
Content-Disposition: inline
In-Reply-To: <20170223011147.GB905@savin.petertodd.org>
User-Agent: Mutt/1.5.23 (2014-03-12)
X-Server-Quench: ef2585af-f998-11e6-829f-00151795d556
X-AuthReport-Spam: If SPAM / abuse - report it at:
http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVJwpGK10IU0Fd
P1hyKltILEZaQVBf Ri5dBBEKBAw1ADwr dVUTOktfYVU4Cld1
UkhIRUJSEw9qAhYA BFAbUAd3aQROfWBx Z0Z9XHVEXQo8dDh6
PDxSSm0PZWJlbS4X UEhfOVYCcgZCe04T dwZ2XXsQYGRSYGdo
RV49emhpZGgGd3UI TlxQc0QoTBRDLTQ9 WxsFHDNqEUAbcm0P
HztuIVkZGUcNN0g0 LUBpVVVQNRgOQgtT Ek0FCWdCIFcdAiQs
FwASQUlWGjA/CTpH DxM1Jne4
X-Authentic-SMTP: 61633532353630.1037:706
X-AuthFastPath: 0 (Was 255)
X-AuthSMTP-Origin: 52.5.185.120/25
X-AuthVirus-Status: No virus detected - but ensure you scan with your own
anti-virus system.
X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_LOW
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] TXO commitments do not need a soft-fork to be
useful
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, 23 Feb 2017 07:23:16 -0000
--17pEHd4RhPHOinZp
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
On Wed, Feb 22, 2017 at 08:11:47PM -0500, Peter Todd via bitcoin-dev wrote:
> 5) By *not* committing the TXO commitment in the block itself, we obsolet=
e my
> concept of delayed TXO commitments: you don't need to have calculated the=
TXO
> commitment digest to validate a block anyway!
Thinking about this a bit more, by not being forced to calculate a TXO
commitment for every block, we may be able to do significantly better than
delayed TXO commitments by lazily hashing.
Suppose we have the following perfect merkle tree, which we're using as a
key-value map. We'll represent inner nodes for which we've calculated diges=
ts
with "0"'s to represent what version of the tree they correspond too:
0
/ \
/ \
/ \
/ \
/ \
0 0
/ \ / \
/ \ / \
0 0 0 0
/ \ / \ / \ / \
a b c d e f g h
If a value is updated, digests above it become out of date and need to be
recalculated:
1
/ \
/ \
/ \
/ \
/ \
0 1
/ \ / \
/ \ / \
0 0 0 1
/ \ / \ / \ / \
a b c d e f g H
2
/ \
/ \
/ \
/ \
/ \
0 2
/ \ / \
/ \ / \
0 0 2 1
/ \ / \ / \ / \
A b c d e F g H
3
/ \
/ \
/ \
/ \
/ \
0 3
/ \ / \
/ \ / \
0 0 2 3
/ \ / \ / \ / \
a b c d e F G H
Suppose however that your implementation does lazy hashing; after the 3rd
update your state will be:
.
/ \
/ \
/ \
/ \
/ \
0 .
/ \ / \
/ \ / \
0 0 . .
/ \ / \ / \ / \
a b c d e F G H
Basically all the digests on the right side is out of date and need to be
recalculated. Now, first of all it's obviously possible for your implementa=
tion
to keep updating values in the tree given their keys - you've essentially
regressed to a bog standard binary tree.
But what happens if you discard part of your dataset? Let's suppose you've
discarded the left half:
.
/ \
/ \
/ \
/ \
/ \
0 .
/ \
/ \
. .
/ \ / \
e F G H
Note how you still have sufficient information to calculate the current mer=
kle
tip commitment: the left side hasn't changed yet. But what happens when som=
eone
gives you an update proof? Specifically, suppose they want to change b -> B.
That requires them to provide you with the part of the merkle tree proving =
that
position #1 is b. Now you might think that's this data:
3
/ \
/ \
/ \
/ \
/ \
0 3
/ \
/ \
0 0
/ \
a b
But the inner node digests marked "3" are useless to you: you haven't
calculated those digests yet so you can't compare them to anything. What you
can compare is the following:
0
/ \
/ \
0 0
/ \
a b
With that extra data your local knowledge is now:
.
/ \
/ \
/ \
/ \
/ \
0 .
/ \ / \
/ \ / \
0 0 . .
/ \ / \ / \
a b e F G H
Allowing you to apply the update:
.
/ \
/ \
/ \
/ \
/ \
. .
/ \ / \
/ \ / \
. 0 . .
/ \ / \ / \
a B e F G H
If you want to again prune that data, simply recalculate the digests so you
can verify a copy given to you by a peer in the future:
.
/ \
/ \
/ \
/ \
/ \
4 .
/ \ / \
/ \ / \
4 0 . .
/ \ / \ / \
a B e F G H
And prune, leaving you with:
.
/ \
/ \
/ \
/ \
/ \
4 .
/ \
/ \
. .
/ \ / \
e F G H
So tl;dr: the reason this works is that we can substitute commitments for
pointers: our merkle tree can also be viewed as a binary tree. So a reasona=
ble
real-world implementation would be to delay computation of digests for anyt=
hing
we have in RAM, and only compute digests as in-RAM data is flushed to disk.
Equally, on disk we can use standard time-space tradeoffs to only store a
subset of the digests, recalculating the rest on the fly. Given that'd we c=
ould
effectively combine both a cryptographic data structure and a standard
pointer-based data structure in one, I suspect we can get good performance =
out
of this.
The main subtlety of this approach will be how exactly to handle the proofs:
the level of verification possible depends on what digests a given node has
calculated, and we want to avoid making network splitting attacks possible =
by
attackers deliberately giving nodes proofs with upper digests that are
incorrect, something only some nodes can detect. Not sure yet exactly what's
the right approach there.
Finally, notice how this entire approach depends on schemes like MMR's where
the overall structure of the tree does not change as nodes are added and
updated; it would be much harder to implement this idea for something like a
merklized red-black tree where the structure changes as the tree is rebalan=
ced.
--=20
https://petertodd.org 'peter'[:-1]@petertodd.org
--17pEHd4RhPHOinZp
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
-----BEGIN PGP SIGNATURE-----
iQEcBAEBCAAGBQJYro3ZAAoJECSBQD2l8JH7JgMH/RA54bEamAkLnuFrfMwU4W8T
0V9PvFPx1H3Lb6a4aT+Hqzui+llIqRtP8gEdPd4pQneZcFoui2hIwh8UEkoEZLHj
MI7Gd0bKTWxlAJHRwEoLPi0w+jrLfFHsBVMecvscfLvOHVQokT1NZDZ4OogP30NG
DxWEttho1hFJWwZnrCrlzhm7lKBnDGtOn30IiQjQKLAWAat5aExp9Y+Whi/pEDiY
zUyOEZVxMjEaJuAgz+IAbNiZFiLBOCuXqElNJtrToml2psv2PVgQxQc1oTmxZCuO
4J0VwRgOnW8Vsrtwxix5MdDEdOcW81aIc9bCFazS3xfQR+GSwFqEwx9Ct1cziVE=
=1cic
-----END PGP SIGNATURE-----
--17pEHd4RhPHOinZp--
|
