diff options
| -rw-r--r-- | docs/federation.md | 1044 |
1 files changed, 409 insertions, 635 deletions
diff --git a/docs/federation.md b/docs/federation.md index 1cf0e76..63b4632 100644 --- a/docs/federation.md +++ b/docs/federation.md @@ -1,31 +1,31 @@ # Federation: a design -A design, not what the code does: none of this is built. 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. +A design, not what the code does: none of this is built. 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. +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). A swarm -leaves the federation as any group carries on: by forking, with the policy it wants -(Forks). +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 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, @@ -34,29 +34,28 @@ groups included; nothing tells a group from a person. What an adversary can do: * run nodes, once a party lists them; -* craft any change: under any writer, with any dependencies, any operations; -* send different changes to different peers, send none, or pass on only some; +* 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 changes with one hash. +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. +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 that holds the swarm from its genesis change, or - followed every remake since, building each itself, refuses what the version current - at a change's history doesn't let be written, whoever sends it, and reads nothing - else as counting. -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 changes 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). + 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. +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. Nobody is held by parties it doesn't follow. @@ -65,74 +64,75 @@ 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 document, whose nodes keep - remakes from committing, or whose nodes start writers without end (Where Automerge - sets limits), 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 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 honest nodes stay together where a node commits two changes under one writer - and number: they are apart until operators have one side drop what it took, or a - fork (Where Automerge sets limits); -* that a remake reaches every node: one that can't build it itself, or isn't to follow - it (Remakes), stays where it is; - nor that nodes follow one remake where two were decided for one epoch: each follows - the one it holds, until operators name one (Remakes); -* that a node taken off its party's list can't still commit at a history from before: - from a remake whose base holds that list on, it can't, and no node follows a remake it - coordinates; -* anything to a node with an empty document: it takes the epoch its peers give it, or - the one its operator pins (Remakes). +* that the store stays small: it keeps every event, and a fork its whole history. ## The design -It builds on values signed by their users ([`access.md`](access.md)): continuum's -signed value, `cv2.<value>.<meta>.<signature>`, read the one way every part of -continuum reads it *(checked: `document::signed`)*. The meta names the swarm, the path, -who signed, when, the envelope it replaces (`prev`) and its number there (`seq`, one -more than that one's). A federated swarm's value is an envelope its party signs, the -same with a prefix of its own, `cv3.<value>.<meta>.<signature>`, whose meta names also -the **version** of the policy current where it was written, by number (`version`, The -policy). A swarm that isn't federated reads a `cv3.` string as the string it is. +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. -A change writing an envelope that names another version than the one current at its -history is refused, but for an epoch's first change (a remake's snapshot, a fork's -genesis), which is judged by none. Of the envelopes a place holds, written at once, its -value is the one with the highest version number, then the highest `seq`, then the lower -SHA-256, among those signed by a key their party holds (Keys); where none is, nothing -there counts. Judging a change goes by all of them, as they stand: its `prev` names the -first of all, whoever signed it, so a party's first envelope where another's is (a place -given to it, an envelope a dropped key wrote) names that one, its `seq` one more. So -what a place holds is its party's to say, never the order of operations, which whoever -writes a change steers, nor a key the party dropped; and what was signed under a later -version is ahead of anything written at a history from before it. +What it asks of the store: -A swarm under a strict policy reads by `seq` alone, the same way, and replays a value -its user signed as the chain of envelopes that leads to it *(checked: -`document::store::candidates`, `remake::delta`)*; the version number is the -federation's. +* **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. +* **Forks**: a store whose root builds on another's events, carrying their history. +* **Members**: the nodes that carry the store, which the federation names. -### What it asks of the document +### Events -* **A change's history**, fixed by the change's hash: what its writer had seen. A - change is judged at its history and nothing else. -* **The document at a set of changes**: the tree its writes make, the same on every - node for the same set. A deletion removes what its writer saw, and nothing written - at the same time. -* **Remakes a node builds itself**: whatever continuum does to start the document - anew, a node follows it only where it built the new document itself, from a base it - holds (Remakes). +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: -Continuum's document is an Automerge document, which gives all of this and has limits -worth knowing (Where Automerge sets limits). +```json +{ "deps": ["<ID>", "<ID>"], + "party": "tv", "key": "ssh-ed25519 AAAA…", + "write": { "path": "names/r/tv/toaster", "value": "10.243.7.3" }, + "sig": "<signature>" } +``` + +* **`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, an + `ssh-ed25519` key without its comment. +* **What it does**, one of: `write`, a value at a place (The policy); `keys`, the + party's key set (Keys); `nodes`, its node list (Nodes); `proposal` and `vote` + (Changing the policy). +* **`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). + +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 +what a sync message carries. 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 -A federated swarm's `_continuum/access/policy` is `{"version": 2, "federated": true}`. -What the policy says is in its **versions**, a chain: each is a string of JSON, named by -the SHA-256 of its bytes, numbered, and naming the version it changes (`null` for the -first, number 0, which only the genesis change writes; a fork's first changes the one +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 @@ -165,105 +165,62 @@ current at its heads, Forks). Spread out: * **The node lists** (`nodes`): every party's, a list of node IDs 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 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); none is - `@`. A rule matches a path key by key: a key holding `/` is one segment, which only - `*` and `**` match. 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. Its value is the envelope in its `@` key -(`names/r/tv/toaster/@`). An envelope goes only in an `@` key, an `@` key never holds a -map, and a change writes nothing else where rules say who writes but the maps on the way -to the `@` keys it writes, each only where none is, never deleting or replacing one: so -no key is both a value and the way to places, whatever the rules of any version say, a -version may give a place and places below it alike, no map is left empty, and no change -plants keys in another's namespace. Nothing is written within a list. 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). + later version may name it anew again; the first version and a fork's name those of the + parties that start it (Nodes). +* **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 version is none if its bytes aren't the JCS encoding (RFC 8785) of the JSON they read -as, so that nothing in it is spelled two ways and no key is there twice; if a field is -missing or more; if its bytes don't hash to its place; or if it breaks any of the above. -It can't pass, and a change writing it as a version is refused. A proposal is taken -whatever its text, but for its hash, which must be its place's: its party and version -are read from its place and its envelope, and whether it is a version is asked where it -is written as one, 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 **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). -The federation's own paths are its number's, not the rules': the same in every -version. They hold their values directly, and never nest; a change makes the maps on -the way to what it writes there as it does to `@` keys. +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). -| Where | What | Who writes it | -|---|---|---| -| `_continuum/federation/versions/<hash>` | a version that passed | any member, once it passed | -| `_continuum/federation/proposals/<party>/<hash>` | a version proposed | that party | -| `_continuum/federation/votes/<party>/<version>/<proposal>` | `true` or `false` | that party | -| `_continuum/federation/keys/<party>` | its keys | that party, by a key its version names | -| `_continuum/federation/nodes/<party>` | its nodes' IDs | that party, by a key its version names | - -What a party writes is an envelope, signed by one of its keys. A version is written as -its text, a plain string, and counts by the votes it had. A proposal's place takes only -the proposal. - -A federated swarm has no user registry, and of `_continuum` takes only these writes: - -* at `_continuum/federation`, as the table says; -* by a member: its own entry, its own acks, a remake's record and proposal; by a - remake's coordinator only: its decision, or its abort; -* by an epoch's first change (the genesis change, a remake's snapshot): epochs and the - swarm's ID. - -Everything else is closed, a write at, within or above it refused: users, bans, logouts, -sessions, forgotten nodes, `_continuum/access` with the policy's place, the swarm's -topology (`neighbours`, `relays`, `topology`, `dissemination`), and whatever a later -continuum adds. The topology is continuum's own, as the genesis change writes none; each -node picks its own relays, and some of its neighbours by party (Nodes). Nothing but the -policy is read of the rest. A member's change carries its node's signature, as -signatures are required in a strict swarm. A party logs in to each of its nodes as its -operator sets up, and a node takes no token another node issued: a list naming a node as -its party's, which a version or a key the version names writes, opens nothing on the -party's own nodes. Whoever a node lets in through its API may have it commit what the -rules take: envelopes, whoever signed them, and the node's own protocol data; -`--protocol-writers` names nobody in a federated swarm. +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 writes at -`_continuum/federation/proposals/<party>/<hash>`, its hash the version's, signed with -one of the keys the version it changes names for its party; it is on the version its -envelope names, the one current at its history. It counts as written by those keys, -whatever keys the party writes since, until it lapses. +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 writing `true` or `false` at -`_continuum/federation/votes/<party>/<version>/<proposal>`: the version the proposal -is on, and the proposal, by their hashes. No vote there is no vote. +A party **votes** on a proposal by a `vote` event, +`{"on": <hash>, "proposal": <hash>, "yes": true}` or `"yes": false`: the version the +proposal is on, and the proposal, by their hashes. -* **A vote is taken only where, at its history, its version is current and its - proposal is written.** A vote cast at a history from before can't reach a proposal - made since. -* **A vote never changes**, and **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, after a remake left it - out. Nobody deletes it, and a write at a vote's place is refused. A party's client - keeps what its party voted, and votes by that, never by what a node shows. +* **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. * **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, whatever its vote's place reads - as, so that a history holding more votes never takes back a pass or a death. + 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. @@ -275,63 +232,58 @@ that could pass at one history and be taken back at another would let two versio written without anyone voting twice. Once a proposal passed on the current version, a node writes it as soon as it holds it -passed, at `_continuum/federation/versions/<hash>`: any member may, and the same version -written by several is one (below). Every node judges that change by its history: the -proposal written there, on the version the text changes, its votes there, and that -version current. A version takes effect when it is written, and judges every change in -sight of it. +passed, by a **version** event, `{"deps": […], "version": <hash>}`, 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 change writing any other, valid at its history or not, it -refuses, with everything built on it, reports, and leaves to its operator; another -node's refusal doesn't make it drop what it took. One valid at its history breaks no -rule: its committer isn't refused as a whole, as a member whose own change broke a rule -is ([`access.md`](access.md)), and the node reports it apart from changes against the -rules. Of two that change the one it reads, it takes the first it judges. Without keys -voting twice, every version written changes the one every node reads, or is one it took, -and none is refused. +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. 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**: a version the others refused, or -any change, with everything built on it, as continuum drops a change its node took and -the swarm's rules refuse (`drop_taken`: the document as it would be without them, the -node's own writes among them to its quarantine), and then take what the others hold. No -peer's word moves a node; its operator's does. In that epoch the node refuses the -changes it dropped, from whoever brings them, and any change writing a version among -them, 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, -or of a writer forked, may join the other without what parts them, and without a fork. +any event, with everything built on it ([`store.md`](store.md), A node's own), and then +take what the others hold. 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, read from what the document holds without the versions behind it, -which a remake leaves out (Remakes). +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 changes 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). +* **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 a vote was - committed, and how often, changes none of it, and two envelopes of one value at one - vote's place 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 remake 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. + 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 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. +* **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, @@ -341,121 +293,99 @@ 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 its keys at -`_continuum/federation/keys/<party>`: one envelope, the set, signed with a key the -version current at its history names for the party, numbered as any envelope. A set is -checked only where it is written, never by the keys of a set (What counts, 2). +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, 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 where the set names 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 naming an -earlier version counts, and the party's next set, naming that version, does. Nothing is -written for it: the version says it. +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, signs - again with one of them what should stay (a change is judged at its history, where only - the set it replaces is the party's), writes a set without the old ones, and signs - again after it what should stay (a client does it all). What a key it dropped signed - counts no more; what that key writes at a history from before the drop can't name what - the party signed after it as replaced, and counts no more either, so it takes nothing - out. A key added back, from a backup say, brings back what it signed where it is still - there. + 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. * **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 before it counts any more. What the party then - signs names that version, and is ahead of anything the old key writes at a history - from before it. Until then, the old key votes, and writes the party's set and node - list, as the party's. + 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 -A change is judged at its history, by the version current there, as every node judges -it ([`access.md`](access.md), Changes judged on every node). 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 document as a -whole. These count no more, and nothing else does: +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 value at a place its party may not write by the current version: the party is no +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 value signed by a key that isn't among its party's, votes, proposals, key sets - and node lists aside, which go by the keys their version names; and a key set or - node list naming a version before the `since` its version gives it (Keys); +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. an envelope behind another at its place, of those 2 leaves; -6. the member entry of a node its own party doesn't list (Nodes). +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. -Nothing is deleted within an epoch but by a party at its own place, writing `null`. -Automerge keeps every operation, so a deletion shrinks nothing: only a remake shrinks -the document. What counts no more stays until a remake's snapshot or a fork's genesis -leaves it out. Either holds each place's value alone, so an envelope that isn't it goes, -whatever version it names; of the rest, it leaves out what counts no more where it is or -names a version before the one current there, and member entries that count no more -(Remakes). Until then, 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. +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 +with the lower ID; the party writes again, after both, to choose. ### Nodes -A party lists the nodes that carry for it, by node ID, at -`_continuum/federation/nodes/<party>`: one envelope, signed with a key its version -names. A party's list is that one where it names 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). A node's party is its operator's, in its configuration, and its own -member entry names it. A node is a member while that party lists it: it registers, -commits changes and syncs, and nodes sync with members only (Stages). Another party's -list does nothing. 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 commits whatever envelopes it is given, its party's and others' alike: what counts -is who signed a value, not which node committed it. So a party without nodes of its own -writes through any node that takes its envelopes. - -A node keeps some of its neighbours among its own party's nodes and those of the -parties its operator names, so that a party listing many nodes can't be every node's -neighbours. A federated swarm has no swarm key: a secret its parties share keeps out -nobody, and the node lists say who syncs. +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, 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, the parties can't agree, or it leaves the federation. It -**forks**: it starts a swarm of its own from the document. +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 starts the new swarm. Its genesis change holds what the old document - read as at heads it names, each place's value as the federation reads it (The - design), built byte for byte from the fork's first version and those heads alone, - with the swarm's Automerge version: its writer from the fork's name, time 0, no - message; so one version and one set of heads make one swarm, and a node with an empty - document takes it on its peers' word, as it takes an epoch. It holds all of it but - for what a snapshot leaves out, by the version current at those heads (Remakes), the - federation's versions, and continuum's own data (member entries, remake records and - acks, earlier epochs' metadata, the swarm's name): of versions, only the group's own, - the fork's first. It names the highest version at those heads as the one it changes, - is numbered one past it, and names anew the node lists of the parties that start it, - and the keys of any party whose keys it changes; judged by none, as an epoch's first - change is. Every proposal is a chance to fork: the version is usually one that didn't - pass. To leave the federation, the genesis holds another policy instead, and what it - needs. -2. A fork is named by the hash of its first version together with the heads it names, - which nobody can steer to a given name, the old swarm's least of all: its genesis - change writes it at `_continuum/swarm`, as every node checks, and an envelope's meta - names it. The genesis change holds envelopes as the old document read them, and they - count, whatever swarm they name; beyond them, nothing signed for one swarm is taken - in another. -3. The others join it as a node joins any swarm, by its genesis change's hash. A node - that holds the old document takes it only where it holds the heads' history, syncing - what it lacks from the old swarm, each change judged there; otherwise it says it - can't check, and leaves it to its operator. It checks the new one against the old - first, the same at those heads but for what step 1 leaves out; says what it holds - that those heads lack; and says, 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. +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. +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 + 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. 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 @@ -466,153 +396,45 @@ they can follow whenever they like, without asking. What a party's nodes do of themselves is their operators' business, written nowhere: join a fork their operator follows, vote as parties their operator follows voted, vote -by bounds their operator set, or do nothing without their operator. So a federation -that cooperates can have a group that leads without being named: the active parties the +by bounds their operator set, 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. +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. +(`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 swarm of its own: its genesis change, the swarm's first, -holds the federated policy, the swarm's name and the first version, and nothing else; -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. It -is built byte for byte from the first version alone, as a fork's genesis is from its -version and heads (Forks): its writer from the swarm's name, time 0, no message; and the -swarm is named by the first version's hash, so one first version makes one swarm, and a -node joining builds the genesis change and checks it. A swarm strict from its start -records its policy in its genesis change too (`--bootstrap-policy`) *(checked: -`swarm::bootstrap`)*, which starts it empty: content before it would be a change from -before the federation, judged by none. So nothing is from before the federation, and -nothing writes the policy's place after the genesis change: the federation changes by -versions, and is left by a fork. A running swarm doesn't become federated; its parties -start one, and sign into it, after the genesis change, what they keep. - -### Remakes - -A remake starts the document anew, for Automerge's sake only (Where Automerge sets -limits); the federation needs none and asks for none. When to remake, and who acks, is -continuum's as in every swarm: acks tell an honest coordinator when to commit, so that -fewer nodes are away, and a node follows a decision without counting them. They bind -nobody: a member may ack another remake of its epoch without the first aborted, and an -honest coordinator decides only while the acks it counts are still for its remake. A -federated swarm takes compaction only, whose snapshot is a function of its base and its -record (its ID, its coordinator): two remakes at one base are two epochs. What a -federated node asks of a remake: - -* **It builds it itself.** A node that holds an epoch leaves it only for one whose - snapshot it built itself, as continuum's node builds a compaction's and checks it - against the committed epoch *(checked: `remake::switch`)*, from a base it holds, where - it is a member (its party lists it there) and the version it reads is written, as it - reads it when it switches: a version it takes while it builds leaves it where it is, - as one taken before. Never on its peers' word, however it hears of the new epoch: a - node that lacks some of the base (it was away) syncs it from peers that keep the old - epoch, each change judged there, and builds then; where it can't build it, it stays - where it is, says so, and never rejoins an epoch it refused. A remake's decision is - its coordinator's alone, and so is its abort: whether one expired is no node's to say, - and one its coordinator leaves undecided binds nobody. A node follows a decision only - where the coordinator's party lists the coordinator, as the node reads it when it - switches. How long a node keeps the old document is its own setting, not the remake's, - and while it keeps it, it syncs it with nodes still on that epoch. -* **Two decisions for one epoch** come from a coordinator that wrote two, or from - remakes decided at once; a decision whose coordinator its party doesn't list, as the - node reads it, is none of them. A node that holds both follows neither, says so, and - leaves it to its operator. On its operator's word, a node builds the remake named of - the epoch before its own, from the old document it keeps, as it builds any, and - switches, what it wrote since replayed: so nodes that followed different decisions - come together where their operators choose. -* **The snapshot** holds what the old document read as at the base, each place's value - as the federation reads it (The design), not the first of all its envelopes as - continuum's merged view has it, but for what counts no more by the version current - there and is or names a version before it, a party's `null` naming a version before - it, and the member entry of a node its party doesn't list there: nothing naming an - earlier version can be written in the new epoch, an empty place reads as one holding - `null` does, and a node listed again registers again. -* **Writes after the base** are replayed as the policy shapes them: at each place, the - chain of envelopes that leads from what the new document holds there to the old one's - value there, as the federation reads it, each in a change of its own, judged again in - the new epoch, the other writes with them, each after those its change builds on, - clocks only between changes neither of which saw the other, as continuum replays under - a strict policy *(checked: `remake::delta`)*. No version is among them: a node that - took one written after the base doesn't switch, so what it replays names the version - current at the base, or one before. Votes and proposals go by the keys their version - names, which the snapshot holds, so they count as cast in the new epoch too, whatever - key sets of their party are replayed around them. Whether a place is held already goes - by version number, then `seq`. What the new epoch refuses is tried again once the rest - is replayed, as the clocks may have put it before what it builds on (a vote committed - again at another history, before the nays that freed its party); what it refuses then - (its key was dropped, its place given to another) goes to the quarantine of the node - that holds it, and its party signs it again if it still may. - -So a remake decides nothing that counts, but what it can't hold: of two envelopes of one -version and `seq` at a place at the base, the snapshot keeps one, and a write after the -base on the other, a write after it on what the snapshot left out, or an envelope -written after it at a history where a version before the base's was current (its node -lagged), goes to the quarantine, and its party writes again. A swarm that never remakes -stays as correct as one that remakes all the time; it only grows. A remake does end one -thing: nothing is written at a history from before its base, so what a node taken off -its list before the base could still commit there ends with it. - -A remake that races a version or a listing leaves the nodes that took the version, or -were listed since the base, where they are, apart from those that switched, until their -operators move them or a fork. An operator moves a node that took a version by having it -drop that version (Changing the policy): the base then holds the version it reads, so it -switches, and the new epoch writes the version again from the votes replayed, as a node -writes any it holds passed. A node with an empty document can't check: it takes the -epoch its peers give it, or the one its operator pins. - -### Where Automerge sets limits - -* **Bytes.** The nodes of a federated swarm run one Automerge version, which its - federation's number names (Changing the federation): a rule, as two versions that - encode a change differently refuse each other's changes. -* **Changes it shouldn't apply.** A change is first of all one Automerge itself - writes, or it is refused before Automerge sees it, in every swarm *(checked: - `document::changes::Written`)*. - -The rest are recommendations: none breaks a promise, only how fast a node is, whether -it stays up, or how long nodes stay together. - -* **Writers.** Every writer costs every node memory while the epoch lasts, in - proportion to the document's history *(measured: about 4 bytes per change)*. A node - writes under a fresh writer each time it starts, rejoins or drops. A federated swarm - remakes before its writers and history make that felt, and a node keeps its writer - over a clean restart where it can. Nothing bounds the writers a node starts: one that - starts one with every change, by fault or on purpose, runs the others out of memory. - Its writers name it, and its entry its party; a remake leaves an epoch's writers - behind, and the others fork without the party. -* **One change a number.** A node that commits two changes under one writer and number - splits the nodes that took one from those that took the other: a node holding one - can't take the other. Continuum refuses the second as forged, by whoever brings it - *(checked: `Signatures::forks`)*. No remake brings the two sides together, as neither - builds from a base holding what it refused; an operator having its node drop the - change it took, and take the other, does (Changing the policy), and so does a fork at - heads both hold. -* **History.** The document keeps every operation, which only remakes bound. +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. ## Why it holds -1. **What counts.** A change is judged at its history, which its hash fixes, by the - version current there, which the versions written in that history fix, each judged by - the votes in its own. Every node judges alike, and refuses the change and everything - built on it. What counts is read from what the document holds: the current version, - the highest number; each party's keys, by that version and its set; each place's - value, among the envelopes their party's keys signed, by version number, then `seq`. - None of it depends on the order of operations, and no key is both a value and the way - to places. A copy of an older envelope is behind; a new one written at a history from - before a version is behind what is written under it. +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. 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 @@ -623,171 +445,128 @@ it stays up, or how long nodes stay together. 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 changes still + With them, each node keeps the version it took, nodes holding the same events still read the same policy, and the parties fork. -3. **Remakes.** A node follows a remake only where it built the snapshot itself, from a - base it holds, a member there, the version it reads written there, its coordinator - listed; its peers' word never moves it. What came after, under that version, is - replayed in history's order, each change judged as every node judges it: votes and - proposals by the keys their version names; envelopes as chains, from what the - snapshot holds, by version, then `seq`. So what counted, counts, but what a remake - can't hold (Remakes), each of which its party writes again. -4. **Carrying on.** A fork is a swarm of its own, named by its first version and the - heads it names, 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, 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. ## Attacks -What an attacker does, and what happens. *Unit*: the judging, with crafted changes. -*Sim*: a simulation. *Bench*: measured, not judged. +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 envelope signed by a key that isn't its party's, or by no party | Refused at its history | unit | -| 2 | An envelope for another path, swarm or version | Refused: its meta names all three | unit | -| 3 | An older envelope written where a newer one is | Refused: `prev`, `seq` | unit | -| 4 | An older envelope put beside the newer by a change that saw neither | Taken, and behind | unit | -| 5 | A former holder writes a chain at a history where it held the place | Behind what is written under the version that gave the place away | 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, naming a version before the one that named the party's keys anew, it counts no more | unit | +| 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 written without the votes, or not changing the current one at its history | Refused at its history | unit | -| 9 | A version not in its JCS bytes, 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, refused where written as one | unit | -| 10 | A proposal naming a federation, or saying what, a node doesn't know | Taken as a proposal; asked where it is written as a version | 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 changed or deleted | Refused | unit | -| 15 | A vote cast at a history from before, on a proposal made since | Refused: its proposal isn't written there | unit | -| 16 | A party's vote committed again at another history | One vote; voting twice is read from the votes alone, not from where they were committed | unit | -| 17 | A party changes keys after voting or proposing, or beside its vote or proposal | It counts as cast, by its version's keys, at a remake too | unit | -| 18 | Votes split, honestly or not | Nothing passes; nays make the proposals dead, and another passes | unit | -| 19 | The parties beyond two thirds never vote, or vote `false` on everything | Nothing passes; the others fork | sim | -| 20 | The party a version takes out writes that version itself | Written: a version counts by its votes, not its writer | unit | -| 21 | 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 | -| 22 | Two versions changing the one a node reads, coming together | It takes the first it judges, and refuses the other | unit | -| 23 | Values signed with a key a party's set holds, stolen | Count until the party drops the key | unit | -| 24 | 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 | -| 25 | A write in another party's namespace, or at an identifier of another's | Refused by the rule | unit | -| 26 | A deletion of a value of another party, or of what counts no more | Refused: only a party's `null`, at its own place | unit | -| 27 | An envelope outside an `@` key, a map in one, or a map on the way to one deleted or replaced | Refused | unit | -| 28 | An envelope and a map at one key, written at once | None: envelopes go only in `@` keys, which hold no maps | unit | -| 29 | A remake whose snapshot isn't the one a node builds, whose base it lacks and no peer keeps, or where it isn't a member | It stays, and never rejoins it | sim | -| 30 | A coordinator records an old base, before the version nodes read | They stay | sim | -| 31 | Two members advertise an epoch ahead, or offer a rejoin | Not taken: a node leaves its epoch only for one it built | sim | -| 32 | A remake's decision or abort written by a node not its coordinator | Refused | unit | -| 33 | Two envelopes at one place beyond a remake's base | The chain to the one read is replayed | unit | -| 34 | A version taken while a node builds a remake's snapshot | It stays, as with one taken before | sim | -| 35 | Two envelopes of one version and `seq` at a base, a write after it on the one not kept | Quarantined; its party writes again | unit | -| 36 | A write after a base on what the snapshot left out, or naming a version before the base's | Quarantined; its party writes again | unit | -| 37 | A node with an empty document handed a made-up epoch | Taken. Not promised | sim | -| 38 | A coordinator remakes often, or a party never acks | Slow, not wrong; the others fork | sim | -| 39 | A writer forked: two changes, one number | Honest nodes split until operators have one side drop what it took, or a fork. Not promised | sim | -| 40 | Different changes to different peers | Honest nodes agree once they sync, but where keys voted twice, a coordinator decided two remakes for one epoch, or a writer forked | sim | -| 41 | A party withholding its changes or votes | Not promised | — | -| 42 | Flooding: namespace, proposals, history, writers | Slow, or out of memory; not wrong: a remake leaves the writers behind, and the others fork | bench | -| 43 | A node taken off its list writes changes at a history where it was on | Taken where valid there; ended by a remake whose base holds that list | unit | -| 44 | A token from another node, even one its party lists | Refused: a node takes only its own | unit | -| 45 | A party lists another party's nodes, or one its party dropped | Nothing changes: a node is its own party's | unit | -| 46 | A party lists many nodes, to be every node's neighbours | Each node keeps some among its own party's and those its operator names | sim | -| 47 | A party's node writing another node's member entry | Refused: an entry is its member's | unit | -| 48 | A party's node writing under `_continuum` where the list doesn't say | Refused: closed | unit | -| 49 | Envelopes the stayers sign after a fork, brought to the fork | Refused: signed for the other swarm | unit | -| 50 | A fork whose genesis change differs from the document it names | Nodes holding that document don't join, and say what differs | sim | -| 51 | A fork at heads of its founder's choosing | Joiners holding the document are told what those heads lack | sim | -| 52 | A fork's version giving a party that didn't go keys of its founder's | Joiners holding the document are told, party by party | sim | -| 53 | Two founders forking one version at one set of heads | One swarm: the genesis change is built byte for byte | sim | -| 54 | A group whose parties list no nodes forks | Its version names their node lists | sim | -| 55 | A federation, or a policy, a node doesn't know | It stops taking changes | unit | -| 56 | Two parties each writing a key set beside the other's vote, crossed | Nothing: votes go by their version's keys, at a remake too | unit | -| 57 | Content written before a federation's genesis change, and a change built on it | None: the genesis change is the swarm's first | unit | -| 58 | A federation's genesis change whose first version lists no node | Nothing after it is taken: no node is a member | unit | -| 59 | A version replacing every listed party's keys | The lists still count, each its party's until it writes another | unit | -| 60 | 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: refused written as one | unit | -| 61 | A version written again late, at a history from before the next, by a member that was away | Taken: it is one every node took | unit | -| 62 | A proposal whose text doesn't hash to its place | Refused | unit | -| 63 | An honest member writes a version valid where it is written, on the side a node doesn't read | Refused, and reported apart; its committer isn't refused as a whole | unit | -| 64 | Nodes reinstalled under new IDs, their old entries left behind | Each counts no more, and the next snapshot leaves it out | unit | -| 65 | A fork at heads holding a change sent to nobody (a version written without votes, say) | A node holding the old document takes the fork only where it holds the heads' history, each change judged | sim | -| 66 | A node away while the others switch | It syncs the rest of the base from a peer that keeps the old epoch, builds, and switches; it stays where none keeps it | sim | -| 67 | A key its party dropped writes, from a history before the drop, ahead of what the party signed | Counts no more, and takes out nothing the party signed again after the drop | unit | -| 68 | A coordinator shows one of two decisions for an epoch to some nodes, the other to the rest | Each follows the one it holds; a node holding both follows neither; their operators bring them together | sim | -| 69 | 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 | -| 70 | A path whose `{party}` segment names no party (`names/r/foo`) | The `{party}` rule doesn't match; a later rule decides | unit | -| 71 | A map made where no `@` key is written below it, or where one is (hiding what it holds) | Refused | unit | -| 72 | A party's first envelope at a place another's envelope holds | Names that one as `prev`, its `seq` one more; anew, refused | unit | -| 73 | A federation's genesis change holding more than its first version gives (values, votes, a topology) | A node joining builds it and doesn't join one that differs | sim | -| 74 | Two federations started under one swarm name | None: a federation is named by its first version's hash | unit | -| 75 | A version, set, list, path or value larger than the federation allows | Refused; none can be too large for a sync message | unit | -| 76 | 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 | -| 77 | A party's vote committed again at a history before the nays that freed it, its clock set between, then a remake | The replay refuses it at first, and takes it once the rest is in | unit | -| 78 | Keys voting twice, or a writer forked, part honest nodes | An operator has its node drop what it took and take the other side's; no fork | sim | -| 79 | 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 | -| 80 | A node whose operator had it drop a version is sent it again, written anew by another member, or holds the votes that passed it | It refuses any change writing that version and writes it no more, in that epoch, until its operator says otherwise | unit | -| 81 | A key its party dropped wrote, from a history before the drop, ahead of the party's envelope; then a remake or a fork | The snapshot or genesis keeps the party's value, as the federation reads it | unit | -| 82 | A node taken off its list proposes and decides a remake at a history where it was on | Nobody follows it: a node follows a remake only where its coordinator's party lists the coordinator when it switches | unit | -| 83 | A party taken out and let in again within an epoch | The list it wrote before counts no more: its list's `since` is the version that let it in | unit | -| 84 | A node taken off its list decides a remake beside an honest one of the same epoch | Its decision counts for nothing: nodes follow the honest one | unit | +| 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 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 | +| 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 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 | +| 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 | +| 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 | 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 | ## Roads not taken -* **First come, first served, for identifiers.** Order between two parties that wrote - at once can't be read from the document without trusting someone's clock or - someone's witness. Votes need neither. +* **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 changes - 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. +* **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.** It needs every version kept, and old - keys could still grow a chain longer than the one nodes took. + 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 by its genesis change needs + 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. -* **Votes counted by the keys their party had at their history.** A remake replays a - vote and its party's key set in an order of its own, and where two parties' key sets - and votes cross, no order keeps every vote. The keys a version names don't move. -* **Housekeeping within an epoch**: members deleting what counts no more. Automerge - keeps every operation, so it shrinks nothing; and a place it empties reads whatever - its party once signed there and anyone puts back. A remake's snapshot and a fork's - genesis leave it out. -* **Versions replayed across a remake**, so that a node that took one written after the - base follows too. It needs versions, their votes and what names each replayed in an - order of their own, and two `true`s cast at once, replayed one after the other, can - undo a version that passed. A remake racing a version is rare; the nodes that took it - stay. -* **Remakes of other kinds** (`replace`, `import`, `strict`), followed where the new - document reads as the old one did. A snapshot judged by none could swap an envelope - for one naming a later version, and a node would take it on its peers' word wherever - it can't read the old one. A compaction's snapshot every node builds itself. -* **Rules of a fixed depth**, without `**`, so that the rules alone say whether a key is - a place or the way to places. A party's namespace would be flat; values in `@` keys do - the same with `**`. +* **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. +* **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. * **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. -* **Forks within one document**, each side judging by its own chain of versions. It - needs judging per chain, judging again when a node changes sides, node lists and - remakes per chain. A swarm 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 fork with that policy - starts clean. +* **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. @@ -796,67 +575,62 @@ What an attacker does, and what happens. *Unit*: the judging, with crafted chang 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, the envelope and how the value of -a place is read, what makes a change one Automerge writes, how a path and a version are -spelled and read, the sizes each may have, which version a node takes and which is -current, the remake's snapshot, its replay and its order, and the Automerge version, -whose encoding fixes a change's hash. +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. 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 the policy, its swarm has stops taking changes and says so. +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 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 genesis change, never as - content before it; + (`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 -1. **The federated policy**: a swarm started federated by its genesis change, with the - node lists its first version gives; versions and what makes one valid, rules and - paths, values in `@` keys, keys, votes, passing and dead, which version a node takes - and the current one, judging by it; votes and proposals by their version's keys; the - protocol data as listed, all else closed; the `cv3.` envelope with the meta's - version, and the order by it; node lists, a node's party in its configuration, and no - token from another node; what every reading of a strict policy in continuum - (`strict()`) makes of the federated one; screening's frontier moved by every change - touching what the federation reads (versions, proposals, votes, key sets, node - lists), as `access::screen` moves it today for what continuum's rules read; the byte - formats (a version's JCS bytes, hashes in paths and how two compare, the meta's - version); and the sizes a version, a set, a list, a path and a value may have, each - within what a sync message carries. A node that doesn't know the policy stops taking - changes. 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. -2. **What counts**, read by the current version and the keys; shown in the API. - Reports of the versions a node refused, and its operator having it drop what it - took; a tool reporting, from the votes, a party that voted twice. -3. **Nodes**: membership by the node lists and the party a node's own entry names, the - party shown in the handshake before that entry exists, a node syncing with members - only (a wire change), neighbours by party. -4. **Forks**: a swarm started from another's document, named by its first version and - the heads it names, and the check against it. -5. **Remakes**: compaction only, each node building it from a base it holds, never on - its peers' word; the old epoch synced, while a node keeps it, with nodes still on it; - replay under the version current at the base. +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, 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. +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. 6. **The registry**: the rules for krebs, the tool that signs kartei's entries in as - their parties', after the genesis change, and the one that reads them out. + their parties', after the root, and the one that reads them out. -Each stage's tests are its rows of Attacks. Each stage keeps every swarm that isn't -federated as it is, its tests passing untouched. A federated swarm made before the last -stage is for tests: a later stage judges it otherwise. Until stage 2, nothing brings -together the nodes a writer forked splits. +A federated swarm made before the last stage is for tests: a later stage judges it +otherwise. |
