From efaf79e7fd55db2b9704ccefedde33346f874a1d Mon Sep 17 00:00:00 2001 From: tv Date: Thu, 19 Nov 2026 03:56:57 +0000 Subject: vote: a node proposes a checkpoint at the heads it holds A node proposed a checkpoint at the heads of what it held for a while: every event written in that while, and every one built on an event beside those heads, as one party writing now and then on something old makes them, was beside them, and refused once the store moved. A voter whose while was shorter backed none, one whose while was longer backed it and lost those. It proposes at the heads its store holds, sorted: what was written before is in their history, and only what is written while the vote takes its course may be beside them. It proposes none where they are more than an event may name: under a revision with merge events, it merges them first; otherwise, what is written after does. `--store-held-for` keeps the voters' rule and how long a new proposal holds back a checkpoint. `federation.md`, the guides and the options say so. --- docs/federation.md | 71 ++++++++++++++++-------------- docs/guides/federation/checkpoints.md | 12 ++--- docs/guides/federation/voting-by-itself.md | 10 +++-- src/config/mod.rs | 4 +- src/federation/vote.rs | 53 +++++++++++----------- 5 files changed, 79 insertions(+), 71 deletions(-) diff --git a/docs/federation.md b/docs/federation.md index d10a220..30bff6e 100644 --- a/docs/federation.md +++ b/docs/federation.md @@ -462,36 +462,37 @@ than it may name dependencies. The current checkpoint at a history is the one th version of that history's chain that names one names, or else the root: a question of the history alone. As the version naming the current checkpoint is among the next checkpoint's heads or in their history, every later version naming one names heads after those, and a -node starting from a checkpoint holds what judging them reads. A proposer names heads it -has held for a while, by its own clock, which judges nothing, so that every node holds -them. A party's client, and a node voting by itself, back a checkpoint only where -everything they held for a while before it was proposed is among its heads, in their -history, or above them, proposals and votes aside, which lapse with the move: a move -refuses what isn't above its heads, and heads a proposer made up, built on little, would -take back what was written since, a key set dropping a stolen key among it. A node shows, -for a proposed checkpoint, what it holds that its heads lack, as for a fork -([Forks](#forks)). This is the voter's rule, by its own clock: nothing more is judged. It -is a version only where its proposal is above those heads, and a version event writing it -is taken only where it is above them too, and so is every vote it is written on -([`store.md`](store.md), [Events](store.md#events)): so moving to the checkpoint refuses -nothing that decided it. A party's client, and a node voting by itself, vote on the events -proposing what they vote on that are above those heads, as a node shows them, and a node -proposes a checkpoint on its heads: so their votes are above those heads wherever the -proposal is. One proposing it again beside them they don't build on, as a vote on it would -be beside them too. A vote beside them binds its party as any yes does, until the move -refuses it. A node that takes the version moves to the checkpoint: it builds it, forgets -everything before those heads that it doesn't keep, and every event not above them, and -refuses such events from then on. Judging an event after them needs nothing it forgot: the -version, every party's keys and node list, and the proposals on the current version with -their votes all count, and are kept. A node starting from a checkpoint reads what it keeps -as written under its version, as it holds none of their histories: each was written under -that one or an earlier, counting there, a kept proposal is on it, and a later `since` that -leaves one out is past it. A node that can't build a checkpoint, as it was away across a -move and a remake after it, or as it joins, takes it only where its operator pins it -([`store.md`](store.md), [Pinned checkpoints](store.md#pinned-checkpoints)). What it can't -check of its heads it takes on its operator's word: that they are after the checkpoint -current at the version naming them, at which that one is current too; so it judges that -version as every node does. +node starting from a checkpoint holds what judging them reads. A proposer names the heads +it holds as it proposes, so that what was written before is in their history: a node +lacking one takes the proposal once it holds it. A party's client, and a node voting by +itself, back a checkpoint only where everything they held for a while before it was +proposed is among its heads, in their history, or above them, proposals and votes aside, +which lapse with the move: a move refuses what isn't above its heads, and heads a proposer +made up, built on little, would take back what was written since, a key set dropping a +stolen key among it. A node shows, for a proposed checkpoint, what it holds that its heads +lack, as for a fork ([Forks](#forks)). This is the voter's rule, by its own clock: nothing +more is judged. It is a version only where its proposal is above those heads, and a +version event writing it is taken only where it is above them too, and so is every vote it +is written on ([`store.md`](store.md), [Events](store.md#events)): so moving to the +checkpoint refuses nothing that decided it. A party's client, and a node voting by itself, +vote on the events proposing what they vote on that are above those heads, as a node shows +them, and a node proposes a checkpoint on its heads: so their votes are above those heads +wherever the proposal is. One proposing it again beside them they don't build on, as a +vote on it would be beside them too. A vote beside them binds its party as any yes does, +until the move refuses it. A node that takes the version moves to the checkpoint: it +builds it, forgets everything before those heads that it doesn't keep, and every event not +above them, and refuses such events from then on. Judging an event after them needs +nothing it forgot: the version, every party's keys and node list, and the proposals on the +current version with their votes all count, and are kept. A node starting from a +checkpoint reads what it keeps as written under its version, as it holds none of their +histories: each was written under that one or an earlier, counting there, a kept proposal +is on it, and a later `since` that leaves one out is past it. A node that can't build a +checkpoint, as it was away across a move and a remake after it, or as it joins, takes it +only where its operator pins it ([`store.md`](store.md), +[Pinned checkpoints](store.md#pinned-checkpoints)). What it can't check of its heads it +takes on its operator's word: that they are after the checkpoint current at the version +naming them, at which that one is current too; so it judges that version as every node +does. What a checkpoint loses: what counted no more before it, so that a key added back, or a place given back, brings back nothing signed before it, and a party that voted twice on @@ -499,8 +500,8 @@ a version behind it shows only in the votes kept outside the store: a client kee own votes and the nays that freed it, not another party's two, so where keys voted twice, whoever saw it keeps the votes naming the party (`GET /events/{id}`) before a checkpoint leaves them out; and what isn't above its heads, which its party signs again. Few are: the -heads are ones its proposer held for a while, no voter backs heads that leave out what it -held for a while, nodes build on them while the vote takes its course, a client writing +heads are those its proposer held as it proposed, no voter backs heads that leave out what +it held for a while, nodes build on them while the vote takes its course, a client writing once a checkpoint is proposed builds only on what is above its heads, and a party's client signs again what a move refused. @@ -541,8 +542,10 @@ as it judges any vote or proposal. The design has two in mind: revision it follows never: its party's operators vote on that one by hand, once their nodes run a continuum that knows it ([Changing the federation](#changing-the-federation)). -* **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 +* **Proposing a checkpoint**: propose a version that only moves to a checkpoint, at the + heads the node holds, where they are no more than an event may name (a node merges them + first, under a revision with merge events, [Nodes](#nodes)), 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. One after every version ends, at the checkpoint, what keys voting twice could grow beside that version at a history diff --git a/docs/guides/federation/checkpoints.md b/docs/guides/federation/checkpoints.md index cd77e28..ad468f8 100644 --- a/docs/guides/federation/checkpoints.md +++ b/docs/guides/federation/checkpoints.md @@ -26,9 +26,9 @@ current version's hash as `changes`, and the heads as `checkpoint` ([`proposing-and-voting.md`](proposing-and-voting.md), [Writing a version](proposing-and-voting.md#writing-a-version)). The heads are events after the current checkpoint, at which the current version is current too, none in -another's history, their IDs ascending: heads a node showed (`heads` in `GET /events`) -once the version was written, and that it has held for a while since, so that every node -holds them. Propose it afterwards: the client signs the proposal on the heads its node +another's history, their IDs ascending: the heads a node shows (`heads` in `GET /events`) +as late as you can, so that what was written before is in their history. Propose it +then: the client signs the proposal on the heads its node shows then, above the ones it names, as it must be. Like any version, it lapses the proposals on the version before: propose one where @@ -37,9 +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`), so many versions were written since it (`--store-propose-versions`, after every version with 1), -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 no proposal holds it -back ([`voting-by-itself.md`](voting-by-itself.md), +or so long after its store moved there (`--store-propose-every`), at the heads it holds, +no more than an event may name (64, which it merges first under a revision with merge +events), 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 diff --git a/docs/guides/federation/voting-by-itself.md b/docs/guides/federation/voting-by-itself.md index 0390cfd..2209389 100644 --- a/docs/guides/federation/voting-by-itself.md +++ b/docs/guides/federation/voting-by-itself.md @@ -52,10 +52,12 @@ or `POST /admin/events/vote` with `{"proposal": "8d02…", "yes": true}`. COUNT`, `--store-propose-every DURATION`): once it holds so many events beyond its checkpoint, so many versions were written since it, 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 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 + heads it holds, no more than an event may name (64, which it merges first under a + revision with merge events), 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 + (`--store-held-for`, ten minutes unless set) whose proposer has none older on the + version. It backs what it proposes, so that the nodes following its party back it too. With `--store-propose-versions 1`, it proposes one after every version: after a close vote, one key voting twice can pass a rival version at a history from before it, any time diff --git a/src/config/mod.rs b/src/config/mod.rs index 0e6e1b9..a1e6328 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 no proposal on the current version holds it back (docs/federation.md, Votes a node casts by itself); 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 it holds, no more than an event may name, 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( @@ -318,7 +318,7 @@ pub(crate) const OPTIONS: &[OptionSpec] = &[ Kind::Duration, "DURATION", 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.", + "With store-vote-key: how long it holds an event before it holds it for a while: it backs no checkpoint whose heads leave out one it held for a while before it was proposed, and a new proposal holds back its checkpoints that long.", ), #[cfg(feature = "federation")] option( diff --git a/src/federation/vote.rs b/src/federation/vote.rs index c274849..4ba2e8f 100644 --- a/src/federation/vote.rs +++ b/src/federation/vote.rs @@ -9,8 +9,8 @@ //! the revision. //! * **Proposing a checkpoint**: once so many events are held beyond its checkpoint, so //! many versions were written since, 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 no proposal on the current version holds it back: one it would back that +//! proposes a version that only moves to a checkpoint, at the heads its store holds, no +//! more than an event may name, 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. @@ -51,7 +51,8 @@ pub(crate) struct Rules { pub(crate) propose_every: Option, /// ...or once so many versions were written since the one it holds. pub(crate) propose_versions: Option, - /// How long it holds an event before it holds it for a while. + /// How long it holds an event before it holds it for a while: the voters' rule, and how + /// long a new proposal holds back a checkpoint. pub(crate) held_for: Duration, /// Voting `false` on a checkpoint proposed beside one it backs. pub(crate) nay_beside: bool, @@ -414,9 +415,10 @@ pub(crate) fn by_hand( } /// 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. +/// propose one: at the heads its store holds, at which the current version is current, +/// where no proposal on it holds it back. None where they are more than an event may name: +/// the node merges them first, under a revision with merge events (`Holding::merge`), or +/// what is written after does. fn checkpoint(seen: &Seen<'_>, rules: &Rules, current: &Version, all: &[Proposed]) -> Option { let store = seen.store; let since = current.number - store.state().checkpoint_version().number; @@ -442,23 +444,11 @@ fn checkpoint(seen: &Seen<'_>, rules: &Rules, current: &Version, all: &[Proposed 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(); - // No event is above more heads than it may name: what is written merges them. - if heads.is_empty() + // Its heads, which nothing taken builds on: the checkpoint's own, where nothing came + // after it, which a later checkpoint names not. + let mut heads = store.heads(); + heads.sort_unstable(); + if store.taken().is_empty() || heads.len() > super::event::DEPENDENCIES || store.state_at(&heads).current().hash != current.hash { @@ -848,8 +838,10 @@ mod tests { assert_eq!(version.changes, Some(next.hash())); } + /// A node proposes a checkpoint at the heads its store holds, the one it took a moment + /// ago among them; none where they are more than an event may name. #[test] - fn a_node_proposes_a_checkpoint_at_what_it_held_for_a_while() { + fn a_node_proposes_a_checkpoint_at_the_heads_it_holds() { let (tv, _, _, first, mut store) = three(); let root = store.id(); let old = taken( @@ -875,7 +867,7 @@ mod tests { panic!("not one proposal: {acts:?}"); }; let version = Version::read(json).unwrap(); - assert_eq!(version.checkpoint, Some(vec![old])); + assert_eq!(version.checkpoint, Some(vec![new])); assert!(version.only_moves_on(store.state().current())); assert_eq!(version.changes, Some(first.hash())); // Not due: none. @@ -892,6 +884,17 @@ mod tests { let acts = decide(&seen(&store, &held), &rules, &record); assert_eq!(acts.len(), 1); assert!(matches!(&acts[0], Act::Vote { yes: true, .. })); + // Heads apart, more than an event may name. + let (tv, _, _, _, mut apart) = three(); + let root = apart.id(); + for n in 0..=crate::federation::event::DEPENDENCIES { + taken( + &mut apart, + tv.write(&[root], &format!("home/tv/k{n}"), harness::str("1")), + ); + } + let record = super::tests::record(&apart, "tv"); + assert!(decide(&seen(&apart, &held), &rules, &record).is_empty()); } /// Two checkpoints proposed at once: a node backing one votes `false` on the other by -- cgit v1.3.1