Willow General Purpose Sync Protocol

Status: Proposal (as of 17.01.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).

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 hash function fingerprint_singleton from LengthyEntries into Fingerprint for computing the Fingerprints of singleton LengthyEntry sets, an associative, commutative binary operation fingerprint_combine on Fingerprint for computing the Fingerprints of larger LengthyEntry sets, and a value fingerprint_neutral of type Fingerprint that is a neutral element for fingerprint_combine for serving as the Fingerprint 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 MeadowcapAuthorisationToken. (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.

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.

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.

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.

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 from oldest to newest.
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.

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 from oldest to newest, 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.

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.

ReconciliationSendEntry 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 two pieces of state: an Entry currently_received_entry, and a U64 currently_received_offsetThese are used by DataSendPayload messages.. When receiving an DataSendEntry message whose offset is strictly less than the entry’s payload_length, a peer sets its currently_received_entry to the received entry and its currently_received_offset to the received offset.

Initially, currently_received_entry is default_entry(default_namespace_id, default_subspace_id, default_payload_digest), and currently_received_offset is zero.

DataSendEntry messages use the DataChannel.

Transmit some Payload bytes.
The number of transmitted bytes.
amount many bytes, to be added to the Payload of the receiver’s currently_received_entry at offset currently_received_offset.
bytes: [u8]

The DataSendPayload messages let peers transmit Payloads.

A DataSendPayload message may only be sent if its amount of bytes plus the receiver’s currently_received_offset is less than or equal to the payload_length of the receiver’s currently_received_entry. The receiver then increases its currently_received_offset by amount. If the currently_received_entry was set via a DataReplyPayload message, the receiver also increases the offset to which the PayloadRequestHandle is bound.

DataSendPayload messages use the DataChannel.

Express a preference whether the other peer should eagerly forward Payloads in the intersection of two AreaOfInterests.
Whether Payloads should be pushed.
An AreaOfInterestHandle, bound by the sender of this message.
An AreaOfInterestHandle, bound by the receiver of this message.

The DataSetEagerness 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.

DataSetEagerness 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 and currently_received_offset values to those to which the message’s handle is bound.

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:

Prior to receiving any corresponding message, prev_range, prev_sender_handle, prev_receiver_handle, prev_entry, and prev_token are undefined and must not be referenced.

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_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

If either bit 6 or 7 of this initial bitfield are 0, this is followed by the following bitflag:

BitBig-endian bitfield
0, 1ignored, 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.
2, 3ignored, 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.
4 – 7unused0000

This is followed by the concatenation of:

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_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
15unused0
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))

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.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 DataSetEagerness message m is the concatenation of:

BitBig-endian bitfield
0 – 2message category011
3 – 5message kind010
61 iff m.DataSetEagerness == 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.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