summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-19 01:48:57 +0000
committertv <tv@krebsco.de>2026-11-19 03:19:19 +0100
commit101080b8a62709cd2606dece086f959781bdf38f (patch)
tree618e9acdd6e5d311ece2cf5b213432257c31bc39 /src
parente0075264e9efdd4c8a32290c0d5643e7f48bfb14 (diff)
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.
Diffstat (limited to 'src')
-rw-r--r--src/config/mod.rs14
-rw-r--r--src/federation/vote.rs176
-rw-r--r--src/lib.rs1
3 files changed, 157 insertions, 34 deletions
diff --git a/src/config/mod.rs b/src/config/mod.rs
index 8196db6..412753e 100644
--- a/src/config/mod.rs
+++ b/src/config/mod.rs
@@ -312,6 +312,14 @@ pub(crate) const OPTIONS: &[OptionSpec] = &[
Some("10m"),
"With store-vote-key: how long it holds an event before it holds it for a while: it proposes a checkpoint at the heads of such, and backs none whose heads leave out one it held for a while before it was proposed.",
),
+ #[cfg(feature = "federation")]
+ option(
+ "store-back-after",
+ Kind::Duration,
+ "DURATION",
+ Some("10m"),
+ "With store-vote-key: how long its store holds its checkpoint, or runs, by its own clock, before it backs or proposes a later one, by itself or by hand: a party it follows moves the store once that long at most, and just started it backs none, as it holds nothing for a while yet.",
+ ),
option(
"strict-keys",
Kind::List,
@@ -832,6 +840,12 @@ pub(crate) struct Settings {
with = "crate::units::duration_option"
)]
pub(crate) store_held_for: Duration,
+ #[cfg(feature = "federation")]
+ #[serde(
+ default = "default_store_held_for",
+ with = "crate::units::duration_option"
+ )]
+ pub(crate) store_back_after: Duration,
#[serde(default)]
pub(crate) strict_keys: Vec<String>,
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<Proposed> {
/// 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<Act> {
@@ -218,36 +238,48 @@ pub(crate) fn decide(seen: &Seen<'_>, rules: &Rules, record: &Record) -> Vec<Act
.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 {
+ 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(&current));
- 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(&current))
+ && holds_back(&current, 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, &current, version, proposed.held).is_err()
- }))
+ if 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;
+ if let Ok(kept) = record.may_vote(&current, 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]
diff --git a/src/lib.rs b/src/lib.rs
index 739f712..66d54bc 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -70,6 +70,7 @@ fn voter(args: &config::Settings) -> Result<Option<federation::held::Voter>> {
propose_events: args.store_propose_events,
propose_every: args.store_propose_every,
held_for: args.store_held_for,
+ back_after: args.store_back_after,
},
}))
}