diff options
Diffstat (limited to 'src/federation')
| -rw-r--r-- | src/federation/mod.rs | 1 | ||||
| -rw-r--r-- | src/federation/vote.rs | 513 |
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(¤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<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, ¤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<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(¤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 !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 +} + +/// 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, ¤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<Vec<u8>> = 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<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, .. })); + } +} |
