[tahoe-dev] "Elk Point" design for mutable, add-only, and immutable files

[David-Sarah Hopwood]

David-Sarah Hopwood wrote:
> David-Sarah Hopwood wrote:
>> Thinking off the top of my head: suppose that there were an arbiter
>> who you trusted not to disclose the read cap or the file contents,
>> and that the server trusted to decide which shares are the correct
>> ones. Then you could give the read cap to the arbiter, and they could
>> sign a declaration that you could give to the server along with the
>> shares.
>>
>> I wonder whether there's a way to do the same thing without an arbiter
>> by using some fancy zero knowledge proof. Effectively you have to prove
>> that S = f(R || T), where f is currently a hash function but might be
>> replaceable with some other kind of deterministic one-way function,
>> without giving away R.
> 
> Actually that's not a correct description of what you would have to
> prove in order to get the full integrity check -- for that you would also
> have to prove hash_n(decrypt[R](K1_enc), Dhash, V) = R (which seems like
> it is probably not amenable to a ZK proof, unless they've got a lot more
> advanced since I last looked at them). But just proving that the creator
> of the share knows R, as the scheme I suggested following the above
> paragraph does, is helpful anyway.

Combining that with the arbiter idea: suppose that we have a trusted public
timestamping service. When two uploaders attempt to upload shares with
conflicting storage indices, the server should give preference to the
share that proves earlier knowledge of the read cap. In the idea I posted
earlier in the thread, this proof is a signature included with the share,
so it would be sufficient to timestamp the shares when they are created.
The storage servers might still allow multiple shares for a given storage
index as in Zooko's suggestion, but send them to clients in order of
their timestamps, earliest first.

A disadvantage of this scheme is that it gives an advantage to an attacker
who can subvert the timestamping service. Certainly, the reliance on a
timestamping service is undesirable, but it does strictly improve on the
arbiter approach, since the timestamp service is not trusted with the
read cap or file contents. (It also doesn't need the ciphertext, since it
can timestamp just a hash of the share.)

Since timestamping is a fairly well-studied class of cryptographic protocol,
perhaps there are already published techniques for doing distributed
timestamping that could be implemented by the storage servers, and that
take account of the possibility that some servers could be dishonest.

(Note that the proof-of-knowledge-of-read-cap idea solves roadblock
attacks on initial upload, so now we are just trying to deal with roadblock
attacks against the repair process.)

-- 
David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com