# dig-dht — Normative Specification
This document is the authoritative statement of what the `dig-dht` crate implements: a Kademlia
DHT with **provider records** for the DIG Node peer network. It specifies the wire protocol, the
keyspace and key derivation, the record and routing-table semantics, the lookup algorithm, the
public API surface, configuration defaults, error behavior, and security properties.
The key words **MUST**, **MUST NOT**, **SHOULD**, **SHOULD NOT**, and **MAY** are to be interpreted
as described in RFC 2119. Statements marked as *wire contracts* are fixed at the field/byte level;
a conforming reimplementation must reproduce them exactly.
The ecosystem-level normative anchor for this protocol is the DIG Protocol **Peer network** page
(docs.dig.net → Protocol → Peer network, §4c "Content discovery — the DHT" and the "DHT RPC — a
distinct framed wire" subsection). Where this document and that page describe the same contract,
they agree; this document additionally pins the crate-level API semantics.
---
## 1. Scope and role
`dig-dht` answers exactly one question for a DIG Node: **"which peers hold this content?"**
- A node that holds content (a store / capsule / root / resource) **announces** a provider record
keyed by a content identifier (§4).
- A node that wants content runs an iterative **find-providers lookup** (§8) and receives the set
of holder `peer_id`s with candidate addresses.
- The DHT **locates** peers only. Byte transfer is out of scope: the finder connects to providers
over `dig-nat` (mTLS, `peer_id = SHA-256(TLS SubjectPublicKeyInfo DER)`) and fetches via the L7
peer RPC (`dig.getAvailability` → `dig.fetchRange`), which are specified on the Peer network page.
Every node is simultaneously a DHT **client** (it runs lookups) and a DHT **server** (it holds a
slice of the routing table and of the global provider records and answers inbound RPCs, §10).
## 2. Identity and keyspace
### 2.1 Keys
- The keyspace is **256-bit**. A `Key` is 32 bytes, interpreted big-endian.
- A **node's key IS its `peer_id`, verbatim**. `peer_id = SHA-256(TLS SubjectPublicKeyInfo DER)`
(the `dig_nat::PeerId`) is already a uniform 256-bit value; the DHT node id and the peer id are
one and the same. Implementations MUST NOT re-hash the peer id.
- A **content key** is derived from a `ContentId` per §4.2.
- The canonical text rendering of a key (and of a `peer_id`) is **lowercase 64-character hex**.
Producers MUST emit lowercase hex on the wire (see §5.6 for why this is load-bearing for
`content_key`).
### 2.2 Distance metric
- The distance between two keys is their bytewise **XOR**, compared as a **big-endian unsigned
integer** (smaller = closer). Distance is symmetric; distance-to-self is zero.
- The **bucket index** of a nonzero distance is `255 − leading_zero_bits(distance)` — the position
of the most-significant set bit, equivalently indexing by shared-prefix length with the local
node. The zero distance has no bucket index (a node never buckets itself).
*Wire contract:* every implementation MUST derive the identical key, distance, and bucket index for
the same inputs, or provider records announced by one implementation are not found by another.
## 3. Content granularities
A `ContentId` matches the availability granularities of the L7 peer network:
| `Store` | `store_id` (32 bytes) | "does a peer serve this store at all?" |
| `Root` | `store_id` + `root` (32 bytes each) | "does a peer have this generation `(store_id, root)`?" — the immutable **capsule** `store_id:root` |
| `Resource` | `store_id` + `root` + `retrieval_key` (32 bytes each) | "does a peer have this resource within the capsule?" |
`ContentId::capsule(store_id, root)` is an exact alias of `ContentId::root(store_id, root)`: a
capsule IS a root generation; the two construct the same variant and derive the same key.
## 4. Content-key derivation (frozen wire contract)
### 4.1 Domain-separation tags
| `0x01` | Store | `0x01 ‖ store_id` (33 bytes) |
| `0x02` | Root / capsule | `0x02 ‖ store_id ‖ root` (65 bytes) |
| `0x03` | Resource | `0x03 ‖ store_id ‖ root ‖ retrieval_key` (97 bytes) |
These tag values are **frozen**: they MUST NOT be renumbered or repurposed. New granularities MAY
be added only with new, previously unused tag bytes.
### 4.2 Derivation
```
content_key = SHA-256( tag ‖ fixed-order raw 32-byte fields )
```
- The encoding is canonical: fixed field order, raw (un-hexed) 32-byte hashes, one leading tag
byte. Every implementation MUST derive the identical key for the same content.
- Domain separation guarantees that a store key, a root key, and a resource key are **distinct
points** even when they share the same `store_id` (and that no field-shifting collision between
granularities is possible), so their provider records never collide in the DHT.
## 5. Wire protocol
### 5.1 Transport binding
The DHT RPC rides an authenticated `dig-nat` peer connection (mTLS, multiplexed logical streams):
each RPC opens a logical stream, writes one framed request, and reads one framed response. The
caller's identity is established by the mTLS handshake, **never** by any field in the request body
(§10.2, §14).
### 5.2 Framing (wire contract)
Every DHT message — request and response — is framed as:
```
u32 big-endian body length ‖ JSON body
```
- This framing is byte-identical to the `dig-nat` control-message framing, so a node speaks one
framing across the peer network.
- The body length MUST NOT exceed **`MAX_FRAMED_BODY` = 262 144 bytes (256 KiB)**. A receiver MUST
reject a frame whose declared length exceeds this bound *before* allocating, with an
invalid-data error. A truncated frame (fewer body bytes than declared) MUST error, not hang or
yield a partial message.
- The JSON body is a `type`-tagged object (snake_case tags). Decoders MUST ignore unknown fields
(forward compatibility: new fields are additive); an unknown `type` tag fails the decode.
### 5.3 The four RPC methods (wire contract)
| `find_node` | `{ "type":"find_node", "target":"<64hex>" }` | `{ "type":"nodes", "nodes":[Contact] }` |
| `find_providers` | `{ "type":"find_providers", "content_key":"<64hex>" }` | `{ "type":"providers", "providers":[ProviderRecord], "closer":[Contact] }` |
| `add_provider` | `{ "type":"add_provider", "record":ProviderRecord }` | `{ "type":"add_provider_ok" }` |
| `ping` | `{ "type":"ping", "nonce":<u64> }` | `{ "type":"pong", "nonce":<u64> }` |
Semantics:
- **`find_node`** — the responder returns up to `k` contacts it knows closest (XOR) to `target`,
closest-first, from its routing table.
- **`find_providers`** — the responder returns every **live** (non-expired, §6.2) provider record
it holds for `content_key`, **plus, always,** the up-to-`k` closer contacts it knows
(`closer`) — even when providers were found, because more providers may live nearer the key.
This unconditional `closer` is what lets an iterative lookup keep converging.
- **`add_provider`** — the responder stores the record in its local provider store (§6.3) and
additionally folds the record's provider (peer id + addresses) into its routing table as a
contact. It replies `add_provider_ok` on acceptance.
- **`ping`** — the responder echoes the request's `nonce` in `pong`. A caller MUST treat a pong
with a non-matching nonce as a failure.
### 5.4 Error envelope
A responder that cannot answer returns:
```json
{ "type":"error", "code":<uint>, "message":<string> }
```
- The error envelope is **advisory**: a lookup treats a peer that returns it exactly like an
unreachable peer and walks on. It is never fatal to a lookup.
- Defined codes:
- **`2` — invalid key** (the `target` / `content_key` was not valid 64-char hex).
- **`3` — provider store over capacity** (an `add_provider` was rejected by the provider-store
admission control, §6.3; the record was NOT stored).
- **`4` — provider identity mismatch** (an `add_provider` named a `provider_peer_id` other than
the authenticated caller, §6.4; the record was NOT stored).
Other codes MAY be used by responders; callers MUST NOT rely on codes other than those defined
here.
### 5.5 Wire shapes (wire contract)
```
Contact = { "peer_id":"<64hex>", "addresses":[CandidateAddr] }
"addresses":[CandidateAddr], "expires_at":<u64 unix-seconds> }
```
- The `CandidateAddr` shape and the lowercase `kind` tokens are **byte-compatible with the L7
`dig.getPeers` `addresses[]` shape** (Peer network §7), so a returned `Contact` or
`ProviderRecord` drops straight into a dial target for the NAT-traversal ladder.
- `kind` rank, most-direct-first: `direct` (0) < `mapped` (1) < `reflexive` (2) < `relay` (3).
- `host` is an IPv4/IPv6 literal or hostname; `port` is the peer's P2P port.
- **Address ordering is IPv6-first, then by `kind` rank** (ecosystem-wide IPv6-first, IPv4-fallback
rule for peer communication): [`ProviderRecord::new`] and [`Contact::new`] sort their `addresses`
so every IPv6-literal candidate sorts before every IPv4-literal or hostname candidate, and within
each family candidates are ordered most-direct-first by `kind` rank. **The address-family half of
the sort key comes from the canonical `dig-ip` crate (`dig_ip::Family::of`) — the ecosystem's
single source of truth for the IPv6-first / IPv4-fallback family contract (CLAUDE.md §5.2)** — not
a hand-rolled `is_ipv6` check, so dig-dht cannot drift off the canonical rule; the dht-specific
most-direct-first `kind` rank remains dig-dht's own tiebreak within a family. `dig_ip::Family`
classifies `host` from a real `IpAddr` parse (not a `contains(':')` heuristic), and in particular
classifies an IPv4-mapped IPv6 literal (`::ffff:a.b.c.d`) as **IPv4** — it is IPv4 reachability, so
it sorts with the IPv4 family. The family half has **three** tiers: IPv6 literal (0) < IPv4
literal (1) < a `host` that is not an IP literal at all (2). A DHT candidate is an *observed*
socket address, so a non-literal is a malformed or hostname-bearing record whose reachability this
specification does not classify and an implementation does not resolve on the dial path; it MUST
NOT outrank a usable IPv4 literal. Address order on the wire is therefore IPv6-first-then-rank as
produced by a conforming implementation; a consumer that receives a record from a
non-conforming/older peer MUST NOT assume the ordering and SHOULD still pick by family-then-rank
itself. A bare `relay` marker (`host:""`, `port:0`) is not directly dialable and sorts in the
non-literal tier (its empty `host` does not parse as an IP), last by `kind` rank. This ordering is additive: it does not
change the `CandidateAddr` field names, types, or JSON encoding — only the list order.
- **Address-list cap is a receive-side limit, NOT a wire encoding change.** `addresses[]` carries
no length prefix or bound of its own on the wire beyond the overall `MAX_FRAMED_BODY` frame
(§5.2); an implementation MUST NOT reject or mis-decode a message because it carries more than
`MAX_ADDRESSES_PER_RECORD` (**8**) addresses — the JSON shape and field shapes are unaffected and
a conforming decoder MUST successfully parse a longer list. Instead, every point that admits an
address list into local state (or hands one back to a caller) MUST sort it IPv6-first-then-rank
(above) and then **truncate to `MAX_ADDRESSES_PER_RECORD`**, so the most-preferred candidates are
the ones retained: [`ProviderRecord::new`], [`Contact::new`], the responder's `add_provider`
handling (both the record's own `addresses` and the authenticated caller's `Contact`, §10.2),
contacts absorbed from a lookup's `closer`/`nodes` results, and provider records returned to a
`find_providers` caller. This bounds per-record memory and the amplification of re-serving a
received list to other peers without changing what a conforming peer may transmit or how a
receiver decodes it.
- **The cap MUST hold by construction at the decode boundary.** Deserializing a `ProviderRecord` or
a `Contact` MUST itself sort-then-truncate `addresses` to `MAX_ADDRESSES_PER_RECORD`, so no
deserialized value — from a peer's frame, a config file, or a cached snapshot — can carry an
unbounded list even if some future ingest path forgets to cap it. Enforcement at decode
**bounds, never rejects**: an over-long list MUST still parse successfully (a decode error would
make a non-conforming or older producer's record unreadable and would hand a peer a way to poison
a whole frame). Because the sort precedes the truncation, the most-preferred candidates survive
regardless of the order the sender listed them in.
- **Dial order (the candidate iterator).** An implementation MUST expose, for both a
`ProviderRecord` and a `Contact`, the peer's **dialable** candidates in dial order — the
family-then-`kind` ranking above (IPv6, then IPv4, then non-literal), deduplicated by ENDPOINT and
capped at `MAX_DIAL_CANDIDATES` (**4**).
- **Deduplication is by parsed endpoint, not by host text.** Two candidates naming the same
address in different spellings (`2001:db8::1`, `2001:0db8::1`, `2001:db8:0:0:0:0:0:1`,
`2001:DB8::1`) are ONE dial target, and an IPv4-mapped IPv6 literal reduces to its IPv4 form, so
`::ffff:a.b.c.d` and `a.b.c.d` are the same endpoint (consistent with both ranking as IPv4
reachability). A non-literal host deduplicates on its text. Distinct ports are always distinct
targets. Text-based dedup would let one address, spelled `MAX_DIAL_CANDIDATES` ways, consume the
entire dial set.
- **The cap MUST NOT eliminate the fallback tier.** Truncating the family-sorted list outright lets
the preferred tier fill the cap alone: a holder advertising `MAX_DIAL_CANDIDATES` or more IPv6
candidates would yield a dial set with NO IPv4, so a dialer that walked every candidate it was
given would still never reach a working IPv4 address. When the cap would exclude every non-IPv6
candidate and at least one exists, the least-preferred kept slot MUST be given to the best
non-IPv6 candidate. IPv6 still leads the resulting list; the reservation costs one surplus IPv6
attempt, never the ordering. A dialer MUST walk that list, falling
through on each failure, and MUST NOT conclude a holder is unreachable until every candidate has
been tried: IPv4 is the **fallback** (CLAUDE.md §5.2), so a failed IPv6 attempt must never mask a
working IPv4 candidate. A single-address accessor (`best_address`) is a display/logging
convenience and MUST NOT be the basis of a dial decision. Relay markers are excluded (those peers
are reached via the relay / a brokered punch); non-literal candidates are retained last so a
dialer can report a concrete per-candidate reason rather than reporting no address at all.
### 5.6 Hex-case requirement
The `target`, `content_key`, `peer_id`, and `provider_peer_id` fields MUST be **lowercase** 64-hex.
Responders parse-and-renormalize lookup keys, but a stored record's `content_key` string is the
lookup index in the provider store; a non-lowercase `content_key` in `add_provider` would be stored
under a string that lowercase-normalized lookups never match, making the record unfindable.
## 6. Provider records
### 6.1 Meaning
A provider record asserts: *peer `provider_peer_id` holds the content whose key is `content_key`,
reachable at `addresses`, until `expires_at`.* It is **soft state**, not a permanent entry.
### 6.2 TTL semantics
- `expires_at` is an **absolute Unix-seconds** timestamp. A record is expired when
`now >= expires_at` (the expiry instant itself is expired — the boundary is inclusive).
- Reads MUST never return expired records; garbage collection (§9.4) drops them.
- An announcing node sets `expires_at = now + provider_ttl` (saturating addition) and republishes
before the TTL elapses (§9.3), so a provider that goes offline ages out automatically.
- **Inbound clamp (wire contract).** A responder handling `add_provider` MUST NOT trust the
record's `expires_at` as received: before admission (§6.3) it MUST clamp it to
`min(record.expires_at, now + local provider_ttl)`. Without this clamp, a record naming
`expires_at = u64::MAX` (or any value far beyond the responder's own TTL horizon) would never
satisfy `now >= expires_at` and so would never be reclaimed by GC (§9.4) for the life of the
process. The clamp bounds every third-party record to the responder's own TTL horizon
regardless of what the announcer claims.
### 6.3 Provider store (per-node local state)
Every node keeps a local provider store, which MUST behave as:
- **Keyed by `content_key` (the 64-hex string) → one record per distinct `provider_peer_id`.**
- **Dedup-on-provider:** a second record from the same provider for the same key REPLACES the
first (refreshing `expires_at` and `addresses`); it never accumulates duplicates. A refresh
(same `content_key` + same `provider_peer_id`) MUST always succeed regardless of capacity — it
does not grow the store.
- **TTL-filtered reads:** `get` returns only records live at the supplied `now`.
- **GC:** expired records (and content keys left with no live providers) are removed; GC returns
the number of records dropped.
- **Bounded admission control (`put`).** A genuinely new `(content_key, provider_peer_id)` pair is
subject to two caps, both enforced on every `put`, not just at GC time:
- **Per-key cap** (`max_providers_per_key`, default **20** — equal to `k`): when a new provider
for a key would exceed this, one existing record for that key is evicted to make room, chosen in
**two ordered steps**:
1. **An EXPIRED record is the victim, wherever it sits** — including inside the reserved floor
below. An expired record is already invisible to `get` and merely awaits GC, so reclaiming its
slot costs nothing. **Liveness MUST outrank establishment**: a reserved-but-dead record must
never cause a LIVE provider to be evicted. This is not merely an adversarial concern — a
node's GC period is coarser than `provider_ttl`, so a key whose earliest providers have gone
offline holds expired records inside its floor for a whole GC period, and a policy that
protected them would evict a live provider on every new announcement during that window,
making content LESS discoverable the more holders announce it.
2. **Otherwise every record is live and the established floor governs:** the
`max_providers_per_key / 2` providers of that key this node admitted EARLIEST are reserved and
MUST NOT be evicted; the victim is the soonest-to-expire among the remaining (newest) slots.
Ties break on admission order in both steps, so the choice is deterministic. A store MUST record
each provider's admission order on first admission and MUST PRESERVE it across refreshes — a
republish (the mechanism by which an honest holder stays findable) must never cost that holder its
establishment. Because the reserved floor is strictly smaller than the cap, a newcomer can always
be admitted; the policy bounds WHOM a flood can displace, never whether new holders can be
learned.
- **Residual (the floor protects an incumbent, not a latecomer).** An attacker that establishes
itself BEFORE an honest holder occupies the reserved floor and retains the full pre-policy
eviction primitive against every later arrival. That race is winnable routinely rather than
exceptionally: the provider store specified here is in-memory soft state with no persistence, so
every node restart resets each key's floor to first-come; keyspace churn that makes a node newly
one of the `k` closest does the same; and a node that caches content and then reshares it is a
late arrival by construction. **Provider-set membership MUST NOT be treated as Sybil-resistant**
— the floor raises the cost of displacing an established holder, and closing the vector requires
provider records to be cryptographically bound to their announcing identity (which this
specification does not yet define).
- **Global cap** (`max_total_records`, default **100 000**): when a new `(content_key,
provider_peer_id)` pair would exceed this, the `put` is **rejected**
(`PutOutcome::RejectedOverCapacity`) rather than stored. Rejection MUST NOT evict a
*different* content key's records — a single peer flooding new keys can never evict another
key's legitimate holders.
- A rejected `put` MUST leave the store byte-for-byte as it was before the call (no stray empty
entry for a content key that was never actually populated).
- The store also tracks the set of content keys **this node itself announces** (its republish
work list). Marking is idempotent; unmarking returns whether the key was being announced.
On the serving side, `handle_request_from`'s `AddProvider` arm MUST, in order:
1. **Check self-announce identity** (§6.4) when the caller identity is known — reject a
third-party-named record before doing anything else.
2. **Clamp** `record.expires_at` to the local TTL ceiling (§6.2) — before admission control and
before storage.
3. **Admit** the (now-clamped) record via `put` (this section) and check the outcome: on
`RejectedOverCapacity` it MUST return the `error` envelope (§5.4, code `3` — provider store
over capacity) instead of `add_provider_ok`, and MUST NOT fold the (rejected, unstored)
record's provider into the routing table.
The implementation does not verify that it is among the `k` closest nodes to the record's key
before accepting an `add_provider` (§14) — that remains a known limitation distinct from capacity
admission.
### 6.4 Self-announce identity check
`ProviderRecord` carries **no signature** (§14): nothing on the wire cryptographically binds a
record to the peer it names as `provider_peer_id`. Without a check, any authenticated caller could
announce an arbitrary *third-party* `provider_peer_id` as a provider of arbitrary content at
attacker-chosen addresses — **provider-set poisoning**: a finder would receive and attempt to dial
a bogus provider, wasting `dig-nat` connection attempts (and, since finders bias toward
first-returned providers, this can also skew which legitimate providers get tried).
- When `handle_request_from` is given a caller identity (the common, authenticated-transport case,
§10.2), the responder MUST reject an `add_provider` whose `record.provider_peer_id` does not
equal the caller's `peer_id`, returning the `error` envelope (§5.4, code `4` — provider identity
mismatch) and MUST NOT store the record or fold its provider into the routing table.
- `handle_request` (no caller identity supplied, §10.2) cannot perform this check — that path
already deviates from the mTLS-authenticated model and is unaffected by this rule.
- This check is a coarse, unsigned substitute for real authenticity: it constrains announces to
**self-announces only** (a peer may announce itself, not vouch for others). It does not by
itself prevent a peer from lying about content it does not actually hold — that integrity comes
from the download layer's per-chunk merkle verification, not from the record (§14). A future
signed-record scheme (provider signs `content_key ‖ addresses ‖ expires_at`) would allow
authenticated third-party relaying; until then, third-party announces are simply rejected.
### 6.5 Authenticated ingest (real-time holdings — engine of the content-replication flywheel)
The serving-side `add_provider` (§6.4) constrains announces to **self-announces** because a
`ProviderRecord` carries no signature and mTLS attribution is all the responder has. The real-time
holdings map lifts that constraint by moving verification to the CALLER: a node's announce receiver
verifies a signed holdings announce (the caller's cryptographic proof of who provides the content),
then pushes the already-verified record into the DHT store via **`ingest_verified_provider`**.
- **`ingest_verified_provider(record) -> PutOutcome`** — store a record whose `provider_peer_id`
attribution the caller has ALREADY verified (a signature the caller checked; the DHT never sees
it). Because that verification replaces mTLS attribution, this path **bypasses the §6.4
self-announce identity check** — a node may thereby ingest a record naming a *third party* as the
holder, which `add_provider` forbids. **This is the ONLY sanctioned bypass of §6.4**, and it is
sound only because the caller established authenticity out-of-band.
- **dig-dht stays crypto-free (§15).** `ingest_verified_provider` performs NO signature check; the
caller is solely responsible for verifying the holder signature before calling. Passing an
unverified record is a caller bug that poisons the local provider set — the DHT cannot detect it.
- **Every other admission guard still applies, identically to `add_provider`:** the address list is
capped (§5.5), `expires_at` is clamped to `min(record.expires_at, now + provider_ttl)` (§6.2),
and the per-key + global admission caps (§6.3) are enforced — an over-capacity ingest returns
`RejectedOverCapacity` and stores nothing. On acceptance the holder is folded into the routing
table. `add_provider` (§6.4) and `ingest_verified_provider` share ONE admission pipeline; only the
identity check differs (present for the former, delegated to the caller for the latter).
- **No chain anchor on ingest (NC-9).** Ingest does NOT require an on-chain proof — anchoring stays
at FETCH time (the download layer's verification), because requiring a chain read per ingested
announce would itself be a DoS vector. Ingest is bounded purely by the admission caps above.
### 6.6 Authenticated retract and active own-retract
Provider records are soft state that normally age out via TTL (§6.2). Two operations remove a record
**immediately**, for the content-replication flywheel where a holder that drops content must stop
being advertised at once rather than after a TTL:
- **`remove_provider_record(content_key, provider_peer_id) -> bool`** (inbound retract) — remove
exactly the local record for `(content_key, provider_peer_id)`. Returns whether a record was
removed. The caller MUST have verified the retract was signed by that same `provider_peer_id`
(the DHT does not, §15). It MUST remove ONLY that (key, signer) record — **a retract signed by one
holder can never evict another provider of the same key** (censorship-resistance). A content key
left with no remaining providers is dropped.
- **`retract_own_provider(content) -> bool`** (active own-retract) — remove THIS node's own local
provider record for `content` AND unmark it for republish, so `find_providers` on this node stops
returning self as a holder immediately. Returns whether this node was providing the content.
Contrast **`withdraw_provider`** (§9.2), which is passive (stops republish only, leaves the local
record to expire via TTL). `retract_own_provider` is the local-state half of the flywheel's atomic
**evict + retract** step; the copies previously PUT at the `k` closest peers are NOT deleted by
this call — they age out via TTL, or sooner when the node floods the signed retract announce and
each recipient calls `remove_provider_record`.
- **`holders_of(content) -> Result<Vec<PeerId>, DhtError>`** — a thin, address-free projection over `find_providers`
(§9.2) for callers that only need "which peers hold X". `find_providers` (which returns full
records with candidate addresses the download layer dials) remains the PRIMARY query.
### 6.7 Answer-to-question binding (finder side)
A responder's `providers` answer is untrusted input: a `ProviderRecord` carries no signature and the
responding peer is not the record's subject, so a peer on a lookup path may return records naming
any `provider_peer_id` at any `addresses`, for any `content_key`.
A finder MUST therefore **discard every returned record whose `content_key` is not the key it
queried**, and MUST do so before the record can influence the lookup — specifically before the
`stop_on_providers` early-exit decision (§8) and before any record is returned to the finder's
caller. Off-key records that reach a caller become dial targets, giving any peer on the path a free
way to fan out a finder's dial attempts (wasted-dial DoS and lookup amplification); off-key records
counted as "found" would additionally end the walk before it reached a real holder, which turns the
same free lie into content-discovery censorship.
This is an equality check on the full 64-hex `content_key`, not a prefix or distance test: a
near-miss key is not the queried key. Records the finder holds LOCALLY are indexed by key and are
therefore already bound to it.
## 7. Routing table
### 7.1 Structure
- **256 k-buckets**, each holding up to `k` contacts. A contact with key `K` lives in the bucket
whose index is `bucket_index(local_key XOR K)` (§2.2) — i.e. bucketed by shared-prefix length
with the local node.
- A node MUST NOT store its own id in the table. A contact with a malformed (non-64-hex)
`peer_id` is silently ignored.
### 7.2 Least-recently-seen (LRS) policy
Buckets are ordered least-recently-seen at the front, most-recently-seen at the back:
- **Offer, already present** → the contact moves to the back (recency refreshed, addresses
updated). The table never double-counts a peer.
- **Offer, room available** → the contact is appended at the back.
- **Offer, bucket full** → the newcomer is NOT inserted; the operation reports the current LRS
(front) contact. The caller SHOULD then **ping-and-replace**: ping the LRS contact and, only if
it fails to respond, evict it in favour of the newcomer. Long-lived nodes are kept — this is the
standard Kademlia eviction-attack resistance.
- **Replace** is guarded: it succeeds only if the named LRS contact is *still* at the front of the
bucket. If the slot changed in the meantime (e.g. the LRS answered a ping and was refreshed),
the replace is a no-op and the newcomer is dropped.
### 7.3 Closest query
`closest(target)` returns the `k` contacts nearest `target` by XOR distance across all buckets,
closest-first. This is both the seed set for iterative lookups and the answer to `find_node` /
the `closer` list of `find_providers`.
## 8. Iterative lookup
One convergence engine serves node-lookup and provider-lookup. Given a `target` key, seeds, `k`,
and `α`:
1. **Seed** a shortlist with the closest contacts already known (dedup by `peer_id`; contacts with
malformed peer ids are skipped), sorted by XOR distance to the target.
2. Each round, query the **`α` closest un-queried, non-failed** shortlist entries **concurrently**
— implementations MUST issue all `α` RPCs of a round in flight at once (e.g. one task per peer)
rather than awaiting them one at a time, so a round of `α` peers that each stall to the
transport timeout costs about one `rpc_timeout`, not `α × rpc_timeout`. The reference
implementation spawns each peer's query as its own task and joins the round's results as they
arrive.
3. Fold each response in: collected provider records are deduplicated **by provider `peer_id`**
(first record per provider wins); returned `closer`/`nodes` contacts merge into the shortlist.
4. Re-sort the shortlist by distance and **cap** it at `max(3·k, k + 2·α)` entries to bound memory.
5. **Failure is non-fatal:** a peer whose RPC errors (transport failure, timeout, error envelope,
unexpected response shape) is marked failed-and-queried and never retried within the lookup;
the walk continues.
6. **Termination:** the lookup ends when there is no un-queried, non-failed entry left to ask, or
when none of the `k` closest entries is still un-queried (converged). If `stop_on_providers`
is set (used by `find_providers`), the lookup additionally ends as soon as at least one
provider record has been collected — finders want the first holders fast, not the exhaustive
`k`-closest walk.
7. **Result:** the up-to-`k` closest **non-failed** contacts (closest-first) plus all distinct
provider records collected.
**Untrusted-response bounds (wire contract).** A lookup consumes responses from untrusted peers, so
it MUST bound what any one response — or a colluding swarm — can impose:
- **Providers per response** — at most `max(64, 2·k)` provider records from a single response are
folded into the collected set (the honest per-key cap is `max_providers_per_key`); the rest are
discarded. Bounds the collected-providers map against a peer that packs an unbounded set into one
frame.
- **Closer contacts per response** — at most `max(64, 2·k)` `closer`/`nodes` contacts from a single
response are merged; the rest are discarded. Bounds per-round merge work.
- **Round guard** — a lookup runs at most `MAX_LOOKUP_ROUNDS` (64) iterative rounds. An honest
lookup converges in O(log n) rounds; the guard only trips on an adversarial swarm feeding endless
ever-closer contacts to livelock convergence, and guarantees the lookup always terminates.
**Client probe:** the client-side lookup issues `find_providers` as its per-peer probe for *all*
lookup flavours (bootstrap self-lookup, `find_node`, announce placement, and provider lookup),
because its response carries both closer contacts and any providers. A `nodes` response is also
accepted and treated as closer-contacts-only. Responders MUST therefore implement `find_providers`
even if they never store records; `find_node` remains a served wire method.
## 9. Service operations and lifecycle
`DhtService` is the per-node handle. All operations below are its public semantics.
### 9.1 Bootstrap
`bootstrap(peers)` — insert each `BootstrapPeer` (peer id + candidate addresses) into the routing
table, then run a **self-lookup** (an iterative lookup targeting the node's own key, seeded with
the bootstrap contacts) and absorb the discovered contacts. Returns the number of peers now known.
- Bootstrap peers come from the node's existing discovery (the gossip peer pool / the relay
introducer); the crate takes them as input and MUST NOT hard-depend on a live relay.
- Bootstrap is idempotent-by-merge: calling it repeatedly merges, never resets.
`bootstrap` is a one-shot, network-bound seed run against a KNOWN set of peers. It cannot cover a
freshly-formed network where no peers are connected yet at bring-up time (routing would stay empty
and discovery would be impossible). For that, the routing table is also fed LIVE as peers connect:
- **`add_peer(peer_id, addresses)`** — insert one connected peer into the routing table WITHOUT a
network round-trip. Driven by the host's live peer-membership signal (a `dig-gossip`
`PoolEvent::PeerAdded`), so routing populates as the pool fills. Idempotent-by-merge (§7.2); a
self-id is a no-op (§7.1).
- **`remove_peer(peer_id_hex)`** — evict a departed peer (a `PoolEvent::PeerRemoved`) so lookups
never seed from a dead contact. Returns whether it was present.
### 9.2 Announce / withdraw / find
- **`announce_provider(content)`** — build a provider record naming THIS node (its id + advertised
addresses, `expires_at = now + provider_ttl`), store it locally, mark the content key announced
(for republish), then run a lookup toward the content key and `add_provider` the record at each
of the converged `k` closest peers (skipping self). Returns the count of peers that accepted.
Replication is **best-effort**: a peer that errors is skipped. With no peers to ask, the local
record stands and the return value is 0 — republish re-attempts once bootstrapped.
- **`withdraw_provider(content)`** — stop republishing the key. The record is NOT actively deleted
from other nodes; it ages out via TTL. Returns whether the key was being announced.
- **`find_providers(content)`** — merge (a) locally held live records for the key and (b) the
records collected by an iterative lookup toward the key (`stop_on_providers = true`), dedup by
provider `peer_id`, drop expired records, and return the result. Records a queried peer returns
for a DIFFERENT `content_key` are discarded at the wire boundary before they can affect the walk
(§6.7). An empty result is **not** an
error — it means no known providers. `DhtError::NoPeers` is returned only when a lookup has no
one to seed from *and* is expected to run (`find_node`); `find_providers` with an empty routing
table returns whatever is held locally (possibly empty).
- **`find_node(peer_id)`** — iterative lookup toward the peer's key; returns the converged closest
contacts. Errors with `NoPeers` when the routing table is empty.
- **`holders_of(content)`** — the peer ids of the holders `find_providers` finds; an address-free
projection over `find_providers` (§6.6). Same distributed lookup, same errors.
**Real-time holdings operations** (§6.5, §6.6) — `ingest_verified_provider(record)` (authenticated
third-party inbound add), `remove_provider_record(content_key, provider_peer_id)` (authenticated
inbound retract), and `retract_own_provider(content)` (active own-retract) — mutate the local
provider store directly for the content-replication flywheel and are specified in §6.5/§6.6.
All lookups **absorb** the converged contacts back into the routing table. A full bucket's
LRS-report is left to ping-and-replace maintenance — lookups never block on a liveness ping.
### 9.3 Maintenance loop
The embedding node MUST drive maintenance on the configured intervals:
- **`republish()`** (every `republish_interval`) — for every announced content key: refresh the
local record (new `expires_at = now + provider_ttl`) and re-run the announce PUT at the current
`k` closest peers. This keeps records alive while the node is online and heals placement as the
network churns. `republish_interval` MUST be shorter than `provider_ttl`.
- **`refresh_buckets()`** (every `refresh_interval`) — for every **non-empty** bucket, look up a
random key whose distance from the local node falls in that bucket (the bit at position
`255 − bucket_index` set, lower bits randomized), absorbing what the lookup finds.
- **`gc()`** (periodically; MAY piggy-back on the above) — drop expired provider records.
- **`ping(contact)`** — send a `ping` with a fresh random `u64` nonce; alive iff a `pong` echoing
the same nonce arrives. On any failure (including a nonce mismatch) the peer is **evicted** from
the routing table and `false` is returned. This is the ping half of ping-and-replace (§7.2).
### 9.4 Provider-record lifecycle (summary)
```
announce_provider ──► local store + announced-set + PUT at k closest
│ │
│ every republish_interval │ TTL (provider_ttl) runs down
▼ ▼
republish() re-PUTs (new expiry) expired ⇒ hidden from reads, dropped by gc()
│
▼
withdraw_provider ⇒ stop republishing ⇒ record ages out network-wide via TTL
```
## 10. Serving side
### 10.1 Request handling
`handle_request_from(caller, request)` answers one inbound RPC. It reads/writes only local state
(routing table + provider store) and MUST NOT make outbound RPCs — the server half can never
recurse or block on the network. Behavior per method is §5.3; an unparsable 64-hex key yields the
`error` envelope with code `2`.
### 10.2 Learning the caller (wire contract)
On **every** inbound RPC the responder folds the caller's `Contact` into its routing table (unless
the caller is itself) — every request is evidence the caller is alive, and this is how Kademlia
tables fill bidirectionally without explicit announces. The caller identity MUST come from the
**authenticated transport** (the mTLS-verified `peer_id`), never from a field in the request body —
identity is not self-asserted. `handle_request(request)` (no caller) exists for transports that
cannot supply one; `handle_request_from` SHOULD be preferred.
## 11. Transport abstraction
The crate is written against one trait:
```rust
#[async_trait]
pub trait DhtTransport: Send + Sync {
async fn rpc(&self, from: &Contact, peer: &Contact, request: &DhtRequest)
-> Result<DhtResponse, DhtError>;
}
```
A conforming production implementation (wired by the embedding node, e.g. `dig-node`):
- MUST connect to `peer` over `dig-nat` (verifying the mTLS identity against `peer.peer_id`),
using `peer.addresses` as dial candidates; it MAY reuse a pooled connection.
- MUST perform the framed request/response exchange of §5.2 on one logical stream.
- MUST supply `from` (the caller's own contact) to the responder as the **authenticated** caller —
on a real dig-nat connection the remote learns the identity from the mTLS certificate, not the
wire body.
- MUST enforce the per-RPC timeout (`rpc_timeout`); the DHT core does not.
- MUST surface any failure (connect, stream, parse, timeout) as a `DhtError`; the lookup treats it
as that one peer being unreachable and continues.
## 12. Configuration and defaults
| `k` | Replication parameter: bucket size, lookup convergence set, announce fan-out | **20** |
| `alpha` | Lookup parallelism per round | **3** |
| `provider_ttl` | Provider-record validity window | **2 hours** |
| `republish_interval` | How often announced keys are re-PUT (MUST be `< provider_ttl`) | **1 hour** |
| `refresh_interval` | How often populated buckets are refreshed | **1 hour** |
| `rpc_timeout` | Per-RPC deadline (enforced by the transport, §11) | **5 seconds** |
| `provider_store_limits.max_providers_per_key` | Per-content-key provider-record cap, soonest-to-expire evicted on overflow (§6.3) | **20** |
| `provider_store_limits.max_total_records` | Global provider-record ceiling across all keys, new records rejected on overflow (§6.3) | **100 000** |
Defaults for `k` and `α` follow the canonical Kademlia paper (Maymounkov & Mazières, 2002).
## 13. Errors
`DhtError` variants and their meaning:
| `Transport(String)` | Connect/stream/timeout failure talking to one peer | That peer is unreachable; lookup continues |
| `MalformedResponse(String)` | A peer's response did not parse / match the request | As above |
| `InvalidHex(String)` | A hex identifier supplied to the API was not valid 64-hex | Operation rejected |
| `NoPeers` | Routing table + bootstrap set empty — no one to ask | Operation cannot run (see §9.2 for which ops return it) |
| `Timeout` | An RPC exceeded its deadline | That peer is unreachable; lookup continues |
Invariant: **no single peer failure is ever fatal to a lookup.**
## 14. Security properties
- **Identity.** All trust rests on the dig-nat mTLS identity: `peer_id = SHA-256(TLS SPKI DER)`.
The DHT never derives trust from wire fields; the serving side learns callers only from the
authenticated transport (§10.2). Node ids are therefore bound to key possession — a peer cannot
claim an arbitrary id without holding the matching TLS key.
- **Allocation safety.** The framing bound (§5.2) caps any attacker-declared body at 256 KiB
before allocation; truncated frames error deterministically.
- **Eviction resistance.** The LRS bucket policy (§7.2) keeps long-lived contacts unless proven
dead, resisting table-flush attacks by newly minted ids.
- **Soft state.** Provider records self-expire (§6.2); a withdrawn or dead provider disappears
within one `provider_ttl` without any delete protocol.
- **Bounded provider store.** `add_provider` is admission-controlled (§6.3): a per-key cap and a
global cap (rejection) bound the memory a single peer's `add_provider` traffic can consume,
independent of any rate limiting the embedding node may add.
- **Sybil-resistant provider eviction.** Because an inbound record's expiry is clamped to the
responder's own TTL horizon, a provider that announces LATER necessarily carries a later
`expires_at`; a plain soonest-to-expire eviction would therefore make an honest incumbent the
deterministic victim of any later announcer, letting `max_providers_per_key` freely-minted Sybil
identities evict the ONLY real holder of a capsule and leave that content undiscoverable through
the node (and, repeated across the k-closest, network-wide). The established-floor policy (§6.3)
reserves each key's earliest-admitted half from eviction, so a flood can churn the newest slots
but cannot displace an ALREADY-ESTABLISHED holder however many identities it spends or however it
times its expiries. This mirrors the LRS bucket policy applied to contacts (§7.2). Eviction also
prefers reclaiming an EXPIRED record over any live one (§6.3), so the reservation can never cost a
live provider its slot.
- **Scope of that property — read this before relying on it.** It protects an INCUMBENT, not a
latecomer. An attacker that establishes first retains the full pre-policy primitive against all
later arrivals, and because the store is in-memory soft state the race resets on every node
restart (and on any keyspace churn that makes a node newly k-closest), while a cache-and-reshare
holder is a late arrival by construction. Membership of a provider set is therefore NOT
Sybil-resistant, and a consumer MUST NOT treat it as an authenticated holder list. Full closure
requires signed provider records (§14 "Known limitations" — records are not signed).
- **TTL clamp.** An inbound `expires_at` is never trusted as received: it is clamped to the
responder's own TTL horizon (§6.2) before storage, so a malicious record can never outlive local
GC indefinitely — combined with the bounded store above, this makes the worst case from a
misbehaving peer bounded and self-healing, not permanent.
- **Address-list cap.** Every `addresses[]` admitted into local state (a stored `ProviderRecord`,
a routing-table `Contact`, or a `find_providers` result handed back to a caller) is capped at
`MAX_ADDRESSES_PER_RECORD` (§5.5) — a single record/contact can never carry an unbounded address
list, which would otherwise inflate per-record memory and, once stored, be re-served (cloned) to
every peer that later queries for it (bandwidth amplification). The cap is additionally enforced
at the decode boundary itself (§5.5), so the bound holds by construction for every deserialized
value rather than only at the ingest sites that remember to apply it.
- **Answer-to-question binding.** A finder discards provider records returned for a key it did not
query (§6.7), before the early-exit decision and before returning anything to its caller — so a
peer on the lookup path cannot fan out the finder's dial attempts or halt its walk with records it
was never asked for.
- **Self-announce identity check.** When the caller identity is known, `add_provider` is rejected
(error code `4`) unless `record.provider_peer_id == caller.peer_id` (§6.4) — an authenticated
caller may announce only itself, never vouch for a third party.
- **Known limitations (as implemented).** Provider records are **not signed**: the self-announce
check (§6.4) constrains WHO may be named as provider but does not cryptographically bind the
record to that identity, and the check cannot run at all on the `handle_request` (no-caller)
path. A finder gets content integrity from the content itself (per-chunk merkle verification in
the download layer), not from the record. Responders also do not verify their own closeness to
the key before accepting `add_provider`. Rate limiting per-caller (as opposed to the crate's own
per-key/global capacity caps) is not implemented in this crate and, where needed, is the
embedding node's responsibility.
## 15. Public API surface
Exported from the crate root (`#![forbid(unsafe_code)]`, MSRV **1.75.0**, license
**Apache-2.0 OR MIT**):
- `DhtService` — `new(local_id, local_addresses, config, transport)`, `local_id()`,
`bootstrap(&[BootstrapPeer])`, `find_node(&PeerId)`, `find_providers(&ContentId)`,
`announce_provider(&ContentId)`, `withdraw_provider(&ContentId)`, `republish()`,
`refresh_buckets()`, `gc()`, `ping(&Contact)`, `handle_request(DhtRequest)`,
`handle_request_from(Option<Contact>, DhtRequest)`, `known_closest(&Key)`, `routing_len()`,
`ingest_verified_provider(ProviderRecord)`, `remove_provider_record(String, PeerId)`,
`retract_own_provider(&ContentId)`, `holders_of(&ContentId)`.
- `DhtConfig` (§12), `ContentId` (§3–4), `Key` / `Distance` (§2), `ProviderRecord` /
`CandidateAddr` / `AddressKind` / `MAX_ADDRESSES_PER_RECORD` / `dial_candidates` /
`MAX_DIAL_CANDIDATES` (§5.5, §6) — `ProviderRecord::dial_candidates()` and
`Contact::dial_candidates()` are the §5.2-compliant dial-order accessors, and `best_address()` on
either type returns the first candidate only (display/logging, never a dial decision), `Contact` /
`RoutingTable` (§7), `BootstrapPeer` (§9.1), `DhtTransport` (§11), `DhtRequest` / `DhtResponse` +
`MAX_FRAMED_BODY` (§5), `DhtError` (§13), and the re-exported `dig_nat::PeerId` (one
peer-identity type across the transport and the DHT).
- `lookup::iterative_find` (§8) and `provider_store::ProviderStore` /
`provider_store::ProviderStoreLimits` / `provider_store::PutOutcome` (§6.3) are public modules
usable directly. `ProviderStore::put_at(record, now)` is the admission entry point that takes the
caller's clock — `put(record)` delegates to it with the system clock — so admission, expiry, and
eviction can all be evaluated against ONE instant (§6.3 step 1 requires a liveness test, which
needs a `now`).
Dependency posture: the crate depends on `dig-nat` for identity/transport types only — not on the
gossip or Chia stacks — so the dependency tree stays minimal.
## 16. Quality gates
CI (push/PR to `main`) enforces: `cargo fmt --check`, `cargo clippy --all-targets -- -D warnings`,
`cargo test --all`, a release build, `cargo doc --no-deps`, and **line coverage ≥ 80%**
(`cargo llvm-cov --fail-under-lines 80`). Releases are tag-driven (`vX.Y.Z`): the publish workflow
re-runs the gates, publishes to crates.io, and cuts a GitHub Release. The full stack — buckets,
lookup, provider store, wire framing, and service RPCs — is exercised end-to-end over an in-memory
multi-node swarm harness (no real network), including round-tripping every RPC through the §5.2
framing.
## 17. Conformance summary
| Content-key derivation | `SHA-256(tag ‖ raw fields)`, tags `0x01` store / `0x02` root(capsule) / `0x03` resource (§4) | Byte-identical across implementations, or records are unfindable |
| Node key | `peer_id` verbatim (SHA-256 of TLS SPKI DER) (§2.1) | Nodes and content share one keyspace |
| Distance / bucketing | XOR, big-endian compare; bucket = `255 − leading_zeros` (§2.2) | Same closeness ordering everywhere |
| Framing | `u32`-BE length ‖ JSON, body ≤ 256 KiB, same as dig-nat control framing (§5.2) | One framing across the peer network |
| RPC methods | `find_node` / `find_providers` / `add_provider` / `ping` + `error` envelope, snake_case `type` tags (§5.3–5.4) | Any node's DHT speaks the same wire |
| `find_providers` response | ALWAYS carries `closer` (§5.3) | Iterative lookups converge |
| Address shape | `{host, port, kind}` with lowercase `kind` tokens, byte-compatible with L7 `dig.getPeers` (§5.5) | Results drop into dial targets |
| Address ordering | IPv6-first (family key from canonical `dig_ip::Family`), then by `kind` rank (§5.5) | Dialers try IPv6 before IPv4, per the ecosystem IPv6-first/IPv4-fallback rule (CLAUDE.md §5.2) |
| Address-list cap | `MAX_ADDRESSES_PER_RECORD` = 8, receive-side truncation post-sort, not a wire/decode limit (§5.5) | No record/contact can carry an unbounded address list; wire encoding is unaffected |
| Hex case | Lowercase 64-hex identifiers on the wire (§5.6) | Records remain findable |
| Provider TTL | Absolute `expires_at` Unix seconds; expired at `now >= expires_at`; republish < TTL (§6.2, §12) | Stale providers age out uniformly |
| Inbound TTL clamp | `add_provider`'s `expires_at` clamped to `min(received, now + local provider_ttl)` before storage (§6.2, §10.1) | A malicious/over-long expiry can never outlive local GC |
| Caller identity | mTLS-authenticated, never wire-asserted (§10.2) | Routing tables cannot be poisoned by claimed ids |
| Provider-store capacity | Per-key cap (soonest-to-expire eviction) + global cap (rejection), error code `3` on reject (§5.4, §6.3) | One peer's `add_provider` flood cannot exhaust responder memory |
| Self-announce identity | `add_provider` rejected (error code `4`) unless `provider_peer_id == caller.peer_id`, when caller is known (§5.4, §6.4) | A caller cannot announce a third party as a content provider |
Cross-repo: the wire and keyspace contracts above must match the DIG Protocol **Peer network** page
(docs.dig.net → Protocol → Peer network, §4c and its conformance table) exactly; `dig-nat` provides
the transport + `PeerId`, `dig-download` consumes `find_providers` results, and `dig-node` embeds
the service and wires both transport halves.