tahoe-lafs objects

[warner]

When Zooko and I did a run-through of our upcoming RSA talk at the "friam" captalk meeting (12-feb-2010), Carl Hewitt asked the question "what would it take to turn this Tahoe file/directory graph into a graph of objects?". We generally understood "objects" to mean "bundle of state and behavior", like in object-oriented programming, whereas Tahoe's current file/directory objects are just inert state (with any behavior coming from the Tahoe client node that's processing it)..

This question prompted a lot of deep thinking around the table. There is a very juicy idea lurking in this, but we all metaphorically went off to separate corners to meditate on it.

Norm Hardy expressed his subsequent thoughts here: ​http://cap-lore.com/BigStore/Tahoe.html .

Zooko, when asked a day later on IRC, mentioned these:

1. we should make tahoe dirs extensible as suggested by someone
2. we should have a meeting of the minds with friam especially Norm to understand how "opaque object" stuff can be implemented just by making the gateway be the security (and availability ?) domain for your opaque object.

The idea that came to me (Brian) was:

• suppose we stored three things in a Tahoe file
  • a numerically-indexed list of childcaps (the "C-list")
  • an arbitrary chunk of serialized state
  • a chunk of code written in some confineable language (E or secure javascript), or perhaps an immutable reference to some external code file, share between lots of objects
• Some subset of these three things might be mutable, or maybe they'd all be immutable. Some filecap points to this collection.
• when a Tahoe client node loads this object, it runs the code and gives it access to:
  • the serialized state
  • the objects referenced by the childcaps (but not the caps themselves)
• the object receives any webapi request messages aimed at its filecap, processes those requests itself, then can update its state and/or return a response

Much of the post-Carl's-question discussion was about how to implement an "opaque boundary", which I interpreted to mean hiding the childcaps from the confined code that gets run. The code would be able to reference childcap[0] and send it messages, but it wouldn't be allowed to know the actual childcap string (thus helping the child maintain its own privacy).

I'm not sure where to go with these ideas, but they smell powerful. One direction is a forwards-compatibility thing: with a sufficiently general runtime environment for the bundled code, it could be used to implement dirnodes, add-only collections, revocable forwarders, all sorts of stuff that we haven't invented yet. Those fancy things could work on Tahoe clients that were written before the fancy thing was invented because they'd be implemented by portable code that would come along with the object being stored.

Our current dirnode actions (get child, add child, rename, list, delete) could probably be implemented this way (with some additional layer to hide new childcaps from the embedded code, maybe an extra webapi service which adds childcaps to the C-list and only informs the code about the new index).

This whole thing falls into the category of "mobile code", except that instead of a behavior-laden object moving directly from one machine to another, it's being stored in the grid and waking up again later (in one or many places). These objects would have control over their internal state (subject to the behavior of any client node that was allowed to host one of them). Isolation between these objects would be provided by the client nodes.

Something to brainstorm about, at any rate..

[zooko]

I'm not sure I understand Norm's terminology at ​http://cap-lore.com/BigStore/Tahoe.html but it looks like his proposal is the same as Brian's idea in the original post of this ticket.

[zooko]

Norm wrote on ​http://cap-lore.com/BigStore/Tahoe.html:

This plan contravenes an implicit Tahoe dictum: “Trust no mechanism outside your physical control.”. The O-agents of a given RSA key pair rely on either tamper resistance, or more likely physical protection. I think that Tahoe also violates this property in their scheme for mutable objects. (I am not sure.) Such violation also seems necessary for revocation services. In all three cases the trust of externally instantiated objects impacts only those who specifically rely on them.

I don't think Tahoe-LAFS violates this property for our mutable files but to be sure let's see if we can restate the property in terms of "reliance sets" (as in ​MarkM's thesis).

The set of things that you rely on for the unforgeability of your mutable files is:

1. the client (e.g. a web browser which is viewing the file or a unix shell which is catting the file to its stdout)
2. the Tahoe-LAFS gateway

Note that a very common deployment pattern is that you run your own Tahoe-LAFS gateway on your local computer, so both of the items in the reliance set are running as user-space processes within the protection of your operating system and your machine.

So all of the items in the set of "things on which you rely for unforgeability of your mutable files" can be under your physical control.

Now, what about this notion of "Tahoe-LAFS objects"? My proposal for how to implement Tahoe-LAFS objects is simply to make a special client that implements the attenuated, revocable, filtered, or otherwise modified access and that itself has access to the underlying files. That Tahoe-LAFS client then serves its special kind of access out to another client. Let's call that Tahoe-LAFS client an "opaque object server". Then the set of "things on which you rely for the unforgeability of your mutable file" becomes:

1. your client (such as a web browser or cmdline tool), which connects to the opaque object server
2. the opaque object server, which connects to the Tahoe-LAFS gateway
3. the Tahoe-LAFS gateway

(Note: the "opaque object server" is just what Norm mentioned early on his page when he wrote: "The obvious way to do this is to create a web server with the custom filter programmed in, and endow that server with the file handle to the original file.".)

Now here is where it gets confusing to me: we can't maintain the opacity property if you run the opaque object server on your own local machine! So now you can either have the unforgeability property within your physical control (by running all three elements of the reliance set on your own local machine) or you can have the opacity property (by running the opaque object server on a machine that you cannot hack), but not both.

(I haven't thought it through, but I suspect that the "distributed opaque object" proposals by Norm and by Brian will have the same choice.)

But you know what, the opaque object property is not something that the user actually wants. I'll be happy to run all three elements on my own machine and use the resulting "not really opaque" objects. The opacity property is a way to prevent me from doing something, not a way to offer me any useful property. So there must be someone else who wants this opacity property to be preserved, and whoever that is they should run the opaque object server (and the Tahoe-LAFS gateway that it uses) on their machine and give me remote access to the service provided by their opaque object server.

[zooko]

P.S. See ​http://allmydata.org/source/tahoe-lafs/trunk/docs/about.html for a diagram showing the client, web gateway, and storage servers along with reliance set analysis.

[davidsarah]

Replying to zooko:

Now here is where it gets confusing to me: we can't maintain the opacity property if you run the opaque object server on your own local machine!

You can maintain the opacity property as far as the code running on that server is concerned. See below for why this is useful (for some, not all, possible uses of opacity).

So now you can either have the unforgeability property within your physical control (by running all three elements of the reliance set on your own local machine) or you can have the opacity property (by running the opaque object server on a machine that you cannot hack), but not both.

(I haven't thought it through, but I suspect that the "distributed opaque object" proposals by Norm and by Brian will have the same choice.)

But you know what, the opaque object property is not something that the user actually wants. I'll be happy to run all three elements on my own machine and use the resulting "not really opaque" objects. The opacity property is a way to prevent me from doing something, not a way to offer me any useful property.

That's not true in general. I think you're assuming that the code running on the opaque object server is fully trusted by the user who controls that server. But that code may not be fully trusted because it may have bugs that are exploitable for a particular input, and/or it may have been provided by another party.

The opacity helps in both these cases, since it allows enforcing confinement between subcomponents or between the code and Tahoe files, or enforcing other restrictions on the computational model, such as determinism. It also helps in ways that are not only security-related -- basically anything that depends on knowing the reachability graph (memory management, transactional memory, various optimizations...). All of the advantages of using opaque/ partitioned capabilities rather than data capabilities where possible, apply in this situation.

[jsgf]

I was thinking of a simpler scheme to distribute code around a grid: validation of writes/updates to enforce the syntax of files (such as directories). The code would be stateless, and have the only side-effect of either accepting or rejecting an update.

At present this would be useful for: 1) enforcing the syntax of an immutable file, and 2) enforcing correctness updates to immutable files. It would be even more useful with append-only files, since you could enforce new updates to be consistent with what's already present.

Ideally it would be run on each storage server as part of the decision to accept/reject an incoming share, but this has a couple of obvious problems: a) the server doesn't gave keys, so can't decrypt incoming content; b) even if it did, erasure encoding means that a given share can't be decrypted in isolation anyway; c) and even then, the validator could only be sure of inspecting a single segment. (But if you're fetching other shares of a given segment, then fetching other segments may not be a problem.)

It could also be run on a local gateway, to validate outgoing and incoming changes, which simplifies the problem. But this wouldn't prevent illegal updates from ill-behaved clients to immutable files.

A thought on how these validation functions might be implemented. The obvious would be to have something like:

if (valid(file)) then accept() else reject();

but perhaps it might be more interesting to do something like include the output of the validator in the file hash, so the validity is more deeply baked in:

H = hash(file + validity(file))

And a merkle tree would allow you to validate/express validity for parts of the file rather than the whole thing (which is especially interesting if the leaves of the tree correlate to synatactic boundaries of the file rather than just splitting at particular byte boundaries).

But I don't know if that would let you express all the interesting things one would want to express.

There's some overlap with Schneier's idea of Clueless Agents: ​http://www.schneier.com/paper-clueless-agents.html

[jsgf]

Oops, typo:

2) enforcing correctness updates to *mutable* files

[nejucomo]

Summary: A "C-list + blob" feature is a useful stepping-stone for both "live objects" and "arbitrary dag structures".

Note: As I write this, I haven't read all of the comments yet...

Responding to warner:

suppose we stored three things in a Tahoe file

• a numerically-indexed list of childcaps (the "C-list")
• an arbitrary chunk of serialized state
• a chunk of code written in some confineable language (E or secure javascript), or perhaps an immutable reference to some external code file, share between lots of objects

With only the first two of these bullets, the storage model becomes "arbitrary DAGs (Directed Acyclic Graphs)" instead of only "files or directories". This is an interesting direction, even outside of a "live object code" feature.

The C-list would have the same confidentiality properties as current directory references, except they are unassociated with a filename, but they have a unique index for a given version of the cap contents. (Thus verification and repair would work in a similar fashion, although I'm less certain about how updates are implemented.)

Simple "monolithic" directories (similar to SDMF directories) could be implemented on top of this "C-list + blob" format to promote "our own dog food" cuisine, which would help work out bugs and usage issues. This implementation would have a blob which links file names and other link metadata to the C-list.

It's easy to imagine other data structures: sets, queues, trees whose edge labels are not filenames, etc... (In fact, a queue could have an empty blob, if we trust the writer to maintain the C-list order "correctly". A set is even simpler and has an empty blob and the C-list order is ignored.)

Of course, those data structure examples don't address distributed consistency issues, so I don't mean to imply desirable properties such as append-only or "eventually consistent ordering" or the like. See #796 for a discussion of some of those features.

Consider also, these proposed distinct (abstract) webapi calls:

• get_raw(readcap) → C_list_and_blob_bytes
• get_blob(readcap) → blob_bytes
• get_clist(readcap) → C_list

Now, the blob could be html and javascript, so that a GET to the get_blob api will load that into a browser, and the javascript can then use the get_clist api to access references. Some pros/cons of this particular example:

• Pros:
  • This is approaching a "live capabilities objects" feature.
  • It keeps the layering fairly distinct - lafs doesn't know about "live object code" very much, outside of standard http+browser tech.
  • Because the "C-list + blob" feature is a separate layer, this does not preclude other approaches to live objects, and it does not complicate other uses of "C-list + blob".
• Cons:
  • This example is inefficient compared to a more direct implementation of "live objects".
    • Example: a webapi which knows the blob is javascript with a special interface could inject the C-list into the script in a well defined convention prior to responding to an http request. Thus, there'd only be one http request/response. (This would not use the proposed API above.)

I haven't figured out yet how to quarantine the javascript to have object-capabilities-like access control, in this scheme. However that problem seems similar to object-capabilities-restriction for javascript in current lafs.

[zooko]

Replying to nejucomo:

With only the first two of these bullets, the storage model becomes "arbitrary DAGs (Directed Acyclic Graphs)" instead of only "files or directories".

I don't understand the distinction. Isn't the current LAFS files-and-directories structure already an arbitrary DAG? Just use incrementing integers as your filenames in your directories, and then that's a C-list. Or am I missing something?

[nejucomo]

Summary:

1. Nejucomo brainstorms differences between a native C-List + blob feature, versus
2. "emulating" that with existing lafs directories and files, and
3. realizes that emulation is good enough, and
4. abandons support for any new "C-List + blob" feature, and then
5. asks if that "emulation" is good enough for live objects.

-then finally decides to post the whole brainstorm in case posterity finds anything useful in it. ;-)

Replying to zooko:

Replying to nejucomo:

With only the first two of these bullets, the storage model becomes "arbitrary DAGs (Directed Acyclic Graphs)" instead of only "files or directories".

I don't understand the distinction. Isn't the current LAFS files-and-directories structure already an arbitrary DAG? Just use incrementing integers as your filenames in your directories, and then that's a C-list. Or am I missing something?

Yes, having an existing lafs directory to serve as a C-List and a separate lafs file to serve as the blob, and a third container directory to bind the two is already possible, at the cost of efficiency.

I'll call that "the emulation design" below (because it is emulating "C-List + blob" as a built-in feature). Let's contrast emulation with a built-in feature:

Emulation:

• Requires three file nodes.
• Requires the application to encode their data structure into lafs directory names or other edge metadata.
  • Is there a simple, safe way to encode arbitrary bytes into an edge name?
  • Is it possible to attach arbitrary metadata to edges?
• Cannot guarantee consistency between the C-List-emulation and blob-emulation:
  • A reader must read these separately, thus has no guarantee the two reads return a consistent view.
• Fits the current "files and directories" abstraction well, so the user interfaces map reasonably well.
  • For example, fuse interfaces know what to do.

By contrast:

Native C-List+Blob Feature:

• Requires a single node for any application.
• Allows the application to generate/interpret blob "directly".
• Ensures mutation consistency between the C-List and blob in the same manner as single file-node mutable consistency is currently ensured.
• Can represent directories as a particular application.
• Breaks the notion of "just file and directories", introducing complexity into the user interfaces.
  • For example, what does a fuse interface do with an arbitrary C-List + blob?
    • It could do the "inverse" of the emulation above: Present a directory with a C-List subdirectory and a blob file. Now we have the same encoding problems as with emulation, except instead of the application which wrote the blob inventing the encoding, a completely unaware general application (ie: fuse interface) has to pick an encoding.

After brainstorming those differences, to me it seems like the primary advantage is mutation consistency properties.

It occurs to me that if it's already possible to encode arbitrary metadata in the node edges, when we already have C-List + blob where the blob is split up across the edge metadata.

Oh... I just realized: If the emulation container directory is mutable, but the C-List-emulation child and the blob child are immutable, this solves the consistency problem, right? A reader of the container directory knows that the immutable C-List cap and the immutable blob-file cap were written together by a single writer, and therefore their inter-relationships are as consistent as the writer.

Ok, now I'm pretty much satisfied that "C-List + blob" is unnecessary, at least for arbitrary DAGs.

Is this also true of the "live objects" proposal? If we require that the interpretation of a "C-List + blob + object-code" structure starts with a cap to a directory where C-List, blob, and object-code are separate but *immutable* files, is this a sufficient building block for live objects?

[meejah]

Ticket retargeted after milestone closed (editing milestones)