[tahoe-dev] Hack Fest Day One report

[Kevin Reid]

On Mar 31, 2012, at 16:15, Zooko Wilcox-O'Hearn wrote:

> That's way better! It is almost elegant. But as Brian then pointed
> out, it can't work. Because all directories (except for the root dir)
> that are produced by a "tahoe backup" are immutable. You can't have a
> cycle of immutable directories, because it is impossible to get a link
> to an immutable directory before providing the initial and final
> contents of it.
> 
> • This led me to off-handedly comment that such a thing would be
> possible with Petrification a.k.a. revocation of write authority
> (#954)

I note that a revoked-write read-cap is less strongly immutable than an immutable cap, in that accident to or conspiracy by the storage servers could make it writable again.


Here's a probably impractical way to create truly immutable cycles I just thought of. The upload procedure is:

1. Construct all of your directory/file graph except with placeholders for the cyclic references (either arbitrary caps or special undereferenceable caps, i.e. unique IDs). Call the root of this graph R.

2. For each distinct subset of authority provided by some cap D reachable from R, construct a directory whose keys are the placeholders reachable from D and values are their proper referents. Call this dircap T(D). (It should also provide a map of D' to T(D') for every D' which is a member of D such that T(D') is distinct from T(D).)

3. Construct a cap of a new type — call it a cycle cap — which has the bits of both R and T(R); call it C(R, T(R)).

When C(R, T(R)) is dereferenced, it has contents similar to R, except that any dircap D stored in R is replaced by C(D, T(D) if present in T(R) else T(R)).


This is fully immutable and breaks cycles, but it produces caps twice as long and more expensive to dereference, compared to ordinary immutable dircaps.

It also introduces a general mechanism for saying "this graph, but with this other subgraph substituted here", for whatever that's worth; I was slightly inspired by git having a mechanism to do this (AFAIK primarily used for replacing ancestry, not replacing subdirectories; I haven't looked at its uses myself).


>  which inspired David-Sarah to announce that they were going to
> implement #954 during Hack Fest.

Perhaps this announcement should be posted on the ticket?

https://tahoe-lafs.org/trac/tahoe-lafs/ticket/954

-- 
Kevin Reid                                  <http://switchb.org/kpreid/>