From mboxrd@z Thu Jan 1 00:00:00 1970 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 ) 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 ) id 1YbWF3-0004uP-J2; Fri, 27 Mar 2015 15:32:13 +0000 To: Matt Whitlock 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 In-Reply-To: <2210650.iUsfZECcCc@crushinator> References: <55034205.4030607@localhost.local> <7854077.3GbzoT9yL1@crushinator> <2210650.iUsfZECcCc@crushinator> Message-ID: 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: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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