# 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

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:

- Incremental sync: peers can detect regions of shared data with relatively sparse communication to avoid redundant data transfer.
- Partial sync: peers synchronise only those regions of data they both care about, at sub-namespace granularity.
- Access control: conformant peers only hand out data if the request authorises its access.
- Private area intersection: peers can discover common interests without disclosing any non-shared information to each other.
- Resource control: peers communicate (and enforce) their computational resource limits so as not to overload each other.
- Transport independence: peers can communicate over arbitrary reliable, ordered, byte-oriented channels, whether tcp, quic, or unix pipe.
- General efficiency: peers can make use of efficient implementation techniques, and the overall bandwidth consumption stays low.

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 $x≤64.$ This sets the maximum payload size of that peer to$2_{x}.$The 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.enum HandleTypeResource 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: Resource handle for AreaOfInterests that peers wish to sync.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.enum LogicalChannel`

### 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:

`struct CommitmentReveal`

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.

`struct PaiBindFragmentThe result of first applying hash_into_group to some fragment for private area intersection and then performing scalar multiplication with scalar.`

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.struct PaiReplyFragmentThe 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.struct PaiRequestSubspaceCapabilityThe IntersectionHandle bound by the sender for the least-specific secondary fragment for whose NamespaceId to request the 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.struct PaiReplySubspaceCapabilityThe 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.

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.

`struct SetupBindReadCapabilityA 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 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.

`struct SetupBindAreaOfInterestAn 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.

`struct SetupBindStaticTokenThe StaticToken to bind.`

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.

`Send a Fingerprint as part of 3d range-based set reconciliation.`

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.A boolean flag to indicate whether the sender wishes to receive a ReconciliationAnnounceEntries message for the same 3dRange in return.`

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.

`Transmit a LengthyEntry as part of 3d range-based set reconciliation.struct ReconciliationSendEntryThe 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.struct DataSendEntryThe 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.struct DataSendPayloadThe 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.`

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.struct DataSetEagernessWhether 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.

`struct DataBindPayloadRequestThe Entry to request.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.struct DataReplyPayloadThe 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.struct ControlIssueGuaranteeAllow the other peer to reduce its total buffer capacity by amount.struct ControlAbsolveAsk the other peer to send an ControlAbsolve message such that the receiver remaining guarantees will be target.struct ControlPleadNotify 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.struct ControlAnnounceDroppingNotify the other peer that it can stop dropping messages of this logical channel.struct ControlApologiseAsk the other peer to free a resource handle.struct ControlFreeIndicates 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:

- An encoding function encode_group_member for PsiGroup.
- When using the McSubspaceCapability type, you can use encode_mc_subspace_capability, but omitting the encoding of the namespace_key.An encoding function encode_subspace_capability for SubspaceCapabilities of known granted namespace.
- An encoding function encode_sync_subspace_signature for SyncSubspaceSignature.
- When using the McCapability type, you can use encode_mc_capability, but omitting the encoding of the namespace_key.An encoding function encode_read_capability for ReadCapabilities of known granted namespace and whose granted area is included in some known Area.
- An encoding function encode_sync_signature for SyncSignature.
- Used indirectly when encoding Entries, Areas, and 3dRanges.An encoding function for SubspaceId.
- The total order makes 3dRanges meaningful, the least element and successors ensure that every Area can be expressed as an equivalent 3dRange.A total order on SubspaceId with least element default_subspace_id, in which for every SubspaceId s there exists a successor t such that s is less than t and no other SubspaceId is greater than s and less than t.
- An encoding function encode_static_token for StaticToken.
- An encoding function encode_dynamic_token for DynamicToken.
- An encoding function encode_fingerprint for Fingerprint.

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:

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`000` |

3 – 5 | message kind`000` |

6, 7 | unused`00` |

m.nonce as a big-endian, unsigned, challenge_length-byte integer |

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

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`000` |

3 – 5 | message kind`001` |

6 | `1` iff m.is_secondary |

7 | unused`0` |

`encode_group_member(m.group_member)` |

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

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`000` |

3 – 5 | message kind`010` |

6, 7 | 2-bit integer `n` such that `2^n` gives `compact_width(m.handle)` |

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:

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`000` |

3 – 5 | message kind`011` |

6, 7 | 2-bit integer `n` such that `2^n` gives `compact_width(m.handle)` |

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:

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`000` |

3 – 5 | message kind`100` |

6, 7 | 2-bit integer `n` such that `2^n` gives `compact_width(m.handle)` |

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.

- out.subspace_id is granted_area.subspace_id if frag is a primary fragment, and any, otherwise,
- out.path is pre, and
- out.times is an open TimeRange of start zero.

Then, the encoding of m is the concatenation of:

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`001` |

3, 4 | message kind`00` |

5 | unused`0` |

6, 7 | 2-bit integer `n` such that `2^n` gives `compact_width(m.handle)` |

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:

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`001` |

3, 4 | message kind`01` |

5 | Encode 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, 7 | 2-bit integer `n` such that `2^n` gives `compact_width(m.authorisation)` |

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 |

`m.area_of_interest.max_count != 0`

or `m.area_of_interest.max_size != 0`

, this is followed by the concatenation of:Bit | Big-endian bitfield |
---|---|

0, 1 | 2-bit integer `n` such that `2^n` gives `compact_width(m.area_of_interest.max_count)` |

2, 3 | 2-bit integer `n` such that `2^n` gives `compact_width(m.area_of_interest.max_size)` |

4 – 7 | unused`0000` |

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:

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`001` |

3, 4 | message kind`10` |

5 – 7 | unused`000` |

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:

- A 3dRange prev_range, which is updated every time after proccessing a ReconciliationSendFingerprint or ReconciliationAnnounceEntries message to the message’s range. The initial value is
`default_3d_range(default_subspace_id)`

. - An AreaOfInterestHandle prev_sender_handle, which is updated every time after proccessing a ReconciliationSendFingerprint or ReconciliationAnnounceEntries message to the message’s sender_handle. The initial value is
`0`

. - An AreaOfInterestHandle prev_receiver_handle, which is updated every time after proccessing a ReconciliationSendFingerprint or ReconciliationAnnounceEntries message to the message’s receiver_handle. The initial value is
`0`

. - An Entry prev_entry, which is updated every time after proccessing a ReconciliationSendEntry message to the entry of the message’s entry. The initial value is
`default_entry(default_namespace_id, default_subspace_id, default_payload_digest)`

. - A StaticTokenHandle prev_token, which is updated every time after proccessing a ReconciliationSendEntry message to the message’s static_token_handle. The initial value is
`0`

.

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:

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`010` |

3 | message kind`0` |

4 | `1` iff `m.fingerprint == fingerprint_neutral` |

5 | `1` iff m.range will be encoded relative to prev_range |

6 | `1` iff `m.sender_handle == prev_sender_handle` |

7 | `1` 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:

Bit | Big-endian bitfield |
---|---|

0, 1 | ignored, or 2-bit integer `n` such that `2^n` gives `compact_width(m.sender_handle)` `00` if `m.sender_handle == prev_sender_handle` , otherwise: |

2, 3 | ignored, or 2-bit integer `n` such that `2^n` gives `compact_width(m.receiver_handle)` `00` if `m.receiver_handle == prev_receiver_handle` , otherwise: |

4 – 7 | unused`0000` |

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:

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`010` |

3 | message kind`1` |

4 | `1` iff `m.want_response == ` |

5 | `1` iff m.range will be encoded relative to prev_range |

6 | `1` iff `m.sender_handle == prev_sender_handle` |

7 | `1` iff `m.receiver_handle == prev_receiver_handle` |

8, 9 | ignored, or 2-bit integer `n` such that `2^n` gives `compact_width(m.sender_handle)` `00` if `m.sender_handle == prev_sender_handle` , otherwise: |

10, 11 | ignored, or 2-bit integer `n` such that `2^n` gives `compact_width(m.receiver_handle)` `00` if `m.receiver_handle == prev_receiver_handle` , otherwise: |

12, 13 | 2-bit integer `n` such that `2^n` gives `compact_width(m.count)` |

14 | `1` iff `m.will_sort == ` |

15 | unused`0` |

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:

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`010` |

3 | message kind`1` |

4 | `1` iff `m.static_token_handle == ` |

5 | `1` iff m.entry will be encoded relative to prev_entry |

6, 7 | 2-bit integer `n` such that `2^n` gives `compact_width(m.entry.available)` |

If bit 4 of this initial bitfield is `0`

, this is followed by the following byte:

- If
`m.static_token_handle < 63`

, then m.static_token_handle encoded as a single byte, - else, if
`compact_width(m.static_token_handle) == 1`

, then the byte`0x3f`

, - else, if
`compact_width(m.static_token_handle) == 2`

, then the byte`0x7f`

, - else, if
`compact_width(m.static_token_handle) == 4`

, then the byte`0xbf`

, - else, the byte
`0xff`

,

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:

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`011` |

3 – 5 | message kind`000` |

6, 7 | 2-bit integer `n` such that `2^n` gives `compact_width(m.static_token_handle)` |

8 | Encode m.offset?1 iff`m.offset != 0` , and `m.offset != m.entry.payload_length` |

9, 10 | `01` , if `m.offset == m.entry.payload_length` , else |

11 | `1` iff m.entry will be encoded relative to currently_received_entry |

12, 13 | ignored, or 2-bit integer `n` such that `2^n` gives `compact_width(sender_handle)` |

14, 15 | ignored, or 2-bit integer `n` such that `2^n` gives `compact_width(receiver_handle)` |

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:

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`011` |

3 – 5 | message kind`001` |

6, 7 | 2-bit integer `n` such that `2^n` gives `compact_width(m.amount)` |

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:

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`011` |

3 – 5 | message kind`010` |

6 | `1` iff `m.DataSetEagerness == true` |

7 | unused`0` |

8, 9 | 2-bit integer `n` such that `2^n` gives `compact_width(m.sender_handle)` |

10, 11 | 2-bit integer `n` such that `2^n` gives `compact_width(m.receiver_handle)` |

12 – 15 | unused`0000` |

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:

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`011` |

3 – 5 | message kind`011` |

6, 7 | 2-bit integer `n` such that `2^n` gives `compact_width(m.capability)` |

8 | Encode m.offset?1 iff`m.offset != 0` , |

9, 10 | ignored, or 2-bit integer `n` such that `2^n` gives `compact_width(m.offset)` |

11 | `1` iff m.entry will be encoded relative to currently_received_entry |

12, 13 | ignored, or 2-bit integer `n` such that `2^n` gives `compact_width(sender_handle)` |

14, 15 | ignored, or 2-bit integer `n` such that `2^n` gives `compact_width(receiver_handle)` |

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:

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`011` |

3 – 5 | message kind`100` |

6, 7 | 2-bit integer `n` such that `2^n` gives `compact_width(m.handle)` |

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

- ReconciliationChannel to
`000`

, - DataChannel to
`001`

, - IntersectionChannel to
`010`

, - CapabilityChannel to
`011`

, - AreaOfInterestChannel to
`100`

, - PayloadRequestChannel to
`101`

, and - StaticTokenChannel to
`110`

.

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

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`100` |

3 – 5 | message kind`000` |

6, 7 | 2-bit integer `n` such that `2^n` gives `compact_width(m.amount)` |

8 – 10 | encode_channel(m.channel) |

11 – 15 | unused`00000` |

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:

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`100` |

3 – 5 | message kind`001` |

6, 7 | 2-bit integer `n` such that `2^n` gives `compact_width(m.amount)` |

8 – 10 | encode_channel(m.channel) |

11 – 15 | unused`00000` |

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:

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`100` |

3 – 5 | message kind`010` |

6, 7 | 2-bit integer `n` such that `2^n` gives `compact_width(m.target)` |

8 – 10 | encode_channel(m.channel) |

11 – 15 | unused`00000` |

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:

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`100` |

3, 4 | message kind`10` |

5 – 7 | encode_channel(m.channel) |

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

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`100` |

3, 4 | message kind`11` |

5 – 7 | encode_channel(m.channel) |

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

- IntersectionHandle to
`000`

, - CapabilityHandle to
`001`

, - AreaOfInterestHandle to
`010`

, - PayloadRequestHandle to
`011`

, - StaticTokenHandle to
`100`

,

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

Bit | Big-endian bitfield |
---|---|

0 – 2 | message category`100` |

3 – 5 | message kind`011` |

6, 7 | 2-bit integer `n` such that `2^n` gives `compact_width(m.handle)` |

8 – 10 | encode_handle_type(m.handle_type) |

11 | `1` iff `m.mine == true` |

12 – 15 | unused`0000` |

m.handle, encoded as an unsigned, big-endian `compact_width(m.handle)` -byte integer |