aboutsummaryrefslogtreecommitdiffstats
path: root/docs/federation-tests.md
blob: bc91fad2a38120594fd01431e6e2c0d94d794dc4 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
# Testing the store and the federation: a plan

A plan, built stage by stage (By stage): so far, the store's tests, the federation's
fold's, the store's on Automerge, the forks', and the remakes' (stages 1 to 5). 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 per table reads it from its
  document 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 and forks), 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.
* **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.** A fork takes nothing of the store it came from after its heads, nor that
   store of it; and its root keeps what counts at its heads with its version current.
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, nor heads that leave out what it held for a while.

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; and honest nodes
  hold one document, whatever each takes from it.
* **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; an event whose value holds names JCS sorts by their
UTF-16 units otherwise than by their bytes (one from U+E000 to U+FFFF beside one beyond
U+FFFF); events at federation 1's sizes and just past them; a signature, a version and
its hash, a checkpoint and its ID, the genesis change of a federation's root and of a
fork'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**: 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.