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.

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

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).

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.

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:

• generate_keys maps a seed to a public key and a corresponding secret key.
• sign maps a secret key and a bytestring to a signature of the bytestring.
• verify takes a public key, a signature, and a bytestring, and returns whether the signature had been created with the secret key that corresponds to the given public key.

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

• In owned namespaces, all valid capabilities stem from knowing a particular secret key of the namespace_signature_scheme.A signature scheme namespace_signature_scheme consisting of algorithms namespace_generate_keys, namespace_sign, and namespace_verify. The public keys have type NamespacePublicKey, and the signatures have type NamespaceSignature.
• An encoding function encode_namespace_pk for NamespacePublicKey.
• An encoding function encode_namespace_sig for NamespaceSignature.
• Users identities are public keys of the user_signature_scheme. Further, SubspaceIds must be public keys of the user_signature_scheme as well. In communal namespaces, all valid capabilities stem from knowing a particular secret key of the user_signature_scheme.A signature scheme user_signature_scheme consisting of algorithms user_generate_keys, user_sign, and user_verify. The public keys have type UserPublicKey, and the signatures have type UserSignature.
• An encoding function encode_user_pk for UserPublicKey.
• An encoding function encode_user_sig for UserSignature.
• A function is_communal that maps NamespacePublicKeys to booleans, determining whether a namespace of a particular NamespaceId is communal or owned.
• Limits on the sizes of the Paths and their Components that can appear in capabilities:
  • A natural number max_component_length for limiting the length of individual Components.
  • A natural number max_component_count for limiting the number of Components per Path.
  • A natural number max_path_length for limiting the overall size of Paths.

A Meadowcap instantiation is compatible with Willow if

• the Willow parameter NamespaceId is equal to the Meadowcap parameter NamespacePublicKey,
• the Willow parameter SubspaceId is equal to the Meadowcap parameter UserPublicKey, and
• the Willow parameters max_component_length, max_component_count, and max_path_length are equal to the Meadowcap parameters max_component_length, max_component_count, and max_path_length respectively.

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

Capabilities

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

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:

• If prev_cap.delegations is empty, then handover is the concatenation of the following bytestrings:
  • the byte 0x00 (if prev_cap.access_mode is read) or the byte 0x01 (if prev_cap.access_mode is write),
  • encode_namespace_pk(prev_cap.namespace_key),
  • encode_area_in_area(new_area, prev_area),
  • encode_user_pk(new_user).
• Otherwise, let prev_signature be the UserSignature in the last triplet of prev_cap.delegations. Then handover is the concatenation of the following bytestrings:
  • encode_area_in_area(new_area, prev_area),
  • encode_user_sig(prev_signature).
  • encode_user_pk(new_user).

Owned Namespaces

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:

• If prev_cap.delegations is empty, then handover is the concatenation of the following bytestrings:
  • encode_area_in_area(new_area, prev_area),
  • encode_user_sig(prev_cap.initial_authorisation).
  • encode_user_pk(new_user).
• Otherwise, let prev_signature be the UserSignature in the last triplet of prev_cap.delegations. Then handover is the concatenation of the following bytestrings:
  • encode_area_in_area(new_area, prev_area),
  • encode_user_sig(prev_signature).
  • encode_user_pk(new_user).

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 McCapability cap is valid if either

• cap.inner is a valid CommunalCapability and is_communal(cap.inner.namespace_key) is true, or
• cap.inner is a valid OwnedCapability and is_communal(cap.inner.namespace_key) is false.

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:

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

• mat.capability is valid,
• the access mode of mat.capability is write,
• the granted area of mat.capability includes entry, and
• user_verify(receiver, mat.signature, encode_entry(entry)) is true, where receiver is the receiver of mat.capability.

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.