diff options
| author | tv <tv@krebsco.de> | 2026-11-18 20:14:00 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-18 21:18:01 +0100 |
| commit | 5d26bfd64ee01ad921daf56005641518d398cb4b (patch) | |
| tree | 2db60a8fa55718a92e1ec480b567e0ba10915b67 /src/federation | |
| parent | 7404dcef34dbad11a5ac2a6b8a27836b01c82635 (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/federation')
| -rw-r--r-- | src/federation/model.rs | 36 | ||||
| -rw-r--r-- | src/federation/properties.rs | 60 |
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(¤t)).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()); |
