open-standards/wai/extensions/holdings.md

# WAI Extension: Holdings

> Status: Draft. Registers the record `wai.delivery.holdings`: a node's signed statement of which
> objects of which groups it holds now, for its neighbours. A receiver that stores what a
> broadcast carried, a neighbourhood cache or a peer can serve those objects over a short link,
> and a neighbour that knows who holds what fetches from them before it spends the backhaul. A
> holdings record (`WHD1`, §4) lists, for each group a node holds objects of, the group's link
> hash, its object count and either `whole` or a bitmap of the objects held: exact, so a
> neighbour never goes to a node for an object it does not hold, and compact where objects are
> held as groups are delivered. A verifier checks a record's form, signature and freshness and
> holds it to the group receipts it has (§5), answers whether a holder holds an object, and
> derives which wanted objects each neighbour can serve and which must come from the origin
> (§5.4). An object a neighbour serves is verified as every object is (jwp-receipts §3); a
> record is never evidence of an object's bytes. WAI defines no transport. The reference
> implementation is the `holdings` module of `wai-rs` (feature `holdings`); the corpus is
> [`live-conformance/holdings/`](../live-conformance/holdings/), and its second implementation is
> `live-conformance/holdings_verify.py`.
> Keywords **MUST**, **MUST NOT**, **SHOULD**, **MAY** are RFC 2119/8174.

## 1. Scope

In scope: the holdings record, its form, digest and signature (§4); what a verifier derives from
records and the group receipts it has, at an instant (§5); and how a fetch from a neighbour is
verified (§6).

Out of scope: how records travel (a neighbourhood's own announcements, a file beside a bearer's
carousel, a request); how a node chooses what to keep; how a neighbour is reached or what a link
costs, which the asker orders its neighbours by itself; and objects not delivered under a group
receipt, which have no holdings here.

Relationship to the core spec: `wai.delivery.holdings` is a **record** ([SPEC](../SPEC.md) §5).
It names no payload format and is not dispatchable.

## 2. Terms

- **Group**, **link hash**, **leaf count**: as [jwp-receipts](jwp-receipts.md) §2.4.1 and §3
  step 3. Object *i* of a group is its object at position *i*, from 0.
- **Holder**: the node a record speaks for, named by its Ed25519 key. **Asker**: a node that wants
  objects and reads its neighbours' records.
- **Instant**: a count of milliseconds since 1970-01-01T00:00:00Z, leap seconds not counted, as
  [channel-lineup](channel-lineup.md) writes one.
- **Bitmap**: object *i* is bit `0x80 >> (i mod 8)` of byte ⌊*i* / 8⌋, as a reconciliation's
  `received` is ([bearer-receipts](bearer-receipts.md) §5.1).

## 3. Why groups and bitmaps

Everything WAI delivers is delivered under a group receipt that names its objects by position, and
a node that holds objects holds them as they arrived: a whole group, or most of one, from a
broadcast's carousel or a relay. A bitmap per group is exact and costs a bit an object; a group
held whole costs 41 bytes. A probabilistic filter over content hashes costs over twenty bits an
object at a one-in-a-million false-positive rate and sends an asker, now and then, after an
object its neighbour does not hold: on a constrained link that is a wasted exchange each time.
Naming objects by group and position also lets an asker check a record against the receipts it
holds (§5.2), and fetch an object it knows the position of without knowing its bytes.

## 4. The record

### 4.1 Layout

Integers are unsigned and big-endian.

| size | field | meaning |
|---|---|---|
| 4 | `magic` | `WHD1` (ASCII) |
| 1 | `version` | 1 in this revision |
| 32 | `holder` | the holder's Ed25519 key |
| 8 | `as_of_ms` | u64: the instant the record states the holdings at |
| 8 | `expires_ms` | u64: the instant after which it states nothing |
| 4 | `n` | u32: the entries' count |
| … | `entries` | `n` entries, §4.2, in strictly increasing order of `group`'s bytes |
| 64 | `sig` | §4.3 |

### 4.2 An entry

| size | field | meaning |
|---|---|---|
| 32 | `group` | the group receipt's link hash |
| 8 | `leaf_count` | u64: the group's leaf count |
| 1 | `form` | 0: the objects `held` names; 1: every object of the group |
| ⌈`leaf_count` / 8⌉ | `held` | form 0 only: the bitmap of the objects held |

### 4.3 Digest and signature

The **digest** of a record is SHA-256 over its bytes from `magic` through its last entry. The
**signature** is Ed25519 by `holder` over `wai:holdings` (ASCII) and 0x01, followed by the bytes
the digest covers.

### 4.4 Reading and rules

A reader reads exactly the bytes it is given as one record, in the order of §4.1, and refuses it
`holdings_malformed` when the bytes are more than 1,048,576, end before a field the layout
requires or go on after `sig`, or when:

1. its magic is not `WHD1` or its version not 1;
2. `as_of_ms` is not below `expires_ms`, or `expires_ms` is above 2^53 − 1;
3. `n` is 0, or the entries' `group` values are not in strictly increasing order of their bytes;
4. an entry's `leaf_count` is 0 or above 2^53 − 1, or its `form` is not 0 or 1;
5. a form-0 entry's `held` sets a bit at or past `leaf_count`, sets none (a node holding nothing
   of a group lists no entry for it), or sets every bit (that holding is form 1).

So each holding has exactly one record form, and two records of one holder at one instant that
state the same holdings are the same bytes. A record that reads is then refused
`holdings_signature_invalid` when its signature does not verify under `holder` as SPEC §7
*Signatures* verifies every signature: a key that is not the canonical encoding of a point of
large order fails, as does a signature whose scalar is not below the group order.

## 5. What a verifier derives

### 5.1 At an instant

A record that reads and verifies is held to the verifier's instant *t*: it is refused
`holdings_not_yet` when *t* is below `as_of_ms`, and `holdings_expired` when *t* is at or past
`expires_ms`. A verifier does not stretch either bound; one whose clock it does not trust
**SHOULD** say what instant it used.

### 5.2 Against the group receipts held

For each group receipt the verifier holds that passes jwp-receipts §3 steps 1 and 2, an entry
whose `group` is its link hash **MUST** have its `leaf_count` (`holdings_leaf_count_mismatch`).
A record with one such entry is refused whole: a holder that misstates a group misstates its
holdings. An entry for a group the verifier holds no receipt of is kept: it cannot be checked
yet, and an asker that fetches an object of it verifies that object under its receipt (§6).

### 5.3 One holder's records

Of the records of one `holder` that stand at *t*, the one with the greatest `as_of_ms` stands
alone: a node's later record states what it holds now. Two with that same `as_of_ms` and
different digests set both aside (`holdings_contradicted`), and records with the same digest are
one.

### 5.4 Who holds what

A verifier **MAY** be asked whether a record that stands holds object *i* of group *G*: **held**
when it has an entry for *G* with *i* below its `leaf_count` and, in form 0, bit *i* set; refused
`object_not_held` when its entry has *i* below its `leaf_count` and bit *i* clear;
`object_out_of_range` when *i* is at or past its `leaf_count`; and `group_not_advertised` when it
has no entry for *G*.

An asker with its neighbours' records, in the order it prefers them (by link cost, say, which it
judges itself), and a list of wanted objects, each a group's link hash and a position, derives for
each wanted object the holders whose record stands and holds it, in that order; and the wanted
objects no holder holds, which it fetches from the origin. An object held by none is not missing:
it is the backhaul's.

## 6. Fetching from a neighbour

An object a neighbour serves is an object like any other: the asker verifies it under its object
receipt and the group receipt (jwp-receipts §3), `delivered-verified` over the bytes it received,
whoever sent them. A record says where to ask, never what the answer is: an object whose bytes do
not verify is refused as jwp-receipts §3 refuses it, and a holder that advertised it and did not
serve it, or served other bytes, gave the asker one wasted exchange and nothing else.

## 7. Reasons

The codes this extension adds, each with where it is raised:

| reason | raised at |
|---|---|
| `holdings_malformed` | §4.4 |
| `holdings_signature_invalid` | §4.4 |
| `holdings_not_yet` | §5.1 |
| `holdings_expired` | §5.1 |
| `holdings_leaf_count_mismatch` | §5.2 |
| `holdings_contradicted` | §5.3 |
| `object_not_held` | §5.4 |
| `object_out_of_range` | §5.4 |
| `group_not_advertised` | §5.4 |

## 8. Conformance

[`live-conformance/holdings/`](../live-conformance/holdings/) holds the corpus, written from fixed
seeds by `wai_holdings_vectors gen` as `vectors.json`. It has:

- **Records**: whole and partial groups, a group of one object and of nine (a bitmap's last byte
  part used), several groups, each with its digest and verdict; and one negative control for each
  rule of §4.4 and for a signature that does not verify, a non-canonical key among them.
- **Verdicts**: records at an instant before, within and at the end of their window; held against
  receipts, matching, mismatching and unknown; a holder's later record standing alone, and two at
  one instant contradicting each other.
- **Queries and plans**: every answer of §5.4, and an asker's plan over three neighbours, with
  objects held by several, by one and by none.

A conforming verifier gives every case the outcome, the reason and everything else the corpus
states. `wai_holdings_vectors verify` and the test `tests/holdings.rs` check that the file
regenerates byte for byte, that `wai-rs` gives every case its outcome, that every reason of §7
appears, and that §7 lists exactly the reference's codes. `live-conformance/holdings_verify.py` is
the second implementation, written from this text: it shares no code with `wai-rs`; it verifies
group receipts with the JWP corpus's second implementation (`jwp-conformance/jwp_verify.py`),
writes §4, §5 and the plans itself, mutates copies of the corpus and requires every copy to fail,
and drops each of its own checks in turn and requires the corpus to catch the weakened verifier.

## 9. Security and privacy considerations

- **A record discloses what its holder holds**, to everyone it reaches: which groups, and which of
  their objects. A node **SHOULD** advertise only groups that reached it over a `multicast` or
  `unidirectional` bearer ([bearer-receipts](bearer-receipts.md) §2), which every receiver in
  range could hold, and **SHOULD NOT** advertise what it fetched for itself alone. A node **MAY**
  sign each record with a fresh key, which unlinks its records from each other and from its
  other statements; a neighbour then cannot tell a node's later record from another node's, and
  §5.3 does not apply across them. A node whose service is to be placed signs with the key its
  operator lists ([cache-authority](cache-authority.md) §4.5); a fresh key unlinks its records and
  leaves its service unplaced.
- **A record is its holder's word**, and costs a wasted exchange when it is false (§6). An asker
  that is sent wrong bytes refuses them and **MAY** stop asking that holder; nothing here scores
  holders.
- **Freshness**: a record past `expires_ms` states nothing. A holder **SHOULD** set an expiry no
  later than it expects to keep what it lists, since an eviction it does not announce sends
  askers after objects it no longer has.
- **Bounded work**: a record is at most 1,048,576 bytes, read once, in order; a query is a lookup
  by group and a bit test.