Meadowcap

Status: Candidate (as of 17.01.2024)

Meadowcap is a capability system for use with Willow. In this specification, we assume familiarity with the Willow data model.

Overview

When interacting with a peer in Willow, there are two fundamental operations: writing data — asking your peer to add Entries to their stores — and reading data — asking your peer to send Entries to you. Both operations should be restricted; Willow would be close to useless if everyone in the world could (over-)write data everywhere, and it would be rather scary if everyone could request to read any piece of data.

A capability system helps enforce boundaries on who gets to read and write which data. A capability is an unforgeable token that bestows read or write access for some data to a particular person, issued by the owner of that data. When Alfie asks Betty for some entries owned by Gemma, then Betty will only answer when presented with a valid capability proving that Gemma gave read access to Alfie. Similarly, Betty will not integrate data created by Alfie in a subspace owned by Gemma, unless the data is accompanied by a capability proving that Gemma gave write access to Alfie.

A two-column comic. The left column first shows Alfie handing a neat slip of paper to Betty. The second panel shows Betty inspecting the paper with a magnifying glass. The magnified text clearly reads "signed: Gemma". In the final panel, a happy Betty hands a box over to a happy Alfie. The right column depicts a less fruitful interaction. A cartoonish troll approaches Betty with a crumpled paper sheet. When Betty inspects it in the second panel, it reads "i AM StiNKY GEMA", clearly not Gemma’s real signature. In the final panel, Betty tells the troll off, not handing over anything.

What makes somebody “the owner” of “some data”? Meadowcap offers two different models, which we call owned namespaces and communal namespaces.

A front view of a stylised house. The house has three separate entries, each with a differently-coloured keyhole. Above each entry is a window in a matching color, each with some happy denizens sticking their heads out. The outer windows contain a single person each, the middle window is shared by two people.A communal namespace. Metaphorically, everyone has their own private space in the same building.

In a communal namespace, each subspace is owned by a particular author. This is implemented by using public keys of a digital signature scheme as SubspaceIds, you then prove ownership by providing valid signatures (which requires the corresponding secret key).

A similar front view of a house, with windows showing the inhabitants. Unlike the preceding drawing, this house only a single door, with an orange keyhole. The three windows each show a combination of orange and an individual color per window. In front of the window stands the owner, dutifully (and cheerfully) maintaining the lawn with a broom.An owned namespace. Metaphorically, a single owner manages others’ access to their building.

In an owned namespace, the person who created the namespace is the owner of all its data. To implement this, NamespaceIds are public keys. In an owned namespace, peers reject all requests unless they involve a signature from the namespace keypair; in a communal namespace, peers reject all requests unless they involve a signature from the subspace keypair.

Owned namespaces would be quite pointless were it not for the next feature: capability delegation. A capability bestows not only access rights but also the ability to mint new capabilities for the same resources but to another peer. When you create an owned namespace, you can invite others to join the fun by delegating read and/or write access to them.

The implementation relies on signature schemes again. Consider Alfie and Betty, each holding a key pair. Alfie can mint a new capability for Betty by signing his own capability together with her public key.

Once Alfie has minted a capability for Betty, Betty can mint one (or several) for Gemma, and so on.

Verifying whether a delegated capability bestows access rights is done recursively: check that the last delegation step is accompanied by a valid signature, then verify the capability that was being delegated.

The next important feature of Meadowcap is that of restricting capabilities. Suppose I maintain several code repositories inside my personal subspace. I use different Paths to organise the data pertaining to different repositories, say codeseasonal-clock and codeearthstar. If I wanted to give somebody write-access to the codeseasonal-clock repository, I should not simply grant them write access to my complete subspace — if I did, they could also write to codeearthstar. Or to blogembarrassing-facts for that matter.

Hence, Meadowcap allows to restrict capabilities, turning them into less powerful ones. Restrictions can limit access by subspace_id, by path, and/or by timestamp.

If it helps to have some code to look at, there's also a reference implementation of Meadowcap.

This concludes the intuitive overview of Meadowcap. The remainder of this document is rather formal: capabilities are a security feature, so we have to be fully precise when defining them.

Parameters

Like Willow, Meadowcap is a generic protocol that needs to be instantiated with concrete choices for the parameters we describe in this section.

Meadowcap makes heavy use of digital signature schemes; it assumes that Willow uses public keys as NamespaceIds and SubspaceIds. A signature scheme consists of three algorithms:

An instantiation of Meadowcap must define concrete choices of the following parameters:

A Meadowcap instantiation is compatible with Willow if

Throughout the specification, we use these pairs of parameters interchangeably.

Capabilities

A neat piece of paper, styled like an admission ticket, with a heading saying "This Capability Grants...". The heading is followed by four sections. The first section states the receiver as "Alfie", the second section states the granting of "read access", the third section gives a time range of "all messages from last week", and, finally, a large stamp mark simply says "valid".Intuitively, a capability should be some piece of data that answers four questions: To whom does it grant access? Does it grant read or write access? For which Entries does it grant access? And finally, is it valid or a forgery?

We define three types that provide these semantics: one for implementing communal namespaces, one for implementing owned namespaces, and one for combining both.

Communal Namespaces

A capability that implements communal namespaces.
The kind of access this grants.
The namespace in which this grants access.
Remember that we assume SubspaceId and UserPublicKey to be the same types.

The subspace for which and to whom this grants access.

Successive authorisations of new UserPublicKeys, each restricted to a particular Area.

The access mode of a CommunalCapability cap is cap.access_mode.

The receiver of a CommunalCapability is the user to whom it grants access. Formally, the receiver is the final UserPublicKey in the delegations, or the user_key if the delegations are empty.

The granted namespace of a CommunalCapability is the namespace for which it grants access. Formally, the granted namespace of a CommunalCapability is its namespace_key.

The granted area of a CommunalCapability is the Area for which it grants access. Formally, the granted area of a CommunalCapability is the final Area in its delegations if the delegations are non-empty. Otherwise, it is the subspace area of the user_key.

Validity governs how CommunalCapabilities can be delegated and restricted. We define validity based on the number of delegations.

Every CommunalCapability with zero delegations is valid.

For a CommunalCapabilities cap with more than zero delegations, let (new_area, new_user, new_signature)be the final triplet of cap.delegations, and let prev_cap be the CommunalCapability obtained by removing the last triplet from cap.delegations. Denote the receiver of prev_cap as prev_receiver, and the granted area of prev_cap as prev_area.

Then cap is valid if prev_cap is valid, the granted area of prev_cap includes new_area, and new_signature is a UserSignature issued by the prev_receiver over the bytestring handover, which is defined as follows:

Owned Namespaces

A capability that implements owned namespaces.
The kind of access this grants.
The namespace for which this grants access.

The user to whom this grants access; granting access for the full namespace_key, not just to a subspace.

Authorisation of the user_key by the namespace_key.

Successive authorisations of new UserPublicKeys, each restricted to a particular Area.

The access mode of an OwnedCapability cap is cap.access_mode.

The receiver of an OwnedCapability is the user to whom it grants access. Formally, the receiver is the final UserPublicKey in the delegations, or the user_key if the delegations are empty.

The granted namespace of an OwnedCapability is the namespace for which it grants access. Formally, the granted namespace of an OwnedCapability is its namespace_key.

The granted area of an OwnedCapability is the Area for which it grants access. Formally, the granted area of an OwnedCapability is the final Area in its delegations if the delegations are non-empty. Otherwise, it is the full area.

Validity governs how OwnedCapabilities can be delegated and restricted. We define validity based on the number of delegations.

An OwnedCapability with zero delegations is valid if initial_authorisation is a NamespaceSignature issued by the namespace_key over either the byte 0x02 (if access_mode is read) or the byte 0x03 (if access_mode is write), followed by the user_key (encoded via encode_user_pk).

For an OwnedCapabilities cap with more than zero delegations, let (new_area, new_user, new_signature)be the final triplet of cap.delegations, and let prev_cap be the OwnedCapability obtained by removing the last triplet from cap.delegations. Denote the receiver of prev_cap as prev_receiver, and the granted area of prev_cap as prev_area.

Then cap is valid if prev_cap is valid, the granted area of prev_cap includes new_area, and new_signature is a UserSignature issued by the prev_receiver over the bytestring handover, which is defined as follows:

Bringing Everything Together

CommunalCapabilities and OwnedCapabilities are capability types for realising communal namespaces and owned namespaces respectively. It remainsIf you do not need to support both cases, you can also use one of CommunalCapabilities or OwnedCapabilities directly. to define a type that unifies both.

Crucially, for a given NamespaceId, all its valid capabilities should implement either a communal namespace or an owned namespace, but there should be no mixture of capabilities. It should be impossible to have people believe they work in a communal namespace, for example, only to later present an OwnedCapability that allows you to read or edit all their Entries.

To ensure a strict distinction between communal namespaces and owned namespaces, we rely on the function is_communal that specifies which kinds of capabilities are valid for which namespaces.

A Meadowcap capability.

A McCapability cap is valid if either

Access mode, receiver, granted namespace, and granted area of a McCapability cap are those of cap.inner.

Usage With Willow

We have defined capabilities and their semantics. Now what?

Writing Entries

McCapabilities with access mode write can be used to control who gets to write Entries in which namespaces and with which subspace_ids, paths, and/or timestamps. Intuitively, you authorise writing an Entry by supplying a McCapability that grants write access to the Entry together with a signature over the Entry by the receiver of the McCapability.

More precisely, Willow verifies Entries via its AuthorisationToken and is_authorised_write parameters. Meadowcap supplies concrete choices of these parameters:

To be used as an AuthorisationToken for Willow.
Certifies that an Entry may be written.
Proves that the Entry was created by the receiver of the capability.

The function meadowcap_is_authorised_write maps an Entry and a McAuthorisationToken to a Bool. It maps entry and mat to true if and only if

For this definition to make sense, the protocol parameters of Meadowcap must be compatible with those of Willow. Further, there must be concrete choices for the encoding functions encode_namespace_id, encode_subspace_id, and encode_payload_digest that determine the exact output of encode_entry.

Reading Entries

Whereas write access control is baked into the Willow data model, read access control resides in the replication layer. To manage read access via capabilities, all peers must cooperate in sending Entries only to peers who have presented a valid read capability for the Entry.

We describe the details in a capability-system-agnostic way here. To use Meadowcap for this approach, simply choose the type of valid McCapabilities with access mode read as the read capabilities.

A Meadowcap emblem: A stylised drawing of two meadowcaps (a type of mushroom), next to a hand-lettered cursive of the word "Meadowcap".