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

[Brian Warner]

David-Sarah Hopwood wrote:
> I've designed a new version of the cap protocol I posted a few days
> ago, that addresses Brian's comments about roadblock attacks.

This is great stuff. The diagram is immensely helpful too. Some
comments:

* so S+T is the storage-index, and the conservative values make it 210
  bits for immutable files and 288 bits for mutable files.

* roadblock attacks: I agree that it's probably plenty to make "t" large
  enough that the attacker can't put roadblocks in place before the
  uploader finishes their upload. If convergence is in use, the
  roadblocker may get more time to construct their preimages
  (particularly for likely-to-be-popular files, especially if someone
  has exclusive access to the file for some period of time before it
  becomes popular). However, we can (and probably should) design the
  upload code to detect a roadblock (i.e. notice shares for the existing
  SI, download some pieces of it to validate the hashes, then discover
  the problem) and re-upload with a randomly-generated key.

* more significantly, the attacker can prevent repair of the file,
  because once the original shares are uploaded, they have plenty of
  time to compute preimages and place roadblocks on all the other
  servers

But, 2**50 is still pretty big, and each operation requires generating a
DSA keypair, so perhaps we can rely upon the significant expense of this
attack to discourage people from trying it.

For mutable files:

* The destroy-cap is a neat bit of feature, but I'd want to think about
  it further before actually building it in. It makes a lot more sense
  in the context of add-only files.. if you don't have those, then
  there's not a lot of difference between filling the mutable slot with
  an empty file and completely destroying the slot. The existing URI:SSK
  files grant this ability to writecap holders: they can set the
  container length to zero, which will cause the server to delete the
  share altogether (the idea being to help with rebalancing/GC).

* I'd rename "master cap" to "writecap" or "full-writecap".. I spent a
  bit of time trying to figure out how to reattain offline
  writecap-to-readcap attenuation before realizing that the red "KCsign"
  value is actually the add-only cap, and the rainbow-colored box is the
  writecap. Also, I'd probably use "extra-verification readcap" or
  something similar instead of "read/verify cap".. the latter makes me
  think that the "readcap" doesn't provide any verification properties
  (when in fact, with your parameters, provides something like
  128+50=178 bits of integrity checking, which corresponds to a 178/2=
  2^89 work factor to find a single collision?).

* I like the variable-length cap thing. You'd store R+T+U everywhere,
  but you'd let users pass just R+T when they want to share. I think we
  could make this non-quantized: they could pass R+T+U[:extra] when they
  want to share, setting 'extra' according to how much they value
  brevity over integrity.

I'll try to write up a message later this weekend about server-side
validation properties. The most important reason is to get rid of the
write-enabler, to enable a future non-confidential share transport
protocol.

thanks!
 -Brian