aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-19 01:48:57 +0000
committertv <tv@krebsco.de>2026-11-19 03:19:12 +0100
commite0075264e9efdd4c8a32290c0d5643e7f48bfb14 (patch)
tree646f0ab7fb2dd61e93bc1b8cce6f6a13a5ff0b8b
parent31d41eb1c902c907a5c6e5608510f96c4b1bc864 (diff)
federation: a checkpoint of 64 heads at most, a version of 96 parties
No event is above more heads than it may name dependencies (64): a version naming more for its checkpoint is never written. A node voting by itself proposed one at whatever heads it held for a while, however many; it now proposes none past 64, as what is written merges them, and a party's client backs none such (`client::backable`). A version event names the votes passing a proposal, two thirds of its version's parties: past 96 parties, more than an event may name. A version names at most 96 now (`version::PARTIES`).
-rw-r--r--docs/federation.md72
-rw-r--r--docs/guides/federation/proposing-and-voting.md30
-rw-r--r--src/federation/client.rs30
-rw-r--r--src/federation/version.rs25
-rw-r--r--src/federation/vote.rs6
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(&current, &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(&current, &wide.json()).is_ok());
+ wide.checkpoint = Some(heads);
+ assert!(
+ backable(&current, &wide.json())
+ .unwrap_err()
+ .contains("65 heads")
+ );
let mut far = one.clone();
far.number += 1;
assert!(backable(&current, &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