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
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
|
Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191]
helo=mx.sourceforge.net)
by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <thomasv1@gmx.de>) id 1VzsgD-0003TT-AL
for bitcoin-development@lists.sourceforge.net;
Sun, 05 Jan 2014 18:44:09 +0000
Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of gmx.de
designates 212.227.15.18 as permitted sender)
client-ip=212.227.15.18; envelope-from=thomasv1@gmx.de;
helo=mout.gmx.net;
Received: from mout.gmx.net ([212.227.15.18])
by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:AES128-SHA:128)
(Exim 4.76) id 1VzsgA-0006GU-Py
for bitcoin-development@lists.sourceforge.net;
Sun, 05 Jan 2014 18:44:09 +0000
Received: from [192.168.1.27] ([86.73.30.122]) by mail.gmx.com (mrgmx101) with
ESMTPSA (Nemesis) id 0MDV5t-1WBguI3RC1-00Gu66 for
<bitcoin-development@lists.sourceforge.net>;
Sun, 05 Jan 2014 19:44:00 +0100
Message-ID: <52C9A7EE.2050904@gmx.de>
Date: Sun, 05 Jan 2014 19:43:58 +0100
From: Thomas Voegtlin <thomasv1@gmx.de>
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
rv:24.0) Gecko/20100101 Thunderbird/24.2.0
MIME-Version: 1.0
To: bitcoin-development@lists.sourceforge.net
References: <52B3A1C8.5000005@monetize.io>
In-Reply-To: <52B3A1C8.5000005@monetize.io>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Provags-ID: V03:K0:0QarU1l91rWsXxP5jamUH1dnsRr1OoFdMslobPEHFVxL+ZbeqOG
RXDHLfYnbbrEesxHFqrerOcpsew2CQkmRmz5qsaA0wv1+DWXnNIVNL1yFZVB3UocVf6l5wu
7qQ4sRz7qU7Qmasw9NSKtPgBVdSydqw8d83OnA5xBzJNUJ0ci9yTomQbEJL/aMbVBeqbHeL
72nQ+YkjI+9DuBNFNzfSg==
X-Spam-Score: -1.2 (-)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at http://www.dnswl.org/,
no trust [212.227.15.18 listed in list.dnswl.org]
-1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
sender-domain
0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
(thomasv1[at]gmx.de)
-0.0 SPF_PASS SPF: sender matches SPF record
0.2 FREEMAIL_ENVFROM_END_DIGIT Envelope-from freemail username ends in
digit (thomasv1[at]gmx.de)
X-Headers-End: 1VzsgA-0006GU-Py
Subject: Re: [Bitcoin-development] BIP proposal: Authenticated prefix trees
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: Sun, 05 Jan 2014 18:44:09 -0000
Hello and happy new year to this mailing list!
Thank you Mark for the incredible work you've been doing on this.
I am following this very closely, because it is of primary importance
for Electrum.
I have written a Python-levelDB implementation of this UTXO hashtree,
which is currently being tested, and will be added to Electrum servers.
My implementation follows Alan Reiner's idea to store the tree as items
in a key-value database. I believe that a C++ implementation like yours
will be at least an order of magnitude faster, and I am looking forward
to it.
I too believe that BIPs should define interoperability points, but probably
not implementation details. For the UTXO hashtree, this means that a BIP
should at least specify how the root hash is constructed. This might be the
only thing that needs to be specified.
However, I see no pressing issue with writing a BIP; it might be preferable
to implement and test different options first, and learn from that.
Thomas
Le 20/12/2013 02:47, Mark Friedenbach a écrit :
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Hello fellow bitcoin developers. Included below is the first draft of
> a BIP for a new Merkle-compressed data structure. The need for this
> data structure arose out of the misnamed "Ultimate blockchain
> compression" project, but it has since been recognized to have many
> other applications.
>
> In addition to this BIP I am preparing three additional BIPs
> describing the use of this data structure in stateless validation &
> mining, the UBC address index for "SPV+" operating modes, document
> timestamping and merged mining.
>
> A Python implementation of this data structure is available here:
>
> https://github.com/monetizeio/python-bitcoin
>
> A C++ implementation is being worked on.
>
> As per the BIP-1 procedure, I am submitting this rough draft to the
> community for discussion. I welcome all comments and criticisms of
> both form and content.
>
> - -Mark
>
>
> ==Abstract==
>
> This BIP describes a [http://en.wikipedia.org/wiki/Hash_tree Merkle
> hash tree] variant of the [http://en.wikipedia.org/wiki/Trie
> prefix-tree data structure], ideally suited for encoding key-value
> indices which support memory-efficient proofs.
>
> ==Motivation==
>
> There are a number of applications which would benefit from having a
> data structure with the following properties:
>
> * '''Arbitrary mapping of keys to values.''' A ''key'' can be any
> bytestring, and its ''value'' any other bytestring.
> * '''Duplicate keys disallowed.''' Every key has one, and only one
> value associated with it. Some applications demand assurance that no
> key value is reused, and that this constraint can be checked without
> requiring access to the entire data structure.
> * '''Efficient look-up by key.''' The data structure should support
> sub-linear lookup operations with respect to the number of keys in the
> mapping. Logarithmic time or linear with respect to the length of the
> key should be achievable and would be sufficient for realistic
> applications.
> * '''Merkle compression of mapping structure.''' It should be possible
> to produce a reduced description of the tree consisting of a single
> root hash value which is deterministically calculated from the mapping
> structure.
> * '''Efficient proofs of inclusion.''' It should be possible to
> extract a proof of key/value mapping which is limited in size and
> verification time by the length of the key in the worst case.
> * '''Computation of updates using local information.''' Given a set of
> inclusion proofs, it should be possible to calculate adjustments to
> the local mapping structure (update or deletion of included mappings,
> or insertion between two included mappings which are adjacent in the
> global structure).
>
> Such applications include committed validation indices which enable
> stateless mining nodes, committed wallet indices which enable
> trust-less querying of the unspent transaction output set by
> <code>scriptPubKey</code>, efficient document time-stamping, and
> secure & efficient merged mining. This BIP describes an authenticated
> prefix tree which has the above properties, but leaves the myriad
> applications to be formalized in future BIPs.
>
> ==Data structure==
>
> This BIP defines a binary prefix tree. Such a structure provides a
> mapping of bitstrings (the ''keys'') to bytestrings (the ''values'').
> It is an acyclic binary tree which implicitly encodes keys within the
> traversal path -- a "left" branch is a 0, and a "right" branch is a 1.
> Each node is reachable by only one unique path, and reading off the
> branches taken (0 for each left, 1 for each right) as one follows the
> path from root to target yields the node's key.
>
> The particular binary prefix tree defined by this BIP is a hybrid
> PATRICIA / de la Brandais tree structure.
> [http://en.wikipedia.org/wiki/Radix_tree PATRICIA trees] compress a
> long sequence of non-branching nodes into a single interior node with
> a per-branch ''skip prefix''. This achieves significant savings in
> storage space, root hash calculation, and traversal time.
>
> A de la Brandais trie achieves compression by only storing branches
> actually taken in a node. The space savings are minimal for a binary
> tree, but place the serialized size of a non-branching interior node
> under the SHA-256 block size, thereby reducing the number of hash
> operations required to perform updates and validate proofs.
>
> This BIP describes the authenticated prefix tree and its many
> variations in terms of its serialized representation. Additional BIPs
> describe the application of authenticated prefix trees to such
> applications as committed indices, document time-stamping, and merged
> mining.
>
> ==Serialization format==
>
> As a hierarchical structure, the serialization of an entire tree is
> the serialization of its root node. A serialized node is the
> concatenation of five structures:
>
> node := flags || VARCHAR(extra) || value || left || right
>
> The <code>flags</code> is a single byte field whose composite values
> determine the bytes that follow.
>
> flags = (left_flags << 0) |
> (right_flags << 2) |
> (has_value << 4) |
> (prune_left << 5) |
> (prune_right << 6) |
> (prune_value << 7)
>
> The <code>left_flags</code> and <code>right_flags</code> are special
> 2-bit enumeration fields. A value of 0 indicates that the node does
> not branch in this direction, and the corresponding <code>left</code>
> or <code>right</code> branch is missing (replaced with the empty
> string in the node serialization). A value of 1 indicates a single bit
> key prefix for this branch, implicitly 0 for <code>left</code> and 1
> for <code>right</code>. A 2 indicates up to 7 bits of additional skip
> prefix (beyond the implicit first bit, making 8 bits total) are stored
> in a compact single-byte format. A 3 indicates a skip prefix with
> greater than 7 additional bits, stored length-prefix encoded.
>
> The single bit <code>has_value</code> indicates whether the node
> stores a data bytestring, the value associated with its key prefix.
> Since keys may be any value or length, including one key being a
> prefix of another, it is possible for interior nodes in addition to
> leaf nodes to have values associated with them, and therefore an
> explicit value-existence bit is required.
>
> The remaining three bits are used for proof extraction, and are masked
> away prior to hash operations. <code>prune_left</code> indicates that
> the entire left branch has been pruned. <code>prune_right</code> has
> similar meaning for the right branch. If <code>has_value</code> is
> set, <code>prune_value</code> may be set to exclude the node's value
> from encoded proof. This is necessary field for interior nodes, since
> it is possible that their values may be pruned while their children
> are not.
>
> The <code>value</code> field is only present if the bit
> <code>flags.has_value</code> is set, in which case it is a
> <code>VARCHAR</code> bytestring:
>
> switch flags.has_value:
> case 0:
> value := ε
> case 1:
> value := VARCHAR(node.value)
>
> The <code>extra</code> field is always present, and takes on a
> bytestring value defined by the particular application. Use of the
> <code>extra</code> field is application dependent, and will not be
> covered in this specification. It can be set to the empty bytestring
> (serialized as a single zero byte) if the application has no use for
> the <code>extra</code> field.
>
> value := VARCHAR(calculate_extra(node))
>
> The <code>left</code> and <code>right</code> non-terminals are only
> present if the corresponding <code>flags.left_flags</code> or
> <code>flags.right_flags</code> are non-zero. The format depends on the
> value of this flags setting:
>
> switch branch_flags:
> case 0:
> branch := ε
> case 1:
> branch := branch_node_or_hash
> case 2:
> prefix = prefix >> 1
> branch := int_to_byte(1 << len(prefix) | bits_to_int(prefix)) ||
> branch_node_or_hash
> case 3:
> prefix = prefix >> 1
> branch := VARINT(len(prefix) - 9) ||
> bits_to_string(prefix) ||
> branch_node_or_hash
>
> <code>branch_flags</code> is a stand-in meant to describe either
> <code>left_flags</code> or <code>right_flags</code>, and likewise
> everywhere else in the above pseudocode <code>branch</code> can be
> replaced with either <code>left</code> or <code>right</code>.
>
> <code>prefix</code> is the key bits between the current node and the
> next branching, terminal, and/or leaf node, including the implicit
> leading bit for the branch (0 for the left branch, 1 for the right
> branch). In the above code, <code>len(prefix)</code> returns the
> number of bits in the bitstring, and <code>prefix >> 1</code> drops
> the first bit reducing the size of the bitstring by one and
> renumbering the indices accordingly.
>
> The function <code>int_to_byte</code> takes an integer in the range
> [0, 255] and returns the octet representing that value. This is a NOP
> in many languages, but present in this pseudocode so as to be explicit
> about what is going on.
>
> The function <code>bits_to_int</code> interprets a sequence of bits as
> a little-endian integer value. This is analogous to the following
> pseudocode:
>
> def bits_to_int(bits):
> result = 0
> for idx in 1..len(bits):
> if bits[idx] == 1:
> result |= 1<<idx
>
> The function <code>bits_to_string</code> serializes a sequence of bits
> into a binary string. It uses little-endian bit and byte order, as
> demonstrated by the following pseudocode:
>
> def bits_to_string(bits):
> bytes = [0] * ceil(len(bits) / 8)
> for idx in 1..len(bits):
> if bits[idx] == 1:
> bytes[idx / 8] |= 1 << idx % 8
> return map(int_to_byte, bytes)
>
> <code>branch_node_or_hash</code> is either the serialized child node
> or its SHA-256 hash and associated meta-data. Context determines which
> value to use: during digest calculations, disk/database serialization,
> and when the branch is pruned the hash value is used and serialized in
> the same way as other SHA-256 values in the bitcoin protocol (note
> however that it is single-SHA-256, not the double-SHA-256 more
> commonly used in bitcoin). The number of terminal (value-containing)
> nodes and the serialized size in bytes of the fully unpruned branch
> are suffixed to the branch hash. When serializing a proof or
> snapshotting tree state and the branch is not pruned, the serialized
> child node is included directly and the count and size are omitted as
> they can be derived from the serialization.
>
> if branch_pruned or SER_HASH:
> branch_node_or_hash := SHA-256(branch) ||
> count(branch) ||
> size(branch)
> else:
> branch_node_or_hash := serialize(branch)
>
> As an example, here is the serialization of a prefix tree mapping the
> names men and women of science to the year of their greatest publication:
>
> >>> dict = AuthTree()
> >>> dict['Curie'] = VARINT(1898)
> >>> dict('Einstein') = VARINT(1905)
> >>> dict['Fleming'] = VARINT(1928)
> >>> dict['中本'] = VARINT(2009)
> >>> dict.serialize()
> # An bytestring, broken out into parts:
>
> # . Root node:
> 0x0e # left_flags: 2, right_flags: 3, has_value: 1
> 0x00 # extra: ε
>
> # .l Inner node: 0b01000
> 0x11 # 0b01000
> 0x07 # left_flags: 3, right_flags: 1
> 0x00 # extra: ε
>
> # .l.l Inner node: 0b01000011 0b01110101 0b01110010 0b01101001
> # 'C' 'u' 'r' 'i'
> # 0b01100101
> # 'e'
> 0x1abb3a599a02 # 0b01101110101011100100110100101100101
> 0x10 # has_value: 1
> 0x00 # extra: ε
> 0x03fd6a07 # value: VARINT(1911)
>
> # .l.r Inner node: 0b010001
> 0x0f # left_flags: 3, right_flags: 3
> 0x00 # extra: ε
>
> # .l.r.l Inner node: 0b01000101 0b01101001 0b01101110 0b01110011
> # 'E' 'i' 'n' 's'
> # 0b01110100 0b01100101 0b01101001 0b01101110
> # 't' 'e' 'i' 'n'
> 0x312ded9c5d4c2ded00 # 0b1011010010110111
> # 0b0011100110111010
> # 0b0011001010110100
> # 0b101101110
> 0x10 # has_value: 1
> 0x00 # extra: ε
> 0x03fd7107 # value: VARINT(1905)
>
> # .l.r.r Inner node: 0b01000110 0b01101100 0b01100101 0b01101101
> # 'F' 'l' 'e' 'm'
> # 0b01101001 0b01101110 0b01100111
> # 'i' 'n' 'g'
> 0x296c4c6d2dedcc01 # 0b0011011000110010
> # 0b1011011010110100
> # 0b10110111001100111
> 0x10 # has_value: 1
> 0x00 # extra: ε
> 0x03fd8807 # value: VARINT(1928)
>
> # .r Inner node: 0b11100100 0b10111000 0b10101101
> # '中'
> # 0b11100110 0b10011100 0b10101100
> # '本'
> 0x27938edab39c1a # 0b1100100101110001
> # 0b0101101111001101
> # 0b001110010101100
> 0x10 # has_value: 1
> 0x00 # extra: ε
> 0x03fdd907 # value: VARINT(2009)
>
> ==Hashing==
>
> There are two variations of the authenticated prefix tree presented in
> this draft BIP. They differ only in the way in which hash values of a
> node and its left/right branches are constructed. The variations,
> discussed below, tradeoff computational resources for the ability to
> compose operational proofs. Whether the performance hit is
> significant, and whether or not the added features are worth the
> tradeoff depends very much on the application.
>
> ===Variation 1: Level-compressed hashing===
>
> In this variation the referenced child node's hash is used in
> construction of an interior node's hash digest. The interior node is
> serialized just as described (using the child node's digest instead of
> inline serialization), the resulting bytestring is passed through one
> round of SHA-256, and the digest that comes out of that is the hash
> value of the node. This is very efficient to calculate, requiring the
> absolute minimum number of SHA-256 hash operations, and achieving
> level-compression of computational resources in addition to reduction
> of space usage.
>
> For example:
>
> >>> dict = AuthTree()
> >>> dict['a'] = 0xff
> >>> dict.serialize()
> 0x0200c3100001ff
> >>> dict.root
> AuthTreeNode(
> left_prefix = 0b01100001,
> left_hash =
> 0xbafa0e2bba3396c5e9804b6cbe61be82bc442c1121aed81f8d5de36e9b20dc2f,
> left_count = 1,
> left_size = 4)
> >>> dict.hash
> 0xb4837376022a7c9ddaa7d685ad183bcbd5d16c362b81fa293a7b9e911766cf3c
>
> Assuming uniform distribution of key values, level-compressed hashing
> has time-complexity logarithmic with respect to the number of keys in
> the prefix tree. The disadvantage is that it is not possible in
> general to "rebase" an operational proof on top of a sibling,
> particularly if that sibling deletes branches that result in
> reorganization and level compression of internal nodes used by the
> rebased proof.
>
> ===Variation 2: Proof-updatable hashing===
>
> In this variation, level-compressed branches are expanded into a
> series of chained single-branch internal nodes, each including the
> hash of its direct child. For a brach with a prefix N bits in length,
> this requires N chained hashes. Thanks to node-compression (excluding
> empty branches from the serialization), it is possible for each hash
> operation + padding to fit within a single SHA-256 block.
>
> Note that the serialization semantics are unchanged! The variation
> only changes the procedure for calculating the hash values of interior
> nodes. The serialization format remains the same (modulo differing
> hash values standing in for pruned branches).
>
> Using the above example, calling <code>dict.hash</code> causes the
> following internal nodes to be constructed:
>
> >>> node1 = AuthTreeNode(
> right_prefix = 0b1,
> right_hash =
> 0xbafa0e2bba3396c5e9804b6cbe61be82bc442c1121aed81f8d5de36e9b20dc2f,
> right_count = 1,
> right_size = 4)
> >>> node2 = AuthTreeNode( left_prefix=0b0, left_hash=node1.hash,
> left_count=1, left_size=4)
> >>> node3 = AuthTreeNode( left_prefix=0b0, left_hash=node2.hash,
> left_count=1, left_size=4)
> >>> node4 = AuthTreeNode( left_prefix=0b0, left_hash=node3.hash,
> left_count=1, left_size=4)
> >>> node5 = AuthTreeNode( left_prefix=0b0, left_hash=node4.hash,
> left_count=1, left_size=4)
> >>> node6 = AuthTreeNode(right_prefix=0b1, right_hash=node5.hash,
> right_count=1, right_size=4)
> >>> node7 = AuthTreeNode(right_prefix=0b1, right_hash=node6.hash,
> right_count=1, right_size=4)
> >>> node8 = AuthTreeNode( left_prefix=0b0, left_hash=node7.hash,
> left_count=1, left_size=4,
> value=0xff)
> >>> dict.hash == node8.hash
> True
> >>> dict.hash
> 0xc3a9328eff06662ed9ff8e82aa9cc094d05f70f0953828ea8c643c4679213895
>
> The advantage of proof-updatable hashing is that any operational proof
> may be "rebased" onto the tree resulting from a sibling proof, using
> only the information locally available in the proofs, even in the
> presence of deletion operations that result in level-compression of
> the serialized form. The disadvantage is performance: validating an
> updatable proof requires a number of hash operations lower-bounded by
> the length of the key in bits.
>
> ==Inclusion proofs==
>
> An inclusion proof is a prefix tree pruned to contain a subset of its
> keys. The serialization of an inclusion proof takes the following form:
>
> inclusion_proof := variant || root_hash || root_node || checksum
>
> Where <code>variant</code> is a single-byte value indicating the
> presence of level-compression (0 for proof-updatable hashing, 1 for
> level-compressed hashing). <code>root_hash</code> is the Merkle
> compression hash of the tree, the 32-byte SHA-256 hash of the root
> node. <code>tree</code> is the possibly pruned, serialized
> representation of the tree. And finally, <code>checksum</code> is the
> first 4 bytes of the SHA-256 checksum of <code>variant</code>,
> <code>root_hash</code>, and <code>root_node</code>.
>
> For ease of transport, the standard envelope for display of an
> inclusion proof is internet-standard base64 encoding in the following
> format:
>
> - -----BEGIN INCLUSION PROOF-----
> ATzPZheRnns6KfqBKzZs0dXLOxithdan2p18KgJ2c4O0DgARBwAauzpZmgIQAAP9agcPADEt7Zxd
> TC3tABAAA/1xBylsTG0t7cwBEAAD/YgHJ5OO2rOcGhAAA/3ZByEg+2g=
> - -----END INCLUSION PROOF-----
>
> Decoded, it looks like this:
>
> 0x01 # Level-compressed hashing
> # Merkle root:
> 0x3ccf6617919e7b3a29fa812b366cd1d5cb3b18ad85d6a7da9d7c2a02767383b4
> # Serialized tree (unpruned):
> 0x0e001107001abb3a599a02100003fd6a070f00312ded9c5d4c2ded00100003fd
> 0x7107296c4c6d2dedcc01100003fd880727938edab39c1a100003fdd907
> # Checksum:
> 0x2120fb68
>
> ==Operational proofs==
>
> An operational proof is a list of insert/update and delete operations
> suffixed to an inclusion proof which contains the pathways necessary
> to perform the specified operations. The inclusion proof must contain
> the key values to be updated or deleted, and the nearest adjacent key
> values for each insertion. The serialization of an operational proof
> takes the following form:
>
> operational_proof := variant || root_hash || tree ||
> VARLIST(delete*) || VARLIST(update*) ||
> new_hash || checksum
>
> delete := VARCHAR(key)
> update := VARCHAR(key) || VARCHAR(value)
>
> The first three fields, <code>variant</code>, <code>root_hash</code>,
> and <code>tree</code> are the inclusion proof, and take the same
> values described in the previous section. <code>deletes</code> is a
> list of key values to be deleted; each key value in this list must
> exist in the inclusion proof. <code>updates</code> is a list of key,
> value mappings which are to be inserted into the tree, possibly
> replacing any mapping for the key which already exists; either the key
> itself if it exists (update), or the two lexicographically closest
> keys on either side if it does not (insert) must be present in the
> insertion proof. <code>new_hash</code> is the resulting Merkle root
> after the insertion, updates, and deletes are performed, and
> <code>checksum</code> is the initial 4 bytes of the SHA-256 hash of
> the preceding fields.
>
> Just like inclusion proofs, an operational proof is encoded in base64
> for display and transport. Here's the same
>
> - -----BEGIN OPERATIONAL PROOF-----
> ATzPZheRnns6KfqBKzZs0dXLOxithdan2p18KgJ2c4O0LgARaIsVaQi/GdhOPOgA8p4Pu4PiEfEg
> lcmy3j7bOc7hXw0DLSeTjtqznBoQAAP92QcBMOS4reacrACzuZJbyP7fqIOf5VEk4iarG4+uPoZC
> oun8BztQMQBy0LHVeSY=
> - -----END OPERATIONAL PROOF-----
>
> Decoded and broken into its constituent fields:
>
> 0x01 # Level-compressed hashing
> # Original Merkle root:
> 0x3ccf6617919e7b3a29fa812b366cd1d5cb3b18ad85d6a7da9d7c2a02767383b4
> # Serialized tree (included keys: '中本'):
> 0x2e0011688b156908bf19d84e3ce800f29e0fbb83e211f12095c9b2de3edb39ce
> 0xe15f0d032d27938edab39c1a100003fdd907
> # Deletion list ['中本']:
> 0x01
> 0x30e4b8ade69cac
> # Insertion list []:
> 0x00
> # New Merkle root:
> 0xb3b9925bc8fedfa8839fe55124e226ab1b8fae3e8642a2e9fc073b50310072d0
> # Checksum:
> 0xb1d57926
>
> ~End of File~
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.14 (GNU/Linux)
> Comment: GPGTools - http://gpgtools.org
> Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/
>
> iQIcBAEBAgAGBQJSs6HIAAoJEAdzVfsmodw4gooQAJm7XNsZjgdeTSpKIvUIU38f
> tQx2FD08hQdLl48me5mDUbHJgGlYINsKAgoZ8Mqwi/kHEEYhuIlLIX1p6Ovigidb
> 21BiVoOLdG1egGOwxp17DuwYaDPTppFTlN9TBjZzW6WKc7+4aNvyc1KtrbHIhtj/
> 04ekFyAn4U5UH0ht7CI79j0u3Kp85p5D4PyYZB2m82mzti6OxpSM4tXlMkDW7ihg
> QJwiZSjzejqTd7WF0zr0SLeGVRSN2A0dzUCoVsI98eIa3hkw2N4ae6dRkibyStOT
> V8VEDvHArEDlvu8jiryajhsom5mvtOOclNDkVXWAf/Te4gj05iYdTIvNvDEJtqsP
> XDbmw6GgV1kBLlLo0mp//t/+wr+nIvy+sVAP+eqtM/0vjaVXBkXxkUMqqNkrtVpB
> f3whq7nFahssUMSoWE93jgob1ayAax2XUALVMAXYsJl7b2MqBGlhiTZ8FQZ+TW4A
> tIpKeUprPmDvA18rO3SCbmLMQryZqYiH0sRyvUc5kvn3qCRHrISZNkEuK591eS+x
> BO1eOluPzVqeXPPSK1jvGeY0FNJtwzbov4nI1mzOvzQHLCvkHn5PhUFCK5tL5tAe
> b0Z5qwDV+SvVs7W1R7ejYBzEj77U1zuzZ9AtikOuvy+bNGrkIlpI49EyXHijm7C3
> Q6JacTuI0PelYji2gaBJ
> =BbDs
> -----END PGP SIGNATURE-----
>
> ------------------------------------------------------------------------------
> Rapidly troubleshoot problems before they affect your business. Most IT
> organizations don't have a clear picture of how application performance
> affects their revenue. With AppDynamics, you get 100% visibility into your
> Java,.NET, & PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro!
> http://pubads.g.doubleclick.net/gampad/clk?id=84349831&iu=/4140/ostg.clktrk
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
|