add documentation

1 files changed, 358 insertions, 0 deletions

diff --git a/docs/peers.md b/docs/peers.md
new file mode 100644
index 0000000..95b4dab
--- /dev/null
+++ b/docs/peers.md
@@ -0,0 +1,358 @@
+# Peers: handshake, keepalive, dormancy and topology
+
+The timings named below (`dormant_after` and the like) derive from `--keepalive`
+([Timings](#timings), at the end).
+
+The phases a node goes through (starting, joining, ready, rejoining, stopping) are in
+[`lifecycle.md`](lifecycle.md); this page is the protocol between peers.
+
+## Node IDs and addresses
+
+A node is its node ID (`continuum:<hex>`, from its node key); a transport address only
+says where it is (`mycelium:<public key>`). The identity layer (`transport::identity`)
+between the node and its transports keeps the two apart, so everything below speaks of
+node IDs. A node may have several transports, and reaches a peer on one both have
+(module `transport::paths`). With several, it measures them: every 30 s (or every
+keepalive interval, if that is longer) each gets a PING (the keepalive's, or one of its own), answered by a PONG over the same path, which
+gives its round-trip time. A peer's only path is measured the same way once messages
+go over it (a busy pair sends no keepalives). The
+configured order decides until both are measured; then the node changes to another
+path when it is a quarter faster (and at least 5 ms), so it doesn't flap. A send that
+fails goes to the next path at once, and a path whose sends fail, or whose PINGs go
+unanswered three times in a row, is down: used only when no other works. A node on
+several transports bridges nodes that share none ([`transports.md`](transports.md), Several transports):
+the topology links it on each of its transports (below).
+
+```mermaid
+sequenceDiagram
+    participant N as New node
+    participant S as Seed
+    N->>S: WHO(N's node key, signature over N's and S's address)
+    S-->>N: ME(S's node key, signature over S's and N's address)
+    Note over N,S: each knows which node is at the other's address
+```
+
+A WHO asks who is at an address and says who is asking; a ME answers. Each carries the
+sender's public node key and its signature over the sender's address and the
+recipient's. The transport authenticates the sender's address, so a proof holds for
+that pair of addresses only. Once a node proved itself at an address, messages from
+there are that node's; messages from an address no node proved itself at are dropped,
+and the address is asked WHO (at most every 5 s), so after a restart the first message
+from a peer brings its proof back.
+
+A seed is an address (or something the transport resolves to one: a Mycelium public
+key, IPv6 address or host name); it is asked WHO, and its ME names the node. Where other
+nodes are comes from HELLO_REPLYs and the member list: hints, which are asked WHO before
+anything is sent there; a send to a node that hasn't proven itself anywhere yet is
+refused, and retried like any refused send. A node proven on some transports is also
+asked WHO at its hinted addresses on the others, at most once a minute each: its ME
+there adds a path to it (a second transport, Tor say), which is then measured and failed
+over to. No seed is needed for that: the member list carries every member's addresses.
+
+## Handshake and join
+
+```mermaid
+sequenceDiagram
+    autonumber
+    participant N as New node N
+    participant S as Node S (reached via a seed)
+    participant P as Peer P (known to S)
+
+    N->>S: HELLO(swarm ID if known, epoch, key proof)
+    Note over S: claimed swarm ID matches ours (or none claimed)<br/>N is member, Established, sync reset
+    S->>N: HELLO_REPLY(swarm ID, active established neighbours [P], epoch, key proof)
+    Note over N: swarm ID matches or is adopted<br/>S is member, Established, sync reset
+    N->>P: HELLO(swarm ID, epoch, key proof) - discovered via S
+    P->>N: HELLO_REPLY(...)
+    par sync with one ready peer on the same epoch, the catch-up source (here S)
+        S-->>N: sync messages
+        N-->>S: sync messages
+    end
+    Note over N: all of the source's heads applied: initial sync done<br/>then sync with every neighbour on the same epoch
+    alt S is on a newer epoch than N
+        Note over N: no sync (epochs differ)<br/>remake worker starts a rejoin
+        N->>S: BLOB request (snapshot change)
+        S-->>N: manifest, then chunks (also from other peers on the epoch)
+        Note over N: snapshot applied, then sync as above
+    end
+```
+
+One round trip makes both sides members of each other: the HELLO proves the sender's
+key, the reply the swarm ID and the responder's key. A new handshake resets the sync
+session on both sides; HELLOs carry the handshake's number, so a resent HELLO (its
+reply was lost) or a late copy is answered without resetting again. A node that doesn't know its swarm
+yet (it is joining itself) doesn't answer a HELLO; the sender retries.
+
+The reply lists at most 64 of the responder's active neighbours, each with the addresses
+it reaches them at (at most 8): if it has more, those the recipient would most likely
+pick itself (lowest pair score with it). The recipient takes at most 64 from a reply,
+only valid identities (node IDs), and, once it knows the member list, only
+its own neighbours; their addresses are hints for its transport, and each gets a
+HELLO.
+
+Every HELLO carries a random id of the sender's current run, and the HELLO_REPLY echoes
+it. A reply with another id answers a HELLO from an earlier run (delivered late, or
+queued in Mycelium while the node was down) and is ignored.
+
+**Stale messages.** Mycelium may deliver a message up to 5 minutes late, and an external
+Mycelium queues messages while our node is down (a restart drains that queue for up to
+2 s, but only to cut noise). The protocol therefore must not depend on where in a
+peer's message stream a node starts listening: unanswered HELLOs are retried, a HELLO
+resets the session on both sides, sync messages are idempotent and checked against the
+epoch, and lost or stale sync state is repaired by the reply timeout, the `need` rule and
+the heal. Keepalives only inform.
+
+Every message carries the sender's epoch, and with it how many times the sender changed
+epoch in its current run. A node records a peer's epoch only from a message whose count
+is at least the newest it has seen from that peer, so a message delayed from before
+the peer switched (or rejoined, or gave up a rejoin) can't flip its recorded epoch
+back. The count starts over when the peer restarts, which its HELLO or HELLO_REPLY
+shows by a new run ID.
+
+With a swarm key (`--swarm-key-file`), every HELLO and HELLO_REPLY carries
+`HMAC-SHA256(key, label, swarm ID, from, to)`. A peer is admitted by its first valid one;
+until then everything else it sends is ignored, and a handshake without a valid proof
+gets no answer at all.
+
+Retries: an unanswered HELLO is resent after 1 s, doubling up to 30 s. To an
+unreachable peer (dormant, or three unanswered HELLOs) it is a probe: after
+`dormant_probe`, doubling up to 6 × `dormant_probe` (or `--dormant-probe-max`, which is
+every wait if shorter); members get probes even when they
+aren't neighbours. A member a HELLO_REPLY lists among the sender's active neighbours is
+probed at once: the sender reaches it, so after a partition the first pair to find each
+other again brings the others' probes forward, and the sides reconnect within seconds
+rather than pair by pair. So are all unreachable members once this node becomes
+reachable where it wasn't (libp2p: a relay grants it a slot, or AutoNAT finds it
+public): two nodes behind NATs that restart together can't reach each other until they
+hold slots, and the second to get one reaches the first at once instead of at its next
+probe. Sync messages from a peer that isn't a member yet are
+dropped (the handshake resets the session anyway) and trigger our HELLO.
+
+After a sync reset, both sides may open the sync; crossed openings cost nothing between
+peers that share history. Only a ready node never opens towards a peer that isn't ready
+(HELLO, HELLO_REPLY, sync messages and keepalives all say whether the sender is): that
+peer's answer would carry empty heads, and the whole document would go out twice. The
+peer that isn't ready opens itself.
+
+While a node catches up (joining, or rejoining a newer epoch, until its initial sync is
+done), it syncs with one peer only, the first it tries: otherwise every peer would send it
+the whole document (or everything it lacks) at once. Messages from the others are applied
+but not answered until the initial sync is done; then they only exchange heads. The
+source counts as alive while any message from it arrives; after `catch_up_probe` of
+silence (keepalive / 30, between 1 and 5 s) it gets a STATUS. After three unanswered
+probes, or when it says it isn't ready, or twice that it wouldn't sync with us, the next
+peer takes over. Being alive isn't progress, though: the next peer also takes over when
+three of our sync messages in a row went unanswered and the source has sent no sync
+message for the transport's delivery limit (five minutes for Mycelium: by then it has
+delivered or dropped anything sent, however large); the source given up then isn't
+chosen again for as long,
+so a stalled source doesn't simply take the role back, and gets a fresh HELLO, whose
+reply brings its current peer list (the first one may have listed nobody: a peer lists
+only its neighbours, and a new member isn't one until its registration has spread). Every minute without a sync
+message from the source is logged as a warning.
+
+A sync message larger than 16 chunks (16 × `--blob-chunk`, 1 MiB by default) isn't
+sent: it would be all or nothing, sent again whole after a lost copy, and on a slow link
+may not arrive within the transport's delivery limit (Mycelium's five minutes). The sender takes it back and offers a
+*delta* instead: the changes in the history of its heads but not of the peer's (as far
+as it knows them). The peer fetches them as a blob, in chunks, from the sender and any
+other peer holding those heads (every such peer produces the same bytes), loads them,
+and syncs on; the rest goes in ordinary messages. Until the peer answers, the sender
+sends it nothing; if the answer is overdue, it offers again. This is how a join without a
+recent remake, or a return after much was written, gets the bulk of its changes.
+
+Towards a peer on a slow link the limit is lower: a message is offered as a delta if it
+would take more than 5 s at the throughput measured to that peer (`syncThroughput`,
+[`measurements.md`](measurements.md)), or if it is at least half as large as one that didn't make it to
+the peer in the last hour (its send failed, or it went unanswered; only those of more
+than two chunks count), but never below one chunk. A message too large for the link
+then goes chunk by chunk instead of failing and being sent again whole.
+
+Every sync message says whether its sender is ready. Only a ready peer can be the source,
+and only a message from one completes the initial sync: a peer that is itself still
+catching up has empty heads, which any document trivially contains.
+
+The two sides of a pair take turns sending keepalives; the one that leads the pair sends
+the first. The leader is chosen by one bit of `SHA-256(label, smaller key, larger
+key)`, so both sides agree without talking and each node leads about half of its pairs
+([`swarm/pair.rs`](../src/swarm/pair.rs)).
+
+## Liveness, dormancy and HELLO state (per peer)
+
+```mermaid
+stateDiagram-v2
+    direction LR
+    state Liveness {
+        [*] --> Unknown
+        Unknown --> Active: any message received
+        Unknown --> Dormant: node ready, a neighbour, nothing received for dormant_after
+        Active --> Dormant: node ready, a neighbour, nothing received for dormant_after
+        Active --> Dormant: its farewell (a STATUS saying it is leaving)
+        Dormant --> Active: any message received (after its farewell: from its next run)
+    }
+    state Handshake {
+        [*] --> NotSent
+        NotSent --> Sending: HELLO goes out
+        Sending --> AwaitingReply: sent (or failed)
+        AwaitingReply --> Sending: retry due
+        AwaitingReply --> Established: HELLO_REPLY
+        AwaitingReply --> NotSent: no longer a neighbour (unless probed while unreachable)
+        Sending --> Established: HELLO_REPLY
+        Established --> NotSent: heal, stall reset, peer reactivated,<br/>or it no longer proves the swarm key
+    }
+```
+
+- **Unknown** is a peer nothing was heard from since this node started (it is known
+  from the member list, or another peer named it). It is treated as active; it only
+  shows that nobody answered yet.
+- **Becoming dormant** resets sync with the peer, stops syncing and pinging it, and
+  probes it with a HELLO (after `dormant_probe`, doubling). A dormant member stays in
+  the electorate of remakes while its alive stamp is recent ([`remakes.md`](remakes.md)), so enough
+  of them make a majority impossible; an operator can forget them (`DELETE /peers/{peer}`,
+  a swarm-wide record that is cancelled if the peer turns out to be alive).
+- **Any message** from a dormant peer makes it active again and forces a fresh
+  handshake, whose reply resets sync on both sides.
+- Dormancy is only judged while the node is ready, so joining nodes keep fast retries.
+  A peer's farewell (it is shutting down: a STATUS with `leaving`) makes it dormant at
+  once, whatever our phase; it isn't counted as an incident (`dormancies`). What that
+  run still sends while it stops (sync messages, PINGs, a LINKS_REPLY) doesn't make it
+  active again: only a HELLO or HELLO_REPLY from its next run does.
+- **Strangers** (peers that never became members: listed to us but never answering, or
+  failing the handshake) are forgotten locally once silent for a day, so peers named
+  to a node can't grow its list without bound.
+
+## Member registry and neighbours
+
+`_continuum/members/<node ID>` lists every node that has joined, replicated with the
+document and carried into new epochs. An entry says where its node can be reached
+(`addresses`, kept up to date by the node), so members find each other without having
+met. It is a pure registry, not access control (that
+is the swarm key). A node registers itself as soon as it is ready and again whenever its
+entry is missing while it runs (checked every 5 s). Forgetting a peer (`DELETE /peers/{peer}`)
+removes its entry along with writing the forget record; a forgotten node that is alive
+cancels the record and registers again. Each node acts on a record as soon as it has
+it (and looks at the records again every 5 s), once: a peer it hears of again before
+the cancel arrives is kept.
+
+From the member list every node computes the graph ([`swarm/topology/`](../src/swarm/topology/)), leaving out
+members it can't reach (three unanswered HELLOs, or dormant, until they answer a probe;
+or with no address on any of its transports), and those whose alive stamp is older than
+the electorate window (`electorate-window`) that it hasn't heard from since it started
+(a member coming back sends its HELLO, and counts again from then):
+a ring by key hash, each member linked to the nearest reachable member
+in both directions, plus, per member, the `k − 2` reachable others with the lowest pair
+score; a link exists if either end chose it. With several transports, each has such a
+graph among the members on it (by the addresses in their entries), and a node's
+neighbours are its neighbours on each transport it is on: every transport's graph is
+connected, and a member on two transports is in both, so as long as some members are
+on several, the swarm is connected, and those have about `k` neighbours per
+transport. With 100 members of which 10 are online,
+the 10 form a full mesh; nodes that briefly disagree on who is reachable only add links. `k` is `--neighbours` (default 12), so swarms of up to 13 nodes are a
+full mesh. A node *initiates* only towards its neighbours (HELLO, keepalive, dormancy
+checks, sync openings, pushing its changes, epoch announcements, the heal, the peer list
+in HELLO_REPLY) and *answers* anyone. Changes travel over several hops; heads in
+keepalives tell a node when a neighbour has something it lacks. Until a node is ready
+and knows the member list, everyone counts as a neighbour, so joining works as before.
+A peer that proved itself a member of the swarm (its handshake) but isn't in the member
+list yet is a neighbour too, until it is: otherwise a node that joined before the
+genesis node registered itself, and registered itself in a document without the genesis
+node, would never sync with it, and neither registration would pass.
+So is a member that lists no address on the node's transports but reaches it anyway, as
+long as it says it syncs with the node (STATUS): it only connects out (a libp2p node
+without a listen address), so it is in no graph but its own, and the nodes it picked
+would otherwise only answer it, never send it their changes.
+The neighbours are recomputed as soon as the member list changes or a peer becomes
+unreachable or reachable again, and every 5 s for what has no event of its own
+(unreachability expiring); new ones get a HELLO and a sync opening, former ones a session
+reset.
+
+Each node judges its own stability ([`swarm/stability.rs`](../src/swarm/stability.rs)): the fraction of the last 24 h
+it had at least one live peer. It writes only a coarse tier into its registry entry
+(`tier`: `stable` after a day at ≥ 95%, back to `transient` below 80%), and only when it
+changes. After a restart, a stable node stays stable if a peer's HELLO_REPLY says it was
+away for less than an hour; otherwise it starts over as transient. In the neighbour graph,
+half of each member's scored slots prefer stable members, so long-running nodes form the
+backbone (with 20 stable of 250 members and k = 12: about 65 links per stable member).
+
+Changes travel through a partial mesh by announcement and pull ([`swarm/relay.rs`](../src/swarm/relay.rs)): a node
+pushes its own writes to its neighbours; after applying changes from one neighbour it
+sends its other neighbours a STATUS with its new heads, and a neighbour that lacks those
+heads pulls them (it sets them as the peer's heads in its sync state, so Automerge asks
+for what's missing). It pulls from one neighbour at a time (15 s timeout); neighbours
+that announce heads it lacks meanwhile wait their turn and are pulled from as soon as
+the current pull is answered, if they still have something it lacks. The regular
+STATUS (every third keepalive) triggers the same pull, so gaps close within a few
+keepalive intervals. A node
+that just caught up announces its heads once. In a full mesh nothing is announced: the
+writer reaches everyone (while a node doesn't know its neighbours yet, it announces).
+
+## Keepalive and self-healing
+
+```mermaid
+sequenceDiagram
+    participant A as Node A (its turn)
+    participant B as Node B
+
+    Note over A: B established and active, quiet for keepalive,<br/>no keepalive to B for keepalive, known for keepalive
+    alt no STATUS between them for 3 × keepalive
+    A->>B: STATUS(heads, epoch, ready, syncs with you)
+    Note over B: mark A seen (reactivate if dormant)<br/>record A's epoch, reset sync if it changed<br/>re-handshake if A was dormant or unknown
+    B->>A: STATUS_REPLY(heads, epoch, ready, syncs with you)
+    Note over A: mark B seen, record B's epoch
+    else otherwise
+    A->>B: PING(nonce)
+    Note over B: mark A seen (reactivate if dormant)
+    B->>A: PONG(nonce, B's time)
+    Note over A: mark B seen, round-trip sample
+    end
+    alt after a STATUS: same epoch, heads have differed for resync_after with no sync from it since,<br/>no answer due to our own sync message, last heal at least resync_after ago
+        A->>B: HELLO
+        B->>A: HELLO_REPLY
+        Note over A,B: sync reset on both sides, sync restarts
+    end
+    Note over A,B: after an epoch switch a node announces its epoch at once:<br/>ready peers already on it get its sync opening,<br/>all others a STATUS#59; a node that becomes ready<br/>sends every neighbour a STATUS
+```
+
+A quiet pair's keepalive is a PING, which the peer's paths layer answers at once with a
+PONG over the same path (`transport::paths`): both sides learn the other is alive, and
+the leader gets a round-trip time. Every third one is a STATUS instead, answered with a STATUS_REPLY: each
+side's state, for the heal and against lost announcements. A node's state also goes out
+when it changes: its heads (announcements, above), its epoch after a switch, and its
+readiness when it becomes ready (or ready again after a rejoin) and at shutdown.
+
+A STATUS lists the sender's heads (up to 32; more as a digest of them with 32 of
+them, another 32 each time, so a recipient pulls the listed ones it lacks), its epoch,
+whether it is ready, and whether it would sync with the recipient.
+
+The two sides take turns: after a keepalive from the peer, the next one is ours (the
+leader of the pair sends the first). On its turn a node sends once the pair has been
+quiet for a keepalive interval; off its turn only after 1.5 × keepalive, in case the
+other one doesn't, e.g. because a keepalive or its answer was lost (any message counts
+as heard, so sync traffic suppresses keepalives on both sides). If two keepalives
+cross anyway (the peer's arrives within half an interval after ours), the next turn is
+the leader's, so they don't keep crossing. One keepalive and its answer per pair and interval, each side sending
+every other one, so both measure the round trip, instead of keepalives from both sides
+that often cross.
+
+Inside sync, a lost message is resent after the reply timeout (10 s, 30 s with Tor
+enabled, doubling up to 30 times that). If the peer asks for a change we believe it has (the message carrying it was
+lost while later ones arrived), we forget which changes were sent, and the next message
+carries everything it lacks. A peer that got a change without the ones it builds on asks
+only for those, without saying what it has; Automerge would send just them, and the peer
+ask again for theirs, one round trip per missing change. So we answer as if it had
+nothing since what we share: everything since then goes at once (a blob, if large).
+
+## Timings
+
+Derived from `--keepalive` (`Timing::from_keepalive`, [`state/timing.rs`](../src/state/timing.rs)):
+
+| Name | Value | What for |
+|---|---|---|
+| `status_refresh` | 3 × keepalive | every third keepalive is a STATUS |
+| `dormant_after` | 4 × keepalive | silent this long, a peer is dormant (three keepalives lost in a row are tolerated) |
+| `resync_after` | 2 × keepalive, at least twice the first sync reply timeout (20 s; 60 s with Tor) | heads differing this long make a heal |
+| `dormant_probe` | 10 × keepalive | the first probe of an unreachable peer, doubling up to 6 × (or `--dormant-probe-max`) |
+| `catch_up_probe` | keepalive / 30, from 1 to 5 s | how soon a silent catch-up source is probed |
+| sync reply timeout | 10 s (30 s with Tor enabled: the longest of the transports'), doubling up to 30 × | resending a sync message nothing answered |
+
+The peer worker runs when the earliest of these is due for some peer (and when something may have made one due sooner: a HELLO sent, a sync message sent, a keepalive received, a new peer or new neighbours), at least every 5 s; the remake worker every second.