Willow General Purpose Sync Protocol

Status: Candidate (as of 19.06.2024)

The Willow data model specifies how to arrange data, but it does not prescribe how peers should synchronise data. In this document, we specify one possible way for performing synchronisation: the Willow General Purpose Sync (WGPS) protocol. This document assumes familiarity with the Willow data model.

Introduction

An ornamental drawing of two Willow data stores. Each store is a three-dimensional space, alluding to the path/time/subspace visualisations in the data model specification. Within each data store, a box-shaped area is highlighted. Between these highlighted areas flows a bidirectional stream of documents. Alfie, Betty, and Dalton lounge around the drawing.

The WGPS aims to be appropriate for a variety of networking settings, particularly those of peer-to-peer systems where the replicating parties might not necessarily trust each other. Quite a bit of engineering went into the WGPS to satisfy the following requirements:

The WGPS provides a shared vocabulary for peers to communicate with, but nothing more. It cannot and does not force peers to use it efficiently or to use the most efficient data structures internally. That is a feature! Implementations can start out with inefficient but simple implementation choices and later replace those with better-scaling ones. Throughout that evolution, the implementations stay compatible with any other implementation, regardless of its degree of sophistication.

Concepts

Data synchronisation for Willow needs to solve a number of sub-problems, which we summarise in this section.

Access Control

Peers only transfer data to peers that can prove that they are allowed to access that data. We describe how peers authenticate their requests here.

Private Area Intersection

The WGPS lets two peers determine which namespaces and Areas therein they share an interest in, without leaking any data that only one of them wishes to synchronise. We explain the underlying private area intersection protocol here.

Partial Synchronisation

To synchronise data, peers specify any number of AreaOfInterestsNote that peers need abide to the max_count and max_size limits of the AreaOfInterests only on a best-effort basis. Imagine Betty has just transmitted her 100 newest Entries to Alfie, only to then receive an even newer Entry from Gemma. Betty should forward that Entry to Alfie, despite that putting her total number of transmissions above the limit of 100. per namespace. The non-empty intersections of AreaOfInterests from both peers contain the Entries to synchronise.

The WGPS synchronises these intersections via 3d range-based set reconciliation, a technique we explain in detail here.

Post-Reconciliation Forwarding

After performing set reconciliation, peers might receive new Entries that fall into their shared AreaOfInterests. Hence, the WGPS allows peers to transmit Entries unsolicitedly.

Payload Transmission

When a peer sends an Entry, it can choose whether to immediately transmit the corresponding Payload as well. Peers exchange preferences11These preferences are not binding. The number of intersections between the peers’ AreaOfInterests can be quadratic in the number of AreaOfInterests, and we do not want to mandate keeping a quadratic amount of state. for eager or lazy Payload transmission based on payload_lengths for each intersection. These preferences are expressive enough to implement the plumtree algorithm.

Peers can further explicitly request the Payloads of arbitrary Entries (that they are allowed to access).

Payload Transformation

Peers are not restricted to exchanging Payloads verbatim, they may transform the payloads first. This can enable, for example, streaming verification or just-in-time compression.

Resource Limits

Multiplexing and management of shared state require peers to inform each other of their resource limits, lest one peer overload the other. We use a protocol-agnostic solution based on logical channels and resource handles that we describe here.

Parameters

The WGPS is generic over specific cryptographic primitives. In order to use it, one must first specify a full suite of instantiations of the parameters of the core Willow data model. The WGPS further requires parameters for access control, private area intersection, and 3d range-based set reconciliation.

Access control requires a type ReadCapability of read capabilities, a type Receiver of receivers, and a type SyncSignature of signatures issued by the Receivers. The access challenges have a length of challenge_length bytes, and the hash function used for the commitment scheme is a parameter challenge_hash whose outputs have a length of challenge_hash_length bytes.

Private area intersection requires a type PsiGroup whose values are the members of a finite cyclic group suitable for key exchanges, a type PsiScalar of scalars, and a function psi_scalar_multiplication that computes scalar multiplication in the group. We require a function hash_into_group that hashes fragments into PsiGroup. And finally, we require a type SubspaceCapability of subspace capabilities, with a type SubspaceReceiver of receivers, and a type SyncSubspaceSignature of signatures issued by the SubspaceReceivers.

3d range-based set reconciliation requires a type Fingerprint of hashes of LengthyEntries, a type PreFingerprint and a (probabilistically) injective function fingerprint_finalise from PreFingerprint into Fingerprint, a hash function fingerprint_singleton from LengthyEntries into PreFingerprint for computing the PreFingerprints of singleton LengthyEntry sets, an associative, commutative binary operation fingerprint_combine on PreFingerprint for computing the PreFingerprints of larger LengthyEntry sets, and a value fingerprint_neutral of type PreFingerprint that is a neutral element for fingerprint_combine for serving as the PreFingerprint of the empty set.

To efficiently transmit AuthorisationTokens, we decompose them into two parts: the StaticToken (which might be shared between many AuthorisationTokens), and the DynamicTokenIn Meadowcap, for example, StaticToken is the type McCapability and DynamicToken is the type UserSignature, which together yield a McAuthorisationToken. (which differs between any two Entries). Formally, we require that there is an isomorphism between AuthorisationToken and pairs of a StaticToken and a DynamicToken with respect to the is_authorised_write function.

Payload transformation requires a (not necessarily deterministic) algorithm transform_payload that converts a Payload into another bytestring.

Finally, we require a NamespaceId default_namespace_id, a SubspaceId default_subspace_id, and a PayloadDigest default_payload_digest.

Protocol

The protocol is mostly message-based, with the exception of the first few bytes of communication. To break symmetry, we refer to the peer that initiated the synchronisation session as Alfie, and the other peer as Betty.

Peers might receive invalid messages, both syntactically (i.e., invalid encodings) and semantically (i.e., logically inconsistent messages). In both cases, the peer to detect this behaviour must abort the sync session. We indicate such situations by writing that something “is an error”. Any message that refers to a fully freed resource handle is an error. More generally, whenever we state that a message must fulfil some criteria, but a peer receives a message that does not fulfil these criteria, that is an error.

Before any communication, each peer locally and independently generates some random data: a challenge_length-byte integer nonce, and a random value scalar of type PsiScalar. Both are used for cryptographic purposes and must thus use high-quality sources of randomness — they must both be unique across all protocol runs, and unpredictable.

The first byte each peer sends must be a natural number This sets the maximum payload size of that peer toThe maximum payload size limits when the other peer may include Payloads directly when transmitting Entries: when an Entry’s payload_length is strictly greater than the maximum payload size, its Payload may only be transmitted when explicitly requested.

The next challenge_hash_length bytes a peer sends are the challenge_hash of nonce; we call the bytes that a peer received this way its received_commitment.

After those initial transmissions, the protocol becomes a purely message-based protocol. There are several kinds of messages, which the peers create, encode as byte strings, and transmit mostly independently from each other.

The messages make use of the following resource handles:

The different resource handles employed by the WGPS.
Resource handle for the private set intersection part of private area intersection. More precisely, an IntersectionHandle stores a PsiGroup member together with one of two possible states:
  • pending (waiting for the other peer to perform scalar multiplication),
  • completed (both peers performed scalar multiplication).
Resource handle for ReadCapabilities that certify access to some Entries.
Resource handle for AreaOfInterests that peers wish to sync.
Resource handle that controls the matching from Payload transmissions to Payload requests.
Resource handle for StaticTokens that peers need to transmit.

The messages are divided across the following logical channels:

The different logical channels employed by the WGPS.

These logical channels are not fully logically independent: messages on some channels refer to resource handles bound on other channels. Whenever a message references a handle from another channel, but that handle has not yet been bound, processing of that message must be halted until all buffered messages in the channel for that kind of handle have been processed, or until the handle has been bound, whichever comes first.

Messages

We now define the different kinds of messages. When we do not mention the logical channel that messages of a particular kind use, then these messages are control messages that do not belong to any logical channel.

Commitment Scheme

The WGPS enforces access control by making peers prove ownership of secret keys by signing a nonce determined via a commitment scheme. Peers transmit the challenge_hash of their committed data in the first few bytes of the protocol, the CommitmentReveal message then allows them to conclude the commitment scheme:

Complete the commitment scheme to determine the challenge for read authentication.
The nonce of the sender, encoded as a big-endian unsigned integer.

Upon receiving a CommitmentReveal message, a peer can determine its challenge: for Alfie, challenge is the bitwise exclusive or of his nonce and the received nonce. For Betty, challenge is the bitwise complement of the bitwise exclusive or of her nonce and the received nonce.

Each peer must send this message at most once, and a peer should not send this message before having fully received a received_commitment.

Private Area Intersection

Private area intersection operates by performing private set intersection and requesting and supplying SubspaceCapabilities.

The result of first applying hash_into_group to some fragment for private area intersection and then performing scalar multiplication with scalar.
Set to true if the private set intersection item is a secondary fragment.

In the colour mixing metaphor, a PaiBindFragment message corresponds to mixing a data colour with one’s secret colour, and sending the mixture to the other peer.The PaiBindFragment messages let peers submit fragments to the private set intersection part of private area intersection. The freshly created IntersectionHandle binds the group_member in the pending state.

PaiBindFragment messages use the IntersectionChannel.

Finalise private set intersection for a single item.
The IntersectionHandle of the PaiBindFragment message which this finalises.
The result of performing scalar multiplication between the group_member of the message that this is replying to and scalar.

In the colour mixing metaphor, a PaiReplyFragment message corresponds to mixing one’s secret colour with a colour mixture received from the other peer, and sending the resulting colour back.The PaiReplyFragment messages let peers complete the information exchange regarding a single fragment submitted to private set intersection in the private area intersection process.

The handle must refer to an IntersectionHandle bound by the other peer via a PaiBindFragment message. A peer may send at most one PaiReplyFragment message per IntersectionHandle. Upon sending or receiving a PaiReplyFragment message, a peer updates the resource handle binding to now bind the group_member of the PaiReplyFragment message, in the state completed.

Ask the receiver to send a SubspaceCapability.

The PaiRequestSubspaceCapability messages let peers request SubspaceCapabilities, by sending the least-specific secondary fragment. This item must be in the intersection of the two peers’ fragments. The receiver of the message can thus look up the subspace in question.

A peer may send at most one PaiRequestSubspaceCapability message per IntersectionHandle.

Send a previously requested SubspaceCapability.
The handle of the PaiRequestSubspaceCapability message that this answers (hence, an IntersectionHandle bound by the receiver of this message).
A SubspaceCapability whose granted namespace corresponds to the request this answers.
The SyncSubspaceSignature issued by the receiver of the capability over the sender’s challenge.

Note that PaiReplySubspaceCapability messages do not use any logical channel. Hence, peers must be able to verify them in a constant amount of memory. Whether this is possible, depends on the capability system.The PaiReplySubspaceCapability messages let peers answer requests for SubspaceCapabilities. To do so, they must present a valid SyncSubspaceSignature over their challenge, thus demonstrating they hold the secret key corresponding to the receiver of the SubspaceCapability.

A peer may send at most one PaiReplySubspaceCapability message per PaiRequestSubspaceCapability it received.

Setup

To transmit Entries, a peer first has to register ReadCapabilities, AreaOfInterests, and StaticTokens with the other peer.

A ReadCapability that the peer wishes to reference in future messages.
The IntersectionHandle, bound by the sender, of the capability’s fragment with the longest Path in the intersection of the fragments. If both a primary and secondary such fragment exist, choose the primary one.
The SyncSignature issued by the Receiver of the capability over the sender’s challenge.

The SetupBindReadCapability messages let peers bind a ReadCapability for later reference. To do so, they must present a valid SyncSignature over their challenge, thus demonstrating they hold the secret key corresponding to receiver of the ReadCapability.

These requirements allow us to encode SetupBindReadCapability messages more efficiently.The handle must be bound to the fragment (primary, if possible) of the capability with the longest Path prefix that is in the intersection of the two peers’ fragments.

SetupBindReadCapability messages use the CapabilityChannel.

An AreaOfInterest that the peer wishes to reference in future messages.
A CapabilityHandle bound by the sender that grants access to all entries in the message’s area_of_interest.

The SetupBindAreaOfInterest messages let peers bind an AreaOfInterest for later reference. They show that they may indeed receive Entries from the AreaOfInterest by providing a CapabilityHandle bound by the sender that grants access to all entries in the message’s area_of_interest.

SetupBindAreaOfInterest messages use the AreaOfInterestChannel.

Let handle be an AreaOfInterestHandle. We then define handle_to_namespace_id(handle) to denote the granted namespace of the ReadCapability whose CapabilityHandle is the authorisation of the SetupBindAreaOfInterest that bound handle.

The SetupBindStaticToken messages let peers bind StaticTokens. Transmission of AuthorisedEntries in other messages refers to StaticTokenHandles rather than transmitting StaticTokens verbatim.

SetupBindStaticToken messages use the StaticTokenChannel.

Reconciliation

We use 3d range-based set reconciliation to synchronise the data of the peers.

The 3dRange whose Fingerprint is transmitted.
The Fingerprint of the range, that is, of all LengthyEntries the peer has in the range.
An AreaOfInterestHandle, bound by the sender of this message, that fully contains the range.
An AreaOfInterestHandle, bound by the receiver of this message, that fully contains the range.
If this message is the last of a set of messages that together cover the range of some prior ReconciliationSendFingerprint message, then this field contains the range_count of that ReconciliationSendFingerprint message. Otherwise, none.

The ReconciliationSendFingerprint messages let peers initiate and progress 3d range-based set reconciliation. Each ReconciliationSendFingerprint message must contain AreaOfInterestHandles issued by both peers; this upholds read access control.

In order to inform each other whenever they fully cover a 3dRange during reconciliation, each peer tracks two numbers: my_range_counter and your_range_counter. Both are initialised to zero. Whenever a peer sends either a ReconciliationAnnounceEntries message with want_response set to true or a ReconciliationSendFingerprint message, it increments its my_range_counter. Whenever it receives either a ReconciliationAnnounceEntries message with want_response set to true or a ReconciliationSendFingerprint message, it increments its your_range_counter. When a messages causes one of these values to be incremented, we call the22Both peers assign the same values to the same messages. value before incrementation the message's range_count.

When a peer receives a ReconciliationSendFingerprint message of range_count count, it may recurse by producing a cover of smaller 3dRanges. For each subrange of that cover, it sends either a ReconciliationSendFingerprint message or a ReconciliationAnnounceEntries message. If the last of these messages that it sends for the cover is a ReconciliationSendFingerprint message, its covers field should be set to count. The covers field of all other ReconciliationSendFingerprint messages should be set to none.

ReconciliationSendFingerprint messages use the ReconciliationChannel.

Prepare transmission of the LengthyEntries a peer has in a 3dRange as part of 3d range-based set reconciliation.
The 3dRange whose LengthyEntries to transmit.
The number of Entries the sender has in the range.
A boolean flag to indicate whether the sender wishes to receive a ReconciliationAnnounceEntries message for the same 3dRange in return.
Whether the sender promises to send the Entries in the range sorted ascendingly by subspace_id first, path second.
An AreaOfInterestHandle, bound by the sender of this message, that fully contains the range.
An AreaOfInterestHandle, bound by the receiver of this message, that fully contains the range.
If this message is the last of a set of messages that together cover the range of some prior ReconciliationSendFingerprint message, then this field contains the range_count of that ReconciliationSendFingerprint message. Otherwise, none.

The ReconciliationAnnounceEntries messages let peers announce how many Entries they have in a 3dRange by transmitting their LengthyEntries in the 3dRange. Each ReconciliationAnnounceEntries message must contain AreaOfInterestHandles issued by both peers that contain the range; this upholds read access control.

Actual transmission of the LengthyEntries in the range happens via ReconciliationSendEntry messages. The will_sort flag should be set to 1 if the sender will transmit the LengthyEntriesSorting the Entries allows the receiver to determine which of its own Entries it can omit from a reply in constant space. For unsorted Entries, peers that cannot allocate a linear amount of memory have to resort to possibly redundant Entry transmissions to uphold the correctness of 3d range-based set reconciliation. sorted in ascending order by subspace_id first, using the path as a tiebreaker. If the sender will not guarantee this order, the flag must be set to 0.

No ReconciliationAnnounceEntries message may be sent until all Entries announced by a prior ReconciliationAnnounceEntries message have been sent.

When a peer receives a ReconciliationSendFingerprint message that matches its local Fingerprint, it should reply with a ReconciliationAnnounceEntries message of count zero and want_response false, to indicate to the other peer that reconciliation of the 3dRange has concluded successfully.

When a peer receives a ReconciliationSendFingerprint message of range_count count, it may recurse by producing a cover of smaller 3dRanges. For each subrange of that cover, it sends either a ReconciliationSendFingerprint message or a ReconciliationAnnounceEntries message. If the last of these messages that it sends for the cover is a ReconciliationAnnounceEntries message, its covers field should be set to count. The covers field of all other ReconciliationAnnounceEntries messages should be set to none.

ReconciliationAnnounceEntries messages use the ReconciliationChannel.

The LengthyEntry itself.
A StaticTokenHandle, bound by the sender of this message, that is bound to the static part of the entry’s AuthorisationToken.
The dynamic part of the entry’s AuthorisationToken.

The ReconciliationSendEntry messages let peers transmit Entries as part of 3d range-based set reconciliation. These messages may only be sent after a ReconciliationAnnounceEntries message has announced the containing 3dRange, and the number of messages must not exceed the announced number of Entries. The transmitted Entries must be included in the announced 3dRange.

No ReconciliationAnnounceEntries or ReconciliationSendEntry message may be sent after a ReconciliationSendEntry message, until a sequence of zero or more ReconciliationSendPayload messages followed by exactly one ReconciliationTerminatePayload message has been sent.

ReconciliationSendEntry messages use the ReconciliationChannel.

Transmit some transformed Payload bytes.
The number of transmitted bytes.
amount many bytes, a substring of the bytes obtained by applying transform_payload to the Payload to be transmitted.
bytes: [u8]

The ReconciliationSendPayload messages let peers transmit (parts of) transformed Payloads.

Each ReconciliationSendPayload message transmits a successive (starting at byte zero) part of the result of applying transform_payload to the Payload of the Entry with the most recent ReconciliationSendEntry message by the sender. The WGPS does not concern itself with how (or whether) the receiver can reconstruct the original Payload from these chunks of transformed bytes, that is a detail of choosing a suitable transformation function.

After sending a ReconciliationSendPayload message, a peer may not send ReconciliationAnnounceEntries or ReconciliationSendEntry messages until it has sent a ReconciliationTerminatePayload message. ReconciliationSendPayload messages must only be sent when there was a corresponding ReconciliationSendEntry message that indicates which Entry the payload chunk belongs to.

ReconciliationSendEntry messages use the ReconciliationChannel.

Indicate that no more bytes will be transmitted for the currently transmitted Payload as part of set reconciliation.

The ReconciliationTerminatePayload messages let peers indicate that they will not send more payload bytes for the current Entry as part of set reconciliation. This may be because the end of the Payload has been reached, or simply because the peer chooses to not send any further bytes.

ReconciliationTerminatePayload messages use the ReconciliationChannel.

Data

Outside of 3d range-based set reconciliation peers can unsolicitedly push Entries and Payloads to each other, and they can request specific Payloads.

Transmit an AuthorisedEntry to the other peer, and optionally prepare transmission of its Payload.
The Entry to transmit.
A StaticTokenHandle bound to the StaticToken of the Entry to transmit.
The DynamicToken of the Entry to transmit.
The offset in the Payload in bytes at which Payload transmission will begin. If this is equal to the Entry’s payload_length, the Payload will not be transmitted.

The DataSendEntry messages let peers transmit LengthyEntries outside of 3d range-based set reconciliation. They further set up later Payload transmissions (via DataSendPayload messages).

To map Payload transmissions to Entries, each peer maintains a piece of state: an Entry currently_received_entryThese are used by DataSendPayload messages.. When receiving a DataSendEntry message, a peer sets its currently_received_entry to the received entry.

Initially, currently_received_entry is default_entry(default_namespace_id, default_subspace_id, default_payload_digest).

DataSendEntry messages use the DataChannel.

Transmit some transformed Payload bytes.
The number of transmitted bytes.
amount many bytes, a substring of the bytes obtained by applying transform_payload to the Payload to be transmitted.
bytes: [u8]

The DataSendPayload messages let peers transmit (parts of) transformed Payloads.

Each DataSendPayload message transmits a successive part of the result of applying transform_payload to the Payload of the currently_received_entry of the receiver. The WGPS does not concern itself with how (or whether) the receiver can reconstruct the original Payload from these chunks of transformed bytes, that is a detail of choosing a suitable transformation function.

DataSendPayload messages use the DataChannel.

Express preferences for Payload transfer in the intersection of two AreaOfInterests.
An AreaOfInterestHandle, bound by the sender of this message.
An AreaOfInterestHandle, bound by the receiver of this message.
Whether the other peer should eagerly forward Payloads in this intersection.

The DataSetMetadata messages let peers express whether the other peer should eagerly push Payloads from the intersection of two AreaOfInterests, or whether they should send only DataSendEntry messages for that intersection.

DataSetMetadata messages are not binding, they merely present an optimisation opportunity. In particular, they allow expressing the Prune and Graft messages of the epidemic broadcast tree protocol.

Bind an Entry to a PayloadRequestHandle and request transmission of its Payload from an offset.
The Entry to request.
The offset in the Payload starting from which the sender would like to receive the Payload bytes.
A resource handle for a ReadCapability bound by the sender that grants them read access to the bound Entry.

If the receiver of a DataBindPayloadRequest does not have the requested Payload and does not plan to obtain it in the future, it should signal so by freeing the PayloadRequestHandle.The DataBindPayloadRequest messages let peers explicitly request Payloads, by binding a PayloadRequestHandle to the specified entry and offset. The other peer is expected to then transmit the Payload, starting at the specified offset. The request contains a CapabilityHandle to a ReadCapability whose granted area must include the requested Entry.

DataBindPayloadRequest messages use the PayloadRequestChannel.

Set up the state for replying to a DataBindPayloadRequest message.
The PayloadRequestHandle to which to reply.

The DataReplyPayload messages let peers reply to DataBindPayloadRequest messages, by indicating that future DataSendPayload messages will pertain to the requested Payload. More precisely, upon receiving a DataReplyPayload message, a peer sets its currently_received_entry value to that to which the message’s handle is bound.

DataReplyPayload messages use the DataChannel.

Resource Control

Finally, we maintain logical channels and free resource handles, as explained in the resource control document.

Make a binding promise of available buffer capacity to the other peer.
Allow the other peer to reduce its total buffer capacity by amount.
Ask the other peer to send an ControlAbsolve message such that the receiver remaining guarantees will be target.
Notify the other peer that you have started dropping messages and will continue to do so until you receives a ControlApologise message. Note that you must send any outstanding guarantees of the logical channel before sending a ControlAnnounceDropping message.
Notify the other peer that it can stop dropping messages of this logical channel.
Ask the other peer to free a resource handle.
Indicates whether the peer sending this message is the one who created the handle (true) or not (false).

Encodings

We now describe how to encode the various messages of the WGPS. When a peer receives bytes it cannot decode, this is an error.

Parameters

To be able to encode messages, we require certain properties from the protocol parameters:

We can now define the encodings for all messages.

Commitment Scheme and Private Area Intersection

The encoding of a CommitmentReveal message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category000
3 – 5message kind000
6, 7unused00
m.nonce as a big-endian, unsigned, challenge_length-byte integer


The encoding of a PaiBindFragment message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category000
3 – 5message kind001
61 iff m.is_secondary
7unused0
encode_group_member(m.group_member)


The encoding of a PaiReplyFragment message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category000
3 – 5message kind010
6, 72-bit integer n such that 2^n gives compact_width(m.handle)
Bit 6 is 1 iff compact_width(m.handle) is 4 or 8.
Bit 7 is 1 iff compact_width(m.handle) is 2 or 8.
m.handle, encoded as an unsigned, big-endian compact_width(m.handle)-byte integer
encode_group_member(m.group_member)


The encoding of a PaiRequestSubspaceCapability message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category000
3 – 5message kind011
6, 72-bit integer n such that 2^n gives compact_width(m.handle)
Bit 6 is 1 iff compact_width(m.handle) is 4 or 8.
Bit 7 is 1 iff compact_width(m.handle) is 2 or 8.
m.handle, encoded as an unsigned, big-endian compact_width(m.handle)-byte integer


The encoding of a PaiReplySubspaceCapability message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category000
3 – 5message kind100
6, 72-bit integer n such that 2^n gives compact_width(m.handle)
Bit 6 is 1 iff compact_width(m.handle) is 4 or 8.
Bit 7 is 1 iff compact_width(m.handle) is 2 or 8.
m.handle, encoded as an unsigned, big-endian compact_width(m.handle)-byte integer
encode_subspace_capability(m.capability) — the known granted namespace is the NamespaceId of the fragment corresponding to m.handle
encode_sync_subspace_signature(m.signature)

Setup

Let m be a SetupBindReadCapability message, let granted_area be the granted area of m.capability, let frag be the fragment corresponding to m.handle, and let pre be the Path of frag.

Define out as the Area with

Then, the encoding of m is the concatenation of:

BitBig-endian bitfield
0 – 2message category001
3, 4message kind00
5unused0
6, 72-bit integer n such that 2^n gives compact_width(m.handle)
Bit 6 is 1 iff compact_width(m.handle) is 4 or 8.
Bit 7 is 1 iff compact_width(m.handle) is 2 or 8.
m.handle, encoded as an unsigned, big-endian compact_width(m.handle)-byte integer
encode_read_capability(m.capability) — the known granted namespace is the NamespaceId of frag, and the known including Area is out
encode_sync_signature(m.signature)


The encoding of a SetupBindAreaOfInterest message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category001
3, 4message kind01
5Encode m.area_of_interest.max_count and m.area_of_interest.max_size?1 iff m.area_of_interest.max_count != 0 or m.area_of_interest.max_size != 0
6, 72-bit integer n such that 2^n gives compact_width(m.authorisation)
Bit 6 is 1 iff compact_width(m.authorisation) is 4 or 8.
Bit 7 is 1 iff compact_width(m.authorisation) is 2 or 8.
m.authorisation, encoded as an unsigned, big-endian compact_width(m.authorisation)-byte integer
encode_area_in_area(m.area_of_interest.area, out), where out is the granted area of the read capability to which m.authorisation is bound
If m.area_of_interest.max_count != 0 or m.area_of_interest.max_size != 0, this is followed by the concatenation of:
BitBig-endian bitfield
0, 12-bit integer n such that 2^n gives compact_width(m.area_of_interest.max_count)
2, 32-bit integer n such that 2^n gives compact_width(m.area_of_interest.max_size)
4 – 7unused0000
m.area_of_interest.max_count, encoded as an unsigned, big-endian compact_width(m.area_of_interest.max_count)-byte integer
m.area_of_interest.max_size, encoded as an unsigned, big-endian compact_width(m.area_of_interest.max_size)-byte integer


The encoding of a SetupBindStaticToken message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category001
3, 4message kind10
5 – 7unused000
encode_static_token(m.static_token)

Reconciliation

Successive reconciliation messages often concern related 3dRanges and Entries. We exploit this for more efficient encodings by allowing to specify 3dRanges and Entries in relation to the previously sent one. To allow for this optimization, peers need to track the following pieces of state:

Given two AreaOfInterestHandles aoi1 and aoi2, we define aoi_handles_to_3drange(aoi1, aoi2) as the 3dRange that includes the same Entries as the intersection of the areas of the AreaOfInterests to which aoi1 and aoi2 are bound.


The encoding of a ReconciliationSendFingerprint message m starts with a bitfield:

BitBig-endian bitfield
0 – 2message category010
3message kind0
41 iff m.fingerprint == fingerprint_finalise(fingerprint_neutral)
51 iff m.range will be encoded relative to prev_range
61 iff m.sender_handle == prev_sender_handle
71 iff m.receiver_handle == prev_receiver_handle
8, 9ignored, or 2-bit integer n such that 2^n gives compact_width(m.sender_handle)
00 if m.sender_handle == prev_sender_handle, otherwise:
Bit 8 is 1 iff compact_width(m.sender_handle) is 4 or 8.
Bit 9 is 1 iff compact_width(m.sender_handle) is 2 or 8.
10, 11ignored, or 2-bit integer n such that 2^n gives compact_width(m.receiver_handle)
Bit 10 is 1 iff compact_width(m.receiver_handle) is 4 or 8.
Bit 11 is 1 iff compact_width(m.receiver_handle) is 2 or 8.
121 iff m.covers != none
13unused0
14, 15ignored, or 2-bit integer n such that 2^n gives compact_width(m.covers)
00 if m.covers != none, otherwise:
Bit 14 is 1 iff compact_width(m.covers) is 4 or 8.
Bit 15 is 1 iff compact_width(m.covers) is 2 or 8.

This is followed by the concatenation of:

m.covers, encoded as an unsigned, big-endian compact_width(m.covers)-byte integer, or the empty string, if m.covers == none
m.sender_handle, encoded as an unsigned, big-endian compact_width(m.sender_handle)-byte integer, or the empty string, if m.sender_handle == prev_sender_handle
m.receiver_handle, encoded as an unsigned, big-endian compact_width(m.receiver_handle)-byte integer, or the empty string, if m.receiver_handle == prev_receiver_handle
encode_fingerprint(m.fingerprint), or the empty string, if m.fingerprint == fingerprint_finalise(fingerprint_neutral)
Must match bit 5 of the first bitfield.either encode_3drange_relative_3drange(m.range, prev_range), or encode_3drange_relative_3drange(m.range, aoi_handles_to_3drange(m.sender_handle, m.receiver_handle))

The encoding of a ReconciliationAnnounceEntries message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category010
3message kind1
41 iff m.want_response == true
51 iff m.range will be encoded relative to prev_range
61 iff m.sender_handle == prev_sender_handle
71 iff m.receiver_handle == prev_receiver_handle
8, 9ignored, or 2-bit integer n such that 2^n gives compact_width(m.sender_handle)
00 if m.sender_handle == prev_sender_handle, otherwise:
Bit 0 is 1 iff compact_width(m.sender_handle) is 4 or 8.
Bit 1 is 1 iff compact_width(m.sender_handle) is 2 or 8.
10, 11ignored, or 2-bit integer n such that 2^n gives compact_width(m.receiver_handle)
Bit 2 is 1 iff compact_width(m.receiver_handle) is 4 or 8.
Bit 3 is 1 iff compact_width(m.receiver_handle) is 2 or 8.
12, 132-bit integer n such that 2^n gives compact_width(m.count)
Bit 4 is 1 iff compact_width(m.count) is 4 or 8.
Bit 5 is 1 iff compact_width(m.count) is 2 or 8.
141 iff m.will_sort == true
151 iff m.covers != none

If m.covers != none, this is followed by:

BitBig-endian bitfield
0 – 7
11111111 if the length of m.covers is greater or equal to 2^32,
11111110 if the length of m.covers is greater or equal to 2^16,
11111101 if the length of m.covers is greater or equal to 256,
11111100 if the length of m.covers is greater or equal to 252, or
the length of m.covers otherwise.

This is followed by:

the length of m.covers, encoded as an unsigned, big-endian compact_width(the length of m.covers)-byte integer, or the empty string, if the length of m.covers is less than or equal to 251
m.sender_handle, encoded as an unsigned, big-endian compact_width(m.sender_handle)-byte integer, or the empty string, if m.sender_handle == prev_sender_handle
m.receiver_handle, encoded as an unsigned, big-endian compact_width(m.receiver_handle)-byte integer, or the empty string, if m.receiver_handle == prev_receiver_handle
m.count, encoded as an unsigned, big-endian compact_width(m.count)-byte integer
Must match bit 5 of the bitfield.either encode_3drange_relative_3drange(m.range, prev_range), or encode_3drange_relative_3drange(m.range, aoi_handles_to_3drange(m.sender_handle, m.receiver_handle))

The WGPS mandates a strict cadence of ReconciliationAnnounceEntries messages followed by ReconciliationSendEntry messages, there are no points in time where it would be valid to send both. Hence, their encodings need not be distinguishable.

When it is possible to receive a ReconciliationSendEntry message, denote the preceeding ReconciliationAnnounceEntries message by announced.

The encoding of a ReconciliationSendEntry message m starts with a bitfield:

BitBig-endian bitfield
0 – 2message category010
3message kind1
41 iff m.static_token_handle == sync_enc_prev_token
51 iff m.entry will be encoded relative to prev_entry
6, 72-bit integer n such that 2^n gives compact_width(m.entry.available)
Bit 6 is 1 iff compact_width(m.entry.available) is 4 or 8.
Bit 7 is 1 iff compact_width(m.entry.available) is 2 or 8.

If bit 4 of this initial bitfield is 0, this is followed by the following byte:

If bit 4 of the initial bitfield is 0 and m.static_token_handle >= 63, this is followed by m.static_token_handle, encoded as an unsigned, big-endian compact_width(m.static_token_handle)-byte integer.

This is followed by the concatenation of:

m.entry.available, encoded as an unsigned, big-endian compact_width(m.entry.available)-byte integer
encode_dynamic_token(m.dynamic_token)
Must match bit 5 of the initial bitfield.either encode_entry_relative_entry(m.entry.entry, prev_entry), or encode_entry_in_namespace_3drange(m.entry.entry, announced.range, handle_to_namespace_id(announced.receiver_handle))

ReconciliationSendPayload and ReconciliationTerminatePayload messages need to be distinguishable from each other, bit not from ReconciliationAnnounceEntries or ReconciliationSendEntry messages.

The encoding of a ReconciliationSendPayload message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category010
3, 4message kind10
5unused0
6, 72-bit integer n such that 2^n gives compact_width(m.amount)
Bit 6 is 1 iff compact_width(m.amount) is 4 or 8.
Bit 7 is 1 iff compact_width(m.amount) is 2 or 8.
m.amount, encoded as an unsigned, big-endian compact_width(m.amount)-byte integer
m.bytes

The encoding of a ReconciliationTerminatePayload message is a single byte:

BitBig-endian bitfield
0 – 2message category010
3, 4message kind11
5 – 7unused000

Data

When encoding Entries for DataSendEntry and DataBindPayloadRequest messages, the Entry can be encoded either relative to the currently_received_entry, or as part of an Area. Such an Area out is always specified as the intersection of the Areas bound by an AreaOfInterestHandle sender_handle bound by the sender of the encoded message, and an AreaOfInterestHandle receiver_handle bound by the receiver of the encoded message.


The encoding of a DataSendEntry message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category011
3 – 5message kind000
6, 72-bit integer n such that 2^n gives compact_width(m.static_token_handle)
Bit 6 is 1 iff compact_width(m.static_token_handle) is 4 or 8.
Bit 7 is 1 iff compact_width(m.static_token_handle) is 2 or 8.
8Encode m.offset?1 iffm.offset != 0, and m.offset != m.entry.payload_length
9, 10
00, if m.offset == 0, else
01, if m.offset == m.entry.payload_length, else
Bit 9 is 1 iff compact_width(m.offset) is 4 or 8.
Bit 10 is 1 iff compact_width(m.offset) is 2 or 8.
111 iff m.entry will be encoded relative to currently_received_entry
12, 13ignored, or 2-bit integer n such that 2^n gives compact_width(sender_handle)
00 if m.entry will be encoded relative to currently_received_entry, otherwise:
Bit 12 is 1 iff compact_width(sender_handle) is 4 or 8.
Bit 13 is 1 iff compact_width(sender_handle) is 2 or 8.
14, 15ignored, or 2-bit integer n such that 2^n gives compact_width(receiver_handle)
00 if m.entry will be encoded relative to currently_received_entry, otherwise:
Bit 14 is 1 iff compact_width(receiver_handle) is 4 or 8.
Bit 15 is 1 iff compact_width(receiver_handle) is 2 or 8.
m.static_token_handle, encoded as an unsigned, big-endian compact_width(m.static_token_handle)-byte integer
encode_dynamic_token(m.dynamic_token)
m.offset, encoded as an unsigned, big-endian compact_width(m.offset)-byte integer, or the empty string, if m.offset == 0 or m.offset == m.entry.payload_length
Must match bit 11 of the initial bitfield.the empty string if encoding relative to currently_received_entryotherwise sender_handle, encoded as an unsigned, big-endian compact_width(sender_handle)-byte integer
Must match bit 11 of the initial bitfield.the empty string if encoding relative to currently_received_entry otherwise receiver_handle, encoded as an unsigned, big-endian compact_width(receiver_handle)-byte integer
Must match bit 11 of the initial bitfield.either encode_entry_relative_entry(m.entry, currently_received_entry), or encode_entry_in_namespace_area(m.entry, out, handle_to_namespace_id(receiver_handle))


The encoding of a DataSendPayload message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category011
3 – 5message kind001
6, 72-bit integer n such that 2^n gives compact_width(m.amount)
Bit 6 is 1 iff compact_width(m.amount) is 4 or 8.
Bit 7 is 1 iff compact_width(m.amount) is 2 or 8.
m.amount, encoded as an unsigned, big-endian compact_width(m.amount)-byte integer
m.bytes


The encoding of a DataSetMetadata message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category011
3 – 5message kind010
61 iff m.is_eager == true
7unused0
8, 92-bit integer n such that 2^n gives compact_width(m.sender_handle)
Bit 8 is 1 iff compact_width(m.sender_handle) is 4 or 8.
Bit 9 is 1 iff compact_width(m.sender_handle) is 2 or 8.
10, 112-bit integer n such that 2^n gives compact_width(m.receiver_handle)
Bit 10 is 1 iff compact_width(m.receiver_handle) is 4 or 8.
Bit 11 is 1 iff compact_width(m.receiver_handle) is 2 or 8.
12 – 15unused0000
m.sender_handle, encoded as an unsigned, big-endian compact_width(m.sender_handle)-byte integer
m.receiver_handle, encoded as an unsigned, big-endian compact_width(m.receiver_handle)-byte integer


The encoding of a DataBindPayloadRequest message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category011
3 – 5message kind011
6, 72-bit integer n such that 2^n gives compact_width(m.capability)
Bit 6 is 1 iff compact_width(m.capability) is 4 or 8.
Bit 7 is 1 iff compact_width(m.capability) is 2 or 8.
8Encode m.offset?1 iffm.offset != 0,
9, 10ignored, or 2-bit integer n such that 2^n gives compact_width(m.offset)
00 if m.offset == 0, otherwise:
Bit 6 is 1 iff compact_width(m.offset) is 4 or 8.
Bit 7 is 1 iff compact_width(m.offset) is 2 or 8.
111 iff m.entry will be encoded relative to currently_received_entry
12, 13ignored, or 2-bit integer n such that 2^n gives compact_width(sender_handle)
00 if m.entry will be encoded relative to currently_received_entry, otherwise:
Bit 12 is 1 iff compact_width(sender_handle) is 4 or 8.
Bit 13 is 1 iff compact_width(sender_handle) is 2 or 8.
14, 15ignored, or 2-bit integer n such that 2^n gives compact_width(receiver_handle)
00 if m.entry will be encoded relative to currently_received_entry, otherwise:
Bit 14 is 1 iff compact_width(receiver_handle) is 4 or 8.
Bit 15 is 1 iff compact_width(receiver_handle) is 2 or 8.
m.capability, encoded as an unsigned, big-endian compact_width(m.capability)-byte integer
m.offset, encoded as an unsigned, big-endian compact_width(m.offset)-byte integer, or the empty string, if m.offset == 0
Must match bit 11 of the initial bitfield.the empty string if encoding relative to currently_received_entry otherwise sender_handle, encoded as an unsigned, big-endian compact_width(sender_handle)-byte integer
Must match bit 11 of the initial bitfield.the empty string if encoding relative to currently_received_entry otherwise receiver_handle, encoded as an unsigned, big-endian compact_width(receiver_handle)-byte integer
Must match bit 11 of the initial bitfield.either encode_entry_relative_entry(m.entry, currently_received_entry), or encode_entry_in_namespace_area(m.entry, out, handle_to_namespace_id(receiver_handle))


The encoding of a DataReplyPayload message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category011
3 – 5message kind100
6, 72-bit integer n such that 2^n gives compact_width(m.handle)
Bit 6 is 1 iff compact_width(m.handle) is 4 or 8.
Bit 7 is 1 iff compact_width(m.handle) is 2 or 8.
m.handle, encoded as an unsigned, big-endian compact_width(m.handle)-byte integer

Control

To denote LogicalChannels, we use sequences of three bits. encode_channel maps


The encoding of a ControlIssueGuarantee message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category100
3 – 5message kind000
6, 72-bit integer n such that 2^n gives compact_width(m.amount)
Bit 6 is 1 iff compact_width(m.amount) is 4 or 8.
Bit 7 is 1 iff compact_width(m.amount) is 2 or 8.
8 – 10encode_channel(m.channel)
11 – 15unused00000
m.amount, encoded as an unsigned, big-endian compact_width(m.amount)-byte integer


The encoding of a ControlAbsolve message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category100
3 – 5message kind001
6, 72-bit integer n such that 2^n gives compact_width(m.amount)
Bit 6 is 1 iff compact_width(m.amount) is 4 or 8.
Bit 7 is 1 iff compact_width(m.amount) is 2 or 8.
8 – 10encode_channel(m.channel)
11 – 15unused00000
m.amount, encoded as an unsigned, big-endian compact_width(m.amount)-byte integer


The encoding of a ControlPlead message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category100
3 – 5message kind010
6, 72-bit integer n such that 2^n gives compact_width(m.target)
Bit 6 is 1 iff compact_width(m.target) is 4 or 8.
Bit 7 is 1 iff compact_width(m.target) is 2 or 8.
8 – 10encode_channel(m.channel)
11 – 15unused00000
m.target, encoded as an unsigned, big-endian compact_width(m.target)-byte integer


The encoding of a ControlAnnounceDropping message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category100
3, 4message kind10
5 – 7encode_channel(m.channel)


The encoding of a ControlApologise message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category100
3, 4message kind11
5 – 7encode_channel(m.channel)


To denote HandleTypes, we use sequences of three bits. encode_handle_type maps


The encoding of a ControlFree message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category100
3 – 5message kind011
6, 72-bit integer n such that 2^n gives compact_width(m.handle)
Bit 6 is 1 iff compact_width(m.handle) is 4 or 8.
Bit 7 is 1 iff compact_width(m.handle) is 2 or 8.
8 – 10encode_handle_type(m.handle_type)
111 iff m.mine == true
12 – 15unused0000
m.handle, encoded as an unsigned, big-endian compact_width(m.handle)-byte integer

And with that, we have all the pieces we need for secure, efficient synchronisation of namespaces. Thanks for reading!

A WGPS emblem: A stylised drawing of satellite in the night sky, backlit by the full moon.