Willow Transfer Protocol

The RequestEntries messages let peers request Entries in a grouping (AreaOfInterest or AreaSlice). The basic information consists of the grouping, a NamespaceId, and a ReadCapability authenticating the request. The message carries various further options to make it more expressive.

First, additional options for requesting the payloads of the Entries in the grouping: a payload length threshold up to which the receiver should automatically send the payloads without further requests, and the value k for the Bab k-grouping used when sending these payloads.

Second, options regarding streaming responses. The responses always concern the entries the receiver has at the point of responding, but an additional flag can indicate that the request is long-running, asking the the receiver to keep forwarding new Entries it obtains in the future. For the immediate response, the requester can also ask for the Entries to be sent in sortedIn set reconciliation, the part where a peer sends everything they had in a range except for the items they just received can be implemented more efficiently if the received items arrive in sorted order. order.

Third, and finally, options pertaining to This specification assumes familiarity with our page on region-based set reconciliation.region-based set reconciliation:

• The sender can attach the Fingerprint over their own LengthyAuthorisedEntries in the requested grouping — the receiver can then compute the fingerprint over their LengthyAuthorisedEntries and skip sending anything in case of a match.
• The sender can specify a maximum Entry count and a maximum total Payload size. If the Entries of the receiver exceeds those thresholds, the receiver should answer with a summary (Fingerprint, number of Entries, and their total Payload size) instead of the data itself.
• The sender can allow the receiver to respond (if the count or size thresholds are exceeded) not with metadata but to instead partition the requested grouping into smaller AreaSlices and respond with RequestEntries messages of its own; this implements the symmetric, collaborative drilling-down to differences of RBSR. Such responses state which message they are responding to, as well as the original non-response message that kicked things off — this lets peers efficiently track progress on their original requests.

Note that the symmetric nature of region-based set reconciliation can lead to redundancies: if both peers send RequestEntries messages for the same grouping and then both are recursively split and reconciled, a lot of work is unnecessarily duplicated. We recommend employing some sort of symmetry-breaking. For example, the peer who initiated the connection could be responsible for detecting duplicates and stopping to process redundant messages (if both peers did this simultaneously, then symmetric requests would end up being dropped completely).

The RespondToRequestEntries messages let peers respond to RequestEntries messages. Somewhat unconventionally, a single RequestEntries is not responded to by a single RespondToRequestEntries. Instead, the process of fully responding to a RequestEntries is a sequence of steps, forming a (simple and small) state machine. RequestEntries messages indicate transitions in that state machine. When we write that a particular kind of RespondToRequestEntries “terminates the response”, that means that a final state has been reached, the request has been completely responded to and will not be interacted with again. Both peers can then clear up any state associated with that request.

The state transitions are straightforward. After receiving a RequestEntries message, there are five options:

• The first option does not involve RespondToRequestEntries messages at all: if you reply with other RespondToRequestEntries messages instead, the response is terminated once the final such message (with the is_final_response flag set to true) has been sent.
• The second option is the Decline transition, which indicates that the request will not be processed (any further) and immediately terminates the response. This transition can be taken at any time, not only as the very first transition.
• The third option is the Done transition, which signals that the locally computed Fingerprint over the requested grouping equals the own_fingerprint field of the RequestEntries message and terminates the response.
• The fourth option is the Metadata transition, which carries metadata summarising the grouping and then terminates the response.
• The final option is the ImmediateEntries transition which moves to a new state. In this state, you can send SendEntry and SendPayloadSlice messages pertaining to the request.

After sending a ImmediateEntries response, there are two further transitions. One is the Done transition, indicating that all entries and payloads have been sent and terminating the response. The other option is the LiveEntries transition. It must only be taken if the request did not set the is_oneshot flag.

After a LiveEntries transition, you can continue sending SendEntry and SendPayloadSlice messages, with the difference that these are now encoded relative to the root request and need not adhere to any promises of a particular order of entry transmissions any longer. The intuition is that the switch from ImmediateEntries to LiveEntries marks going from sending the collection of stored entries to forwarding live updates. Finally, the Done transition can be used to terminate the response.

The ImmediateEntries transition serves a second purpose: it can optionally let the sender of the transition request the LengthyAuthorisedEntries the other peer has in the same grouping.This makes the set reconciliation symmetric: both peers should send their items in each small range. The receiver is encouraged to wait with its response until a subsequent LiveEntries or Done transition and to omit from its response those entries sent by the other peer.

The RequestPayloadSlice messages let peers request a slice of the Payload of a specific Entry. Specific here means that not only its namespace_id, subspace_id, and path are used to address it, but also its payload_digest.

The RespondToRequestPayloadSlice messages let peers respond to RequestPayloadSlice messages. Analogous to RespondToRequestEntries messages, the actual Payload slice data is carried by different messages (SendPayloadSlice), the RespondToRequestPayloadSlice merely handle error reporting and request termination by stepping through a simple state machine.

The state transitions are very simple. The Decline transition, which indicates that the request will not be processed (any further) and immediately terminates the response. This transition can be taken at any time, not only as the very first transition.

The Found transition indicates that the responder has the Entry whose Payload (subslice) was requested. After doing the Found transition, the responder can then send SendPayloadSlice messages to fulfil the request.

Finally, the Done transition can be taken after the Found transition to signal that no more slices will be transmitted, terminating the response. If the responder has the Entry but not its Payload (or at least not the requested slice), the Done transition can be sent immediately after the Found transition, and likewise if the Payload of the Entry is the empty string.

Alternatively, the Done transition can be taken before the Found transition, signalling that the responder does not have the Entry matching the request.

The SendEntry messages let peers transmit LengthyAuthorisedEntries. They may specifically indicate a RequestEntries message they are responding to, or they can be sent as standalone messages.

Note that the available field of the transmitted LengthyAuthorisedEntry gives the length of the available prefix in Bab chunks, not in bytes.

The SendPayloadSlice messages let peers transmit verifiable slice streams for (parts of) Payloads. They may specifically indicate a RequestPayloadSlice or RequestEntries message they are responding to, or they can be sent as standalone messages.

When sent as a response, many of the fields can often be derived from context and are thus omitted from the actual message encoding. Specifically:

For the first SendPayloadSlice message sent in response to a RequestPayloadSlice message, after a RespondToRequestPayloadSlice message with response Found for that RequestPayloadSlice message, the following fields of the SendPayloadSlice message are predetermined:

• namespace_id must be the namespace_id of the RequestPayloadSlice message,
• subspace_id must be the subspace_id of the RequestPayloadSlice message,
• path must be the path of the RequestPayloadSlice message,
• payload_digest must be the payload_digest of the RequestPayloadSlice message,
• start must be the start of the RequestPayloadSlice message,
• k must be the k of the RequestPayloadSlice message,
• left_skip must be the right_skip of the RequestPayloadSlice message, and
• right_skip must be the right_skip of the RequestPayloadSlice message.

For every subsequent SendPayloadSlice message pertaining to the same RequestPayloadSlice message, the start is the sum of the start and the length of the preceding SendPayloadSlice message pertaining to the same RequestPayloadSlice message, and the left_skip is maximal so that only the verification metadata is contained in the transmitted slice stream that has not been covered by previous SendPayloadSlice messages yet, and the other predetermined fields stay the same.

In other words, the predetermined values make it so that peers always respond with exactly the verifiable slice stream that was requested, split over arbitrarily many slicesThis is so that peers cannot be forced to send huge individual messages. of arbitrary lengths.

When sending a SendPayloadSlice message in response to a RequestEntries message, after having sent a RespondToRequestEntries message with response ImmediateEntries or LiveEntries for that RequestEntries message, and then having sent at least one SendEntry message in response to that same RequestEntries message, some fields of the SendPayloadSlice are predetermined. For the first SendPayloadSlice per SendEntry message:

• namespace_id, subspace_id, path, and payload_digest must be equal to those of the entry of the SendEntry message,
• start must be zero,
• k must be the k of the RequestEntries message,
• left_skip must be zero, and
• right_skip must be zero.

For every subsequent SendPayloadSlice message pertaining to the same Payload message,This is fully analogous to sneding multiple SendPayloadSlice messages in response to the same RequestPayloadSlice message. the start is the sum of the start and the length of the preceding SendPayloadSlice message pertaining to that same Payload, and the left_skip is maximal so that only the verification metadata is contained in the transmitted slice stream that has not been covered by previous SendPayloadSlice messages yet, and the other predetermined fields stay the same.

The CancelOwnRequest messages let peers signal that they are no longer interested in the response(s) to a RequestEntries or RequestPayloadSlice message that they themselves had originally sent.

The UpdatePayloadLazyness messages let peers adjust the payload_lazyness of a RequestEntries message they had previously sent. This allows peers to implement the Plumtree algorithm (Leitao et al., 2007).