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
|
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 1SgLjY-0008KK-DY
for bitcoin-development@lists.sourceforge.net;
Sun, 17 Jun 2012 20:06:04 +0000
Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of petertodd.org
designates 62.13.149.84 as permitted sender)
client-ip=62.13.149.84; envelope-from=pete@petertodd.org;
helo=outmail149084.authsmtp.net;
Received: from outmail149084.authsmtp.net ([62.13.149.84])
by sog-mx-1.v43.ch3.sourceforge.com with esmtp (Exim 4.76)
id 1SgLjX-0001s4-2W for bitcoin-development@lists.sourceforge.net;
Sun, 17 Jun 2012 20:06:04 +0000
Received: from mail-c194.authsmtp.com (mail-c194.authsmtp.com [62.13.128.121])
by punt8.authsmtp.com (8.14.2/8.14.2/Kp) with ESMTP id
q5HJ5Ceh051408; Sun, 17 Jun 2012 20:05:12 +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 q5HJ59mD065220
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO);
Sun, 17 Jun 2012 20:05:11 +0100 (BST)
Date: Sun, 17 Jun 2012 15:05:11 -0400
From: Peter Todd <pete@petertodd.org>
To: Alan Reiner <etotheipi@gmail.com>
Message-ID: <20120617190511.GA26047@savin>
References: <4FDE2460.5080301@gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha1;
protocol="application/pgp-signature"; boundary="azLHFNyN32YCQGCU"
Content-Disposition: inline
In-Reply-To: <4FDE2460.5080301@gmail.com>
User-Agent: Mutt/1.5.21 (2010-09-15)
X-Server-Quench: 5d6f6fe5-b8af-11e1-80b9-0022640b883e
X-AuthReport-Spam: If SPAM / abuse - report it at:
http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR
aAdMdwUUEkAaAgsB AmQbWVReUFh7WGE7 aQpXcwdZalRPVwB0
WE9WR1pVCwQmQBl5 fBsXD21ycQBEen4+ ZEdqW3AVWRB8I0Ar
F0tJR2VXM3phaTUe 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: 1SgLjX-0001s4-2W
Cc: Bitcoin Dev <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: Sun, 17 Jun 2012 20:06:04 -0000
--azLHFNyN32YCQGCU
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
On Sun, Jun 17, 2012 at 02:39:28PM -0400, Alan Reiner wrote:
> All,
>=20
> With the flurry of discussion about blockchain compression, I
> thought it was time to put forward my final, most-advanced idea,
> into a single, well-thought-out, *illustrated*, forum post.
> Please check it out: https://bitcointalk.org/index.php?topic=3D88208.0
>=20
> This is a huge undertaking, but it has some pretty huge benefits.
> And it's actually feasible because it can be implemented without
> disrupting the main network. I'm sure there's lots of issues with
> it, but I'm putting it out there to see how it might be improved and
> actually executed.
>=20
> ----
> *Summary:
>=20
> */Use a special tree data structure to organize all unspent-TxOuts
> on the network, and use the root of this tree to communicate its
> "signature" between nodes. The leaves of this tree actually
> correspond to addresses/scripts, and the data at the leaf is
> actually a root of the unspent-TxOut list for that address/script.
> To maintain security of the tree signatures, it will be included in
> the header of an alternate blockchain, which will be secured by
> merged mining.
>=20
> This provides the same compression as the simpler unspent-TxOut
> merkle tree, but also gives nodes a way to download just the
> unspent-TxOut list for each address in their wallet, and verify that
> list directly against the blockheaders. Therefore, even lightweight
> nodes can get full address information, from any untrusted peer, and
> with only a tiny amount of downloaded data (a few kB). /*
How are you going to prevent people from delibrately unbalancing the
tree with addresses with chosen hashes?
One idea that comes to mind, which unfortunately would make for a
pseudo-network rule, is to simply say that any *new* address whose hash
happens to be deeper in the tree than, say, 10*log(n), indicating it was
probably chosen to be unbalanced, gets discarded. The "new address" part
of the rule would be required, or else you could use the rule to get
other people's addresses discarded.
Having said that, such a rule just means that anyone playing games will
find they can't spend *their* money, and only with pruning clients.
Unrelated people will not be effected. The coins can also always be
spent with a non-pruning client to an acceptable address, which can
later re-spend on a pruning client.
It also comes to mind is that with the popularity of firstbits it may be
a good idea to use a comparison function that works last bit first...
It's merkles all the way down...
--=20
'peter'[:-1]@petertodd.org
--azLHFNyN32YCQGCU
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
iQEcBAEBAgAGBQJP3ipmAAoJEH+rEUJn5PoEcAEH/3ZUyX+yaumviSoq7fdcqQYg
9/s/pFrMfV36FIuf3GLk0/hurePf9HNM5H+2C0SUqAdj6zMvGyYqeIRbx0YsaMd+
myU+/Hw0jEoXevHGPueWlNW/TO/eFLjANj3Rj6Zj2LuuMfd8kc8R/5DwcEH9jg38
JSH5or2RM1JpuSN8Uve4HquZnskE/XCp6v1eAK9fjDWeQK6o+Q5C+/WufxlYLUPy
oqY0wQQmA0zKzig4H24ckrzRZV8wuocfRl+2kwZyFTyWP7Fph2zWqWWkaKTcrQKS
x9ejFT6ICZ1U8tZrK7pG8QfQR3boXKC85Vhw2L3paV3Nr86i/fN7yukAqlkA16Q=
=OqKD
-----END PGP SIGNATURE-----
--azLHFNyN32YCQGCU--
|
