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
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
|
Return-Path: <danny.thorpe@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 2275198C
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 17 Apr 2017 07:11:12 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-lf0-f48.google.com (mail-lf0-f48.google.com
[209.85.215.48])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 97725F0
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 17 Apr 2017 07:11:10 +0000 (UTC)
Received: by mail-lf0-f48.google.com with SMTP id 88so14655530lfr.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 17 Apr 2017 00:11:10 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to
:cc; bh=szG8TwH/AuVaO36vEupnualefkijGq7Ub+uzYGDfzIk=;
b=FizBHgsqmbYgwmvzb4PMachnvhF0BOZnwiq/U3zxtQDNYxx+w9J0aRinxiVEeFCaNc
obbP2ukEgZybsVuGUD+1a1BqpHSDtL6xAj+qFR1mAV44DuAwMyoyhnpcHa4r559sjDhT
EO8bfuzYDASgIG9Q500sjt0mPlR1qihWpeKbrTDlpJ8U5vN+do92gq3dChqVZwif28cw
eA5U/OjCz4UH2QRMGBfBKn5im27VNUJYFOnv4IZAYB/5h9T3ifNlk3wCeuTvKKVEmNGQ
O9IbchM3dtGGT4kFQVzsL3kMEg6tfIBiuXnmUzveYB+MZMNejo74cHvxKdc1xIo+IH5U
+3gA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:in-reply-to:references:from:date
:message-id:subject:to:cc;
bh=szG8TwH/AuVaO36vEupnualefkijGq7Ub+uzYGDfzIk=;
b=IURbQwDiFmgLh0FQxAiZOIEFpf1wsjht59Q63AjNEc+s9uGfFKFpZbR5LIUvXgnaIi
OzZzIFMBWAdhWmo2Mop2EWC6IfLua7bc1nudOVFtu8NzR/IpKFBrTgKslMesXD7IiBNB
Zz1h2kkY7EB19q9B6RKmthx/novL4glJNh1DvyB3DGMeNnQnIfPkEYoedyS0NtgD6dt0
2+UewoMniE0o3LdlHtj2X0cJLJnXrCGj+6dMcWcKNrPr9CBAsI5yt3CqyDaZvnLCLkSj
+DfGyR7p/dTixxI7VuBZdQv04rjVP9ogsUed0SIKXoyHVml7slMVI7Z59S6LmbRESkrK
SziQ==
X-Gm-Message-State: AN3rC/4VscAXSKOk2Bp2Ad3zX4TK5pLdcQHKQ5QI0tFarRv0VfXjKmdW
g5G/+1xo4VpgdIN3FLj9Eq2A7b2agw==
X-Received: by 10.25.26.69 with SMTP id a66mr2351907lfa.48.1492413068933; Mon,
17 Apr 2017 00:11:08 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.46.32.9 with HTTP; Mon, 17 Apr 2017 00:11:07 -0700 (PDT)
Received: by 10.46.32.9 with HTTP; Mon, 17 Apr 2017 00:11:07 -0700 (PDT)
In-Reply-To: <CAFVRnypbQQ-vsSLqv48cYaqTCty4R1DmFRqfAvxe4mAqyQNXxQ@mail.gmail.com>
References: <CAFVRnypbQQ-vsSLqv48cYaqTCty4R1DmFRqfAvxe4mAqyQNXxQ@mail.gmail.com>
From: Danny Thorpe <danny.thorpe@gmail.com>
Date: Mon, 17 Apr 2017 00:11:07 -0700
Message-ID: <CAJN5wHW=p+q+DT9R=uheLxOjKBX=xcB+fOZR2KACgJO9SdXypw@mail.gmail.com>
To: David Vorick <david.vorick@gmail.com>
Content-Type: multipart/alternative; boundary=001a11472d54d4fea5054d577ef8
X-Spam-Status: No, score=-1.5 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE,
RCVD_IN_DNSWL_NONE,
RCVD_IN_SORBS_SPAM autolearn=no version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Small Nodes: A Better Alternative to Pruned Nodes
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Mon, 17 Apr 2017 07:11:12 -0000
--001a11472d54d4fea5054d577ef8
Content-Type: text/plain; charset=UTF-8
1TB HDD is now available for under $40 USD. How is the 100GB storage
requirement preventing anyone from setting up full nodes?
On Apr 16, 2017 11:55 PM, "David Vorick via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> *Rationale:*
>
> A node that stores the full blockchain (I will use the term archival node)
> requires over 100GB of disk space, which I believe is one of the most
> significant barriers to more people running full nodes. And I believe the
> ecosystem would benefit substantially if more users were running full nodes.
>
> The best alternative today to storing the full blockchain is to run a
> pruned node, which keeps only the UTXO set and throws away already verified
> blocks. The operator of the pruned node is able to enjoy the full security
> benefits of a full node, but is essentially leeching the network, as they
> performed a large download likely without contributing anything back.
>
> This puts more pressure on the archival nodes, as the archival nodes need
> to pick up the slack and help new nodes bootstrap to the network. As the
> pressure on archival nodes grows, fewer people will be able to actually run
> archival nodes, and the situation will degrade. The situation would likely
> become problematic quickly if bitcoin-core were to ship with the defaults
> set to a pruned node.
>
> Even further, the people most likely to care about saving 100GB of disk
> space are also the people least likely to care about some extra bandwidth
> usage. For datacenter nodes, and for nodes doing lots of bandwidth, the
> bandwidth is usually the biggest cost of running the node. For home users
> however, as long as they stay under their bandwidth cap, the bandwidth is
> actually free. Ideally, new nodes would be able to bootstrap from nodes
> that do not have to pay for their bandwidth, instead of needing to rely on
> a decreasing percentage of heavy-duty archival nodes.
>
> I have (perhaps incorrectly) identified disk space consumption as the most
> significant factor in your average user choosing to run a pruned node or a
> lite client instead of a full node. The average user is not typically too
> worried about bandwidth, and is also not typically too worried about
> initial blockchain download time. But the 100GB hit to your disk space can
> be a huge psychological factor, especially if your hard drive only has
> 500GB available in the first place, and 250+ GB is already consumed by
> other files you have.
>
> I believe that improving the disk usage situation would greatly benefit
> decentralization, especially if it could be done without putting pressure
> on archival nodes.
>
> *Small Nodes Proposal:*
>
> I propose an alternative to the pruned node that does not put undue
> pressure on archival nodes, and would be acceptable and non-risky to ship
> as a default in bitcoin-core. For lack of a better name, I'll call this new
> type of node a 'small node'. The intention is that bitcoin-core would
> eventually ship 'small nodes' by default, such that the expected amount of
> disk consumption drops from today's 100+ GB to less than 30 GB.
>
> My alternative proposal has the following properties:
>
> + Full nodes only need to store ~20% of the blockchain
> + With very high probability, a new node will be able to recover the
> entire blockchain by connecting to 6 random small node peers.
> + An attacker that can eliminate a chosen+ 95% of the full nodes running
> today will be unable to prevent new nodes from downloading the full
> blockchain, even if the attacker is also able to eliminate all archival
> nodes. (assuming all nodes today were small nodes instead of archival nodes)
>
> Method:
>
> A small node will pick an index [5, 256). This index is that node's
> permanent index. When storing a block, instead of storing the full block,
> the node will use Reed-Solomon coding to erasure code the block using a
> 5-of-256 scheme. The result will be 256 pieces that are 20% of the size of
> the block each. The node picks the piece that corresponds to its index, and
> stores that instead. (Indexes 0-4 are reserved for archival nodes -
> explained later)
>
> The node is now storing a fragment of every block. Alone, this fragment
> cannot be used to recover any piece of the blockchain. However, when paired
> with any 5 unique fragments (fragments of the same index will not be
> unique), the full block can be recovered.
>
> Nodes can optionally store more than 1 fragment each. At 5 fragments, the
> node becomes a full archival node, and the chosen indexes should be 0-4.
> This is advantageous for the archival node as the encoded data for the
> first 5 indexes will actually be identical to the block itself - there is
> no computational overhead for selecting the first indexes. There is also no
> need to choose random indexes, because the full block can be recovered no
> matter which indexes are chosen.
>
> When connecting to new peers, the indexes of each peer needs to be known.
> Once peers totaling 5 unique indexes are discovered, blockchain download
> can begin. Connecting to just 5 small node peers provides a >95% chance of
> getting 5 uniques, with exponentially improving odds of success as you
> connect to more peers. Connecting to a single archive node guarantees that
> any gaps can be filled.
>
> A good encoder should be able to turn a block into a 5-of-256 piece set in
> under 10 milliseconds using a single core on a standard consumer desktop.
> This should not slow down initial blockchain download substantially, though
> the overhead is more than a rounding error.
>
> *DoS Prevention:*
>
> A malicious node may provide garbage data instead of the actual piece.
> Given just the garbage data and 4 other correct pieces, it is impossible
> (best I know anyway) to tell which piece is the garbage piece.
>
> One option in this case would be to seek out an archival node that could
> verify the correctness of the pieces, and identify the malicious node.
>
> Another option would be to have the small nodes store a cryptographic
> checksum of each piece. Obtaining the cryptographic checksum for all 256
> pieces would incur a nontrivial amount of hashing (post segwit, as much as
> 100MB of extra hashing per block), and would require an additional ~4kb of
> storage per block. The hashing overhead here may be prohibitive.
>
> Another solution would be to find additional pieces and brute-force
> combinations of 5 until a working combination was discovered. Though this
> sounds nasty, it should take less than five seconds of computation to find
> the working combination given 5 correct pieces and 2 incorrect pieces. This
> computation only needs to be performed once to identify the malicious peers.
>
> I also believe that alternative erasure coding schemes exist which
> actually are able to identify the bad pieces given sufficient good pieces,
> however I don't know if they have the same computational performance as the
> best Reed-Solomon coding implementations.
>
> *Deployment:*
>
> Small nodes are completely useless unless the critical mass of 5 pieces
> can be obtained. The first version that supports small node block downloads
> should default everyone to an archival node (meaning indexes 0-4 are used)
>
> Once there are enough small-node-enabled archive nodes, the default can be
> switched so that nodes only have a single index by default. In the first
> few days, when there are only a few small nodes, the previously-deployed
> archival nodes can help fill in the gaps, and the small nodes can be useful
> for blockchain download right away.
>
> ----------------------------------
>
> This represents a non-trivial amount of code, but I believe that the
> result would be a non-trivial increase in the percentage of users running
> full nodes, and a healthier overall network.
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
--001a11472d54d4fea5054d577ef8
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"auto">1TB HDD is now available for under <span class=3D"money">=
$40</span>=C2=A0USD.=C2=A0 How is the 100GB storage requirement preventing =
anyone from setting up full nodes?</div><div class=3D"gmail_extra"><br><div=
class=3D"gmail_quote">On Apr 16, 2017 11:55 PM, "David Vorick via bit=
coin-dev" <<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org"=
>bitcoin-dev@lists.linuxfoundation.org</a>> wrote:<br type=3D"attributio=
n"><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left=
:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div><div><b>Rationale:<=
/b><br></div><div><br>A node that stores the full blockchain (I will use th=
e term archival node) requires over 100GB of disk space, which I believe is=
one of the most significant barriers to more people running full nodes. An=
d I believe the ecosystem would benefit substantially if more users were ru=
nning full nodes.<br><br></div>The best alternative today to storing the fu=
ll blockchain is to run a pruned node, which keeps only the UTXO set and th=
rows away already verified blocks. The operator of the pruned node is able =
to enjoy the full security benefits of a full node, but is essentially leec=
hing the network, as they performed a large download likely without contrib=
uting anything back.<br><br></div><div>This puts more pressure on the archi=
val nodes, as the archival nodes need to pick up the slack and help new nod=
es bootstrap to the network. As the pressure on archival nodes grows, fewer=
people will be able to actually run archival nodes, and the situation will=
degrade. The situation would likely become problematic quickly if bitcoin-=
core were to ship with the defaults set to a pruned node.<br><br></div><div=
>Even further, the people most likely to care about saving 100GB of disk sp=
ace are also the people least likely to care about some extra bandwidth usa=
ge. For datacenter nodes, and for nodes doing lots of bandwidth, the bandwi=
dth is usually the biggest cost of running the node. For home users however=
, as long as they stay under their bandwidth cap, the bandwidth is actually=
free. Ideally, new nodes would be able to bootstrap from nodes that do not=
have to pay for their bandwidth, instead of needing to rely on a decreasin=
g percentage of heavy-duty archival nodes.<br><br></div><div>I have (perhap=
s incorrectly) identified disk space consumption as the most significant fa=
ctor in your average user choosing to run a pruned node or a lite client in=
stead of a full node. The average user is not typically too worried about b=
andwidth, and is also not typically too worried about initial blockchain do=
wnload time. But the 100GB hit to your disk space can be a huge psychologic=
al factor, especially if your hard drive only has 500GB available in the fi=
rst place, and 250+ GB is already consumed by other files you have.<br><br>=
</div><div>I believe that improving the disk usage situation would greatly =
benefit decentralization, especially if it could be done without putting pr=
essure on archival nodes.<br></div><div><br></div><div><b>Small Nodes Propo=
sal:</b><br><br></div><div>I propose an alternative to the pruned node that=
does not put undue pressure on archival nodes, and would be acceptable and=
non-risky to ship as a default in bitcoin-core. For lack of a better name,=
I'll call this new type of node a 'small node'. The intention =
is that bitcoin-core would eventually ship 'small nodes' by default=
, such that the expected amount of disk consumption drops from today's =
100+ GB to less than 30 GB.<br><br></div><div>My alternative proposal has t=
he following properties:<br><br></div><div>+ Full nodes only need to store =
~20% of the blockchain<br></div><div>+ With very high probability, a new no=
de will be able to recover the entire blockchain by connecting to 6 random =
small node peers.<br></div><div>+ An attacker that can eliminate a chosen+ =
95% of the full nodes running today will be unable to prevent new nodes fro=
m downloading the full blockchain, even if the attacker is also able to eli=
minate all archival nodes. (assuming all nodes today were small nodes inste=
ad of archival nodes)<br><br></div><div>Method:<br><br></div><div>A small n=
ode will pick an index [5, 256). This index is that node's permanent in=
dex. When storing a block, instead of storing the full block, the node will=
use Reed-Solomon coding to erasure code the block using a 5-of-256 scheme.=
The result will be 256 pieces that are 20% of the size of the block each. =
The node picks the piece that corresponds to its index, and stores that ins=
tead. (Indexes 0-4 are reserved for archival nodes - explained later)<br><b=
r></div><div>The node is now storing a fragment of every block. Alone, this=
fragment cannot be used to recover any piece of the blockchain. However, w=
hen paired with any 5 unique fragments (fragments of the same index will no=
t be unique), the full block can be recovered.<br><br></div><div>Nodes can =
optionally store more than 1 fragment each. At 5 fragments, the node become=
s a full archival node, and the chosen indexes should be 0-4. This is advan=
tageous for the archival node as the encoded data for the first 5 indexes w=
ill actually be identical to the block itself - there is no computational o=
verhead for selecting the first indexes. There is also no need to choose ra=
ndom indexes, because the full block can be recovered no matter which index=
es are chosen.<br><br></div><div>When connecting to new peers, the indexes =
of each peer needs to be known. Once peers totaling 5 unique indexes are di=
scovered, blockchain download can begin. Connecting to just 5 small node pe=
ers provides a >95% chance of getting 5 uniques, with exponentially impr=
oving odds of success as you connect to more peers. Connecting to a single =
archive node guarantees that any gaps can be filled.<br><br></div><div>A go=
od encoder should be able to turn a block into a 5-of-256 piece set in unde=
r 10 milliseconds using a single core on a standard consumer desktop. This =
should not slow down initial blockchain download substantially, though the =
overhead is more than a rounding error.<br></div><div><br></div><div><b>DoS=
Prevention:</b><br><br></div><div>A malicious node may provide garbage dat=
a instead of the actual piece. Given just the garbage data and 4 other corr=
ect pieces, it is impossible (best I know anyway) to tell which piece is th=
e garbage piece.<br><br></div><div>One option in this case would be to seek=
out an archival node that could verify the correctness of the pieces, and =
identify the malicious node.<br><br></div><div>Another option would be to h=
ave the small nodes store a cryptographic checksum of each piece. Obtaining=
the cryptographic checksum for all 256 pieces would incur a nontrivial amo=
unt of hashing (post segwit, as much as 100MB of extra hashing per block), =
and would require an additional ~4kb of storage per block. The hashing over=
head here may be prohibitive.<br><br></div><div>Another solution would be t=
o find additional pieces and brute-force combinations of 5 until a working =
combination was discovered. Though this sounds nasty, it should take less t=
han five seconds of computation to find the working combination given 5 cor=
rect pieces and 2 incorrect pieces. This computation only needs to be perfo=
rmed once to identify the malicious peers.<br><br></div><div>I also believe=
that alternative erasure coding schemes exist which actually are able to i=
dentify the bad pieces given sufficient good pieces, however I don't kn=
ow if they have the same computational performance as the best Reed-Solomon=
coding implementations.<br></div><br><div><b>Deployment:</b><br><br></div>=
<div>Small nodes are completely useless unless the critical mass of 5 piece=
s can be obtained. The first version that supports small node block downloa=
ds should default everyone to an archival node (meaning indexes 0-4 are use=
d)<br><br></div><div>Once there are enough small-node-enabled archive nodes=
, the default can be switched so that nodes only have a single index by def=
ault. In the first few days, when there are only a few small nodes, the pre=
viously-deployed archival nodes can help fill in the gaps, and the small no=
des can be useful for blockchain download right away.<br><br>--------------=
----------------<wbr>----<br><br></div><div>This represents a non-trivial a=
mount of code, but I believe that the result would be a non-trivial increas=
e in the percentage of users running full nodes, and a healthier overall ne=
twork.<br></div></div>
<br>______________________________<wbr>_________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
<wbr>linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wbr>org=
/mailman/listinfo/bitcoin-<wbr>dev</a><br>
<br></blockquote></div></div>
--001a11472d54d4fea5054d577ef8--
|