On Encodings

Status: Proposal (as of 17.01.2024)

Those encodings referenced from the Meadowcap specification have status Candidate.

A perhaps curious feature of the Willow data model is that its specification does not 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. Hence, we need to precisely specify some properties and terminology around encodings.

Let $S$ be a set of values we want to encode. Then an encoding relationIn mathy terms: an encoding relation is a left-unique, left-total binary relation on $S \times {0, 1, \dots, 255}^{*}$ which defines a prefix code. assigns to each value in $S$ at least one (but possibly many) finite bytestrings, called the codes of that value. The assignment must satisfy the following properties:

each bytestring is the code of at most one value in $S$ , and
no code is a prefix of any other code.

An encoding relation in which every value has exactly one corresponding codeThe one-to-one mapping between values and codes lets us deterministically hash or sign values. is called an encoding function.

Quite often, we define an encoding relation for some set of values, and then specify a subset of its codes to obtain an encoding function. We call such a specialisation to a function a canonic subset or encoding.

A nice technique for achieving small codes is to not encode a value itself, but to encode merely how a value differs from some reference value. This requires both the party doing the encoding and the party doing the decoding to know that reference value, of course. We formally capture this notion in the concepts of relative encoding relationsSince the definitions require rather careful parsing, they are followed by an example. and relative encoding functions:

Let $S$ be a set of values we want to encode relative to some set of values $R$ . For each $s$ in $S,$ let $R_{s} \subseteq R$ denote the set of values relative to which $s$ can be encoded. Then a relative encoding relation assigns to each pair of an $s$ in $S$ and an $r$ in $R_{s}$ at least one (but possibly many) finite bytestrings, called the $r$ -relative codes of $s$ . For every fixed $r$ in $R,$ the assignment must satisfy the following properties:

each bytestring is the $r$ -relative code of at most one value in $S$ , and
no $r$ -relative code is a prefix of any other $r$ -relative code.

If there is exactly one $r$ -relative code for every $s$ in $S$ and every $r$ in $R_{s},$ we call the relative encoding relation a relative encoding function.

A toy example: we can encode unsigned bytes (natural numbers between $0$ and $255$ inclusive) relative to other unsigned bytes by encoding the difference between them as a bytestring of length one (the difference as a single unsigned byte). For simplicity, we allow this only when the difference is non-negative. So the $7$ -relative code of $12$ would be the byte 0x05 (because $12 - 7 = 5$ ). It would not be possible to encode $3$ relative to $7,$ however, since $3 - 7$ is a negative number.

In this example, both $S$ and $R$ are the set of unsigned bytes. For any unsigned byte $s,$ $R_{s}$ is the set of unsigned bytes greater than or equal to $s .$ For any fixed unsigned byte $r,$ all $r$ -relative code are unique (which also implies prefix-freeness, since all codes have the same length), so we have indeed defined a valid relative encoding relation. Note that codes might be duplicated across different $r$ — the $2$ -relative code of $3$ and the $123$ -relative code of $124$ are both 0x01, for example — but this is perfectly ok.

Compact Integer Encodings

In various places, we need to encode U64 values. When we expect small values to be significantly more common than large values, we can save space by using a variable-length encoding that encodes smaller numbers in fewer bytes than larger numbers. In this section, we define some building blocks for doing just that.

The basic idea is to use a tag — a small bitstring — to encode how many bytes will be used for encoding the actual number. We allow for actual encodings of either one, two, four, or eight bytes. To indicate those four options, we need tags of at least two bits. We can also allot more bits to a tag. When we do, the four greatest numbers that can be represented in the tag indicate the four possible encoding widths in bytes. Using any smaller number as the tag indicates that the tag itself is the U64.

Some examples before we give a formal definition: when using a four-bit tag, there are five different ways of encoding the number $7 :$

the tag can be $15$ ( $1111$ in binary), indicating an encoding in eight additional bytes, or
the tag can be $14$ ( $1110$ in binary), indicating an encoding in four additional bytes, or
the tag can be $13$ ( $1101$ in binary), indicating an encoding in two additional bytes, or
the tag can be $12$ ( $1100$ in binary), indicating an encoding in one additional byte, or
the tag can be $7$ ( $0111$ in binary), indicating an encoding in zero additional bytes.

When using a two-bit tag for the number $300,$ , there are only three options:

the tag can be $3$ ( $11$ in binary), indicating an encoding in eight additional bytes, or
the tag can be $2$ ( $10$ in binary), indicating an encoding in four additional bytes, or
the tag can be $1$ ( $01$ in binary), indicating an encoding in two additional bytes.

Now for the formal definitions:

Let n be a U64, and let tag_width be a natural number between two and eight inclusive. Then the natural number t is a (valid) tag for n of width tag_width in all of the following cases:

$t = 2^{t a g_w i d t h} - 1$ , or
$n < 25 6^{4}$ and $t = 2^{t a g_w i d t h} - 2,$ or
$n < 25 6^{2}$ and $t = 2^{t a g_w i d t h} - 3,$ or
$n < 256$ and $t = 2^{t a g_w i d t h} - 4,$ or
$n = t$ and $t \leq 2^{t a g_w i d t h} - 5 .$

Note that there might be multiple tags to choose from for any given combination of a U64 and a width, but once the tag is selected, the corresponding compact U64 encoding is unique.For any U64 n and any tag t for n of width tag_width, the corresponding compact U64 encoding is:

the unsigned little-endian 8-byte encoding of n if $t = 2^{t a g_w i d t h} - 1,$
the unsigned little-endian 4-byte encoding of n if $t = 2^{t a g_w i d t h} - 2,$
the unsigned little-endian 2-byte encoding of n if $t = 2^{t a g_w i d t h} - 3,$
the unsigned little-endian 1-byte encoding of n if $t = 2^{t a g_w i d t h} - 4,$ and
the empty string otherwise.

Examples: the minimal tag for $7$ of width four is $7,$ and the minimal tag for $300$ of width two is $1 .$ We call a tag minimal for some given U64 and width if the corresponding compact U64 encoding is shorter than that for any other valid tag for the same U64 and width. This notion coincides with being the numerically least tag for a given U64 and width.

Data Model Encodings

We now list some useful encodings for the types of the Willow data model. We assume availability of encoding functions for various parameters of Willow:

an encoding function encode_namespace_id for NamespaceId,
an encoding function encode_subspace_id for SubspaceId, and
an encoding function encode_payload_digest for PayloadDigest.

We have provided a set of test vectors here.

Path Encoding

Encodings for Paths.

`EncodePath`

We define an encoding relation EncodePath for Path. The codes in EncodePath for any Path val are the bytestrings that are concatenations of the following form:

Bits

Big-Endian Bitfield

0 – 3

A tag of width

4

for the sum of the lengths of the Components of val.

4 – 7

A tag of width

4

for the number of Components of val.

The corresponding compact U64 encoding for bits 0 – 3.

The corresponding compact U64 encoding for bits 4 – 7.

For every Component comp of val but the final one, a concatenation of the following form:

Bits	Big-Endian Bitfield
0 – 7	A tag of width $8$ for the length of comp.
The corresponding compact U64 encoding for bits 0 – 7.
The raw bytes of comp.

The length of the final Component can be reconstructed from the total length and the lengths of all prior Components.The raw bytes of the final Component of val, or the empty string if val has zero components.

We define the encoding function encode_path as the canonic subset of EncodePath obtained by using only minimal tags.

An example: encoding the Path blogideasfun with encode_path yields

0C 03 00 04 62 6C 6F 67 00 05 69 64 65 61 73 66 75 6E, because

0C is the minimal tag of width $4$ for the total path length ( $12$ ),
03 is the minimal tag of width $4$ for the number of Components,
the corresponding compact U64 encodings for both are the empty string, so they do not appear in the code,
00 04 is the minimal tag of width $8$ for the length of "blog",
the corresponding compact U64 encodings of the length of "blog" is the empty string, so it does not appear in the code,
62 6C 6F 67 is the ASCII encoding of "blog",
00 05 is the minimal tag of width $8$ for the length of "ideas",
the corresponding compact U64 encodings of the length of "ideas" is the empty string, so it does not appear in the code,
69 64 65 61 73 is the ASCII encoding of "ideas",
the length of "fun" is not encoded (it can be reconstructed as $12 - (4 + 5) = 3$ ), and
66 75 6E is the ASCII encoding of "fun".

`EncodePathRelativePath`

We define a relative encoding relation EncodePathRelativePath for any Path relative to any Path. Let val be any Path, and let rel be any Path.

Let prefix_count be a natural number such that the first prefix_count Components of val are equal to the first prefix_count Components of rel.

Then the codes in EncodePathRelativePath for val relative to rel are the bytestrings that are concatenations of the following form:

A tag of width $8$ for prefix_count, followed by the corresponding compact U64 encoding.
Any code in EncodePath for the difference from rel to val.

We define the relative encoding function path_rel_path as the canonic subset of EncodePathRelativePath obtained by

choosing the greatest possible prefix_count,
using only minimal tags, and
using only the canonic subsets of all sub-encodings.

`EncodePathExtendsPath`

We define a relative encoding relation EncodePathExtendsPath for any Path relative to any Path which is a prefix of val. The codes in EncodePathExtendsPath for any Path val relative to any Path which is a prefix of val rel are the bytestrings that are concatenations of the following form:

Any code in EncodePath for the difference from rel to val.

We define the relative encoding function path_extends_path as the canonic subset of EncodePathExtendsPath obtained by using only the canonic subsets of all sub-encodings.

Entry Encoding

Encodings for Entries.

`EncodeEntry`

We define an encoding relation EncodeEntry for Entry. The codes in EncodeEntry for any Entry val are the bytestrings that are concatenations of the following form:

The code in encode_namespace_id for val.namespace_id.
The code in encode_subspace_id for val.subspace_id.
Any code in EncodePath for val.path.
A tag of width $8$ for val.timestamp, followed by the corresponding compact U64 encoding.
A tag of width $8$ for val.payload_length, followed by the corresponding compact U64 encoding.
The code in encode_payload_digest for val.payload_digest.

We define the encoding function encode_entry as the canonic subset of EncodeEntry obtained by using only minimal tags, and using only the canonic subsets of all sub-encodings.

`EncodeEntryRelativeEntry`

We define a relative encoding relation EncodeEntryRelativeEntry for any Entry relative to any Entry. Let val be any Entry, and let rel be any Entry.

Let time_diff be the absolute value of val.timestamp - rel.timestamp

Then the codes in EncodeEntryRelativeEntry for val relative to rel are the bytestrings that are concatenations of the following form:

Bits	Big-Endian Bitfield
0	`1` iff `val.namespace_id != rel.namespace_id`
1	`1` iff `val.subspace_id != rel.subspace_id`
2	`1` iff `val.timestamp > rel.timestamp`
3, 4	A tag of width $2$ for time_diff.
5 – 7	A tag of width $3$ for val.payload_length.
If `val.namespace_id != rel.namespace_id`: any code in encode_namespace_id for val.namespace_id, otherwise: the empty string.
If `val.subspace_id != rel.subspace_id`: any code in encode_subspace_id for val.subspace_id, otherwise: the empty string.
The corresponding compact U64 encoding for bits 3, 4.
The corresponding compact U64 encoding for bits 5 – 7.
Any relative code in EncodePathRelativePath for val.path, relative to rel.path.
Any code in encode_payload_digest for val.payload_digest.

`EncodeEntryInNamespace3dRange`

We define a relative encoding relation EncodeEntryInNamespace3dRange for any Entry relative to any 3dRange including it, and the Entry’s namespace_id. Let val be any Entry, and let rel be any fitting 3dRange.

Let path_relative_to_start be true if rel.paths is an open range, and an arbitrary Bool otherwise.
Let time_relative_to_start be true if rel.times is an open range, and an arbitrary Bool otherwise.
Let time_diff be val.timestamp - rel.times.start if time_relative_to_start, and rel.times.end - val.timestamp otherwise.

Then the codes in EncodeEntryInNamespace3dRange for val relative to rel are the bytestrings that are concatenations of the following form:

Bits	Big-Endian Bitfield
0	`1` iff `val.subspace_id != rel.subspaces.start`
1	`1` iff path_relative_to_start
2	`1` iff time_relative_to_start
3, 4	A tag of width $2$ for time_diff.
5 – 7	A tag of width $3$ for val.payload_length.
If `val.subspace_id != rel.subspace_id`: any code in encode_subspace_id for val.subspace_id, otherwise: the empty string.
If `path_relative_to_start`: any relative code in EncodePathRelativePath for val.path, relative to rel.paths.start, otherwise: any relative code in EncodePathRelativePath for val.path, relative to rel.paths.end.
The corresponding compact U64 encoding for bits 3, 4.
The corresponding compact U64 encoding for bits 5 – 7.
Any code in encode_payload_digest for val.payload_digest.

Area Encoding

We define a relative encoding relation EncodeAreaInArea for any Area relative to any Area that includes the other one. Let val be any Area, and let rel be any fitting Area.

Let start_from_start and end_from_start be arbitrary Bools. If rel.times.end is open, then

start_from_start must be true, and
end_from_start must be false if and only if val.times.end is open.

Then the codes in EncodeAreaInArea for val relative to rel are the bytestrings that are concatenations of the following form:

Bits	Big-Endian Bitfield
0	`1` iff `val.subspace_id != rel.subspace_id`
1	`1` iff `val.times.end == open`
2	`1` iff start_from_start
3	`1` iff end_from_start
4, 5	A tag of width $2$ for either `val.times.start- rel.times.start` (if start_from_start), or `rel.times.end - val.times.start` (otherwise).
6, 7	A tag of width $2$ for either `val.times.end- rel.times.start` (if end_from_start), or `rel.times.end - val.times.end` (otherwise). If `val.times.end == open`, these two bits can be set arbitrarily instead.
If `val.subspace_id != rel.subspace_id`: any code in encode_subspace_id for val.subspace_id, otherwise: the empty string.
The corresponding compact U64 encoding for bits 4, 5.
The corresponding compact U64 encoding for bits 6, 7, or the empty string if `val.times.end == open`.
Any relative code in EncodePathExtendsPath for val.path, relative to rel.path.

We define the relative encoding function encode_area_in_area as the canonic subset of EncodeAreaInArea obtained by

using only minimal tags,
setting all arbitrary bits to zero,
using only the canonic subsets of all sub-encodings,
choosing start_from_start such that the value whose tag is given in bits 4, 5 is minimal (in case of a tie, choose start_from_start as false), and
choosing end_from_start such that the value whose tag is given in bits 6, 7, if any, is minimal (in case of a tie, choose end_from_start as false).

3dRange Encoding

We define a relative encoding relation Encode3dRangeRelative3dRange for any 3dRange relative to any 3dRange. Let val be any 3dRange, and let rel be any 3dRange.

Let path_start_relative_to_start and path_end_relative_to_start be true if rel.paths is an open range, and arbitrary Bools otherwise.

Let time_start_relative_to_start and time_end_relative_to_start be true if rel.times is an open range, and arbitrary Bools otherwise.

Let start_time_diff be the absolute value of val.times.start - rel.times.start if time_start_relative_to_start, and the absolute value of val.times.start - rel.times.end otherwise.

If val.times.end != open: let end_time_diff be the absolute value of val.times.end - rel.times.start if time_end_relative_to_start, and the absolute value of val.times.end - rel.times.end otherwise.

Then the codes in Encode3dRangeRelative3dRange for val relative to rel are the bytestrings that are concatenations of the following form:

Bits	Big-Endian Bitfield
0, 1	If `val.subspaces.start == rel.subspaces.start`: the bitstring `01` or `11`. If `val.subspaces.start == rel.subspaces.end`: the bitstring `10` or `11`. Otherwise: the bitstring `11`.
2, 3	If `val.subspaces.end == open`: the bitstring `00`. If `val.subspaces.end == rel.subspaces.start`: the bitstring `01` or `11`. If `val.subspaces.end == rel.subspaces.end`: the bitstring `10` or `11`. Otherwise: the bitstring `11`.
4	`1` iff path_start_relative_to_start
5	`1` iff `val.paths.end == open`
6	If `val.paths.end == open`: arbitrary. Otherwise: `1` iff path_end_relative_to_start.
7	`1` iff `val.times.end == open`
8	`1` iff time_start_relative_to_start
9	Whether to add or subtract start_time_diff to obtain the start of the time range. If time_start_relative_to_start, and `val.times.start > rel.times.start`: `1`. If time_start_relative_to_start, and `val.times.start < rel.times.start`: `0`. If not time_start_relative_to_start, and `val.times.start > rel.times.end`: `1`. If time_start_relative_to_start, and `val.times.start < rel.times.end`: `0`. Otherwise: arbitrary.
10, 11	A tag of width $2$ for start_time_diff.
12	If `val.times.end == open`: arbitrary. Otherwise: `1` iff time_end_relative_to_start.
13	Whether to add or subtract end_time_diff to obtain the end of the time range. If `val.times.end == open`: arbitrary. If time_end_relative_to_start, and `val.times.end > rel.times.start`: `1`. If time_end_relative_to_start, and `val.times.end < rel.times.start`: `0`. If not time_end_relative_to_start, and `val.times.end > rel.times.end`: `1`. If time_end_relative_to_start, and `val.times.end < rel.times.end`: `0`.
14, 15	A tag of width $2$ for end_time_diff.
If bits 0, 1 are `11`: any code in encode_subspace_id for val.subspaces.start, otherwise: the empty string.
If bits 2, 3 are `11`: any code in encode_subspace_id for val.subspaces.end, otherwise: the empty string.
If `path_start_relative_to_start`: any relative code in EncodePathRelativePath for val.paths.start, relative to rel.paths.start, otherwise: any relative code in EncodePathRelativePath for val.paths.start, relative to rel.paths.end.
If `rel.paths.end != open`: If `path_end_relative_to_start`: any relative code in EncodePathRelativePath for val.paths.end, relative to rel.paths.start, otherwise: any relative code in EncodePathRelativePath for val.paths.end, relative to rel.paths.end. , otherwise: the empty string.
The corresponding compact U64 encoding for bits 10, 11.
If `val.times.end != open`: The corresponding compact U64 encoding for bits 14, 15, otherwise: the empty string.

Capabilities

Encodings for Meadowcap and McEnumerationCapabilities.

`EncodeCommunalCapability`

We define an encoding relation EncodeCommunalCapability for CommunalCapability. Let val be any CommunalCapability.

We denote the the $i$ -th Area in val.delegations as $a re a_{i} .$ Further, let $a re a_{- 1}$ be the full area.

Then the codes in EncodeCommunalCapability for val are the bytestrings that are concatenations of the following form:

Bits Big-Endian Bitfield

0, 1

If val.access_mode == read: the bitstring 00.
Otherwise: the bitstring 01.

2 – 7 A tag of width $6$ for the length of val.delegations.

The code in encode_namespace_pk for val.namespace_key.

The code in encode_user_pk for val.user_key.

The corresponding compact U64 encoding for bits 2 – 7.

For every

i

-th triplet (area, pk, sig) of val.delegations , a concatenation of the following form:

Any relative code in EncodeAreaInArea for area, relative to $a re a_{i - 1}$ .
The code in encode_user_pk for pk.
The code in encode_user_sig for sig.

We define the encoding function encode_communal_capability as the canonic subset of EncodeCommunalCapability obtained by using only minimal tags, and using only the canonic subsets of all sub-encodings.

`EncodeOwnedCapability`

We define an encoding relation EncodeOwnedCapability for OwnedCapability. Let val be any OwnedCapability.

We denote the the $i$ -th Area in val.delegations as $a re a_{i} .$ Further, let $a re a_{- 1}$ be the full area.

Then the codes in EncodeOwnedCapability for val are the bytestrings that are concatenations of the following form:

Bits Big-Endian Bitfield

0, 1

If val.access_mode == read: the bitstring 10.
Otherwise: the bitstring 11.

2 – 7 A tag of width $6$ for the length of val.delegations.

The code in encode_namespace_pk for val.namespace_key.

The code in encode_user_pk for val.user_key.

The code in encode_namespace_sig for val.initial_authorisation.

The corresponding compact U64 encoding for bits 2 – 7.

For every

i

-th triplet (area, pk, sig) of val.delegations , a concatenation of the following form:

Any relative code in EncodeAreaInArea for area, relative to $a re a_{i - 1}$ .
The code in encode_user_pk for pk.
The code in encode_user_sig for sig.

We define the encoding function encode_owned_capability as the canonic subset of EncodeOwnedCapability obtained by using only minimal tags, and using only the canonic subsets of all sub-encodings.

Meadowcap Capability Encoding

We define an encoding relation EncodeMcCapability for McCapability. The codes in EncodeMcCapability for any McCapability val are the bytestrings that are concatenations of the following form:

If val.inner is a CommunalCapability: any code in EncodeCommunalCapability for val.inner,
otherwise: any code in EncodeOwnedCapability for val.inner.

We define the encoding function encode_mc_capability as the canonic subset of EncodeMcCapability obtained by using only the canonic subsets of all sub-encodings.

`EncodeEnumerationCapability`

We define an encoding relation EncodeMcEnumerationCapability for McEnumerationCapability. The codes in EncodeMcEnumerationCapability for any McEnumerationCapability val are the bytestrings that are concatenations of the following form:

The code in encode_namespace_pk for val.namespace_key.

The code in encode_user_pk for val.user_key.

The code in encode_namespace_sig for val.initial_authorisation.

A tag of width

8

for the length of val.delegations, followed by the corresponding compact U64 encoding.

For every

i

-th triplet (pk, sig) of val.delegations , a concatenation of the following form:

The code in encode_user_pk for pk.
The code in encode_user_sig for sig.

Authorisation Tokens

Relative encodings for MeadowcapAuthorisationTokens, suitable for the EncodeAuthorisationToken relation of Confidential Sync. It encodes AuthorisationTokens relative to the previously transmitted AuthorisedEntry (in particular, its AuthorisationToken) and relative to the Entry which is being authorised.

`EncodeCommunalCapabilityRelative`

We define a relative encoding relation EncodeCommunalCapabilityRelative for any CommunalCapability with access mode write relative to any pair of a McCapability prior_cap of access mode write and an Entry entry such that val.namespace_key == entry.namespace_id the granted area of val includes entry. Let val be any CommunalCapability with access mode write, and let rel be any fitting pair of a McCapability and an Entry.

Let shared be

zero, if prior_cap is an OwnedCapability, or else
a natural number (possibly zero) less than or equal to the lenght (i.e., the number of triplets) of the longest common prefix of val.delegations and prior_cap.inner.delegations.

Let nice_hack be

zero, if prior_cap is an OwnedCapability, and else
shared + 1.

To efficiently encode the Areas in the delegations of val, we define a sequence of PrivateAreaContexts. $c t x_{i}$ is the PrivateAreaContext whose private has

and whose rel is the $i$ -th Area in val.delegations. Further, we define $c t x_{- 1}$ as the PrivateAreaContext whose private is given as above and whose rel is the subspace area of SubspaceId entry.subspace_id.

Then the codes in EncodeCommunalCapabilityRelative for val relative to rel are the bytestrings that are concatenations of the following form:

Bits Big-Endian Bitfield

0 The bitstring 0.

1 – 3 A tag of width $3$ for nice_hack.

4 – 7 A tag of width $4$ for the length of val.delegations.

The corresponding compact U64 encoding for bits 1 – 3.

The corresponding compact U64 encoding for bits 4 – 7.

For every

i

-th triplet (area, pk, sig) of val.delegations , a concatenation of the following form:

If $i \geq s ha re d$ : any relative code in EncodePrivateAreaAlmostInArea for area, relative to $c t x_{i - 1}$ , otherwise: the empty string.
If $i \geq s ha re d$ : any code in encode_user_pk for pk, otherwise: the empty string.
If $i \geq s ha re d$ : any code in encode_user_sig for sig, otherwise: the empty string.

`EncodeOwnedCapabilityRelative`

We define a relative encoding relation EncodeOwnedCapabilityRelative for any OwnedCapability with access mode write relative to any pair of a McCapability prior_cap of access mode write and an Entry entry such that val.namespace_key == entry.namespace_id and the granted area of val includes entry. Let val be any OwnedCapability with access mode write, and let rel be any fitting pair of a McCapability and an Entry.

Let shared be

zero, if prior_cap is a CommunalCapability, or else
a natural number (possibly zero) less than or equal to the lenght (i.e., the number of triplets) of the longest common prefix of val.delegations and prior_cap.inner.delegations.

Let nice_hack be

zero, if prior_cap is a CommunalCapability, or if val.user_key != prior_cap.inner.user_key, or if val.initial_authorisation != prior_cap.inner.initial_authorisation, and else
shared + 1.

To efficiently encode the Areas in the delegations of val, we define a sequence of PrivateAreaContexts. $c t x_{i}$ is the PrivateAreaContext whose private has

Then the codes in EncodeOwnedCapabilityRelative for val relative to rel are the bytestrings that are concatenations of the following form:

Bits Big-Endian Bitfield

0 The bitstring 1.

1 – 3 A tag of width $3$ for nice_hack.

4 – 7 A tag of width $4$ for the length of val.delegations.

The corresponding compact U64 encoding for bits 1 – 3.

The corresponding compact U64 encoding for bits 4 – 7.

If nice_hack == 0: the code in encode_user_pk for val.user_key,
otherwise: the empty string.

If nice_hack == 0: The code in encode_user_sig for val.initial_authorisation.,
otherwise: the empty string.

For every

i

-th triplet (area, pk, sig) of val.delegations , a concatenation of the following form:

If $i \geq s ha re d$ : any relative code in EncodePrivateAreaAlmostInArea for area, relative to $c t x_{i - 1}$ , otherwise: the empty string.
If $i \geq s ha re d$ : any code in encode_user_pk for pk, otherwise: the empty string.
If $i \geq s ha re d$ : any code in encode_user_sig for sig, otherwise: the empty string.

`EncodeMeadowcapAuthorisationTokenRelative`

We define a relative encoding relation EncodeMeadowcapAuthorisationTokenRelative for any MeadowcapAuthorisationToken relative to any pair of an AuthorisedEntry prior_authorised_entry and an Entry entry such that the granted namespace of the val is entry.namespace_id, and the granted areaof val includes entry. The codes in EncodeMeadowcapAuthorisationTokenRelative for any MeadowcapAuthorisationToken val relative to any fitting pair of an AuthorisedEntry and an Entry rel are the bytestrings that are concatenations of the following form:

If val.capability.inner is a CommunalCapability: any relative code in EncodeCommunalCapabilityRelative for val.capability.inner, relative to rel, otherwise: any relative code in EncodeOwnedCapabilityRelative for val.capability.inner, relative to rel.
The code in encode_user_sig for val.signature.

Private Encodings

We now define some relative encodings which take care to not reveal certain parts of the values being encoded. We use these in the Read Access and Confidentiality parts of Confidential Sync.

The private encodings of Meadowcap read capabilities are relative to the combination of a PrivateInterest and the public key of the receiver. We call this combination a PersonalPrivateInterest:

1
struct PersonalPrivateInterest {
2
 
private_interest: PrivateInterest,
3
 
user_key: UserPublicKey,
4
}

Private Path Encoding

We start with a building block for more complex private encodings: the ability to encode a Path relative to one of its prefixes, while keeping secret all Components that coincide with a third Path.

1
The context necessary to privately encode Paths.
2
struct PrivatePathContext {
3
 
The Path whose Components are to be kept private.
4
 
private: Path,
5
 
The prefix relative to which we encode.
6
 
rel: Path,
7
}

We define a relative encoding relation EncodePrivatePathExtendsPath for any Path relative to any PrivatePathContext such that rel.rel is a prefix of val and rel.private is related to val. Let val be any Path, and let rel be any fitting PrivatePathContext.

Let rel_count be the number of components in rel.rel. Let private_count be the number of components in rel.private.

Then the codes in EncodePrivatePathExtendsPath for val relative to rel are the bytestrings that are concatenations of the following form:

If private_count <= rel_count: any relative code in EncodePathExtendsPath for val, relative to rel.rel,

otherwise: The concatenation of the following bytestrings:

A tag of width $8$ for the number of Components in the longest common prefix of val and rel.private, followed by the corresponding compact U64 encoding.
If rel.private is a prefix of val: any relative code in EncodePathExtendsPath for val, relative to rel.private, otherwise: the empty string.

Private Area Encoding

Next, we build up to private Area encoding. We say an Area almost includes another Area if setting the subspace_id of the first Area to that of the second Area would make the first Area include the second Area, and the subspace_ids are either equal or one of them is any.

We say a PrivateInterest almost includes an Area if

the path of the PrivateInterest relates to the paths of the Area, and
the subspace_id of the PrivateInterest is either equal to the subspace_ids of the Area, or one of them is any.

Now, we can define a private Area encoding: we encode an Area that almost includes another Area, while keeping secret a PrivateInterest that almost includes both Areas.

1
The context necessary to privately encode Areas.
2
struct PrivateAreaContext {
3
 
The PrivateInterest to be kept private.
4
 
private: PrivateInterest,
5
 
The almost containing Area relative to which we encode.
6
 
rel: Area,
7
}

We define a relative encoding relation EncodePrivateAreaAlmostInArea for any Area relative to any PrivateAreaContext such that rel.rel almost includes val and rel.private almost includes rel.rel. Let val be any Area, and let rel be any fitting PrivateAreaContext.

Let start_from_start and end_from_start be Bools, defined according to certain restrictions:

If rel.rel.times.end == open, then
- start_from_start must be true, and
- end_from_start must be false if and only if val.times.end is open.
Otherwise (rel.rel.times.end != open), they can be set arbitrarily.

Then the codes in EncodePrivateAreaAlmostInArea for val relative to rel are the bytestrings that are concatenations of the following form:

Bits	Big-Endian Bitfield
0	`1` iff `val.subspace_id != rel.rel.subspace_id`
1	`1` iff `val.subspace_id == any`
2	`1` iff start_from_start
3	`1` iff end_from_start
4, 5	A tag of width $2$ for either `val.times.start- rel.rel.times.start` (if start_from_start), or `rel.rel.times.end - val.times.start` (otherwise).
6, 7	A tag of width $2$ for either `val.times.end- rel.rel.times.start` (if end_from_start), or `rel.rel.times.end - val.times.end` (otherwise). If `val.times.end == open`, these two bits can be set arbitrarily instead.
If `val.subspace_id != open` and `val.subspace_id != rel.rel.subspace_id`: any code in encode_subspace_id for val.subspace_id, otherwise: the empty string.
The corresponding compact U64 encoding for bits 4, 5.
The corresponding compact U64 encoding for bits 6, 7, or the empty string if `val.times.end == open`.
Any relative code in EncodePrivatePathExtendsPath for val.path, relative to the PrivatePathContext with `private := rel.private.path` and `rel := rel.rel.path`.

Communal Capability Encoding

We define a relative encoding relation EncodeCommunalCapabilityRelativePrivateInterest for any CommunalCapability with val.access_mode == read relative to any Note that CommunalCapabilities are always restricted to a single SubspaceId, so PersonalPrivateInterests with subspace_id == any are never needed.PersonalPrivateInterest with rel.private_interest.subspace_id == val.user_key ,rel.private_interest.namespace_id == val.namespace_key, and such that the path of the granted area of val is a prefix of rel.private_interest.path, and such that rel.user_key is equal to the receiver of val. Let val be any such CommunalCapability, and let rel be any fitting PersonalPrivateInterest.

To efficiently and privately encode the Areas in the delegations of val, we define a sequence of PrivateAreaContexts. $c t x_{i}$ is the PrivateAreaContext whose private is rel and whose rel is the $i$ -th Area in val.delegations. Further, we define $c t x_{- 1}$ as the PrivateAreaContext whose private is rel and whose rel is the subspace area of SubspaceId rel.private.private_interest.subspace_id.

Then the codes in EncodeCommunalCapabilityRelativePrivateInterest for val relative to rel are the bytestrings that are concatenations of the following form:

A tag of width

8

for the number of triplets in val.delegations, followed by the corresponding compact U64 encoding.

For every

i

-th triplet (area, pk, sig) of val.delegations but the final one, a concatenation of the following form:

Any relative code in EncodePrivateAreaAlmostInArea for area, relative to $c t x_{i - 1}$ .
Any code in encode_user_pk for pk.
Any code in encode_user_sig for sig.

If the number of triplets in val.delegations is nonzero: any relative code in EncodePrivateAreaAlmostInArea for the final Area in val.delegations, relative to $c t x_{i - 1}$ (where $i$ is the length of val.delegations minus one),
otherwise: the empty string.

If the number of triplets in val.delegations is nonzero: any code in encode_user_sig for the final UserSignature in val.delegations,
otherwise: the empty string.

Owned Capability Encoding

We define a relative encoding relation EncodeOwnedCapabilityRelativePrivateInterest for any OwnedCapability with val.access_mode == read relative to any PersonalPrivateInterest with rel.private_interest.namespace_id == val.namespace_key, whose rel.private_interest.subspace_id is a specific SubspaceId only if the granted area of val has that SubspaceId as its subspace_id, , and such that the path of the granted area of val is a prefix of rel.private_interest.path, and such that rel.user_key is equal to the receiver of val. Let val be any such OwnedCapability, and let rel be any fitting PersonalPrivateInterest.

Then the codes in EncodeOwnedCapabilityRelativePrivateInterest for val relative to rel are the bytestrings that are concatenations of the following form:

A tag of width

8

for the number of triplets in val.delegations, followed by the corresponding compact U64 encoding.

If the number of triplets in val.delegations is nonzero: the code in encode_user_pk for val.user_key,
otherwise: the empty string.

The code in encode_user_sig for val.initial_authorisation.

For every

i

-th triplet (area, pk, sig) of val.delegations but the final one, a concatenation of the following form:

Any relative code in EncodePrivateAreaAlmostInArea for area, relative to $c t x_{i - 1}$ .
Any code in encode_user_pk for pk.
Any code in encode_user_sig for sig.

If the number of triplets in val.delegations is nonzero: any relative code in EncodePrivateAreaAlmostInArea for the final Area in val.delegations, relative to $c t x_{i - 1}$ (where $i$ is the length of val.delegations minus one),
otherwise: the empty string.

If the number of triplets in val.delegations is nonzero: any code in encode_user_sig for the final UserSignature in val.delegations,
otherwise: the empty string.

Meadowcap Capability Encoding

We define a relative encoding relation EncodeMcCapabilityRelativePrivateInterest for McCapability relative to any PersonalPrivateInterest such that the capability’s inner can be encoded relatively to the PersonalPrivateInterest via EncodeCommunalCapabilityRelativePrivateInterest or EncodeOwnedCapabilityRelativePrivateInterest, whichever applies. The codes are simply those from these two relations; the is_communal function as applied to the namespace_id of the PersonalPrivateInterest allows disambiguating how to decode.

Enumeration Capability Encoding

We define a relative encoding relation EncodeMcEnumerationCapabilityRelativePrivateInterest for any McEnumerationCapability relative to any pair of val.namespace_key and the receiver of val. The codes in EncodeMcEnumerationCapabilityRelativePrivateInterest for any McEnumerationCapability val relative to any fitting pair rel are the bytestrings that are concatenations of the following form:

Bits

Big-Endian Bitfield

0 – 7

A tag of width

8

for the number of pairs in val.delegations.

The corresponding compact U64 encoding for bits 0 – 7.

Any code in encode_namespace_sig for val.initial_authorisation.

If the number of pairs in val.delegations is nonzero: any code in encode_user_pk for val.user_key,
otherwise: the empty string.

For every pair (pk, sig) of val.delegations but the final one, a concatenation of the following form:

Any code in encode_user_pk for pk.
Any code in encode_user_sig for sig.

If the number of pairs in val.delegations is nonzero: any code in encode_user_sig for the final UserSignature in val.delegations,
otherwise: the empty string.