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
|
Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193]
helo=mx.sourceforge.net)
by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <socrates1024@gmail.com>) id 1Sh1a1-0000Ro-JA
for Bitcoin-development@lists.sourceforge.net;
Tue, 19 Jun 2012 16:47:01 +0000
Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of gmail.com
designates 74.125.82.175 as permitted sender)
client-ip=74.125.82.175; envelope-from=socrates1024@gmail.com;
helo=mail-we0-f175.google.com;
Received: from mail-we0-f175.google.com ([74.125.82.175])
by sog-mx-3.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1Sh1Zy-0004Af-F9
for Bitcoin-development@lists.sourceforge.net;
Tue, 19 Jun 2012 16:47:01 +0000
Received: by werg55 with SMTP id g55so5216936wer.34
for <Bitcoin-development@lists.sourceforge.net>;
Tue, 19 Jun 2012 09:46:52 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.180.94.4 with SMTP id cy4mr4901249wib.2.1340124412181; Tue, 19
Jun 2012 09:46:52 -0700 (PDT)
Sender: socrates1024@gmail.com
Received: by 10.217.2.207 with HTTP; Tue, 19 Jun 2012 09:46:52 -0700 (PDT)
Date: Tue, 19 Jun 2012 12:46:52 -0400
X-Google-Sender-Auth: xRkqSG3FKtSodSxG-I6fV-SpS24
Message-ID: <CAF7tpEyEWCbcB+jSpWOMyeZUBjQ=FbVEC8kLt3j2Yzv3YJOgiA@mail.gmail.com>
From: Andrew Miller <amiller@cs.ucf.edu>
To: Bitcoin-development@lists.sourceforge.net
Content-Type: text/plain; charset=ISO-8859-1
X-Spam-Score: -1.2 (-)
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 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
(socrates1024[at]gmail.com)
-0.0 SPF_PASS SPF: sender matches SPF record
0.2 FREEMAIL_ENVFROM_END_DIGIT Envelope-from freemail username ends in
digit (socrates1024[at]gmail.com)
0.1 DKIM_SIGNED Message has a DKIM or DK signature,
not necessarily valid
-0.1 DKIM_VALID Message has at least one valid DKIM or DK signature
X-Headers-End: 1Sh1Zy-0004Af-F9
Subject: Re: [Bitcoin-development] Ultimate Blockchain Compression w/
trust-free lite node
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: Tue, 19 Jun 2012 16:47:01 -0000
> Peter Todd wrote:
> My solution was to simply state that vertexes that happened to cause the
> tree to be unbalanced would be discarded, and set the depth of inbalance
> such that this would be extremely unlikely to happen by accident. I'd
> rather see someone come up with something better though.
Here is a simpler solution. (most of this message repeats the content
of my reply to the forum)
Suppose we were talking about a binary search tree, rather than a
Merkle tree. It's important to balance a binary search tree, so that
the worst-case maximum length from the root to a leaf is bounded by
O(log N). AVL trees were the original algorithm to do this, Red-Black
trees are also popular, and there are many similar methods. All
involve storing some form of 'balancing metadata' at each node. In a
RedBlack tree, this is a single bit (red or black). Every operation on
these trees, including search, inserting, deleting, and rebalancing,
requires a worst-case effort of O(log N).
Any (acyclic) recursive data structure can be Merkle-ized, simply by
adding a hash of the child node alongside each link/pointer. This way,
you can verify the data for each node very naturally, as you traverse
the structure.
In fact, as long as a lite-client knows the O(1) root hash, the rest
of the storage burden can be delegated to an untrusted helper server.
Suppose a lite-client wants to insert and rebalance its tree. This
requires accessing at most O(log N) nodes. The client can request only
the data relevant to these nodes, and it knows the hash for each chunk
of data in advance of accessing it. After computing the updated root
hash, the client can even discard the data it processed.
This technique has been well discussed in the academic literature,
e.g. [1,2], although since I am not aware of any existing
implementation, I made my own, intended as an explanatory aid:
https://github.com/amiller/redblackmerkle/blob/master/redblack.py
[1] Certificate Revocation and Update
Naor and Nissim. 1998
http://static.usenix.org/publications/library/proceedings/sec98/full_papers/nissim/nissim.pdf
[2] A General Model for Authenticated Data Structures
Martel, Nuckolls, Devanbu, Michael Gertz, Kwong, Stubblebine. 2004
http://truthsayer.cs.ucdavis.edu/algorithmica.pdf
--
Andrew Miller
|
