aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--docs/federation.md59
1 files changed, 41 insertions, 18 deletions
diff --git a/docs/federation.md b/docs/federation.md
index b08ffcc..ea13273 100644
--- a/docs/federation.md
+++ b/docs/federation.md
@@ -1080,6 +1080,13 @@ statement on its side.
### What every node judges
+A change is first of all one that Automerge itself writes, or it is refused before
+Automerge sees it: its bytes are the ones Automerge encodes for it; every other actor
+it names has changes in its history; and its first operation is numbered one after
+the highest of its dependencies. Automerge 0.12 applies changes that are none of
+these, and then panics, or saves a document that doesn't load *(measured upstream)*.
+All three are read from the change and its history, as the rules are.
+
A change is valid if, in the document at its dependencies:
1. It has no dependencies and is the root the node was given (the genesis change, or
@@ -1338,6 +1345,10 @@ the document. What must hold for this, and doesn't everywhere today:
have the registers of users and claims, the decisions and what is uncovered;
* nothing a node keeps a bounded number of decides validity: a change pushed out of
the waiting ones comes again *(checked: `MAX_WAITING`)*;
+* a change being what Automerge itself writes. Automerge 0.12 applies some that
+ aren't, and then holds another change than the one it was given: under the hash
+ received it gives back a change with another hash, and its save doesn't load
+ *(measured upstream)*. Screening refuses those before Automerge sees them;
* one change per actor and number. A forked actor breaks "hold the same changes"
until one side drops. Automerge names a change by actor and number where
Kleppmann's construction needs the hash.
@@ -1819,18 +1830,19 @@ Nodes and syncing:
| 101 | Sends envelopes that don't check, without end | Refuse each (a signature costs about 30 µs to check *(docs)*); the node is refused as a whole after the first of its own | 6 | sim: `a_refused_node_costs_little` |
| 102 | Writes its own member entry without end; fills the waiting changes; sends changes that say they saw little, each to be judged far back | Take them no faster than a budget per party: put off, never refused; a share of the waiting each | 6 | sim: `a_party_past_its_budget_waits` |
| 103 | Crafts a change Automerge won't take, or that writes in an object nowhere to be found | Refuse *(checked: the rules refuse the second today)*; only the message that brought it fails | 1 | unit: `a_change_writing_nowhere` |
+| 104 | Crafts a change Automerge takes and shouldn't: bytes it wouldn't encode itself, an actor named that nobody wrote as, operations numbered far ahead of its dependencies' or below them | Refuse before Automerge sees it: applied, such a change makes a node panic, or its document save to bytes that don't load | 1, 2 | unit: `only_what_automerge_writes` |
Rules, and the swarm as it is:
| # | The adversary | Honest nodes | Promise | Shown by |
|---|---|---|---|---|
-| 104 | A rule differs between versions (a bug) | Each side refuses what the other takes, or their stamps name two digests for the same changes: each logs and shows it. A node that finds itself apart from a third of the voters' nodes at its first start with a version writes nothing. One side upgrades and drops | not promised | sim: `a_side_drops_and_comes_back`, `two_digests_one_history`; unit: `a_node_checks_itself` |
-| 105 | Stamps a wrong digest, to keep the nodes that upgrade from writing | A node stops only where it differs from the nodes of a third of the voters; from fewer it shows it and goes on | 6 | unit: `one_wrong_digest_stops_nobody` |
-| 106 | A policy version a node doesn't know: in the root, or decided | It doesn't sync, and takes no such proposal up: a policy is decided only with two thirds of the voters' nodes knowing it | 1 | unit: `no_sync_under_an_unknown_policy`, `an_unknown_policy_isnt_taken_up` |
-| 107 | A root that lies and isn't left out; a user nobody unvouches | The parties ban it from a cut on and read on without it | not promised | unit: `a_ban_for_those_who_follow` |
-| 108 | A banned user's name claimed by one who bans it | The node refuses its own user's write: the others would | 1 | unit: `no_write_by_ones_bans_alone` |
-| 109 | A partition, for any length of time | A side decides only with nodes of two thirds of all the voters on it. Where a third of them have nodes and votes on both sides, both may: every node then acts on the higher number, and of two remakes ends up in the one that holds | 7 | sim: `one_side_decides`; unit: `the_last_holds` |
-| 110 | None: a swarm that isn't federated | Everything as today | Optional | the existing tests, untouched; `bench_screening` |
+| 105 | A rule differs between versions (a bug) | Each side refuses what the other takes, or their stamps name two digests for the same changes: each logs and shows it. A node that finds itself apart from a third of the voters' nodes at its first start with a version writes nothing. One side upgrades and drops | not promised | sim: `a_side_drops_and_comes_back`, `two_digests_one_history`; unit: `a_node_checks_itself` |
+| 106 | Stamps a wrong digest, to keep the nodes that upgrade from writing | A node stops only where it differs from the nodes of a third of the voters; from fewer it shows it and goes on | 6 | unit: `one_wrong_digest_stops_nobody` |
+| 107 | A policy version a node doesn't know: in the root, or decided | It doesn't sync, and takes no such proposal up: a policy is decided only with two thirds of the voters' nodes knowing it | 1 | unit: `no_sync_under_an_unknown_policy`, `an_unknown_policy_isnt_taken_up` |
+| 108 | A root that lies and isn't left out; a user nobody unvouches | The parties ban it from a cut on and read on without it | not promised | unit: `a_ban_for_those_who_follow` |
+| 109 | A banned user's name claimed by one who bans it | The node refuses its own user's write: the others would | 1 | unit: `no_write_by_ones_bans_alone` |
+| 110 | A partition, for any length of time | A side decides only with nodes of two thirds of all the voters on it. Where a third of them have nodes and votes on both sides, both may: every node then acts on the higher number, and of two remakes ends up in the one that holds | 7 | sim: `one_side_decides`; unit: `the_last_holds` |
+| 111 | None: a swarm that isn't federated | Everything as today | Optional | the existing tests, untouched; `bench_screening` |
## The registry on it
```
@@ -1887,16 +1899,16 @@ the network at large reads.
## Stages
Each leaves the system working, and is a few patches with its tests, which leave
-their vectors. At every stage the existing tests pass untouched (110).
+their vectors. At every stage the existing tests pass untouched (111).
1. **A federated swarm's frame.** `--genesis-policy` (a file, written into the genesis
change with the roots, the voters and the users it starts with); a federated node
- is given its root, syncs under no policy it doesn't know, takes no remake yet,
- takes tokens and logins by key as its operator says, keeps ended sessions to
- itself, stamps as the policy says, and writes a member entry of the policy's shape
- and size. What the genesis change sets for the swarm as a whole is read from the
- policy. Tests: 97 to 100, 106, 110, and the policy's existing tests under a policy
- from the root.
+ is given its root, syncs under no policy it doesn't know, refuses a change that
+ isn't what Automerge itself writes, takes no remake yet, takes tokens and logins by
+ key as its operator says, keeps ended sessions to itself, stamps as the policy
+ says, and writes a member entry of the policy's shape and size. What the genesis
+ change sets for the swarm as a whole is read from the policy. Tests: 97 to 100,
+ 104, 107, 111, and the policy's existing tests under a policy from the root.
2. **Statements.** The users' registers (`create`, `key`, `node`, `vouch`, `release`);
the user ID, the epoch and what its signer saw in an envelope; nodes carrying for
users by their own word, and the rule for committers by it; nothing plain; the
@@ -1926,7 +1938,7 @@ their vectors. At every stage the existing tests pass untouched (110).
8. **Coming back.** The drop an operator asks for, a forked actor proven and shown
with what the roots' nodes hold, the budget and the share per party. Tests: 94, 101
to 103.
-9. **Bans** for those who follow. Tests: 107, 108.
+9. **Bans** for those who follow. Tests: 108, 109.
10. **The registry.** Import, export, and a federated swarm of the simulations with
the registry's kinds and a few hundred hosts. From here it can be tried: users,
hosts, names, a root that settles, names that become final. It isn't to be relied
@@ -1938,10 +1950,10 @@ their vectors. At every stage the existing tests pass untouched (110).
`GET /registry/decisions`. What is decided: a number, a user's first keys, the
names of a user that is out, whose a contested name is, a name the rules leave to
the voters. The simulations start from a root change naming several voters, as a
- remake's does. Tests: 16, 50, 54, 57 to 63, 65 to 72, 109.
+ remake's does. Tests: 16, 50, 54, 57 to 63, 65 to 72, 110.
12. **Versions.** The digest with every stamp, a node checking itself before it
writes; for every swarm, a node that speaks the wire version before its own, and a
- handshake that says which epochs its node keeps. Tests: 104, 105.
+ handshake that says which epochs its node keeps. Tests: 105, 106.
13. **Remakes.** The proposal with who votes and who the roots are; the coordinator
and the base, taking a remake up by its result, the snapshot every node builds,
what it leaves out and what can't be written again; carrying over, by every node
@@ -1951,7 +1963,7 @@ their vectors. At every stage the existing tests pass untouched (110).
its operator gave, and by none that peers advertise. Tests: 55, 56, 75 to 87.
14. **The policy by a decision.** The policy as a matter, a node that doesn't know it,
what it no longer covers: shown aside, taken away by its user only, dropped after
- a time, moved at a remake. Tests: 73, 74, 106.
+ a time, moved at a remake. Tests: 73, 74, 107.
15. **Going apart, and refusing.** A fork followed by an operator's word, with who
votes and who the roots are on its side. Refusing a decision: a node's bounds, the
epoch without the decision, what a node takes along. Tests: 64, 88 to 92. From
@@ -1999,6 +2011,14 @@ with the whole batch it came in (`DuplicateSeqNumber`); the change that made an
operation is found (`hash_for_opid`), so the change carrying a value is found from
the document.
+Measured upstream, with Automerge 0.12.0 alone, on histories of small writes to a map:
+
+* It applies a change that lists an actor none of its operations names, and then
+ gives back another change under that hash and saves a document that doesn't load;
+ where the document doesn't hold that actor, applying panics. It applies a change
+ whose first operation is numbered below its dependencies', and the save doesn't
+ load; one numbered 2^32 − 1, and the node's next write panics.
+
From the docs: a node under an unknown policy receives without judging; every node
takes a token any member signed, and lets in by key any user of the registry; where
a refused member shows; the cost of checking a signature; a node keeps the documents
@@ -2039,3 +2059,6 @@ Assumed, to be shown as it is built:
* The digest of the registry as it resolves is cheap enough to make with every stamp
at a registry's size, and to make at another node's stamp now and then.
* A version can speak the wire version before its own.
+* The three things asked of a change before Automerge sees it keep out every change
+ it applies and shouldn't. Six such changes were tried; operations on objects that
+ don't exist, and others crafted, weren't.