diff options
| author | tv <tv@krebsco.de> | 2026-11-15 16:41:07 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-15 16:41:07 +0000 |
| commit | 2d1c64a6e7134f4d6942d4539b27d45f14e7538c (patch) | |
| tree | 8253ae9782fa3067ae4a75d1cea15840f9d456ba /src | |
| parent | 5005b13115caedbe0bda9a8496d95d2b4752c62d (diff) | |
remakes: values signed by their users replayed as chains
Under a strict policy, a replay wrote at each path the old document's
merged view: at a place of a value its user signed, the last envelope
alone, whose `prev` names one the new epoch doesn't hold if the value
was written twice since the base. Every node refused it, it went to
the quarantine, and the new epoch kept the base's value: a remake
rolled back every signed value changed twice since its base, and a
rejoining node lost its own the same way. And the replay found what
changed by Automerge's diff, which says nothing of a value that
changed beside Automerge's own choice: where a place held two values
at the base, a write replacing the one read by `seq` wasn't replayed
at all.
Now, under a strict policy, the places of signed values are found from
the changes' operations as well as from the diff, and each is replayed
as the chain that leads to the envelope the old document reads: every
envelope from the one the new document holds there, following `prev`
through the changes since the base, each in a change of its own by its
signer at the time it was made, judged as every node will judge it.
A place is replayed only where the new document holds a lower `seq`
there; where no chain leads from what it holds, it goes to the
quarantine. A path above such places is split into its keys. Without
a strict policy nothing changes.
Diffstat (limited to 'src')
| -rw-r--r-- | src/remake/delta.rs | 402 |
1 files changed, 399 insertions, 3 deletions
diff --git a/src/remake/delta.rs b/src/remake/delta.rs index a152861..c8e07c0 100644 --- a/src/remake/delta.rs +++ b/src/remake/delta.rs @@ -32,14 +32,25 @@ //! document touched it (or a path above or below it) later than the write being //! replayed, as the changes' timestamps say; and the replayed changes carry the times //! of the writes they replay, not of the replay, so later replays judge by those. +//! +//! Under a strict policy, a value its user signed (`access::envelope`) is replayed as +//! the chain that leads to it ([`signed_places`], [`chain`]): every envelope from the +//! one the new document holds there to the one the old document reads, each in a +//! change of its own, by its signer, at its own time, so that each replaces the one +//! before it as every node checks; and only where the new document holds a lower `seq` +//! there, as values signed by their users are read by `seq`, not by clocks. A place is +//! found from the changes' operations as well as from the diff, which says nothing of a +//! value that changed beside Automerge's own choice. -use std::collections::{BTreeMap, HashMap, HashSet}; +use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet}; use crate::document::{ActorId, ChangeHash, Document, ReadDoc, Transactable}; use serde::{Deserialize, Serialize}; use tracing::{info, warn}; use super::kind::{Translation, Translator}; +use crate::access::envelope; +use crate::document::at::At; use crate::document::meta::{self, EPOCHS, REMAKES, VOTES}; use crate::document::store::{self, InLists, StoreError}; @@ -102,9 +113,18 @@ pub(crate) fn replay_newest( if before == after { return stats; } - let written = touched(src, &between(src, before, after)); + let changes = between(src, before, after); + let written = touched(src, &changes); + // Values their users signed, under a strict policy: replayed as chains, below. + let (signed, paths) = signed_places( + src, + before, + after, + &written, + changed_paths(src, before, after), + ); // Split where several users wrote below a path: each part replayed for its own. - let paths = by_user(src, dst, &written, changed_paths(src, before, after)); + let paths = by_user(src, dst, &written, paths); let ours: Vec<(i64, Option<String>)> = paths .iter() .map(|path| { @@ -124,6 +144,23 @@ pub(crate) fn replay_newest( let theirs = touched(dst, &newer); let mut by_time: BTreeMap<(i64, Option<String>), Vec<Vec<String>>> = BTreeMap::new(); + // The links of the chains to signed values, each a change of its own, before what is + // written at the same time (it may decide who may write that). + let mut links: BTreeMap<(i64, usize), (Vec<String>, String, String)> = BTreeMap::new(); + for place in signed { + match chain(src, &changes, &place, dst) { + Chain::Links(chain) => { + // In their order, whatever their clocks say. + let mut at = i64::MIN; + for (when, envelope, user) in chain { + at = at.max(when); + links.insert((at, links.len()), (place.clone(), envelope, user)); + } + } + Chain::Held => stats.superseded += 1, + Chain::Broken(why) => stats.quarantined.push((place, why)), + } + } for (path, (at, user)) in paths.into_iter().zip(ours) { if user.is_none() && others_entry(&path, node) { continue; @@ -142,7 +179,25 @@ pub(crate) fn replay_newest( } } crate::document::replica::authored(dst, node); + let mut refused: HashSet<Vec<String>> = HashSet::new(); + let mut links = links.into_iter().peekable(); for ((at, user), paths) in by_time { + while let Some(((when, _), _)) = links.peek() + && *when <= at + { + let ((when, _), (place, envelope, signer)) = links.next().expect("peeked"); + write_link( + dst, + epoch, + node, + when, + &place, + envelope, + &signer, + &mut refused, + &mut stats, + ); + } let before = dst.get_heads(); let mut transaction = dst.transaction(); let group = replay_paths(src, &mut transaction, &paths, translator); @@ -182,6 +237,19 @@ pub(crate) fn replay_newest( } } } + for ((when, _), (place, envelope, signer)) in links { + write_link( + dst, + epoch, + node, + when, + &place, + envelope, + &signer, + &mut refused, + &mut stats, + ); + } if stats.superseded > 0 { info!( superseded = stats.superseded, @@ -196,6 +264,216 @@ pub(crate) fn replay_newest( stats } +/// Writes `envelope` at `place` in `dst`, a change of its own by `node` for `signer` at +/// `at`, judged as every node will judge it: one they would refuse is taken back, and +/// its place quarantined, and nothing more of that place's chain written. +#[allow(clippy::too_many_arguments)] +fn write_link( + dst: &mut Document, + epoch: crate::document::replica::Epoch, + node: &str, + at: i64, + place: &[String], + envelope: String, + signer: &str, + refused: &mut HashSet<Vec<String>>, + stats: &mut ReplayStats, +) { + if refused.contains(place) { + return; + } + let before = dst.get_heads(); + let mut transaction = dst.transaction(); + if let Err(error) = store::write_path( + &mut transaction, + place, + &serde_json::Value::String(envelope), + ) { + transaction.rollback(); + log_failure(place, &error); + stats.failed += 1; + refused.insert(place.to_vec()); + return; + } + let writer = crate::document::replica::Writer { + node, + user: Some(signer), + }; + let mut options = automerge::transaction::CommitOptions::default().with_time(at); + if let Some(message) = writer.message() { + options = options.with_message(message); + } + transaction.commit_with(options); + match judged(dst, epoch, &before) { + Ok(()) => stats.replayed += 1, + Err(why) => { + let actor = dst.get_actor().clone(); + match dst.fork_at(&before) { + Ok(kept) => { + *dst = kept.with_actor(actor); + crate::document::replica::authored(dst, node); + } + Err(error) => { + warn!(error = %error, "Could not take back a replay every node would refuse"); + stats.replayed += 1; + return; + } + } + refused.insert(place.to_vec()); + stats + .quarantined + .push((place.to_vec(), format!("every node would refuse it: {why}"))); + } + } +} + +/// Under a strict policy in `src` at `after` (`access::policy`), the places of values +/// their users sign (`access::envelope::signed_paths`) whose value, as a read shows it, +/// changed between `before` and `after`: found among `paths` (from the diff) and among +/// the paths the changes wrote (`written`), a path above such places split into its +/// keys. And the rest of `paths`. Without a strict policy, none, and `paths` as they are. +fn signed_places( + src: &Document, + before: &[ChangeHash], + after: &[ChangeHash], + written: &[Touched], + paths: Vec<Vec<String>>, +) -> (Vec<Vec<String>>, Vec<Vec<String>>) { + let (Some(then), Some(now)) = (At::new(src, before), At::new(src, after)) else { + return (Vec::new(), paths); + }; + if !crate::access::policy::of(&now).strict() { + return (Vec::new(), paths); + } + let signed = envelope::signed_paths(&now); + let mut places = BTreeSet::new(); + let mut rest = Vec::new(); + let mut todo: Vec<Vec<String>> = paths; + todo.extend( + written + .iter() + .flat_map(|(_, _, paths)| paths.iter()) + .filter(|path| envelope::is_signed(&signed, path)) + .cloned(), + ); + while let Some(path) = todo.pop() { + if envelope::is_signed(&signed, &path) { + places.insert(path); + } else if envelope::above_signed(&signed, &path) { + let mut keys = store::keys_at(&now, &path) + .ok() + .flatten() + .unwrap_or_default(); + keys.extend( + store::keys_at(&then, &path) + .ok() + .flatten() + .unwrap_or_default(), + ); + keys.sort(); + keys.dedup(); + for key in &keys { + let mut child = path.clone(); + child.push(key.clone()); + todo.push(child); + } + if keys.is_empty() { + rest.push(path); + } + } else { + rest.push(path); + } + } + rest.sort(); + rest.dedup(); + let places = places + .into_iter() + .filter(|place| store::read_path(&then, place).ok() != store::read_path(&now, place).ok()) + .collect(); + (places, rest) +} + +/// What replaying a signed place takes. +enum Chain { + /// The envelopes to write, in order, each with its change's time and its signer. + Links(Vec<(i64, String, String)>), + /// The new document holds as high a `seq` there already. + Held, + /// No chain leads there from what the new document holds: why. + Broken(String), +} + +/// The chain of envelopes `src` holds at `place` (written by `changes`) that leads from +/// what `dst` holds there to what `src` reads there, following `prev`. +fn chain(src: &Document, changes: &[ChangeHash], place: &[String], dst: &Document) -> Chain { + let raw = |doc: &dyn Fn() -> Option<serde_json::Value>| match doc() { + Some(serde_json::Value::String(text)) => Some(text), + _ => None, + }; + let Some(target) = raw(&|| store::read_path(src, place).ok().flatten()) else { + return Chain::Broken("no value its user signed is there to replay".to_owned()); + }; + let Ok(payload) = envelope::read(&target) else { + return Chain::Broken("what is there isn't a value its user signed".to_owned()); + }; + let held = raw(&|| store::read_path(dst, place).ok().flatten()) + .filter(|text| envelope::read(text).is_ok()); + if let Some(seq) = held.as_deref().and_then(envelope::seq) + && seq >= payload.seq + { + return Chain::Held; + } + // Every envelope the changes left at the place, by its digest, with its time. + let mut known: HashMap<String, (i64, String)> = HashMap::new(); + for hash in changes { + let wrote = store::changed_by(src, hash, InLists::Whole) + .is_some_and(|paths| paths.iter().any(|path| path == place)); + let Some(at) = wrote + .then(|| At::new(src, std::slice::from_ref(hash))) + .flatten() + else { + continue; + }; + let time = src + .get_change_by_hash(hash) + .map_or(0, |change| change.timestamp()); + for value in store::read_candidates(&at, place).unwrap_or_default() { + if let serde_json::Value::String(text) = value + && envelope::read(&text).is_ok() + { + let digest = envelope::digest(Some(&text)); + known.entry(digest).or_insert((time, text)); + } + } + } + let from = envelope::digest(held.as_deref()); + let mut links = Vec::new(); + let mut current = target; + loop { + let Ok(payload) = envelope::read(¤t) else { + return Chain::Broken("a link of its chain isn't a value its user signed".to_owned()); + }; + let time = known + .get(&envelope::digest(Some(¤t))) + .map_or(0, |(time, _)| *time); + let prev = payload.prev.clone(); + links.push((time, current, payload.user)); + if prev == from { + break; + } + match known.get(&prev) { + Some((_, before)) if links.len() <= known.len() => current = before.clone(), + _ => { + return Chain::Broken( + "the new epoch holds another value there, not one it replaced".to_owned(), + ); + } + } + } + links.reverse(); + Chain::Links(links) +} + /// The change just committed to `doc` (the one head after `before`), judged under a /// policy as every node will judge it on receipt; why it is refused, if it is. fn judged( @@ -783,6 +1061,124 @@ mod tests { assert!(store::read_path(&new, &path("notes/y")).unwrap().is_none()); } + /// A strict swarm's document, with alice, whose key is `key`, writing `config`, + /// a value its user signs; and the envelope alice signs there, after `prev`. + fn strict_with(key: &ed25519_dalek::SigningKey) -> Document { + use crate::access::sshsig; + let path = |text: &str| -> Vec<String> { text.split('/').map(str::to_owned).collect() }; + let mut alice = crate::access::registry::entry( + "root", + 1, + &[(path("config"), &[crate::access::Right::Write][..])], + ); + alice["keys"] = json!({ "k": sshsig::PublicKey(key.verifying_key().to_bytes()).line() }); + let mut doc = Document::new(); + change(&mut doc, |doc| { + store::write_path(doc, &path("_continuum/swarm"), &json!("s")).unwrap(); + store::write_path( + doc, + &path("_continuum/access/policy"), + &json!({"version": 1, "values": "signed"}), + ) + .unwrap(); + store::write_path( + doc, + &path("_continuum/access/userSigned"), + &json!([["config"]]), + ) + .unwrap(); + store::write_path(doc, &path("_continuum/members/node"), &json!({})).unwrap(); + store::write_path(doc, &path("_continuum/users/alice"), &alice).unwrap(); + }); + crate::document::replica::authored(&mut doc, "node"); + doc + } + + fn signed_after(key: &ed25519_dalek::SigningKey, prev: Option<&str>, value: i64) -> String { + use crate::access::sshsig; + let payload = crate::document::signed::Payload { + value: json!(value), + swarm: "s".to_owned(), + path: vec!["config".to_owned()], + user: "alice".to_owned(), + at: 1, + seq: prev.and_then(envelope::seq).map_or(0, |seq| seq + 1), + prev: envelope::digest(prev), + }; + let bytes = payload.signed(); + envelope::seal(&bytes, &sshsig::sign(key, envelope::NAMESPACE, &bytes)).unwrap() + } + + fn alice_writes(doc: &mut Document, at: i64, envelope: &str) { + let mut transaction = doc.transaction(); + store::write_path(&mut transaction, &["config".to_owned()], &json!(envelope)).unwrap(); + transaction.commit_with( + automerge::transaction::CommitOptions::default() + .with_time(at) + .with_message("User: alice".to_owned()), + ); + } + + /// Under a strict policy, a value its user signed, written twice since the base, is + /// replayed as its chain: each envelope after the one the new document holds, in + /// order, so that every node takes each. Of two written at once, only the one the + /// chain leads through. + #[test] + fn signed_values_replay_as_chains() { + let key = ed25519_dalek::SigningKey::from_bytes(&[7; 32]); + let mut old = strict_with(&key); + let first = signed_after(&key, None, 1); + alice_writes(&mut old, 5, &first); + let base = old.get_heads(); + let new = old.clone().with_actor(automerge::ActorId::random()); + + // Two written at once after the first, and one more after the second of them. + let mut side = old.fork_at(&base).unwrap(); + let aside = signed_after(&key, Some(&first), 2); + alice_writes(&mut side, 10, &aside); + let second = signed_after(&key, Some(&first), 3); + alice_writes(&mut old, 10, &second); + let third = signed_after(&key, Some(&second), 4); + alice_writes(&mut old, 20, &third); + old.merge(&mut side).unwrap(); + assert_eq!( + store::read_path(&old, &["config".to_owned()]).unwrap(), + Some(json!(third)) + ); + + let mut replayed = new.clone(); + let stats = replay_newest( + &old, + &base, + &old.get_heads(), + &mut replayed, + crate::document::replica::Epoch::GENESIS, + "node", + &Translator::default(), + Superseded::Drop, + ); + assert!(stats.quarantined.is_empty(), "{:?}", stats.quarantined); + assert_eq!(stats.replayed, 2); + assert_eq!( + store::read_candidates(&replayed, &["config".to_owned()]).unwrap(), + [json!(third)] + ); + + // Where the new document holds as high a `seq` already: nothing. + let stats = replay_newest( + &old, + &base, + &old.get_heads(), + &mut replayed, + crate::document::replica::Epoch::GENESIS, + "node", + &Translator::default(), + Superseded::Drop, + ); + assert_eq!(stats.replayed, 0); + assert!(stats.quarantined.is_empty()); + } + /// The first group refused: those after it still replayed, still the node's (a /// fork, taking the refused one back, has no author of its own). #[test] |
