summaryrefslogtreecommitdiff
path: root/b7/ac66a09095c4ef56709602e502db9591516ec4
blob: 971eab300df5adeea89db1a56076ddead5e5c413 (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
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
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 <pete@petertodd.org>) id 1UzPRu-0000j9-QR
	for bitcoin-development@lists.sourceforge.net;
	Wed, 17 Jul 2013 10:59:11 +0000
Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of petertodd.org
	designates 62.13.148.161 as permitted sender)
	client-ip=62.13.148.161; envelope-from=pete@petertodd.org;
	helo=outmail148161.authsmtp.com; 
Received: from outmail148161.authsmtp.com ([62.13.148.161])
	by sog-mx-3.v43.ch3.sourceforge.com with esmtp (Exim 4.76)
	id 1UzPRq-0003G1-M4 for bitcoin-development@lists.sourceforge.net;
	Wed, 17 Jul 2013 10:59:10 +0000
Received: from mail-c232.authsmtp.com (mail-c232.authsmtp.com [62.13.128.232])
	by punt6.authsmtp.com (8.14.2/8.14.2/Kp) with ESMTP id
	r6HAww49062952; Wed, 17 Jul 2013 11:58:58 +0100 (BST)
Received: from savin (76-10-178-109.dsl.teksavvy.com [76.10.178.109])
	(authenticated bits=128)
	by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id r6HAwsXX033769
	(version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO);
	Wed, 17 Jul 2013 11:58:56 +0100 (BST)
Date: Wed, 17 Jul 2013 06:58:53 -0400
From: Peter Todd <pete@petertodd.org>
To: Wendell <w@grabhive.com>
Message-ID: <20130717105853.GA10083@savin>
References: <CANEZrP0_H9+prDSF92q8a4QzP=fzDM6cTDv0+KcfV9NF9thkmw@mail.gmail.com>
	<3E7894A0-06F3-453D-87F8-975A244EBACF@include7.ch>
	<CANEZrP2jmWkDbpJEm0vd2CKF-prFNbz_ZeNJfDWtSCKb8k5ZXA@mail.gmail.com>
	<2BDA0943-22BB-4405-9AF0-86FB41FD04A6@include7.ch>
	<CANEZrP0McSrVzwv=-qimPyX41EEDmyQdYW5QjPr_i+KWyJZSZw@mail.gmail.com>
	<2F20A509-13A9-4C84-86D7-A15C21BACD53@include7.ch>
	<CANEZrP2yQvmvwP_ZULdS2i+X6L9MeZ+DfidiuZPD2EHwLsN2MA@mail.gmail.com>
	<2A1C412D-414E-4C41-8E20-F0D21F801328@grabhive.com>
	<CANEZrP12V_5Ak0f91RsMziuqXysde102rGeSko=qPBjefy3AeA@mail.gmail.com>
	<8EE501AA-1601-4C28-A32E-80F17D219D3A@grabhive.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
	protocol="application/pgp-signature"; boundary="ew6BAiZeqk4r7MaW"
Content-Disposition: inline
In-Reply-To: <8EE501AA-1601-4C28-A32E-80F17D219D3A@grabhive.com>
User-Agent: Mutt/1.5.21 (2010-09-15)
X-Server-Quench: e0ff021f-eecf-11e2-b10b-0025903375e2
X-AuthReport-Spam: If SPAM / abuse - report it at:
	http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR
	aAdMdwUUEkAYAgsB AmUbWlVeVVV7XGQ7 bAxPbAVDY01GQQRq
	WVdMSlVNFUsqB2Rw QV12OhlxdAJAcTBy Y0JgWj4OXBIsdUR8
	FFMBQD5QeGZhPWIC AkFYJR5UcAFPdx9G aVd6AXFDAzANdhES
	HhM4ODE3eDlSNilR RRkIIFQOdA4wJgB0 TREeFjIuG0FSD2Us
	Jgd0Yn8aAFwWPlg5 MF0uOxoyMgMZDQxY PEBRRiFDLlwMWC0x DkIy
X-Authentic-SMTP: 61633532353630.1019:706
X-AuthFastPath: 0 (Was 255)
X-AuthSMTP-Origin: 76.10.178.109/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: 1UzPRq-0003G1-M4
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] SPV bitcoind? (was: Introducing
 BitcoinKit.framework)
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: Wed, 17 Jul 2013 10:59:11 -0000


--ew6BAiZeqk4r7MaW
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Tue, Jul 16, 2013 at 04:16:23PM +0200, Wendell wrote:
> Hello everyone,
>=20
> In the previous thread, I expressed interest in seeing an SPV bitcoind, f=
urther stating that I would fund such work. Mike Hearn followed up with som=
e of Satoshi's old code for this, which is now quite broken. The offer and =
interest on my side still stand, as more diversity in SPV options seems lik=
e the right way to go.
>=20
> Time-permitting, I would really appreciate feedback from knowledgable par=
ties about the possible approaches to an SPV bitcoind. We at Hive ideally w=
ant to see something that could one be merge into master, rather than a for=
k.

Keep in mind that SPV mode is newer than many realize: bloom filters are
a 0.8 feature, itself released only last Febuary. As John Dillon posted
earlier this week in "Protecting Bitcoin against network-wide DoS
attack" the Bitcoin codebase will have to implement much better anti-DoS
attack defences soon, and in a decentralized system there aren't any
options other than requiring peers to either do work (useful or not) or
sacrifice something of value. SPV peers can't do useful work, leaving
only sacrifice - to what extent and how much is unknown. In addition SPV
nodes have serious privacy issues because their peers know that any
transaction sent to them by the SPV node is guaranteed to be from the
node rather than relayed; bloom filters are only really helpful with
payment protocols that don't exist yet and don't apply to merchants.
Then you have MITM problems, vulnerability to fake blocks etc.

It'll be awhile before we know how serious these issues are in practice,
and we're likely to find new issues we didn't think of too. In any case
Bitcoin is far better off if we make it easy to run a full node,
donating whatever resources you can. Fortunately there's a whole
continuum between SPV and full nodes.

The way you do this is by maintaining partial UTXO sets. The trick is
that if you have verified every block in some range i to j, every time
you see a txout created by a transaction, and not subsequently spent,
you can be sure that at height j the txout existed. If height j is the
current block, you can be sure the txout exists provided that the chain
itself is valid. Any transaction that only spends txouts in this partial
set is a transaction you can fully verify and safely relay; for other
transactions you just don't know and have to wait until you see them in
a block.

So what's useful about that? Basically it means your node starts with
the same security level, and usefulness to the network, as a SPV node.
But over time you keep downloading blocks as they are created, and with
whatever bandwidth you have left (out of some user-configurable
allocation) you download additional blocks going further and further
back in time. Gradually your UTXO set becomes more complete, and over
time you can verify a higher and higher % of all valid transactions.
Eventually your node becomes a full node, but in the meantime it was
still useful for the user, and still contributed to the network by
relaying blocks and an increasingly large subset of all transactions.
(optionally you can store a subset of the chain history too for other
nodes to bootstrap from) You've also got better security because you
*are* validating blocks, starting off incompletely, and increasingly
completely until your finally validating fully. Privacy is improved, for
both you and others, by mixing your transactions with others and adding
to the overall anonymity set.

In the future we'll have miners commit a hash of the UTXO set, and that
gives us even more options to, for instance, have relayed transactions
include proof that their inputs were valid, allowing all nodes to relay
them safely.


As for specifics, you need to maintain a UTXO set, and in addition a set
of spent txouts (the STXO set) for which you haven't seen the
transaction that created the txout. As download newer blocks you update
the UTXO set; as you download older blocks you update the UTXO set and
STXO set.

Nodes now advertise this new variable to their peers:

nOldestBlock - The oldest block that we've validated. (and all
subsequent blocks)

We'll also want the ability to advertise what sub-ranges of the
blockchain data we have on hand:

listArchivedBlockRanges - lists of (begin, end pairs)

Nodes should drop all but the largest n pairs, say 5 or something. The
index -1 is reserved to indicate the last block to make it easy to
advertise that you have every block starting at some height to the most
recent. (reserving -n with n as the last block might be a better choice
to show intent, but still allow for specific proofs when we get node
identities)

We probably want to define a NODE_PARTIAL service bit or something; I'll
have to re-read Pieter Wuille's proposal and think about it. Nodes
should NOT advertize NODE_NETWORK unless they have the full chain and
have verified it.

Nodes with partial peers should only relay transactions to those peers
if the transactions spend inputs the peers know about - remember how
even an SPV node has that information if it's not spending unconfirmed
inputs it didn't create. Nodes will have to update their peers
periodically as nOldestBlock changes. That said it may also be
worthwhile to simply relay all transactions in some cases too - a
reasonable way to approach this might be to set a bloom filter for tx's
that you *definitely* want, and if you are interested in everything,
just set the filter to all 1's. If someone comes up with a reasonable
micropayment or proof-of-work system even relaying txs that you haven't
validated is fine - the proof-of-work and prioritization will prevent
DoS attacks just fine.

Remember that if you're running a partial node, it can get new blocks
=66rom any partial node, and it can retrieve historic blockchain data from
any partial node that has archived the sequence of blocks you need next.
On a large scale this is similar to how in BitTorrent you can serve data
to your peers the moment you get it - a significant scalability
improvement for the network as a whole. Even if a large % of the network
was partial nodes running for just a few hours a day the whole system
would work fine due to how partial nodes can serve each other the data
they need.

On startup you can act as a SPV node temporarily, grabbing asking for
filtered blocks matching your wallet, and then go back and get the full
blocks, or just download the full blocks right away. That's a tradeoff
on how long the node has been off.

Anyway, it's a bit more code compared to pure-SPV, but it results in a
much more scalable Bitcoin, and if you can spare the modest bandwidth
requirements to keep up with the blockchain it'll result in much better
robustness against DoS attacks for you and Bitcoin in general.

--=20
'peter'[:-1]@petertodd.org

--ew6BAiZeqk4r7MaW
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)

iQEcBAEBCAAGBQJR5njtAAoJECSBQD2l8JH77EMIAIy210mcaXNh0A9fiTrrpLoa
D8jdpK7K8xixhSwjkf5enUm/D+BEm2a2ahsm2FlfQjd8GkbdD1r0I/5wWSO9C595
bA+ldDNVO/h0mwrYor0zBT1Kjpj58wzL12xEcSk9ZHFs6FzGPKlDkynbJ2ZzznXe
2HljJ9QOC9kwSwjdX2ddBoxNojRXVIH3OFjvsa+L2XlrBFqVwN37tALPXpzm5r9p
g4e1jBQ7myxxVYQHz6jZaxw7nv3dzD3MAYFqmNzMwRIeaUvDOf9MBzhuj9uwPmn8
aPnEwpgOPCEF1kwyXkZJhslkx+xd06U6yE/jcCxHiV9Is74GmJYcxwZ6uGfBgVU=
=i2/l
-----END PGP SIGNATURE-----

--ew6BAiZeqk4r7MaW--