1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
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 <jeremy@taplink.co>) 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>
<CANEZrP2OM6BrEsgqe5j23qaZp7wypOFJOZf+cNuMMe12WBv8LA@mail.gmail.com>
<CABh=4qNwRqb3f+AM-PKB0F+Kaw02tAq2DsqLmeO87XxXZvTd4Q@mail.gmail.com>
<550704CF.2000808@certimix.com>
Date: Mon, 23 Mar 2015 22:14:23 -0700
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
From: "Jeremy Spilman" <jeremy@taplink.co>
Organization: TapLink
Message-ID: <op.xvzkt9nryldrnw@laptop-air>
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: <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: Tue, 24 Mar 2015 06:15:09 -0000
On Mon, 16 Mar 2015 09:29:03 -0700, Sergio Lerner
<sergiolerner@certimix.com> 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.
|
