public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Sergio Lerner <sergiolerner@certimix.com>
To: Jeremy Spilman <jeremy@taplink.co>,
	 bitcoin-development <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] "network disruption as a service" and proof of local storage
Date: Thu, 26 Mar 2015 19:09:00 -0300	[thread overview]
Message-ID: <5514837C.4030905@certimix.com> (raw)
In-Reply-To: <op.xvzkt9nryldrnw@laptop-air>


> 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.





  reply	other threads:[~2015-03-26 22:21 UTC|newest]

Thread overview: 23+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2015-03-13 20:01 [Bitcoin-development] Criminal complaints against "network disruption as a service" startups Justus Ranvier
2015-03-13 21:48 ` Mike Hearn
2015-03-13 22:03   ` Justus Ranvier
2015-03-13 22:08     ` Mike Hearn
2015-03-13 22:16       ` Justus Ranvier
2015-03-13 22:24         ` Mike Hearn
2015-03-13 22:38           ` Justus Ranvier
2015-03-16  8:44   ` Jan Møller
2015-03-16 16:29     ` [Bitcoin-development] "network disruption as a service" and proof of local storage Sergio Lerner
2015-03-24  5:14       ` Jeremy Spilman
2015-03-26 22:09         ` Sergio Lerner [this message]
2015-03-26 23:04           ` Matt Whitlock
2015-03-27 14:32             ` Robert McKay
2015-03-27 15:16               ` Matt Whitlock
2015-03-27 15:32                 ` Robert McKay
     [not found]                 ` <20150327155730.GB20754@amethyst.visucore.com>
2015-03-27 16:00                   ` Matt Whitlock
2015-03-27 16:08                   ` Matt Whitlock
2015-03-27 18:40                 ` Jeremy Spilman
2015-04-01  2:34                   ` Sergio Lerner
2015-03-16 19:33     ` [Bitcoin-development] Criminal complaints against "network disruption as a service" startups Aaron Voisine
2015-03-23  2:44     ` odinn
2015-03-23 10:06 [Bitcoin-development] "network disruption as a service" and proof of local storage Thy Shizzle
2015-03-28  2:55 Thy Shizzle

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=5514837C.4030905@certimix.com \
    --to=sergiolerner@certimix.com \
    --cc=bitcoin-development@lists.sourceforge.net \
    --cc=jeremy@taplink.co \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox