summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-18 20:14:00 +0000
committertv <tv@krebsco.de>2026-11-18 21:18:01 +0100
commit5d26bfd64ee01ad921daf56005641518d398cb4b (patch)
tree2db60a8fa55718a92e1ec480b567e0ba10915b67 /src
parent7404dcef34dbad11a5ac2a6b8a27836b01c82635 (diff)
model: stops at a version it doesn't read
The model stops where `federation.md` says a node does: at a version event whose proposal passed at its history, isn't a version as this continuum reads it, and changes the version the model reads, it takes and refuses nothing more (`Verdict::Stopped`); beside that version, such an event is refused, as the node refuses it of its own. The property checking the store against the model runs on histories where parties propose such versions too (a field this continuum doesn't know): written in order, events come after what they build on, so both must stop at the same event, having taken the same before it, the adversary's two versions changing one among them. A check that some history stopped keeps the property from passing vacuously.
Diffstat (limited to 'src')
-rw-r--r--src/federation/model.rs36
-rw-r--r--src/federation/properties.rs60
2 files changed, 82 insertions, 14 deletions
diff --git a/src/federation/model.rs b/src/federation/model.rs
index 404bdb4..2107d9f 100644
--- a/src/federation/model.rs
+++ b/src/federation/model.rs
@@ -1,7 +1,7 @@
//! The model (`docs/federation-tests.md`, The harness): the federation read as
//! `docs/federation.md` says, as plainly as it can be. It reads every history anew from
-//! the root, keeps nothing between events but which it took, and makes no checkpoint.
-//! It is slow and short, and the fold is checked against it.
+//! the root, keeps nothing between events but which it took and whether it stopped, and
+//! makes no checkpoint. It is slow and short, and the fold is checked against it.
use std::collections::{BTreeMap, BTreeSet};
@@ -19,6 +19,9 @@ pub(crate) enum Verdict {
/// Some of its dependencies aren't taken yet.
Waiting,
Refused,
+ /// Neither taken nor refused: it stopped at a version it doesn't read, this event or
+ /// one before.
+ Stopped,
}
pub(crate) struct Model {
@@ -29,6 +32,8 @@ pub(crate) struct Model {
refused: BTreeSet<Id>,
/// Events offered whose dependencies aren't all taken yet.
waiting: Vec<Vec<u8>>,
+ /// Whether it stopped (`Changing the federation`): it takes and refuses nothing more.
+ stopped: bool,
}
impl Model {
@@ -42,6 +47,7 @@ impl Model {
taken: BTreeMap::new(),
refused: BTreeSet::new(),
waiting: Vec::new(),
+ stopped: false,
}
}
@@ -81,6 +87,9 @@ impl Model {
self.refused.insert(id);
return Verdict::Refused;
};
+ if self.stopped {
+ return Verdict::Stopped;
+ }
let deps = event.deps();
if deps.iter().any(|dep| self.refused.contains(dep)) {
self.refused.insert(id);
@@ -93,7 +102,15 @@ impl Model {
return Verdict::Waiting;
}
let history = self.history(deps);
- if self.judge(&history, &event, deps) && self.keeps(&event) {
+ if !self.judge(&history, &event, deps) {
+ self.refused.insert(id);
+ return Verdict::Refused;
+ }
+ if self.stops(&history, &event) {
+ self.stopped = true;
+ return Verdict::Stopped;
+ }
+ if self.keeps(&event) {
self.taken.insert(id, event);
Verdict::Taken
} else {
@@ -337,8 +354,9 @@ impl Model {
if 3 * yes.len() < 2 * current.parties.len() {
return false;
}
+ // None here: whether it is a version, a later continuum may say.
let Some(next) = self.written(version) else {
- return false;
+ return true;
};
if next.changes_validly(Some(&current)).is_err() {
return false;
@@ -402,6 +420,16 @@ impl Model {
.all(|dep| heads.contains(dep) || self.is_above(dep, heads))
}
+ /// Whether the node stops at `event`, at a history it judged: a version event whose
+ /// proposal is none here, changing the version the node reads, the one current there.
+ fn stops(&self, history: &BTreeSet<Id>, event: &Event) -> bool {
+ let Event::Version { version, .. } = event else {
+ return false;
+ };
+ let reads = |history: &BTreeSet<Id>| self.current(history).map(|current| current.hash);
+ self.written(version).is_none() && reads(history) == reads(&self.taken())
+ }
+
/// A node's own: a version event it takes only where its version changes the version
/// it reads, or is one it took.
fn keeps(&self, event: &Event) -> bool {
diff --git a/src/federation/properties.rs b/src/federation/properties.rs
index d42509b..02c7799 100644
--- a/src/federation/properties.rs
+++ b/src/federation/properties.rs
@@ -15,6 +15,7 @@ use super::event::{Checkpoint, Does, Event};
use super::fold::Federation;
use super::harness::{self, Party, Spec};
use super::held::Holding;
+use super::jcs::Json;
use super::model::{Model, Verdict};
use super::store::memory::{Offered, Refusal, Store};
use super::store::{Fold, Id};
@@ -82,12 +83,14 @@ impl History {
}
}
-/// How a history is written: whether an adversary takes part, and whether versions name
-/// checkpoints.
+/// How a history is written: whether an adversary takes part, whether versions name
+/// checkpoints, and whether parties propose versions this continuum doesn't read, at
+/// which a store stops, which events then take in the order they come.
#[derive(Clone, Copy)]
struct Kind {
adversary: bool,
checkpoints: bool,
+ unread: bool,
}
/// One of `ids`, of the latest five more often than not.
@@ -169,10 +172,27 @@ fn generate(rng: &mut Rng, kind: Kind) -> History {
next.rules
.push((format!("names/x{step}"), harness::str(&party.name)));
}
- let bytes = party.propose(&deps, &next.json());
- proposals.push((Id::of(&bytes), next.hash(), current.hash, named));
- specs.insert(next.hash(), next);
- bytes
+ if kind.unread && rng.chance(0.5) {
+ // A field this continuum doesn't know: none here.
+ let Json::Object(mut members) = next.json() else {
+ unreachable!("a version is an object")
+ };
+ members.push(("later".to_owned(), Json::Bool(true)));
+ let later = Json::object(members).expect("names once each");
+ let bytes = party.propose(&deps, &later);
+ proposals.push((
+ Id::of(&bytes),
+ Id::of(&later.bytes()),
+ current.hash,
+ named,
+ ));
+ bytes
+ } else {
+ let bytes = party.propose(&deps, &next.json());
+ proposals.push((Id::of(&bytes), next.hash(), current.hash, named));
+ specs.insert(next.hash(), next);
+ bytes
+ }
}
}
} else if roll < 85 {
@@ -297,19 +317,28 @@ 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"),
+ Offered::Stopped => Verdict::Stopped,
}
}
+/// Where parties propose versions this continuum doesn't read too, the store stops where
+/// the model does: written in order, events come after what they build on, and both stop
+/// at the same event, taking the same before it.
#[test]
fn the_store_judges_and_reads_as_the_model() {
- for adversary in [false, true] {
+ let stopped = std::cell::Cell::new(0);
+ for (adversary, unread, cases) in [
+ (false, false, 48),
+ (true, false, 48),
+ (false, true, 32),
+ (true, true, 32),
+ ] {
check(
- 48,
+ cases,
Kind {
adversary,
checkpoints: false,
+ unread,
},
|history| {
let mut model = Model::new(&history.root);
@@ -325,6 +354,9 @@ fn the_store_judges_and_reads_as_the_model() {
));
}
}
+ if store.stopped().is_some() {
+ stopped.set(stopped.get() + 1);
+ }
if reads(&store) != model_reads(&model) {
return Err(format!(
"the store reads {:?}, the model {:?}",
@@ -336,6 +368,7 @@ fn the_store_judges_and_reads_as_the_model() {
},
);
}
+ assert!(stopped.get() > 0, "no history stopped a store");
}
#[test]
@@ -345,6 +378,7 @@ fn what_builds_on_a_refused_event_is_refused() {
Kind {
adversary: true,
checkpoints: true,
+ unread: false,
},
|history| {
let (store, _) = history.store(&history.written());
@@ -369,6 +403,7 @@ fn honest_parties_read_the_same_whatever_order_events_come_in() {
Kind {
adversary: false,
checkpoints: true,
+ unread: false,
},
|history| {
let held = holds(&history.store(&history.written()).0);
@@ -401,6 +436,7 @@ fn a_store_read_from_its_document_holds_what_one_given_the_events_alone_holds()
Kind {
adversary: false,
checkpoints: true,
+ unread: false,
},
|history| {
let alone = holds(&history.store(&history.written()).0);
@@ -456,6 +492,7 @@ fn after_a_checkpoint_the_store_judges_and_reads_as_the_whole_history() {
Kind {
adversary: false,
checkpoints: true,
+ unread: false,
},
|history| {
let (store, _) = history.store(&history.written());
@@ -533,6 +570,7 @@ fn every_version_a_store_takes_was_passed_by_two_thirds_in_its_history() {
Kind {
adversary: true,
checkpoints: false,
+ unread: false,
},
|history| {
let (store, _) = history.store(&history.written());
@@ -610,6 +648,7 @@ fn without_a_party_voting_twice_no_two_versions_change_one() {
Kind {
adversary: false,
checkpoints: true,
+ unread: false,
},
|history| {
let (store, _) = history.store(&history.written());
@@ -632,6 +671,7 @@ fn a_fork_keeps_what_counts_at_its_heads_and_takes_nothing_of_the_other() {
Kind {
adversary: false,
checkpoints: false,
+ unread: false,
},
|history| {
let (mut whole, _) = history.store(&history.written());