Store synchronization protocol

Implementation note (non-normative). An MVP of this draft is implemented in src/internal/sync.ts (syncPull / syncPush / syncServe over an abstract byte-stream transport): S.2 framing, the S.3 handshake, S.4 advertisement and wants (modes add and mirror), S.5 exact Merkle-pruned haves and acks, S.6 thin-pack transfer with the per-session sent set, the S.7 completion loop, and S.8 binding (fast-forward, per-name force, mirror deletions, push-mode ref-status). The ancestry, filter, and path-want capabilities remain design-only and are not advertised, so an implementing peer degrades to the core protocol.

The protocol moves the closure of chosen roots from a source store to a sink store, transferring — after a short negotiation — only blocks the sink does not already hold, then binding named refs at the sink. It is rsync-like in shape: cheap approximate agreement on what the other side has, an exact integrity check at the end, and convergence under repeated runs. It differs from rsync where content addressing makes rsync's machinery unnecessary: there are no rolling checksums and no per-file deltas, because a Merkle DAG already names every piece of content by hash. Agreement on a dag-cbor ref is agreement on its entire subtree, so "delta transfer" degenerates to "send the blocks the sink lacks".

#S.1 Model and roles

• A session runs over one reliable, ordered, bidirectional byte stream (TCP, a TLS connection, a pipe, an HTTP/2 stream — the choice is out of scope). One session syncs one (source, sink) pair in one direction.
• The client opens the session and declares the direction: pull (client is the sink) or push (client is the source). After the handshake the protocol is symmetric — every rule below is written in terms of source and sink, not client and server.
• Both stores MUST use the same hash function (§3.4, §10.3). This is checked in the handshake and is fatal. Writer parameters (§14) need NOT match: blocks move verbatim and are never re-chunked or re-encoded, so parameter mismatch cannot affect what this protocol stores. (It affects what each side would write natively, which is not this protocol's concern.)
• All transferred blocks are hash-verified by the sink per §12.4. The protocol never extends trust. A malicious source can at worst send garbage that fails verification, or an incomplete DAG that fails the completion check (S.7). It cannot cause the sink to bind a name to data that does not match its ref.

#S.2 Framing and messages

Every protocol message is one frame:

varint(len(body)) || body        body = canonical CBOR map (§5)

• Varints per §3.1 (strict). Frame length limits follow the pack import rule verbatim (§12.4): enforced the instant the varint decodes, accept ≤ 2^30, reject > 2^31 − 1, never allocate from a declared length alone.
• The body is a canonical-CBOR map (§5) whose t field (text) names the message type. Unknown message types and unknown fields MUST be rejected. Extensions are gated on capabilities negotiated in hello, never sniffed (§15.1 discipline).
• Refs inside messages use the CBOR link form — tag 42 (§4, §5.2 rule 5) — and are validated eagerly on decode, in store context (the session's hash function).
• Pack bytes are NOT sent as CBOR. After a pack message, the raw CARv1 stream follows as chunk frames: varint(n) || n bytes, with a terminating varint(0). This is necessary because CARv1 is self-delimiting only at end of input (§12.1: no terminator), and the session stream continues past it. A zero-length chunk is unambiguous as a terminator: no pack piece is chosen to be empty by the chunker sending it. Concatenating the chunk payloads MUST yield exactly one canonical pack (§12.2–§12.3).

Message types (fields detailed in the sections that follow):

#S.3 Handshake

Each side sends hello first:

{t: "hello", v: 1, hash: "sha2-256", op: "pull"/"push" (client only),
 caps: ["ancestry", "filter", "mirror", "path-want", …]}

• v is the protocol version. v ≠ 1 → error UNSUPPORTED, reported distinctly from corruption (the §15.1 rule, applied to sessions).
• hash is the store's hash function identifier (§10.4). A mismatch is fatal: refs from one store can never resolve in the other (§4 store context), and no re-hashing bridge exists or is wanted.
• caps lists optional capabilities. A capability is in effect only if both sides list it. Core protocol (everything not marked with a capability below) needs no caps at all.

#S.4 Advertisement and wants

The source sends refs: a map of ref name (§10.2) → Link for every named, non-tombstoned ref it is willing to serve (policy on which names to expose is out of scope). The sink replies want:

{t: "want", roots: [Link…], names: {name: Link…}, mode: "add"/"mirror"}

• roots — the refs whose closures the sink wants. Typically chosen from the advertisement, but any valid ref MAY be requested. The source answers error NOT_FOUND if it cannot serve one.
• names — the subset of bindings the sink intends to adopt (name → the advertised Link). Binding happens at the sink at the end (S.8). Echoing the intended bindings here lets a push-mode server refuse a non-fast-forward early instead of after the transfer.
• mode: "mirror" (capability mirror) — after a successful sync, the sink also tombstones (§10.2) every ref name it holds that matches the sync's name selection but was absent from the advertisement. This is rsync's --delete, and like it, opt-in only; default "add" never deletes anything.
• Capability path-want: a want MAY be {path: "/a/b", root: Link}; the source resolves the path under §11 against root and serves the resolved entry's ref, reporting the resolution in its ack so the sink knows what to bind. This is the "sync one subtree" affordance; it adds no format surface because the result is just another root.

#S.5 Negotiation — establishing what the sink already has

The point of negotiation is to compute the source's exclude set for a thin pack (§12.3). Two mechanisms are available, composable, and both optional. With neither, the source sends a full pack and the protocol degrades to "copy everything", which is still correct.

Haves (exact, Merkle-pruned). The sink sends have with roots whose entire closure it is certain to hold — in practice its own named refs, since names are bound only after closure verification (S.8 maintains this invariant). The source replies ack, listing the subset it can expand. A have is usable only if the source holds its closure too, since thin-pack exclusion is computed by traversal in the source's store (§12.3). Acked haves seed both exclusion sets: traversal (full CID) and emission (multihash) — the §4 two-set discipline, inherited unchanged.

Capability ancestry: when a have targets an "r" root the source does not hold, the sink MAY walk its own prev chain (§6) and offer ancestors in further have rounds — the git negotiation shape, cheap when the two stores share history. Rounds are bounded by the sink (RECOMMENDED: stop after 2 unacked rounds or 256 offered roots). An unacked have is simply not excluded — it costs bytes, never correctness.

Filter (approximate, per-block). Capability filter: the sink sends a Bloom filter over the multihashes of every block it holds (block identity, §4). This covers blocks that are not under any named root — orphans from an interrupted transfer (S.9) — which haves can never describe.

{t: "filter", m: bits (power of two, ≤ 2^32), k: probes (1..16),
 bits: byte string, ceil(m/8) bytes}

Probe derivation is fixed so both sides agree bit-for-bit, and it costs no extra hashing — the digest is already uniform. Let d be the multihash digest. h1 = the first 8 digest bytes as a big-endian integer, h2 = the next 8 bytes big-endian, forced odd (h2 | 1). Probe i (0-based, i < k) sets bit (h1 + i·h2) mod m, bit j being byte j >> 3, mask 1 << (j & 7) in bits. (Digests are ≥ 20 bytes, §4, so the 16 bytes consumed always exist.) The sink SHOULD size m for ≈1% false positives at its block count.

A filter hit suppresses emission only. The source still traverses the block's children, because a probabilistic claim about a parent says nothing about its children. Only acked haves may prune traversal, since only they carry the Merkle closure guarantee. Collapsing the two mechanisms into one set re-creates exactly the failure mode §4's two-set rule exists to prevent.

A false positive causes a needed block to be omitted; the completion loop (S.7) detects and repairs it. Correctness never rests on the filter — only byte count does. This is the rsync trade re-expressed: approximate agreement up front, exact verification behind it.

#S.6 Transfer

The source sends {t: "pack"} followed by one thin pack (§12.3) as chunk frames (S.2). Roots are the want roots (deduplicated, first-occurrence order, §12.1); exclusion is seeded from acked haves (both traversal and emission) and from filter hits (emission only, applied per section during the DFS). The pack is otherwise exactly canonical (§12.2) — DFS preorder, per-multihash section dedupe — so a session transcript's pack bytes are a pure function of store contents, wants, acked haves, and the filter.

Across a session the source keeps a per-session sent set (multihash- keyed) and adds every emitted section to its emission exclusion for later rounds: no block is transmitted twice in one session.

The sink imports under §12.4 with hash verification on and root-closure verification off. Completeness is instead checked jointly with what the sink already holds (the thin-pack rule), by the sink itself, in S.7. Import order note (§12.4) applies: a partially imported pack is harmless, blocks are immutable and content-addressed.

#S.7 Completion — the exact check

After each import the sink walks the closure of the want roots in its own store (traversal keyed by full CID, §4; raw refs are checked for presence, never fetched or decoded — the §15.2 mark discipline). Every reachable block found absent goes into:

{t: "missing", refs: [Link…]}      (deduplicated, full CID)

The source answers with another pack whose roots are exactly those refs, excluded by the session sent set and the standing exclusions. A requested ref the source does not hold is error NOT_FOUND. This is fatal: the source advertised something it cannot serve.

Termination: the sink's absent set — closure(wants) minus its store — is finite and strictly shrinks every round (each supplemental pack imports at least one absent block, and blocks are never removed during a session, S.10). Rounds are bounded by DAG depth in the worst case. With no filter and honest acks, zero missing rounds occur, because thin-pack exclusion by acked haves is exact.

When the walk finds nothing absent, the sink sends done. Only then does binding happen.

#S.8 Binding refs at the sink

After done, for each name in the accepted names selection, the sink binds name → ref (§10.2) under a policy:

• Fast-forward (default). Let old be the sink's current target (absent or tombstoned → always fast-forward). If old = new (full CID): no-op. Else if both resolve to "r" nodes and old is reachable from new by the prev chain (§6): update. Anything else is CONFLICT. The name is left untouched and reported. A force flag on the want (explicit, per name) replaces unconditionally — last-write-wins is all the format itself promises (§15.3).
• Mirror deletions (S.4) are applied only after every binding in the selection succeeded.
• In push mode the sink is the server; it reports one ref-status per name (ok / conflict / denied) so the pushing client learns the outcome — the analogue of a git push report.

Binding is the last act, after closure verification: this ordering is what maintains the invariant S.5 leans on, that a named ref's closure is fully present. A crash before binding loses no data and corrupts nothing — it leaves verified orphan blocks (see S.9).

#S.9 Interruption and resumption

The protocol keeps no resumption state. A session killed at any point leaves the sink with some subset of verified blocks and its refs untouched — exactly the §12.4 non-transactional import posture. A re-run converges like rsync does:

• Blocks already landed under a named ref are excluded via haves.
• Orphan blocks from the interrupted transfer are excluded via the filter capability — this, not byte savings on cold syncs, is the strongest argument for implementing it.
• Without filter, a re-run re-sends orphaned blocks; the sink's import treats them as idempotent duplicates (§12.4). Wasteful, never wrong.

#S.10 Concurrency and garbage collection

• Neither store may run garbage collection (§15.2) during a session. Source: acks and the sent set promise availability of blocks not protected by any of its names' liveness. Sink: imported blocks are deliberately unreferenced by names until S.8, so to a concurrent collector they are indistinguishable from garbage. Both are instances of the exclusive-access rule §15.2 already states.
• Concurrent ordinary writes on either side are safe (§15.3). A source-side write racing the session at worst grows the DAG behind an advertised name after advertisement — the session syncs the advertised roots, a snapshot, exactly as a reader would see one.
• Ref binding races at the sink are last-write-wins per §15.3. The fast-forward check narrows but cannot close this without a compare-and-swap capability on the sink's store, which remains out of scope, as §15.3 says.

#S.11 Security considerations

• The sink verifies every block hash (§12.4) and its own closure (S.7); Store.trusted-style verification skipping MUST NOT be applied to sync input from another party (§16).
• The filter reveals a probabilistic sketch of the sink's entire block set to the source — a privacy leak beyond the wants themselves. Implementations SHOULD offer scoping the filter (e.g. to orphans only) and MUST NOT require the capability.
• Haves reveal the sink's named roots to the source; ancestry rounds reveal history. Same posture: optional, sink-controlled.
• A hostile sink can request arbitrary refs (want, missing) and probe for block existence. Sources exposed beyond trusted peers need an authorization layer, which is out of scope with the rest of transport (§1.4).
• Frame and chunk length limits (S.2) bound memory exactly as pack import does; negotiation rounds and offered-root counts are bounded (S.5, RECOMMENDED limits) so a peer cannot spin the session.

#S.12 Non-normative: worked session shape

Pull, shared history, no filter — the common case:

client(sink) → hello {v:1, hash:"sha2-256", op:"pull", caps:["ancestry"]}
server(src)  → hello {v:1, hash:"sha2-256", caps:["ancestry","filter"]}
             → refs  {heads:main → bafy…A}
sink         → want  {roots:[bafy…A], names:{heads:main: bafy…A}, mode:"add"}
             → have  {roots:[bafy…B]}          # sink's heads:main
source       → ack   {roots:[bafy…B]}          # source has B: common ancestor
             → pack  + thin pack: closure(A) minus closure(B)
sink         → done                            # closure walk found nothing absent
sink binds heads:main → bafy…A (fast-forward: B on A's prev chain)

One round trip of negotiation, one pack, zero repair rounds — and every byte of the pack is a block the sink genuinely lacked.