diff options
| author | tv <tv@krebsco.de> | 2026-11-19 01:48:58 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-19 03:19:23 +0100 |
| commit | b00371d1260f4379241a9226d576270dd3a68285 (patch) | |
| tree | 05e4a4f86689112a75cb05fb09904546345937fa | |
| parent | 101080b8a62709cd2606dece086f959781bdf38f (diff) | |
vote: a proposal holds back checkpoints by a third, or new for a while
A node voting by itself proposes no checkpoint beside a proposal that holds it back, as
the checkpoint would lapse it, and a follower backs none so. A proposal held one back
where someone but its proposer backed it: two parties, or one and a stolen key, kept a
junk proposal alive, and no automatic checkpoint came while it lived, ending it taking
nays from more than a third each round. And one new, its proposer alone backing it, was
lapsed at once by a checkpoint its writes brought about.
A proposal that can still pass holds back now where a third of the parties back it,
someone but its proposer among them; or where it is new, held for less than a while
(`--store-held-for`), and its proposer has none older on the version: so it is heard
before a checkpoint lapses it, once a version for each proposer. Row 67 says so, and a
test of nine parties checks it.
| -rw-r--r-- | docs/federation.md | 27 | ||||
| -rw-r--r-- | docs/guides/federation/checkpoints.md | 9 | ||||
| -rw-r--r-- | docs/guides/federation/voting-by-itself.md | 12 | ||||
| -rw-r--r-- | src/config/mod.rs | 2 | ||||
| -rw-r--r-- | src/federation/vote.rs | 99 |
5 files changed, 117 insertions, 32 deletions
diff --git a/docs/federation.md b/docs/federation.md index 784915a..1d77e4f 100644 --- a/docs/federation.md +++ b/docs/federation.md @@ -511,20 +511,23 @@ as it judges any vote or proposal. The design has two in mind: and its `true` shown to some and its `false` to the rest would pass a proposal at one history and make it dead at another. By default it follows only on a version that only moves to a checkpoint ([Checkpoints](#checkpoints)), and only where no proposal that - changes more can still pass, but one nobody backs but its proposer: such a version - lapses every other proposal, and the party it follows would end any it disliked by - passing one. Even so, the parties following one hand it their votes on checkpoints: with - them, it passes one at heads of its choosing, by the voters' rule (below). Its operator - may have it follow on any version, which hands that party the node's `true`: a party - followed so by two thirds of the parties, its key kept on a node, passes what it backs. + changes more holds it back (below): such a version lapses every other proposal, and the + party it follows would end any it disliked by passing one. Even so, the parties + following one hand it their votes on checkpoints: with them, it passes one at heads of + its choosing, by the voters' rule (below). Its operator may have it follow on any + version, which hands that party the node's `true`: a party followed so by two thirds of + the parties, its key kept on a node, passes what it backs. * **Proposing a checkpoint**: propose a version that only moves to a checkpoint, at heads the node has held for a while, once conditions its operator sets are met: so many events or bytes held beyond its checkpoint, so many versions since it, or so long - by its own clock, by which nothing anyone judges goes. It proposes only where nothing - that can still pass is proposed on the current version, as such a version lapses what - is, but a proposal it wouldn't back that nobody backs but its proposer: so a party - keeping one alive holds back no checkpoint. It backs what it proposes, so that the - nodes following its party back it too. + by its own clock, by which nothing anyone judges goes. It proposes only where no + proposal on the current version holds it back, as such a version lapses what is: one it + would back that can still pass; one that can still pass that a third of the parties + back, someone but its proposer among them; or one new, held for less than a while, whose + proposer has none older on the version. So neither a party keeping a proposal alive, + nor two of a federation of seven or more, hold back checkpoints, and a new proposal is + lapsed by none before its proposer is heard, once a version. It backs what it proposes, + so that the nodes following its party back it too. Such a node keeps to what a party's client keeps to: one yes at a time; never `true` and `false` on one proposal, so a party has one node vote by itself, as two of its nodes @@ -738,7 +741,7 @@ fold, with crafted events. *Sim*: a simulation. *Bench*: measured, not judged. | 64 | Checkpoint heads before the current checkpoint, or at which it isn't current, or one in another's history | No version: a version event naming it is refused | unit | | 65 | After a checkpoint, a party that backed a second proposal once its first was dead, the nays that freed it withheld by those who cast them | Not named: its client keeps those nays with its `true` | unit | | 66 | Two clients of one party back two proposals at once, or its operator votes by hand beside the node that votes for it | Voting twice: a party votes from one client, the node that votes for it where it has one, through which it votes by hand | — | -| 67 | A party keeps a proposal alive that nobody else backs, to hold back automatic checkpoints | Holds back none: a node proposes a checkpoint beside a proposal it wouldn't back that nobody backs but its proposer | sim | +| 67 | A party keeps a proposal alive that nobody else backs, or two parties of seven or more, to hold back automatic checkpoints | Holds back none past a while: a node proposes a checkpoint beside a proposal it wouldn't back that fewer than a third of the parties back, or nobody but its proposer; a new one holds back for a while, once a version for its proposer | sim | | 68 | A checkpoint proposed at heads that leave out what was written since: a key set dropping a stolen key, say | Not backed: clients and nodes back a checkpoint only where what they held for a while is among its heads, in their history, or above them; a node shows what they lack | unit | | 69 | A key a version names, stolen, writes its party's node list at a history from before the version naming the party's keys anew, beside the list the party writes under that version, several, for the lowest ID | The party's counts: of a party's lists, those written under the latest version come first | unit | | 70 | A checkpoint's version proposed again, by an event beside its heads | Voters back it all the same, as a proposal lapses with the move, and vote on the events proposing it above its heads, as a node shows them; a version event on votes beside them is refused | unit | diff --git a/docs/guides/federation/checkpoints.md b/docs/guides/federation/checkpoints.md index 345bc98..f935421 100644 --- a/docs/guides/federation/checkpoints.md +++ b/docs/guides/federation/checkpoints.md @@ -37,8 +37,9 @@ nothing that can still pass is proposed on the current version. A node voting for its party by itself proposes checkpoints by its operator's rules: once it holds so many events beyond its checkpoint (`--store-propose-events`), or so long after its store moved there (`--store-propose-every`), at the heads of what it held for -a while (`--store-held-for`, ten minutes unless set), where nothing that can still pass -is proposed; and it backs what it proposes. +a while (`--store-held-for`, ten minutes unless set), where no proposal holds it back +([`voting-by-itself.md`](voting-by-itself.md), [Its rules](voting-by-itself.md#its-rules)); +and it backs what it proposes. ## Backing one @@ -52,7 +53,9 @@ yourself, or vote through such a node. * `--store-follow PARTY,…` has a node voting by itself follow those parties' `true`, by default on versions that only move to a checkpoint, and still by that rule, but not - where a proposal changing more can still pass that someone but its proposer backs. + where a proposal changing more holds it back, as a node proposing one keeps to + ([`voting-by-itself.md`](voting-by-itself.md), + [Its rules](voting-by-itself.md#its-rules)). * `--store-back-after` (ten minutes unless set) has it back none before its store held its checkpoint, or ran, that long. * `--store-nay-beside` has it vote `false` on every other version only moving to a diff --git a/docs/guides/federation/voting-by-itself.md b/docs/guides/federation/voting-by-itself.md index 97f4eff..cfcdcf3 100644 --- a/docs/guides/federation/voting-by-itself.md +++ b/docs/guides/federation/voting-by-itself.md @@ -38,8 +38,8 @@ or `POST /admin/events/vote` with `{"proposal": "8d02…", "yes": true}`. * **Following** (`--store-follow PARTY,…`): it votes `true` on a proposal where a party it follows voted `true`, never `false`; by default only on a version that only moves to - a checkpoint, and only where no proposal changing more can still pass that someone but - its proposer backs, as a checkpoint lapses it. Even so, the parties following one hand + a checkpoint, and only where no proposal changing more holds it back (below), as a + checkpoint lapses it. Even so, the parties following one hand it their votes on checkpoints. With `--store-follow-any`, on any version: that hands those parties the node's `true`. A party followed so by two thirds of the parties, with its key kept on a node, passes what it backs. @@ -51,9 +51,11 @@ or `POST /admin/events/vote` with `{"proposal": "8d02…", "yes": true}`. DURATION`): once it holds so many events beyond its checkpoint, or so long after its store 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 (`--store-held-for`, ten minutes - unless set), 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, so that the nodes following its party back it too. + unless set), where no proposal on the current version holds it back: one it would back + that can still pass; one that can still pass that a third of the parties back, someone + but its proposer among them; or one held for less than a while whose proposer has none + older on the version. It backs what it proposes, so that the nodes following its party + back it too. * **`false` beside** (`--store-nay-beside`): where it backs a proposal that can still pass, it votes `false` on every other version only moving to a checkpoint, so that of two checkpoints proposed at once the other dies, and its backers are free. diff --git a/src/config/mod.rs b/src/config/mod.rs index 412753e..feb16e3 100644 --- a/src/config/mod.rs +++ b/src/config/mod.rs @@ -294,7 +294,7 @@ pub(crate) const OPTIONS: &[OptionSpec] = &[ Kind::Integer, "COUNT", None, - "With store-vote-key: propose a version that only moves to a checkpoint once it holds this many events beyond its checkpoint, at the heads of what it held for a while (store-held-for), where nothing that can still pass is proposed on the current version; it backs what it proposes.", + "With store-vote-key: propose a version that only moves to a checkpoint once it holds this many events beyond its checkpoint, at the heads of what it held for a while (store-held-for), where no proposal on the current version holds it back (docs/federation.md, Votes a node casts by itself); it backs what it proposes.", ), #[cfg(feature = "federation")] option( diff --git a/src/federation/vote.rs b/src/federation/vote.rs index bf866e7..4c4cdfa 100644 --- a/src/federation/vote.rs +++ b/src/federation/vote.rs @@ -5,13 +5,14 @@ //! * **Following**: it votes `true` on a proposal on the current version where a party it //! 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. +//! more holds it back (`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 -//! 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. +//! a checkpoint, at the heads of what it held for a while, where no proposal on the +//! current version holds it back: one it would back that can still pass, one that can +//! still pass that a third of the parties back, someone but its proposer among them, or +//! one new, held less than a while, whose proposer has no older one on the version +//! (`holds_back`). 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 @@ -208,10 +209,21 @@ 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) +/// Whether `proposed`, of `all`, holds back a version that only moves to a checkpoint, +/// which would lapse it: it can still pass, and a third of the parties back it, someone +/// but its proposer among them; or it came less than `grace` ago, and its proposer has no +/// older proposal on the version. So two parties keep no proposal alive to hold back +/// checkpoints, and one new is lapsed by none before its proposer is heard, once. +fn holds_back(current: &Version, proposed: &Proposed, all: &[Proposed], grace: Duration) -> bool { + let backed = !proposed.yes.is_subset(&proposed.proposers) + && 3 * proposed.yes.len() >= current.parties.len(); + let fresh = proposed.held < grace + && !all.iter().any(|other| { + other.hash != proposed.hash + && other.held >= grace + && !other.proposers.is_disjoint(&proposed.proposers) + }); + alive(current, proposed) && (backed || fresh) } /// What a node voting by itself by `rules` signs now, as it sees its store, by @@ -262,7 +274,7 @@ pub(crate) fn decide(seen: &Seen<'_>, rules: &Rules, record: &Record) -> Vec<Act .version .as_ref() .is_some_and(|version| version.only_moves_on(¤t)) - && holds_back(¤t, other) + && holds_back(¤t, other, &all, rules.held_for) }); if !own_one && moves_on && lapses { continue; @@ -409,7 +421,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) || holds_back(current, proposed) + (alive(current, proposed) && backs) || holds_back(current, proposed, all, rules.held_for) }); if blocked { return None; @@ -642,6 +654,71 @@ mod tests { assert!(decide(&seen(&store, &long), &rules, &record).is_empty()); } + /// Of nine parties, two keep a proposal alive: it holds back no checkpoint a node + /// proposes, as fewer than a third back it. A new one holds back for a while, but not + /// one from a proposer whose earlier one is past that while. + #[test] + fn two_parties_hold_back_no_checkpoint_but_a_new_proposal_does_for_a_while() { + let parties: Vec<Party> = (1..=9).map(|n| Party::new(&format!("p{n}"), n)).collect(); + let named: Vec<&Party> = parties.iter().collect(); + let first = Spec::first(&named, &[]); + let mut store = Store::new(first.root(), Vec::new()).expect("a root"); + let root = store.id(); + let on = first.hash(); + let write = taken( + &mut store, + parties[2].write(&[root], "home/p3/a", harness::str("1")), + ); + let junk = |n: usize| { + let mut junk = first.after(on); + junk.rules.push((format!("names/x{n}"), harness::str("p1"))); + junk + }; + let old = taken(&mut store, parties[0].propose(&[root], &junk(1).json())); + taken( + &mut store, + parties[0].vote(&[old], on, junk(1).hash(), true), + ); + taken( + &mut store, + parties[1].vote(&[old], on, junk(1).hash(), true), + ); + let rules = Rules { + propose_events: Some(1), + held_for: Duration::from_secs(60), + ..Rules::default() + }; + let record = record(&store, "p3"); + let proposes = |acts: Vec<Act>| matches!(acts.as_slice(), [Act::Propose(_)]); + let long = |_: &Id| Some(Duration::from_secs(3600)); + assert!(proposes(decide(&seen(&store, &long), &rules, &record))); + // One by p4, new: held back, for a while. + let new = taken(&mut store, parties[3].propose(&[write], &junk(2).json())); + let fresh = |id: &Id| { + Some(if *id == new { + Duration::from_secs(1) + } else { + Duration::from_secs(3600) + }) + }; + assert!(decide(&seen(&store, &fresh), &rules, &record).is_empty()); + assert!(proposes(decide(&seen(&store, &long), &rules, &record))); + // One by p1 again, new, while its old one is past that while: not. + let again = taken(&mut store, parties[0].propose(&[write], &junk(3).json())); + let fresh_again = |id: &Id| { + Some(if *id == again { + Duration::from_secs(1) + } else { + Duration::from_secs(3600) + }) + }; + assert!(proposes(decide( + &seen(&store, &fresh_again), + &rules, + &record + ))); + } + /// 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. |
