diff options
| author | Robert McKay <robert@mckay.com> | 2015-03-27 14:32:33 +0000 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2015-03-27 14:57:15 +0000 |
| commit | ca11dbf39a9fe4f730035766c84aad3fe36ab383 (patch) | |
| tree | f143ef33880045593f2829d9ed88a2cf6662bc7f | |
| parent | 236a1df69619cbc53982264df0f771b487ceca4f (diff) | |
| download | pi-bitcoindev-ca11dbf39a9fe4f730035766c84aad3fe36ab383.tar.gz pi-bitcoindev-ca11dbf39a9fe4f730035766c84aad3fe36ab383.zip | |
Re: [Bitcoin-development] "network disruption as a service" and proof of local storage
| -rw-r--r-- | e6/d231dd14c069046533b31ffaa654cc308c8137 | 228 |
1 files changed, 228 insertions, 0 deletions
diff --git a/e6/d231dd14c069046533b31ffaa654cc308c8137 b/e6/d231dd14c069046533b31ffaa654cc308c8137 new file mode 100644 index 000000000..dfcc26875 --- /dev/null +++ b/e6/d231dd14c069046533b31ffaa654cc308c8137 @@ -0,0 +1,228 @@ +Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193] + helo=mx.sourceforge.net) + by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) + (envelope-from <robert@mckay.com>) id 1YbVhD-0006gL-IS + for bitcoin-development@lists.sourceforge.net; + Fri, 27 Mar 2015 14:57:15 +0000 +Received-SPF: pass (sog-mx-3.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-3.v43.ch3.sourceforge.com with esmtps (TLSv1:AES128-SHA:128) + (Exim 4.76) id 1YbVhB-0003Iq-JC + for bitcoin-development@lists.sourceforge.net; + Fri, 27 Mar 2015 14:57:15 +0000 +Received: from www-data by mail.mckay.com with local (Exim 4.80) + (envelope-from <robert@mckay.com>) id 1YbVJJ-0004Dr-TA + for bitcoin-development@lists.sourceforge.net; + Fri, 27 Mar 2015 14:32:33 +0000 +To: <bitcoin-development@lists.sourceforge.net> +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 14:32:33 +0000 +From: Robert McKay <robert@mckay.com> +In-Reply-To: <7854077.3GbzoT9yL1@crushinator> +References: <55034205.4030607@localhost.local> + <op.xvzkt9nryldrnw@laptop-air> <5514837C.4030905@certimix.com> + <7854077.3GbzoT9yL1@crushinator> +Message-ID: <f903ef03dc8bb30873e0bbbb9b3786e9@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: 1YbVhB-0003Iq-JC +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 14:57:15 -0000 + +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 + + + |