//! 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. //! * **Voting `false` beside**: where it backs a proposal that can still pass, it votes //! `false` on every other proposal on the current version that only moves to a //! checkpoint, so that, of two checkpoints proposed at once, the one it doesn't back //! dies and its backers are free. //! //! 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, /// 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, /// ...or so long after the store moved to it, by its own clock. pub(crate) propose_every: Option, /// How long it holds an event before it holds it for a while. pub(crate) held_for: Duration, /// Voting `false` on a checkpoint proposed beside one it backs. pub(crate) nay_beside: bool, } /// 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, pub(crate) held: &'a dyn Fn(&Id) -> Option, 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>, }, /// 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, /// Its proposing events' parties, and how long the node has held the first. proposers: BTreeSet, held: Duration, /// Its votes: each party's, and the events, as bytes. yes: BTreeSet, no: BTreeSet, votes: Vec>, } fn proposed(seen: &Seen<'_>, current: &Version) -> Vec { let store = seen.store; let mut all = Vec::new(); for (hash, ballot) in store.state().ballots(¤t.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 = 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 { let current = seen.store.state().current().clone(); let all = proposed(seen, ¤t); let mut acts = Vec::new(); let mut backed = false; // Its own proposals it backs; others as the parties it follows voted. let own: BTreeSet = 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> = all .iter() .flat_map(|proposed| proposed.votes.iter().cloned()) .collect(); for proposed in &all { let follows = |votes: &BTreeSet| 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(¤t)); 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, ¤t, version, proposed.held).is_err() })) { continue; } if let Ok(kept) = record.may_vote(¤t, proposed.hash, &proposed.json, yes, &nays) { backed |= yes; acts.push(Act::Vote { proposal: proposed.hash, yes, nays: kept, }); } } if rules.nay_beside { acts.extend(beside(¤t, &all, &acts, record, &nays)); } if !backed && let Some(version) = checkpoint(seen, rules, ¤t, &all) { let hash = Id::of(&version.bytes()); if record .may_vote(¤t, hash, &version, true, &nays) .is_ok() { acts.push(Act::Propose(version)); } } acts } /// The votes `false` a node casts beside what it backs: where its party backs a proposal on /// `current` that can still pass, by its `record` or by `acts`, on every other proposal /// that only moves to a checkpoint and can still pass, but where it votes already. fn beside( current: &Version, all: &[Proposed], acts: &[Act], record: &Record, nays: &[Vec], ) -> Vec { let voting: BTreeSet = acts .iter() .filter_map(|act| match act { Act::Vote { proposal, .. } => Some(*proposal), Act::Propose(_) => None, }) .collect(); let backs: BTreeSet = record .backs(¤t.hash) .into_iter() .chain(acts.iter().filter_map(|act| match act { Act::Vote { proposal, yes: true, .. } => Some(*proposal), _ => None, })) .collect(); let backing = all .iter() .any(|proposed| backs.contains(&proposed.hash) && alive(current, proposed)); if !backing { return Vec::new(); } all.iter() .filter(|proposed| { !backs.contains(&proposed.hash) && !voting.contains(&proposed.hash) && alive(current, proposed) && proposed .version .as_ref() .is_some_and(|version| version.only_moves_on(current)) }) .filter(|proposed| { record .may_vote(current, proposed.hash, &proposed.json, false, nays) .is_ok() }) .map(|proposed| Act::Vote { proposal: proposed.hash, yes: false, nays: Vec::new(), }) .collect() } /// 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 { let current = seen.store.state().current().clone(); let all = proposed(seen, ¤t); 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, ¤t, version, proposed.held)?; } let nays: Vec> = all .iter() .flat_map(|proposed| proposed.votes.iter().cloned()) .collect(); let nays = record.may_vote(¤t, 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 { 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 = store .taken() .iter() .filter(|id| (seen.held)(id).is_some_and(|held| held >= rules.held_for)) .copied() .collect(); let built_on: BTreeSet = 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 = 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, bytes: Vec) -> 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) { 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, 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, held: &'a dyn Fn(&Id) -> Option, ) -> 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, .. })); } /// Two checkpoints proposed at once: a node backing one votes `false` on the other by /// its rule, and on nothing else; without the rule, on nothing. #[test] fn a_node_votes_false_on_a_checkpoint_beside_the_one_it_backs() { let (tv, lass, _, first, mut store) = three(); let root = store.id(); let on = first.hash(); let here = taken( &mut store, tv.write(&[root], "home/tv/a", harness::str("1")), ); let there = taken( &mut store, lass.write(&[root], "home/lass/b", harness::str("1")), ); let (mut one, mut two) = (first.after(on), first.after(on)); one.checkpoint = Some(vec![here]); two.checkpoint = Some(vec![there]); let mut other = first.after(on); other.rules.push(("names/x".to_owned(), harness::str("tv"))); let proposing = tv.propose(&[here], &one.json()); let mut record = record(&store, "tv"); record.signed(&proposing); let proposal = taken(&mut store, proposing); let by_lass = [ taken(&mut store, lass.propose(&[there], &two.json())), taken(&mut store, lass.propose(&[root], &other.json())), ]; // lass's, held since its proposals came, after tv proposed. let long = |id: &Id| { Some(if *id == there || by_lass.contains(id) { Duration::from_secs(60) } else { Duration::from_secs(3600) }) }; let rules = Rules { nay_beside: true, ..Rules::default() }; // Backing its own, this round: `false` on the other checkpoint, not on the version // that changes more. let acts = decide(&seen(&store, &long), &rules, &record); assert_eq!(acts.len(), 2, "{acts:?}"); assert!(acts.contains(&Act::Vote { proposal: one.hash(), yes: true, nays: Vec::new() })); assert!(acts.contains(&Act::Vote { proposal: two.hash(), yes: false, nays: Vec::new() })); let quiet = Rules::default(); assert_eq!(decide(&seen(&store, &long), &quiet, &record).len(), 1); // Its `true` recorded and taken: `false` on the other, once. let yes = tv.vote(&[proposal], on, one.hash(), true); record.cast(store.state().current(), &yes, Vec::new()); taken(&mut store, yes); let acts = decide(&seen(&store, &long), &rules, &record); assert_eq!( acts, vec![Act::Vote { proposal: two.hash(), yes: false, nays: Vec::new() }] ); let no = tv.vote(&[proposal], on, two.hash(), false); record.cast(store.state().current(), &no, Vec::new()); assert!(decide(&seen(&store, &long), &rules, &record).is_empty()); } }