aboutsummaryrefslogtreecommitdiffstats
path: root/docs/federation-tests.md
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-16 14:38:16 +0000
committertv <tv@krebsco.de>2026-11-16 16:26:55 +0100
commitf2ed3e1e9e9c6199fb0bc3b1e2efb4eeb5f89b05 (patch)
tree4ccdd3eb355ec436dd5f9eb32b1fcc32780577bb /docs/federation-tests.md
parent0dde043f1e8c6e8c99a876b4d0dffdd499a9c961 (diff)
docs/federation-tests: how the store and the federation are tested
A plan, the contract the code is built to: the fold and the store tested as pure code, events in and verdicts and states out; a model written plainly from the design, which the store is checked against; every rule by its smallest scenarios; every attack row a test named by its table and number, and a test that every row has one; the promises as properties over generated histories, every order for small ones and seeded ones beyond, cut down before they are printed; the store on Automerge checked against the store in memory; simulations with an adversary node; fixed vectors for every encoding; fuzzing and mutants in longer runs. All of it behind the `federation` feature, by stage.
Diffstat (limited to 'docs/federation-tests.md')
-rw-r--r--docs/federation-tests.md149
1 files changed, 149 insertions, 0 deletions
diff --git a/docs/federation-tests.md b/docs/federation-tests.md
new file mode 100644
index 0000000..fa23ae7
--- /dev/null
+++ b/docs/federation-tests.md
@@ -0,0 +1,149 @@
+# Testing the store and the federation: a plan
+
+A plan, not what the code does: none of this is built. It says how the store
+([`store.md`](store.md)) and the federation ([`federation.md`](federation.md)) are
+tested, so that nothing in continuum breaks the federation, and no change made later
+breaks it apart. It is the contract the code is built to: a stage is done when its tests
+are.
+
+## What the tests rest on
+
+* **The core is pure.** The fold and the store in memory take events as values and give
+ verdicts and states: no network, no clock, no disk, no Automerge. Everything that can
+ be checked there is checked there. What Automerge and the network add is tested for
+ that alone: that they carry the events and change nothing the store holds.
+* **Every run is the same run.** Randomness comes from a seed, as
+ `what_passes_leaves_automerge_sound` takes it (SplitMix64); a failing test prints its
+ seed, and a seed that failed once stays as a fixed case.
+* **Every attack is a test.** Every row of the attack tables (`federation.md` and
+ `store.md`, Attacks) has a test named by its table and number (`federation_attack_12`,
+ `store_attack_23`), of the kind its row says. A test reads both tables from the
+ documents and checks that every row has its test, and that no test names a row that
+ isn't there.
+* **Every byte is fixed.** Every encoding the nodes must agree on has vectors, byte for
+ byte (Fixed bytes).
+* **Nothing else changes.** All of it is behind the `federation` feature. A build
+ without it runs the tests continuum has today, untouched, and passes them.
+
+## The harness
+
+* **Keys.** Ed25519 keys made from seeds, signing as `ssh-keygen -Y sign` does; a vector
+ checks one signature against `ssh-keygen` itself.
+* **Events.** A builder for every kind (writes, key sets, node lists, proposals, votes,
+ version events, checkpoints, roots, forks and merges), each from a party, a key and
+ its dependencies, encoded and signed as the design says; and for what is none: bytes
+ that aren't JCS, a field missing or more, another key, a broken signature, too large.
+* **Scenarios.** A scenario is a value: the parties and the first version, events by
+ name with their dependencies, which node is given which events in which order, and
+ what is expected (each node's verdicts, the current version, what counts, the
+ members). It prints as the builder calls that make it, so a failure found by
+ generating pastes in as a test.
+* **The model.** A second fold, written from `federation.md` as plainly as it can be: it
+ reads every history by adding all of its events anew, keeps no state, makes no
+ checkpoint. It is slow and short, and it is what the store is checked against: both
+ given the same events in the same order must give the same verdicts and the same
+ state.
+
+## The fold and the store, by example
+
+* **The rules.** Every rule of `federation.md` by the smallest scenarios that show it:
+ passing and dead, for every number of parties from 1 to 20; one yes at a time; which
+ version a node takes, and the current one; a party's keys and node list by their
+ `since`; a place's value; rules matching (`{party}`, `*`, `**`, first match); what
+ counts, item by item; checkpoints and what they keep; forks and merges.
+* **The attacks marked unit**, each by a scenario, its expectation the row's.
+* **The store** with a fold made for its tests, smaller than the federation's, for what
+ `store.md` checks (Tests): order, history, refusal, checkpoints.
+
+## Properties, over generated histories
+
+Histories are generated: a few parties (3 to 7), their keys, versions passing, honest
+writes and votes, and an adversary that signs anything its own keys or stolen ones can,
+on any dependencies, and puts out events no party signs. Each property is checked for
+every order of every history small enough (up to some 8 events, every order that puts
+each after its dependencies), and for seeded histories and orders beyond that.
+
+1. **Order.** The same events give the same state, in every order, on every node.
+2. **History.** Judging at a history gives what the model gives.
+3. **Refusal.** What is refused is refused with everything built on it.
+4. **What counts.** Every value that counts is signed by a key among its party's keys,
+ at a place the current version gives its party.
+5. **The policy.** Every version taken has two thirds of the parties of the version it
+ changes voting `true` in its history. Without a party voting twice, at most one
+ version changes a version, and nodes holding the same events read the same current
+ version.
+6. **Voting twice.** Wherever two versions change one, the tool over the votes names a
+ party with `true` and `false` on one proposal, or `true` on two of one version
+ neither dead.
+7. **Checkpoints.** Judging any event above a checkpoint's heads gives the verdict
+ judging it with the whole history gives; reading gives what the whole history reads
+ but for what counted no more; nodes moving at different times read the same once they
+ hold the same; moving refuses nothing that decided it.
+8. **Forks and merges.** A fork takes nothing of the stores it came from after its
+ heads, nor they of it; a merge's state is the values that count on each side at
+ places its version gives their party, and a key dropped on one side brings back
+ nothing until its party lists it again.
+9. **Votes a node casts by itself.** By its rules a node casts one yes at a time, never
+ `true` and `false` on one proposal, and, by a rule for checkpoints, backs nothing
+ that changes more.
+
+A failing history is cut down before it is printed: events are taken out, one at a time
+and with what is built on them, for as long as it still fails.
+
+## The store on Automerge
+
+* **The same as in memory.** The same events through the store on Automerge and the
+ store in memory give the same state, for seeded runs of changes, refusals, drops,
+ events put again, checkpoints, remakes, rejoins and writers forked.
+* **Changes that stay sound.** What a node of a swarm holding a store commits passes
+ screening on every other node, and what screening takes leaves Automerge sound: the
+ generated changes of `what_passes_leaves_automerge_sound` with the store's among them.
+* **The attacks marked unit** of `store.md`, each by crafted changes.
+
+## Simulations
+
+In [`src/simtest/`](../src/simtest/), whole nodes on the simulated network: swarms of 3
+to 7 parties, honest nodes and an adversary node the test drives. It sends different
+events and changes to different peers, withholds, crafts changes, decides two remakes
+for one epoch. The network partitions, delays and restarts nodes, by seed. Once it is
+quiet, the test checks that honest nodes holding the same events read the same, and what
+each row marked sim expects.
+
+## Fixed bytes
+
+Vectors for: an event and its ID, a signature, a version and its hash, a checkpoint and
+its ID, the genesis change of a federation's root, of a fork's and of a merge's, and a
+snapshot after a checkpoint. A vector that changes is a change of the federation, which
+takes its next number ([`federation.md`](federation.md), Changing the federation).
+
+## Fuzzing and mutants
+
+* **Fuzzing**, with `cargo fuzz` (a nightly compiler), outside `cargo quick`: the event
+ decoder and the fold's judging given any bytes, and screening given any change of a
+ swarm holding a store, refuse what isn't theirs and never panic. The vectors and
+ generated scenarios seed it; what it finds becomes a fixed case.
+* **Mutants**, with `cargo mutants`, now and then over the store and the fold: a change
+ to the code that no test notices is a test missing, or code that can go.
+
+## What runs where
+
+* `cargo quick`: the rules and attacks by example, the properties at small sizes and a
+ few hundred seeds, the store on Automerge by crafted changes and seeded runs, the
+ vectors, and the check that every row has its test.
+* `cargo sim`: the simulations.
+* Longer runs, by hand or on a schedule: the properties and the store on Automerge with
+ many more seeds (a count from the environment), fuzzing, mutants.
+
+## By stage
+
+1. **The store**: the harness, the store's own fold, its properties (order, history,
+ refusal, checkpoints).
+2. **The federation's fold**: the model, the rules and attacks marked unit, the
+ properties, the vectors of events, versions and checkpoints.
+3. **The store on Automerge**: the same as in memory, changes that stay sound, the
+ store's attacks marked unit, the simulations of a federation without forks or
+ remakes, the vectors of genesis changes.
+4. **Forks**, merges among them: their rows, properties and vectors.
+5. **Remakes**: their rows and simulations, and the vector of a snapshot after a
+ checkpoint.
+6. **The registry**: its rules by example, and the tools reading and writing kartei.