aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-16 22:18:31 +0000
committertv <tv@krebsco.de>2026-11-16 23:32:49 +0100
commit023bc8ca4e571b6eb2095b8f1f34ea4363452db9 (patch)
tree8cdee8b78bc8675437df4034c2e94299897a3d84 /src
parent618cf683bf19de7f9c3de3d7eb4a7614881094a1 (diff)
federation: what a node voting by itself decides
A party may have one of its nodes vote and propose for it, by rules its operator sets (`docs/federation.md`, Votes a node casts by itself): `federation::vote::decide`, from the node's store, how long it held each event, and its party's record. * Following: `true` on a proposal on the current version where a party it follows voted `true`, `false` where one voted `false`; by default only on a version that only moves to a checkpoint, a `true` as a `false`. * Proposing a checkpoint: once so many events are held beyond its checkpoint, or so long after the store moved there, a version that only moves to a checkpoint at the heads of what it held for a while, at which the current version is current; only where nothing that can still pass is proposed on the current version, but a proposal it wouldn't back that nobody backs but its proposer. It backs what it proposes. It keeps to what a party's client keeps to (`Record::may_vote`), one `true` at a time; and by the voters' rule (`vote::backs_checkpoint`) backs a version naming a checkpoint only where it changes nothing of the current one but its number, what it changes and its checkpoint, and its heads leave out nothing it held for a while before it was proposed. A party that has a node vote by itself votes by hand only through that node, which keeps its one record: `vote::by_hand` decides such a vote by the record and, with a `true`, by the voters' rule.
Diffstat (limited to 'src')
-rw-r--r--src/federation/mod.rs1
-rw-r--r--src/federation/vote.rs513
2 files changed, 514 insertions, 0 deletions
diff --git a/src/federation/mod.rs b/src/federation/mod.rs
index 8d059cc..61949fd 100644
--- a/src/federation/mod.rs
+++ b/src/federation/mod.rs
@@ -25,3 +25,4 @@ pub(crate) mod store;
#[cfg(test)]
mod vectors;
pub(crate) mod version;
+pub(crate) mod vote;
diff --git a/src/federation/vote.rs b/src/federation/vote.rs
new file mode 100644
index 0000000..4b11c32
--- /dev/null
+++ b/src/federation/vote.rs
@@ -0,0 +1,513 @@
+//! Votes a node casts by itself, by its operator's rules (`docs/federation.md`, Votes a
+//! node casts by itself), written nowhere in the swarm: every node judges what it signs as
+//! any vote or proposal.
+//!
+//! * **Following**: it votes `true` on a proposal on the current version where a party it
+//! follows voted `true`, and `false` where one voted `false`; by default only on a
+//! version that only moves to a checkpoint (`Version::only_moves_on`), a `true` as a
+//! `false`.
+//! * **Proposing a checkpoint**: once so many events are held beyond its checkpoint, or so
+//! long after it moved there by its own clock, it proposes a version that only moves to
+//! a checkpoint, at the heads of what it held for a while, where nothing that can still
+//! pass is proposed on the current version, but a proposal it wouldn't back that nobody
+//! backs but its proposer. It backs what it proposes.
+//!
+//! It keeps to what a party's client keeps to (`client::Record::may_vote`), its party's
+//! one record of its votes kept on it; and, by the voters' rule, backs a version naming a
+//! checkpoint only where it changes nothing of the current one but its number, what it
+//! changes and its checkpoint, and its heads leave out nothing it held for a while before
+//! it was proposed (`Store::left_out`).
+
+use std::collections::BTreeSet;
+use std::time::Duration;
+
+use super::client::Record;
+use super::event::{Does, Event, Signed};
+use super::fold::Federation;
+use super::jcs::Json;
+use super::store::Id;
+use super::store::memory::Store;
+use super::version::Version;
+
+/// A node's rules for voting by itself, its operator's.
+#[derive(Clone, Debug, Default)]
+pub(crate) struct Rules {
+ /// The parties it follows.
+ pub(crate) follow: Vec<String>,
+ /// Following on any version, not only one that only moves to a checkpoint.
+ pub(crate) follow_any: bool,
+ /// Proposing a checkpoint once so many events are held beyond the checkpoint...
+ pub(crate) propose_events: Option<usize>,
+ /// ...or so long after the store moved to it, by its own clock.
+ pub(crate) propose_every: Option<Duration>,
+ /// How long it holds an event before it holds it for a while.
+ pub(crate) held_for: Duration,
+}
+
+/// What the node sees: its store, how long it has held each event it took, and how long
+/// since its store moved to its checkpoint.
+pub(crate) struct Seen<'a> {
+ pub(crate) store: &'a Store<Federation>,
+ pub(crate) held: &'a dyn Fn(&Id) -> Option<Duration>,
+ pub(crate) since_move: Duration,
+}
+
+/// What a node voting by itself signs.
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub(crate) enum Act {
+ /// A vote, with the nays that freed its party, to keep.
+ Vote {
+ proposal: Id,
+ yes: bool,
+ nays: Vec<Vec<u8>>,
+ },
+ /// A proposal of this version.
+ Propose(Json),
+}
+
+/// A proposal on the current version, as the node holds it.
+struct Proposed {
+ hash: Id,
+ /// What it proposes, and whether that is a version.
+ json: Json,
+ version: Option<Version>,
+ /// Its proposing events' parties, and how long the node has held the first.
+ proposers: BTreeSet<String>,
+ held: Duration,
+ /// Its votes: each party's, and the events, as bytes.
+ yes: BTreeSet<String>,
+ no: BTreeSet<String>,
+ votes: Vec<Vec<u8>>,
+}
+
+fn proposed(seen: &Seen<'_>, current: &Version) -> Vec<Proposed> {
+ let store = seen.store;
+ let mut all = Vec::new();
+ for (hash, ballot) in store.state().ballots(&current.hash) {
+ let mut proposers = BTreeSet::new();
+ let mut json = None;
+ let mut held = Duration::ZERO;
+ for id in &ballot.proposals {
+ if let Some(Event::Signed(Signed {
+ party,
+ does: Does::Proposal { version, .. },
+ ..
+ })) = store.get(id).and_then(Event::read_taken)
+ {
+ proposers.insert(party);
+ held = held.max((seen.held)(id).unwrap_or_default());
+ json = Some(version);
+ }
+ }
+ let Some(json) = json else {
+ continue;
+ };
+ let (mut yes, mut no, mut votes) = (BTreeSet::new(), BTreeSet::new(), Vec::new());
+ for id in &ballot.votes {
+ let Some(bytes) = store.get(id) else {
+ continue;
+ };
+ if let Some(Event::Signed(Signed {
+ party,
+ does: Does::Vote { yes: vote, .. },
+ ..
+ })) = Event::read_taken(bytes)
+ {
+ if vote {
+ yes.insert(party);
+ } else {
+ no.insert(party);
+ }
+ votes.push(bytes.to_vec());
+ }
+ }
+ all.push(Proposed {
+ hash,
+ version: Version::read(&json).ok(),
+ json,
+ proposers,
+ held,
+ yes,
+ no,
+ votes,
+ });
+ }
+ all
+}
+
+/// Whether the node backs `version`, proposed `proposed_held` ago, by the voters' rule: one
+/// naming a checkpoint only where it changes nothing of `current` but its number, what it
+/// changes and its checkpoint, and its heads leave out nothing the node held for a while
+/// before it was proposed.
+pub(crate) fn backs_checkpoint(
+ seen: &Seen<'_>,
+ rules: &Rules,
+ current: &Version,
+ version: &Version,
+ proposed_held: Duration,
+) -> Result<(), String> {
+ let Some(heads) = &version.checkpoint else {
+ return Ok(());
+ };
+ if !version.only_moves_on(current) {
+ return Err(
+ "a checkpoint that changes more than its number and what it changes".to_owned(),
+ );
+ }
+ let before = proposed_held + rules.held_for;
+ let held: Vec<Id> = seen
+ .store
+ .taken()
+ .iter()
+ .filter(|id| (seen.held)(id).is_some_and(|held| held >= before))
+ .copied()
+ .collect();
+ let left_out = seen.store.left_out(heads, &held);
+ match left_out.first() {
+ None => Ok(()),
+ Some(id) => Err(format!(
+ "its heads leave out {id}, held for a while before it was proposed, and {} more",
+ left_out.len() - 1
+ )),
+ }
+}
+
+/// Whether a proposal can still pass: not dead by the votes cast.
+fn alive(current: &Version, proposed: &Proposed) -> bool {
+ let parties = current.parties.len();
+ 3 * (parties - proposed.no.len().min(parties)) >= 2 * parties
+}
+
+/// What a node voting by itself by `rules` signs now, as it sees its store, by
+/// its party's `record`: its votes, at most one `true`, and a proposal of a checkpoint.
+pub(crate) fn decide(seen: &Seen<'_>, rules: &Rules, record: &Record) -> Vec<Act> {
+ let current = seen.store.state().current().clone();
+ let all = proposed(seen, &current);
+ let mut acts = Vec::new();
+ let mut backed = false;
+ // Its own proposals it backs; others as the parties it follows voted.
+ let own: BTreeSet<Id> = record
+ .signed
+ .iter()
+ .filter_map(|text| match Event::read_taken(text.as_bytes()) {
+ Some(Event::Signed(Signed {
+ does: Does::Proposal { hash, .. },
+ ..
+ })) => Some(hash),
+ _ => None,
+ })
+ .collect();
+ let nays: Vec<Vec<u8>> = all
+ .iter()
+ .flat_map(|proposed| proposed.votes.iter().cloned())
+ .collect();
+ for proposed in &all {
+ let follows =
+ |votes: &BTreeSet<String>| rules.follow.iter().any(|party| votes.contains(party));
+ let yes = if own.contains(&proposed.hash) || follows(&proposed.yes) {
+ true
+ } else if follows(&proposed.no) {
+ false
+ } else {
+ continue;
+ };
+ let moves_on = proposed
+ .version
+ .as_ref()
+ .is_some_and(|version| version.only_moves_on(&current));
+ if !own.contains(&proposed.hash) && !rules.follow_any && !moves_on {
+ continue;
+ }
+ // One `true` at a time, for a version, by the voters' rule.
+ if yes
+ && (backed
+ || proposed.version.as_ref().is_none_or(|version| {
+ backs_checkpoint(seen, rules, &current, version, proposed.held).is_err()
+ }))
+ {
+ continue;
+ }
+ if let Ok(kept) = record.may_vote(&current, proposed.hash, &proposed.json, yes, &nays) {
+ backed |= yes;
+ acts.push(Act::Vote {
+ proposal: proposed.hash,
+ yes,
+ nays: kept,
+ });
+ }
+ }
+ if !backed && let Some(version) = checkpoint(seen, rules, &current, &all) {
+ let hash = Id::of(&version.bytes());
+ if record
+ .may_vote(&current, hash, &version, true, &nays)
+ .is_ok()
+ {
+ acts.push(Act::Propose(version));
+ }
+ }
+ acts
+}
+
+/// A vote by hand, cast through the node that votes for its party, which keeps its
+/// party's one record: `yes` on the proposal of hash `proposal` on the current version, by
+/// the record, and with a `true` by the voters' rule; or why not.
+pub(crate) fn by_hand(
+ seen: &Seen<'_>,
+ rules: &Rules,
+ record: &Record,
+ proposal: Id,
+ yes: bool,
+) -> Result<Act, String> {
+ let current = seen.store.state().current().clone();
+ let all = proposed(seen, &current);
+ let proposed = all
+ .iter()
+ .find(|proposed| proposed.hash == proposal)
+ .ok_or_else(|| format!("no proposal of hash {proposal} on the current version"))?;
+ if yes {
+ let version = proposed.version.as_ref().ok_or("it proposes no version")?;
+ backs_checkpoint(seen, rules, &current, version, proposed.held)?;
+ }
+ let nays: Vec<Vec<u8>> = all
+ .iter()
+ .flat_map(|proposed| proposed.votes.iter().cloned())
+ .collect();
+ let nays = record.may_vote(&current, proposal, &proposed.json, yes, &nays)?;
+ Ok(Act::Vote {
+ proposal,
+ yes,
+ nays,
+ })
+}
+
+/// The version that only moves to a checkpoint the node proposes now, if its rules have it
+/// propose one: at the heads of what it held for a while, at which the current version is
+/// current, where nothing that can still pass is proposed on it, but one it wouldn't back
+/// that nobody backs but its proposer.
+fn checkpoint(seen: &Seen<'_>, rules: &Rules, current: &Version, all: &[Proposed]) -> Option<Json> {
+ let store = seen.store;
+ let due = rules
+ .propose_events
+ .is_some_and(|events| store.taken().len() >= events)
+ || rules
+ .propose_every
+ .is_some_and(|every| seen.since_move >= every);
+ if !due {
+ return None;
+ }
+ let blocked = all.iter().any(|proposed| {
+ let backs = proposed.version.as_ref().is_some_and(|version| {
+ version.only_moves_on(current)
+ && backs_checkpoint(seen, rules, current, version, proposed.held).is_ok()
+ });
+ alive(current, proposed) && (backs || !proposed.yes.is_subset(&proposed.proposers))
+ });
+ if blocked {
+ return None;
+ }
+ let held: BTreeSet<Id> = store
+ .taken()
+ .iter()
+ .filter(|id| (seen.held)(id).is_some_and(|held| held >= rules.held_for))
+ .copied()
+ .collect();
+ let built_on: BTreeSet<Id> = held
+ .iter()
+ .filter_map(|id| store.get(id))
+ .filter_map(|bytes| match Event::read_taken(bytes)? {
+ Event::Signed(Signed { deps, .. }) | Event::Version { deps, .. } => Some(deps),
+ })
+ .flatten()
+ .collect();
+ let heads: Vec<Id> = held.difference(&built_on).copied().collect();
+ if heads.is_empty() || store.state_at(&heads).current().hash != current.hash {
+ return None;
+ }
+ let Json::Object(mut members) = current
+ .json
+ .without("number")
+ .without("changes")
+ .without("checkpoint")
+ else {
+ return None;
+ };
+ members.push(("number".to_owned(), Json::Int(current.number as i64 + 1)));
+ members.push(("changes".to_owned(), Json::Str(current.hash.to_string())));
+ members.push((
+ "checkpoint".to_owned(),
+ Json::Array(heads.iter().map(|id| Json::Str(id.to_string())).collect()),
+ ));
+ Json::object(members)
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use crate::federation::event::Checkpoint;
+ use crate::federation::harness::{self, Party, Spec};
+ use crate::federation::store::memory::Offered;
+
+ fn taken(store: &mut Store<Federation>, bytes: Vec<u8>) -> Id {
+ match store.offer(bytes) {
+ Offered::Taken(ids) => ids[0],
+ other => panic!("not taken: {other:?}"),
+ }
+ }
+
+ /// tv, lass and makefu, and a store of their federation.
+ fn three() -> (Party, Party, Party, Spec, Store<Federation>) {
+ 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 = Checkpoint {
+ at: Vec::new(),
+ keeps: Vec::new(),
+ version: Version::read(&first.json()).unwrap(),
+ };
+ let store = Store::new(root.bytes(), Vec::new()).unwrap();
+ (tv, lass, makefu, first, store)
+ }
+
+ fn record(store: &Store<Federation>, party: &str) -> Record {
+ let mut record = Record::begin(store.id(), party, store.state().current());
+ record.began = Id::of(b"earlier").to_string();
+ record
+ }
+
+ fn seen<'a>(
+ store: &'a Store<Federation>,
+ held: &'a dyn Fn(&Id) -> Option<Duration>,
+ ) -> Seen<'a> {
+ Seen {
+ store,
+ held,
+ since_move: Duration::ZERO,
+ }
+ }
+
+ #[test]
+ fn a_node_follows_a_party_on_checkpoints() {
+ let (tv, lass, _, first, mut store) = three();
+ let root = store.id();
+ let write = taken(
+ &mut store,
+ tv.write(&[root], "home/tv/a", harness::str("1")),
+ );
+ let mut checkpoint = first.after(first.hash());
+ checkpoint.checkpoint = Some(vec![write]);
+ let mut other = first.after(first.hash());
+ other.rules.push(("names/x".to_owned(), harness::str("tv")));
+ let proposal = taken(&mut store, tv.propose(&[write], &checkpoint.json()));
+ let elsewhere = taken(&mut store, tv.propose(&[write], &other.json()));
+ let rules = Rules {
+ follow: vec!["tv".to_owned()],
+ held_for: Duration::from_secs(60),
+ ..Rules::default()
+ };
+ let long = |_: &Id| Some(Duration::from_secs(3600));
+ let record = record(&store, "makefu");
+ assert!(decide(&seen(&store, &long), &rules, &record).is_empty());
+ taken(
+ &mut store,
+ tv.vote(&[proposal], first.hash(), checkpoint.hash(), true),
+ );
+ taken(
+ &mut store,
+ tv.vote(&[elsewhere], first.hash(), other.hash(), false),
+ );
+ // The checkpoint, followed; the other changes more, and isn't, by default.
+ let acts = decide(&seen(&store, &long), &rules, &record);
+ assert_eq!(acts.len(), 1);
+ assert!(matches!(
+ &acts[0],
+ Act::Vote { proposal, yes: true, .. } if *proposal == checkpoint.hash()
+ ));
+ let any = Rules {
+ follow_any: true,
+ ..rules.clone()
+ };
+ assert_eq!(decide(&seen(&store, &long), &any, &record).len(), 2);
+ // Heads leaving out what it held for a while before it was proposed: not backed.
+ let later = taken(
+ &mut store,
+ lass.write(&[root], "home/lass/b", harness::str("1")),
+ );
+ let held = |id: &Id| {
+ Some(if *id == later {
+ Duration::from_secs(7200)
+ } else {
+ Duration::from_secs(60)
+ })
+ };
+ assert!(decide(&seen(&store, &held), &rules, &record).is_empty());
+ }
+
+ #[test]
+ fn a_vote_by_hand_keeps_to_the_record() {
+ let (tv, _, _, first, mut store) = three();
+ let root = store.id();
+ let next = first.after(first.hash());
+ taken(&mut store, tv.propose(&[root], &next.json()));
+ let long = |_: &Id| Some(Duration::from_secs(3600));
+ let rules = Rules::default();
+ let mut record = record(&store, "tv");
+ assert!(by_hand(&seen(&store, &long), &rules, &record, Id::of(b"none"), true).is_err());
+ let act = by_hand(&seen(&store, &long), &rules, &record, next.hash(), true).unwrap();
+ assert!(matches!(act, Act::Vote { yes: true, .. }));
+ record.cast(
+ store.state().current(),
+ &tv.vote(&[root], first.hash(), next.hash(), true),
+ Vec::new(),
+ );
+ assert!(by_hand(&seen(&store, &long), &rules, &record, next.hash(), false).is_err());
+ }
+
+ #[test]
+ fn a_node_proposes_a_checkpoint_at_what_it_held_for_a_while() {
+ let (tv, _, _, first, mut store) = three();
+ let root = store.id();
+ let old = taken(
+ &mut store,
+ tv.write(&[root], "home/tv/a", harness::str("1")),
+ );
+ let new = taken(&mut store, tv.write(&[old], "home/tv/a", harness::str("2")));
+ let rules = Rules {
+ propose_events: Some(2),
+ held_for: Duration::from_secs(60),
+ ..Rules::default()
+ };
+ let held = |id: &Id| {
+ Some(if *id == new {
+ Duration::from_secs(1)
+ } else {
+ Duration::from_secs(3600)
+ })
+ };
+ let record = record(&store, "tv");
+ let acts = decide(&seen(&store, &held), &rules, &record);
+ let [Act::Propose(json)] = acts.as_slice() else {
+ panic!("not one proposal: {acts:?}");
+ };
+ let version = Version::read(json).unwrap();
+ assert_eq!(version.checkpoint, Some(vec![old]));
+ assert!(version.only_moves_on(store.state().current()));
+ assert_eq!(version.changes, Some(first.hash()));
+ // Not due: none.
+ let quiet = Rules {
+ propose_events: Some(3),
+ ..rules.clone()
+ };
+ assert!(decide(&seen(&store, &held), &quiet, &record).is_empty());
+ // Proposed, it backs it, and proposes none beside it.
+ let mut record = record;
+ let proposing = tv.propose(&[new], json);
+ record.signed(&proposing);
+ taken(&mut store, proposing);
+ let acts = decide(&seen(&store, &held), &rules, &record);
+ assert_eq!(acts.len(), 1);
+ assert!(matches!(&acts[0], Act::Vote { yes: true, .. }));
+ }
+}