From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192] helo=mx.sourceforge.net) by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1YbWDJ-0006bI-E0 for bitcoin-development@lists.sourceforge.net; Fri, 27 Mar 2015 15:30:25 +0000 X-ACL-Warn: Received: from resqmta-po-04v.sys.comcast.net ([96.114.154.163]) by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:AES128-SHA:128) (Exim 4.76) id 1YbWDH-0003WT-LN for bitcoin-development@lists.sourceforge.net; Fri, 27 Mar 2015 15:30:25 +0000 Received: from resomta-po-08v.sys.comcast.net ([96.114.154.232]) by resqmta-po-04v.sys.comcast.net with comcast id 8fGQ1q004516pyw01fGnLG; Fri, 27 Mar 2015 15:16:47 +0000 Received: from crushinator.localnet ([IPv6:2601:6:4800:47f:1e4e:1f4d:332c:3bf6]) by resomta-po-08v.sys.comcast.net with comcast id 8fGk1q00G2JF60R01fGlLh; Fri, 27 Mar 2015 15:16:46 +0000 From: Matt Whitlock To: bitcoin-development@lists.sourceforge.net Date: Fri, 27 Mar 2015 11:16:43 -0400 Message-ID: <2210650.iUsfZECcCc@crushinator> User-Agent: KMail/4.14.6 (Linux/3.18.7-gentoo; KDE/4.14.6; x86_64; ; ) In-Reply-To: References: <55034205.4030607@localhost.local> <7854077.3GbzoT9yL1@crushinator> MIME-Version: 1.0 Content-Transfer-Encoding: 7Bit Content-Type: text/plain; charset="us-ascii" X-Spam-Score: 0.0 (/) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -0.0 RCVD_IN_DNSWL_NONE RBL: Sender listed at http://www.dnswl.org/, no trust [96.114.154.163 listed in list.dnswl.org] 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: 1YbWDH-0003WT-LN 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: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 27 Mar 2015 15:30:25 -0000 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