signatures: changes signed by their node

Every node signs the changes it commits with its node key, an Ed25519
signature over the change's hash, kept beside the document. One
signature on an actor's latest change vouches for its earlier ones.
Protocol data and paths listed in _continuum/access/signed are signed,
and writes with ?signed=true.

Auth plan M5.

3 files changed, 188 insertions, 0 deletions

diff --git a/src/document/mod.rs b/src/document/mod.rs
index 00ba4cb..19d1110 100644
--- a/src/document/mod.rs
+++ b/src/document/mod.rs
@@ -44,6 +44,7 @@ pub(crate) mod file;
 pub(crate) mod lock;
 pub(crate) mod meta;
 pub(crate) mod replica;
+pub(crate) mod signatures;
 pub(crate) mod store;
 pub(crate) mod sync;
 #[cfg(test)]
diff --git a/src/document/replica.rs b/src/document/replica.rs
index 03325eb..ead42f6 100644
--- a/src/document/replica.rs
+++ b/src/document/replica.rs
@@ -124,6 +124,8 @@ pub(crate) struct Replica {
     /// What local writes and sync changed since the change publisher last looked
     /// (`changed_since`), so it needn't diff the document for it.
     log: std::sync::Mutex<Log>,
+    /// The signatures of the document's changes this node has (`document::signatures`).
+    pub(crate) signatures: super::signatures::Signatures,
 }
 
 /// The patches of the changes from `from` to `to` (sorted heads) of the document of
@@ -180,6 +182,7 @@ impl Replica {
             heads: Vec::new(),
             stamp,
             log,
+            signatures: Default::default(),
         };
         replica.refresh_heads();
         replica
diff --git a/src/document/signatures.rs b/src/document/signatures.rs
new file mode 100644
index 0000000..5d50a33
--- /dev/null
+++ b/src/document/signatures.rs
@@ -0,0 +1,184 @@
+//! Changes signed by the node that committed them: an Ed25519 signature by its node
+//! key over the change's hash (`message`), kept beside the document, not in it (a
+//! change's hash covers its message, so it can't carry its own signature).
+//!
+//! 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
+//! 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.
+
+use std::collections::HashMap;
+
+use super::{ChangeHash, Document};
+
+/// Where the swarm lists the paths whose writes are signed: a list of paths, each a
+/// list of segments, as capabilities name them (`access.md`).
+pub(crate) const SIGNED_PATHS: [&str; 3] = ["_continuum", "access", "signed"];
+
+/// What a signature is made over: a domain, then the change's hash.
+pub(crate) fn message(hash: &ChangeHash) -> Vec<u8> {
+    let mut message = b"continuum/change/1\0".to_vec();
+    message.extend_from_slice(&hash.0);
+    message
+}
+
+/// Whether a write is signed (`wanted`).
+#[derive(Debug, Clone)]
+pub(crate) enum Sign {
+    /// The node's own work: protocol data, always signed.
+    Protocol,
+    /// A write through the API at `path`, signed if `asked` (`?signed=true`) or if the
+    /// path is protocol data or listed as signed.
+    Write { path: Vec<String>, asked: bool },
+}
+
+impl Sign {
+    /// Whether a change made so, in `doc`, is to be signed.
+    pub(crate) fn wanted(&self, doc: &Document) -> bool {
+        match self {
+            Sign::Protocol => true,
+            Sign::Write { path, asked } => {
+                *asked
+                    || path.first().map(String::as_str) == Some(SIGNED_PATHS[0])
+                    || listed(doc).iter().any(|signed| related(signed, path))
+            }
+        }
+    }
+}
+
+/// Whether a write at `path` touches what is at `signed`: within it, or above it
+/// (replacing or deleting what holds it).
+fn related(signed: &[String], path: &[String]) -> bool {
+    path.starts_with(signed) || signed.starts_with(path)
+}
+
+/// The paths `doc` lists as signed (`SIGNED_PATHS`); an entry that isn't a list of
+/// strings is left out.
+pub(crate) fn listed(doc: &Document) -> Vec<Vec<String>> {
+    let at: Vec<String> = SIGNED_PATHS.iter().map(|s| (*s).to_owned()).collect();
+    let Ok(Some(serde_json::Value::Array(entries))) = super::store::read_path(doc, &at) else {
+        return Vec::new();
+    };
+    entries
+        .iter()
+        .filter_map(|entry| {
+            entry
+                .as_array()?
+                .iter()
+                .map(|segment| segment.as_str().map(str::to_owned))
+                .collect()
+        })
+        .collect()
+}
+
+/// A document's signatures, by change.
+#[derive(Debug, Default)]
+pub(crate) struct Signatures {
+    by_change: HashMap<ChangeHash, [u8; 64]>,
+}
+
+impl Signatures {
+    pub(crate) fn insert(&mut self, hash: ChangeHash, signature: [u8; 64]) {
+        self.by_change.insert(hash, signature);
+    }
+
+    /// Signs `hash` with `key` and keeps the signature.
+    pub(crate) fn sign(&mut self, hash: ChangeHash, key: &crate::identity::NodeKey) {
+        self.insert(hash, key.sign(&message(&hash)));
+    }
+}
+
+/// What a valid signature of a change in `doc` verifies: its actor's changes up to its
+/// seq, committed by the node its author names (its node ID, whose key it is). None if
+/// `doc` doesn't hold the change, its author isn't a node ID, or the signature isn't
+/// that node's over it.
+#[cfg_attr(not(test), allow(dead_code))]
+pub(crate) fn check(
+    doc: &Document,
+    hash: &ChangeHash,
+    signature: &[u8; 64],
+) -> Option<(super::ActorId, u64)> {
+    let meta = doc.get_change_meta_by_hash(hash)?;
+    let author = std::str::from_utf8(meta.author.as_ref()?.as_bytes()).ok()?;
+    let key = crate::identity::public_of(author)?;
+    crate::identity::verify(&key, &message(hash), signature)
+        .then(|| (meta.actor.into_owned(), meta.seq))
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::clock::UnixMillis;
+    use crate::document::replica::{Writer, transact};
+    use crate::document::store;
+    use crate::identity::NodeKey;
+    use serde_json::json;
+
+    fn write(doc: &mut Document, node: &str, path: &[&str], value: serde_json::Value) {
+        let path: Vec<String> = path.iter().map(|s| (*s).to_owned()).collect();
+        let writer = Writer { node, user: None };
+        transact(doc, UnixMillis(1), &writer, |doc| {
+            store::write_path(doc, &path, &value)
+        })
+        .unwrap();
+    }
+
+    /// A signature verifies its actor's changes up to it, by the node its author names;
+    /// another node's key, or another change, doesn't.
+    #[test]
+    fn a_signature_vouches_for_its_actors_changes_up_to_it() {
+        let key = NodeKey::from_seed([1; 32]);
+        let other = NodeKey::from_seed([2; 32]);
+        let node = key.id();
+        let mut doc = Document::new();
+        write(&mut doc, &node, &["a"], json!(1));
+        write(&mut doc, &node, &["b"], json!(2));
+        let last = doc.get_heads()[0];
+        let (actor, seq) = check(&doc, &last, &key.sign(&message(&last))).unwrap();
+        assert_eq!(&actor, doc.get_actor());
+        assert_eq!(seq, 2);
+        assert!(check(&doc, &last, &other.sign(&message(&last))).is_none());
+        let first = doc.get_changes(&[])[0].hash();
+        assert!(check(&doc, &last, &key.sign(&message(&first))).is_none());
+        // A change whose author isn't a node ID: nobody's to check.
+        let mut named = Document::new();
+        write(&mut named, "node", &["a"], json!(1));
+        let hash = named.get_heads()[0];
+        assert!(check(&named, &hash, &key.sign(&message(&hash))).is_none());
+    }
+
+    /// Protocol data, listed paths (within or above them) and asked-for writes are
+    /// signed; others aren't.
+    #[test]
+    fn which_writes_are_signed() {
+        let mut doc = Document::new();
+        let write_at = |path: &[&str], asked| Sign::Write {
+            path: path.iter().map(|s| (*s).to_owned()).collect(),
+            asked,
+        };
+        assert!(Sign::Protocol.wanted(&doc));
+        assert!(write_at(&["_continuum", "users", "a"], false).wanted(&doc));
+        assert!(!write_at(&["metrics", "cpu"], false).wanted(&doc));
+        assert!(write_at(&["metrics", "cpu"], true).wanted(&doc));
+        write(
+            &mut doc,
+            "node",
+            &SIGNED_PATHS,
+            json!([["config"], ["servers", "eu"], "junk", [1]]),
+        );
+        assert_eq!(
+            listed(&doc),
+            vec![
+                vec!["config".to_owned()],
+                vec!["servers".to_owned(), "eu".to_owned()]
+            ]
+        );
+        assert!(write_at(&["config", "x"], false).wanted(&doc));
+        assert!(write_at(&["servers"], false).wanted(&doc));
+        assert!(!write_at(&["servers", "us"], false).wanted(&doc));
+        assert!(!write_at(&["configs"], false).wanted(&doc));
+    }
+}