From 101080b8a62709cd2606dece086f959781bdf38f Mon Sep 17 00:00:00 2001 From: tv Date: Thu, 19 Nov 2026 01:48:57 +0000 Subject: vote: a follower copies no false, lapses nothing others back, waits after a move A node following a party (`--store-follow`) handed it more than the text said: * it copied the party's `false`: one party's nay freed bound followers, and its `true` shown to some and its `false` to the rest passed a checkpoint at one history and made it dead at another. It copies the `true` alone now, on any version too; * a checkpoint lapses every other proposal: the followed party ended any proposal it disliked by passing one. A node follows a checkpoint only where no proposal that changes more can still pass that someone but its proposer backs; * nothing bounded how often the store moved, so fresh events could be left out of every checkpoint; and a node just started held nothing for a while, so the voters' rule kept nothing. A node backs, and proposes, a checkpoint only once its store held its checkpoint, or ran, for a while (`--store-back-after`, ten minutes unless set), by itself or by hand. `federation.md` says what following hands over, and row 58 what a follower on any version copies; the guides and the example say the rest. --- src/federation/vote.rs | 176 +++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 142 insertions(+), 34 deletions(-) (limited to 'src/federation') diff --git a/src/federation/vote.rs b/src/federation/vote.rs index 693339e..bf866e7 100644 --- a/src/federation/vote.rs +++ b/src/federation/vote.rs @@ -3,9 +3,10 @@ //! 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`. +//! follows voted `true`, never `false`; by default only on a version that only moves to a +//! checkpoint (`Version::only_moves_on`), and then only where no proposal that changes +//! more can still pass, but one nobody backs but its proposer (`holds_back`), as such a +//! version lapses it. //! * **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 @@ -20,7 +21,9 @@ //! 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`). +//! it was proposed (`Store::left_out`), and only once its store held its checkpoint, or +//! ran, for a while (`Rules::back_after`): a party it follows moves the store once that +//! long at most, and a node just started backs none, as it holds nothing for a while yet. use std::collections::BTreeSet; use std::time::Duration; @@ -48,6 +51,9 @@ pub(crate) struct Rules { pub(crate) held_for: Duration, /// Voting `false` on a checkpoint proposed beside one it backs. pub(crate) nay_beside: bool, + /// How long its store holds its checkpoint, or runs, before it backs or proposes a + /// later one. + pub(crate) back_after: Duration, } /// What the node sees: its store, how long it has held each event it took, and how long @@ -144,7 +150,8 @@ fn proposed(seen: &Seen<'_>, current: &Version) -> Vec { /// 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, proposals and votes aside, which lapse with the move. +/// before it was proposed, proposals and votes aside, which lapse with the move; and only +/// once its store held its checkpoint, or ran, for a while (`Rules::back_after`). pub(crate) fn backs_checkpoint( seen: &Seen<'_>, rules: &Rules, @@ -160,6 +167,13 @@ pub(crate) fn backs_checkpoint( "a checkpoint that changes more than its number and what it changes".to_owned(), ); } + if seen.since_move < rules.back_after { + return Err(format!( + "its store held its checkpoint, or ran, {}s: it backs a later one after {}s", + seen.since_move.as_secs(), + rules.back_after.as_secs() + )); + } let before = proposed_held + rules.held_for; // Proposals and votes lapse with the move: they count no more on the version after. let lapsing = |id: &Id| { @@ -194,6 +208,12 @@ fn alive(current: &Version, proposed: &Proposed) -> bool { 3 * (parties - proposed.no.len().min(parties)) >= 2 * parties } +/// Whether `proposed` holds back a version that only moves to a checkpoint, which would +/// lapse it: it can still pass, and someone but its proposer backs it. +fn holds_back(current: &Version, proposed: &Proposed) -> bool { + alive(current, proposed) && !proposed.yes.is_subset(&proposed.proposers) +} + /// 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 { @@ -218,36 +238,48 @@ pub(crate) fn decide(seen: &Seen<'_>, rules: &Rules, record: &Record) -> Vec| 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 { + let own_one = own.contains(&proposed.hash); + // A `false` it copies not: one party's would free bound followers. + let follows = rules + .follow + .iter() + .any(|party| proposed.yes.contains(party)); + if !own_one && !follows { 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 { + if !own_one && !rules.follow_any && !moves_on { + continue; + } + // A checkpoint lapses what else is proposed: the party it follows may not end so + // a proposal that changes more. + let lapses = all.iter().any(|other| { + other.hash != proposed.hash + && !other + .version + .as_ref() + .is_some_and(|version| version.only_moves_on(¤t)) + && holds_back(¤t, other) + }); + if !own_one && moves_on && lapses { 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() - })) + if 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; + if let Ok(kept) = record.may_vote(¤t, proposed.hash, &proposed.json, true, &nays) { + backed = true; acts.push(Act::Vote { proposal: proposed.hash, - yes, + yes: true, nays: kept, }); } @@ -369,7 +401,7 @@ fn checkpoint(seen: &Seen<'_>, rules: &Rules, current: &Version, all: &[Proposed || rules .propose_every .is_some_and(|every| seen.since_move >= every); - if !due { + if !due || seen.since_move < rules.back_after { return None; } let blocked = all.iter().any(|proposed| { @@ -377,7 +409,7 @@ fn checkpoint(seen: &Seen<'_>, rules: &Rules, current: &Version, all: &[Proposed 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)) + (alive(current, proposed) && backs) || holds_back(current, proposed) }); if blocked { return None; @@ -506,11 +538,12 @@ mod tests { &acts[0], Act::Vote { proposal, yes: true, .. } if *proposal == checkpoint.hash() )); + // On any version, the checkpoint still; the other's `false` it copies not. let any = Rules { follow_any: true, ..rules.clone() }; - assert_eq!(decide(&seen(&store, &long), &any, &record).len(), 2); + assert_eq!(decide(&seen(&store, &long), &any, &record).len(), 1); // Heads leaving out what it held for a while before it was proposed: not backed. let later = taken( &mut store, @@ -528,7 +561,8 @@ mod tests { /// Row 58 (`docs/federation.md`): a party the node follows backs, or votes `false` on, /// a version that changes more than moving to a checkpoint: by default the node follows - /// neither; one following on any version, as its operator chose, follows both. + /// neither; one following on any version, as its operator chose, backs the one, and + /// copies the `false` not. #[test] fn federation_attack_58() { let (tv, _, _, first, mut store) = three(); @@ -563,15 +597,89 @@ mod tests { ..rules }; let acts = decide(&seen(&store, &long), &any, &record); - assert_eq!(acts.len(), 2); - assert!(acts.iter().any(|act| matches!( - act, + assert_eq!(acts.len(), 1); + assert!(matches!( + &acts[0], Act::Vote { proposal, yes: true, .. } if *proposal == backed.hash() - ))); - assert!(acts.iter().any(|act| matches!( - act, - Act::Vote { proposal, yes: false, .. } if *proposal == opposed.hash() - ))); + )); + } + + /// A party the node follows backs a checkpoint while a proposal that changes more, + /// which another party backs, can still pass: the node backs it not, as it would lapse + /// that one; while nobody but its proposer backs that one, it does. + #[test] + fn a_follower_lets_no_checkpoint_lapse_what_others_back() { + let (tv, lass, _, first, mut store) = three(); + let root = store.id(); + let on = first.hash(); + let write = taken( + &mut store, + tv.write(&[root], "home/tv/a", harness::str("1")), + ); + let mut checkpoint = first.after(on); + checkpoint.checkpoint = Some(vec![write]); + let mut other = first.after(on); + other + .rules + .push(("names/x".to_owned(), harness::str("lass"))); + let proposal = taken(&mut store, tv.propose(&[write], &checkpoint.json())); + let elsewhere = taken(&mut store, lass.propose(&[root], &other.json())); + taken( + &mut store, + tv.vote(&[proposal], on, checkpoint.hash(), true), + ); + let rules = Rules { + follow: vec!["tv".to_owned()], + ..Rules::default() + }; + let long = |_: &Id| Some(Duration::from_secs(3600)); + let record = record(&store, "makefu"); + // lass proposed the other, and backs it alone: the checkpoint, followed. + taken(&mut store, lass.vote(&[elsewhere], on, other.hash(), true)); + assert_eq!(decide(&seen(&store, &long), &rules, &record).len(), 1); + // Backed by another too: not. + taken(&mut store, tv.vote(&[elsewhere], on, other.hash(), true)); + assert!(decide(&seen(&store, &long), &rules, &record).is_empty()); + } + + /// A node backs no checkpoint, and proposes none, before its store held its checkpoint, + /// or ran, for a while: a party it follows moves the store once that long at most, and + /// just started it holds nothing for a while yet. + #[test] + fn a_node_backs_no_checkpoint_soon_after_a_move_or_its_start() { + let (tv, _, _, first, mut store) = three(); + let root = store.id(); + let on = first.hash(); + let write = taken( + &mut store, + tv.write(&[root], "home/tv/a", harness::str("1")), + ); + let mut checkpoint = first.after(on); + checkpoint.checkpoint = Some(vec![write]); + let proposal = taken(&mut store, tv.propose(&[write], &checkpoint.json())); + taken( + &mut store, + tv.vote(&[proposal], on, checkpoint.hash(), true), + ); + let rules = Rules { + follow: vec!["tv".to_owned()], + propose_events: Some(1), + back_after: Duration::from_secs(600), + ..Rules::default() + }; + let long = |_: &Id| Some(Duration::from_secs(3600)); + let record = record(&store, "makefu"); + let soon = Seen { + store: &store, + held: &long, + since_move: Duration::from_secs(60), + }; + assert!(decide(&soon, &rules, &record).is_empty()); + let later = Seen { + since_move: Duration::from_secs(700), + ..soon + }; + assert_eq!(decide(&later, &rules, &record).len(), 1); } #[test] -- cgit v1.3.1