Protocol v3 · §§3, 4, 6

Files and versions

Sorted-record-files

A sorted-record-file holds lines in key order and a table of contents. Each block and the footer is one gzip member (RFC 1952). A reader MUST accept any valid gzip member. Nothing that is hashed depends on compressed bytes.

[record block]… [key block]… [footer] [trailer]

entry, in a file from an upload:  [kind, type, id, hash, size, block, offset]
entry, in a rebuilt file:         [kind, type, id, hash, size, block, offset, commit]
  • Record blocks. The file’s lines, in order, cut into blocks. A block closes after the first line that brings its uncompressed size (lines and their \n) to 262,144 bytes or more. The last block closes at the last line. A file with no lines has no record blocks.
  • Key blocks. The entries, in order, cut into blocks of 1,024 entries; the last block holds the rest. A key block’s uncompressed bytes are its entries, each as JCS followed by \n.
  • A file holds at most 1,048,576 entries.

Entries

Each line has one or more entries.

  • kind is "r" for a record line, "x" for a removal line, and "w" for a record whose line is withheld (a takedown).
  • hash is the line’s hash, or null for a removal. size is the line’s size.
  • block is the number of the record block holding the line, from 0. offset is the byte offset of the line within that block’s uncompressed bytes. Both are null for "w", which has no line in the file.
  • commit is the number of the commit that wrote the row.

A file is labeled if its entries carry commit, and unlabeled otherwise. All entries of a file are one or the other, and "w" entries appear only in labeled files. Entries are in key order; in a labeled file, entries with the same key are in ascending commit order, and no two have the same commit. In an unlabeled file keys are unique.

Lines are in the order of their first entry. In a labeled file, consecutive entries with the same key, the same kind, and the same hash (a row rewritten unchanged) share one line: they have the same block, offset, and size. No other entries share a line. Sharing is a rule, not a choice, so that the entries alone decide the lines.

The footer’s uncompressed bytes are the JCS of:

{"content": {
   "underlay": 3,
   "labeled": boolean,
   "entries": n, "lines": n, "records": n, "removals": n, "withheld": n,
   "bytes": total uncompressed size of the record blocks,
   "first": [type, id] | null, "last": [type, id] | null,
   "commits": [lowest, highest] | null,
   "keyBlocks": [[type, id, hash, entries], …]
 },
 "locator": {
   "recordBlocks": [compressed length, …],
   "keyBlocks": [compressed length, …]
 }}

file id = SHA-256(JCS(content)), lowercase hex
trailer = 55 4C 33 53 52 46 0A 00 ("UL3SRF\n\0"), then the footer's compressed
          length as an unsigned 64-bit big-endian integer: 16 bytes
  • keyBlocks lists, for each key block, the key of its first entry, the SHA-256 of its uncompressed bytes, and its number of entries.
  • records, removals, and withheld count entries of each kind; lines counts lines. first and last are the keys of the first and last entries, null in an empty file. commits is null in an unlabeled file.
  • The locator gives each block’s compressed length in file order. Record blocks start at byte 0, key blocks follow them, and the footer follows the key blocks.
  • Determinism. The same lines and entries produce the same content, and so the same file id, whatever compressor, compression level, or write buffering is used. A writer has no choices that reach content.

Validity

A file is valid if and only if:

  • the trailer and footer parse, and the footer is the JCS of an object with exactly these members; it has at most 1,048,576 entries;
  • the footer, each key block, and each record line is UTF-8, with no byte-order mark;
  • the object’s length is what its footer accounts for: the blocks’ stored lengths, the footer, and the trailer;
  • a file with no entries has no blocks, and each count in its footer is zero;
  • each key block’s uncompressed bytes hash to the listed hash, hold the listed number of entries, and its first entry has the listed key; each key block but the last has 1,024 entries;
  • entries are in order, each is canonical JSON, with a valid type and id;
  • each entry’s line, read at (block, offset, size), is followed by \n; for "r" it hashes to hash and is the canonical form of a record with the entry’s id and type; for "x" it is exactly the removal line for the entry’s key; a "w" entry has no line;
  • lines fill each record block exactly, in entry order, shared as above, and blocks are cut as above;
  • the counts, bytes, first, last, commits, and labeled match the entries.

A reader that does not trust where a file came from MUST check what it reads: the footer against the file id, a key block against the footer, a line against its entry. It SHOULD also bound what it reads before it has checked it, since a stored length says nothing of what a block inflates to. The reference reader refuses a footer over 16 MiB stored or inflated, and a key block over 8 MiB or with more than 1,024 lines, before parsing them.

Commits

A commit is the JCS of:

{"underlay": 3,
 "collection": collection id,
 "number": n,                       1 for the first commit
 "previous": version id | null,     of commit n − 1
 "semver": "v1.0.0",
 "createdAt": ISO 8601 UTC,
 "changes": [{"collection": collection id,
              "files": [{"id", "first", "last", "entries", "records", "removals", "bytes"}, …],
              "base": version id | null,
              "message": string | null,
              "keyId": string | null, "sig": string | null}, …],
 "keyId": string | null, "sig": string | null}

version id = "ulv3:" + SHA-256(JCS(commit)), lowercase hex

A commit has two parts. A change is what an author sent: the files of one upload, the version they were working from, and a message. The rest is what the server adds when the change lands: its number, the commit before it, the semver, and the time.

  • The files a commit names MUST be unlabeled: files as their author built them, with no commit numbers inside. A server MUST refuse a change that names a labeled file. Within one commit their key ranges MUST NOT overlap. Each row in them counts as written by this commit.
  • first and last are each file’s first and last keys, and bytes its footer’s bytes. With them the commit’s rows can be cut into the same files again after a rebuild.
  • A commit with number n exists only once. A writer creates it only if no commit n exists, and only if commit n − 1 exists and has version id previous.
  • A commit, each change, and each file entry has exactly the members shown. A writer MUST NOT write a commit a reader would refuse: nothing can be committed after a commit that cannot be read, so one would end the log.
  • A change’s collection is the commit’s. changes is a list so that one commit can later carry several authors’ uploads. A writer today makes one change per commit.

Version id

A version’s id is ulv3: followed by the SHA-256, in lowercase hex, of its commit’s bytes. Version ids and signatures rest on commits, and through them on the unlabeled files commits name, and on nothing else. None rests on a labeled file or a layout file, so how those are written can change at the cost of a rebuild.

On underlay.org, the API takes a version as its semver, its ulv3: id, or latest. A version converted from v2 also answers to its old ulv2: id.

Base

base is the version id the author was working from when they prepared the upload, or null. The author sets it; the server sets previous. The two are equal unless another commit landed in between.

  • The server records base as given. It MUST refuse a base that is not the version id of an earlier commit in this collection’s log (which, for a fork, includes the commits of the collections it was forked from).
  • Nothing else depends on it. A commit is never refused because of its base, and reading is unchanged: the newest entry wins.
  • What it gives: for any commit, the keys it wrote that other commits changed after its base and up to its previous can be listed from key entries alone. Those are the changes the author had not seen.

Signatures

Both signatures are Ed25519 over the JCS of the signed object without its sig member, base64url without padding. keyId is the first 16 hex characters of the SHA-256 of the raw public key. keyId and sig are both null, or neither is.

  • The author signs the change: its collection, files, base, message, and keyId. The signature does not cover the commit’s number or previous.
  • The server signs the commit: each member but its own sig, the changes and their signatures included.
  • A change that loses the race for a number is committed at the next free number with the author’s signature unchanged. Only the server’s part is made again.
  • Which keys a reader trusts, for either signature, is not part of this protocol.

On underlay.org changes are unsigned. The server keeps no authors’ keys: it signs each commit with its own key and records who pushed in its catalog, outside the commit. It does not move a change to the next free number: a push whose head moved before it landed is refused, and the client pushes again.

Naming a file

A server MUST NOT accept a change that names a file unless the file’s bytes came with that upload and check out against the file id. That a file with the id is already stored is never enough: otherwise knowing an id would be a way to test whether a file exists, and then to read it through a collection of one’s own. The one exception is the server’s own copy of commits from a collection the caller may read, which is how a fork begins.

The same holds for an asset (see Assets). The bytes a server checks MUST be the bytes it installs: an uploader who can still write where its upload was sent must not be able to change a file between the check and the install.

Semver

The semver follows from what the commit changes relative to the version before it:

  1. The first commit is v1.0.0.
  2. If it adds, removes, or changes a $schema row: major, v(M+1).0.0.
  3. Otherwise, if it adds, removes, or changes a row of any non-reserved type: minor, vM.(m+1).0.
  4. Otherwise (metadata or assets only): patch, vM.m.(p+1).

A $schema row equal to the row it would replace (same key, same hash; or a removal of an absent key) is not a change, so a committer always compares schema rows with the version before. For other rows a committer MAY make the same comparison, and otherwise counts each row as a change. A commit that changes nothing SHOULD NOT be made. The reference server compares each row with the version before, leaves out rows that change nothing, and makes no commit if none is left.

Reading a version

To read version v of a collection:

  1. Let L be the current layout, or none. The files are L’s files plus the files named by commits L.through + 1 to v (all commits 1 to v if there is no layout).
  2. For a key, among the entries of those files whose commit is at most v, the entry with the highest commit wins. If it is a removal, or there is none, the version has no record with that key. If it is withheld, the version has a record with that key and hash whose line the server no longer holds. Otherwise the record is the entry’s line.

If v is at or below L.through and L does not retain it, the read fails. underlay.org retains all versions.

The changes between versions a and b (a < b) are the keys with an entry whose commit is above a and at most b. A file whose commits range lies outside that is not read.