diff options
| author | tv <tv@krebsco.de> | 2026-11-16 18:43:42 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-16 20:08:46 +0100 |
| commit | 01a11cb403af0351411fe79deb49269b667bf881 (patch) | |
| tree | b8b2ee5ba1e4b78065c726a058cc853de2f6b883 /src/federation/model.rs | |
| parent | cdbfe7e4fb4646a7749d1155d1b784a4ca2a99c2 (diff) | |
federation: the model, a second reading of the federation
The model (`docs/federation-tests.md`, The harness) reads the federation as
`docs/federation.md` says, as plainly as it can: every event judged at its history read
anew from the root, the version current there the highest-numbered written one, keys,
key sets, node lists, votes, passing and dead, version events and the heads a version
may name each worked out from that history alone; a node's own, the first of two
versions changing one; and what counts read from everything taken. It keeps nothing but
which events it took, and makes no checkpoint: slow and short, it is what the fold is
checked against. A test takes it through a version passing, offered last event first.
Diffstat (limited to 'src/federation/model.rs')
| -rw-r--r-- | src/federation/model.rs | 530 |
1 files changed, 530 insertions, 0 deletions
diff --git a/src/federation/model.rs b/src/federation/model.rs new file mode 100644 index 0000000..404bdb4 --- /dev/null +++ b/src/federation/model.rs @@ -0,0 +1,530 @@ +//! 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. + +use std::collections::{BTreeMap, BTreeSet}; + +use super::event::{Checkpoint, Does, Event, Signed}; +use super::jcs::Json; +use super::store::Id; +use super::version::Version; + +/// What became of an event offered to the model. +#[derive(Clone, Debug, PartialEq, Eq)] +pub(crate) enum Verdict { + Taken, + /// Taken already. + Held, + /// Some of its dependencies aren't taken yet. + Waiting, + Refused, +} + +pub(crate) struct Model { + root: Id, + first: Version, + /// The events taken, by ID. + taken: BTreeMap<Id, Event>, + refused: BTreeSet<Id>, + /// Events offered whose dependencies aren't all taken yet. + waiting: Vec<Vec<u8>>, +} + +impl Model { + /// A model of the federation starting from `root`, a root without heads. + pub(crate) fn new(root: &[u8]) -> Model { + let checkpoint = Checkpoint::read(root).expect("a root"); + assert!(checkpoint.at.is_empty() && checkpoint.keeps.is_empty()); + Model { + root: Id::of(root), + first: checkpoint.version, + taken: BTreeMap::new(), + refused: BTreeSet::new(), + waiting: Vec::new(), + } + } + + pub(crate) fn taken(&self) -> BTreeSet<Id> { + self.taken.keys().copied().collect() + } + + /// Offers an event; those waiting for it are taken or refused with it. + pub(crate) fn offer(&mut self, bytes: &[u8]) -> Verdict { + let verdict = self.consider(bytes); + if verdict == Verdict::Waiting { + self.waiting.push(bytes.to_vec()); + } + loop { + let waiting = std::mem::take(&mut self.waiting); + let before = waiting.len(); + for event in waiting { + if self.consider(&event) == Verdict::Waiting { + self.waiting.push(event); + } + } + if self.waiting.len() == before { + return verdict; + } + } + } + + fn consider(&mut self, bytes: &[u8]) -> Verdict { + let id = Id::of(bytes); + if self.taken.contains_key(&id) { + return Verdict::Held; + } + if self.refused.contains(&id) { + return Verdict::Refused; + } + let Some(event) = Event::read(bytes) else { + self.refused.insert(id); + return Verdict::Refused; + }; + let deps = event.deps(); + if deps.iter().any(|dep| self.refused.contains(dep)) { + self.refused.insert(id); + return Verdict::Refused; + } + if !deps + .iter() + .all(|dep| *dep == self.root || self.taken.contains_key(dep)) + { + return Verdict::Waiting; + } + let history = self.history(deps); + if self.judge(&history, &event, deps) && self.keeps(&event) { + self.taken.insert(id, event); + Verdict::Taken + } else { + self.refused.insert(id); + Verdict::Refused + } + } + + /// The events taken among `ids` and all they build on. + fn history(&self, ids: &[Id]) -> BTreeSet<Id> { + let mut history = BTreeSet::new(); + let mut todo = ids.to_vec(); + while let Some(id) = todo.pop() { + if let Some(event) = self.taken.get(&id) + && history.insert(id) + { + todo.extend_from_slice(event.deps()); + } + } + history + } + + /// The version a version event writes: what the proposal of its hash holds. + fn written(&self, hash: &Id) -> Option<Version> { + self.taken.values().find_map(|event| match event { + Event::Signed(Signed { + does: + Does::Proposal { + hash: proposed, + version, + }, + .. + }) if proposed == hash => Version::read(version).ok(), + _ => None, + }) + } + + /// The versions written in a history: the first, and those its version events write. + fn versions(&self, history: &BTreeSet<Id>) -> Vec<Version> { + let mut versions = vec![self.first.clone()]; + for id in history { + if let Some(Event::Version { version, .. }) = self.taken.get(id) + && !versions.iter().any(|known| known.hash == *version) + && let Some(written) = self.written(version) + { + versions.push(written); + } + } + versions + } + + /// The version current at a history: the written one with the highest number; none + /// where two of one number are written there. + fn current(&self, history: &BTreeSet<Id>) -> Option<Version> { + let versions = self.versions(history); + let numbers: BTreeSet<u64> = versions.iter().map(|version| version.number).collect(); + if numbers.len() < versions.len() { + return None; + } + versions.into_iter().max_by_key(|version| version.number) + } + + /// The version an event is written under: the one current at its history. + fn under(&self, id: &Id) -> Option<Version> { + let event = self.taken.get(id)?; + self.current(&self.history(event.deps())) + } + + /// Whether `b` is in the history of `a`. + fn builds_on(&self, a: &Id, b: &Id) -> bool { + self.taken + .get(a) + .is_some_and(|event| self.history(event.deps()).contains(b)) + } + + /// Of `ids`, those no other of them has in its history; of those, the lowest ID. + fn latest(&self, ids: &[Id]) -> Option<Id> { + ids.iter() + .filter(|id| { + !ids.iter() + .any(|other| other != *id && self.builds_on(other, id)) + }) + .min() + .copied() + } + + /// The signed events of a history. + fn signed<'a>(&'a self, history: &'a BTreeSet<Id>) -> impl Iterator<Item = (Id, &'a Signed)> { + history.iter().filter_map(|id| match self.taken.get(id) { + Some(Event::Signed(signed)) => Some((*id, signed)), + _ => None, + }) + } + + /// The key set, or node list, of `party` that counts in a history by `version`. + fn list( + &self, + history: &BTreeSet<Id>, + party: &str, + version: &Version, + keys: bool, + ) -> Option<Id> { + let given = version.parties.get(party)?; + let since = if keys { + given.keys_since + } else { + given.nodes_since + }; + let ids: Vec<Id> = self + .signed(history) + .filter(|(id, signed)| { + signed.party == party + && match signed.does { + Does::Keys(_) => keys, + Does::Nodes(_) => !keys, + _ => false, + } + && self.under(id).is_some_and(|under| under.number >= since) + }) + .map(|(id, _)| id) + .collect(); + self.latest(&ids) + } + + /// The keys of `party` in a history by `version`. + fn keys(&self, history: &BTreeSet<Id>, party: &str, version: &Version) -> Vec<String> { + let Some(given) = version.parties.get(party) else { + return Vec::new(); + }; + match self + .list(history, party, version, true) + .map(|id| &self.taken[&id]) + { + Some(Event::Signed(Signed { + does: Does::Keys(keys), + .. + })) => keys.clone(), + _ => given.keys.clone(), + } + } + + /// The parties voting `true`, and `false`, on a proposal on `on` in a history. + fn votes( + &self, + history: &BTreeSet<Id>, + on: &Id, + proposal: &Id, + ) -> (BTreeSet<String>, BTreeSet<String>) { + let mut yes = BTreeSet::new(); + let mut no = BTreeSet::new(); + for (_, signed) in self.signed(history) { + if let Does::Vote { + on: voted_on, + proposal: voted, + yes: vote, + } = &signed.does + && voted_on == on + && voted == proposal + { + if *vote { + yes.insert(signed.party.clone()); + } else { + no.insert(signed.party.clone()); + } + } + } + (yes, no) + } + + fn proposed_on(&self, history: &BTreeSet<Id>, proposal: &Id, on: &Id) -> bool { + self.signed(history).any(|(id, signed)| { + matches!(&signed.does, Does::Proposal { hash, .. } if hash == proposal) + && self.under(&id).is_some_and(|under| under.hash == *on) + }) + } + + /// The events taken above `heads`, by `store.md`'s Events: each with them all in its + /// history, and each of its dependencies one of them or above them. + fn is_above(&self, id: &Id, heads: &[Id]) -> bool { + let Some(event) = self.taken.get(id) else { + return false; + }; + if heads.contains(id) { + return false; + } + let history = self.history(event.deps()); + heads.iter().all(|head| history.contains(head)) + && event + .deps() + .iter() + .all(|dep| heads.contains(dep) || self.is_above(dep, heads)) + } + + fn judge(&self, history: &BTreeSet<Id>, event: &Event, deps: &[Id]) -> bool { + let Some(current) = self.current(history) else { + return false; + }; + match event { + Event::Signed(signed) => { + let Some(given) = current.parties.get(&signed.party) else { + return false; + }; + let by_version = given.keys.contains(&signed.key); + match &signed.does { + Does::Write { path, .. } => { + self.keys(history, &signed.party, ¤t) + .contains(&signed.key) + && current.writer(path) == Some(signed.party.as_str()) + } + Does::Keys(_) | Does::Nodes(_) | Does::Proposal { .. } => by_version, + Does::Vote { on, proposal, yes } => { + by_version + && *on == current.hash + && self.proposed_on(history, proposal, on) + && (!*yes || { + // Every other proposal its party backs on that version is dead. + self.signed(history).all(|(_, other)| match &other.does { + Does::Vote { + on: voted_on, + proposal: voted, + yes: true, + } if other.party == signed.party + && voted_on == on + && voted != proposal => + { + let (_, no) = self.votes(history, on, voted); + let parties = current.parties.len(); + 3 * parties.saturating_sub(no.len()) < 2 * parties + } + _ => true, + }) + }) + } + } + } + Event::Version { version, .. } => { + if !self.proposed_on(history, version, ¤t.hash) { + return false; + } + let (yes, _) = self.votes(history, ¤t.hash, version); + if 3 * yes.len() < 2 * current.parties.len() { + return false; + } + let Some(next) = self.written(version) else { + return false; + }; + if next.changes_validly(Some(¤t)).is_err() { + return false; + } + match &next.checkpoint { + None => true, + Some(heads) => self.may_name(history, heads, deps), + } + } + } + } + + /// Whether a version event on `deps`, at a history, may name `heads` for a checkpoint. + fn may_name(&self, history: &BTreeSet<Id>, heads: &[Id], deps: &[Id]) -> bool { + // None in another's history. + if heads + .iter() + .any(|a| heads.iter().any(|b| a != b && self.builds_on(a, b))) + { + return false; + } + // After the current checkpoint: that the last version of the history's chain + // naming one names, or the root; and at which that one is current too. + let latest = self + .versions(history) + .into_iter() + .filter(|version| version.checkpoint.is_some()) + .max_by_key(|version| version.number); + if let Some(latest) = latest { + let current = latest.checkpoint.clone().unwrap_or_default(); + if !heads.iter().all(|head| self.is_above(head, ¤t)) { + return false; + } + let writing: Vec<Id> = history + .iter() + .filter(|id| { + matches!(self.taken.get(id), Some(Event::Version { version, .. }) if *version == latest.hash) + }) + .copied() + .collect(); + let holds = heads.iter().any(|head| { + writing + .iter() + .any(|event| head == event || self.builds_on(head, event)) + }); + if !holds { + return false; + } + } else if !heads.iter().all(|head| self.taken.contains_key(head)) { + return false; + } + // The version event above them. + let mut history_of_it = BTreeSet::new(); + for dep in deps { + history_of_it.insert(*dep); + history_of_it.extend(self.history(&[*dep])); + } + heads.iter().all(|head| history_of_it.contains(head)) + && deps + .iter() + .all(|dep| heads.contains(dep) || self.is_above(dep, heads)) + } + + /// 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 { + let Event::Version { version, .. } = event else { + return true; + }; + let all = self.taken(); + let versions = self.versions(&all); + if versions.iter().any(|known| known.hash == *version) { + return true; + } + let Some(current) = self.current(&all) else { + return false; + }; + self.written(version) + .is_some_and(|next| next.changes == Some(current.hash)) + } + + /// The version current over everything taken. + pub(crate) fn version(&self) -> Version { + self.current(&self.taken()) + .expect("one version of each number") + } + + /// What counts: each place's value, unless `null`. + pub(crate) fn values(&self) -> BTreeMap<String, Json> { + let all = self.taken(); + let current = self.version(); + let mut places: BTreeMap<Vec<String>, Vec<Id>> = BTreeMap::new(); + for (id, signed) in self.signed(&all) { + if let Does::Write { path, .. } = &signed.does + && current.writer(path) == Some(signed.party.as_str()) + && self + .keys(&all, &signed.party, ¤t) + .contains(&signed.key) + { + places.entry(path.clone()).or_default().push(id); + } + } + places + .into_iter() + .filter_map(|(path, ids)| { + let id = self.latest(&ids)?; + match &self.taken[&id] { + Event::Signed(Signed { + does: Does::Write { value, .. }, + .. + }) if *value != Json::Null => Some((path.join("/"), value.clone())), + _ => None, + } + }) + .collect() + } + + /// The keys of `party` over everything taken. + pub(crate) fn keys_of(&self, party: &str) -> Vec<String> { + self.keys(&self.taken(), party, &self.version()) + } + + /// The members: each node a party's node list names, with its party. + pub(crate) fn members(&self) -> BTreeSet<(String, String)> { + let all = self.taken(); + let current = self.version(); + let mut members = BTreeSet::new(); + for (party, given) in ¤t.parties { + let nodes = match self + .list(&all, party, ¤t, false) + .map(|id| &self.taken[&id]) + { + Some(Event::Signed(Signed { + does: Does::Nodes(nodes), + .. + })) => nodes.clone(), + _ => given.nodes.clone(), + }; + for node in nodes { + members.insert((node, party.clone())); + } + } + members + } +} + +#[cfg(test)] +mod tests { + use super::super::harness::{self, Party, Spec}; + use super::*; + + #[test] + fn the_model_reads_a_version_passing_and_a_write_after_it() { + let (tv, lass) = (Party::new("tv", 1), Party::new("lass", 2)); + let first = Spec::first(&[&tv, &lass], &[]); + let root = Checkpoint { + at: Vec::new(), + keeps: Vec::new(), + version: Version::read(&first.json()).expect("a version"), + } + .bytes(); + let mut model = Model::new(&root); + let root = Id::of(&root); + let mut next = first.after(first.hash()); + next.rules.push(("names/x".to_owned(), harness::str("tv"))); + let proposal = tv.propose(&[root], &next.json()); + let p = Id::of(&proposal); + let votes = [ + tv.vote(&[p], first.hash(), next.hash(), true), + lass.vote(&[p], first.hash(), next.hash(), true), + ]; + let written = harness::version_event(&[Id::of(&votes[0]), Id::of(&votes[1])], next.hash()); + let write = tv.write(&[Id::of(&written)], "names/x", harness::str("1")); + // Offered last first: each waits until what it builds on is taken. + assert_eq!(model.offer(&write), Verdict::Waiting); + assert_eq!(model.offer(&written), Verdict::Waiting); + assert_eq!(model.offer(&votes[1]), Verdict::Waiting); + assert_eq!(model.offer(&votes[0]), Verdict::Waiting); + assert_eq!(model.offer(&proposal), Verdict::Taken); + assert_eq!(model.taken().len(), 5); + assert_eq!(model.version().number, 1); + assert_eq!(model.values().get("names/x"), Some(&harness::str("1"))); + // Too early: at the root's history nobody writes there. + assert_eq!( + model.offer(&tv.write(&[root], "names/x", harness::str("2"))), + Verdict::Refused + ); + } +} |
