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/, 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. A record's compact form, for a return path whose messages hold few bytes, is bearer-receipts §13's; it expands to the record's own bytes.

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

2. Terms

• Group, link hash, leaf count: as jwp-receipts §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 writes one.
• Bitmap: object i is bit 0x80 >> (i mod 8) of byte ⌊i / 8⌋, as a reconciliation's received is (bearer-receipts §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/ 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 §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 §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.