screen: a signature vouches for its change and what it builds on

Review finding 5: vouching by (actor, seq) isn't bound to a hash. A
member can make a change under another member's actor at a seq that
member's signature covers. The change is then taken as vouched, and if
it breaks a rule, the honest member is refused as a whole and logged as
the one whose own change broke the rules.

A signature now vouches for its change and the changes of its actor it
builds on: in the document, as before; among received changes, those
it reaches through the batch's dependencies. A received change under an
actor at a seq whose change the document holds (a signature verified up
to it) is a fork: refused as forged, never as its actor's node's, not
told back in REFUSALS, and logged with the peer that brought it.

3 files changed, 108 insertions, 10 deletions

diff --git a/src/access/screen.rs b/src/access/screen.rs
index be4bb9c..37e3adf 100644
--- a/src/access/screen.rs
+++ b/src/access/screen.rs
@@ -22,8 +22,11 @@
 //! A change whose dependencies are neither in the document nor among those received
 //! waits (`Waiting`) until they come, a bounded number; Automerge never sees it before.
 //! With signatures required (`access::policy`), so does one no signature by its
-//! committer vouches for yet (`Signatures::vouch_batch`), and whatever builds on it,
-//! until one comes, but an epoch's root, which no node signs.
+//! committer vouches for yet, and whatever builds on it, until one comes, but an epoch's
+//! root, which no node signs: a signature vouches for its change and the changes of its
+//! actor among those received it builds on (`Signatures::vouch_batch`). One made under
+//! an actor at a seq whose change the document holds is forged (`Signatures::forks`):
+//! refused, by whoever brought it, not by the node the actor is.
 
 use std::collections::{BTreeSet, HashMap, HashSet};
 
@@ -200,6 +203,8 @@ pub(crate) struct Screened {
     pub(crate) taken_from: BTreeSet<String>,
     /// The changes that broke a rule, of those refused (now, or again).
     pub(crate) roots: BTreeSet<ChangeHash>,
+    /// Received changes forged under another node's actor (`Signatures::forks`).
+    pub(crate) forged: usize,
 }
 
 /// Judges `received` (and those `waiting` before) and applies to `doc` (of `epoch`)
@@ -217,6 +222,7 @@ pub(crate) fn apply(
     log: &mut crate::document::PatchLog,
 ) -> Result<Screened> {
     let mut screened = Screened::default();
+    let from_received: HashSet<ChangeHash> = received.iter().map(Change::hash).collect();
     // Each once, not in the document yet, not refused before.
     let mut seen = HashSet::new();
     let candidates: Vec<Change> = std::mem::take(&mut waiting.0)
@@ -299,12 +305,37 @@ pub(crate) fn apply(
     if let Some(signatures) = signatures.as_deref_mut() {
         signatures.vouch_batch(&ready, &committers);
     }
+    // Those a signature vouches for: a signed one, and the changes of its actor among
+    // these it builds on (`ready` is in order: one's descendants come after it).
+    let mut vouched: HashSet<ChangeHash> = HashSet::new();
+    if let Some(signatures) = signatures.as_deref() {
+        let in_batch: HashSet<ChangeHash> = ready.iter().map(Change::hash).collect();
+        let mut signed_after: HashMap<ChangeHash, HashSet<crate::document::ActorId>> =
+            HashMap::new();
+        for change in ready.iter().rev() {
+            let hash = change.hash();
+            let mut actors = signed_after.remove(&hash).unwrap_or_default();
+            if signatures.signed(&hash) {
+                actors.insert(change.actor_id().clone());
+            }
+            if actors.contains(change.actor_id()) {
+                vouched.insert(hash);
+            }
+            for dep in change.deps().iter().filter(|dep| in_batch.contains(dep)) {
+                signed_after
+                    .entry(*dep)
+                    .or_default()
+                    .extend(actors.iter().cloned());
+            }
+        }
+    }
 
     // The changes of the document each accepted one, not applied yet, builds on.
     let mut frontier: HashMap<ChangeHash, Vec<ChangeHash>> = HashMap::new();
     // Refused in this batch, each with the change that broke a rule.
     let mut refused: HashMap<ChangeHash, ChangeHash> = HashMap::new();
     let mut unsigned: HashSet<ChangeHash> = HashSet::new();
+    let mut forged: HashSet<ChangeHash> = HashSet::new();
     let mut accepted: Vec<Change> = Vec::new();
     for (index, change) in ready.iter().enumerate() {
         let hash = change.hash();
@@ -333,13 +364,29 @@ pub(crate) fn apply(
                 .push(refuse(format!("it builds on refused change {dep}")));
             continue;
         }
-        // No signature vouches for it yet, or for what it builds on: it waits.
-        let vouched = |signatures: &Signatures| {
-            change.deps().is_empty() || signatures.verified(change.actor_id(), change.seq())
-        };
+        // Made under an actor whose change at its seq the document holds: forged, by
+        // whoever brought it, not by the node the actor is.
         if signatures
             .as_deref()
-            .is_some_and(|signatures| !vouched(signatures))
+            .is_some_and(|signatures| signatures.forks(doc, change))
+        {
+            refused.insert(hash, hash);
+            forged.insert(hash);
+            if from_received.contains(&hash) {
+                screened.forged += 1;
+            }
+            screened.refused.push(Refused {
+                committer: None,
+                ..refuse(format!(
+                    "it is forged: the document holds the change of its actor ({}) at its seq ({})",
+                    committer.unwrap_or("unknown"),
+                    change.seq()
+                ))
+            });
+            continue;
+        }
+        // No signature vouches for it yet, or for what it builds on: it waits.
+        if signatures.is_some() && !change.deps().is_empty() && !vouched.contains(&hash)
             || change.deps().iter().any(|dep| unsigned.contains(dep))
         {
             unsigned.insert(hash);
@@ -409,7 +456,10 @@ pub(crate) fn apply(
     }
     for (hash, root) in refused {
         refusals.insert(hash, root);
-        screened.roots.insert(root);
+        // A forged one broke no rule its sender would judge it by.
+        if !forged.contains(&root) {
+            screened.roots.insert(root);
+        }
     }
     waiting.0.truncate(MAX_WAITING);
     Ok(screened)
@@ -425,6 +475,8 @@ pub(crate) struct Outcome {
     pub(crate) refused_again: bool,
     /// The changes that broke a rule, of those refused (`swarm::refusals`).
     pub(crate) roots: Vec<ChangeHash>,
+    /// Changes the bytes carried forged under another node's actor: their sender's.
+    pub(crate) forged: usize,
 }
 
 /// [`apply`] of the changes in `bytes`, as sync messages and downloads carry them, with
@@ -470,6 +522,7 @@ pub(crate) fn apply_bytes(
         applied: screened.applied,
         refused_again: received > 0 && screened.refused_again == received,
         roots: screened.roots.iter().copied().collect(),
+        forged: screened.forged,
     };
     screening.judge_members(&screened);
     screening.record(screened.refused);
@@ -848,8 +901,16 @@ mod tests {
             &format!("_continuum/members/{node}"),
             json!({}),
         );
+        let before = theirs.get_heads();
         write(&mut theirs, &node, Some("alice"), "notes/x", json!(1));
         let last = theirs.get_heads()[0];
+        // Another change under the node's actor at the seq of its last: a fork anyone
+        // could make, which no signature of the node vouches for.
+        let mut forger = theirs
+            .fork_at(&before)
+            .unwrap()
+            .with_actor(crate::document::actor(&theirs));
+        write(&mut forger, &node, Some("alice"), "notes/forged", json!(4));
 
         let mut ours = Document::new();
         let mut waiting = Waiting::default();
@@ -902,5 +963,20 @@ mod tests {
             store::read_path(&ours, &path("notes/x")).unwrap(),
             Some(json!(1))
         );
+        // The fork: refused as forged, by whoever brought it, not as the node's.
+        let screened = required(
+            &mut ours,
+            &mut waiting,
+            &mut signatures,
+            received(&forger, &before),
+        );
+        assert_eq!((screened.applied, screened.forged), (0, 1));
+        assert!(screened.broke_rules.is_empty() && screened.roots.is_empty());
+        assert!(screened.refused[0].committer.is_none());
+        assert!(
+            store::read_path(&ours, &path("notes/forged"))
+                .unwrap()
+                .is_none()
+        );
     }
 }
diff --git a/src/document/signatures.rs b/src/document/signatures.rs
index 5d8731b..19c13b8 100644
--- a/src/document/signatures.rs
+++ b/src/document/signatures.rs
@@ -4,8 +4,11 @@
 //!
 //! One signature vouches for more than its change: a change's hash covers its
 //! dependencies, and a node's change builds on its previous one, so a signed change of
-//! an actor vouches for all that actor's changes up to it (`check`: the actor and seq
-//! it verifies up to). So not every change needs one: a change is signed when it
+//! an actor vouches for the changes of that actor it builds on: in the document, all
+//! up to it (`check`: the actor and seq it verifies up to); received, not in it yet,
+//! those among them it builds on (`access::screen`). Only those: anyone can make a
+//! change under any actor, and one at a seq whose change the document holds is a fork
+//! (`forks`). So not every change needs one: a change is signed when it
 //! touches protocol data (`_continuum`) or a path the swarm lists as signed
 //! (`_continuum/access/signed`, `listed`), or when its write asks for it (`Sign`); a
 //! change left unsigned is vouched for by the node's next signed one, which, as
@@ -388,6 +391,22 @@ impl Signatures {
         }
     }
 
+    /// Whether a valid signature of `hash` is kept: it vouches for its change and the
+    /// changes of its actor it builds on.
+    pub(crate) fn signed(&self, hash: &ChangeHash) -> bool {
+        self.by_change.contains_key(hash)
+    }
+
+    /// Whether `change`, not in `doc`, forks its actor's changes: `doc` holds a change
+    /// a signature verified of that actor at a seq as late, so its real change at
+    /// `change`'s seq too. Anyone can make a change under any actor; only its node can
+    /// sign one.
+    pub(crate) fn forks(&self, doc: &Document, change: &super::Change) -> bool {
+        self.latest.get(change.actor_id()).is_some_and(|latest| {
+            latest.seq >= change.seq() && doc.get_change_meta_by_hash(&latest.hash).is_some()
+        })
+    }
+
     /// Whether a signature vouches for `actor`'s change `seq`.
     pub(crate) fn verified(&self, actor: &super::ActorId, seq: u64) -> bool {
         self.latest
diff --git a/src/swarm/sync.rs b/src/swarm/sync.rs
index ef2c1b3..ffdbf07 100644
--- a/src/swarm/sync.rs
+++ b/src/swarm/sync.rs
@@ -661,6 +661,9 @@ pub(crate) async fn handle_sync(
                             )?;
                             refused_again = outcome.refused_again;
                             roots = outcome.roots;
+                            if outcome.forged > 0 {
+                                tracing::warn!(peer = %peer, forged = outcome.forged, "A peer brought changes forged under another node's actor: refused");
+                            }
                         }
                         sync.receive_logged(doc, message, log)
                     })();