This is a longer-form writeup of what I’ve been thinking in response to Brendan’s LDFile ideas.
The context is we’re collaborating with Qri (and Brendan especially) on two implementations for the next WNFS. Brendan is working on wnfs-go while we’re working on a typescript implementation.
Brendan raised that he’d have a use-case for something he calls ‘LDFile’ (Linked Data File). This would be something tagged differently than regular files or directories. The way I understand it so far is that he’d want to be able to use files more like dag-cbor vs. using UnixFS today. That is, having something better than a “here’s some huge byte array” abstraction. This in turn implies that you’d have more control over the resulting DAG you’re building, which I think is another great benefit.
For the public side the specification effort should be pretty small, we would simply add another file type “LDFile” and tag the content CID of LDFiles with that. Everything else would either already work as expected (pinning/syncing) or is just a matter of programming API, not specification.
For the private side, it’s harder. The issue is we can’t simply link between blocks using CIDs and expect e.g. pinning to work, because these CIDs will be encrypted inside the private filesystem blocks. Additionally, there’s a choice we need to make about what keys to use to encrypt which blocks. (Do we use the same key for all blocks? If not, do we need a ratchet per block?, etc.)
It should now be clear that we can’t use plain dag-cbor for the private side. As a mental model I’ll be writing about “taking a dag-cbor graph and ‘making it private’”. I don’t think it’s supposed to work like this, but I think it makes it easier to think about & it implies that we can support everything that dag-cbor supports today plus more, as long as we’re not removing features from dag-cbor, if that makes sense.
To make a dag-cbor graph work with the private filesystem, we take each block in the graph and encrypt it with a random key, except for the root block that is referenced in the LDFile header. That block should be encrypted using the keys that the ratchet in the header generates.
To make it possible for entities that know the root block’s key to encrypt the rest of the graph, we should add them to every link before we’re encrypting the blocks. Also, the CIDs should reference the hash of the encrypted blocks instead of the “original” blocks.
The resulting links will thus be a { key, cid } pair. (There’s some bike shedding to do on what this should encode to exactly. E.g. it could be its own CBOR tag.)
To solve the pinning problem I propose we “just” reuse the private HAMT, similar to how we use it for private files & directories today. (As a recap for anyone not familiar with the private HAMT: It stores encrypted blocks as blobs without further links under keys that are saturated namefilters which can be checked against for write access.)
This means we need to walk the DAG and put each block into the HAMT.
The key that each block should be put in should be the bloom filter saturate(add(ldFileHeader.bareNameFilter, [block.cid, block.key])).
With this construction we arrive at these trade-offs:
- An LDFile’s underlying DAG structure is hidden. To an observer without keys all blocks in the HAMT have no relation to each other.
- The LDFile’s content is completely encrypted.
- Parts of the LDFile can be changed without having to re-encrypt every block, because the keys used for each block are chosen independently. You only need to re-encrypt the “spine” of your change, similar to what happens when you need to update a node in a dag-cbor DAG and need to update the hashes of parents.
- Given any HAMT containing all blocks & the LDFile header bare namefilter & root DAG node CID & a key to unlock root node, you can efficiently decrypt all of the DAG’s nodes by following the links, constructing the namefilters, looking the next node(s) up in the HAMT & decrypting them, etc.
- A third party without encryption keys can verify that a write to all nodes of the DAG in the HAMT is authenticated with respect to a UCAN giving write capabilities to the LDFile header.
- It is not possible to give write access to only a fraction of an LDFile.
As you can see, what distinguishes LDFiles from regular private files & directories is that they’re a single entity as far as WNFS is concerned: You’re meant to only provide read and/or write access to the LDFile as a whole, never only a part of it.
I think that’s the right trade-off given I think the main use-case for this is files that only make sense to an application as a whole, and I think we don’t want to define merge-semantics for blocks within those files in general, only for their headers. (And then the application can have its own custom merge semantics.)
There’s a couple of different approaches I’ve considered:
- Only store
{ key }as links. I.e. remove thecids. However, that only works if every time you want to encrypt a block with different content, you encrypt it with a completely new key. Otherwise you’d have clashing entries in the HAMT (one namefilter pointing to two blocks). This would make applications that have some scheme for choosing keys (e.g. some custom ratchet) impossible. - Make the keys used for encryption predictable. E.g. have a canonical path for each block in the DAG and hash it together with the LDFile’s header’s key to gain the encryption key for that block.
However, this means you’d need to re-encrypt the whole DAG on every change. - Even simpler: Use the same key for the whole DAG. This also needs a re-encryption of the whole DAG on every change.
- Store a ratchet & inumber in the links: This makes it possible to seek ahead individual blocks. I don’t think that’s a feature we want for LDFiles, which should be considered like a structure that only makes sense as a whole.
- Store the saturated namefilter + key instead of a CID + key in each link. This makes it efficient to look up the next node even if you don’t have the bare namefilter from the LDFile’s header. However, this greatly increases the size of each link (additional 256 bytes instead of 32 additional bytes) and I think it goes against the “LDFiles considered as a whole” idea.
