diff options
| -rw-r--r-- | docs/federation.md | 424 |
1 files changed, 246 insertions, 178 deletions
diff --git a/docs/federation.md b/docs/federation.md index 8907915..9d43411 100644 --- a/docs/federation.md +++ b/docs/federation.md @@ -15,12 +15,12 @@ are marked *(checked)* where they were read in it. ## Optional A swarm is federated once its policy says so. It can say so from the genesis change, -or later (Becoming federated), and stops by a version of its policy (Changing the -policy). Nothing else changes: a swarm that doesn't say so stays as it is, its -registry, rules, remakes and replay included. Continuum's wire version says only -whether a node can take part in a federation at all; which federation a swarm follows -is a number of its own, in its policy: this design is federation 1 (Changing the -federation). +or later (Becoming federated). Nothing else changes: a swarm that doesn't say so stays +as it is, its registry, rules, remakes and replay included. Continuum's wire version +says only whether a node can take part in a federation at all; which federation a +swarm follows is a number of its own, in 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). ## Parties and the adversary @@ -51,12 +51,13 @@ that nothing coming from any node breaks a promise for the others. 1. **What counts is what a party signed, with a key it holds, where the policy lets it write.** Every honest node that holds the swarm from its genesis change refuses - what no policy would let be written, whoever sends it, and reads nothing else as - counting. + 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 a share of its parties**, two thirds unless they decide otherwise, as one history saw their votes; and nodes that hold - the same changes read the same policy. A version that passed stays, as long as no - party votes twice (Changing the policy). + the same changes read the same policy. Without a party voting twice, a version that + passed stays; with one, the parties' nodes agree again once they sync (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. @@ -68,23 +69,38 @@ Not promised: * that the swarm stays fast. A party that floods the document, or whose nodes keep remakes from committing, makes nodes slow, not wrong: denial of service breaks no promise here, and the others fork away from it; +* that honest nodes stay together where a node commits two changes under one writer + and number: they are apart until a remake, or a fork (Where Automerge sets limits); +* that a node taken off its party's list, or a key a party dropped by itself, can't + still commit or sign at a history from before: only a version ends what a key signs + (Keys), and a remake ends what is written at the time before it; * anything to a node that joins, or comes back after a remake without holding the epoch before: it takes the document on its peers' word (Remakes). ## The design It builds on values signed by their users ([`access.md`](access.md)): a value is an -envelope its party signs, `cv2.<value>.<meta>.<signature>`, the meta naming the swarm, -the path, who signed, the envelope it replaces (`prev`) and its number (`seq`, one -more than that one's). Of the envelopes a place holds, written at once, the one with -the highest `seq` is its value, of equal ones the one with the lower SHA-256 *(checked: -`document::store`, `access::envelope`)*. So what a place holds is its party's to say, -never the order of operations, which whoever writes a change steers. +envelope its party signs, `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). Under the federation it names also the **version** of the +policy current where it was written, by number (`version`, The policy): a change +writing one that names another is refused. Of the envelopes a place holds, written at +once, the one with the highest version number is its value, then the highest `seq`, +then the lower SHA-256. So what a place holds is its party's to say, never the order +of operations, which whoever writes a change steers; and what was signed under a later +version is ahead of anything written at a history from before it. + +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. ### What it asks of the document * **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. + change is judged at its history and nothing else, but for one rule: nothing is + added to the time before the swarm was federated (Becoming federated). * **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. @@ -110,16 +126,17 @@ the first, number 0): "rules": [ { "path": "home/{party}/**", "writer": "{party}" }, { "path": "names/r/{party}/**", "writer": "{party}" }, - { "path": "names/r/wiki", "writer": "lass" }, + { "path": "names/r/wiki/@", "writer": "lass" }, { "path": "ip4/10/243/7/*", "writer": "tv" }, { "path": "names/**", "writer": false } ] } ``` * **The federation** it follows, and its **number**, one more than that of the version it changes. -* **The share** of the parties a proposal needs, two whole numbers: with `[2, 3]`, the - votes of two of every three (3·votes ≥ 2·parties). More than a half, at most all. -* **The parties**, by name. +* **The share** of the parties a proposal needs, two whole numbers `[a, b]`, 0 < a ≤ b, + 2·a > b: with `[2, 3]`, the votes of two of every three (3·votes ≥ 2·parties). +* **The parties**, by name: as continuum's user names, 1 to 64 of `A-Z a-z 0-9 . _ @ + -`, each once. * **The keys it sets**: those of a party new in it, or of one whose keys the parties replace (Keys). * **The rules**, in order: the first whose path matches a path says who writes there. @@ -127,14 +144,17 @@ the first, number 0): `_continuum`; any other is literal, `{party}` (a party's name), `*` (any one segment) or, last only, `**` (one segment or more). The writer is `"{party}"` (the party the path names, where the rule's path holds `{party}`), a party's name, or - `false`: nobody. A path no rule matches, nobody writes. A **place** is a path where - an envelope is written; nothing is written within one. + `false`: nobody. A path no rule matches, nobody writes. -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`), and -an address by its parts, so that a party's zone or block is one rule. +A **place** is a map key where an envelope is written: never within a list, nothing +written within one, and a path that holds places is no place. How names and addresses +are spelled as paths is the application's: the registry writes a name by its labels, +last first, its own value at `@` (`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 is one rule. -A version that doesn't read as one, or breaks any of the above, is none: it can't +A version is none if it doesn't read as one (JSON with a key twice, fields missing or +more), its bytes don't hash to its place, or it breaks any of the above: it can't pass, and a change writing it is refused. The federation's own paths are its number's, not the rules': the same in every @@ -145,14 +165,18 @@ version. | `_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 | +| `_continuum/federation/keys/<party>` | its keys | that party; the change that writes a version setting them | | `_continuum/federation/nodes/<party>` | its nodes' IDs | that party | +| `_continuum/federation/went/<party>` | the fork it went to | that party | -What a party writes is an envelope, signed by one of its keys, everywhere but at -`versions`. Of continuum's own data, a federated swarm keeps what nodes write for the -protocol (member entries, remakes and their votes, epochs), written by members as in -every swarm. It has no user registry: `_continuum/users`, bans, and every other entry -of `_continuum/access` are closed, and nothing reads them. A party logs in to its own +What a party writes is an envelope, signed by one of its keys. A version, and the +keys a version sets, are written unsigned, and count by the votes the version had. A +proposal's place takes only the proposal, or its party's `null`. Of continuum's own +data, a federated swarm keeps what nodes write for the protocol (member entries, +remakes and their acks, epochs), written by members as in every swarm; a member's +change carries its node's signature, as signatures are required in a strict swarm. It +has no user registry: `_continuum/users`, bans, and every other entry of +`_continuum/access` are closed, and nothing reads them. A party logs in to its own nodes as its operator sets up, and a node takes tokens only from the nodes its own party lists. @@ -165,9 +189,13 @@ A party **votes** on a proposal by writing `true` or `false` at `_continuum/federation/votes/<party>/<version>/<proposal>`: the version the proposal changes, and the proposal, by their hashes. No vote there is no vote. -* **A vote never changes.** A write where a vote is keeps its value (a party signs its - votes again when it changes keys). A `true` and a `false` written there at once read - as `false`. +* **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**: by the keys its party had at its + history, whatever keys the party has since. It goes only with its version, when that + is replaced (What counts), and nobody deletes it before. A write at a vote's place + is refused. * **A proposal passes** once at least the share of its version's parties voted `true`. It is **dead** once so many voted `false` that the rest are fewer than the share. * **One yes at a time.** A party's `true` is taken only if, at its history, every other @@ -175,58 +203,62 @@ changes, and the proposal, by their hashes. No vote there is no vote. and is free again when that one can't pass any more. Once a proposal passed on the current version, any member writes it at -`_continuum/federation/versions/<hash>`, as it is, unsigned; every node judges that -change by the votes in its history, and by the version it changes being written -there. **The current version** is the written one with the highest number; of equal -ones, the one with the lower hash. A version takes effect when it is written, and -judges every change in sight of it. +`_continuum/federation/versions/<hash>`, as it is, unsigned, with the keys it sets +(Keys); every node judges that change by the votes in its history, and by the version +it changes being current there. A version takes effect when it is written, and judges +every change in sight of it. + +**The current version** is the end of the longest chain of written versions from the +first, each changing the one before. Of chains of one length, the one with the lower +hash where they part. * **Votes that split pass nothing**, like a proposal that gets only nays: three for one proposal and three for another, of six. Those who didn't back a proposal vote `false` on it; once it is dead, its backers are free, and another proposal can pass - on the same version. Clients vote for the proposal that leads, so that splits are - rare. Parties that won't wait fork. -* **Two versions with one number** are written only if a party voted twice: `true` and - `false` on one proposal, each shown to some, or `true` on two. Then every node that - holds both reads the one with the lower hash, so nodes still agree once they sync; - but a node may have read the other for a while. One party is enough for that, where - a vote is close. Both its votes are in the document for all to see, and the parties - can take it out. + on the same version. Parties that won't wait fork. +* **Two versions changing one version** are written only if a party voted twice: + `true` and `false` on one proposal, each shown to some, or `true` on two; one party + is enough where a vote is close. The nodes that read each side for a while agree once + they sync: the side the parties went on with is the longer, and if neither went on + yet, the lower hash. What was written under the other side stays written, and counts + as the current version says. A version written late beside one the parties went on + from is shorter, and stays so: making it longer takes votes on proposals made on it, + and honest parties vote only on what they read as current. +* **A party that voted twice shows**: its two votes on one version, both signed with + its keys. A node that holds them, or two versions changing one, reports it (a log, + the API), with both votes; a client keeps them, as they are signed and anyone can + check them after the document has dropped them. 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 a version, the parties' choice. * **A proposal on a version that isn't current lapses**, with the votes on that - version. Its party proposes it again on the current one; a client does that by - itself for one that touches nothing the version that passed changed. + version. Its party proposes it again on the current one. * **Who proposed doesn't matter** once it is written: a proposal passes whether its party is still one or not. Everything the federation decides is a change of the policy: who the parties are, and their keys where they lost them; who writes where, which is giving an identifier, -taking it back and giving it to another; the share; and the federation itself. A -version may name another federation (Changing the federation), or none, with the -policy the swarm goes on with (`"federation": null, "policy": {…}`, and the registry -it starts with, where that policy has one), which the change that writes it puts at -`_continuum/access/policy`. From then on, that policy is the swarm's, whatever it is. +taking it back and giving it to another; the share; and the federation itself, by +naming another (Changing the federation). ### Keys -A party's keys are those the latest version that set its keys gave it, unless the -party replaced them since: an envelope at `_continuum/federation/keys/<party>`, naming -that version and the keys, signed with a key of the set it replaces. The envelope's -`seq` orders a party's sets, so an older one put back is behind. +A party's keys are at `_continuum/federation/keys/<party>`: one envelope, the set, +signed with a key of the set it replaces, numbered as any envelope. The change that +writes a version setting a party's keys writes them there too, unsigned, with the +version's hash: they are ahead of every set written under an earlier version. -* **A value counts only while the key that signed it is among its party's keys.** So - changing keys is: write the new set, and sign again what should stay (a client does - that). Nothing remembers a key that was dropped. -* **A stolen key.** The party writes a set without it: what the thief signed stops - counting, and so does what the party signed with it, until signed again. If the - thief wrote a set first, without the party's other keys, the party has none it can - answer with: the parties give it new keys by a version, which is ahead of every set - written before. A vote the thief cast on a proposal that passed stays cast. -* **The first envelope at a place names its party's keys**: where it replaces nothing, - its `prev` is the digest of its party's key envelope (or the hash of the version - that set its keys). So one that was replaced or deleted can't be put back later - where the place is empty again, once its party changed keys. -* **Deleting a value** is writing an envelope with `null` in its place, which stays as - any value does, while its key is among its party's. +* **A value counts only while the key that signed it is among its party's keys**, + votes excepted, which count as cast. Changing keys is: write the new set, and sign + again what should stay (a client does that, its deletions too). +* **Only a version revokes a key.** A party changing its keys by itself adds keys and + tidies; but a key it drops can still sign, at a history from before the drop, a set + of its own numbered past the party's, and nothing in the document tells which of two + chains from one set is the party's. A key lost, stolen, or retired and not + destroyed, is answered by a version setting the party's keys, which is ahead of every + set before it. What the party then signs again names that version, and is ahead of + anything the old key writes at a history from before it. +* **A vote cast with a key before the version that replaced it stays cast**: one + party's votes, on the versions current until then. ### What counts @@ -239,10 +271,13 @@ whole. These count no more, and nothing else is stale: 1. a value 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 keys and its node list; -2. a value signed by a key that isn't among its party's; +2. a value signed by a key that isn't among its party's, votes excepted; 3. a proposal on a version that isn't current, and the votes on that version; -4. a version behind the current one; -5. the member entry of a node no party lists. +4. a version not on the chain to the current one, or behind it; +5. an envelope behind another at its place; +6. the member entry of a node no party lists; +7. a value written before the swarm was federated, unless a party's key signed it and + the first version lets that party write there. **Any member may delete what counts no more**, place by place, never a map holding places; every node judges the deletion by the document the deleting change makes. That @@ -251,43 +286,50 @@ deletions don't flood the document, the one whose write made something stale del it in the same change; others delete only what they find stale, as in a swarm whose parties went quiet. -What is deleted this way can come back only as its party's own: an envelope first at -its place, put back where the place is empty, counts if its party still has the keys -it named and may write there. So a place taken from a party and given back may show -what the party had there, until the party writes there again. +**What is deleted can be put back** where its place is empty, by anyone who holds it, +and counts if its key is among its party's and its party may write there: a place +taken from a party and given back may show what the party had there. Whatever the +party writes there under a later version is ahead of it. ### Nodes A party lists the nodes that carry for it, by node ID, at -`_continuum/federation/nodes/<party>`. Only a listed node is a member: it registers, -commits changes and syncs, and a node syncs with no other (Stages). 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. +`_continuum/federation/nodes/<party>`; a node listed by two parties carries for +neither. Only a listed node is a member: it registers, commits changes and syncs, and +nodes sync with members only (Stages). 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. ### 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. It **forks**: it starts a -swarm of its own from the document. +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. 1. One of the group starts the new swarm. Its genesis change holds what the old - document read as at heads it names, as a remake's snapshot does, with a version of - the group's choosing written as its first: the parties it wants to carry on with, - and whatever else it wants changed. It names the swarm and the heads it came from. - Every proposal is a chance to fork: the version is usually one that didn't pass. -2. The others join it as a node joins any swarm, by its genesis change's hash. A node - that holds the old document checks the new one against it first: the same at those - heads, but for the version. -3. What the genesis change holds counts as it did, signed for the swarm it came from. - Everything written from then on is signed for the new swarm. + document read as at heads it names, as a remake's snapshot does, but for the + federation's versions and continuum's member entries: of versions, only the + group's own, written as the fork's first, numbered one past the highest at those + heads, setting every party's keys. 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 swarm is named by its genesis change's hash, which nobody chooses, and an + envelope's meta names it so. The genesis change holds envelopes signed for the swarm + it came from, and they count; 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 checks the new one against it first, the same at those + heads but for the versions and member entries, and says what it holds that those + heads lack. A fork needs nobody's vote and nobody's ack: it binds only those who go, and the swarm they left goes on for those who stay. A party the fork's version leaves out writes nothing there, and what it had counts no more; to come back, the fork's parties let it -in by a version, as they would anyone new. A fork may name parties that weren't among -the first to go (every party its founders consider honest, say), so that they can -follow whenever they like, without asking. +in by a version, as they would anyone new. A fork's version may name parties that +weren't among the first to go (every party its founders consider honest, say), so that +they can follow whenever they like, without asking. A party that goes may say where, +at `went/<party>`. What a party's nodes do of themselves is their operators' business, written nowhere: join a fork where parties their operator follows went, vote as those voted, vote by @@ -301,8 +343,8 @@ Anything outside a party's namespace is shared: names, addresses, anything a rul 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. +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 one rule (`ip4/10/243/7/*`), and a new host is a write where its party may write. Votes are @@ -311,11 +353,17 @@ for parties, zones, blocks and names that are nobody's by their spelling. ### Becoming federated A swarm becomes federated by one change: it writes the federated policy and the first -version, by one who may write the policy. From then on a node refuses every change it -doesn't hold yet whose history lacks that change: nothing is added to the time before. -What was written before counts only as anything does, where a party's key signed it -and the first version lets that party write there: the parties sign again what they -keep. +version, by one who may write the policy. From then on a change is taken only if that +change is in its history, or it is in that change's history; any other is refused, +received or held, and a node that held one beside it drops it, with what builds on +it, once a peer tells it so. It is continuum's rule for a swarm turned strict +*(checked: `access::rules`, `before_strict`)*, read for the federating change. Of two +federating changes written at once, the one with the lower hash. A swarm federated +from its genesis change has no time before. + +What was written before counts only where a party's key signed it and the first +version lets that party write there: the parties sign again what they keep. An +envelope from before names no version, and is behind every one that does. ### Remakes @@ -325,21 +373,25 @@ is continuum's as in every swarm. What a federated node asks of a remake: * **It loses nothing and adds nothing.** A node follows a remake only where the new document reads as the old one did at the base, at every place and every path of the - federation. A node checks that before it switches, stays where it is otherwise, and - never rejoins an epoch it refused. -* **Writes after the base** are replayed as the policy shapes it: every envelope beyond - the base, in the order they were written, each judged again in the new epoch. One - the new epoch refuses (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. - Housekeeping after the base isn't replayed: what it deleted is stale again, and is - deleted again. + federation, as continuum reads it. A node checks that before it switches, stays + where it is otherwise, and never rejoins an epoch it refused. +* **Writes after the base** are replayed as the policy shapes them, as continuum replays + under a strict policy: at each place, the chain of envelopes that leads from what the + new document holds there to what the old one reads, each in a change of its own, + judged again in the new epoch. Versions written after the base are replayed with + them, in the order they were written, each judged by the votes as when it was + written. What the new epoch refuses (its key was dropped by a version, 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. Housekeeping after the base isn't replayed: what it + deleted is stale again, and is deleted again. -So a remake decides nothing, and a swarm that never remakes stays as correct as one -that remakes all the time; it only grows slower. +So a remake decides nothing that counts, and a swarm that never remakes stays as +correct as one that remakes all the time; it only grows slower. A remake does end one +thing: nothing is written at a history from before it, so what a dropped key or a +node taken off its list could still write there ends with it. A node that doesn't hold the epoch before (it joins, or was away) can't check: it -takes the epoch its peers give it. Its operator gives it the swarm's genesis change -and, to be sure of the policy, the hash of the version it expects to be current. +takes the epoch its peers give it. ### Where Automerge sets limits @@ -368,19 +420,19 @@ Recommendations, not rules: none of these breaks a promise, only how fast a node 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 written; each party's keys, by that version and - the highest `seq`; each place's value, by the highest `seq`. None of it depends on - the order of operations, so a change made to look older or newer than it is moves - nothing. + current version, the end of the longest chain; each party's keys, by that version + and its set; each place's value, by version number, then `seq`. None of it depends + on the order of operations. 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. 2. **The policy.** A version is written only where, at one history, the share of the parties of the version it changes voted `true` for it. An honest party backs one - proposal on a version at a time, and another only once the first is dead: a - proposal can't pass at one history and be dead at another unless some party's - `true` and `false` for it are both there. So without a party voting twice, at most - one version is written per number. With one, nodes still read the same version - once they hold the same changes: the lower hash. -3. **Carrying on.** A fork is a swarm of its own, joined by its operators' choice - only. A party nobody follows carries on alone. + proposal on a version at a time, and another only once the first is dead; its votes + count as cast. So a proposal can't pass at one history and be dead at another + unless some party's `true` and `false` for it are both there. Without a party voting + twice, at most one version changes a version. With one, nodes still read the same + version once they hold the same changes: the longest chain. +3. **Carrying on.** A fork is a swarm of its own, named by its genesis change, joined + by its operators' choice only. A party nobody follows carries on alone. ## Attacks @@ -390,44 +442,47 @@ What an attacker does, and what happens. *Unit*: the judging, with crafted chang | # | 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, or another swarm | Refused: its meta names both | 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, its operations numbered to win | Taken, and behind: the highest `seq` is the value | unit | -| 5 | An older version written again | The same place, the same bytes; behind the current one by its number | unit | -| 6 | An older key set, or node list, put back beside the newer | Behind, by `seq` | unit | -| 7 | A version written without the votes, or on a version that isn't written | Refused at its history | unit | -| 8 | A version that doesn't read, a share of a half, a rule under `_continuum` or without a literal first segment | No version: can't pass, refused when written | 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 dropped key writes a key-set chain at a history before the drop | Ahead of the party's own set, until a version sets the party's keys; then behind | unit | +| 7 | A version written without the votes, or not changing the current one at its history | Refused at its history | unit | +| 8 | A version that doesn't read, has a key twice, a share of a half, a rule under `_continuum` or without a literal first segment | No version: can't pass, refused when written | unit | | 9 | `true` on two proposals of one version | The second refused, unless the first is dead at its history | unit | -| 10 | `true` on two proposals at once, from two nodes | Both taken; two versions may be written; the lower hash is read. Not promised to stay; the votes show | unit, every order | -| 11 | `true` and `false` on one proposal at once | Reads as `false`; a node that saw only the `true` may write the version. As 10 | unit, every order | -| 12 | A vote changed | Refused | unit | -| 13 | Votes split, honestly or not | Nothing passes; nays make the proposals dead, and another passes | unit | -| 14 | A third of the parties never votes, or votes `false` on everything | Nothing passes; the others fork | sim | -| 15 | The party a version takes out writes that version itself | Written: a version counts by its votes, not its writer | unit | -| 16 | A lapsed proposal, or votes on it, written again | Count no more at once | unit | -| 17 | Values signed with a stolen key | Count until the party drops the key, then none of them | unit | -| 18 | The thief writes a key set without the party's keys | The parties set its keys by a version, ahead of every set before | unit | -| 19 | The thief writes changes that look older than the key's loss | Count no more: counting is by the keys now | unit | -| 20 | A deleted or replaced first envelope put back where its place is empty | Refused once its party changed keys; else its party's own value again | unit | -| 21 | A place taken and given back, a party taken out and let in | What it had may be put back until it writes there | unit | +| 10 | `true` on two proposals at once, from two nodes | Both taken; two versions may be written; the longest chain is read; reported | unit, every order | +| 11 | `true` and `false` on one proposal at once | Both held; a node that saw only one may write a version. As 10 | unit, every order | +| 12 | A vote changed, or deleted while its version is current | Refused | unit | +| 13 | A vote cast at a history from before, on a proposal made since | Refused: its proposal isn't written there | unit | +| 14 | A party changes keys after voting | Its vote counts as cast | unit | +| 15 | Votes split, honestly or not | Nothing passes; nays make the proposals dead, and another passes | unit | +| 16 | The parties beyond the share never vote, or vote `false` on everything | Nothing passes; the others fork | sim | +| 17 | The party a version takes out writes that version itself | Written: a version counts by its votes, not its writer | unit | +| 18 | A version written late beside one the parties went on from | Shorter: changes nothing | unit | +| 19 | A proposer grinds its version's hash | Wins a tie of two versions, one number, nothing built on either; only with a double vote | unit | +| 20 | Values signed with a stolen key | Count until a version drops the key, then none of them | unit | +| 21 | A deleted value put back where its place is empty | Counts if its key and its place are still its party's; behind whatever the party writes there later | unit | | 22 | A write in another party's namespace, or at an identifier of another's | Refused by the rule | unit | | 23 | Housekeeping of something that counts | Refused, by the document the change makes | unit | | 24 | Housekeeping by a change that saw a time when it didn't count | Taken; the party writes again | unit | -| 25 | A map holding places deleted | Refused: places only | unit | -| 26 | A change with a history from before the swarm was federated, sent later | Refused | unit, sim | -| 27 | A remake whose document reads otherwise than the base | Nodes holding the base stay, and never rejoin it | sim | -| 28 | A remake at a base where a place holds two envelopes | The one that was the value stays the value | unit | -| 29 | A joining node handed a made-up epoch | Taken, unless it lacks the version its operator named. Not promised | sim | -| 30 | The party with most nodes remakes often, or never acks | Slow, not wrong; the others fork | sim | -| 31 | A writer forked: two changes, one number | Honest nodes split until a remake, or a fork | sim | -| 32 | Different changes to different peers | Honest nodes agree once they sync | sim | -| 33 | A party withholding its changes or votes | Not promised | — | -| 34 | Flooding: namespace, proposals, history, writers | Slow, not wrong | bench | -| 35 | A node taken off its list writes changes that look older | Taken where valid at their history; they move nothing (4 to 6) | unit | -| 36 | A token from another party's node | Refused | unit | -| 37 | Envelopes the stayers sign after a fork, brought to the fork | Refused: signed for the other swarm | unit | -| 38 | A fork whose genesis change differs from the document it names | Nodes holding that document don't join | sim | -| 39 | A federation, or a policy, a node doesn't know | It stops taking changes | unit | +| 25 | A map holding places deleted, or a place written within | Refused | unit | +| 26 | A change from before the swarm was federated, sent later | Refused; held, dropped once told | unit, sim | +| 27 | A change written at once with the federating change | As 26, on every node alike | sim | +| 28 | A remake whose document reads otherwise than the base | Nodes holding the base stay, and never rejoin it | sim | +| 29 | Two envelopes at one place beyond a remake's base | The chain to the one read is replayed | unit | +| 30 | A version written after a remake's base | Replayed with the envelopes, in order | unit | +| 31 | A joining node handed a made-up epoch | Taken. Not promised | sim | +| 32 | The party with most nodes remakes often, or never acks | Slow, not wrong; the others fork | sim | +| 33 | A writer forked: two changes, one number | Honest nodes split until a remake, or a fork. Not promised | sim | +| 34 | Different changes to different peers | Honest nodes agree once they sync | sim | +| 35 | A party withholding its changes or votes | Not promised | — | +| 36 | Flooding: namespace, proposals, history, writers | Slow, not wrong | bench | +| 37 | A node taken off its list writes changes at a history where it was on | Taken where valid there; behind what is written under later versions | unit | +| 38 | A token from another party's node | Refused | unit | +| 39 | Envelopes the stayers sign after a fork, brought to the fork | Refused: signed for the other swarm | unit | +| 40 | A fork whose genesis change differs from the document it names | Nodes holding that document don't join, and say what differs | sim | +| 41 | A fork at heads of its founder's choosing | Joiners holding the document are told what those heads lack | sim | +| 42 | A federation, or a policy, a node doesn't know | It stops taking changes | unit | ## Roads not taken @@ -437,15 +492,25 @@ What an attacker does, and what happens. *Unit*: the judging, with crafted chang * **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, and the party - signs again what was its own. + look as old as it likes. A version dropping the key takes all of them back, 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 a version replaced by - another that also had its votes; the votes show who. + ends, and one party voting twice on a close vote can have two versions written; the + longest chain heals it, and the votes show who. +* **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. +* **The highest number for the current version.** A party that voted twice could + write the other version months later, and everything built since on the one it + replaced would go. * **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 before + and during the federation, would be read again by the next policy. A fork with that + policy 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. @@ -454,8 +519,9 @@ 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 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, and how a path -and a version are spelled. The hash of a change and its encoding are Automerge's +value of a place is read, what makes a change one Automerge writes, how a path and a +version are spelled and read, the longest chain, the rule for the time before, the +remake's check and its replay. The hash of a change and its encoding are Automerge's version's. A change to the federation is a design like this one, with the next number. A swarm @@ -477,17 +543,19 @@ On a federated swarm: ## Stages 1. **The federated policy**: versions and what makes one valid, rules and paths, keys, - votes, passing and dead, the current version, judging by it. A node that doesn't - know the policy stops taking changes. Until stage 4, a federated swarm takes no - remake. + votes, passing and dead, the longest chain, judging by it; the meta's version + number and the order by it; tokens from one's own party's nodes only. A node that + doesn't know the policy stops taking changes. Until stage 4, a federated swarm takes + no remake. 2. **What counts**, read by the current version and the keys; shown in the API. - Housekeeping. + Housekeeping. Reports of a party that voted twice. 3. **Nodes**: membership by the node lists, a node syncing with members only, as a - swarm key does today (a wire change); tokens from one's own party's nodes only. -4. **Remakes**: the check that a remake lost and added nothing; replay of envelopes, - each judged again. -5. **Forks**: a swarm started from another's document, and the check against it. -6. **Becoming federated** in a running swarm, and leaving. + swarm key does today (a wire change). +4. **Remakes**: the check that a remake lost and added nothing; replay of versions with + the envelopes. +5. **Forks**: a swarm started from another's document, named by its genesis change's + hash, and the check against it. +6. **Becoming federated** in a running swarm. 7. **The registry**: the rules for krebs, the tool. Each stage's tests are its rows of Attacks. Each stage keeps every swarm that isn't |
