From mboxrd@z Thu Jan 1 00:00:00 1970 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 ) id 1YaI7J-0007Lr-KL for bitcoin-development@lists.sourceforge.net; Tue, 24 Mar 2015 06:15:09 +0000 Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of taplink.co designates 50.117.27.232 as permitted sender) client-ip=50.117.27.232; envelope-from=jeremy@taplink.co; helo=mail.taplink.co; Received: from mail.taplink.co ([50.117.27.232]) by sog-mx-3.v43.ch3.sourceforge.com with esmtps (TLSv1:AES128-SHA:128) (Exim 4.76) id 1YaI7I-0000YQ-78 for bitcoin-development@lists.sourceforge.net; Tue, 24 Mar 2015 06:15:09 +0000 Received: from laptop-air (c-76-21-80-35.hsd1.ca.comcast.net [76.21.80.35]) by mail.taplink.co with ESMTPSA (version=TLSv1 cipher=DHE-RSA-AES256-SHA bits=256) ; Mon, 23 Mar 2015 22:14:33 -0700 Content-Type: text/plain; charset=iso-8859-15; format=flowed; delsp=yes To: bitcoin-development@lists.sourceforge.net References: <55034205.4030607@localhost.local> <550704CF.2000808@certimix.com> Date: Mon, 23 Mar 2015 22:14:23 -0700 MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: "Jeremy Spilman" Organization: TapLink Message-ID: In-Reply-To: <550704CF.2000808@certimix.com> User-Agent: Opera Mail/1.0 (Win32) 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: 1YaI7I-0000YQ-78 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: Tue, 24 Mar 2015 06:15:09 -0000 On Mon, 16 Mar 2015 09:29:03 -0700, Sergio Lerner wrote: > I proposed a (what I think) is better protocol for Proof of Storage that > I call "Proof of Local storage" here > https://bitslog.wordpress.com/2014/11/03/proof-of-local-blockchain-storage/ Thanks so much for publishing this. It could be useful in any application to try to prove a keyed copy of some data. 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. The verifier keeps blocks in the keyed format, and can decrypt quickly to provide raw data, or use the keyed data for hashing to try to demonstrate they have a pre-keyed copy. > > 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? > 2. (prover pay a high cost, verified pays negligible cost). The verifier > chooses a seed n, and then pre-computes the encrypted blocks derived > from the seed using the prover's IP. Then the verifier sends the seed, > and the prover must respond with the hash of the encrypted blocks within > a certain time bound. The proved does not require to do any PH > decryption, just take the encrypted blocks for indexes derived from the > seed, hash them and send the hash back to the verifier. The verifier > validates the time bound and the hash. The challenger requests a hash-sum of a random sequence of indices of the keyed data, based on a challenge seed. So in a few bytes round-trip we can see how fast the computation is completed. If the data is already keyed, the hash of 1,000 random 1024-bit blocks should come back much faster than if the data needs to be keyed on-the-fly. To verify the response, the challenger would have to use the peer's identity key and perform the slower transforms on those same 1,000 blocks and see that the result matches, so cost to challenger is higher than prover, assuming they actually do the computation. Which brings up a good tweak, a full-node challenger could have to do the computation first, then also include something like HMAC(identityKey, expectedResult). The prover could then know if the challenger was honest before returning a result, and blacklist them if not. > > Both protocols can me made available by the client, under different > states. For instance, new nodes are only allowed to request protocol 2 > (and so they get an initial assurance their are connecting to > full-nodes). After a first-time mutual authentication, they are allowed > to periodically perform protocol 1. Also new nodes may be allowed to > perform protocol 1 with a small index set, and increase the index set > over time, to get higher confidence. I guess a new-node could see if different servers all returned the same challenge response, but they would have no way to know if the challenge response was technically correct, or sybil. 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.