Willow Drop Format

Parameters
Format
Transport

An ornamental drawing of various characters transporting and discovering cardboard boxes. Dalton is looking at a map, unaware of the cardboard boxes behind the bush next to them. Alfie is transporting two cardboard boxes on the back of a bicycle. Betty is preparing to launch a cardboard box with a catapult, and seems rather pleased about it. You really could transport Willow data using any of the means above.The Confidential Sync protocol presents a way for two peers with an established connection to efficiently exchange data. But running the necessary infrastructure to establish such connections (e.g. a STUN server, distributed hash table, or relay servers) is a non-trivial task, limiting who can operate them.

The Willow Drop Format presents a way for peers to transmit data to each other asynchronously and via completely user-improvised channels.

Instead of statefully coordinating which data to exchange, the Drop Format encodes drops, arbitrary sets of Entries and Payloads compiled into a single bytestring. A drop can then be treated as a kind of static store which can be joined with any other store as per the Willow Data Model.

A diagram of an ad-hoc network. An old computer connects to a newer desktop computer via a USB key. The newer desktop computer connects to a smartphone via email. The smartphone connects to another smartphone via a messaging app. And that smartphone connects to a laptop via a local wireless connection. An example flow of Willow data travelling from device to device, first via USB key, then email, then a messaging app, then local wireless.Drops are then shared via informal ad-hoc infrastructure:

USB keys
SD cards
CDs
Email attachments
Instant messages
Torrents
Or whatever means users have at hand.

Drops will often undoubtedly contain stale data that users are already aware of or no longer need. But what the Drop Format gives up in efficiency it more than makes up for in simplicity and flexibility. It is simple to implement, and works with the infrastructure users already have.

Parameters

See Drop Format Parameters for a default recommendation of parameters.In order to use the drop format, one must first specify a full suite of instantiations of the parameters of the core Willow data model. The hash_payload parameter of the data model must be a member of the Bab family of hash functions. In addition to this, the drop format requires the following:

An encoding function encode_namespace_id for NamespaceId,
An encoding function encode_subspace_id for SubspaceId,
An encoding function encode_payload_digest for PayloadDigest,
When using MeadowcapAuthorisationToken as the type of AuthorisationTokens, you can use EncodeMeadowcapAuthorisationTokenRelative.A relative encoding relation EncodeAuthorisationToken encoding AuthorisationTokens relative to pairs of an AuthorisedEntry (the previously encoded AuthorisedEntry) and an Entry (the Entry currently being encoded),
a NamespaceId default_namespace_id,
a SubspaceId default_subspace_id,
a PayloadDigest default_payload_digest,
an AuthorisationToken default_authorisation_token which authorises default_entry(default_namespace_id, default_subspace_id, default_payload_digest), and

Format

A drop is a collection of entries, together with verifiable subslices of their payloads. The payload slice verification relies on Bab; drops store the baseline verifiable slice streams of payload slices.

Let entries a sequence of pairs of a PossiblyAuthorisedEntries and a sequence of non-overlapping slices of payload chunks with stricly increasing start offsets. The PossiblyAuthorisedEntries must all come from a single namespace with NamespaceId namespace. The Sideloading Protocol then defines how to encode this sequence as a single bytestring (the corresponding drop).

Let $e n t r y_{- 1}$ be the result of default_entry(default_namespace_id, default_subspace_id, default_payload_digest), and let $a u t h_{- 1}$ be default_authorisation_token.

Then, the actual drop is the concatenation of the following:

A tag of width

8

for the length (number) of entries, followed by the corresponding compact U64 encoding.

The code in encode_namespace_id for namespace.

For every

i

-th pair ((

e n t r y_{i}

a u t h_{i}

p a y l o a d_s l i ce s_{i}

) of entries , a concatenation of the following form:

Bits Big-Endian Bitfield

0 1 iff $e n t r y_{i}$ .subspace_id != $e n t r y_{i - 1}$ .subspace_id

1 1 if $e n t r y_{i}$ .timestamp > $e n t r y_{i - 1}$ .timestamp, 0 if $e n t r y_{i}$ .timestamp < $e n t r y_{i - 1}$ .timestamp, arbitrary if $e n t r y_{i}$ .timestamp == $e n t r y_{i - 1}$ .timestamp.

2, 3 A tag of width $2$ for abs( $e n t r y_{i}$ .timestamp - $e n t r y_{i - 1}$ .timestamp).

4, 5 A tag of width $2$ for $e n t r y_{i}$ .payload_length.

6, 7

Two bits, selected as follows:

If $p a y l o a d_s l i ce s_{i}$ is empty, these two bits may be set to 00.
If $p a y l o a d_s l i ce s_{i}$ consists of a single slice, and that slice constitutes the full payload of $e n t r y_{i}$ , these two bits may be set to 01.
If $p a y l o a d_s l i ce s_{i}$ consists of a single slice, and that slice starts at chunk index zero, these two bits may be set to 10.
These two bits may always be set to 11.

If $e n t r y_{i}$ .subspace_id != $e n t r y_{i - 1}$ .subspace_id: any code in encode_subspace_id for $e n t r y_{i}$ .subspace_id,
otherwise: the empty string.

Any relative code in EncodePathRelativePath for

e n t r y_{i}

.path, relative to

e n t r y_{i - 1}

.path.

The corresponding compact U64 encoding for bits 2, 3.

The corresponding compact U64 encoding for bits 4, 5.

Any code in encode_payload_digest for $e n t r y_{i}$ .payload_digest.

Any relative code in EncodeAuthorisationToken for

a u t h_{i}

, relative to the pair of (

e n t r y_{i - 1}

a u t h_{i - 1}

) and

e n t r y_{i}

If bits 6, 7 are 00: the empty string.
If bits 6, 7 are 01: the raw bytes of the payload of $e n t r y_{i}$ .
If bits 6, 7 are 10: the concatenation of
- a tag of width $8$ for the length of the slice in chunks, followed by the corresponding compact U64 encoding, and
- the raw bytes of the 64-grouped baseline verifiable slice stream of the single slice in $p a y l o a d_s l i ce s_{i}$ .

If bits 6, 7 are 11: the concatenation of

a tag of width $8$ for the number in slices in $p a y l o a d_s l i ce s_{i}$ , followed by the corresponding compact U64 encoding,
a tag of width $8$ for the final chunk index (inclusive) of the final slice in $p a y l o a d_s l i ce s_{i}$ , followed by the corresponding compact U64 encoding, and

For every

s l i c e_{j}

p a y l o a d_s l i ce s_{i}

, a concatenation of the following form:

A tag of width $8$ for the start chunk index of $s l i c e_{j}$ minus the end chunk index of the previously encoded slice for this entry (or zero for the first slice of the entry), followed by the corresponding compact U64 encoding.
A tag of width $8$ for the length of $s l i c e_{j}$ in chunks, followed by the corresponding compact U64 encoding.
The raw bytes of the 64-grouped baseline verifiable slice stream of $s l i c e_{j}$ , with the maximal left-skip such that the only omitted node data has been included in the encoding of an earlier slice in $p a y l o a d_s l i ce s_{i}$ .

Transport

Once created, a drop can be transported by whatever means a single bytestring can be transferred, so that the decoded entries can be ingested by its recipients.

We highly recommend encrypting drops for transport.

A Sideloading emblem: A stylised drawing of tufty grass growing in between the cracks of paving stones, next to a graffiti-styled rendition of the word "Sideload".