summaryrefslogtreecommitdiff
path: root/c5/ebed89920ee4ae5b75a052cb173dda62874556
blob: 4a01e0a6b6d6b98ae7f7ae6b907ec9d4a8705434 (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
Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191]
	helo=mx.sourceforge.net)
	by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
	(envelope-from <robert@mckay.com>) id 1YbWEZ-0000Zt-6s
	for bitcoin-development@lists.sourceforge.net;
	Fri, 27 Mar 2015 15:31:43 +0000
Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of mckay.com
	designates 37.1.88.131 as permitted sender)
	client-ip=37.1.88.131; envelope-from=robert@mckay.com;
	helo=mail.mckay.com; 
Received: from mail.mckay.com ([37.1.88.131])
	by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:AES128-SHA:128)
	(Exim 4.76) id 1YbWEX-0003St-H1
	for bitcoin-development@lists.sourceforge.net;
	Fri, 27 Mar 2015 15:31:43 +0000
Received: from www-data by mail.mckay.com with local (Exim 4.80)
	(envelope-from <robert@mckay.com>)
	id 1YbWF3-0004uP-J2; Fri, 27 Mar 2015 15:32:13 +0000
To: Matt Whitlock <bip@mattwhitlock.name>
X-PHP-Originating-Script: 0:main.inc
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8;
 format=flowed
Content-Transfer-Encoding: 7bit
Date: Fri, 27 Mar 2015 15:32:13 +0000
From: Robert McKay <robert@mckay.com>
In-Reply-To: <2210650.iUsfZECcCc@crushinator>
References: <55034205.4030607@localhost.local> <7854077.3GbzoT9yL1@crushinator>
	<f903ef03dc8bb30873e0bbbb9b3786e9@webmail.mckay.com>
	<2210650.iUsfZECcCc@crushinator>
Message-ID: <af66c470d2072242338ed8b08e1fc644@webmail.mckay.com>
X-Sender: robert@mckay.com
User-Agent: Roundcube Webmail/0.7.2
X-Spam-Score: -1.6 (-)
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 T_RP_MATCHES_RCVD Envelope sender domain matches handover relay
	domain
	-0.0 SPF_PASS               SPF: sender matches SPF record
	-0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from
	author's domain
	0.1 DKIM_SIGNED            Message has a DKIM or DK signature,
	not necessarily valid
	-0.1 DKIM_VALID Message has at least one valid DKIM or DK signature
X-Headers-End: 1YbWEX-0003St-H1
Cc: bitcoin-development@lists.sourceforge.net
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: Fri, 27 Mar 2015 15:31:43 -0000

The main motivation is to try and stop a single entity running lots of 
nodes in order to harvest transaction origin IPs. That's what's behind 
this.

Probably the efforts are a waste of time.. if someone has to keep a few 
hundred copies of the blockchain around in order to keep IP specific 
precomputed data around for all the IPs they listen on then they'll just 
buy a handful of 5TB HDs and call it a day.. still some of the ideas 
proposed are quite interesting and might not have much downside.

Rob


On 2015-03-27 15:16, Matt Whitlock wrote:
> I agree that someone could do this, but why is that a problem? Isn't
> the goal of this exercise to ensure more full nodes on the network? 
> In
> order to be able to answer the challenges, an entity would need to be
> running a full node somewhere. Thus, they have contributed at least
> one additional full node to the network. I could certainly see a case
> for a company to host hundreds of lightweight (e.g., EC2) servers all
> backed by a single copy of the block chain. Why force every single
> machine to have its own copy? All you really need to require is that
> each agency/participant have its own copy.
>
>
> On Friday, 27 March 2015, at 2:32 pm, Robert McKay wrote:
>> Basically the problem with that is that someone could setup a single
>> full node that has the blockchain and can answer those challenges 
>> and
>> then a bunch of other non-full nodes that just proxy any such 
>> challenges
>> to the single full node.
>>
>> Rob
>>
>> On 2015-03-26 23:04, Matt Whitlock wrote:
>> > Maybe I'm overlooking something, but I've been watching this 
>> thread
>> > with increasing skepticism at the complexity of the offered 
>> solution.
>> > I don't understand why it needs to be so complex. I'd like to 
>> offer
>> > an
>> > alternative for your consideration...
>> >
>> > Challenge:
>> > "Send me: SHA256(SHA256(concatenation of N pseudo-randomly 
>> selected
>> > bytes from the block chain))."
>> >
>> > Choose N such that it would be infeasible for the responding node 
>> to
>> > fetch all of the needed blocks in a short amount of time. In other
>> > words, assume that a node can seek to a given byte in a block 
>> stored
>> > on local disk much faster than it can download the entire block 
>> from
>> > a
>> > remote peer. This is almost certainly a safe assumption.
>> >
>> > For example, choose N = 1024. Then the proving node needs to 
>> perform
>> > 1024 random reads from local disk. On spinning media, this is 
>> likely
>> > to take somewhere on the order of 15 seconds. Assuming blocks are
>> > averaging 500 KiB each, then 1024 blocks would comprise 500 MiB of
>> > data. Can 500 MiB be downloaded in 15 seconds? This data transfer
>> > rate
>> > is 280 Mbps. Almost certainly not possible. And if it is, just
>> > increase N. The challenge also becomes more difficult as average
>> > block
>> > size increases.
>> >
>> > This challenge-response protocol relies on the lack of a "partial
>> > getdata" command in the Bitcoin protocol: a node cannot ask for 
>> only
>> > part of a block; it must ask for an entire block. Furthermore, 
>> nodes
>> > could ban other nodes for making too many random requests for 
>> blocks.
>> >
>> >
>> > On Thursday, 26 March 2015, at 7:09 pm, Sergio Lerner wrote:
>> >>
>> >> > If I understand correctly, transforming raw blocks to keyed 
>> blocks
>> >> > takes 512x longer than transforming keyed blocks back to raw. 
>> The
>> >> key
>> >> > is public, like the IP, or some other value which perhaps 
>> changes
>> >> less
>> >> > frequently.
>> >> >
>> >> Yes. I was thinking that the IP could be part of a first layer of
>> >> encryption done to the blockchain data prior to the asymetric
>> >> operation.
>> >> That way the asymmetric operation can be the same for all users 
>> (no
>> >> different primers for different IPs, and then the verifiers does 
>> not
>> >> have to verify that a particular p is actually a pseudo-prime
>> >> suitable
>> >> for P.H. ) and the public exponent can be just 3.
>> >>
>> >> >
>> >> >> 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, 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.
>> >> >>
>> >> >
>> >> > Can you clarify, the prover is hashing random blocks of
>> >> *decrypted*,
>> >> > as-in raw, blockchain data? What does this prove other than,
>> >> perhaps,
>> >> > fast random IO of the blockchain? (which is useful in its own
>> >> right,
>> >> > e.g. as a way to ensure only full-node IO-bound mining if baked
>> >> into
>> >> > the PoW)
>> >> >
>> >> > How is the verifier validating the response without possession 
>> of
>> >> the
>> >> > full blockchain?
>> >>
>> >> You're right, It is incorrect. Not the decrypted blocks must be
>> >> sent,
>> >> but the encrypted blocks. There correct protocol is this:
>> >>
>> >> 1. (prover and verifier pay a small cost) The verifier sends a 
>> seed
>> >> to
>> >> derive some n random indexes, and the prover must respond with 
>> the
>> >> the
>> >> encrypted blocks within a certain time bound. The verifier 
>> decrypts
>> >> those blocks to check if they are part of the block-chain.
>> >>
>> >> But then there is this improvement which allows the verifier do
>> >> detect
>> >> non full-nodes with much less computation:
>> >>
>> >> 3. (prover pays a small cost, verifier smaller cost) The verifier
>> >> asks
>> >> the prover to send a Merkle tree root of hashes of encrypted 
>> blocks
>> >> with
>> >> N indexes selected by a psudo-random function seeded by a 
>> challenge
>> >> value, where each encrypted-block is previously prefixed with the
>> >> seed
>> >> before being hashed (e.g. N=100). The verifier receives the 
>> Markle
>> >> Root
>> >> and performs a statistical test on the received information. From
>> >> the N
>> >> hashes blocks, it chooses M < N (e.g. M = 20), and asks the 
>> proved
>> >> for
>> >> the blocks at these indexes. The prover sends the blocks, the
>> >> verifier
>> >> validates the blocks by decrypting them and also verifies that 
>> the
>> >> Merkle tree was well constructed for those block nodes. This 
>> proves
>> >> with
>> >> high probability that the Merkle tree was built on-the-fly and
>> >> specifically for this challenge-response protocol.
>> >>
>> >> > I also wonder about the effect of spinning disk versus SSD. 
>> Seek
>> >> time
>> >> > for 1,000 random reads is either nearly zero or dominating
>> >> depending
>> >> > on the two modes. I wonder if a sequential read from a random
>> >> index is
>> >> > a possible trade-off,; it doesn't prove possession of the whole
>> >> chain
>> >> > nearly as well, but at least iowait converges significantly. 
>> Then
>> >> > again, that presupposes a specific ordering on disk which might
>> >> not
>> >> > exist. In X years it will all be solid-state, so eventually 
>> it's
>> >> moot.
>> >> >
>> >> Good idea.
>> >>
>> >> Also we don't need that every node implements the protocol, but 
>> only
>> >> nodes that want to prove full-node-ness, such as the ones which 
>> want
>> >> to
>> >> receive bitnodes subsidy.
>> >
>> >
>> >
>> > 
>> ------------------------------------------------------------------------------
>> > Dive into the World of Parallel Programming The Go Parallel 
>> Website,
>> > sponsored
>> > by Intel and developed in partnership with Slashdot Media, is your
>> > hub for all
>> > things parallel software development, from weekly thought 
>> leadership
>> > blogs to
>> > news, videos, case studies, 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
>>
>>
>> 
>> ------------------------------------------------------------------------------
>> Dive into the World of Parallel Programming The Go Parallel Website, 
>> sponsored
>> by Intel and developed in partnership with Slashdot Media, is your 
>> hub for all
>> things parallel software development, from weekly thought leadership 
>> blogs to
>> news, videos, case studies, 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