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.

10 files changed, 251 insertions, 14 deletions

diff --git a/src/api/login.rs b/src/api/login.rs
index 023408e..b84a412 100644
--- a/src/api/login.rs
+++ b/src/api/login.rs
@@ -14,6 +14,7 @@
 //! Every request may bring a token instead of a password: `Authorization: Bearer ct1…`
 //! (`bearer`).
 
+use crate::document::signatures::Sign;
 use std::sync::Arc;
 
 use axum::{
@@ -261,7 +262,7 @@ pub(crate) async fn revoke_tokens(state: &AppState, name: &str, by: &str) -> Res
     // Issued in this very millisecond: revoked too.
     let after = state.clock.now_millis().as_u64() + 1;
     state
-        .mutate_doc_for(Some(by.to_owned()), move |doc| {
+        .mutate_doc_for(Some(by.to_owned()), Sign::Protocol, move |doc| {
             if !registry::exists(&*doc) {
                 return Err(ApiError(
                     StatusCode::CONFLICT,
diff --git a/src/api/store.rs b/src/api/store.rs
index 48fc2c6..7307d92 100644
--- a/src/api/store.rs
+++ b/src/api/store.rs
@@ -1,5 +1,6 @@
 //! /store and /stream handlers.
 
+use crate::document::signatures::Sign;
 use std::io::Error as IoError;
 
 use axum::{
@@ -90,12 +91,18 @@ pub(crate) struct PostQuery {
     /// With `cast`, how timestamps are read from and written as strings (`rfc3339` by
     /// default; `typed::TimestampFormat`).
     format: Option<String>,
+    /// Whether the change is signed whatever its path (`document::signatures`).
+    #[serde(default)]
+    signed: bool,
 }
 
 #[derive(Debug, Deserialize)]
 pub(crate) struct DeleteQuery {
     #[serde(default)]
     prune: bool,
+    /// Whether the change is signed whatever its path (`document::signatures`).
+    #[serde(default)]
+    signed: bool,
 }
 
 /// `GET /store`: the whole store (`docs/openapi.yaml`).
@@ -349,6 +356,9 @@ pub(crate) struct PutQuery {
     /// default); if not, one that would is `409` (`store::Writing::retype`).
     #[serde(default = "yes")]
     retype: bool,
+    /// Whether the change is signed whatever its path (`document::signatures`).
+    #[serde(default)]
+    signed: bool,
 }
 
 fn yes() -> bool {
@@ -377,6 +387,10 @@ pub(crate) async fn put_store_entry(
     }
 
     let path = parse_write_path(&state, &user, &access, &key, "PUT")?;
+    let sign = Sign::Write {
+        path: path.clone(),
+        asked: query.signed,
+    };
     if let Some(redirect) = to_positive(&state, &path, false, None, raw_query.as_deref()).await? {
         return Ok(redirect);
     }
@@ -387,7 +401,7 @@ pub(crate) async fn put_store_entry(
     // A value that can't be shown as asked is refused, and the write with it.
     let writer = user.0.clone();
     let ((retyped, read), heads) = state
-        .mutate_doc_for(Some(user.0.clone()), move |doc| {
+        .mutate_doc_for(Some(user.0.clone()), sign.clone(), move |doc| {
             let before = Before::of(&*doc, &writer);
             let retyped = store::write_val_path(doc, &path, &body.value, writing)
                 .map_err(|e| store_status(e, "Failed to write store value"))?;
@@ -706,6 +720,10 @@ pub(crate) async fn post_store_entry(
         return Err(StatusCode::SERVICE_UNAVAILABLE.into());
     }
     let path = parse_write_path(&state, &user, &access, &key, "POST")?;
+    let sign = Sign::Write {
+        path: path.clone(),
+        asked: query.signed,
+    };
     if query.increment.is_some() && query.cast.is_some() {
         return Err(ApiError(
             StatusCode::BAD_REQUEST,
@@ -723,7 +741,7 @@ pub(crate) async fn post_store_entry(
     if let Some(by) = query.increment {
         let writer = user.0.clone();
         let (value, heads) = state
-            .mutate_doc_for(Some(user.0.clone()), move |doc| {
+            .mutate_doc_for(Some(user.0.clone()), sign.clone(), move |doc| {
                 let before = Before::of(&*doc, &writer);
                 let value = store::increment_path(doc, &path, by)
                     .map_err(|e| store_status(e, "Failed to increment a counter"))?;
@@ -759,7 +777,7 @@ pub(crate) async fn post_store_entry(
         // A value that can't be shown as asked is refused, and the cast with it.
         let writer = user.0.clone();
         let ((retyped, read), heads) = state
-            .mutate_doc_for(Some(user.0.clone()), move |doc| {
+            .mutate_doc_for(Some(user.0.clone()), sign.clone(), move |doc| {
                 let before = Before::of(&*doc, &writer);
                 let retyped = store::cast_path(doc, &path, to, timestamps)
                     .map_err(|e| store_status(e, "Failed to cast a store value"))?;
@@ -775,7 +793,7 @@ pub(crate) async fn post_store_entry(
     let value = body_value(&headers, &body)?;
     let writer = user.0.clone();
     let ((), heads) = state
-        .mutate_doc_for(Some(user.0.clone()), move |doc| {
+        .mutate_doc_for(Some(user.0.clone()), sign.clone(), move |doc| {
             let before = Before::of(&*doc, &writer);
             store::insert_val_path(doc, &path, &value.value)
                 .map_err(|e| store_status(e, "Failed to insert into a list"))?;
@@ -803,6 +821,10 @@ pub(crate) async fn delete_store_entry(
     RawQuery(raw_query): RawQuery,
 ) -> Result<Response, ApiError> {
     let path = parse_write_path(&state, &user, &access, &key, "DELETE")?;
+    let sign = Sign::Write {
+        path: path.clone(),
+        asked: query.signed,
+    };
 
     tracing::Span::current().record("path", path.join("/").as_str());
 
@@ -826,7 +848,7 @@ pub(crate) async fn delete_store_entry(
     });
     let writer = user.0.clone();
     let ((), heads) = state
-        .mutate_doc_for(Some(user.0.clone()), move |doc| {
+        .mutate_doc_for(Some(user.0.clone()), sign.clone(), move |doc| {
             let before = Before::of(&*doc, &writer);
             store::delete_path_pruning(doc, &path, prune)
                 .map_err(|e| store_status(e, "Failed to delete store value"))?;
diff --git a/src/api/users.rs b/src/api/users.rs
index 1d01af7..3b8174d 100644
--- a/src/api/users.rs
+++ b/src/api/users.rs
@@ -23,6 +23,7 @@
 //! the document, logged, named by who made it, and refused (`409`) where it would lock
 //! its maker out (`access::registry_kept`).
 
+use crate::document::signatures::Sign;
 use axum::{
     Extension, Json,
     extract::{Path, State},
@@ -166,7 +167,7 @@ async fn change(
     let writer = user.to_owned();
     let since = state.clock.now_millis().as_u64();
     state
-        .mutate_doc_for(Some(user.to_owned()), move |doc| {
+        .mutate_doc_for(Some(user.to_owned()), Sign::Protocol, move |doc| {
             let before = Before::of(&*doc, &writer);
             f(doc, &by, since)?;
             registry_kept(&*doc, &registry::users_dir(), before, &writer)
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));
+    }
+}
diff --git a/src/node.rs b/src/node.rs
index 23a881d..e64db6c 100644
--- a/src/node.rs
+++ b/src/node.rs
@@ -64,7 +64,9 @@ pub(crate) struct NodeConfig {
     /// (`access::registry::first_users`); empty elsewhere, and where none were named
     /// (the simulations: no registry).
     pub(crate) first_users: crate::access::registry::FirstUsers,
-    /// To sign the tokens this node issues (`access::token`); none in the simulations.
+    /// To sign the tokens this node issues (`access::token`) and the changes it commits
+    /// (`document::signatures`): every node's, its node ID being its public key; none in
+    /// the simulations without the identity layer, whose node IDs are names.
     pub(crate) node_key: Option<Arc<crate::identity::NodeKey>>,
     /// `--token-lifetime`, `--session-lifetime`.
     pub(crate) token_lifetime: Duration,
diff --git a/src/simtest/mod.rs b/src/simtest/mod.rs
index a3001c8..5128d11 100644
--- a/src/simtest/mod.rs
+++ b/src/simtest/mod.rs
@@ -212,7 +212,8 @@ impl Sim {
             swarm_key: None,
             protocol_writers: HashSet::new(),
             first_users: Vec::new(),
-            node_key: None,
+            // Under the identity layer, its key signs as a node's does.
+            node_key: self.identity.then(|| Arc::new(sim_key(id))),
             token_lifetime: Duration::from_secs(3600),
             session_lifetime: Duration::from_secs(86400),
             cors_origins: Vec::new(),
diff --git a/src/state/host.rs b/src/state/host.rs
index b4a785b..47fd946 100644
--- a/src/state/host.rs
+++ b/src/state/host.rs
@@ -24,6 +24,8 @@ impl AppState {
     /// document. (Lock order doc -> peer, as in sync generation.)
     fn swap_document(&self, replica: &mut Replica, epoch: Epoch, doc: Document) -> Document {
         let old = std::mem::replace(&mut replica.doc, doc);
+        // The old document's signatures are of its changes.
+        replica.signatures = Default::default();
         replica.epoch = epoch;
         replica.epoch_seq += 1;
         // Publishes the epoch with the heads (`Replica::stamps`), under the same lock,
diff --git a/src/state/mod.rs b/src/state/mod.rs
index 671aff7..ef1559d 100644
--- a/src/state/mod.rs
+++ b/src/state/mod.rs
@@ -38,6 +38,7 @@ use tracing::{debug, error, warn};
 
 use crate::document::lock::DocumentLock;
 use crate::document::replica::{Epoch, Stamp};
+use crate::document::signatures::Sign;
 use crate::document::store::{ChangeSet, StoreError};
 use crate::document::{Document, Transaction};
 use crate::locks::{MutexExt, RwLockExt};
@@ -143,7 +144,8 @@ pub(crate) struct AppState {
     pub(crate) protocol_writers: Arc<std::collections::HashSet<String>>,
     /// The swarm's first users, recorded by a genesis node (`NodeConfig::first_users`).
     pub(crate) first_users: Arc<crate::access::registry::FirstUsers>,
-    /// Signs the tokens this node issues (`NodeConfig::node_key`).
+    /// Signs the tokens this node issues and the changes it commits
+    /// (`NodeConfig::node_key`).
     pub(crate) node_key: Option<Arc<crate::identity::NodeKey>>,
     pub(crate) token_lifetime: Duration,
     pub(crate) session_lifetime: Duration,
@@ -452,7 +454,7 @@ impl AppState {
     /// cancelled request can't leave a committed write unannounced. While a rejoin runs,
     /// the write goes into the document before it (`StaleView`), replayed when the
     /// rejoin ends; on a node that keeps none, it is refused (`StoreError::Rejoining`,
-    /// `f` not called).
+    /// `f` not called). Protocol data: the change is signed (`document::signatures`).
     pub(crate) async fn mutate_doc<T, E>(
         &self,
         f: impl FnOnce(&mut Transaction<'_>) -> Result<T, E> + Send + 'static,
@@ -461,15 +463,19 @@ impl AppState {
         T: Send + 'static,
         E: From<StoreError> + Send + 'static,
     {
-        self.mutate_doc_for(None, f).await.map(|(out, _)| out)
+        self.mutate_doc_for(None, Sign::Protocol, f)
+            .await
+            .map(|(out, _)| out)
     }
 
     /// [`mutate_doc`](Self::mutate_doc) for `user`, who wrote through the API: the
-    /// change names them (`replica::Writer`). With the heads of the document written to
-    /// after the write (sorted): what a read must have to include it.
+    /// change names them (`replica::Writer`), and is signed as `sign` says, with this
+    /// node's key. With the heads of the document written to after the
+    /// write (sorted): what a read must have to include it.
     pub(crate) async fn mutate_doc_for<T, E>(
         &self,
         user: Option<String>,
+        sign: Sign,
         f: impl FnOnce(&mut Transaction<'_>) -> Result<T, E> + Send + 'static,
     ) -> Result<(T, Vec<crate::document::ChangeHash>), E>
     where
@@ -511,7 +517,21 @@ impl AppState {
                     node: state.local_id(),
                     user: user.as_deref(),
                 };
+                let before = replica.doc.get_heads();
                 let result = replica.transact(state.clock.now_millis(), &writer, f);
+                if result.is_ok()
+                    && let Some(key) = &state.node_key
+                {
+                    // The change made, if any: the one head after it, as it builds on
+                    // every head before.
+                    let after = replica.doc.get_heads();
+                    if after != before
+                        && let [hash] = after[..]
+                        && sign.wanted(&replica.doc)
+                    {
+                        replica.signatures.sign(hash, key);
+                    }
+                }
                 replica.refresh_heads();
                 result.map(|out| (out, replica.heads().to_vec()))
             }; // lock released before notifying