On Encodings

Status: Proposal (as of 17.01.2024)

A perhaps curious feature of the Willow data model is that its specifications rarely talk about encodings. We11Let’s be honest: Aljoscha strongly believe that specifications should concern themselves with purely logical data types as long as possible, treating encodings as a minor and ultimately interchangeable detail. When specifications define concepts in terms of their encodings, results usually end up miserably underspecified (see JSON) or full of incidental complexity (see XML).

Nevertheless, protocols that deal with persistent storage and network transmissions eventually have to serialise data. In this document, we give both some generic definitions around arbitrary encodings, and some specific encodings that recur throughout the Willow family of specifications.

Encodings, In Detail

The Willow protocols are generic over user-supplied parameters. Invariably, some values of the user-supplied types need to be encoded, so there also have to be user-supplied definitions of how to encode things. But not every function that turns values into byte strings defines an encoding.

Hence, we formally define what we mean by encodings. We first give a succinct, rather mathematical definition, followed by a more accessible English explanation.

An encoding function encode_s for a set S is a function from S to the set of bytestrings, such that there exists a function decode_s such that:

• for every s in S and every bytestring b that starts with encode_s(s), we have $decode\_s(\text{b})=\text{s}\text{,}$ and
• for every s in S and every bytestring b that does not start with encode_s(s), we have $decode\_s(\text{b})\ne \text{s}\text{.}$

In plain language:

• encode_s must deterministically map any value of type S to exactly one bytestring.

  Input	Output	Correctness
  	“turtle”
  	“turtle” | “tortoise”

• Further, there must be a corresponding decoding function decode_s. This function must map valid encodings back to values of type S, and it must report a decoding error for any input string that does not start with a valid encoding of any value of type S.

  Input	Output	Correctness
  “turtle”
  “tortoise”
  “turtle”
  “tortoise”

• And finally, appending arbitrary bytes to a valid encoding must not cause any change in the return value of decode_s.This requirement makes it so we can encode sequences of multiple values by simply concatenating their encodings, without running the risk that the resulting string would be a valid encoding of a different value as well.

  Input	Output	Correctness
  “turtle”
  “turtleneck”
  “turtle”
  “turtleneck”
  “turtle”
  “turtleneck”

Encoding Techniques

We now prepare to define some specific encodings for several datatypes of Willow.

When designing encodings, there rarely exists a single best solution. Different scenarios might warrant different trade-offs between encoding and decoding time, encoding size, or simplicity. Furthermore, additional context can often enable more efficient encodings than general-purpose solutions. For example, a database that groups Entries by namespace_id would not need to encode the namespace_id of every individual Entry.

For these reasons, we encourage you to take the following suggested encodings with a grain of salt, and to look for contextual information that you could leverage to obtain even more efficient encodings for your specific use cases.

To encode small numbers with fewer bytes than large numbers, we define for any U64 n the value compact_width(n) as

• $1\text{,}$ if $\text{n}<256\text{,}$ or
• $2\text{,}$ if $\text{n}<256^2\text{,}$ or
• $4\text{,}$ if $\text{n}<256^4\text{,}$ or
• $8\text{,}$ otherwise.

Data Model Encodings

When encoding Paths, we want to use fixed-width unsigned integers of minimal width. Hence, we define:

path_length_power is the least natural number such that $256^{path\_length\_power}\ge max\_component\_length\text{.}$ We can represent the length of any Component in path_length_power bytes. UPathLengthPower denotes the type of numbers between zero (inclusive) and $256^{path\_length\_power}$ (exclusive).

path_count_power is the least natural number such that $256^{path\_count\_power}\ge max\_component\_count\text{.}$ We can represent the number of Components of any Path in path_count_power bytes. UPathCountPower denotes the type of numbers between zero (inclusive) and $256^{path\_count\_power}$ (exclusive).

encode_path

To encode a Path p, we define encode_path(p) as the concatenation of

• the number of Components of p, encoded as a big-endian UPathCountPower,
• for each Component of p,
  • the length of the Component, encoded as a big-endian UPathLengthPower, followed by the bytes of the Component.

encode_entry

To encode an Entry e, let encode_namespace_id be an encoding function for NamespaceId, let encode_subspace_id be an encoding function for SubspaceId, and let encode_payload_digest be an encoding function for PayloadDigest. We then define encode_entry(e) as the concatenation of:

Relativity

When encoding Willow objects, we can often achieve smaller encoding sizes by encoding how some object differs from another. In this section, we define several such relative encodings.

In all subsequent definitions, whenever the value open is part of a numeric computation or comparison, it should be treated as a very large number, say, $2^{9999}\text{.}$ The definitions all ensure that the resulting values never have to be encoded.

encode_path_relative_path

To encode a Path p relative to a reference Path ref, we define encode_path_relative_path(p, ref) as the concatenation of:

encode_entry_relative_entry

To encode an Entry e relative to a reference Entry ref, we first define time_diff as the absolute value of e.timestamp - ref.timestamp. We then define encode_entry_relative_entry(e, ref) as the concatenation of:

encode_entry_in_namespace_area

To encode an Entry e that is included in an outer Area out in a namespace of NamespaceId namespace_id, we first define time_diff as the minimum of e.timestamp - out.times.start and out.times.end - e.timestamp. We then define encode_entry_in_namespace_area(e, out, namespace_id) as the concatenation of:

encode_entry_in_namespace_3drange

To encode an Entry e that is included in a 3dRange out in a namespace of NamespaceId namespace_id, we first define time_diff as the minimum absolute value of e.timestamp - out.times.start and e.timestamp - out.times.end. We then define encode_entry_in_namespace_3drange(e, out, namespace_id) as the concatenation of:

encode_area_in_area

To encode an Area a that is included in an outer Area out, we first define start_diff as the minimum of a.times.start - out.times.start and out.times.end - a.times.start, and we define end_diff as the minimum of a.times.end - out.times.start and out.times.end - a.times.end. We then define encode_area_in_area(a, out) as the concatenation of:

encode_3drange_relative_3drange

To encode a 3dRange r relative to a reference 3dRange ref, we first define

• start_to_start as the absolute value of r.times.start - ref.times.start,
• start_to_end as the absolute value of r.times.start - ref.times.end,
• end_to_start as the absolute value of r.times.end - ref.times.start,
• end_to_end as the absolute value of r.times.end - ref.times.end,
• start_time_diff as the minimum of start_to_start and start_to_end, and
• end_time_diff as the minimum of end_to_start and end_to_end.

Capabilities

Encodings for Meadowcap and McSubspaceCapabilities.

encode_subspace_capability

To encode a McSubspaceCapability c, we define encode_mc_subspace_capability(c) as the concatenation of:

encode_mc_capability

To encode a McCapability c whose granted area is know to be included in some22If no smaller containing Area is known from context, use the full area. Area out, we define encode_mc_capability(c) depending on whether c.inner is a CommunalCapability or an OwnedCapability.

If c.inner is a CommunalCapability, then encode_mc_capability(c) is the concatenation of:

If c.inner is an OwnedCapability, then encode_mc_capability(c) is the concatenation of: