diff options
| -rw-r--r-- | docs/federation.md | 72 | ||||
| -rw-r--r-- | docs/guides/federation/proposing-and-voting.md | 30 | ||||
| -rw-r--r-- | src/federation/client.rs | 30 | ||||
| -rw-r--r-- | src/federation/version.rs | 25 | ||||
| -rw-r--r-- | src/federation/vote.rs | 6 |
5 files changed, 108 insertions, 55 deletions
diff --git a/docs/federation.md b/docs/federation.md index 6438c42..ade27a9 100644 --- a/docs/federation.md +++ b/docs/federation.md @@ -241,11 +241,12 @@ application keeps party names apart from its spelling (no party named `wiki` whi `wiki.r` is lass's). A version is none if a field is missing or more (but for `checkpoint`, which it may -leave out), if it gives a party more keys than a key set may hold or more nodes than a -node list, or a rule a path longer than a write's may be, or if it breaks any of the -above. A proposal is taken whatever it holds: whether it is a version is asked where a -version event names it, so that nodes knowing more of what a version may say don't part -from those knowing less. A node can't tell a version that is none from one a later +leave out), if it names more than 96 parties (two thirds of them would be more votes than +a version event may name), if it gives a party more keys than a key set may hold or more +nodes than a node list, or a rule a path longer than a write's may be, or if it breaks +any of the above. A proposal is taken whatever it holds: whether it is a version is asked +where a version event names it, so that nodes knowing more of what a version may say don't +part from those knowing less. A node can't tell a version that is none from one a later continuum reads: at a version event writing one that passed, it stops ([Changing the federation](#changing-the-federation)). A node shows whether a proposal is a version by the federation it knows, and a party's client backs none that isn't: two @@ -438,36 +439,37 @@ later is one the node took. A version names a checkpoint by its heads (`checkpoint`): events after the current checkpoint, at which it is current too, none in another's history, their IDs ascending, -one at least. The current checkpoint at a history is the one the last 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 +one at least. One naming more than 64 is never written, as no event is above more heads +than it may name dependencies. The current checkpoint at a history is the one the last +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 diff --git a/docs/guides/federation/proposing-and-voting.md b/docs/guides/federation/proposing-and-voting.md index 2bf0dee..6793271 100644 --- a/docs/guides/federation/proposing-and-voting.md +++ b/docs/guides/federation/proposing-and-voting.md @@ -38,13 +38,13 @@ for the changes made most): Otherwise leave it out, though the current version names one: its heads are behind, and a version naming them again is never written. -Party names are 1 to 64 of `A-Z a-z 0-9 . _ @ -`; a party has up to 16 keys and 64 -nodes; a rule's path is a path as a write's is, its first segment literal and not -`_continuum`, `**` last only, `{party}` once at most, and its writer a party of the -version, `"{party}"` where the path holds it, or `false`. A version breaking any of that -is none, and a party's client backs none; where two thirds pass it all the same, nodes -stop at the version event writing it, until their operators have them drop it -([`when-things-go-wrong.md`](when-things-go-wrong.md), +Party names are 1 to 64 of `A-Z a-z 0-9 . _ @ -`; a version names up to 96 parties; a +party has up to 16 keys and 64 nodes; a rule's path is a path as a write's is, its first +segment literal and not `_continuum`, `**` last only, `{party}` once at most, and its +writer a party of the version, `"{party}"` where the path holds it, or `false`. A version +breaking any of that is none, and a party's client backs none; where two thirds pass it +all the same, nodes stop at the version event writing it, until their operators have them +drop it ([`when-things-go-wrong.md`](when-things-go-wrong.md), [A node stopped](when-things-go-wrong.md#a-node-stopped)). ## Proposing @@ -62,14 +62,14 @@ node instead. The client proposes only a version it would back: one changing the current one as a version must (its `number`, `changes`, and each `since`), whose checkpoint, where it names -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 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. +one, names no more than 64 heads and 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 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. A proposal lapses, with the votes on it, once its version isn't current any more: when another proposal on it passed. diff --git a/src/federation/client.rs b/src/federation/client.rs index c5d3651..489741a 100644 --- a/src/federation/client.rs +++ b/src/federation/client.rs @@ -362,15 +362,24 @@ impl Record { } /// The version `proposed` is, where a party may back it on `current`, and so propose it: a -/// version, changing `current` as a version must (`Version::changes_validly`), and naming -/// none of the heads of the checkpoint `current` names: a version's checkpoint is after the -/// current one's, and one naming those heads again is never written. +/// version, changing `current` as a version must (`Version::changes_validly`), naming no +/// more checkpoint heads than an event may be above, and none of the heads of the +/// checkpoint `current` names: a version's checkpoint is after the current one's, and one +/// naming those heads again is never written. pub(crate) fn backable(current: &Version, proposed: &Json) -> Result<Version, String> { let version = Version::read(proposed).map_err(|why| format!("no version: {why}"))?; version .changes_validly(Some(current)) .map_err(|why| format!("no version changing the current one: {why}"))?; let named = version.checkpoint.as_deref().unwrap_or_default(); + if named.len() > super::event::DEPENDENCIES { + return Err(format!( + "its checkpoint names {} heads: no event is above more than {}, so it is never \ + written", + named.len(), + super::event::DEPENDENCIES + )); + } if let Some(head) = current .checkpoint .iter() @@ -752,11 +761,24 @@ mod tests { } /// A party backs, and proposes, only a version changing the current one whose - /// checkpoint, where it names one, names none of the current checkpoint's heads. + /// checkpoint, where it names one, names no more heads than an event may be above, and + /// none of the current checkpoint's heads. #[test] fn a_version_backed_changes_the_current_one_and_moves_on() { let (_, _, _, first, current, one, _) = three(); assert!(backable(¤t, &one.json()).is_ok()); + let mut wide = one.clone(); + let heads: Vec<Id> = (0..=super::super::event::DEPENDENCIES) + .map(|n| Id::of(format!("head {n}").as_bytes())) + .collect(); + wide.checkpoint = Some(heads[1..].to_vec()); + assert!(backable(¤t, &wide.json()).is_ok()); + wide.checkpoint = Some(heads); + assert!( + backable(¤t, &wide.json()) + .unwrap_err() + .contains("65 heads") + ); let mut far = one.clone(); far.number += 1; assert!(backable(¤t, &far.json()).is_err()); diff --git a/src/federation/version.rs b/src/federation/version.rs index d714a47..378e122 100644 --- a/src/federation/version.rs +++ b/src/federation/version.rs @@ -16,6 +16,11 @@ pub(crate) const KEYS: usize = 16; /// Nodes a node list may name. pub(crate) const NODES: usize = 64; +/// Parties a version may name: a version event names the votes passing a proposal, two +/// thirds of its version's parties, and an event names no more than 64 events +/// (`event::DEPENDENCIES`). +pub(crate) const PARTIES: usize = 96; + /// Segments a path may have, and bytes a segment. pub(crate) const SEGMENTS: usize = 32; pub(crate) const SEGMENT_BYTES: usize = 255; @@ -210,6 +215,12 @@ impl Version { if keys.names().is_empty() { return Err("no party".to_owned()); } + if keys.names().len() > PARTIES { + return Err(format!( + "{} parties, more than {PARTIES}", + keys.names().len() + )); + } let mut parties = BTreeMap::new(); let mut every_key = BTreeSet::new(); for name in keys.names() { @@ -534,6 +545,20 @@ mod tests { ); } + /// A version names no more parties than a version event may name the votes of two + /// thirds of. + #[test] + fn a_version_names_at_most_96_parties() { + use super::super::harness::{Party, Spec}; + let parties: Vec<Party> = (1..=PARTIES as u8 + 1) + .map(|n| Party::new(&format!("p{n}"), n)) + .collect(); + let named: Vec<&Party> = parties.iter().collect(); + assert!(Version::read(&Spec::first(&named[1..], &[]).json()).is_ok()); + let why = Version::read(&Spec::first(&named, &[]).json()).unwrap_err(); + assert_eq!(why, "97 parties, more than 96"); + } + #[test] fn a_version_changes_another_by_its_number_hash_and_sinces() { let first = Version::read(&first()).expect("a version"); diff --git a/src/federation/vote.rs b/src/federation/vote.rs index 1b4de16..693339e 100644 --- a/src/federation/vote.rs +++ b/src/federation/vote.rs @@ -397,7 +397,11 @@ fn checkpoint(seen: &Seen<'_>, rules: &Rules, current: &Version, all: &[Proposed .flatten() .collect(); let heads: Vec<Id> = held.difference(&built_on).copied().collect(); - if heads.is_empty() || store.state_at(&heads).current().hash != current.hash { + // No event is above more heads than it may name: what is written merges them. + if heads.is_empty() + || heads.len() > super::event::DEPENDENCIES + || store.state_at(&heads).current().hash != current.hash + { return None; } let Json::Object(mut members) = current |
