From c9c7807bf0f068474ce5c853244bcb392bdfcce3 Mon Sep 17 00:00:00 2001 From: tv Date: Sun, 8 Nov 2026 19:16:10 +0000 Subject: roots: an epoch's root pinned, and named in every handshake Review 2, N7, the care it raised: a joining node's empty document took as the first epoch's root whatever dependency-less change came first, from whichever peer it joined through; the first epoch's ID is all zeros, so nothing pinned it. A remake's epoch has its ID, the snapshot change's hash, which the rules hold its root to. * Every node names its epoch's root in HELLO and HELLO_REPLY (the epoch's ID for a remake's, its genesis change for the first; wire version 45). A node whose document starts from another root of the same epoch refuses the handshake, logging it: another history under the swarm's ID, a forged root or a genesis started again. * A joining node with an empty document takes as its root only the one it was given (--genesis-root, new), else the one its peers name, and none while they name different ones (access::screen::RootPin, kept in Screening across documents): one peer hands it another root only if it is all the joiner hears, or never, with --genesis-root. A root refused is listed with the refused, what builds on it with it. * The genesis node logs the root (`The swarm's root`); GET /admin/epochs shows it (`root`). A genesis started again under a remembered swarm ID used to merge with the nodes of it still running; they now refuse it (another root), and the docs say to join them with seeds instead. The epoch's identity stays as it is (generation 0 all zeros): records and epoch metadata name it so, and every comparison of epochs with them. --- src/swarm/roots.rs | 171 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 171 insertions(+) create mode 100644 src/swarm/roots.rs (limited to 'src/swarm/roots.rs') diff --git a/src/swarm/roots.rs b/src/swarm/roots.rs new file mode 100644 index 0000000..5089418 --- /dev/null +++ b/src/swarm/roots.rs @@ -0,0 +1,171 @@ +//! An epoch's root, pinned: the change without dependencies a document of that epoch +//! starts from. For a remake's epoch it is the epoch's ID (its snapshot change's hash), +//! which the rules hold every root to; for the first epoch, whose ID is all zeros, the +//! genesis change, which a node joining with an empty document would take from whoever +//! sent it first. So every node names its epoch's root in its handshakes +//! (`HelloRequest::root`, `HelloReply::root`), and: +//! +//! * a node whose document holds another root of the same epoch refuses the handshake: +//! another history under this swarm's ID (a forged root, or a genesis started again); +//! * a joining node takes as its root only the one given (`--genesis-root`), or else the +//! one its peers name, and none while they name different ones (`RootPin`), so one +//! peer can't hand it another root unless it is all the joiner hears. + +use std::collections::{HashMap, HashSet}; + +use anyhow::{Result, bail}; +use tracing::{error, info, warn}; + +use crate::access::screen::RootPin; +use crate::document::replica::Epoch; +use crate::document::{ChangeHash, Document}; +use crate::locks::MutexExt; +use crate::state::AppState; + +/// What the node heard of its epoch's root, and knows of its own. +#[derive(Debug, Default)] +pub(crate) struct Roots { + /// Of the first epoch, as each peer named it. + named: HashMap, + /// Its own, for the document (`Replica::epoch_seq`), once known. + own: Option<(u32, ChangeHash)>, + /// Peers whose root differs, logged once each. + differing: HashSet, +} + +/// A change hash in hex (`--genesis-root`). +pub(crate) fn parse(hex: &str) -> Option { + let hex = hex.trim(); + if hex.len() != 64 { + return None; + } + let mut bytes = [0u8; 32]; + for (index, byte) in bytes.iter_mut().enumerate() { + *byte = u8::from_str_radix(hex.get(index * 2..index * 2 + 2)?, 16).ok()?; + } + Some(ChangeHash(bytes)) +} + +/// `doc`'s root, of `epoch`: the epoch's ID for a remake's, the change without +/// dependencies of the first epoch's; None for an empty document. +pub(crate) fn of(doc: &Document, epoch: Epoch) -> Option { + if epoch.generation > 0 { + return Some(ChangeHash(epoch.id)); + } + if doc.get_heads().is_empty() { + return None; + } + doc.get_changes(&[]) + .iter() + .find(|change| change.deps().is_empty()) + .map(|change| change.hash()) +} + +/// This node's epoch's root, if its document holds one; found once per document. +pub(crate) async fn own(state: &AppState) -> Option { + let (epoch, epoch_seq) = state.epoch_stamp(); + if epoch.generation > 0 { + return Some(ChangeHash(epoch.id)); + } + if let Some((seq, root)) = state.roots.lock_or_recover().own + && seq == epoch_seq + { + return Some(root); + } + let replica = state.doc.read().await; + let root = of(&replica.doc, replica.epoch)?; + state.roots.lock_or_recover().own = Some((replica.epoch_seq, root)); + Some(root) +} + +/// `peer`, in a handshake of `epoch`, names `root` as its root. Refused (an error) if +/// this node's document holds another of the same epoch; of the first epoch, what an +/// empty document takes as its root follows (`pin`). +pub(crate) async fn heard( + state: &AppState, + peer: &str, + epoch: Epoch, + root: Option<&[u8]>, +) -> Result<()> { + let Some(root) = root.and_then(|bytes| <[u8; 32]>::try_from(bytes).ok()) else { + return Ok(()); + }; + let root = ChangeHash(root); + if epoch != state.epoch_stamp().0 { + // Another epoch: catching up is its business. + return Ok(()); + } + if let Some(ours) = own(state).await + && ours != root + { + if state + .roots + .lock_or_recover() + .differing + .insert(peer.to_owned()) + { + error!(peer = %peer, ours = %ours, theirs = %root, epoch = %epoch, "A peer's document starts from another root of this epoch: another history under this swarm's ID (a forged root, or a genesis started again); not synced with"); + } + bail!("{peer} starts epoch {epoch} from root {root}, ours from {ours}"); + } + if epoch.generation == 0 { + let pin = { + let mut roots = state.roots.lock_or_recover(); + roots.named.insert(peer.to_owned(), root); + pin(state.genesis_root, &roots.named) + }; + let mut screening = state.screening.lock_or_recover(); + if screening.root_pin != pin { + match &pin { + RootPin::Disputed => { + warn!( + "Peers name different roots of the swarm's first epoch: taking none until they agree, or one is given (--genesis-root)" + ); + } + RootPin::Only(root) => { + info!(root = %root, "The swarm's root, as given or as its peers name it") + } + RootPin::Any => {} + } + screening.root_pin = pin; + } + } + Ok(()) +} + +/// What an empty document of the first epoch takes as its root: the one `given`, else +/// the one all peers name (`named`), none while they differ, any while none is named. +pub(crate) fn pin(given: Option, named: &HashMap) -> RootPin { + if let Some(given) = given { + return RootPin::Only(given); + } + let mut roots: Vec<&ChangeHash> = named.values().collect(); + roots.sort_unstable(); + roots.dedup(); + match roots.as_slice() { + [] => RootPin::Any, + [root] => RootPin::Only(**root), + _ => RootPin::Disputed, + } +} + +#[cfg(test)] +mod tests { + use super::*; + + /// The root given wins; else the one every peer names; none while they differ. + #[test] + fn what_a_joiner_takes_as_its_root() { + let (a, b) = (ChangeHash([1; 32]), ChangeHash([2; 32])); + let named = |roots: &[(&str, ChangeHash)]| -> HashMap { + roots + .iter() + .map(|(peer, root)| ((*peer).to_owned(), *root)) + .collect() + }; + assert_eq!(pin(None, &named(&[])), RootPin::Any); + assert_eq!(pin(None, &named(&[("p", a), ("q", a)])), RootPin::Only(a)); + assert_eq!(pin(None, &named(&[("p", a), ("q", b)])), RootPin::Disputed); + assert_eq!(pin(Some(b), &named(&[("p", a)])), RootPin::Only(b)); + } +} -- cgit v1.3.1