Protocol v2 · §§7–10

Trees and versions

Key order

Keys are compared lexicographically by their UTF-8 encodings, octet by octet, a proper prefix first: Unicode code point order. Implementations MUST NOT compare UTF-16 code units (ECMAScript’s default < and sort()), which differ when one key has a character at or above U+10000 where the other has one in U+E000–U+FFFF.

Boundary hash u(k): the first 8 bytes of SHA-256(k) as a big-endian unsigned 64-bit integer. tz(k): the number of trailing zero bits of u(k).

Trees

A tree is a set of entries with unique keys, in key order, partitioned into tree nodes.

  • Leaves (level 0). The current leaf ends after entry k if tz(k) ≥ 10, if it holds 8,192 entries, or if k is the last entry.
  • Interior level i ≥ 1. The current node ends after child c if 10 + 6i ≤ 64 and tz(last key of c) ≥ 10 + 6i, if it has 1,024 children, or if c is the last node of level i − 1.
  • Root. The single node of the lowest level that has exactly one node. A tree with one leaf has that leaf as its root; an empty tree’s root is null.
leaf:      {"e":[entry, ...],"t":"leaf"}
interior:  {"e":[[lastKey, childHash, count, bytes], ...],"l":level,"t":"node"}

record tree entry:  [id, recordHash, recordSize]     key: id          size: recordSize
file tree entry:    [fileHash, fileSize]             key: fileHash    size: fileSize

node hash = SHA-256(JCS(node))

Nodes are encoded as JCS. lastKey is the last key under the child, count the number of entries under it and bytes the sum of their sizes.

A tree is valid if and only if building its entries under these rules yields the same root. A receiver of tree nodes MUST also reject a node that is not canonically encoded, whose keys are not strictly increasing, whose interior entries do not match their children, whose children are not exactly one level below it, or (in a record tree) whose keys are not valid record ids; and a record leaf whose body lines do not match its entries by hash, size, id and type.

Note: a natural boundary depends only on its key, so any range between two boundaries can be rebuilt independently. Leaves average 1,024 entries; interior fan-out averages 64.

Access sets

Each version has two access sets, public and private.

  • A record published with "private": true, and every record of a private type, belongs to the private set; every other record to the public set.
  • Each set lists, per type it contains, the schema hash and the tree of that set’s records of the type. A private type appears in the private set only. A public type appears in the public set, with a null root if it has no public records, and also in the private set if it has private records.
  • A file belongs to each set with a record that references it. A declared file (files.add) also belongs to the private set, whether or not records reference it, and stays declared in later versions until removed (files.remove).
  • Owners MAY read both sets; other readers the public set only. Whether a collection is visible to non-owners at all is collection state outside the version.

Version root

SetObject = {
  "types": { slug: { "schema": schemaHash, "root": treeHash | null, "count": n, "bytes": b } },
  "files": { "root": treeHash | null, "count": n, "bytes": b }
}
PrivateSetObject = SetObject + { "salt": 64 hex characters }

root = {
  "underlay": 2,
  "metadata": object | null,
  "public": SetObject,
  "private": SHA-256(JCS(PrivateSetObject)) | null
}

version hash = "ulv2:" + SHA-256(JCS(root))
  • count and bytes are the tree root’s totals, or 0 for a null root.
  • The salt is 32 random bytes in hex. A writer MUST choose it once per collection and reuse it for every version, so that an unchanged private set keeps its commitment.
  • private is null if and only if the private set lists no types and no files.
  • A root has no parent pointer. Lineage, semver, messages and authorship are recorded in the version log.

A reader of the public set can verify the version hash and every public object, and learns of the private set only whether it exists. An owner also obtains the PrivateSetObject, salt included, and can verify it against the commitment.

Semver

The server that commits a version MUST assign its semver from the differences against its base, with M, m, p the base’s components:

  1. The first version is v1.0.0.
  2. A type added or removed, or a schema hash changed: v(M+1).0.0. Making a type private or public changes its schema. Every record of the type carried over from the base MUST be validated against the new schema, and the publication refused if any fails.
  3. Otherwise, any record added, removed or changed in either set, including a move between sets: vM.(m+1).0.
  4. Otherwise (metadata or file sets only): vM.m.(p+1).

A publication whose version hash equals its base’s MUST NOT create a version. Semvers are unique within a collection and strictly increasing.