diff options
| author | tv <tv@krebsco.de> | 2026-11-19 01:48:57 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-19 03:18:49 +0100 |
| commit | 03744437a5ffc36fbb5e973a0ddfd6b91945b212 (patch) | |
| tree | 227eb42b4e7cac546b857cfacb79ab890e8bb137 | |
| parent | f24063e90d02ef76d87401d6e74cf8c9f489ff7d (diff) | |
federation: votes on the events proposing a checkpoint above its heads
Anyone could propose a checkpoint's version again, by an event beside its heads. A node
voting by itself, and a party's client, built a vote on every event proposing what it
voted on, so every vote was beside the heads, and no version event written on them was
taken: the checkpoint could never move the store. And the voters' rule refused it once
that event was held for a while, as the heads left it out.
They vote on the events proposing it that are above the heads it names
(`State::proposing`), which `GET /events/counts` lists as `proposals`; where there are
none, `none` says so, the node casts nothing and the client says why. The voters' rule
leaves proposals and votes aside, as they lapse with the move.
Row 70 is tested (`federation_attack_70`).
| -rw-r--r-- | docs/federation.md | 51 | ||||
| -rw-r--r-- | docs/guides/federation/checkpoints.md | 12 | ||||
| -rw-r--r-- | docs/guides/federation/proposing-and-voting.md | 3 | ||||
| -rw-r--r-- | docs/guides/federation/voting-by-itself.md | 10 | ||||
| -rw-r--r-- | docs/openapi.yaml | 8 | ||||
| -rw-r--r-- | src/api/events.rs | 15 | ||||
| -rw-r--r-- | src/federation/fold.rs | 27 | ||||
| -rw-r--r-- | src/federation/held.rs | 112 | ||||
| -rw-r--r-- | src/federation/party.rs | 10 | ||||
| -rw-r--r-- | src/federation/vote.rs | 14 |
10 files changed, 205 insertions, 57 deletions
diff --git a/docs/federation.md b/docs/federation.md index 669527d..6438c42 100644 --- a/docs/federation.md +++ b/docs/federation.md @@ -446,30 +446,32 @@ starting from a checkpoint holds what judging them reads. A proposer names heads 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: 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, and a node proposes a checkpoint on its heads: so their votes -are above those heads wherever the proposal is. 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. +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 @@ -730,6 +732,7 @@ fold, with crafted events. *Sim*: a simulation. *Bench*: measured, not judged. | 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 | | 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 | ## Roads not taken diff --git a/docs/guides/federation/checkpoints.md b/docs/guides/federation/checkpoints.md index 66f79e9..69debaf 100644 --- a/docs/guides/federation/checkpoints.md +++ b/docs/guides/federation/checkpoints.md @@ -43,12 +43,12 @@ is proposed; and it backs what it proposes. ## Backing one Back a checkpoint only where everything you held for a while before it was proposed is -among its heads, in their history, or above them: 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 voting by itself backs one only so, and so does a vote by hand through it -(`continuum-party vote … --through`). A party's client voting on its own -(`continuum-party vote`) checks no heads: check them yourself, or vote through such a -node. +among its heads, in their history, or above them, proposals and votes aside, which lapse +with the move: 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 voting by itself backs one +only so, and so does a vote by hand through it (`continuum-party vote … --through`). A +party's client voting on its own (`continuum-party vote`) checks no heads: check them +yourself, or vote through such a node. * `--store-follow PARTY,…` has a node voting by itself follow those parties' votes, by default on versions that only move to a checkpoint, and still by that rule. diff --git a/docs/guides/federation/proposing-and-voting.md b/docs/guides/federation/proposing-and-voting.md index 0f303ea..2bf0dee 100644 --- a/docs/guides/federation/proposing-and-voting.md +++ b/docs/guides/federation/proposing-and-voting.md @@ -65,7 +65,8 @@ version must (its `number`, `changes`, and each `since`), whose checkpoint, wher one, names none of the heads of the current version's checkpoint, as such a version is never written. It says why it doesn't propose one otherwise. The proposal is on the current version, and its hash is the version's: the node shows it under that -hash (`proposals` in `GET /events/counts`), with the events proposing it. +hash (`proposals` in `GET /events/counts`), with the events proposing it that a vote +may build on: of a checkpoint, those above its heads. Several parties proposing the same version make one proposal. The key a party proposes and votes with is one the current version names for it, not one of its key set: the client checks that before it signs, and records nothing otherwise. diff --git a/docs/guides/federation/voting-by-itself.md b/docs/guides/federation/voting-by-itself.md index 300f60c..b88947a 100644 --- a/docs/guides/federation/voting-by-itself.md +++ b/docs/guides/federation/voting-by-itself.md @@ -61,11 +61,13 @@ no version ([`proposing-and-voting.md`](proposing-and-voting.md), [Voting](proposing-and-voting.md#voting)). And, for a version naming a checkpoint, the voters' rule: it backs one only where it changes nothing of the current version but its number, what it changes and its checkpoint, and its heads leave out nothing it held for a -while before it was proposed ([`checkpoints.md`](checkpoints.md), -[Backing one](checkpoints.md#backing-one)). A vote by hand through it keeps to the same. +while before it was proposed, proposals and votes aside +([`checkpoints.md`](checkpoints.md), [Backing one](checkpoints.md#backing-one)). A vote +by hand through it keeps to the same. -It signs its votes on the events proposing what it votes on, and its checkpoint -proposals on its heads, so that a version event may be written on them. +It signs its votes on the events proposing what it votes on, of a checkpoint those above +its heads, and its checkpoint proposals on its heads, so that a version event may be +written on them. ## Watching it diff --git a/docs/openapi.yaml b/docs/openapi.yaml index 57ef132..349f943 100644 --- a/docs/openapi.yaml +++ b/docs/openapi.yaml @@ -1529,13 +1529,15 @@ paths: What counts, as the store reads now (docs/federation.md): the current version (its number, its hash, and the version itself), each party's keys and nodes, the value at each place, the members, each `[node, party]`, and the proposals on the - current version, by their hash, each with the IDs of the events proposing it - (`proposals`) and of the votes on it (`votes`), the parties voting `true` (`yes`) + current version, by their hash, each with the IDs of the events proposing it that + a vote may build on (`proposals`: of a version naming a checkpoint, those above + its heads) and of the votes on it (`votes`), the parties voting `true` (`yes`) and `false` (`no`), whether it passed (`passed`: two thirds of the parties voted `true`) and whether it is dead (`dead`: so many voted `false` that the rest can't pass it), and why a party's client backs it not (`none`), where it is no version, none changing the current one, or one naming the heads of the current one's - checkpoint, as this node reads it: one that passed all the same is never written, + checkpoint, as this node reads it, or no event proposing it is above the heads it + names: one that passed all the same is never written, or, no version here, this node stops at its version event. A passed proposal is written at once, and lapses with the rest. responses: diff --git a/src/api/events.rs b/src/api/events.rs index 496a077..214882a 100644 --- a/src/api/events.rs +++ b/src/api/events.rs @@ -124,7 +124,8 @@ async fn event(State(state): State<AppState>, Path(id): Path<String>) -> Respons /// `GET /events/counts`: what counts, as the store reads now: the current version, each /// party's keys and nodes, the values at places, the members, and the proposals on the -/// current version, each with the events proposing it, the votes on it, the parties +/// current version, each with the events proposing it a vote may build on (`proposing`: +/// for a checkpoint, those above its heads), the votes on it, the parties /// voting `true` and `false`, whether it passed and whether it is dead, and why a party's /// client backs it not, where it is no version that can be written on the current one /// (`client::backable`). @@ -155,13 +156,21 @@ async fn counts(State(state): State<AppState>) -> Response { .into_iter() .map(|(hash, ballot)| { let tally = read.tally(current, &hash); + let proposing = read.proposing(¤t.hash, &hash); let none = read .proposal(&hash) - .and_then(|proposed| client::backable(current, proposed).err()); + .and_then(|proposed| client::backable(current, proposed).err()) + .or_else(|| { + (proposing.is_empty() && !ballot.proposals.is_empty()).then(|| { + "no event proposing it is above the heads it names: no version \ + event is written on a vote on it" + .to_owned() + }) + }); ( hash.to_string(), json!({ - "proposals": ids(ballot.proposals), + "proposals": ids(proposing), "votes": ids(ballot.votes), "yes": tally.yes, "no": tally.no, diff --git a/src/federation/fold.rs b/src/federation/fold.rs index 2e3fc56..7986a13 100644 --- a/src/federation/fold.rs +++ b/src/federation/fold.rs @@ -354,6 +354,33 @@ impl State { self.proposed.get(proposal) } + /// Of the events proposing the proposal of hash `proposal` on `on`, those a vote on it + /// may build on: where its version names a checkpoint, those above its heads, so that + /// a version event written on the votes is above them too. One proposing it again, + /// beside them, a vote doesn't build on. + pub(crate) fn proposing(&self, on: &Id, proposal: &Id) -> Vec<Id> { + let proposals = self + .ballots(on) + .remove(proposal) + .map(|ballot| ballot.proposals) + .unwrap_or_default(); + let heads = self + .proposed + .get(proposal) + .and_then(|json| Version::read(json).ok()) + .and_then(|version| version.checkpoint); + match heads { + None => proposals, + Some(heads) => { + let above = self.above(&heads.into_iter().collect()); + proposals + .into_iter() + .filter(|id| above.contains(id)) + .collect() + } + } + } + /// The version event writing the proposal of hash `proposal` on the current version, /// where it passed here: on the `true` votes of the first parties by name that pass it, /// each party's of the lowest ID, so that nodes holding those votes write the same. diff --git a/src/federation/held.rs b/src/federation/held.rs index 66f20e9..93e2505 100644 --- a/src/federation/held.rs +++ b/src/federation/held.rs @@ -728,7 +728,6 @@ impl Holding { return Ok(Vec::new()); } let current = store.state().current().clone(); - let ballots = store.state().ballots(¤t.hash); let heads = store.heads(); let line = crate::access::sshsig::PublicKey(voter.key.verifying_key().to_bytes()).line(); let mut record = record.clone(); @@ -740,21 +739,24 @@ impl Holding { yes, nays, } => { - // On the events proposing it: above the heads it names for a - // checkpoint wherever they are, so a version event may be written on - // it, which the node's heads, holding what is beside them, may not be. - let proposing = ballots - .get(&proposal) - .map_or_else(Vec::new, |ballot| ballot.proposals.clone()); + // On the events proposing it, those above the heads it names for a + // checkpoint, so a version event may be written on it, which the + // node's heads, holding what is beside them, may not be. + let proposing = store.state().proposing(¤t.hash, &proposal); + if proposing.is_empty() { + if hand.is_some() { + return Err(format!( + "no event proposing {proposal} is above the heads it names: \ + no version event is written on a vote on it" + )); + } + continue; + } let cast = event::signed( &voter.key, party, &line, - if proposing.is_empty() { - &heads - } else { - &proposing - }, + &proposing, event::vote(current.hash, proposal, yes), ); record.cast(¤t, &cast, nays); @@ -1949,6 +1951,92 @@ mod tests { assert!(holding.vote_by_hand(next.hash(), true).is_ok()); } + /// Row 70 (`docs/federation.md`): a checkpoint's version proposed again, by an event + /// beside its heads. A node backs it all the same, as a proposal lapses with the move, + /// and votes on the event proposing it above the heads alone: a version event written + /// on such votes moves it; one on votes built on both events is beside the heads, and + /// refused. + #[test] + fn federation_attack_70() { + 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 = first.root(); + let on = first.hash(); + let head = tv.write(&[Id::of(&root)], "home/tv/a", harness::str("1")); + let mut next = first.after(on); + next.checkpoint = Some(vec![Id::of(&head)]); + let above = tv.propose(&[Id::of(&head)], &next.json()); + let beside = lass.propose(&[Id::of(&root)], &next.json()); + let mut doc = events::started(Federation::NAME, &root, &[]).unwrap(); + for event in [&head, &above, &beside] { + put(&mut doc, event); + } + let dir = crate::files::scratch_dir("held-attack-70"); + let record = dir.join("makefu.json"); + let version = Version::read(&first.json()).unwrap(); + let mut begun = Record::begin(Id::of(&root), "makefu", &version); + begun.began = Id::of(b"before the federation").to_string(); + begun.save(&record).unwrap(); + let holding = Holding::open( + None, + Arc::new(Files::default()), + None, + Some("makefu".into()), + ) + .unwrap() + .voting(Some(Voter { + key: makefu.key.clone(), + record, + // Everything held for a while: the proposal beside the heads too. + rules: Rules::default(), + })); + read(&holding, &doc, 0); + assert_eq!( + holding.with(|store| store.state().proposing(&on, &next.hash())), + Some(vec![Id::of(&above)]) + ); + let cast = holding.vote_by_hand(next.hash(), true).unwrap(); + assert!(matches!( + Event::read_taken(&cast), + Some(Event::Signed(Signed { deps, .. })) if deps == vec![Id::of(&above)] + )); + let both = [Id::of(&above), Id::of(&beside)]; + let beside_votes = [&tv, &lass].map(|party| party.vote(&both, on, next.hash(), true)); + for vote in &beside_votes { + assert!(matches!( + holding.offer(vote.clone()), + Some(Offered::Taken(_)) + )); + } + let refused = harness::version_event( + &[Id::of(&beside_votes[0]), Id::of(&beside_votes[1])], + next.hash(), + ); + assert!(matches!( + holding.offer(refused), + Some(Offered::Refused(Refusal::Judged(_))) + )); + let tv_yes = tv.vote(&[Id::of(&above)], on, next.hash(), true); + assert!(matches!( + holding.offer(tv_yes.clone()), + Some(Offered::Taken(_)) + )); + let written = harness::version_event(&[Id::of(&cast), Id::of(&tv_yes)], next.hash()); + assert!(matches!(holding.offer(written), Some(Offered::Taken(_)))); + assert_eq!( + holding.with(|store| store.state().current().hash), + Some(next.hash()) + ); + assert_ne!( + holding.with(|store| Id::of(store.checkpoint())), + Some(Id::of(&root)) + ); + } + // The store's attack rows (`docs/store.md`, Attacks) read from a document. /// tv's federation, its root, and a document started from it. diff --git a/src/federation/party.rs b/src/federation/party.rs index 04837c3..162f8bd 100644 --- a/src/federation/party.rs +++ b/src/federation/party.rs @@ -696,6 +696,9 @@ async fn vote( }; let proposals = ids(&proposal, "proposals"); let Some(proposing) = proposals.first().copied() else { + if let Some(why) = ballots[proposal.to_string()]["none"].as_str() { + bail!("{proposal}: {why}"); + } bail!("no proposal of hash {proposal} on the current version, as the node reads it"); }; let proposed = match Event::read(&node.event(&proposing).await?) { @@ -731,8 +734,8 @@ async fn vote( let kept = record .may_vote(¤t, proposal, &proposed, yes, &nays) .map_err(|why| anyhow!(why))?; - // On the events proposing it: above the heads it names for a checkpoint wherever they - // are, so a version event may be written on it. + // On the events proposing it the node shows, those above the heads it names for a + // checkpoint, so a version event may be written on it. let cast = signer.sign(&proposals, event::vote(current.hash, proposal, yes))?; record.cast(¤t, &cast, kept); record.save(path).map_err(|why| anyhow!(why))?; @@ -799,6 +802,9 @@ async fn proposals(node: &Node) -> Result<()> { parties(&proposal["no"]) ); let Some(id) = proposal["proposals"][0].as_str() else { + if let Some(why) = proposal["none"].as_str() { + println!(" backed by no client: {why}"); + } continue; }; let id = Id::from_hex(id).ok_or_else(|| anyhow!("the node names no event ID: {id}"))?; diff --git a/src/federation/vote.rs b/src/federation/vote.rs index d4968be..1b4de16 100644 --- a/src/federation/vote.rs +++ b/src/federation/vote.rs @@ -144,7 +144,7 @@ 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. +/// before it was proposed, proposals and votes aside, which lapse with the move. pub(crate) fn backs_checkpoint( seen: &Seen<'_>, rules: &Rules, @@ -161,11 +161,21 @@ pub(crate) fn backs_checkpoint( ); } 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| { + matches!( + seen.store.get(id).and_then(Event::read_taken), + Some(Event::Signed(Signed { + does: Does::Proposal { .. } | Does::Vote { .. }, + .. + })) + ) + }; let held: Vec<Id> = seen .store .taken() .iter() - .filter(|id| (seen.held)(id).is_some_and(|held| held >= before)) + .filter(|id| (seen.held)(id).is_some_and(|held| held >= before) && !lapsing(id)) .copied() .collect(); let left_out = seen.store.left_out(heads, &held); |
