summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-18 18:49:50 +0000
committertv <tv@krebsco.de>2026-11-18 20:29:41 +0100
commitc64fcc05d8c53bee99ab039bd709039afb730cdd (patch)
tree45baad78d7b92de42283be2954fc3f9b4dd6129d
parent598366b03679eac9d04f32d9194f3ba4ba9c3da8 (diff)
federation: a node stops at a version it doesn't read
A version event writing a proposal passed on the version a node reads, which doesn't read as a version there (of a later federation, using what a later continuum takes, or none at all), the node can't judge: `Fold::stops`. The store stops at it: it takes nothing and refuses nothing from then on, holding back whatever comes, that event first (`Offered::Stopped`), and keeps none of it across a restart, where it stops there again. One beside the version the node reads is refused of its own, as any other. Its operator has it drop that event (`POST /admin/events/drop`), or one it builds on: it is refused as dropped, or as built on what was, any version event writing that version with it, kept in the store file; the node judges what it held back and goes on under the version before. Allowed again, it stops there once more. The node logs the stop and its end; `GET /events` names the event, why, and how many it holds back (`stopped`); a put answers `stopped`, written into the document all the same; a node voting by itself casts nothing while stopped. The test fold's eras tagged `new` stop a store. Row 39 is tested (`federation_attack_39`); of rows 9, 10 and 48, a node stops at the version event.
-rw-r--r--docs/federation.md44
-rw-r--r--docs/guides/federation/proposing-and-voting.md5
-rw-r--r--docs/guides/federation/refusals-and-drops.md8
-rw-r--r--docs/guides/federation/upgrades.md11
-rw-r--r--docs/guides/federation/watching.md8
-rw-r--r--docs/guides/federation/when-things-go-wrong.md34
-rw-r--r--docs/guides/federation/writing-and-reading.md5
-rw-r--r--docs/openapi.yaml40
-rw-r--r--docs/store.md32
-rw-r--r--src/api/events.rs18
-rw-r--r--src/federation/attacks.rs17
-rw-r--r--src/federation/fold.rs21
-rw-r--r--src/federation/held.rs195
-rw-r--r--src/federation/properties.rs2
-rw-r--r--src/federation/store/memory.rs189
-rw-r--r--src/federation/store/mod.rs10
-rw-r--r--src/federation/store/testfold.rs12
17 files changed, 569 insertions, 82 deletions
diff --git a/docs/federation.md b/docs/federation.md
index 190f2b4..cef373b 100644
--- a/docs/federation.md
+++ b/docs/federation.md
@@ -242,12 +242,15 @@ application keeps party names apart from its spelling (no party named `wiki` whi
A version is none if a field is missing or more (but for `checkpoint`, which it may
leave out), if it gives a party more keys than a key set may hold or more nodes than a
node list, or a rule a path longer than a write's may be, or if it breaks any of the
-above. It can't pass, and a version event naming it is refused. A proposal is taken
-whatever it holds: whether it is a version is asked where a version event names it, so
-that nodes knowing more of what a version may say don't part from those knowing less. A
-node shows whether a proposal is a version by the federation it knows, and a party's
-client backs none that isn't: two thirds backing one that can never be written bind the
-federation to its version, as a yes binds ([Changing the policy](#changing-the-policy)).
+above. A proposal is taken whatever it holds: whether it is a version is asked where a
+version event names it, so that nodes knowing more of what a version may say don't part
+from those knowing less. A node can't tell a version that is none from one a later
+continuum reads: at a version event writing one that passed, it stops
+([Changing the federation](#changing-the-federation)). A node shows whether a proposal is
+a version by the federation it knows, and a party's client backs none that isn't: two
+thirds backing one that is none stop every node at its version event, until their
+operators have them drop it, and bind the federation to its version, as a yes binds
+([Changing the policy](#changing-the-policy)).
What the swarm's document holds beyond the events, and what a node takes at its API, is
the store's ([`store.md`](store.md), [On Automerge](store.md#on-automerge)).
@@ -296,8 +299,10 @@ Once a proposal passed on the current version, a node writes it as soon as it ho
passed, by a **version** event, `{"deps": […], "version": <hash>}`, which no party
signs: any node may write it, and the same version written by several is one (below).
Every node judges it at its history: the proposal proposed there on the version current
-there, passed there, and a version changing that one. A version takes effect where it is
-written: it is current at every history that holds it and no version after it.
+there, passed there, and a version changing that one; where the proposal is none to the
+node, it can't judge it ([Changing the federation](#changing-the-federation)). A version
+takes effect where it is written: it is current at every history that holds it and no
+version after it.
**A node takes a version only where it changes the version the node reads**, or is one
it took, written again. A version event of any other, valid at its history or not, it
@@ -519,7 +524,9 @@ rule for checkpoints, none for a version that changes more than its number, what
changes and its checkpoint, which it checks against the current one, nor for one whose
heads leave out what it held for a while ([Checkpoints](#checkpoints)). Where two
checkpoints are proposed at once, the votes split, as any do; a rule may vote `false` on
-the one it doesn't back, so that one dies and its backers are free.
+the one it doesn't back, so that one dies and its backers are free. A node that stopped
+at a version it doesn't read casts nothing, by itself or by hand, as what it reads is
+behind ([Changing the federation](#changing-the-federation)).
It signs with a key the party's version names, which the party keeps on that node, not
apart: one stolen there votes, and writes the party's key set and node list, as the
@@ -659,7 +666,7 @@ fold, with crafted events. *Sim*: a simulation. *Bench*: measured, not judged.
| 6 | A key set signed by a key the version doesn't name, or by one a later version replaced, at a history from before | Refused; or, written under a version before the one that named the party's keys anew, it counts no more | unit |
| 7 | A key set without the key that signed it | Counts: a set is checked where it is written | unit |
| 8 | A version event without the votes, or for a proposal not on the version current at its history | Refused at its history | unit |
-| 9 | A version with a field missing or more, a rule under `_continuum`, without a literal first segment, with `**` not last, `{party}` twice, or a writer that is no party of it | No version: can't pass; a version event naming it is refused | unit |
+| 9 | A version with a field missing or more, a rule under `_continuum`, without a literal first segment, with `**` not last, `{party}` twice, or a writer that is no party of it | No version: passed, a node stops at a version event writing it, as at one it doesn't know (39) | unit |
| 10 | A proposal naming a federation, or saying what, a node doesn't know | Taken as a proposal; asked where a version event names it | unit |
| 11 | `true` on two proposals of one version | The second refused, unless the first is dead at its history | unit |
| 12 | `true` on two proposals at once, from two nodes | Both taken; two versions changing one may be written; each node keeps the one it took and refuses the other; reported; the parties fork | unit, every order |
@@ -689,7 +696,7 @@ fold, with crafted events. *Sim*: a simulation. *Bench*: measured, not judged.
| 36 | A fork's version giving a party that didn't go keys of its founder's | Joiners holding the federation are told, party by party | unit |
| 37 | Two founders forking one version at one set of heads, or starting a federation from one first version | One store: its root is built byte for byte | unit |
| 38 | A group whose parties list no nodes forks | Its version names their node lists | unit |
-| 39 | A federation, or a version, a node doesn't know | It stops taking events | unit |
+| 39 | A federation, or a version, a node doesn't know | Of its root, it holds no store; at a version event writing one that passed, it stops: takes nothing and refuses nothing, until it runs a continuum that reads it, or its operator has it drop that event | unit |
| 40 | Two parties each writing a key set beside the other's vote, crossed | Nothing: votes go by their version's keys | unit |
| 41 | A federation's root with heads or events kept, or whose version lists no node | None; or nothing after it is taken, as no node is a member | unit |
| 42 | A version replacing every listed party's keys | The lists still count, each its party's until it writes another | unit |
@@ -698,7 +705,7 @@ fold, with crafted events. *Sim*: a simulation. *Bench*: measured, not judged.
| 45 | An honest node writes a version valid where it is written, on the side a node doesn't read | Refused, and reported apart; nothing is held against the node that put it | unit |
| 46 | A party's `true` and `false` on one proposal, both in a history | Both count there: a history holding more votes takes back no pass and no death | unit |
| 47 | A path whose `{party}` segment names no party (`names/r/foo`) | The `{party}` rule doesn't match; a later rule decides | unit |
-| 48 | Two thirds back a proposal that is no version | It can't be written, nor die; the federation is bound to its version. A node shows that it is none, and clients don't back it | unit |
+| 48 | Two thirds back a proposal that is no version | It can't die; nodes stop at a version event writing it, until their operators have them drop it (39); the federation is bound to its version. A node shows that it is none, and clients don't back it | unit |
| 49 | Keys voting twice part honest nodes | An operator has its node drop what it took and take the other side's; no fork. Where the version it took named a checkpoint, by a checkpoint its operator pins | sim |
| 50 | An honest party backs a second proposal once its first is dead; another party later signs `true` on the first too | It isn't named: its first proposal is dead by all the votes; the party with `true` and `false` on one is | unit |
| 51 | A node whose operator had it drop a version is sent it again, written anew by another node, or holds the votes that passed it | It refuses any event writing that version and writes it no more, until its operator says otherwise | unit |
@@ -805,14 +812,21 @@ and the Automerge version, whose encoding fixes a change's hash.
A change to the federation is a design like this one, with the next number. A swarm
moves to it by a version of its policy that names it (`"federation": 2`), which the
parties pass once their nodes run a continuum that knows it. A node that doesn't know
-the federation, or a version, its swarm has stops taking events and says so.
+the federation its swarm's root names holds no store, and says so. One that doesn't read
+a version that passed on the version it reads stops at the version event writing it, and
+says so: it takes nothing and refuses nothing from then on, and keeps none of it across a
+restart, until it runs a continuum that reads it, or its operator has it drop that event
+([`store.md`](store.md), [A node's own](store.md#a-nodes-own)). Dropped, the node refuses
+that event and any writing that version, as any version its operator had it drop, and
+goes on under the version before. One beside the version it reads, it refuses of its own,
+as any other ([Changing the policy](#changing-the-policy)).
A change that only has the federation take what it refused, and reads nothing it took
otherwise, keeps the number: the keys of type `ecdsa-sha2-nistp256` taken beside Ed25519
ones are such a change. It is rolled out first and used after: every node runs a
continuum that takes it before any party uses it. A node that doesn't refuses what uses
-it, a version naming such a key among them, and reads otherwise than the others until
-it does.
+it, and reads otherwise than the others until it does; at a version naming such a key,
+which it doesn't read, it stops, as above.
## The registry on it
diff --git a/docs/guides/federation/proposing-and-voting.md b/docs/guides/federation/proposing-and-voting.md
index e656083..12f8dfd 100644
--- a/docs/guides/federation/proposing-and-voting.md
+++ b/docs/guides/federation/proposing-and-voting.md
@@ -42,7 +42,10 @@ Party names are 1 to 64 of `A-Z a-z 0-9 . _ @ -`; a party has up to 16 keys and
nodes; a rule's path is a path as a write's is, its first segment literal and not
`_continuum`, `**` last only, `{party}` once at most, and its writer a party of the
version, `"{party}"` where the path holds it, or `false`. A version breaking any of that
-is none: it can't pass, and a party's client backs none.
+is none, and a party's client backs none; where two thirds pass it all the same, nodes
+stop at the version event writing it, until their operators have them drop it
+([`when-things-go-wrong.md`](when-things-go-wrong.md),
+[A node stopped](when-things-go-wrong.md#a-node-stopped)).
## Proposing
diff --git a/docs/guides/federation/refusals-and-drops.md b/docs/guides/federation/refusals-and-drops.md
index b32a819..1d29df1 100644
--- a/docs/guides/federation/refusals-and-drops.md
+++ b/docs/guides/federation/refusals-and-drops.md
@@ -40,8 +40,9 @@ file`).
## Dropping
-An operator may have the node drop events it took after its checkpoint, with everything
-built on them:
+An operator may have the node drop events it took after its checkpoint, or the version
+event it stopped at ([`when-things-go-wrong.md`](when-things-go-wrong.md),
+[A node stopped](when-things-go-wrong.md#a-node-stopped)), with everything built on them:
```sh
curl -u tv:secret -X POST -H 'Content-Type: application/json' \
@@ -50,7 +51,8 @@ curl -u tv:secret -X POST -H 'Content-Type: application/json' \
```
It answers what it dropped, in the order taken: those named, version events naming the
-version one of them names, and what is built on them. From then on the node refuses those
+version one of them names, and what is built on them; then the event it stopped at, if
+named, after which it takes again. From then on the node refuses those
events from whoever brings them, and any version event naming a version among them,
whoever wrote it anew; it writes none itself, though it holds the votes passing it, and
keeps so across restarts. Not what its checkpoint keeps
diff --git a/docs/guides/federation/upgrades.md b/docs/guides/federation/upgrades.md
index 570de19..f91143f 100644
--- a/docs/guides/federation/upgrades.md
+++ b/docs/guides/federation/upgrades.md
@@ -26,8 +26,11 @@ the snapshot, and the Automerge version, whose encoding fixes a change's hash. T
bytes are fixed by vectors that the tests check (`federation::vectors`).
There is one federation, 1. A node knows it alone: a version naming another is none to
-it, refused where a version event names it, with everything built on it. A proposal
-naming another is taken as a proposal, and a party's client backs none.
+it. Where one passes, the node stops at the version event writing it, taking nothing and
+refusing nothing, until it runs a continuum that knows it, or its operator has it drop
+that event ([`when-things-go-wrong.md`](when-things-go-wrong.md),
+[A node stopped](when-things-go-wrong.md#a-node-stopped)). A proposal naming another is
+taken as a proposal, and a party's client backs none.
A change to any of that is a federation of its own, with the next number, and its own
design. A swarm moves to it by a version naming it, which the parties pass once their
@@ -37,5 +40,5 @@ A change that only has the federation take what it refused, and reads nothing it
otherwise, keeps the number: `ecdsa-sha2-nistp256` keys beside Ed25519 ones. Roll it out
first, then use it: every party's operators upgrade their nodes, and only then does a
party name such a key in a version or a key set, or sign with one. A node not upgraded
-refuses what uses it and reads otherwise than the others: a version naming such a key is
-none to it, and it stays on the version before.
+refuses what uses it and reads otherwise than the others; at a version naming such a key,
+none to it, it stops, until it is upgraded.
diff --git a/docs/guides/federation/watching.md b/docs/guides/federation/watching.md
index f55005a..ec7ce6a 100644
--- a/docs/guides/federation/watching.md
+++ b/docs/guides/federation/watching.md
@@ -10,6 +10,11 @@ store, through its API and its log.
* **A version the node refused** (`own` in `GET /events/refused` not empty): keys voted
twice, and nodes may be apart. Act on it at once
([`when-things-go-wrong.md`](when-things-go-wrong.md)).
+* **A stop** (`stopped` in `GET /events` not `null`): a version passed that the node's
+ continuum doesn't read, and it takes nothing until upgraded, or until its operator has
+ it drop that version event
+ ([`when-things-go-wrong.md`](when-things-go-wrong.md),
+ [A node stopped](when-things-go-wrong.md#a-node-stopped)).
* **No store** (`404` from `GET /events` for longer than a start takes): the node can't
read its store ([`when-things-go-wrong.md`](when-things-go-wrong.md),
[A node doing less than it should](when-things-go-wrong.md#a-node-doing-less-than-it-should)).
@@ -37,6 +42,9 @@ At warn or error:
* `Refused an event its history takes, by what this node took before: kept so`: a version
the node refused, as above;
+* `The store stopped at an event this continuum can't judge: it takes none until it runs
+ one that does, or its operator has it drop that one`: a stop, as above; `The store
+ takes events again` once its operator had it drop that event;
* `This node isn't a member of its store, as it reads now: its party doesn't list it, and
members don't sync with it`;
* `The pinned checkpoint isn't in the document (yet): holding no store until it is`;
diff --git a/docs/guides/federation/when-things-go-wrong.md b/docs/guides/federation/when-things-go-wrong.md
index c79f24f..8c46e1d 100644
--- a/docs/guides/federation/when-things-go-wrong.md
+++ b/docs/guides/federation/when-things-go-wrong.md
@@ -1,8 +1,8 @@
# When things go wrong
-What to do when a node reports a version it refused, when a party voted twice, and when
-a node doesn't do what it should. The rules are the design's
-([`federation.md`](../../federation.md),
+What to do when a node reports a version it refused, when a party voted twice, when a
+node stopped at a version it doesn't read, and when a node doesn't do what it should. The
+rules are the design's ([`federation.md`](../../federation.md),
[Changing the policy](../../federation.md#changing-the-policy);
[`store.md`](../../store.md), [A node's own](../../store.md#a-nodes-own)).
@@ -65,6 +65,34 @@ or with its keys named anew ([`forking-and-following.md`](forking-and-following.
Tell the other parties what your node took and what it refused, and send them your
record.
+## A node stopped
+
+A node stops at a version event writing a version that passed on the version it reads,
+which its continuum doesn't read: of a later federation, using what a later continuum
+takes, or none at all. It takes nothing and refuses nothing from then on, and votes
+nothing by itself or by hand; what is put through it, it still writes into the document
+(`stopped` when put). Its log says so (`The store stopped at an event this continuum
+can't judge`), and `GET /events` names the event, why, and how many it holds back:
+
+```sh
+curl -s -u tv:secret localhost:3000/events | jq .stopped
+# {"heldBack":12,"id":"9a1e…","why":"version 3c0f… passed, and doesn't read as one…"}
+```
+
+Upgrade the node to a continuum that reads it: restarted, it reads its store anew and
+takes it. Where none does (two thirds passed a proposal that is no version), have the node
+drop that event: it goes on under the version before, refuses the event and any writing
+that version, and keeps so (`--store-file`):
+
+```sh
+curl -u tv:secret -X POST -H 'Content-Type: application/json' \
+ --data '{"ids": ["<the event it stopped at>"]}' localhost:3000/admin/events/drop
+# {"dropped":["9a1e…"]}
+```
+
+Allowed again (`/admin/events/allow`), it stops there once more. A node that stopped
+keeps none of it in its store file: restarted, it stops there again.
+
## A node doing less than it should
* **It holds no store** (`404` from `GET /events`): it hasn't read its document yet, its
diff --git a/docs/guides/federation/writing-and-reading.md b/docs/guides/federation/writing-and-reading.md
index 3dd0578..057aad7 100644
--- a/docs/guides/federation/writing-and-reading.md
+++ b/docs/guides/federation/writing-and-reading.md
@@ -33,7 +33,10 @@ object, the whole event up to 256 KiB. `null` empties the place.
The client signs the write with its key (`--key`), on the heads its node shows, which
are what the party read; records it (`--record`), to sign it again after a move; and puts
it through the node. The node answers what became of it: `taken`, `held` (taken before),
-or `waiting` for an event it builds on that the node doesn't hold yet.
+`waiting` for an event it builds on that the node doesn't hold yet, or `stopped`: the
+node stopped at a version it doesn't read, and holds it back
+([`when-things-go-wrong.md`](when-things-go-wrong.md),
+[A node stopped](when-things-go-wrong.md#a-node-stopped)).
A write counts while the key that signed it is among its party's keys: those of its key
set, or, while it has written none, those its version names
diff --git a/docs/openapi.yaml b/docs/openapi.yaml
index 3dbcd62..e1e602a 100644
--- a/docs/openapi.yaml
+++ b/docs/openapi.yaml
@@ -1419,9 +1419,12 @@ paths:
description: |
The store's ID (its root's), its checkpoint's ID, its heads (what a new event
builds on) and how many events it took after its checkpoint, as this node reads
- it now; the party this node is of (`party`, `--store-party`), and whether it
- votes for it by itself (`votesByItself`), and so casts votes by hand
- (`POST /admin/events/vote`).
+ it now; the event it stopped at, if any (`stopped`: a version event writing a
+ version that passed, which this continuum doesn't read), why, and how many
+ events it holds back since, that one among them, taking nothing and refusing
+ nothing until upgraded or told to drop it (`/admin/events/drop`); the party this
+ node is of (`party`, `--store-party`), and whether it votes for it by itself
+ (`votesByItself`), and so casts votes by hand (`POST /admin/events/vote`).
responses:
'200':
description: The store.
@@ -1429,7 +1432,7 @@ paths:
application/json:
schema:
type: object
- required: [store, checkpoint, heads, taken, party, votesByItself]
+ required: [store, checkpoint, heads, taken, stopped, party, votesByItself]
properties:
store:
type: string
@@ -1441,6 +1444,16 @@ paths:
type: string
taken:
type: integer
+ stopped:
+ type: [object, 'null']
+ required: [id, why, heldBack]
+ properties:
+ id:
+ type: string
+ why:
+ type: string
+ heldBack:
+ type: integer
party:
type: [string, 'null']
votesByItself:
@@ -1454,7 +1467,8 @@ paths:
Puts an event, the body as its bytes, whoever signed it: offered to the store,
and written into the document at its ID (the SHA-256 of its bytes) unless the
store refuses it. `event` says what became of it: `taken`, `held` (taken
- before), or `waiting` for what it builds on.
+ before), `waiting` for what it builds on, or `stopped`: held back, the store
+ stopped at a version it doesn't read (`stopped` in `GET /events`).
requestBody:
required: true
content:
@@ -1474,7 +1488,7 @@ paths:
type: string
event:
type: string
- enum: [taken, held, waiting]
+ enum: [taken, held, waiting, stopped]
'404':
$ref: '#/components/responses/Error'
'422':
@@ -1680,12 +1694,14 @@ paths:
tags: [Events]
summary: Drop events this node took
description: |
- Drops events the store took after its checkpoint, version events naming the
- version one of them names, and everything built on them: this node refuses them
- from then on, from whoever brings them, and any version event naming a version
- among them, and keeps so across restarts (`--store-file`), until it is told
- otherwise (`/admin/events/allow`). Not what the checkpoint keeps or holds by
- ID. Answers what it dropped, in the order taken. Needs `write` on `_continuum`.
+ Drops events the store took after its checkpoint, or the version event it
+ stopped at (`stopped` in `GET /events`), version events naming the version one
+ of them names, and everything built on them: this node refuses them from then
+ on, from whoever brings them, and any version event naming a version among
+ them, and keeps so across restarts (`--store-file`), until it is told otherwise
+ (`/admin/events/allow`). Not what the checkpoint keeps or holds by ID. Answers
+ what it dropped, in the order taken, then the event it stopped at, after which
+ it takes again. Needs `write` on `_continuum`.
requestBody:
required: true
content:
diff --git a/docs/store.md b/docs/store.md
index 3192389..b598539 100644
--- a/docs/store.md
+++ b/docs/store.md
@@ -114,6 +114,8 @@ A fold says, of its events:
its group ([Members](#members));
* where it needs to, **what a node refuses that its history takes**, by what the node
took before ([A node's own](#a-nodes-own));
+* where it needs to, **what a node can't judge** that it would take: an event only a fold
+ knowing more reads, where the node stops ([A node's own](#a-nodes-own));
* where it needs to, **what an event writes that others may write alike**, so that a node
dropping it refuses them all (the federation: a version event's version).
@@ -126,10 +128,16 @@ pub trait Fold {
const LARGEST: usize;
/// What the event builds on; `None` where its bytes are none of this fold's events.
fn dependencies(event: &[u8]) -> Option<Vec<Id>>;
- /// Whether the event is taken where its history reads as `at`.
+ /// Whether the event is taken where its history reads as `at`, as far as it reads it.
fn judge(at: &Self::State, id: &Id, event: &[u8]) -> Result<(), Refused>;
/// Adds the event, whose dependencies are added already.
fn add(state: &mut Self::State, id: &Id, event: &[u8]);
+ /// Why a node whose store reads as `now` can't judge an event its history doesn't
+ /// refuse, that it would take, where it can't: the store stops at it.
+ fn stops(_at: &Self::State, _now: &Self::State, _id: &Id, _event: &[u8])
+ -> Option<String> {
+ None
+ }
/// Whether a node whose store reads as `now` takes an event its history takes.
fn keeps(_now: &Self::State, _id: &Id, _event: &[u8]) -> bool {
true
@@ -169,10 +177,10 @@ which its tests check ([Tests](#tests)).
## What is promised
1. **Every node takes an event or none**, but for what a fold has a node refuse by what
- it took, what an operator has its node drop ([A node's own](#a-nodes-own)), and what
- moving to a checkpoint refuses. An event is judged at its history, which its ID fixes,
- so every node judges it alike, whenever and from whomever it comes. An event refused is
- refused with everything built on it.
+ it took, what an operator has its node drop, what a node stops at
+ ([A node's own](#a-nodes-own)), and what moving to a checkpoint refuses. An event is
+ judged at its history, which its ID fixes, so every node judges it alike, whenever and
+ from whomever it comes. An event refused is refused with everything built on it.
2. **Nodes that hold the same checkpoint and the same events after it read the same
state**, whatever order the events came in, and whatever carried them.
3. **Nothing underneath adds an event or takes one away.** What a node holds is what it
@@ -203,6 +211,16 @@ so, and its operator's drops, in a file of its own, across restarts. No peer's
word moves a node; its operator's does. A node that refuses what another took holds other
events, and reads its own state from them; two that hold the same read the same.
+A fold may have a node **stop** at an event it can't judge, that it would take: one only
+a fold knowing more reads (the federation's node: a version event writing a version
+that passed, which its continuum doesn't read,
+[Changing the federation](federation.md#changing-the-federation)). The node takes
+nothing and refuses nothing from then on: it holds back whatever comes, that event first,
+keeps none of it across a restart, where it stops there again, and reports it, until it
+runs a continuum that reads the event, or its operator has it drop the event, or one it
+builds on. Then it refuses it, as dropped or as built on what was, with everything built
+on it, and judges what it held back. What it took before it stopped, it holds as it did.
+
## Forks
A **fork** is a store whose root is a checkpoint at heads of another, which its maker
@@ -335,7 +353,9 @@ coordinator): two remakes at one base are two epochs.
checkpoint forgot, and events nobody takes, leave the document here. A node that moved
to a later checkpoint since the base builds the snapshot as one that didn't, as both
read the document; nodes that read the store differently at the base (the sides of
- keys that voted twice, in the federation) build different snapshots, and part here.
+ keys that voted twice, in the federation, or a node that stopped, holding back what
+ the others took: [A node's own](#a-nodes-own)) build different snapshots, and part
+ here.
* **A node follows a decision** whichever node coordinated it: a decision reaches it
only through a member, which could decide one itself, and a remake changes no event.
It builds the snapshot itself, from a base it holds, and checks it against the
diff --git a/src/api/events.rs b/src/api/events.rs
index 04dc77e..bd6db70 100644
--- a/src/api/events.rs
+++ b/src/api/events.rs
@@ -81,16 +81,21 @@ fn why(refusal: &Refusal) -> String {
}
/// `GET /events`: the store's ID, its checkpoint's, its heads, how many events it took
-/// after its checkpoint, the node's party, and whether the node votes for it by itself.
+/// after its checkpoint, the event it stopped at, if any, the node's party, and whether
+/// the node votes for it by itself.
async fn summary(State(state): State<AppState>) -> Response {
let party = state.holding.party().map(str::to_owned);
let votes = state.holding.votes_by_itself();
with_store(&state, |store| {
+ let stopped = store
+ .stopped()
+ .map(|(id, why, held)| json!({"id": id.to_string(), "why": why, "heldBack": held}));
json!({
"store": store.id().to_string(),
"checkpoint": Id::of(store.checkpoint()).to_string(),
"heads": ids(store.heads()),
"taken": store.taken().len(),
+ "stopped": stopped,
"party": party,
"votesByItself": votes,
})
@@ -218,7 +223,7 @@ async fn refused(State(state): State<AppState>) -> Response {
/// `POST /events`: puts an event, the request's body, whoever signed it: offered to the
/// store, and written into the document at its ID unless the store refuses it. Taken,
-/// held already, or waiting for what it builds on.
+/// held already, waiting for what it builds on, or held back, the store stopped.
async fn put(
State(state): State<AppState>,
Extension(AuthenticatedUser(user)): Extension<AuthenticatedUser>,
@@ -238,6 +243,7 @@ async fn put(
Some(Offered::Taken(_)) => "taken",
Some(Offered::Held) => "held",
Some(Offered::Waiting) => "waiting",
+ Some(Offered::Stopped) => "stopped",
};
match crate::federation::held::write(&state, Some(user), bytes).await {
Ok(()) => Json(json!({"id": id.to_string(), "event": became})).into_response(),
@@ -359,10 +365,10 @@ async fn check_fork(State(state): State<AppState>, body: Bytes) -> Response {
}
}
-/// `POST /admin/events/drop`: drops events the store took after its checkpoint, with
-/// everything built on them, as the operator has the node do: it refuses them from then
-/// on, from whoever brings them, and keeps so across restarts (`--store-file`). What it
-/// dropped, in the order taken.
+/// `POST /admin/events/drop`: drops events the store took after its checkpoint, or the
+/// one it stopped at, with everything built on them, as the operator has the node do: it
+/// refuses them from then on, from whoever brings them, and keeps so across restarts
+/// (`--store-file`). What it dropped, in the order taken, then the one it stopped at.
async fn drop_taken(State(state): State<AppState>, Json(named): Json<Named>) -> Response {
let named = match named.ids() {
Ok(ids) => ids,
diff --git a/src/federation/attacks.rs b/src/federation/attacks.rs
index 316f5eb..db047c9 100644
--- a/src/federation/attacks.rs
+++ b/src/federation/attacks.rs
@@ -14,7 +14,7 @@ use super::store::{Fold, Id};
use super::version::Version;
/// Rows whose tests wait: what a node or a party's client doesn't do yet, and flooding.
-const LATER: &[u32] = &[30, 39, 63, 68];
+const LATER: &[u32] = &[30, 63, 68];
fn tv() -> Party {
Party::new("tv", 1)
@@ -71,6 +71,14 @@ impl Fed {
assert!(matches!(why, Refusal::Judged(_)), "{why:?}");
}
+ /// An event the store stops at (`Fold::stops`), and its operator has it drop.
+ fn stops(&mut self, bytes: Vec<u8>) {
+ let id = Id::of(&bytes);
+ assert_eq!(self.store.offer(bytes), Offered::Stopped);
+ assert_eq!(self.store.stopped().map(|(at, ..)| *at), Some(id));
+ assert_eq!(self.store.drop_taken(&[id]), Ok(vec![id]));
+ }
+
fn value(&self, path: &str) -> Option<Json> {
self.store.state().value(path).cloned()
}
@@ -277,7 +285,8 @@ fn federation_attack_9() {
let proposal = fed.take(tv.propose(&[root], &next.json()));
let yes = fed.take(tv.vote(&[proposal], on, next.hash(), true));
let also = fed.take(lass.vote(&[proposal], on, next.hash(), true));
- fed.judged(harness::version_event(&[yes, also], next.hash()));
+ // None to this continuum, as one it doesn't know: it stops at it.
+ fed.stops(harness::version_event(&[yes, also], next.hash()));
// Free the backers for the next one: nays make it dead.
let no = fed.take(makefu().vote(&[proposal], on, next.hash(), false));
fed.take(tv.vote(&[no], on, next.hash(), false));
@@ -299,7 +308,7 @@ fn federation_attack_10() {
let hash = Id::of(&unknown.bytes());
let yes = fed.take(tv.vote(&[proposal], on, hash, true));
let also = fed.take(lass.vote(&[proposal], on, hash, true));
- fed.judged(harness::version_event(&[yes, also], hash));
+ fed.stops(harness::version_event(&[yes, also], hash));
}
#[test]
@@ -921,7 +930,7 @@ fn federation_attack_48() {
let proposal = fed.take(tv.propose(&[root], &bad.json()));
let yes = fed.take(tv.vote(&[proposal], on, bad.hash(), true));
let also = fed.take(lass.vote(&[proposal], on, bad.hash(), true));
- fed.judged(harness::version_event(&[yes, also], bad.hash()));
+ fed.stops(harness::version_event(&[yes, also], bad.hash()));
// It can't die either: its backers are bound.
let next = fed.first.after(on);
let other = fed.take(makefu().propose(&[root], &next.json()));
diff --git a/src/federation/fold.rs b/src/federation/fold.rs
index f37c213..fddedc0 100644
--- a/src/federation/fold.rs
+++ b/src/federation/fold.rs
@@ -484,7 +484,8 @@ impl State {
}
/// Whether a version event is taken here, at its history, `current` the version current
- /// there.
+ /// there. One whose proposal passed but doesn't read as a version, it doesn't refuse:
+ /// a later continuum may read it (`Fold::stops`).
fn judge_version(&self, deps: &[Id], hash: &Id, current: &Version) -> Result<(), Refused> {
if !self.proposed_on(hash, &current.hash) {
return Err(Refused::new(
@@ -494,8 +495,9 @@ impl State {
if !self.tally(current, hash).passed {
return Err(Refused::new("its proposal hasn't passed at its history"));
}
- let next = Version::read(&self.proposed[hash])
- .map_err(|why| Refused::new(format!("no version: {why}")))?;
+ let Ok(next) = Version::read(&self.proposed[hash]) else {
+ return Ok(());
+ };
next.changes_validly(Some(current))
.map_err(|why| Refused::new(format!("no version: {why}")))?;
if let Some(heads) = &next.checkpoint {
@@ -627,6 +629,19 @@ impl Fold for Federation {
state.events.insert(*id, Held { event, under });
}
+ /// A version event whose proposal passed at its history but doesn't read as a version
+ /// here, changing the version the node reads: one a later continuum may read
+ /// (`docs/federation.md`, Changing the federation). Beside the version the node reads,
+ /// it is refused as any other (`keeps`).
+ fn stops(at: &State, now: &State, _id: &Id, bytes: &[u8]) -> Option<String> {
+ let Some(Event::Version { version, .. }) = Event::read_taken(bytes) else {
+ return None;
+ };
+ let why = Version::read(at.proposed.get(&version)?).err()?;
+ (at.current().hash == now.current().hash)
+ .then(|| format!("version {version} passed, and doesn't read as one here: {why}"))
+ }
+
fn keeps(now: &State, _id: &Id, bytes: &[u8]) -> bool {
match Event::read_taken(bytes) {
Some(Event::Version { version, .. }) => {
diff --git a/src/federation/held.rs b/src/federation/held.rs
index 200323e..5155573 100644
--- a/src/federation/held.rs
+++ b/src/federation/held.rs
@@ -135,6 +135,8 @@ struct Inner {
none: Option<Id>,
/// The pinned checkpoint not found in the document, logged once.
unfound: bool,
+ /// The event the store stopped at, logged once (`Fold::stops`).
+ stopped: Option<Id>,
/// The refused changes looked at, of those screening keeps (`look`).
looked: HashSet<ChangeHash>,
/// When, by its own clock, the node took each event its store took after its
@@ -331,7 +333,7 @@ impl Holding {
refused += 1;
info!(event = %id, why = ?why, "The store refuses an event the document holds");
}
- Offered::Held | Offered::Waiting => {}
+ Offered::Held | Offered::Waiting | Offered::Stopped => {}
}
}
if taken > 0 || refused > 0 {
@@ -341,11 +343,23 @@ impl Holding {
}
/// After the store changed: what the node keeps of its own, written to its file where
- /// it changed, and the members, as the store reads now.
+ /// it changed, and the members, as the store reads now; whether it stopped, logged.
fn settle(&self, inner: &mut Inner) {
let Some(store) = &inner.store else {
return;
};
+ let stopped = store.stopped().map(|(id, why, _)| (*id, why));
+ if stopped.map(|(id, _)| id) != inner.stopped {
+ match stopped {
+ Some((id, why)) => error!(
+ event = %id,
+ why = %why,
+ "The store stopped at an event this continuum can't judge: it takes none until it runs one that does, or its operator has it drop that one"
+ ),
+ None => warn!("The store takes events again"),
+ }
+ inner.stopped = stopped.map(|(id, _)| id);
+ }
let now = Instant::now();
let checkpoint = Id::of(store.checkpoint());
if inner.at_checkpoint.map(|(at, _)| at) != Some(checkpoint) {
@@ -385,9 +399,10 @@ impl Holding {
Some(offered)
}
- /// Drops `ids`, events the store took after its checkpoint, with everything built on
- /// them, as its operator has the node do: it refuses them from then on, and keeps so
- /// (`docs/store.md`, A node's own). What it dropped, in the order taken.
+ /// Drops `ids`, events the store took after its checkpoint or the one it stopped at,
+ /// with everything built on them, as its operator has the node do: it refuses them from
+ /// then on, and keeps so (`docs/store.md`, A node's own). What it dropped, in the order
+ /// taken, then the one it stopped at.
pub(crate) fn drop_taken(&self, ids: &[Id]) -> Option<Result<Vec<Id>, Refused>> {
let mut inner = self.inner.lock_or_recover();
let dropped = inner.store.as_mut()?.drop_taken(ids);
@@ -657,6 +672,7 @@ impl Holding {
/// What it signs now, voting by itself by its operator's rules (`vote::decide`), or by
/// hand (`hand`, `vote::by_hand`): recorded, the record written, and offered to the
/// store; the events, to put into the document. By hand, why not where it isn't.
+ /// Nothing while its store is stopped.
fn sign(&self, hand: Option<(Id, bool)>) -> Result<Vec<Vec<u8>>, String> {
let (Some(voter), Some(party)) = (&self.voter, &self.party) else {
return Err("this node doesn't vote for its party".to_owned());
@@ -668,6 +684,15 @@ impl Holding {
let (Some(store), Some(record)) = (&inner.store, &inner.record) else {
return Err("this node holds no store".to_owned());
};
+ // What it reads is behind what passed: it casts nothing.
+ if let Some((id, ..)) = store.stopped() {
+ return match hand {
+ None => Ok(Vec::new()),
+ Some(_) => Err(format!(
+ "its store stopped at {id}: it votes once it takes events again"
+ )),
+ };
+ }
let now = Instant::now();
let held = |id: &Id| inner.taken_at.get(id).map(|at| now.duration_since(*at));
let seen = Seen {
@@ -1676,6 +1701,166 @@ mod tests {
assert_eq!(current(&restarted), Some(one.hash()));
}
+ /// Row 39 (`docs/federation.md`): a version of a federation this continuum doesn't
+ /// know passed, and a version event writes it: the node stops there, taking nothing
+ /// and refusing nothing of what comes after, and writes none of it to its file, before
+ /// or after a restart. Its operator has it drop that event: it takes again, under the
+ /// version before, and keeps so; allowed again, it stops there once more. A root of a
+ /// federation it doesn't know, it holds no store of.
+ #[test]
+ fn federation_attack_39() {
+ let (tv, lass, makefu) = (
+ Party::new("tv", 1),
+ Party::new("lass", 2),
+ Party::new("makefu", 3),
+ );
+ let first = Spec::first(&[&tv, &lass, &makefu], &[]);
+ let root = first.root();
+ let on = first.hash();
+ let later = |json: &[u8]| {
+ String::from_utf8(json.to_vec())
+ .unwrap()
+ .replace(r#""federation":1"#, r#""federation":2"#)
+ };
+ let unknown =
+ crate::federation::jcs::read(later(&first.after(on).json().bytes()).as_bytes())
+ .unwrap();
+ let hash = Id::of(&unknown.bytes());
+ let proposal = tv.propose(&[Id::of(&root)], &unknown);
+ let votes = [&tv, &lass].map(|party| party.vote(&[Id::of(&proposal)], on, hash, true));
+ let written = harness::version_event(&[Id::of(&votes[0]), Id::of(&votes[1])], hash);
+ let stopped_at = Id::of(&written);
+ let beside = tv.write(&[Id::of(&votes[0])], "home/tv/a", harness::str("1"));
+ let after = tv.write(&[stopped_at], "home/tv/b", harness::str("1"));
+ let mut doc = events::started(Federation::NAME, &root, &[]).unwrap();
+ for event in [&proposal].into_iter().chain(&votes).chain([&written]) {
+ put(&mut doc, event);
+ }
+ let stopped = |holding: &Holding| {
+ holding.with(|store| store.stopped().map(|(id, _, held)| (*id, held)))
+ };
+ let current = |holding: &Holding| holding.with(|store| store.state().current().hash);
+ let taken = |holding: &Holding, event: &[u8]| {
+ holding.with(|store| store.taken().contains(&Id::of(event)))
+ };
+ let dir = crate::files::scratch_dir("held-attack-39");
+ let path = dir.join("store.json");
+ let files = Arc::new(Files::default());
+ let holding = Holding::open(Some(path.clone()), Arc::clone(&files), None, None).unwrap();
+ read(&holding, &doc, 0);
+ assert_eq!(stopped(&holding), Some(Some((stopped_at, 1))));
+ put(&mut doc, &beside);
+ put(&mut doc, &after);
+ read(&holding, &doc, 0);
+ assert_eq!(stopped(&holding), Some(Some((stopped_at, 3))));
+ assert_eq!(
+ holding.offer(tv.write(&[Id::of(&root)], "home/tv/c", harness::str("1"))),
+ Some(Offered::Stopped)
+ );
+ assert_eq!(holding.passed(), Vec::<Vec<u8>>::new());
+ assert_eq!(holding.with(|store| store.refused().count()), Some(0));
+ assert!(!path.exists());
+ // Restarted: it stops there again.
+ let restarted = Holding::open(Some(path.clone()), Arc::clone(&files), None, None).unwrap();
+ read(&restarted, &doc, 0);
+ assert_eq!(
+ stopped(&restarted).flatten().map(|(id, _)| id),
+ Some(stopped_at)
+ );
+ // Dropped: it takes again, under the version before, and refuses what is built on
+ // that event; it writes no version event naming that version.
+ assert_eq!(
+ restarted.drop_taken(&[stopped_at]),
+ Some(Ok(vec![stopped_at]))
+ );
+ assert_eq!(stopped(&restarted), Some(None));
+ assert_eq!(current(&restarted), Some(on));
+ assert_eq!(taken(&restarted, &beside), Some(true));
+ assert_eq!(
+ restarted.with(|store| store.refusal(&Id::of(&after)).cloned()),
+ Some(Some(Refusal::BuiltOn(stopped_at)))
+ );
+ assert_eq!(restarted.passed(), Vec::<Vec<u8>>::new());
+ // Kept so across a restart.
+ let again = Holding::open(Some(path.clone()), Arc::clone(&files), None, None).unwrap();
+ read(&again, &doc, 0);
+ assert_eq!(stopped(&again), Some(None));
+ assert_eq!(current(&again), Some(on));
+ assert_eq!(taken(&again, &beside), Some(true));
+ // Allowed again: it stops there once more.
+ assert!(again.allow(&[stopped_at]));
+ read(&again, &doc, 0);
+ assert_eq!(
+ stopped(&again).flatten().map(|(id, _)| id),
+ Some(stopped_at)
+ );
+
+ // A root of a federation it doesn't know.
+ let unknown_root = later(&root).into_bytes();
+ assert_ne!(unknown_root, root);
+ let doc = events::started(Federation::NAME, &unknown_root, &[]).unwrap();
+ let holding = Holding::default();
+ read(&holding, &doc, 0);
+ assert!(holding.with(|_| ()).is_none());
+ }
+
+ /// A node voting by itself whose store stopped casts nothing, by itself or by hand:
+ /// what it reads is behind what passed.
+ #[test]
+ fn a_node_whose_store_stopped_votes_nothing() {
+ let (tv, lass, makefu) = (
+ Party::new("tv", 1),
+ Party::new("lass", 2),
+ Party::new("makefu", 3),
+ );
+ let first = Spec::first(&[&tv, &lass, &makefu], &[]);
+ let root = first.root();
+ let on = first.hash();
+ let mut none = first.after(on);
+ none.rules
+ .push(("_continuum/x".to_owned(), harness::str("tv")));
+ let next = first.after(on);
+ let proposal = tv.propose(&[Id::of(&root)], &none.json());
+ let other = lass.propose(&[Id::of(&root)], &next.json());
+ let votes =
+ [&tv, &lass].map(|party| party.vote(&[Id::of(&proposal)], on, none.hash(), true));
+ let written = harness::version_event(&[Id::of(&votes[0]), Id::of(&votes[1])], none.hash());
+ let mut doc = events::started(Federation::NAME, &root, &[]).unwrap();
+ for event in [&proposal, &other]
+ .into_iter()
+ .chain(&votes)
+ .chain([&written])
+ {
+ put(&mut doc, event);
+ }
+ let dir = crate::files::scratch_dir("held-stopped-votes");
+ let record = dir.join("makefu.json");
+ let version = Version::read(&first.json()).unwrap();
+ let mut begun = Record::begin(Id::of(&root), "makefu", &version);
+ begun.began = Id::of(b"before the federation").to_string();
+ begun.save(&record).unwrap();
+ let holding = Holding::open(
+ None,
+ Arc::new(Files::default()),
+ None,
+ Some("makefu".into()),
+ )
+ .unwrap()
+ .voting(Some(Voter {
+ key: makefu.key.clone(),
+ record,
+ rules: Rules::default(),
+ }));
+ read(&holding, &doc, 0);
+ assert!(holding.with(|store| store.stopped().is_some()).unwrap());
+ assert_eq!(holding.act(), Vec::<Vec<u8>>::new());
+ let why = holding.vote_by_hand(next.hash(), true).unwrap_err();
+ assert!(why.contains("stopped"), "{why}");
+ // Dropped: it votes again.
+ holding.drop_taken(&[Id::of(&written)]).unwrap().unwrap();
+ assert!(holding.vote_by_hand(next.hash(), true).is_ok());
+ }
+
// The store's attack rows (`docs/store.md`, Attacks) read from a document.
/// tv's federation, its root, and a document started from it.
diff --git a/src/federation/properties.rs b/src/federation/properties.rs
index 61d6adc..d42509b 100644
--- a/src/federation/properties.rs
+++ b/src/federation/properties.rs
@@ -297,6 +297,8 @@ fn verdict(offered: &Offered) -> Verdict {
Offered::Held => Verdict::Held,
Offered::Waiting => Verdict::Waiting,
Offered::Refused(_) => Verdict::Refused,
+ // The harness proposes only versions this continuum reads: none stops the store.
+ Offered::Stopped => unreachable!("the store stopped"),
}
}
diff --git a/src/federation/store/memory.rs b/src/federation/store/memory.rs
index 7527a44..f721b47 100644
--- a/src/federation/store/memory.rs
+++ b/src/federation/store/memory.rs
@@ -34,6 +34,9 @@ pub(crate) enum Offered {
Waiting,
/// Refused, and why; what waited on it is refused with it.
Refused(Refusal),
+ /// Held back, neither taken nor refused: the store stopped at an event it can't judge
+ /// (`Fold::stops`), this one or one before.
+ Stopped,
}
/// A checkpoint built: its bytes, and the events it keeps, by ID.
@@ -74,6 +77,12 @@ pub(crate) struct Store<F: Fold> {
/// What a move to a checkpoint forgot that came before its heads: held as accounted
/// for, and nothing after the checkpoint builds on it.
forgotten: HashSet<Id>,
+ /// The event the store stopped at, and why (`Fold::stops`); and what it holds back
+ /// since, that one first, in the order offered: it takes nothing and refuses nothing
+ /// until its operator has it drop that one.
+ stopped: Option<(Id, String)>,
+ held_back: Vec<(Id, Event)>,
+ holding_back: HashSet<Id>,
}
impl<F: Fold> Store<F> {
@@ -117,6 +126,9 @@ impl<F: Fold> Store<F> {
refused: HashMap::new(),
writes: HashMap::new(),
forgotten: HashSet::new(),
+ stopped: None,
+ held_back: Vec::new(),
+ holding_back: HashSet::new(),
})
}
@@ -202,6 +214,14 @@ impl<F: Fold> Store<F> {
self.waiting.contains_key(id)
}
+ /// The event the store stopped at, and why, where it stopped (`Fold::stops`); and how
+ /// many events it holds back, that one among them.
+ pub(crate) fn stopped(&self) -> Option<(&Id, &str, usize)> {
+ self.stopped
+ .as_ref()
+ .map(|(id, why)| (id, why.as_str(), self.held_back.len()))
+ }
+
/// What a new event builds on: the events nothing else held builds on, or the
/// checkpoint's heads where nothing came after it.
pub(crate) fn heads(&self) -> Vec<Id> {
@@ -240,6 +260,9 @@ impl<F: Fold> Store<F> {
if self.waiting.contains_key(&id) {
return Offered::Waiting;
}
+ if self.holding_back.contains(&id) {
+ return Offered::Stopped;
+ }
if bytes.len() > F::LARGEST {
return self.refuse(id, Refusal::None);
}
@@ -447,6 +470,9 @@ impl<F: Fold> Store<F> {
}
fn judged(&mut self, id: Id, event: Event, taken: &mut Vec<Id>) -> Offered {
+ if self.stopped.is_some() {
+ return self.hold_back(id, event);
+ }
if let Some(writes) = F::writes(&event.bytes)
&& self.writes.values().any(|dropped| *dropped == writes)
{
@@ -498,6 +524,10 @@ impl<F: Fold> Store<F> {
if let Err(why) = F::judge(&at, &id, &event.bytes) {
return self.refuse(id, Refusal::Judged(why));
}
+ if let Some(why) = F::stops(&at, &self.state, &id, &event.bytes) {
+ self.stopped = Some((id, why));
+ return self.hold_back(id, event);
+ }
if !F::keeps(&self.state, &id, &event.bytes) {
return self.refuse(id, Refusal::Own);
}
@@ -508,6 +538,14 @@ impl<F: Fold> Store<F> {
Offered::Taken(vec![id])
}
+ /// Holds an event back, the store stopped.
+ fn hold_back(&mut self, id: Id, event: Event) -> Offered {
+ if self.holding_back.insert(id) {
+ self.held_back.push((id, event));
+ }
+ Offered::Stopped
+ }
+
/// The events refused, and why: for reports.
pub(crate) fn refused(&self) -> impl Iterator<Item = (&Id, &Refusal)> {
self.refused.iter()
@@ -517,19 +555,31 @@ impl<F: Fold> Store<F> {
/// (`Fold::writes`), and everything built on them, as their operator has the node do:
/// it refuses them from then on, and whatever writes what they write, until its
/// operator allows them again. What the checkpoint keeps, or holds by ID, it drops not:
- /// every event after it builds on that. Returns what it dropped, in the order taken.
+ /// every event after it builds on that. It drops the event it stopped at alike, or
+ /// refuses it for building on what it drops: then it takes again, and is offered what
+ /// it held back anew. Returns what it dropped, in the order taken, then the event it
+ /// stopped at, where it dropped that.
pub(crate) fn drop_taken(&mut self, ids: &[Id]) -> Result<Vec<Id>, Refused> {
- if let Some(id) = ids.iter().find(|id| !self.events.contains_key(id)) {
+ let stopped = self.stopped.as_ref().map(|(id, _)| *id);
+ if let Some(id) = ids
+ .iter()
+ .find(|id| !self.events.contains_key(id) && Some(**id) != stopped)
+ {
return Err(Refused::new(format!(
- "{id} isn't an event taken after the checkpoint"
+ "{id} isn't an event taken after the checkpoint, nor the one the store stopped at"
)));
}
- let named: HashSet<Id> = ids
+ let taken: Vec<Id> = ids
+ .iter()
+ .filter(|id| self.events.contains_key(id))
+ .copied()
+ .collect();
+ let named: HashSet<Id> = taken
.iter()
.filter_map(|id| F::writes(&self.events[id].bytes))
.collect();
let mut dropped: HashMap<Id, Refusal> =
- ids.iter().map(|id| (*id, Refusal::Dropped)).collect();
+ taken.iter().map(|id| (*id, Refusal::Dropped)).collect();
for id in &self.order {
if dropped.contains_key(id) {
continue;
@@ -547,26 +597,52 @@ impl<F: Fold> Store<F> {
dropped.insert(*id, Refusal::BuiltOn(on));
}
}
- let order: Vec<Id> = self
+ let mut order: Vec<Id> = self
.order
.iter()
.filter(|id| dropped.contains_key(id))
.copied()
.collect();
- self.order.retain(|id| !dropped.contains_key(id));
- for id in &order {
- if let Some(event) = self.events.remove(id)
- && let Some(writes) = F::writes(&event.bytes)
- {
- self.writes.insert(*id, writes);
+ if !order.is_empty() {
+ self.order.retain(|id| !dropped.contains_key(id));
+ for id in &order {
+ if let Some(event) = self.events.remove(id)
+ && let Some(writes) = F::writes(&event.bytes)
+ {
+ self.writes.insert(*id, writes);
+ }
}
+ self.refused.extend(dropped);
+ let mut state = self.start.clone();
+ for id in &self.order {
+ F::add(&mut state, id, &self.events[id].bytes);
+ }
+ self.state = state;
}
- self.refused.extend(dropped);
- let mut state = self.start.clone();
- for id in &self.order {
- F::add(&mut state, id, &self.events[id].bytes);
+ if let Some(stopped) = stopped {
+ let dropping = ids.contains(&stopped);
+ let on_dropped = self.held_back[0]
+ .1
+ .dependencies
+ .iter()
+ .any(|dependency| self.refused.contains_key(dependency));
+ if dropping || on_dropped {
+ self.stopped = None;
+ self.holding_back.clear();
+ let mut held_back = std::mem::take(&mut self.held_back);
+ if dropping {
+ let (_, event) = held_back.remove(0);
+ if let Some(writes) = F::writes(&event.bytes) {
+ self.writes.insert(stopped, writes);
+ }
+ self.refuse(stopped, Refusal::Dropped);
+ order.push(stopped);
+ }
+ for (_, event) in held_back {
+ self.offer(event.bytes);
+ }
+ }
}
- self.state = state;
Ok(order)
}
@@ -868,6 +944,85 @@ mod tests {
assert!(matches!(store.offer(anew), Offered::Taken(_)));
}
+ /// An event the store can't judge, that its node would take: it stops there, holding
+ /// back what comes after, taken or refused by nobody, until its operator has it drop
+ /// that one; then it takes them, as before the stop. Beside what it took, the event
+ /// is refused of its own.
+ #[test]
+ fn a_store_stops_at_what_it_cant_judge_until_its_operator_drops_it() {
+ let mut store = store();
+ let root = store.id();
+ let mark = taken(store.offer(testfold::put(&[root], "mark", "1")));
+ let new = testfold::era(&[mark], 1, "new");
+ let at = Id::of(&new);
+ let on = testfold::put(&[at], "a", "1");
+ // Waiting for it before the stop: refused once it is dropped.
+ assert_eq!(store.offer(on.clone()), Offered::Waiting);
+ assert_eq!(store.offer(new.clone()), Offered::Stopped);
+ let (id, why, held) = store.stopped().expect("stopped");
+ assert_eq!((*id, why, held), (at, "era 1, tagged new", 1));
+ // Nothing taken, nothing refused, junk or not.
+ let later = testfold::put(&[mark], "b", "1");
+ let junk = testfold::junk(&[mark]);
+ assert_eq!(store.offer(later.clone()), Offered::Stopped);
+ assert_eq!(store.offer(junk.clone()), Offered::Stopped);
+ assert_eq!(store.offer(later.clone()), Offered::Stopped);
+ assert_eq!(store.offer(new.clone()), Offered::Stopped);
+ assert_eq!(store.taken(), &[mark]);
+ assert_eq!(store.refused().count(), 0);
+ assert_eq!(store.stopped().map(|(_, _, held)| held), Some(3));
+ assert!(store.drop_taken(&[Id::of(&later)]).is_err());
+ // Dropped: what it held back is taken, or refused, and what waited for it refused.
+ assert_eq!(store.drop_taken(&[at]), Ok(vec![at]));
+ assert!(store.stopped().is_none());
+ assert_eq!(store.taken(), &[mark, Id::of(&later)]);
+ assert!(matches!(
+ store.refusal(&Id::of(&junk)),
+ Some(Refusal::Judged(_))
+ ));
+ assert_eq!(store.refusal(&Id::of(&on)), Some(&Refusal::BuiltOn(at)));
+ assert_eq!(store.own(), (Vec::new(), vec![at]));
+ // Of what writes what it writes, whoever wrote it: dropped.
+ assert_eq!(
+ store.offer(testfold::era(&[root], 1, "new")),
+ Offered::Refused(Refusal::Dropped)
+ );
+ // Allowed again: it stops there once more.
+ store.allow(&[at]);
+ assert_eq!(store.offer(new), Offered::Stopped);
+ assert_eq!(store.offer(on), Offered::Stopped);
+ // Beside an era it took, it is refused of its own, and nothing stops.
+ let mut beside = self::store();
+ let one = taken(beside.offer(testfold::era(&[root], 1, "one")));
+ let new = testfold::era(&[root], 1, "new");
+ assert_eq!(beside.offer(new.clone()), Offered::Refused(Refusal::Own));
+ assert!(beside.stopped().is_none());
+ // Its operator drops the era it took and allows the other: it stops there.
+ beside.drop_taken(&[one]).unwrap();
+ beside.allow(&[Id::of(&new)]);
+ assert_eq!(beside.offer(new), Offered::Stopped);
+ }
+
+ /// The store stopped at an event built on one its operator has it drop: it refuses it
+ /// with the rest, and takes again.
+ #[test]
+ fn a_drop_under_the_event_a_store_stopped_at_takes_it_with_it() {
+ let mut store = store();
+ let root = store.id();
+ let mark = taken(store.offer(testfold::put(&[root], "mark", "1")));
+ let new = Id::of(&testfold::era(&[mark], 1, "new"));
+ assert_eq!(
+ store.offer(testfold::era(&[mark], 1, "new")),
+ Offered::Stopped
+ );
+ let later = testfold::put(&[root], "b", "1");
+ assert_eq!(store.offer(later.clone()), Offered::Stopped);
+ assert_eq!(store.drop_taken(&[mark]), Ok(vec![mark]));
+ assert!(store.stopped().is_none());
+ assert_eq!(store.refusal(&new), Some(&Refusal::BuiltOn(mark)));
+ assert_eq!(store.taken(), &[Id::of(&later)]);
+ }
+
#[test]
fn a_store_read_anew_refuses_what_its_node_refused_of_its_own() {
let mut store = store();
diff --git a/src/federation/store/mod.rs b/src/federation/store/mod.rs
index 4027fb9..c80f5b8 100644
--- a/src/federation/store/mod.rs
+++ b/src/federation/store/mod.rs
@@ -82,13 +82,21 @@ pub(crate) trait Fold {
/// What the event builds on; `None` where its bytes are none of this fold's events.
fn dependencies(event: &[u8]) -> Option<Vec<Id>>;
- /// Whether the event is taken where its history reads as `at`.
+ /// Whether the event is taken where its history reads as `at`, as far as the fold
+ /// reads it (`stops`).
fn judge(at: &Self::State, id: &Id, event: &[u8]) -> Result<(), Refused>;
/// Adds the event, whose dependencies are added already. Events neither of which
/// builds on the other may come in either order: the state is the same.
fn add(state: &mut Self::State, id: &Id, event: &[u8]);
+ /// Why a node whose store reads as `now` can't judge an event its history, read as
+ /// `at`, doesn't refuse, where it can't: one only a fold knowing more reads, that the
+ /// node would take. The store stops at it (`docs/store.md`, A node's own).
+ fn stops(_at: &Self::State, _now: &Self::State, _id: &Id, _event: &[u8]) -> Option<String> {
+ None
+ }
+
/// Whether a node whose store reads as `now` takes an event its history takes.
fn keeps(_now: &Self::State, _id: &Id, _event: &[u8]) -> bool {
true
diff --git a/src/federation/store/testfold.rs b/src/federation/store/testfold.rs
index 2478c0a..17e039b 100644
--- a/src/federation/store/testfold.rs
+++ b/src/federation/store/testfold.rs
@@ -7,7 +7,8 @@
//! * `lock`: a key locked for good.
//! * `era`: era `n`, taken only where `n` is one past the era at its history; of two of one
//! number, a node keeps the first it takes (as the federation's versions). Eras of one
-//! number and tag write the same: a drop of one refuses them all.
+//! number and tag write the same: a drop of one refuses them all. One tagged `new` is
+//! of a fold knowing more: a node that would take it stops at it.
//! * `cut`: cut `n`, naming heads to move the store to, as `era`: above the heads the latest
//! cut of its history names, and holding that cut (or after the checkpoint the state
//! starts from, where it holds none); none of them in another's history. It must be above
@@ -347,6 +348,15 @@ impl Fold for TestFold {
}
}
+ fn stops(at: &State, now: &State, _id: &Id, event: &[u8]) -> Option<String> {
+ match decode(event)? {
+ (_, Kind::Era { n, tag }) if tag == "new" && now.era == at.era => {
+ Some(format!("era {n}, tagged new"))
+ }
+ _ => None,
+ }
+ }
+
fn keeps(now: &State, _id: &Id, event: &[u8]) -> bool {
match decode(event) {
Some((_, Kind::Era { n, tag })) => {