From 5d26bfd64ee01ad921daf56005641518d398cb4b Mon Sep 17 00:00:00 2001 From: tv Date: Wed, 18 Nov 2026 20:14:00 +0000 Subject: 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. --- src/federation/model.rs | 36 ++++++++++++++++++++++++++++++++---- 1 file changed, 32 insertions(+), 4 deletions(-) (limited to 'src/federation/model.rs') 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, /// Events offered whose dependencies aren't all taken yet. waiting: Vec>, + /// 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, event: &Event) -> bool { + let Event::Version { version, .. } = event else { + return false; + }; + let reads = |history: &BTreeSet| 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 { -- cgit v1.3.1