[tahoe-dev] [tahoe-lafs] #795: append-only files

tahoe-lafs trac at allmydata.org
Sun Aug 23 00:45:17 UTC 2009

#795: append-only files
 Reporter:  warner        |           Owner:           
     Type:  enhancement   |          Status:  new      
 Priority:  major         |       Milestone:  undecided
Component:  code-mutable  |         Version:  1.5.0    
 Keywords:                |   Launchpad_bug:           

Comment(by warner):

 More notes:

 Basically, each append-only-able file would have three keypairs:

  * A: the whole-file-changing DSA keypair (As/Av)
  * B: an appending DSA keypair (Bs/Bv)
  * C: an appending RSA (encryption) keypair (Ce/Cd)

 The writecap would get you everything, the appendcap gets you
 Bs+Ce, and the readcap gets you just the three
 verification/decryption keys Av+Bv+Cd. The server must know (and
 enforce with) the verification keys Av+Bv.

 The server would be responsible for:

  * only allowing full-file rewrites that are signed by As
  * accepting "append" messages signed by Bs and appending them
    to the file (or putting them in a unique file in the share
    directory, or something)

 Andy the Appendcap-holder would need to encrypt his message with
 Ce, sign it with Bs, then send it to the servers. Rose the
 readcap-holder would check all the signature and then use Cd to
 decrypt the append messages. Val the verifycap-holder needs to be
 able to check the hashes and signatures on the append messages,
 but not decrypt them (so we need encrypt-then-sign, instead of
 sign-then-encrypt). And Rob the Repairer needs to be able to make
 new shares out of everything, so the body being signed should
 contain the share hash tree root. Each append message will be
 erasure-coded separately.

 Every once in a while, Wally the writecap holder might merge all
 the append messages down into the "base object". Until this
 happened, a colluding set of servers could discard arbitrary
 append messages (meaning the file would not be monotonically
 increasing). There might be ways to have each message include the
 hash of the previous ciphertext to detect this sort of thing
 (forcing the server to discard all-or-nothing, restoring
 monotonicity, but introducing race conditions).

 Maybe "add-only collection" would be a better model for this,
 instead of implying that the object contains a linear sequence
 of bytes. In fact, we might say that the objects stored in this
 collection are arbitrary strings, with IDs based upon hashing
 their contents, and make the append(X) operation be idempotent,
 and give readers an unsorted set of these strings. This would
 make things like the add-only directory easier to model.

 To turn this into a dirnode, the append message would probably
 contain a "proposed child name" and child readcap/writecap.
 If/when Wally merges down the file, any name conflicts would be
 resolved (by appending "(1)", or whatever) then.

 Preserving transitive-readonlyness probably requires that both
 writecap holders and appendcap holders (Wally and Andy) be able
 to get to the same symmetric key (the child-writecap
 superencryption key). One noteable difference with the normal
 mutable-file layout is that this child-writecap key must *not*
 let you derive the read key. Rose the readcap holder can see the
 (encrypted) child-writecap column but can't decrypt it. Andy the
 appendcap holder can't see the child-writecap column ciphertext,
 but if he could, he could decrypt it (since he's supposed to be
 able to put child-writecaps somewhere that Wally can read them).
 This reveals a collusion attack: Andy and Rose could work
 together to learn the child writecaps.

 So child-writecaps in append messages must be encrypted to the
 writecap holder, and not to anybody else. This suggests we need
 another encryption keypair, De/Dd, in which the writecap holder
 gets Dd, and everybody else gets De (but only Andy will use it,
 because those messages must also be signed by Bs, held only by
 Andy and Wally). This can't be a combined sign+encryption key,
 which might save space, since Val and Rob need Bv to verify
 those append messages later.

Ticket URL: <http://allmydata.org/trac/tahoe/ticket/795#comment:2>
tahoe-lafs <http://allmydata.org>
secure decentralized file storage grid

More information about the tahoe-dev mailing list