diff options
| author | tv <tv@krebsco.de> | 2026-11-19 14:42:45 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-19 15:53:14 +0100 |
| commit | 33be6b959c9777c40ca2b16507e9f4f60d6d2d44 (patch) | |
| tree | 9939a86e950edeeac619798f46a6c42c3bc9388b | |
| parent | a67c96469d2d06e85c4be69a725af7b93fb023a2 (diff) | |
vote: a second `true` builds on the nays that freed its party
The federation takes a party's `true` only where, at its history, every
other proposal it backed on that version is dead. A party's client, and
a node voting by itself, built a vote on the events proposing what it
votes on alone. A proposal made while the party's first `true` was
alive, at a history holding it, holds that `true` in its history, and
not the nays that ended the first proposal later: the party's `true` on
it was refused, though its record cast it. The compromise case: five
back X, Y is proposed, X dies, its backers back Y.
A vote now builds on one event proposing what it votes on, and on the
nays that freed its party (`client::building`), so the first proposal is
dead at its history too. One event proposing it is enough, so many
proposing it again don't push a vote past the dependencies an event may
name. A checkpoint's vote builds on its proposal alone: one of those
nays in the history of its heads, named, would put the vote beside them.
A party freed only after the heads were named backs that checkpoint not,
and its client says so before casting; it backs one proposed after.
Row 74 is tested (`federation_attack_74`); federation.md and the guides
say so.
| -rw-r--r-- | docs/federation.md | 16 | ||||
| -rw-r--r-- | docs/guides/federation/proposing-and-voting.md | 8 | ||||
| -rw-r--r-- | docs/guides/federation/voting-by-itself.md | 6 | ||||
| -rw-r--r-- | src/federation/client.rs | 69 | ||||
| -rw-r--r-- | src/federation/held.rs | 29 | ||||
| -rw-r--r-- | src/federation/party.rs | 20 |
6 files changed, 128 insertions, 20 deletions
diff --git a/docs/federation.md b/docs/federation.md index 2cdd4d9..23522e6 100644 --- a/docs/federation.md +++ b/docs/federation.md @@ -296,7 +296,10 @@ A party **votes** on a proposal by a `vote` event, naming the version the propos votes never takes back a pass or a death. * **One yes at a time.** A party's `true` is taken only if, at its history, every other proposal on that version it voted `true` for is dead. So a party backs one proposal, - and is free again when that one can't pass any more. + and is free again when that one can't pass any more. Its next `true` builds on the + nays that freed it, as its first may be in the history of the proposal it backs next, + proposed while the first was alive, and they not; but for a checkpoint + ([Checkpoints](#checkpoints)). So a yes binds its party while its proposal can pass. Of nine parties, five back X, two prefer Y and two never vote: X needs one more and can't die, as that takes four nays. @@ -479,11 +482,15 @@ more is judged. It is a version only where its proposal is above those heads, an 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 +vote on an event proposing what they vote on that is 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 +until the move refuses it. Nor does a vote on a checkpoint build on the nays that freed +its party: named, one in the history of its heads would put the vote beside them. So a +party freed only after the heads were named, its `true` it was freed from in their +history, backs that checkpoint not, as nodes refuse its `true`, and its client says so; +it backs one proposed after. 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 @@ -801,10 +808,11 @@ fold, with crafted events. *Sim*: a simulation. *Bench*: measured, not judged. | 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 | +| 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 an event proposing it above its heads, as a node shows them; a version event on votes beside them is refused | unit | | 71 | Merge events under the base revision, signed by a node its party doesn't list, by a party's key, or spelled otherwise | Refused, or none: a merge event is taken only under a revision with merge events, signed by a node its party's node list names, its `merge` `true`; it counts for nothing | unit | | 72 | A version, or a fork's, admitting a party named as a segment of places others write, or changing the rules or their order, so that who writes those places moves, rules unchanged in the first case | Taken, as any version two thirds pass, or any fork: a party's client names each place holding a value whose writer a proposal changes before it is voted on, and a fork's check does for the fork's version | unit | | 73 | A party writes a great many places, so that every node holds them, and every checkpoint, snapshot and fork's root names them | Taken where its rules let it write: nothing bounds what a party writes but the rules' places and an event's size; the others take it out by a version, or fork | — | +| 74 | A party's second `true`, on a proposal made at a history holding its first, which nays ended later | Taken: a vote builds on the nays that freed its party, as well as on its proposal, so that the first is dead at its history; on a checkpoint only where those nays are in the history of its heads, and else the party backs the next | unit | ## Roads not taken diff --git a/docs/guides/federation/proposing-and-voting.md b/docs/guides/federation/proposing-and-voting.md index 9b50e09..e91806c 100644 --- a/docs/guides/federation/proposing-and-voting.md +++ b/docs/guides/federation/proposing-and-voting.md @@ -93,8 +93,12 @@ record before it sends the vote. It casts no vote that would make its party vote * `true` only for a version changing the current one, whose checkpoint names none of the current checkpoint's heads; * one `true` at a time: another `true` on the same version only once the proposal the - party backed is dead. The client fetches the votes that made it so from the node, and - keeps them in the record beside the new `true`. + party backed is dead. The client fetches the votes that made it so from the node, keeps + them in the record beside the new `true`, and builds the `true` on them, so that the + first is dead at its history too: the proposal it backs next may have been proposed at + a history holding its first `true`. A checkpoint's `true` it builds on the proposal + alone, and says when it may be refused so: where the nays came after the heads the + checkpoint names, back the one proposed after. A `true` holds the party until its proposal passes or is dead, and only other parties' nays make it dead. Where ending it would take every party yet to vote, or more, and those diff --git a/docs/guides/federation/voting-by-itself.md b/docs/guides/federation/voting-by-itself.md index 73e9df8..ebde0cf 100644 --- a/docs/guides/federation/voting-by-itself.md +++ b/docs/guides/federation/voting-by-itself.md @@ -79,9 +79,9 @@ 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, of a checkpoint those above -its heads, and its checkpoint proposals on its heads, so that a version event may be -written on them. +It signs its votes on an event proposing what it votes on, of a checkpoint one above its +heads, and on the nays that freed its party, but for a checkpoint; and its checkpoint +proposals on its heads, so that a version event may be written on them. ## Watching it diff --git a/src/federation/client.rs b/src/federation/client.rs index f0c196f..57e20e1 100644 --- a/src/federation/client.rs +++ b/src/federation/client.rs @@ -395,6 +395,37 @@ pub(crate) fn backable(current: &Version, proposed: &Json) -> Result<Version, St Ok(version) } +/// What a vote on a proposal builds on: `proposing`, an event proposing it (of a +/// checkpoint, one above the heads it names, so that a version event may be written on +/// the vote); and, but for a checkpoint (`checkpoint`), the nays that freed its party +/// (`nays`, as `Record::may_vote` keeps them), so that the proposal its party backed +/// before is dead at the vote's history, as the federation takes a second `true` only so: +/// that `true` may be in the history of the event proposing this one, and the nays not. A +/// checkpoint's vote leaves them out: one in the history of its heads, named, would put +/// the vote beside them, and one cast after they were named is beside them or above, which +/// only a node can tell. None where they are more than an event may name. +pub(crate) fn building( + proposing: Id, + checkpoint: bool, + nays: &[Vec<u8>], +) -> Result<Vec<Id>, String> { + let mut on = vec![proposing]; + if !checkpoint { + on.extend(nays.iter().map(|nay| Id::of(nay))); + on.sort_unstable(); + on.dedup(); + } + if on.len() > super::event::DEPENDENCIES { + return Err(format!( + "the proposal and the nays that freed the party are {} events, more than a vote \ + may build on ({})", + on.len(), + super::event::DEPENDENCIES + )); + } + Ok(on) +} + /// Where a `true` of `party` on a proposal on `current`, on which the parties of `yes` and /// `no` voted so far, binds it until the proposal passes unless every party yet to vote, or /// more, votes `false`, those being a third of the parties or fewer: a `true` holds its @@ -971,6 +1002,44 @@ mod tests { ); } + /// Row 74 (`docs/federation.md`): a party backs X, and Y is proposed at a history + /// holding that `true`; X dies after. Its `true` on Y built on Y's proposal alone is + /// refused, X being alive at its history; built as a vote builds (`building`), on the + /// nays that freed it too, it is taken. + #[test] + fn federation_attack_74() { + use crate::federation::fold::Federation; + use crate::federation::store::memory::{Offered, Store}; + let (tv, lass, makefu, first, _, one, two) = three(); + let mut store = Store::<Federation>::new(first.root(), Vec::new()).unwrap(); + let (root, on) = (store.id(), first.hash()); + let mut take = |bytes: Vec<u8>| -> Id { + let id = Id::of(&bytes); + assert!(matches!(store.offer(bytes), Offered::Taken(_)), "not taken"); + id + }; + let x = take(tv.propose(&[root], &one.json())); + let backed = take(tv.vote(&[x], on, one.hash(), true)); + let y = take(lass.propose(&[backed], &two.json())); + let nays = [ + lass.vote(&[x], on, one.hash(), false), + makefu.vote(&[x], on, one.hash(), false), + ]; + for nay in &nays { + take(nay.clone()); + } + let alone = tv.vote(&[y], on, two.hash(), true); + assert!(matches!(store.offer(alone), Offered::Refused(_))); + let on_them = building(y, false, &nays).unwrap(); + assert_eq!(on_them.len(), 3); + let freed = tv.vote(&on_them, on, two.hash(), true); + assert!(matches!(store.offer(freed), Offered::Taken(_))); + // A checkpoint's vote builds on its proposal alone. + assert_eq!(building(y, true, &nays).unwrap(), [y]); + let many: Vec<Vec<u8>> = (0..64u8).map(|n| vec![n]).collect(); + assert!(building(y, false, &many).is_err()); + } + /// Row 72 (`docs/federation.md`): a party admitted under the name of a place's segment /// moves who writes there, rules unchanged, and so does a change of the rules' order; /// the places it moves are named, the others left out. diff --git a/src/federation/held.rs b/src/federation/held.rs index 6e00e51..9c87995 100644 --- a/src/federation/held.rs +++ b/src/federation/held.rs @@ -29,7 +29,7 @@ use anyhow::{Context, Result, bail}; use serde::{Deserialize, Serialize}; use tracing::{error, info, warn}; -use super::client::Record; +use super::client::{self, Record}; use super::event::{self, Does, Event, Signed}; use super::fold::Federation; use super::revision::Feature; @@ -740,11 +740,14 @@ impl Holding { yes, nays, } => { - // 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() { + // On an event proposing it, of a checkpoint one above the heads it + // names, so a version event may be written on it, which the node's + // heads, holding what is beside them, may not be; and on the nays that + // freed its party (`client::building`). + let state = store.state(); + let Some(proposing) = + state.proposing(¤t.hash, &proposal).first().copied() + else { if hand.is_some() { return Err(format!( "no event proposing {proposal} is above the heads it names: \ @@ -752,12 +755,22 @@ impl Holding { )); } continue; - } + }; + let checkpoint = state + .proposal(&proposal) + .and_then(|json| Version::read(json).ok()) + .and_then(|version| version.checkpoint) + .is_some(); + let on = match client::building(proposing, checkpoint, &nays) { + Ok(on) => on, + Err(why) if hand.is_some() => return Err(why), + Err(_) => continue, + }; let cast = event::signed( &voter.key, party, &line, - &proposing, + &on, event::vote(current.hash, proposal, yes), ); record.cast(¤t, &cast, nays); diff --git a/src/federation/party.rs b/src/federation/party.rs index f64746b..a544155 100644 --- a/src/federation/party.rs +++ b/src/federation/party.rs @@ -836,9 +836,23 @@ async fn vote( eprintln!("Warning: {why}"); } } - // 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))?; + // On an event proposing it the node shows, of a checkpoint one above the heads it + // names, and on the nays that freed the party (`client::building`). + let checkpoint = Version::read(&proposed) + .ok() + .and_then(|version| version.checkpoint) + .is_some(); + if checkpoint && yes && !kept.is_empty() { + eprintln!( + "Warning: this `true` builds on {proposing} alone, not on the nays that freed \ + {party}: where they came after the heads it names, and {party}'s `true` they \ + ended is in the history of {proposing}, nodes refuse it; a checkpoint proposed \ + after them takes {party}'s `true`", + party = signer.party + ); + } + let on = client::building(proposing, checkpoint, &kept).map_err(|why| anyhow!(why))?; + let cast = signer.sign(&on, event::vote(current.hash, proposal, yes))?; record.cast(¤t, &cast, kept); record.save(path).map_err(|why| anyhow!(why))?; node.put(&cast).await |
