aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-12 21:58:34 +0000
committertv <tv@krebsco.de>2026-11-12 21:58:34 +0000
commit6bb6f99d744c7ef9aa18af33e0784f3d2536cbd8 (patch)
treecfcdd553ccb04fa561871d574d4f9d5475c19207
parentf95719a58800bedd5ee021d8bdfac30dc23956ef (diff)
federation: only changes Automerge itself writes
Automerge 0.12.0 applies changes no honest node writes: one that lists an actor none of its operations names, one whose first operation is numbered below its dependencies' or at 2^32 - 1. It then gives back another change than the one it was given, saves a document that doesn't load, or panics (measured with Automerge alone). A party that crafts one stops the honest nodes, where a forked actor only parts them. So a change is refused before Automerge sees it unless 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. An attack with its test, in the first stage.
-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.