Prefix pruning

old.subspace_id == new.subspace_id and new.path is a prefix of old.path and new is newer than old

There are no two of its entries old and new such that

All Entries have same namespace_id

A set of Authorised Entries such taht

An entry e1 overwrites another Entry e2 if

e2.timestamp == e1.timestamp && e2.payload_digest < e1.payload_digest && e2.payload_length < e1.payload_length

e2.timestamp == e1.timestamp && e2.payload_digest < e1.payload_digest

e2.timestamp < e1.timestamp

A path s is a prefix t of another path if the first components of t are exactly the components of s

Time since UNIX epoch in microseconds

Sequence of bytestrings

How do we store them?

Indicates whether the AuthoristionToken does provide write permission for entry.

Function is_authorised_write that maps an Entry and an AuthorisationToken to a Bool.

Proving write permission

Limit the size of paths

Limit the number of path components

Limit the length of path components

Type AuthorisationToken

Function hash_payload that maps bytes into PayloadDigest

Totally ordered Type PayloadDigest for content addressing

Nat max_path_length

Nat max_component_count

Natural number max_component_length

Type SubspaceId

Read and write access can be controlled through policies.

Namespaces

Type NamespaceId

Parameters

The idea is to be generic over a set of parameters. Interoperability between instances of the protocol with different parameters are not interoperable, and it’s meant that way.

It’s kind of a protocol framework

This enables Willow to be adapted to different environments, like resource-constrained systems.

For example, Earthstar is based on Willow, and every Earthstart application should be compatible?

The compatibility happens at a higher level of the stack.

So my first thought is: It never goes offline as long as people are replicating your data.

Higher-order protocol

The Three Dimensions of Data

Data from a photo-sharing app should live separate from a Go playing application.

You can then aggregate subspaces into namespaces

Willow allows for an extra dimension, subspaces. So a user writes to each own separate universe of data.

You modify /blog/idea/2

Then you decide that the whole /blog/idea thing was a bad idea

Something like overwriting a directory in a file system with an empty file

A system for giving meaningful hierarchical names to arbitrary sequences of bytes

Data Model

When stores of the same namespace in different devices belong to the same namespace, they deterministically sync with each other.

Usually these claims need a bit of an extra amount of salt.

Data storage which never goes offline

A protocol for peer-to-peer data stores.