summaryrefslogtreecommitdiff
path: root/35/9ee57b07b58599b2624057a6294d5a7f50c3b1
blob: 366dc6fee8c0fd7300bdf195558091922cbb25d4 (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
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
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194]
	helo=mx.sourceforge.net)
	by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
	(envelope-from <thyshizzle@outlook.com>) id 1YZzGF-00081R-Cw
	for bitcoin-development@lists.sourceforge.net;
	Mon, 23 Mar 2015 10:07:07 +0000
Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of outlook.com
	designates 65.55.34.12 as permitted sender)
	client-ip=65.55.34.12; envelope-from=thyshizzle@outlook.com;
	helo=COL004-OMC1S2.hotmail.com; 
Received: from col004-omc1s2.hotmail.com ([65.55.34.12])
	by sog-mx-4.v43.ch3.sourceforge.com with esmtps (TLSv1:AES256-SHA:256)
	(Exim 4.76) id 1YZzGD-00053g-7s
	for bitcoin-development@lists.sourceforge.net;
	Mon, 23 Mar 2015 10:07:07 +0000
Received: from COL401-EAS404 ([65.55.34.7]) by COL004-OMC1S2.hotmail.com over
	TLS secured channel with Microsoft SMTPSVC(7.5.7601.22751); 
	Mon, 23 Mar 2015 03:06:58 -0700
X-TMN: [STWWraZ8xonjUijGmeik/jd9Hrv4GP8C]
X-Originating-Email: [thyshizzle@outlook.com]
Message-ID: <COL401-EAS404372A396B2C168521E5DCC20D0@phx.gbl>
Content-Type: multipart/alternative;
	boundary="_736f674a-abbd-4e9c-b0dc-604efc5db805_"
MIME-Version: 1.0
To: Sergio Lerner <sergiolerner@certimix.com>,
	<bitcoin-development@lists.sourceforge.net>
From: Thy Shizzle <thyshizzle@outlook.com>
Date: Mon, 23 Mar 2015 21:06:48 +1100
X-OriginalArrivalTime: 23 Mar 2015 10:06:58.0892 (UTC)
	FILETIME=[198928C0:01D06551]
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
	(thyshizzle[at]outlook.com)
	-0.0 SPF_PASS               SPF: sender matches SPF record
	-0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at http://www.dnswl.org/,
	no trust [65.55.34.12 listed in list.dnswl.org]
	1.0 HTML_MESSAGE           BODY: HTML included in message
	-0.2 AWL AWL: Adjusted score from AWL reputation of From: address
X-Headers-End: 1YZzGD-00053g-7s
Subject: Re: [Bitcoin-development] "network disruption as a service" and
 proof	of local storage
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, 23 Mar 2015 10:07:07 -0000

--_736f674a-abbd-4e9c-b0dc-604efc5db805_
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset="utf-8"

Wow=2C that's quite impressive. But what comes to my mind is if such an ext=
ravagant solution really need to be implemented regarding proof of storage?=
 I mean=2C my idea whilst building my node was to do something along the li=
nes of "tell me what you got" i.e get block height from the version message=
=2C and then fire off your getblock=2C getdata etc and simply if a node doe=
s not respond with the requested data after a few attempts=2C we disconnect=
  and perhaps blacklist until the  node restarts or something. I am of cour=
se purely looking at it from the perspective of useless nodes consuming con=
nection slots=2C there may be other scenarios where you require proof of st=
orage that I am not considering. I just think that simple blacklist rules c=
ould easily avoid this without the extra resource usage? I mean if you star=
t doing encryption for every task then before you know it you need to dedic=
ate all your cpu to the node! Especially for tasks that are not mission cri=
tical or require verification=2C I mean useless nodes are more of an annoya=
nce with the potential to disrupt the network=2C slow it down=2C but not co=
mpromise it=2C so I shouldn't think it would be something that you would tu=
rn to encryption for right? I feel this anyway.
________________________________
From: Sergio Lerner<mailto:sergiolerner@certimix.com>
Sent: =E2=80=8E17/=E2=80=8E03/=E2=80=8E2015 3:45 AM
To: bitcoin-development@lists.sourceforge.net<mailto:bitcoin-development@li=
sts.sourceforge.net>
Subject: [Bitcoin-development] "network disruption as a service" and proof =
of local storage

The problem of pseudo-nodes will come over and over. The cat and mouse
chase is just beginning.
It has been discussed some times that the easiest solution world be to
request some kind of resource consumption on each peer to be allowed to
connect to other peers.
Gmaxwell proposed Proof of Storage here:
https://bitcointalk.org/index.php?topic=3D310323.msg3332919#msg3332919

I proposed a (what I think) is better protocol for Proof of Storage that
I call "Proof of Local storage" here
https://bitslog.wordpress.com/2014/11/03/proof-of-local-blockchain-storage/
. It's better because it does not need the storage of additional data=2C
but more importantly=2C it allows you to prove full copy of the blockchain
is being maintained by the peer.
This is specially important now that Bitnodes is trying a full-node
incentive program that may be easily cheated
(http://qntra.net/2015/02/pseudonode-proxy-fools-bitcoin-full-node-incentiv=
e-program/)

Proof of local storage allows a node to prove another peer that he is
storing a LOCAL copy of a PUBLIC file=2C such as the blockchain. So the
peer need not waste more resources (well=2C just some resources to
encode/decode the block-chain).
The main idea is to use what I called asymmetric-time-encoding.
Basically you encode the block-chain in a way that it takes 100 more
times to write it than to read it. Since the block-chain is an
append-only (write-only) file=2C this fit good for our needs. For instance
(and as a simplification)=2C choosing a global 1024-bit prime=2C then
splitting the block-chain in 1024-bit blocks=2C and encrypting each block
using Polihg-Hellman (modexp) with decryption exponent 3.  Then
encryption is at least 100 times slower than decryption. Before PH
encryption each node must xor each block with a pseudo-random mask
derived from the public IP and the block index.  So block encryption
could be:
BlockEncryptIndex(i) =3D E(IP+i=2Cblock(i))^inv(3) (mod p)=2C

where inv(3) is 3^-1 mod (p-1). E() could be a fast tweaked encryption
routine (tweak =3D index)=2C but we only need the PRNG properties of E() an=
d
that E() does share algebraic properties with P.H..

Two protocols can be performed to prove local possession:
1. (prover and verifier pay a small cost) The verifier sends a seed to
derive some n random indexes=2C and the prover must respond with the hash
of the decrypted blocks within a certain time bound. Suppose that
decryption of n blocks take 100 msec (+-100 msec of network jitter).
Then an attacker must have a computer 50 faster to be able to
consistently cheat. The last 50 blocks should not be part of the list to
allow nodes to catch-up and encrypt the blocks in background.

2. (prover pay a high cost=2C verified pays negligible cost). The verifier
chooses a seed n=2C and then pre-computes the encrypted blocks derived
from the seed using the prover's IP. Then the verifier sends the  seed=2C
and the prover must respond with the hash of the encrypted blocks within
a certain time bound. The proved does not require to do any PH
decryption=2C just take the encrypted blocks for indexes derived from the
seed=2C hash them and send the hash back to the verifier. The verifier
validates the time bound and the hash.

Both protocols can me made available by the client=2C under different
states. For instance=2C new nodes are only allowed to request protocol 2
(and so they get an initial assurance their are connecting to
full-nodes). After a first-time mutual authentication=2C they are allowed
to periodically perform protocol 1. Also new nodes may be allowed to
perform protocol 1 with a small index set=2C and increase the index set
over time=2C to get higher confidence.

The important difference between this protocol and classical remote
software attestation protocols=2C is that the time gap between a good peer
and a malicious peer can be made arbitrarily high=2C picking a larger p.
Maybe there is even another crypto primitive which is more asymmetric
than exponent 3 decryption (the LUC or NTRU cryptosystem?).

In GMaxwell proposal each peer builds a table for each other peer. In my
proposal=2C each peer builds a single table (the encrypted blockchain)=2C s=
o
it could be still possible to establish a thousands of connections to
the network from a single peer. Nevertheless=2C the attacker's IP will be
easily detected (he cannot hide under a thousands different IPs). It's
also possible to restrict the challenge-response to a portion of the
block-chain=2C the portion offset being derived from the hash of both IP
addresses and one random numbers provided by each peer. Suppose each
connection has a C-R space equivalent to 1% of the block-chain. Then
having 100 connections and responding to C-R on each connection means
storing approximate 1 copy of the block-chain (there may be overlaps=2C
which would need to be stored twice) =2C while having 1K connections would
require storing 10 copies of the blockchain.


Best regards=2C
 Sergio


---------------------------------------------------------------------------=
---
Dive into the World of Parallel Programming The Go Parallel Website=2C spon=
sored
by Intel and developed in partnership with Slashdot Media=2C is your hub fo=
r all
things parallel software development=2C from weekly thought leadership blog=
s to
news=2C videos=2C case studies=2C tutorials and more. Take a look and join =
the
conversation now. http://goparallel.sourceforge.net/
_______________________________________________
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

--_736f674a-abbd-4e9c-b0dc-604efc5db805_
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html; charset="utf-8"

<html>
<head>
<meta http-equiv=3D"Content-Type" content=3D"text/html=3B charset=3Dutf-8">
</head>
<body>
<div>
<div style=3D"font-family: Calibri=2Csans-serif=3B font-size: 11pt=3B">Wow=
=2C that's quite impressive. But what comes to my mind is if such an extrav=
agant solution really need to be implemented regarding proof of storage? I =
mean=2C my idea whilst building my node was to
 do something along the lines of &quot=3Btell me what you got&quot=3B i.e g=
et block height from the version message=2C and then fire off your getblock=
=2C getdata etc and simply if a node does not respond with the requested da=
ta after a few attempts=2C we disconnect&nbsp=3B and perhaps
 blacklist until the&nbsp=3B node restarts or something. I am of course pur=
ely looking at it from the perspective of useless nodes consuming connectio=
n slots=2C there may be other scenarios where you require proof of storage =
that I am not considering. I just think that
 simple blacklist rules could easily avoid this without the extra resource =
usage? I mean if you start doing encryption for every task then before you =
know it you need to dedicate all your cpu to the node! Especially for tasks=
 that are not mission critical or
 require verification=2C I mean useless nodes are more of an annoyance with=
 the potential to disrupt the network=2C slow it down=2C but not compromise=
 it=2C so I shouldn't think it would be something that you would turn to en=
cryption for right? I feel this anyway.</div>
</div>
<div dir=3D"ltr">
<hr>
<span style=3D"font-family: Calibri=2Csans-serif=3B font-size: 11pt=3B font=
-weight: bold=3B">From:
</span><span style=3D"font-family: Calibri=2Csans-serif=3B font-size: 11pt=
=3B"><a href=3D"mailto:sergiolerner@certimix.com">Sergio Lerner</a></span><=
br>
<span style=3D"font-family: Calibri=2Csans-serif=3B font-size: 11pt=3B font=
-weight: bold=3B">Sent:
</span><span style=3D"font-family: Calibri=2Csans-serif=3B font-size: 11pt=
=3B">=E2=80=8E17/=E2=80=8E03/=E2=80=8E2015 3:45 AM</span><br>
<span style=3D"font-family: Calibri=2Csans-serif=3B font-size: 11pt=3B font=
-weight: bold=3B">To:
</span><span style=3D"font-family: Calibri=2Csans-serif=3B font-size: 11pt=
=3B"><a href=3D"mailto:bitcoin-development@lists.sourceforge.net">bitcoin-d=
evelopment@lists.sourceforge.net</a></span><br>
<span style=3D"font-family: Calibri=2Csans-serif=3B font-size: 11pt=3B font=
-weight: bold=3B">Subject:
</span><span style=3D"font-family: Calibri=2Csans-serif=3B font-size: 11pt=
=3B">[Bitcoin-development] &quot=3Bnetwork disruption as a service&quot=3B =
and proof of local storage</span><br>
<br>
</div>
<div class=3D"BodyFragment">
<div class=3D"PlainText">The problem of pseudo-nodes will come over and ove=
r. The cat and mouse<br>
chase is just beginning.<br>
It has been discussed some times that the easiest solution world be to<br>
request some kind of resource consumption on each peer to be allowed to<br>
connect to other peers.<br>
Gmaxwell proposed Proof of Storage here:<br>
<a href=3D"https://bitcointalk.org/index.php?topic=3D310323.msg3332919#msg3=
332919">https://bitcointalk.org/index.php?topic=3D310323.msg3332919#msg3332=
919</a><br>
<br>
I proposed a (what I think) is better protocol for Proof of Storage that<br=
>
I call &quot=3BProof of Local storage&quot=3B here<br>
<a href=3D"https://bitslog.wordpress.com/2014/11/03/proof-of-local-blockcha=
in-storage/">https://bitslog.wordpress.com/2014/11/03/proof-of-local-blockc=
hain-storage/</a><br>
. It's better because it does not need the storage of additional data=2C<br=
>
but more importantly=2C it allows you to prove full copy of the blockchain<=
br>
is being maintained by the peer.<br>
This is specially important now that Bitnodes is trying a full-node<br>
incentive program that may be easily cheated<br>
(<a href=3D"http://qntra.net/2015/02/pseudonode-proxy-fools-bitcoin-full-no=
de-incentive-program/">http://qntra.net/2015/02/pseudonode-proxy-fools-bitc=
oin-full-node-incentive-program/</a>)<br>
<br>
Proof of local storage allows a node to prove another peer that he is<br>
storing a LOCAL copy of a PUBLIC file=2C such as the blockchain. So the<br>
peer need not waste more resources (well=2C just some resources to<br>
encode/decode the block-chain).<br>
The main idea is to use what I called asymmetric-time-encoding.<br>
Basically you encode the block-chain in a way that it takes 100 more<br>
times to write it than to read it. Since the block-chain is an<br>
append-only (write-only) file=2C this fit good for our needs. For instance<=
br>
(and as a simplification)=2C choosing a global 1024-bit prime=2C then<br>
splitting the block-chain in 1024-bit blocks=2C and encrypting each block<b=
r>
using Polihg-Hellman (modexp) with decryption exponent 3.&nbsp=3B Then<br>
encryption is at least 100 times slower than decryption. Before PH<br>
encryption each node must xor each block with a pseudo-random mask<br>
derived from the public IP and the block index.&nbsp=3B So block encryption=
<br>
could be: <br>
BlockEncryptIndex(i) =3D E(IP&#43=3Bi=2Cblock(i))^inv(3) (mod p)=2C<br>
<br>
where inv(3) is 3^-1 mod (p-1). E() could be a fast tweaked encryption<br>
routine (tweak =3D index)=2C but we only need the PRNG properties of E() an=
d<br>
that E() does share algebraic properties with P.H..<br>
<br>
Two protocols can be performed to prove local possession:<br>
1. (prover and verifier pay a small cost) The verifier sends a seed to<br>
derive some n random indexes=2C and the prover must respond with the hash<b=
r>
of the decrypted blocks within a certain time bound. Suppose that<br>
decryption of n blocks take 100 msec (&#43=3B-100 msec of network jitter).<=
br>
Then an attacker must have a computer 50 faster to be able to<br>
consistently cheat. The last 50 blocks should not be part of the list to<br=
>
allow nodes to catch-up and encrypt the blocks in background.<br>
<br>
2. (prover pay a high cost=2C verified pays negligible cost). The verifier<=
br>
chooses a seed n=2C and then pre-computes the encrypted blocks derived<br>
from the seed using the prover's IP. Then the verifier sends the&nbsp=3B se=
ed=2C<br>
and the prover must respond with the hash of the encrypted blocks within<br=
>
a certain time bound. The proved does not require to do any PH<br>
decryption=2C just take the encrypted blocks for indexes derived from the<b=
r>
seed=2C hash them and send the hash back to the verifier. The verifier<br>
validates the time bound and the hash.<br>
<br>
Both protocols can me made available by the client=2C under different<br>
states. For instance=2C new nodes are only allowed to request protocol 2<br=
>
(and so they get an initial assurance their are connecting to<br>
full-nodes). After a first-time mutual authentication=2C they are allowed<b=
r>
to periodically perform protocol 1. Also new nodes may be allowed to<br>
perform protocol 1 with a small index set=2C and increase the index set<br>
over time=2C to get higher confidence.<br>
<br>
The important difference between this protocol and classical remote<br>
software attestation protocols=2C is that the time gap between a good peer<=
br>
and a malicious peer can be made arbitrarily high=2C picking a larger p.<br=
>
Maybe there is even another crypto primitive which is more asymmetric<br>
than exponent 3 decryption (the LUC or NTRU cryptosystem?).<br>
<br>
In GMaxwell proposal each peer builds a table for each other peer. In my<br=
>
proposal=2C each peer builds a single table (the encrypted blockchain)=2C s=
o<br>
it could be still possible to establish a thousands of connections to<br>
the network from a single peer. Nevertheless=2C the attacker's IP will be<b=
r>
easily detected (he cannot hide under a thousands different IPs). It's<br>
also possible to restrict the challenge-response to a portion of the<br>
block-chain=2C the portion offset being derived from the hash of both IP<br=
>
addresses and one random numbers provided by each peer. Suppose each<br>
connection has a C-R space equivalent to 1% of the block-chain. Then<br>
having 100 connections and responding to C-R on each connection means<br>
storing approximate 1 copy of the block-chain (there may be overlaps=2C<br>
which would need to be stored twice) =2C while having 1K connections would<=
br>
require storing 10 copies of the blockchain.<br>
<br>
<br>
Best regards=2C<br>
&nbsp=3BSergio<br>
<br>
<br>
---------------------------------------------------------------------------=
---<br>
Dive into the World of Parallel Programming The Go Parallel Website=2C spon=
sored<br>
by Intel and developed in partnership with Slashdot Media=2C is your hub fo=
r all<br>
things parallel software development=2C from weekly thought leadership blog=
s to<br>
news=2C videos=2C case studies=2C tutorials and more. Take a look and join =
the <br>
conversation now. <a href=3D"http://goparallel.sourceforge.net/">http://gop=
arallel.sourceforge.net/</a><br>
_______________________________________________<br>
Bitcoin-development mailing list<br>
Bitcoin-development@lists.sourceforge.net<br>
<a href=3D"https://lists.sourceforge.net/lists/listinfo/bitcoin-development=
">https://lists.sourceforge.net/lists/listinfo/bitcoin-development</a><br>
</div>
</div>
</body>
</html>

--_736f674a-abbd-4e9c-b0dc-604efc5db805_--