793ed1f2dc
The change of wai/one-way-delivery (f1258784d..987625394, 28 commits), on the fix branch: its changelog entries as files of wai/changes/, its wai-conformance.yml edits as step files, corpus files and test tags, and every other file as the branch has it. - 25240c4f0 wai: timeliness — when each object of a group is of use, and whether each holder held it in time - c84992362 wai: timeliness_verify.py — the timeliness corpus's second implementation - 44036fcdc wai: timeliness in the registry, SPEC §5, the changelog and CI; http_receipts.py checks its claims - 27ce6754c wai: claim_verify.py lists not-held-by-deadline, and the claim corpus holds a session that switches for it - 73d8d8eb9 wai: timeliness corpus — each holder's own line in key order, a holder's earliest fallback, and §7.2–§7.3's unreached plan rules - 64c735f0c wai: the files timeliness changes are clippy-clean — a let chain, and the fetch callback's type allowed - b72dc36bf wai: rung price — what delivering a rung costs, by bearer and direction, and which option a comparer takes - 4e905e213 wai: rung_price_verify.py — the rung price corpus's second implementation - 711fa6126 wai: rung price in the registry, SPEC §5, the changelog and CI - 8ab70654e wai: rung price corpus — a refusal for every form rule 1 and §6.1 set, and the neighbour order a plan gives - 1bc465959 wai: rung price ranks energy by checked evidence — a class counts only on the seller's own per-hop records, current and under a confirmed key - 9e97997d9 wai: rung_price — the evidence text bound at its exact sizes, and a key confirmed for another class confirming nothing - 8f1168683 wai: rung price corpus — a key confirmed for another class, the uncertainty product, each edge and order of the evidence verdict, and the evidence a plan read - 7330e26ff wai: rung price — §6.1 links jwp-receipts at its first mention, and §10 says a record's age is its room's word - 12c099457 wai: cache authority — who served what a node holds, and on whose authority - f8f5d3e09 wai: cache_authority_verify.py — the cache authority corpus's second implementation - 354146619 wai: cache authority in the registry, SPEC §5, the changelog and CI; its corpus holds what §12 states - 55c7f3031 wai: timeliness §6 reads holdings records alone; cache-authority §9 derives the lines that read every kind - b8fc6f02b wai: cache authority's lines read records as timeliness does, its deadline claim meets the envelopes held, and its corpus fixes each order and instant - 91c5291cf wai: the files cache authority changes are clippy-clean — a boxed envelope, the base's names named once, slices borrowed - 8e479daff wai: a held envelope boxes both its forms, so neither outweighs the other - 3ec8da807 wai: impression aggregates — ad presentations counted over a bearer with no return path - 0433a35c3 wai: impression_aggregate_verify.py — the impression aggregates corpus's second implementation - 7d8e150e4 wai: impression aggregates in the registry, SPEC §5, the changelog and CI; its corpus states each receipt whole and a control for every malformed file - d5e8ace02 wai: impression aggregates' size bounds are checked at their edge, and §4.3's decides no outcome - 4bc8e13bd wai: impression aggregates' table totals are exact, and a receipt given twice is checked when either occurrence was - 3c9f20524 wai: key_log's two result enums keep their public form, and say so to clippy - 987625394 wai: Item::with_authority and Count::instance_received build only with the feature that calls each Co-Authored-By: Claude Opus 5.5 <[email protected]>
12 KiB
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 eitherwholeor 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 theholdingsmodule ofwai-rs(featureholdings); the corpus islive-conformance/holdings/, and its second implementation islive-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 §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'sreceivedis (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:
- its magic is not
WHD1or its version not 1; as_of_msis not belowexpires_ms, orexpires_msis above 2^53 − 1;nis 0, or the entries'groupvalues are not in strictly increasing order of their bytes;- an entry's
leaf_countis 0 or above 2^53 − 1, or itsformis not 0 or 1; - a form-0 entry's
heldsets a bit at or pastleaf_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
multicastorunidirectionalbearer (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_msstates 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.