diff options
| author | tv <tv@krebsco.de> | 2026-11-16 14:02:45 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-16 15:06:17 +0100 |
| commit | e0cac08c5c293f5eb05a5ddf5302b9dc89d9e44d (patch) | |
| tree | 8a2eb513e19bc75b52e19c81d69091e807441c17 /docs/federation.md | |
| parent | 3b5045838daec9d8ffb46ff030bf17e08fd53148 (diff) | |
docs/federation: checkpoints the parties pass
A version may name heads for a checkpoint: what counts there written down, as those
heads, a version and the IDs of the events that count there. Once a node takes the
version, it moves to the checkpoint, forgets what came before but what it keeps, and
refuses every event not above the heads. The proposal, its votes and the version events
writing it must be above them, so that moving refuses nothing that decided it. Judging
after a checkpoint reads only what counts, which it keeps; what it loses is what counted
no more before it, and what isn't above its heads, which its party signs again.
A federation's root is its first checkpoint, and a fork's root a checkpoint at the
heads it forks at, which nodes holding that history check and others take on their
operator's word. A node checks everything back to its checkpoint, which it built itself
or its operator pinned. Checkpoints any member makes are a road not taken.
Diffstat (limited to 'docs/federation.md')
| -rw-r--r-- | docs/federation.md | 228 |
1 files changed, 143 insertions, 85 deletions
diff --git a/docs/federation.md b/docs/federation.md index 63b4632..ce65ebe 100644 --- a/docs/federation.md +++ b/docs/federation.md @@ -51,7 +51,8 @@ nothing coming from any node breaks a promise for the others. 1. **What counts is what a party signed, with a key it holds, where the policy lets it write.** Every honest node refuses an event the version current at its history doesn't let be written, whoever brings it, and reads nothing else as counting. A node - holds every event back to the federation's first, and checks all of it itself. + checks every event back to its checkpoint, which it built itself or its operator + pinned ([`store.md`](store.md)). 2. **The policy changes only by the votes of two thirds of its parties**, as one history saw their votes; and nodes that hold the same events read the same policy. Without keys voting twice, a version that passed stays, on every node; with them, the nodes @@ -71,16 +72,19 @@ Not promised: * that honest nodes stay together where keys voted twice (Changing the policy): each node keeps the version it took, until its operator has it drop it, and one that had taken neither of two (it lagged behind, or joins) may be shown either first; -* that the store stays small: it keeps every event, and a fork its whole history. +* that what isn't above a checkpoint's heads is taken once nodes moved to it: its party + signs it again (Checkpoints); +* that a checkpoint, or a fork's root, that a node takes on its operator's word is the + one the others built ([`store.md`](store.md), Pinned checkpoints). ## The design -It builds on the store ([`store.md`](store.md)): a set of events that only grows, each -named by the SHA-256 of its bytes, its **ID**, and naming the events it builds on, its -**dependencies**; judged at that history, every node alike; and read together as one -state. The federation is the store's fold: what its events are, how one is judged, and -what they read as. What carries the store, a swarm's Automerge document with its changes -and its remakes, the federation never sees. +It builds on the store ([`store.md`](store.md)): events, each named by the SHA-256 of +its bytes, its **ID**, and naming the events it builds on, its **dependencies**; judged +at that history, every node alike; and read together as one state, from a checkpoint and +the events after it. The federation is the store's fold: what its events are, how one is +judged, and what they read as. What carries the store, a swarm's Automerge document with +its changes and its remakes, the federation never sees. What it asks of the store: @@ -90,7 +94,9 @@ What it asks of the store: order they came in. * **A node's own**: a node refusing what its history takes, by what the node took before, and an operator having its node drop what it took. -* **Forks**: a store whose root builds on another's events, carrying their history. +* **Checkpoints**: the store starting anew from what counts at heads the parties name, + forgetting the rest. +* **Forks**: a store whose root is a checkpoint at another's heads. * **Members**: the nodes that carry the store, which the federation names. ### Events @@ -116,9 +122,9 @@ Spread out: * **`sig`**: an SSH signature by `key` (`ssh-keygen -Y sign`, namespace `continuum-federation`) over the event's bytes without `sig`, unarmored, in base64. -Three events no party signs, as their bytes need no signer, each without `party`, `key` -and `sig`: a federation's root (Starting a federation), a fork's (Forks), and a version -(Changing the policy). +Three things no party signs, as their bytes need no signer, each without `party`, `key` +and `sig`: a version event (Changing the policy), and a federation's root and a fork's, +which are checkpoints (Checkpoints). An event is none if its bytes aren't the JCS encoding of the JSON they read as, if a field is missing or more, or if it is larger than the federation allows, which is within @@ -167,6 +173,8 @@ current at its heads, Forks). Spread out: gives it no nodes, so that a list it wrote before it was taken out counts no more; a later version may name it anew again; the first version and a fork's name those of the parties that start it (Nodes). +* **The checkpoint** (`checkpoint`), where the version names one: the heads at which the + store moves to a checkpoint once the version is current (Checkpoints). * **The rules**, in order: the first whose path matches a path says who writes there. A path is segments separated by `/`, none empty. A rule's first segment is literal, and not `_continuum`; any other is literal, `{party}` (the name of a party of the version, @@ -187,13 +195,14 @@ so a party named like a shared name takes it where a `{party}` rule comes before application keeps party names apart from its spelling (no party named `wiki` while `wiki.r` is lass's). -A version is none if a field is missing or more, or if it breaks any of the above. It -can't pass, and a version event naming it is refused. A proposal is taken whatever it -holds: whether it is a version is asked where a version event names it, so that nodes -knowing more of what a version may say don't part from those knowing less. A node shows -whether a proposal is a version by the federation it knows, and a party's client backs -none that isn't: two thirds backing one that can never be written bind the federation to -its version, as a yes binds (Changing the policy). +A version is none if a field is missing or more (but for `checkpoint`, which it may +leave out), or if it breaks any of the above. It can't pass, and a version event naming +it is refused. A proposal is taken whatever it holds: whether it is a version is asked +where a version event names it, so that nodes knowing more of what a version may say +don't part from those knowing less. A node shows whether a proposal is a version by the +federation it knows, and a party's client backs none that isn't: two thirds backing one +that can never be written bind the federation to its version, as a yes binds (Changing +the policy). What the swarm's document holds beyond the events, and what a node takes at its API, is the store's ([`store.md`](store.md), On Automerge). @@ -278,11 +287,11 @@ chain the node took. value on one proposal are one vote. An honest party backs another proposal only once the first is dead, and a death is never taken back. Two versions changing one still name a party: where one of the proposals is passed and dead by all the votes, the - party whose `true` and `false` made it so. A tool over the votes reports it, as they - are signed and anyone can check them; a node reports the versions it refused. That - proves its keys signed both, not that it meant to: two of its nodes voting each by - itself, or a stolen key, look the same. Taking it out is the parties' choice, and a - fork. + party whose `true` and `false` made it so. A tool over the votes the parties' clients + keep reports it, as they are signed and anyone can check them, after a checkpoint left + them out too; a node reports the versions it refused. That proves its keys signed + both, not that it meant to: two of its nodes voting each by itself, or a stolen key, + look the same. Taking it out is the parties' choice, and a fork. * **A proposal on a version that isn't current lapses**, with the votes on that version. Everything the federation decides is a change of the policy: who the parties are, their @@ -311,7 +320,7 @@ does. Nothing is written for it: the version says it. and writes a set without the old ones (a client does it all). What a key it dropped signed counts no more, wherever in history it is, and replaces nothing the party signed. A key added back, from a backup say, brings back what it signed, where nothing - the party signed since replaced it. + the party signed since replaced it and no checkpoint since left it out. * **Only a version revokes a key it names.** One lost or stolen is answered by a version naming the party's keys anew: no set written under an earlier version counts any more. Until then, the old key votes, and writes the party's set and node list, as the @@ -342,12 +351,47 @@ else does: So a place's value, a party's set and its list are each the latest its party signed that counts: what the party signed after replaces what it signed before, whatever order the events came in, and what counts no more replaces nothing. Nothing is deleted: a party -empties its place by writing `null`, and what counts no more stays in the store. A place -given back to its party, or a key added back, shows what the party signed before where -nothing replaced it since, until the party writes there again. Two writes of one party -at one place, neither in the other's history (two of its clients at once), leave the one +empties its place by writing `null`, and what counts no more stays in the store until a +checkpoint leaves it out (Checkpoints). A place given back to its party, or a key added +back, shows what the party signed before where nothing replaced it since and no +checkpoint left it out, until the party writes there again. Two writes of one party at +one place, neither in the other's history (two of its clients at once), leave the one with the lower ID; the party writes again, after both, to choose. +### Checkpoints + +A **checkpoint** writes down what counts at some heads: those heads, a version (the one +current there, or a fork's), and the IDs of the events that count there with that +version current (What counts), as the JCS encoding of +`{"at": [<IDs>], "keeps": [<IDs>], "version": <version>}`, its IDs ascending, named by +its SHA-256 ([`store.md`](store.md), Checkpoints). Every node holding the history up to +those heads builds the same one, and its version counts as written. + +A version names a checkpoint by its heads (`checkpoint`). It is a version only where its +proposal is above those heads, and a vote on it, or a version event writing it, is taken +only where it is above them too ([`store.md`](store.md), Events): so moving to the +checkpoint refuses nothing that decided it. A node that takes the version moves to the +checkpoint: it builds it, forgets everything before those heads that it doesn't keep, +and every event not above them, and refuses such events from then on. Judging an event +after them needs nothing it forgot: the version, every party's keys and node list, and +the proposals on the current version with their votes all count, and are kept. A node +that can't build a checkpoint, as it was away longer than its peers kept what they +forgot, or as it joins, takes it only where its operator pins it +([`store.md`](store.md), Pinned checkpoints). + +What a checkpoint loses: what counted no more before it, so that a key added back, or a +place given back, brings back nothing signed before it, and a party that voted twice on +a version behind it shows only in the votes its clients kept; and what isn't above its +heads, which its party signs again. That is rare: the heads are in the proposal's +history, nodes build on them while the vote takes its course, and a client writing once +a checkpoint is proposed builds only on what is above its heads. + +A version that changes nothing but its number, what it changes and its checkpoint only +moves the store on. Like any version, it lapses the proposals on the version before, so +a party proposes one where nothing else is proposed on the current version. A +federation's root is its first checkpoint, without heads (Starting a federation), and a +fork's root a checkpoint at the heads it forks at (Forks). + ### Nodes A party lists the nodes that carry for it, by node ID, in its **node list**: a `nodes` @@ -370,22 +414,22 @@ Any group can carry on without the rest: too many parties are away for good, a v the group won't follow passed, or the parties can't agree. It **forks**: it starts a store of its own from the federation's ([`store.md`](store.md), Forks). -1. One of the group makes the fork's root, which no party signs: the heads it forks at - as its `deps`, and the fork's version as its `fork`, so that one version and one set - of heads make one fork. Its version changes the version current at those heads, is - numbered one past it, names anew the node lists of the parties that start it, and the - keys of any party whose keys it changes; a root whose version doesn't is no fork. - Every proposal is a chance to fork: the version is usually one that didn't pass. +1. One of the group makes the fork's root, a checkpoint at the heads it forks at, which + no party signs, so that one version and one set of heads make one fork (Checkpoints). + Its version changes the version current at those heads, is numbered one past it, + names anew the node lists of the parties that start it, and the keys of any party + whose keys it changes; a root whose version doesn't is no fork. It keeps the events + that count at those heads with that version current. Every proposal is a chance to + fork: the version is usually one that didn't pass. 2. A fork is named by its root's ID, which nobody can steer to a given name, the - federation it came from least of all. It carries every event of its root's history, - each counting there as it did, and after them takes only events with its root in - their history: what the stayers sign after it isn't taken there, nor what the fork's + federation it came from least of all. It takes only events with its root in their + history: what the stayers sign after it isn't taken there, nor what the fork's parties sign after it in the federation they left. -3. The others join it as a node joins any swarm, by its ID, and judge every event of it, - back to the federation's first, whether or not they hold the federation it came from. - A node that holds it says what it holds that those heads lack, and, party by party, - whether the fork's version gives it the keys it had there: a founder may give a party - that didn't go keys of its own. +3. The others join it as a node joins any swarm, by its ID. A node holding the history + up to those heads builds the root and checks it, says what it holds that those heads + lack, and, party by party, whether the fork's version gives it the keys it had there: + a founder may give a party that didn't go keys of its own. A node that doesn't hold + that history takes the root on its operator's word, as its operator names the fork. A fork needs nobody's vote and nobody's ack: it binds only those who go, and the swarm they left goes on for those who stay. A party the fork's version leaves out writes @@ -415,26 +459,29 @@ parties, zones, blocks and names that are nobody's by their spelling. ### Starting a federation -A federation starts with a store of its own: its root, `{"genesis": <version>}`, holds -the first version and nothing else, and no party signs it, so one first version makes -one federation, named by the root's ID. Among the node lists the version gives, one -names a node of its founders', so the federation starts with members, and other nodes -come in as their parties list them. Its swarm's genesis change holds the root, built -byte for byte from it ([`store.md`](store.md), On Automerge). So nothing is from before -the federation: it changes by versions, and any group carries on by a fork. A running -swarm doesn't become federated; its parties start one, and sign into it what they keep. +A federation starts with a store of its own: its root, a checkpoint without heads that +keeps nothing, its version the first, which no party signs (Checkpoints), so one first +version makes one federation, named by the root's ID. Among the node lists the version +gives, one names a node of its founders', so the federation starts with members, and +other nodes come in as their parties list them. Its swarm's genesis change holds the +root, built byte for byte from it ([`store.md`](store.md), On Automerge). So nothing is +from before the federation: it changes by versions, and any group carries on by a fork. +A running swarm doesn't become federated; its parties start one, and sign into it what +they keep. ## Why it holds 1. **What counts.** An event is judged at its history, which its ID fixes, by the version current there, which the version events in that history fix, each judged by the votes in its own. Every node judges alike, and refuses the event and everything - built on it ([`store.md`](store.md)). What counts is read from the events a node - holds: the current version, the highest number; each party's keys, by that version - and its set; each place's value, the latest its party signed that counts. None of it - depends on the order the events came in, nor on what carried them, and what counts no - more replaces nothing. An event brought again is the same event; one written at a - history from before a version is judged by the version current there. + built on it ([`store.md`](store.md)). What counts is read from what a node holds, its + checkpoint and the events after it: the current version, the highest number; each + party's keys, by that version and its set; each place's value, the latest its party + signed that counts. None of it depends on the order the events came in, nor on what + carried them, and what counts no more replaces nothing. An event brought again is the + same event; one written at a history from before a version is judged by the version + current there. A checkpoint keeps what judging reads, so moving to one changes no + verdict. 2. **The policy.** A version is written only where, at one history, two thirds of the parties of the version it changes voted `true` for it, and a node takes it only where it changes the version the node reads, or is one it took. An honest party backs one @@ -447,9 +494,10 @@ swarm doesn't become federated; its parties start one, and sign into it what the written; keys an earlier version named move no node that took the version after it. With them, each node keeps the version it took, nodes holding the same events still read the same policy, and the parties fork. -3. **Carrying on.** A fork is a store of its own, named by its root, carrying its - history so that anyone checks it, its members those its lists name, joined by its - operators' choice only. A party nobody follows carries on alone. +3. **Carrying on.** A fork is a store of its own, named by its root, which nodes holding + its heads' history check and others take on their operator's word, its members those + its lists name, joined by its operators' choice only. A party nobody follows carries + on alone. ## Attacks @@ -491,7 +539,7 @@ crafted events. *Sim*: a simulation. *Bench*: measured, not judged. | 30 | Flooding: places, proposals, votes | Slow, or out of memory; not wrong: the others fork | bench | | 31 | A party lists another party's nodes, or one its party dropped | Nothing changes: a node is a member as its own party's | unit | | 32 | Events the stayers sign after a fork, brought to the fork | Never taken: their history lacks the fork's root | unit | -| 33 | A fork whose root builds on an event no node takes (a version written without votes, say), sent to nobody before | No fork: every event of its history is judged, and one refused takes the root with it | unit | +| 33 | A fork whose root doesn't read as its heads do: an event kept that doesn't count there, one left out, or heads holding an event no node took | Nodes holding those heads' history build the root, find it differs, and don't join; others take it on their operator's word | sim | | 34 | A fork whose version doesn't change the one current at its heads, or isn't numbered one past it | No fork | unit | | 35 | A fork at heads of its founder's choosing | Joiners holding the federation are told what those heads lack | unit | | 36 | A fork's version giving a party that didn't go keys of its founder's | Joiners holding the federation are told, party by party | unit | @@ -499,7 +547,7 @@ crafted events. *Sim*: a simulation. *Bench*: measured, not judged. | 38 | A group whose parties list no nodes forks | Its version names their node lists | unit | | 39 | A federation, or a version, a node doesn't know | It stops taking events | unit | | 40 | Two parties each writing a key set beside the other's vote, crossed | Nothing: votes go by their version's keys | unit | -| 41 | A federation's root holding more than its first version, or whose version lists no node | None; or nothing after it is taken, as no node is a member | unit | +| 41 | A federation's root with heads or events kept, or whose version lists no node | None; or nothing after it is taken, as no node is a member | unit | | 42 | A version replacing every listed party's keys | The lists still count, each its party's until it writes another | unit | | 43 | A version whose `since` for a party is neither its own number nor the `since` the version it changes gives the party, or that changes a party's keys or list without naming them anew | No version: a version event naming it is refused | unit | | 44 | A version written again late, at a history from before the next, by a node that was away | Taken: it is one every node took | unit | @@ -511,6 +559,11 @@ crafted events. *Sim*: a simulation. *Bench*: measured, not judged. | 50 | An honest party backs a second proposal once its first is dead; another party later signs `true` on the first too | It isn't named: its first proposal is dead by all the votes; the party with `true` and `false` on one is | unit | | 51 | A node whose operator had it drop a version is sent it again, written anew by another node, or holds the votes that passed it | It refuses any event writing that version and writes it no more, until its operator says otherwise | unit | | 52 | A party taken out and let in again | The list it wrote before counts no more: its list's `since` is the version that let it in | unit | +| 53 | A version naming checkpoint heads its proposal isn't above, or a vote on it, or a version event writing it, that isn't | No version, or refused: moving to a checkpoint refuses nothing that decided it | unit | +| 54 | An event not above a checkpoint's heads (written beside them, or built on one that was), after nodes moved to it | Refused; its party signs it again | unit | +| 55 | A checkpoint a node can't build, handed to it by peers, or a fork's root it can't check | Taken only where its operator pinned it, or named the fork | unit | +| 56 | Two versions changing one, naming different checkpoints | As 12: each node keeps the one it took, and moves to its checkpoint | unit | +| 57 | A key added back, or a place given back, after a checkpoint | Brings back nothing signed before the checkpoint that counted no more there | unit | ## Roads not taken @@ -555,9 +608,10 @@ crafted events. *Sim*: a simulation. *Bench*: measured, not judged. * **Votes counted by the keys their party's set held at their history.** A vote would be checked against the sets around it; by the keys its version names, it is checked from itself and its version alone, by a client too, and those keys can be kept offline. -* **Events that count no more left out**, by the store or by a fork. Every node checks - every event back to the federation's first, a fork's joiners too; one that left some - out would take the rest on someone's word. +* **Checkpoints any member makes**, as a remake's coordinator does. No vote would be + needed, but an adversary's node could make one whenever it likes, forgetting what + counts no more and making nodes that were away take one on their operator's word + again; and two at once would part the nodes until their operators chose. * **A place where a party says which fork it went to.** A node following it by itself would follow a stolen key into a swarm with any policy; parties say where they went as they like. @@ -577,9 +631,10 @@ parties can't be made to upgrade together, so from the first federated swarm on, continuum's releases work together in one, and what all its nodes must agree on is named by the federation's number: the rules of this design, an event and its signature, how a path and a version are spelled and read, the sizes each may have, how an event is judged -and what the events read as, which version a node takes and which is current; and of the -store on Automerge ([`store.md`](store.md)), what the document holds, what a change -writes, the snapshot, and the Automerge version, whose encoding fixes a change's hash. +and what the events read as, which version a node takes and which is current, what a +checkpoint keeps and how it is spelled; and of the store on Automerge +([`store.md`](store.md)), what the document holds, what a change writes, the snapshot, +and the Automerge version, whose encoding fixes a change's hash. A change to the federation is a design like this one, with the next number. A swarm moves to it by a version of its policy that names it (`"federation": 2`), which the @@ -608,27 +663,30 @@ Everything here, and the store, is built behind the `federation` feature: withou continuum builds and behaves as it does, and its tests pass untouched. 1. **The store**, generic and in memory, with a fold made for its tests: events, - histories, judging at a history, the state, a node's own refusals and drops, forks - ([`store.md`](store.md), Tests). + histories, judging at a history, the state, checkpoints and moving to them, a node's + own refusals and drops, forks ([`store.md`](store.md), Tests). 2. **The federation's fold**, as pure code: events and what makes one, versions and what makes one valid, rules and paths, places, keys, votes, passing and dead, version events, which version a node takes and the current one, what counts, node lists and - members; the byte formats, and the sizes each may have. Its tests are its rows of - Attacks, each with events made for it, and the promises checked over histories - generated small enough to try every order, and larger by seed. + members, checkpoints: what one keeps, and moving to one; the byte formats, and the + sizes each may have. Its tests are its rows of Attacks, each with events made for it, + and the promises checked over histories generated small enough to try every order, + and larger by seed. 3. **The store on Automerge**: a swarm started from its root, events in its document, - what a change writes, every event put again whichever change carried it; members by - the federation, a node's party in its configuration and its own entry, shown in the - handshake before that entry exists, nodes syncing with members only (a wire change), - neighbours by party, and no token from another node; the API putting events and - showing what counts; reports of the versions a node refused, its operator having it - drop what it took, and a tool reporting, from the votes, a party that voted twice. - Until stage 5, a federated swarm takes no remake: from stage 4 on, one that grows too - large starts afresh by a fork whose version names the same parties, keys and rules. -4. **Forks**: a store started from another's events, named by its root, every event of - its history judged. -5. **Remakes**: compaction only, the snapshot holding the events at its base, and every - event beyond it put again. + what a change writes, every event put again whichever change carried it, what a + checkpoint forgot read no more, a change carrying an event a move refuses dropped, + and a checkpoint its operator pins; members by the federation, a node's party in its + configuration and its own entry, shown in the handshake before that entry exists, + nodes syncing with members only (a wire change), neighbours by party, and no token + from another node; the API putting events and showing what counts; reports of the + versions a node refused, its operator having it drop what it took, and a tool + reporting, from the votes, a party that voted twice. Until stage 5, a federated swarm + takes no remake: from stage 4 on, one that grows too large starts afresh by a fork + whose version names the same parties, keys and rules. +4. **Forks**: a store whose root is a checkpoint at another's heads, named by its root, + checked by the nodes holding that history. +5. **Remakes**: compaction only, the snapshot holding the store as it is at its base, + and every event beyond it put again. 6. **The registry**: the rules for krebs, the tool that signs kartei's entries in as their parties', after the root, and the one that reads them out. |
