Distributed Mutable Containers

Some terms used in this document:

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119].

In Section 2 we give an overview of related work and how DMC relates to and differentiates from respective projects.

The necessary prerequisites are briefly discussed in Section 3. This includes the Resource Description Framework (RDF), content-addressing with the Encoding for Robust Immutable Storage (ERIS), Commutative Replicated Data Types (CRDTs) as well as Datalog as specification language for the computation of container state. References to further reading are provided.

In Section 4 we describe the basic concepts and working of DMC containers. The concrete specification of the two container types (set and register) is given in Section 5.

In Section 6 we describe the necessary state local replicas must hold and how replicas can be synchronized over various transport layers. A CBOR serialization is defined in Section 6.4, which can be used for out-of-band transport of DMC containers.

We conclude with some ideas on how applications might use DMC (Section 7) and with some closing remarks on future work (Section 8).

Hypercore and Secure ScuttleBut (SSB) are protocols for building decentralized applications. Both use an append-only log to keep track of history. This has two major drawbacks:

DMC solves both issues by using CRDTs, which do not impose any order on mutating operations.

With DMC content can be completely removed (or forgotten) without affecting the current or future state of the container. We believe that this is an essential functionality that enables the right to be forgotten. Note however that deletion can not be enforced on remote replicas. See Section 6.2.1 for more details.

The state of two DMC replicas are permitted to diverge as they can be merged back without conflict at any time. This is essential for allowing truly collective control of containers without any out-of-band coordination.

Git is a widely-used distributed version control system. Unlike systems based on append-only logs the state of Git repository may diverge and be merged. However, merging is not conflict-free and requires manual intervention as well as out-of-band coordination.

DMC does not require manual merging: CRDTs are guaranteed to always merge without conflict. The draw-back is that containers are not as general as Git repositories. A Git repository can hold an Unix file system, which can be used to implement a register or a set (and many other data structures). The semantics of a DMC container is hard-coded into the container and is not as flexible as a Git repository.

The semantic restriction allows DMC containers to diverge and merge without conflict and, as shown in Section 7, is enough to still implement many interesting applications.

The GNU Name System (GNS) is a distributed name database being developed by the GNUnet project as a replacement for DNS.

Similar to DMC, GNS provides stable names for mutable content. In GNS names are human-meaningful and can be delegated to form hierarchichal names similar to DNS. DMC, on the other hand, does not provide human-meaningful names (see Section 4.3), but a much more flexible model of mutation and replication.

We believe that GNS and DMC are highly complementary in the sense that GNS might be used for human-meaningful names for DMC containers (see also Section 8.1).

The InterPlanetary File System (IPFS) is a protocol for peer-to-peer storing and sharing of data. IPFS, at its core, only provides immutable storage. IPFS together with exentsions such as the InterPlanetary Name System (IPNS) are closer to the goals of DMC.

IPNS seems to be conceptually similar to a Last-Writer-Win Register (see Section 5.2). An IPNS identifier is the hash of a public key. The corresponding secret key can be used to update what the IPNS identifier resolves to. Unlike DMC, IPNS does not explicitly allow state to diverge or authority over an IPNS identifier to be delegated. We believe that this is important for enabling collective control over data structures.

IPFS does not provide confidentiality and only limited censorship resistance. Content stored on IPFS is by default unencrypted and can thus be trivially blocked by individual hosts. DMC improves by always encrypting content with ERIS (see [_content-addressing]).

IPFS can, however, be securely used as an underlying block storage for DMC (see Section 6.2) by only storing encrypted blocks in IPFS [ERIS].

Vegvisir is a partition-tolerant distributed data-structure that is based on CRDTs [vegvisir] and served as an inspiration for DMC.

Similarly to DMC, Vegvisir allows delegation of authority over a container. Unlike DMC, Vegvisir encodes a partial ordering of operations on the container. While this allows features such as key revocation (Section 4.6.1), it prevents the right to be forgotten (Section 6.2.1).

Riak is a distributed key-value data store for enterprise applications. Similar to DMC, CRDTs are used to ensure consistency over database replicas.

Unlike Riak, DMC is designed for outside of the enterprise datacenter.

The Resource Description Framework (RDF) [RDF] provides a concrete graph data model for highly-interlinked content. It is a concrete data model for Linked Data.

RDF defines a very simple graph model for describing content. The basic unit is a triple consisting of a subject, predicate and object. Subjects and predicates are identified with IRIs (internationalized URIs), while objects are either IRIs or literal values.

DMC uses RDF to describe container definitions, operations and container state. DMC is especially well-suited for applications that also use RDF, but not limited to such.

A basic understanding of RDF is expected to understand this document.

Identifying content by the cryptographic hash of the content itself is called content-addressing. This allows content to be easily replicated, enabling decentralized systems.

DMC groups RDF triples into content-addressable fragment graphs [content-addressable-rdf].

Furthermore, DMC uses the Encoding for Robust Immutable Storage (ERIS) [ERIS], which enables secure and censorship resistant content-addressing. ERIS defines how arbirtary content can be encoded into uniformly sized encrypted blocks. We will use this when discussing local state of replicas and synchronization between replicas (Section 6).

To ensure authenticity of operations and verify that operations are authorized we use the Ed25519 algorithm for cryptographic signatures and the RDF Signify vocabulary for describing signatures [rdf-signify].

Conflict-free replicated data types are a class of data structures that can be replicated over hosts, updated independently and are guaranteed to be mergeable without conflict.

There are two sub-classes of conflict-free replicated data types: Convergent Replicated Data Types (state based) and Commutative Replicated Data Types (operation based). We will use the latter as it seems to work nicer with content-addressing - operations are content-addressed, immutable and individually identifiable entitites.

Commutative Replicated Data Types rely on the fact that operations that mutate the data structures commute, i.e., the order in which the operations are applied does not change the outcome. This guarantees that distributed replicas of a CRDT converge to the same state as soon as the same set of operations is applied at both replicas (regardless of order). This property is called strong eventual consistency.

We will use two types of CRDTs: An Observed-Remove Set (section Section 5.1) and a Last-Writer-Win Register (section Section 5.2) and will introduce both in the respective sections.

The reader is referred to Shapiro et. al. [crdt] for a formal treatment and an overview of the various types of CRDTs.

Datalog is a declarative logic programming language. It has a very simple syntax and semantics that makes it useful as a query language for interacting with large amounts of data.

We will use Datalog as a specification language for describing the semantics of container state. This allows a very concise description that can be directly used in existing, efficient implementations of Datalog. Furthermore, certain aspects of Datalog semantics (monotonicity) make it perfectly adapted for reasoning about distributed systems [calm].

Datalog can also be used as an application level query language (e.g. for answering queries like "all posts about cats posted by people that I have sent a message to in the last year"). The query can be combined with container state resolution queries to a single query. This enables a DMC implementation that uses Datalog to not only provide primitive containers but a rich interface for efficiently interacting with data.

We require three extensions of Datalog which are well studied in the literature: Built-in predicates (for computing cryptographic functions), stratified negation, and monotonic aggregation. All required extensions are available in the open-source Datalog implementation Soufflé, which was used to develop and test the work presented.

For a formal introduction to Datalog the reader is referred to the overview paper by Ceri et. al. "What you always wanted to know about Datalog (and never dared to ask)" [datalog].

DMC distiguishes between three different types of objects:

Objects are immutable RDF fragment graphs [content-addressable-rdf] that are content-addressed using ERIS [ERIS] (see Section 3.2). Objects are referenced using the respective ERIS read capability (an URN).

Objects reference each other and together form a graph that we call the replica object graph. The replica object graph is an RDF graph consisting of RDF triples. Every replica of a container maintains its own graph which corresponds to the local state of the container.

The dynamic container state is computed from the replica object graph. The dynamic state can be referenced by using the container identifier (see Section 4.3).

In the following the Datalog predicate graph(Subject, Predicate, Object) is used to access RDF triples in the replica object graph.

A container is created by creating a container definition.

A container definition MUST include:

The root public key is a Ed25519 public key. The associated secret key of the root public key can be used to mutate the container by signing operations or adding new public keys to the list of authorized keys for the container (see Section 4.6 and Section 4.7).

A container definition MAY contain further triples (predicates and objects) to describe further meta-data (e.g., creator, an ActivityStream inbox, etc.). It is RECOMMENDED to use the Dublin Core Metadata Terms [dcm-terms] for generic meta-data.

For example a container definition for a set (defined in section Section 5.1):

To reference the dynamic and mutable state of a container we use the special URN scheme dmc:CONTAINER_DEFINITION_ERIS_CAPABILITY where CONTAINER_DEFINITION_ERIS_CAPABILITY is the encoded ERIS read capability.

For example the identifier for the container defined in the previous sections is:

dmc:AAAELYRT24S2SACAPSMGTNYYHCCQHBDGQH3SC3K3Y35PI73SLTA6JTO7S7XTA66LZQ2OKSAZZI4BWXJCGGJLZ74WIWEMXZ2SXDC4JVAFKM

Operations mutate container state. They are represented as RDF graphs that are content-addressed using ERIS.

Operations are either:

All operations are sub-classes of dmc:Operation.

All operations MUST contain a single dmc:container predicate to specify the container the operation acts on.

For example the operation for adding an element to the set defined above looks like this:

Public-key cryptographic signatures are used to ensure that operations are issued by authorized entitites.

The RDF Signify vocabulary [rdf-signify] is used to describe signatures as RDF. This means:

We introduce the following signed helper Datalog predicate to decide if there is a valid signature of Message that can be verfied by the public key Key:

This uses the special ed25519Verify(Signature, Message, Key) Datalog predicate which performs the validation of the Ed25519 signature.

An example signature:

An authorized key of a container is an Ed25519 public key whose associated secret key can be used to sign operations.

An authorized key is either:

The following authorizedKey Datalog predicate captures these two possibilities:

A key Key is an authorized key for a container Container if and only if the authorizedKey(Container, Key) holds.

An operation is authorized on a container if and only if it is signed by an authorized key of the container.

An operation Operation is a valid operation on the container Container when authorizedOperation(Container, Operation) holds.

The container state is computed from an replica object graph. Implementations MUST compute the container state when the container identifier is dereferenced.

Container state is represented as RDF using a sub class of the dmc:Container class (either dmc:Set or dmc:Register). The exact representation of the container state as well as the semantics is defined in section Section 5 for the different container types.

For example the state of the set defined above would be resolved as follows after two elements have been added:

The state depends on the available operations and signatures of operations (objects, see Section 4.1). See Section 6 on how the state at local replicas is managed and can be synchronized with other replicas.

Sets are unordered collections that hold distinct members. They are a useful base data structure for building complex applications.

Adding and removing elements from a set are, in general, non-commutative operations:

We will use a little trick to solve this problem. The data structure that implements this trick is called an Observed-Remove Set (OR-Set).

A register is a data structure that holds at most a single element. This is useful for singleton objects that can be updated such as user profiles.

The DMC register is based on a Last-Writer-Wins register.

An implementation of DMC that is capable of computing the state of a local replica MUST maintain two data structures:

Implementations MAY include references to other blocks in the replica block references. For example, it might make sense to add references to blocks required to decode ERIS encoded content that was added to a container (in addition to the operations and signatures).

The replica block references can be shared with caching peers - peers that can help distribute the container state without being able to compute container state.

The necessary data structures can be implemented on a persistent key-value store, a relational database or other persistent storage mechanisms.

The replica objects and replica block references only store read capabilities and references to blocks. A DMC implementation MUST also be able to store and retrieve blocks of size 1KiB or 32KiB (permitted ERIS block sizes). References by which blocks can be retrieved are the Blake2b hash of block content and are stored in the set of block references.

External system such as IPFS or GNUNet can be used as block storage (see examples in the ERIS specification [ERIS]).

Replicas of DMC containers can be synchronized over many transport layers. The general synchronization procedure is:

This synchronization procedure can be implemented over protocols such as HTTP or CoAP. Exact descriptions of this procedure over concrete transport layers will follow with implementations (see Section 8.1).

In Section 6.4 we define a CBOR serialization of replica state. This serialization can be used for out-of-band transport over protocols like Email, FTP or Sneakernet.

Futhermore it is possible to use publish-subscribe systems (such as MQTT or XMPP) to keep replicas synchronized. Replicas subscribe to a publish-subscribe topic and publish modifications of replica objects and replica block references. However, it seems necessary to still be able to run the synchronization procedure as described above when replicas disconnect and reconnect from the publish-subscribe system.

As part of the DREAM project we are researching a peer-to-peer publish-subscribe system, UPSYCLE, which will also be usable to synchronize replicas of DMC containers.

In this section we define a CBOR serialization of replica state suitable for out-of-band transport of replica state (e.g. as an e-mail attachment or on a USB disk). This serialization is not suitable as working state representation. Implementations should use more efficient state storage such as key-value stores.

The replica state is a CBOR array with elements:

Objects and blocks are optional for the cases where a CBOR serialization of the replica state is created for caching peers that are not able to decode objects and compute container state or when an external block storage is used.

The specification of the serialization is given as Concise Data Definition Language (CDDL) [RFC8610]:

Geogrpahical Information Systems (GIS) are systems for modelling, analysis and management of geographically related resources.

We believe that DMC can serve as a foundation for decentralized Geographical Information Systems as it addresses many challenges in building a GIS [smallworld]:

ActivityPub is a protocol for federated social media that uses the ActivityStreams [ActivityStreams] vocabulary to describe social interactions. As ActivityStreams is simply an RDF vocabulary it can be used to describe social interactions over many different data sets (e.g. the creation of a node on a map).

DMC is very well suited for handling RDF and thus also ActivityStreams. This allows interaction between DMC systems and ActivityPub services. Furthermore AcitivtyPub can be implemented using DMC containers.

In the context of the DREAM project we will develop an OCaml implementation of DMC. We expect refinements to the specification from insight gained while implementing the core specification as well as applications that use DMC.

DMC relies on novel specifications such as ERIS, RDF Signify and Content-addressable RDF. Further work is required to mature and finalize these ideas.

It would be interesting to explore usage of other complementary systems such as the GNU Name System (GNS), GNUNet, IPFS, Named Data Networks with DMC.

We would like to acknowledge the value of Sci-Hub and Library Genesis for this work. Independent research such as this would not be possible without liberated access to knowledge. Water the flowers - clean the volcanoes.

An initial version of this document was developed as part of the openEngiadina project and supported by the NLNet Foundation trough the NGI0 Discovery Fund. Further work has been done as part of the DREAM project and is supported within the framework of the NGI-POINTER project.