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
|
Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191]
helo=mx.sourceforge.net)
by sfs-ml-1.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <pete@petertodd.org>) id 1SgYz5-0008Hs-CW
for bitcoin-development@lists.sourceforge.net;
Mon, 18 Jun 2012 10:14:59 +0000
Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of petertodd.org
designates 62.13.148.154 as permitted sender)
client-ip=62.13.148.154; envelope-from=pete@petertodd.org;
helo=outmail148154.authsmtp.co.uk;
Received: from outmail148154.authsmtp.co.uk ([62.13.148.154])
by sog-mx-1.v43.ch3.sourceforge.com with esmtp (Exim 4.76)
id 1SgYyz-0008OZ-9M for bitcoin-development@lists.sourceforge.net;
Mon, 18 Jun 2012 10:14:59 +0000
Received: from mail-c194.authsmtp.com (mail-c194.authsmtp.com [62.13.128.121])
by punt6.authsmtp.com (8.14.2/8.14.2/Kp) with ESMTP id
q5IAEj5L016346; Mon, 18 Jun 2012 11:14:45 +0100 (BST)
Received: from savin (206-248-185-87.dsl.teksavvy.com [206.248.185.87])
(authenticated bits=128)
by mail.authsmtp.com (8.14.2/8.14.2) with ESMTP id q5IAEceL084316
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO);
Mon, 18 Jun 2012 11:14:41 +0100 (BST)
Date: Mon, 18 Jun 2012 06:14:41 -0400
From: Peter Todd <pete@petertodd.org>
To: Alberto Torres <kungfoobar@gmail.com>
Message-ID: <20120618101441.GB11629@savin>
References: <4FDE2460.5080301@gmail.com> <20120617190511.GA26047@savin>
<CAE98tO2PcxKdz670ptHB=3Pc9JvV_+Wjdt1117M4SA2hANKH+w@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha1;
protocol="application/pgp-signature"; boundary="1LKvkjL3sHcu1TtY"
Content-Disposition: inline
In-Reply-To: <CAE98tO2PcxKdz670ptHB=3Pc9JvV_+Wjdt1117M4SA2hANKH+w@mail.gmail.com>
User-Agent: Mutt/1.5.21 (2010-09-15)
X-Server-Quench: 6b74538a-b92e-11e1-80b9-0022640b883e
X-AuthReport-Spam: If SPAM / abuse - report it at:
http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR
aAdMdwoUEkAaAgsB AmQbWlVeUVl7XWE7 aQpXcwdZalRPVwB0
WE9WR1pVCwQmQBl4 d2tNB2VyfwFFeXg+ ZEJlXXMVWhZ9cUN+
Sh9JR2QEMHphaTUe TUhYJQpJcANIfBlB agJ3XHBYLwdSbGoL
NQ4vNDcwO3BTJTpY RgYVKF8UXXNDIzog RhULAThnN0kCTCY4
LxUnLBY3G0MJKEgp KlomXxoHdH1aFhdD BF0IDjVUKhEFRjYm RQVdUUMFeAAA
X-Authentic-SMTP: 61633532353630.1015:706
X-AuthFastPath: 0 (Was 255)
X-AuthSMTP-Origin: 206.248.185.87/587
X-AuthVirus-Status: No virus detected - but ensure you scan with your own
anti-virus system.
X-Spam-Score: -1.5 (-)
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
X-Headers-End: 1SgYyz-0008OZ-9M
Cc: bitcoin-development@lists.sourceforge.net
Subject: Re: [Bitcoin-development] Ultimate Blockchain Compression w/
trust-free lite nodes
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: Mon, 18 Jun 2012 10:14:59 -0000
--1LKvkjL3sHcu1TtY
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
On Mon, Jun 18, 2012 at 12:46:47AM +0200, Alberto Torres wrote:
> Hi,
>=20
> I did describe a very similar thing back in January (also illustrated,
> and, if I'm not mistaken, more simple and efficient to recalculate),
> and I wanted to do a prototype, but I have been very busy with other
> projects since then.
>=20
> https://en.bitcoin.it/wiki/User:DiThi/MTUT
>=20
> I just saw Gavin left a comment in the talk page, I'm sorry I haven't
> seen it earlier.
>=20
> I think armory is the perfect client to implement such an idea. I sort
> of waited it to be able to run in my laptop with 2 GB of RAM before
> being sucked into other projects. I even lost track of its
> development.
I strongly disagree on that point. What you're proposing needs miner
support to work, and miners generally run either the satoshi client as a
daemon, or some other custom code. Implementing the idea in armory
doesn't give those miners a nice upgrade path.
That said, *using* the hash tree is something that can be implemented in
any client, but a lot of the code will be shared between calculating it
and using it anyway, so again implementing in the satoshi client makes
sense.
> I hope this gets developed. I will be able to help after summer if
> this is still not done.
>=20
> DiThi
>=20
> P.S: Sorry Peter, I've sent you the message privately by mistake.
> Also, I don't quite understand your concern of "unbalancing" the tree.
Lets suppose we're trying to make a tree consisting of real numbers:
/\
/ \
* \
/ \ \
/ \ \
* * *
/ \ / \ / \
1 2 3 4 5 6
If the numbers are evenly distributed, as will happen with hashes of
arbitrary data, any number will be at most log(n) steps away from the
head of the tree.
Suppose though some malicious actor adds the following numbers to that
tree: 3.001 3.002 3.003
/\
/ \
* \
/ \ \
/ \ \
* * *
/ \ / \ / \
1 2 * 4 5 6
/ \
| \
* *
/ \ / \
0 1 2 3 <- (3.000 to 3.003)
Ooops, the tree suddenly became a lot higher, with an associated
decrease in retrieval performance and an increase in memory usage.
Of course the exact details depend on what rules there are for
constructing the tree, but essentially the attacker can either force the
a big increase in the depth of the tree, or a large number of vertexes
to be re-organizationed to create the tree, or both.
Now, to be exact, since the key of each vertex is a transaction hash,
this malicious actor will need to brute chosen prefix hash collisions,
but this is bitcoin: the whole system is about efficiently brute forcing
chosen prefix hash collisions. Besides, you would only need something
like k*n collisions to product an n increase in tree depth, with some
small k.
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.
Another naive option would be to hash each vertex key (the transaction
hash) with a nonce known only to the creator of that particular merkle
tree, but then the whole tree has to be recreatred from scratch each
time, which is worse than the problem... Interestingly in a
*non-distributed* system this idea is actually quite feasible feasible,
as the nonce could be kept secret.
--=20
'peter'[:-1]@petertodd.org
--1LKvkjL3sHcu1TtY
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
iQEcBAEBAgAGBQJP3v+QAAoJEH+rEUJn5PoEGf8H/irZXe8wP1ImJNKRjI6Qc+Zx
IzzYtuSf34hb31zrx3sBNgSM5L2Mo8/0Q2HfERqOEGNfTF6NIsyB/vkcq1pYpLaH
DINgC8yrDUuImUtpJI/h0sEQq221uZmOu+VPhlcysorp0fJKBiyYdMd/IrDVOHwf
9sdrtaeGJLWtdRcZTVwM7X7r1Gmwep17jX2NqGkAZFbG21rlFyFhoQcp8pYgjwza
Q0V6Isc1IocEh2ux+sNAWwLjdPyJeXzIEOMSGzrFNkIh+tNyYxG1msnntJKac5Bj
hipkhJFaw9MiZK2lfM60onCcNqju/LAJhJWK4axCoa9IyKk99CjmQc2zawZMYuk=
=H+Fk
-----END PGP SIGNATURE-----
--1LKvkjL3sHcu1TtY--
|
