path: root/e6/d231dd14c069046533b31ffaa654cc308c8137

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