summaryrefslogtreecommitdiff
path: root/6c/b5f68de6416d502cd65cddc4911ccdec2a064c
blob: 9fc2562b387594f41ee79b88188408ad0b9b4d51 (plain)
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
Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192]
	helo=mx.sourceforge.net)
	by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
	(envelope-from <etotheipi@gmail.com>) id 1Sh2v2-0001E0-8i
	for bitcoin-development@lists.sourceforge.net;
	Tue, 19 Jun 2012 18:12:48 +0000
Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmail.com
	designates 209.85.160.175 as permitted sender)
	client-ip=209.85.160.175; envelope-from=etotheipi@gmail.com;
	helo=mail-gh0-f175.google.com; 
Received: from mail-gh0-f175.google.com ([209.85.160.175])
	by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-MD5:128)
	(Exim 4.76) id 1Sh2v1-0007yl-J2
	for bitcoin-development@lists.sourceforge.net;
	Tue, 19 Jun 2012 18:12:48 +0000
Received: by ghbz2 with SMTP id z2so5055387ghb.34
	for <bitcoin-development@lists.sourceforge.net>;
	Tue, 19 Jun 2012 11:12:42 -0700 (PDT)
Received: by 10.236.75.3 with SMTP id y3mr24101641yhd.110.1340129562129;
	Tue, 19 Jun 2012 11:12:42 -0700 (PDT)
Received: from [192.168.1.85] (c-76-111-96-126.hsd1.md.comcast.net.
	[76.111.96.126])
	by mx.google.com with ESMTPS id y66sm82220136yhi.10.2012.06.19.11.12.41
	(version=SSLv3 cipher=OTHER); Tue, 19 Jun 2012 11:12:41 -0700 (PDT)
Message-ID: <4FE0C103.3070304@gmail.com>
Date: Tue, 19 Jun 2012 14:12:19 -0400
From: Alan Reiner <etotheipi@gmail.com>
User-Agent: Mozilla/5.0 (X11; Linux i686 on x86_64;
	rv:12.0) Gecko/20120428 Thunderbird/12.0.1
MIME-Version: 1.0
To: Gregory Maxwell <gmaxwell@gmail.com>
References: <CAF7tpEyEWCbcB+jSpWOMyeZUBjQ=FbVEC8kLt3j2Yzv3YJOgiA@mail.gmail.com>
	<4FE0B7EB.6000100@gmail.com>
	<CAAS2fgRFFtdsuaS+ZoFLYcnUxLBufA8aMV=_sHca5ZOi-3viTw@mail.gmail.com>
In-Reply-To: <CAAS2fgRFFtdsuaS+ZoFLYcnUxLBufA8aMV=_sHca5ZOi-3viTw@mail.gmail.com>
Content-Type: multipart/alternative;
	boundary="------------070000040605000202080204"
X-Spam-Score: -0.8 (/)
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
	(etotheipi[at]gmail.com)
	-0.0 SPF_PASS               SPF: sender matches SPF record
	1.0 HTML_MESSAGE           BODY: HTML included in message
	-0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from
	author's domain
	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
	-0.2 AWL AWL: From: address is in the auto white-list
X-Headers-End: 1Sh2v1-0007yl-J2
Cc: bitcoin-development@lists.sourceforge.net
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 18:12:48 -0000

This is a multi-part message in MIME format.
--------------070000040605000202080204
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit

On 06/19/2012 01:59 PM, Gregory Maxwell wrote:
> On Tue, Jun 19, 2012 at 1:33 PM, Alan Reiner<etotheipi@gmail.com>  wrote:
>>   One app developer updates their
>> RB tree code which updated the RB-tree optimizations/rebalancing, and
>> now a significant portion of the network can't agree on the correct
>> root.  Not only would that be disruptive, it would be a disaster to
>> track down.
> This is why good comprehensive tests and a well specified algorithim
> are important. The tree update algorithm would be normative in that
> scheme. Worrying that implementers might get it wrong would be like
> worrying that they'd get SHA256 wrong.

The point is not that they get it *wrong*, it's that the implement it 
*differently*.  Given a set of 100 TxOuts, there's a seemingly-infinite 
number of ways to construct a binary tree.  Put them in in a different 
order, and you get a different tree. *They're all correct and legal* in 
terms of satisfying expectations of insert, delete and query runtime -- 
but they will produce different root hashes.   And the differences in 
underlying structure are completely transparent to the calling code.

I'm extremely uncomfortable with the idea the you can have all the nodes 
in the tree, but have to replay X years of blockchain history just to 
get the same tree configuration as someone else.  However, a trie 
configuration is history-independent -- given an unspent-TxOut list, 
there's only one way to construct that tree.  That's an important 
property to me.

I can't tell if you're joking about Judy structures: I've never heard of 
them.  But I'll look into it anyway...


--------------070000040605000202080204
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 8bit

<html>
  <head>
    <meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
  </head>
  <body text="#000000" bgcolor="#FFFFFF">
    On 06/19/2012 01:59 PM, Gregory Maxwell wrote:
    <blockquote
cite="mid:CAAS2fgRFFtdsuaS+ZoFLYcnUxLBufA8aMV=_sHca5ZOi-3viTw@mail.gmail.com"
      type="cite">
      <pre wrap="">On Tue, Jun 19, 2012 at 1:33 PM, Alan Reiner <a class="moz-txt-link-rfc2396E" href="mailto:etotheipi@gmail.com">&lt;etotheipi@gmail.com&gt;</a> wrote:
</pre>
      <blockquote type="cite">
        <pre wrap=""> One app developer updates their
RB tree code which updated the RB-tree optimizations/rebalancing, and
now a significant portion of the network can't agree on the correct
root.  Not only would that be disruptive, it would be a disaster to
track down.
</pre>
      </blockquote>
      <pre wrap="">
This is why good comprehensive tests and a well specified algorithim
are important. The tree update algorithm would be normative in that
scheme. Worrying that implementers might get it wrong would be like
worrying that they'd get SHA256 wrong.</pre>
    </blockquote>
    <br>
    The point is not that they get it <b>wrong</b>, it's that the
    implement it <b>differently</b>.  Given a set of 100 TxOuts,
    there's a seemingly-infinite number of ways to construct a binary
    tree.  Put them in in a different order, and you get a different
    tree.  <b>They're all correct and legal</b> in terms of satisfying
    expectations of insert, delete and query runtime -- but they will
    produce different root hashes.   And the differences in underlying
    structure are completely transparent to the calling code.<br>
    <br>
    I'm extremely uncomfortable with the idea the you can have all the
    nodes in the tree, but have to replay X years of blockchain history
    just to get the same tree configuration as someone else.  However, a
    trie configuration is history-independent -- given an unspent-TxOut
    list, there's only one way to construct that tree.  That's an
    important property to me. <br>
    <br>
    I can't tell if you're joking about Judy structures: I've never
    heard of them.  But I'll look into it anyway...<br>
    <br>
  </body>
</html>

--------------070000040605000202080204--