# Federation: a design A design, built stage by stage (Stages): so far, the store it builds on, held in memory. It says how a swarm can be kept by parties that don't trust each other, for a first use: the krebs registry ([krebs/kartei](https://github.com/krebs/kartei)), today plain files in a git repository that one maintainer merges into. What it is for is narrow: to hand out identifiers (names, addresses, keys), and to give every party a namespace of its own that everyone reads. It asks as little as it can of continuum and promises the least that makes a federation possible. A federation that cooperates settles fast; one that doesn't comes apart, and whoever wants to carry on with whom does so. Claims about the code are marked *(checked)* where they were read in it. ## Optional A swarm is federated from its genesis change, or not at all (Starting a federation). Nothing else changes: a swarm that isn't stays as it is, its registry, rules, remakes and replay included. Which federation a swarm follows is a number of its own, in each version of its policy: this design is federation 1 (Changing the federation). Any group carries on with the policy it wants by forking (Forks), and leaves the federation by starting a swarm of another kind, with what it takes along. ## Parties and the adversary A **party** is a name in the policy, with its keys. Parties write, and parties vote: who isn't in the policy writes nothing, and comes in by a decision of those who are. Nobody owns the swarm, and any party may be malicious, alone or with others. A party is whoever holds its keys: several people may keep one party together, and one person may be in several, each with its vote. The parties decide whom they let in, groups included; nothing tells a group from a person. What an adversary can do: * run nodes, once a party lists them; * craft any event, with any dependencies, and any change, under any writer; * send different events and changes to different peers, send none, or pass on only some; * delay or drop messages between any nodes, short of forever between honest ones; * steal another party's key. What it can't: forge an Ed25519 signature, or find two byte strings with one SHA-256. Out of scope: keeping anything from being read (every party reads all of it), hiding who talks to whom, and a party's own machine taken over whole (then the adversary is that party). The design rules nothing about what happens on a party's own nodes, only that nothing coming from any node breaks a promise for the others. ## What is promised 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 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 part, and the parties fork (Changing the policy). 3. **Any group carries on as it chooses.** Its parties fork with the policy they want, and whoever wants to follow does; groups that parted come together as parties come in, one letting the other's in (Forks). Nobody is held by parties it doesn't follow. Not promised: * progress without the parties' cooperation: those who cooperate fork, and carry on; * that a party votes well; * that what a party's nodes withhold reaches anyone; * that the swarm stays fast, or up. A party that floods the store, or whose nodes start writers without end or keep remakes from committing ([`store.md`](store.md)), makes nodes slow, or runs them out of memory, not wrong: denial of service breaks no promise here, and the others fork away from it; * 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 what isn't above a checkpoint's heads is taken once nodes moved to it: its party signs it again (Checkpoints); * that a node joining from the root, in a federation that never passed a checkpoint, isn't shown a chain old keys grew: of two versions changing one it takes neither, but where its seeds are all the adversary's it is shown one (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)): 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: * **An event's history**, which its ID fixes: what its signer had seen. An event is judged at its history and nothing else. * **The state of a set of events**: the same on every node for the same set, whatever 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. * **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 heads of another store. * **Members**: the nodes that carry the store, which the federation names. ### Events An event is the JCS encoding (RFC 8785) of a JSON object, its bytes those of the JSON they read as, so that nothing in it is spelled two ways and no key is there twice. Spread out: ```json { "deps": ["", ""], "party": "tv", "key": "ssh-ed25519 AAAA…", "write": { "path": "names/r/tv/toaster", "value": "10.243.7.3" }, "sig": "" } ``` * **`deps`**: the IDs of its dependencies, as 64 lower-case hex digits, one at least, ascending, none twice; a client gives the heads it read. * **`party`** and **`key`**: the party that signs it, and the key it signs with: `ssh-ed25519`, one space, and the key's base64, padded and canonical, with no comment, its 32 bytes an Ed25519 public key. Keys in a version and a key set are spelled so too, and node IDs as continuum spells them: `continuum:` and the 64 lower-case hex digits of the node's Ed25519 public key. * **What it does**, one field of: * `write`, `{"path": "", "value": }`: a value at a place (The policy); * `keys`, `["", …]`: the party's key set (Keys); * `nodes`, `["", …]`: its node list (Nodes); * `proposal`, a version, the object (Changing the policy); * `vote`, `{"on": "", "proposal": "", "yes": true}`, `"yes"` `true` or `false` (Changing the policy): a version's hash, the SHA-256 of its JCS bytes, written as an ID is. * **`sig`**: an SSH signature (`ssh-keygen -Y sign`, namespace `continuum-federation`) over the event's bytes without `sig`: the SSHSIG blob of version 1, hashed with `sha512`, its key the event's `key`, its reserved field empty, as `ssh-keygen` writes it, in base64, padded and canonical, unarmored. It is checked as continuum checks a user's signature, strictly *(checked: `access::sshsig::verify_blob`)*, which takes `sha256` too, and any reserved field: the federation asks `sha512` and an empty one. 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, if its `key` or `sig` doesn't read back to itself spelled as above, or if it is larger than the federation allows. So nobody but its signer makes another event of what a party signed. Of an event, federation 1 allows: * up to 256 KiB, with up to 64 dependencies; * objects and arrays nested up to 32 deep, the event's own object the first; * a key set of up to 16 keys, and a node list of up to 64 nodes; * in a write, a path of up to 32 segments, each of up to 255 bytes; * anywhere in it, numbers that are integers from −2⁵³ to 2⁵³, and strings of whole Unicode characters, no surrogate alone. It names no swarm, no version and no ID of its own: its history says the first two. An event signed in a federation, or in a fork once it forked, has that store's root in its history, and no other store takes it ([`store.md`](store.md), Forks). An event is **written under** the version current at its history (Changing the policy). ### The policy What the policy says is in its **versions**, a chain: each is a JSON object, named by the SHA-256 of its JCS bytes, numbered, and naming the version it changes (`null` for the first, number 0, which only the federation's root holds; a fork's changes the one current at its heads, Forks). Spread out: ```json { "federation": 1, "number": 7, "changes": "", "keys": { "tv": { "since": 0, "keys": ["ssh-ed25519 AAAA…"] }, "lass": { "since": 4, "keys": ["ssh-ed25519 AAAA…"] }, "makefu": { "since": 7, "keys": ["ssh-ed25519 AAAA…"] } }, "nodes": { "tv": { "since": 0, "nodes": [""] }, "lass": { "since": 4, "nodes": [] }, "makefu": { "since": 7, "nodes": [] } }, "rules": [ { "path": "names/r/wiki", "writer": "lass" }, { "path": "home/{party}/**", "writer": "{party}" }, { "path": "names/r/{party}", "writer": "{party}" }, { "path": "names/r/{party}/**", "writer": "{party}" }, { "path": "ip4/10/243/7/*", "writer": "tv" }, { "path": "names/**", "writer": false } ] } ``` * **The federation** it follows, and its **number**, one more than that of the version it changes. * **The parties and their keys** (`keys`): one party at least, each by name, as continuum's user names, 1 to 64 of `A-Z a-z 0-9 . _ @ -`, with one `ssh-ed25519` key or more, none twice in the version. With them the party signs its votes and proposals on this version, its key set and its node list (Keys, Nodes). Its `since` is the number of the version that named them anew: this one's where it does (a party new in it, keys the parties replace, or the same keys named anew), else the `since` the version it changes gives the party, whose keys it then names unchanged. * **The node lists** (`nodes`): every party's, a list of node IDs, none twice, with its `since` as keys have one. The version that lets a party in names its list anew, empty where it 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, once in a rule at most: a segment naming none doesn't match, and a later rule decides), `*` (any one segment) or, last only, `**` (one segment or more). The writer is `"{party}"` (the party the path names, only where the rule's path holds `{party}`), a party of the version, or `false`: nobody. A path no rule matches, nobody writes. A **place** is a path a rule matches. A party writes there by a `write` event, `{"path": …, "value": …}`: any JSON value, `null` emptying the place. Its value is the latest its party signed there that counts (What counts). A place is a path, not a key in a tree: a version may give a place and places below it alike, and nothing is both a value and the way to others. How names and addresses are spelled as paths is the application's: the registry writes a name by its labels, last first (`names/r/tv/toaster` for `toaster.tv.r`, `names/r/tv` for `tv.r`), and an address by its parts, so that a party's zone or block takes a rule or two. Rules go by first match, so a party named like a shared name takes it where a `{party}` rule comes before it: the 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 (but for `checkpoint`, which it may leave out), if it gives a party more keys than a key set may hold or more nodes than a node list, or a rule a path longer than a write's may be, 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). ### Changing the policy A **proposal** is a version a party proposes, by a `proposal` event, the version itself, signed with one of the keys the version it is written under names for its party: the proposal is **on** that version, and its hash is the version's. It counts as signed by those keys, whatever keys the party writes since, until it lapses. A party **votes** on a proposal by a `vote` event, naming the version the proposal is on (`on`) and the proposal, by their hashes, and saying `true` or `false` (`yes`). * **A vote is taken only where, at its history, the version it is on is current and its proposal is proposed on it.** A vote cast at a history from before can't reach a proposal made since. * **A vote counts as cast**: signed with one of the keys its version names for its party, whatever keys the party writes since. So a vote is checked from itself and its version alone, by a client too, and nothing takes it back. A party's client keeps what its party voted, and votes by that, never by what a node shows. With each `true` it casts, it keeps the votes that made its party's earlier proposal on that version dead, so that, once a checkpoint left them out, nothing names its party as voting twice. A party votes from one client: two of its clients backing two proposals at once is voting twice, as two of its nodes each voting by itself is, or a vote by hand beside the node that votes for it (Votes a node casts by itself). * **A proposal passes** once at least two thirds of its version's parties voted `true` (3·yes ≥ 2·parties). It is **dead** once so many voted `false` that the rest can't pass it (3·(parties − no) < 2·parties). A party whose `true` and `false` on one proposal are both in a history counts for both there, so that a history holding more votes never takes back a pass or a death. * **One yes at a time.** A party's `true` is taken only if, at its history, every other proposal on that version it voted `true` for is dead. So a party backs one proposal, and is free again when that one can't pass any more. So a yes binds its party while its proposal can pass. Of nine parties, five back X, two prefer Y and two never vote: X needs one more and can't die, as that takes four nays. The five back nothing else on this version, and the others take X or fork. A proposal that could pass at one history and be taken back at another would let two versions be written without anyone voting twice. Once a proposal passed on the current version, a node writes it as soon as it holds it passed, by a **version** event, `{"deps": […], "version": }`, which no party signs: any node may write it, and the same version written by several is one (below). Every node judges it at its history: the proposal proposed there on the version current there, passed there, and a version changing that one. A version takes effect where it is written: it is current at every history that holds it and no version after it. **A node takes a version only where it changes the version the node reads**, or is one it took, written again. A version event of any other, valid at its history or not, it refuses, with everything built on it, reports, and leaves to its operator ([`store.md`](store.md), A node's own); another node's refusal doesn't make it drop what it took. One valid at its history breaks no rule: the node reports it apart from events against the rules, and holds nothing against the node that put it. Of two that change the one it reads, it takes the first it judges; a node still joining takes neither, and reports, until its operator names one. A node is still joining, for this, from its start or a rejoin until it has synced with every seed its operator named: continuum's lifecycle has it `Joining` only until its first sync, with one peer, which could be the adversary's alone. Without keys voting twice, every version written changes the one every node reads, or is one it took, and none is refused. **An operator may have its node drop what it took** after its checkpoint: a version the others refused, or any event, with everything built on it ([`store.md`](store.md), A node's own), and then take what the others hold. A version that moved the node to a checkpoint it undoes only by taking a checkpoint its operator pins, as the node forgot what the other side's version needs. No peer's word moves a node; its operator's does. The node refuses what it dropped, from whoever brings it, and any version event naming a version among it, whoever wrote it anew, and writes none itself, though it holds the votes that passed it, until its operator says otherwise. So either side of keys that voted twice may join the other without what parts them, and without a fork. **The current version** is the written version with the highest number: the end of the chain the node took. * **Votes that split pass nothing**, like a proposal that gets only nays: three for one proposal and three for another, of six. Nays end it: once a proposal is dead, its backers are free, and another proposal can pass on the same version. Parties that won't wait fork. * **Two versions changing one** are written only where keys voted twice: a party voting `true` and `false` on one proposal, each shown to some, or `true` on two; or the keys an earlier version named, for two thirds of its parties, passing another proposal on it at a history from before the version that followed: some party among them backed that one too (two shares of two thirds share a party). Each node keeps the version it took and refuses the other, so nodes holding the same events still read the same policy; the sides are apart, and a node that lagged behind, or joins, may be shown either first. The parties answer by forking, without the party that voted twice, or with its keys named anew (Forks). * **A party that voted twice shows** in the votes alone, both signed with keys their version names for it: its `true` and `false` on one proposal, or its `true` on two proposals of one version where neither is dead by all the votes cast. Where in history a vote is, and how often it was signed, changes none of it: a party's votes of one 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 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 keys where they lost them, and their node lists where they have none; who writes where, which is giving an identifier, taking it back and giving it to another; and the federation itself, by naming another (Changing the federation). ### Keys A party votes and proposes with the keys its version names for it, and signs with them its key set and its node list. Everything else it signs with the keys of its **key set**: a `keys` event, the list of its keys, none twice, signed with a key the version it is written under names for the party. A set is checked only where it is written, never by the keys of a set (What counts, 2). A party's keys are those of its set (What counts, 5) where the set is written under a version numbered at least the `since` its version gives the party's keys; otherwise, and while it has written none, those its version names. So once a version names a party's keys anew, no set written under an earlier version counts, and the party's next set does. Nothing is written for it: the version says it. * **A value counts only while the key that signed it is among its party's keys**, as above: votes, proposals, sets and node lists aside, which go by the keys their version names. A party changes its keys by itself: it writes a set with the new keys beside the old, signs again with a new one, at a history holding that set, what should stay, 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 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 party's. * **A party's own key change reaches its votes and proposals** once a version names its new keys. A party can keep the keys its version names apart, offline, and sign its values with a set of its own. ### What counts An event is judged at its history, by the version current there, as every node judges it ([`store.md`](store.md)). So a value its party wrote while it could write there is taken, even where a version written at the same time says otherwise. What **counts** is read by the version current in the store as a whole. These count no more, and nothing else does: 1. a write at a place its party may not write by the current version: the party is no longer one, the place went to another, a rule changed; and of a party that is no longer one, its key set and its node list; 2. a write signed by a key that isn't among its party's; and a key set or node list written under a version before the `since` its version gives it (Keys); 3. a proposal on a version that isn't current, and the votes on that version; 4. a version behind the current one; 5. of the writes at a place that 1 and 2 leave, one another of them has in its history, and of those left, all but the one with the lowest ID; and so of a party's key sets, and of its node lists. 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 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, version events aside, as it holds the version itself (What counts), as the JCS encoding of `{"at": [], "keeps": [], "version": }`, its IDs ascending and its version the version itself, the object, 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 event of it that comes later is one the node took. A version names a checkpoint by its heads (`checkpoint`): events after the current checkpoint, at which it is current too, none in another's history, their IDs ascending, one at least. The current checkpoint at a history is the one the last version of that history's chain that names one names, or else the root: a question of the history alone. As the version naming the current checkpoint is among the next checkpoint's heads or in their history, every later version naming one names heads after those, and a node starting from a checkpoint holds what judging them reads. A proposer names heads it has held for a while, by its own clock, which judges nothing, so that every node holds them. A party's client, and a node voting by itself, back a checkpoint only where everything they held for a while before it was proposed is among its heads, in their history, or above them: a move refuses what isn't above its heads, and heads a proposer made up, built on little, would take back what was written since, a key set dropping a stolen key among it. A node shows, for a proposed checkpoint, what it holds that its heads lack, as for a fork (Forks). This is the voter's rule, by its own clock: nothing more is judged. It is a version only where its proposal is above those heads, and a version event writing it is taken only where it is above them too, and so is every vote it is written on ([`store.md`](store.md), Events): so moving to the checkpoint refuses nothing that decided it. A vote beside them binds its party as any yes does, until the move refuses 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 starting from a checkpoint reads what it keeps as written under its version, as it holds none of their histories: each was written under that one or an earlier, counting there, a kept proposal is on it, and a later `since` that leaves one out is past it. A node that can't build a checkpoint, as it was away across a move and a remake after it, or as it joins, takes it only where its operator pins it ([`store.md`](store.md), Pinned checkpoints). What it can't check of its heads it takes on its operator's word: that they are after the checkpoint current at the version naming them, at which that one is current too; so it judges that version as every node does. 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. Few are: the heads are ones its proposer held for a while, no voter backs heads that leave out what it held for a while, nodes build on them while the vote takes its course, a client writing once a checkpoint is proposed builds only on what is above its heads, and a party's client signs again what a move refused. **Joining.** Once a checkpoint passed, a node joins from a checkpoint its operator pins, not from the root ([`store.md`](store.md), Pinned checkpoints). Whether one passed is its operator's to know, not the node's: a chain old keys grew need name none. From the root, keys a version named before it, revoked since or thrown away, could grow another chain, at histories before the version that followed, and node lists naming only their own nodes would seal a node joining in it, never shown the other. So a checkpoint bounds what old keys can do to the versions after it. 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 that can still pass 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). ### Votes a node casts by itself A party may have one of its nodes vote and propose for it, by rules its operator sets: the rules are written nowhere in the swarm, and every node judges what such a node signs as it judges any vote or proposal. The design has two in mind: * **Following**: back a proposal where a party the rule names backed it, and vote `false` where that party did; a proposal binds its proposer to nothing, so following one would bind the node where that party is free. By default it follows only on a version that only moves to a checkpoint (Checkpoints), a `true` as a `false`; its operator may have it follow on any version, which hands that party the node's vote, its `false` among it: a party followed so by more than a third of the parties, its key kept on a node, ends every proposal, the one naming that key anew among them. * **Proposing a checkpoint**: propose a version that only moves to a checkpoint, at heads the node has held for a while, once conditions its operator sets are met: so many events or bytes held beyond its checkpoint, so many versions since it, or so long by its own clock, by which nothing anyone judges goes. It proposes only where nothing that can still pass is proposed on the current version, as such a version lapses what is, but a proposal it wouldn't back that nobody backs but its proposer: so a party keeping one alive holds back no checkpoint. It backs what it proposes, so that the nodes following its party back it too. Such a node keeps to what a party's client keeps to: one yes at a time; never `true` and `false` on one proposal, so a party has one node vote by itself, as two of its nodes each voting by itself can vote twice; none for a proposal that is no version; and, by a rule for checkpoints, none for a version that changes more than its number, what it changes and its checkpoint, which it checks against the current one, nor for one whose heads leave out what it held for a while (Checkpoints). Where two checkpoints are proposed at once, the votes split, as any do; a rule may vote `false` on the one it doesn't back, so that one dies and its backers are free. It signs with a key the party's version names, which the party keeps on that node, not apart: one stolen there votes, and writes the party's key set and node list, as the party's, until a version names its keys anew (Keys). A party that won't keep one there votes by hand. A party that has a node vote by itself votes by hand only through that node, which keeps the party's one record of its votes and refuses a vote that record forbids: a party votes from one client, and that node is it. ### Nodes A party lists the nodes that carry for it, by node ID, in its **node list**: a `nodes` event, the list of its nodes' IDs, none twice, signed with a key the version it is written under names for the party. A party's list is that one (What counts, 5) where it is written under a version numbered at least the `since` its version gives the party's list, otherwise the list its version gives, if any, as with keys (Keys). The store's members are the nodes each party's list names, each as its party's ([`store.md`](store.md), Members); another party's list does nothing for a node. A party's list counts until the party writes another or a version names one anew, whatever keys its version names since, so that no change of keys leaves a swarm without members; a list a stolen key wrote stays until the party writes one under the version that replaced that key, which it can at once, through any member. A node puts whatever events it is given, its party's and others' alike: what counts is who signed an event, not which node put it. So a party without nodes of its own writes through any node that takes its events. ### Forks Any group can carry on without the rest: too many parties are away for good, a version 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, 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, and names anew the keys of any party whose keys it changes; a root whose version doesn't is no fork. Its founders name their own node lists anew in it, so that their nodes are members there. 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 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. 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 nothing there, and what it had counts no more; to come back, the fork's parties let it in by a version, as they would anyone new. A fork's version may name parties that weren't among the first to go (every party its founders consider honest, say), so that they can follow whenever they like, without asking. Groups that parted come together as any party comes in: one side lets the other side's parties in, by a version, or by a fork naming them, and they sign there again what they keep, as a party's client signs again what a move refused. What one side signed counts on the other only once it is signed there. What a party's nodes do of themselves is their operators' business, written nowhere: join a fork their operator follows, vote by rules their operator set (Votes a node casts by itself), or do nothing without their operator. So a federation that cooperates can have a group that leads without being named: the active parties the others follow. ### Shared identifiers Anything outside a party's namespace is shared: names, addresses, anything a rule names. Who writes one is what a rule says: by its own name (`names/r/{party}/**`: a party writes the names under its own), or given to one party by a version, and taken back and given to another the same way. Nothing is first come, first served. The value is what its writer signs there (`names/r/wiki`: where the name points); what a former writer signed counts no more once a version gives the place to another. Routine work needs no vote: a version gives a party a zone or a block by a rule (`ip4/10/243/7/*`), and a new host is a write where its party may write. Votes are for 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, 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, its policy naming the fold `federation` (`{"version": 2, "store": "federation"}`, [`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 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 proposal on a version at a time, and another only once the first is dead; its votes count as cast. So a proposal can't pass at one history and be dead at another unless some party's `true` and `false` for it are both there, and two proposals on one version pass only where some party backed both while neither was dead, or some party's `true` and `false` on one of them are both there. Without keys voting twice, at most one version changes a version, and every node takes it, however often it is 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, 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 What an attacker does, and what happens; what it does to the store, its document and its remakes, is the store's ([`store.md`](store.md), Attacks). *Unit*: the fold, with crafted events. *Sim*: a simulation. *Bench*: measured, not judged. | # | Attack | What happens | Test | |---|---|---|---| | 1 | An event signed by a key that isn't its party's, or by no party where one must sign | Refused at its history | unit | | 2 | An event not in its JCS bytes, a field missing or more, or larger than the federation allows | None: refused | unit | | 3 | An event of another federation, or of a fork once it forked, brought in | Never taken: its history lacks the root | unit | | 4 | An old write brought again | The same event: nothing changes | unit | | 5 | A former holder writes at a history where it held the place | Taken there; counts no more: the current version gives the place to another | unit | | 6 | A key set signed by a key the version doesn't name, or by one a later version replaced, at a history from before | Refused; or, written under a version before the one that named the party's keys anew, it counts no more | unit | | 7 | A key set without the key that signed it | Counts: a set is checked where it is written | unit | | 8 | A version event without the votes, or for a proposal not on the version current at its history | Refused at its history | unit | | 9 | A version with a field missing or more, a rule under `_continuum`, without a literal first segment, with `**` not last, `{party}` twice, or a writer that is no party of it | No version: can't pass; a version event naming it is refused | unit | | 10 | A proposal naming a federation, or saying what, a node doesn't know | Taken as a proposal; asked where a version event names it | unit | | 11 | `true` on two proposals of one version | The second refused, unless the first is dead at its history | unit | | 12 | `true` on two proposals at once, from two nodes | Both taken; two versions changing one may be written; each node keeps the one it took and refuses the other; reported; the parties fork | unit, every order | | 13 | `true` and `false` on one proposal at once | Both held; a node that saw only one may write a version. As 12 | unit, every order | | 14 | A vote cast at a history from before, on a proposal made since | Refused: its proposal isn't in its history | unit | | 15 | A party's vote signed again, at another history | One vote; voting twice is read from the votes alone, not from where they are in history | unit | | 16 | A party changes keys after voting or proposing, or beside its vote or proposal | It counts as cast, by its version's keys | unit | | 17 | Votes split, honestly or not | Nothing passes; nays make the proposals dead, and another passes | unit | | 18 | The parties beyond two thirds never vote, or vote `false` on everything | Nothing passes; the others fork | unit | | 19 | A node of the party a version takes out writes that version | Taken: a version counts by its votes, not by who wrote it | unit | | 20 | The keys an earlier version named, for two thirds of its parties, pass another proposal on it at a history from before, and raise its number | Refused by every node that took the version after it, and reported; a node that lagged may take it: keys voted twice | unit | | 21 | Two versions changing the one a node reads, coming together | It takes the first it judges, and refuses the other | unit | | 22 | Values signed with a key a party's set holds, stolen | Count until the party drops the key | unit | | 23 | A key a version names, stolen, votes, or writes its party's set or list | Counts while that version is current; the party's own vote beside it is voting twice, answered by a fork | unit | | 24 | A write in another party's namespace, at an identifier of another's, or where no rule matches, `null` included | Refused by the rule | unit | | 25 | A key its party dropped writes, at a history from before the drop, after what the party signed | Counts no more, and replaces nothing the party signed | unit | | 26 | Two writes of one party at one place, neither in the other's history | The lower ID is the value, until the party writes again after both | unit | | 27 | A party taken out signs events at a history where it was one | Taken there; they count no more | unit | | 28 | Different events to different peers | Honest nodes agree once they hold the same events, but where keys voted twice | sim | | 29 | A party withholding its events or votes | Not promised | — | | 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 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 | | 37 | Two founders forking one version at one set of heads, or starting a federation from one first version | One store: its root is built byte for byte | unit | | 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 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; but one naming a checkpoint, written again where it isn't above the checkpoint's heads, is not (54) | unit | | 45 | An honest node writes a version valid where it is written, on the side a node doesn't read | Refused, and reported apart; nothing is held against the node that put it | unit | | 46 | A party's `true` and `false` on one proposal, both in a history | Both count there: a history holding more votes takes back no pass and no death | unit | | 47 | A path whose `{party}` segment names no party (`names/r/foo`) | The `{party}` rule doesn't match; a later rule decides | unit | | 48 | Two thirds back a proposal that is no version | It can't be written, nor die; the federation is bound to its version. A node shows that it is none, and clients don't back it | unit | | 49 | Keys voting twice part honest nodes | An operator has its node drop what it took and take the other side's; no fork. Where the version it took named a checkpoint, by a checkpoint its operator pins | sim | | 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 version event writing it that isn't, written on a vote beside them, say | No version, or the version event refused: moving to a checkpoint refuses nothing that decided it | unit | | 54 | An event not above a checkpoint's heads (written beside them, built on one that was, or naming one before them), 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 | | 58 | A party a node follows backs, or votes `false` on, a version that changes more than its checkpoint | By default the node follows neither; one following on any version does, as its operator chose | unit | | 59 | Two checkpoints proposed at once, by nodes voting by themselves | The votes split; nays from the nodes backing one make the other dead, and its backers are free | sim | | 60 | Two nodes of one party, each voting by itself | They can vote twice, answered as any party voting twice: a party has one node vote by itself | — | | 61 | A key a version names, kept on a node that votes by itself, stolen with it | As 23: it counts while that version is current | unit | | 62 | A party's event spelled anew by another: its `sig` or `key` encoded otherwise, its signature's S not canonical, its blob naming another key | None: `key` and `sig` read back to themselves, the signature is checked strictly, and the blob's key is `key` | unit | | 63 | A node joining from the root is shown a chain old keys grew, beside the one the others took | It takes neither, and reports; once a checkpoint passed, it joins from a pinned one, where that chain is refused | unit | | 64 | Checkpoint heads before the current checkpoint, or at which it isn't current, or one in another's history | No version: a version event naming it is refused | unit | | 65 | After a checkpoint, a party that backed a second proposal once its first was dead, the nays that freed it withheld by those who cast them | Not named: its client keeps those nays with its `true` | unit | | 66 | Two clients of one party back two proposals at once, or its operator votes by hand beside the node that votes for it | Voting twice: a party votes from one client, the node that votes for it where it has one, through which it votes by hand | — | | 67 | A party keeps a proposal alive that nobody else backs, to hold back automatic checkpoints | Holds back none: a node proposes a checkpoint beside a proposal it wouldn't back that nobody backs but its proposer | sim | | 68 | A checkpoint proposed at heads that leave out what was written since: a key set dropping a stolen key, say | Not backed: clients and nodes back a checkpoint only where what they held for a while is among its heads, in their history, or above them; a node shows what they lack | unit | ## Roads not taken * **First come, first served, for identifiers.** Order between two parties that wrote at once can't be read from the store without trusting someone's clock or someone's witness. Votes need neither. * **Anything waiting on time** (final after so many days). Clocks are each node's own. Everything here waits on votes. * **Taking back what a stolen key signed, from history.** A thief makes its events look as old as it likes. Dropping the key takes all of them back (the party drops a key of its set, a version one it names), and the party signs again what was its own. * **One vote per version**, never to be cast again. It bounds what parties voting twice can do at a third of them, and leaves a split for good. With nays a split ends, and one party voting twice on a close vote can have two versions written; the votes show who, and the parties fork without it. * **A recount without a party that voted twice.** Its second vote can come at any time, at a history from before, and would undo a version long after it passed; and honest parties who backed one proposal, then another once the first was dead, would look as if they had voted twice. * **Every node moving to one of two versions changing one**, the lower hash, say. Whoever holds the keys an earlier version named, for two thirds of its parties, could put another policy on every node at any time, raising its number alone, and grind its hash. A node keeps the version it took, and the parties fork. * **The longest chain from the first version.** Old keys could still grow a chain longer than the one nodes took. * **A share each federation sets.** Two thirds is the federation's number's: another share is another federation (Changing the federation). * **Becoming federated in a running swarm.** It needs the time before closed, which continuum doesn't do for a swarm turned strict either, values from before counting only where a party signed them, and of two federating changes at once neither preferred, as a tie broken by hash would let a change made later to look as old take the place of the one every node took. A federation started from its own root needs none of it. * **Values in the document's tree**, each place's signed values in Automerge's maps, read by the version each names and its number there. Every reading the tree allows had to be answered (maps made on the way, values beside maps, deletions, the order of operations), and every remake had to keep each place's value; an event is read only as the federation reads it. * **Numbering a place's writes**, each naming the one it replaces. A write's history says what it replaces; numbers would be one more thing judged, and one to raise from a history where the writer still held the place. * **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. * **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 party's voting rules written in the swarm**, so that every node sees whom it follows. They are its operator's, as the fork its nodes follow is; in the swarm, a stolen key would rewrite them. * **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. * **Merges**: a fork at heads of several stores, keeping what counts on each side. Its version names every party's keys anew, so that a party writes its key set again before anything a key of its set signed counts; and a value a party replaced on one side comes back where the other side's write has the lower ID. Letting the other side's parties in, who sign again what they keep, does the same with nothing new. Nor merging in place, two stores each passing a version that moves them to one checkpoint: it needs a version that changes two, and nodes on each side taking the other side's part on someone's word. * **Forks within one store**, each side judging by its own chain of versions. It needs judging per chain, judging again when a node changes sides, and members per chain. A store of its own needs none of it. * **Leaving the federation by a version.** The closed registry, and the time during the federation, would be read again by the next policy. A swarm of another kind, with what its founders take along, starts clean. * **Users below the parties.** A party's people and keys within it are its own matter: it may hand out its keys as it likes. The federation sees parties. ## Changing the federation Every node of a swarm runs the same version of continuum today. A federated swarm's 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, 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 parties pass once their nodes run a continuum that knows it. A node that doesn't know the federation, or a version, its swarm has stops taking events and says so. ## The registry on it The krebs registry today: users, their hosts, the hosts' names, addresses and keys. On a federated swarm: * the krebs users who will vote are its parties, each its hosts in its namespace (`home/tv/hosts/laptop`: its keys, its addresses as it uses them). The others are in a party that is a group, which holds its keys as it likes, their hosts in its namespace, until a version makes one a party of its own. Every decision takes two thirds of all parties, quiet ones counted, so the first version names only those that will vote; * a party's names `names/r/tv` and those under it by a rule each, and so for `names/w`; its address blocks by a rule each; other names given by versions; * kartei's entries signed in by their parties after the root, never as anything before it; * a tool reads what counts and writes what kartei's consumers read today. ## Stages Everything here, and the store, is built behind the `federation` feature: without it, 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, 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, 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 ([`federation-tests.md`](federation-tests.md)). 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, 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; a party's client, signing events, keeping its votes and the nays that freed it, and signing again what a move refused; reports of the versions a node refused, its operator having it drop what it took, a tool reporting, from the votes, a party that voted twice; votes a node casts by itself, by its operator's rules. 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. A federated swarm made before the last stage is for tests: a later stage judges it otherwise.