agent_mesh_protocol/
revocation.rs

1//! The **revocation log**: a user-signed, append-only chain of
2//! [`MerkleNode`]s naming revoked agents and generation bumps.
3//!
4//! Identity is the node's [`ContentId`]; each node is signed by the user named
5//! in the genesis entry, over `REVOCATION_DOMAIN || cid_bytes` — the same
6//! detached-signature shape as [`crate::Assertion`]. The JSON form of a
7//! [`RevocationLog`] is a container only: nothing in it is trusted until
8//! [`RevocationLog::verify`] recomputes every id and checks every signature.
9//! See `docs/decisions/revocation.md`.
10
11use std::collections::BTreeSet;
12
13use content_addressable::{ContentId, MerkleNode};
14use serde::{Deserialize, Serialize};
15
16use crate::agent_key::{CertChain, Issuer, SerdeSig};
17use crate::{Fingerprint, MeshError, Result, UserKey, UserPublic};
18
19/// Domain tag: a revocation signature can't be replayed as any other signature.
20const REVOCATION_DOMAIN: &[u8] = b"agent-mesh/revocation/v1\0";
21
22/// One entry of the log.
23#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
24pub enum RevocationEntry {
25    /// First node only: names the user whose key signs the whole log.
26    Genesis {
27        /// The log's owner.
28        user: UserPublic,
29    },
30    /// The agent with this key fingerprint is revoked, wherever it sits in a chain.
31    Revoke {
32        /// Fingerprint of the revoked agent's public key.
33        agent: Fingerprint,
34    },
35    /// The current generation moves to `current`; certs scoped to older ones lapse.
36    Generation {
37        /// The new generation. Must exceed every earlier one (0 before any bump).
38        current: u64,
39    },
40}
41
42/// A log node and its detached signature (beside the node, never inside it).
43#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
44pub struct SignedEntry {
45    node: MerkleNode<RevocationEntry>,
46    sig: SerdeSig,
47}
48
49/// The ordered, signed nodes of one user's revocation log.
50#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
51pub struct RevocationLog {
52    entries: Vec<SignedEntry>,
53}
54
55/// What a verified log says: who owns it, where it ends, what is revoked.
56#[derive(Debug, Clone, PartialEq, Eq)]
57pub struct RevocationState {
58    /// Fingerprint of the user that signed the log.
59    pub user: Fingerprint,
60    /// Id of the last node.
61    pub head: ContentId,
62    /// Number of nodes, genesis included.
63    pub len: u64,
64    /// Current generation (0 before any bump).
65    pub generation: u64,
66    /// Fingerprints of revoked agents.
67    pub revoked: BTreeSet<Fingerprint>,
68}
69
70/// The head a consumer last saw and persisted, for rollback/fork detection.
71#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
72pub struct Seen {
73    /// Fingerprint of the log's user.
74    pub user: Fingerprint,
75    /// Number of nodes seen.
76    pub len: u64,
77    /// Id of the last node seen.
78    pub head: ContentId,
79}
80
81fn bad(msg: &str) -> MeshError {
82    MeshError::RevocationState(msg.into())
83}
84
85fn message(cid: &ContentId) -> Vec<u8> {
86    let mut m = REVOCATION_DOMAIN.to_vec();
87    m.extend_from_slice(&cid.to_bytes());
88    m
89}
90
91fn sign_node(user: &UserKey, node: MerkleNode<RevocationEntry>) -> Result<SignedEntry> {
92    let id = node.id().map_err(|e| MeshError::Encoding(e.to_string()))?;
93    Ok(SignedEntry {
94        node,
95        sig: SerdeSig(user.sign(&message(&id))),
96    })
97}
98
99impl RevocationState {
100    /// The [`Seen`] record a consumer should persist after accepting this state.
101    #[must_use]
102    pub fn seen(&self) -> Seen {
103        Seen {
104            user: self.user,
105            len: self.len,
106            head: self.head,
107        }
108    }
109}
110
111impl RevocationLog {
112    /// A new log owned by `user`: just the signed genesis node.
113    ///
114    /// # Errors
115    /// [`MeshError::Encoding`] if the node cannot be encoded.
116    pub fn genesis(user: &UserKey) -> Result<Self> {
117        let node = MerkleNode::genesis(RevocationEntry::Genesis {
118            user: user.public(),
119        });
120        Ok(Self {
121            entries: vec![sign_node(user, node)?],
122        })
123    }
124
125    /// Append `entry`, signed by `user`, parented on the current head.
126    ///
127    /// # Errors
128    /// [`MeshError::RevocationState`] if `user` does not own this log, the log
129    /// is not valid, `entry` is a `Genesis`, or a `Generation` does not exceed
130    /// the current one. Nothing is appended on error.
131    pub fn append(&mut self, user: &UserKey, entry: RevocationEntry) -> Result<()> {
132        let state = self.verify()?;
133        if user.fingerprint() != state.user {
134            return Err(bad("appending key is not the log's user"));
135        }
136        match &entry {
137            RevocationEntry::Genesis { .. } => return Err(bad("genesis only starts a log")),
138            RevocationEntry::Generation { current } if *current <= state.generation => {
139                return Err(bad("generation must strictly increase"))
140            }
141            _ => {}
142        }
143        self.entries
144            .push(sign_node(user, MerkleNode::new(entry, [state.head]))?);
145        Ok(())
146    }
147
148    /// Check the whole log and fold it into a [`RevocationState`].
149    ///
150    /// Fail-closed: genesis first, each parent is the previous id, every
151    /// signature verifies under the genesis user, generations strictly increase.
152    ///
153    /// # Errors
154    /// [`MeshError::RevocationState`] for a structural break;
155    /// [`MeshError::BadSignature`] for a signature that does not verify.
156    pub fn verify(&self) -> Result<RevocationState> {
157        let first = self.entries.first().ok_or_else(|| bad("missing genesis"))?;
158        let RevocationEntry::Genesis { user } = first.node.payload() else {
159            return Err(bad("first node is not a genesis"));
160        };
161        let mut state = RevocationState {
162            user: user.fingerprint(),
163            head: Self::check_link(user, first, None)?,
164            len: 1,
165            generation: 0,
166            revoked: BTreeSet::new(),
167        };
168        for e in &self.entries[1..] {
169            state.head = Self::check_link(user, e, Some(state.head))?;
170            state.len += 1;
171            match e.node.payload() {
172                RevocationEntry::Genesis { .. } => return Err(bad("second genesis")),
173                RevocationEntry::Revoke { agent } => {
174                    state.revoked.insert(*agent);
175                }
176                RevocationEntry::Generation { current } => {
177                    if *current <= state.generation {
178                        return Err(bad("generation does not increase"));
179                    }
180                    state.generation = *current;
181                }
182            }
183        }
184        Ok(state)
185    }
186
187    /// One node: parents are exactly `{prev}` (none for genesis), signature good.
188    /// Returns the node's recomputed id.
189    fn check_link(
190        user: &UserPublic,
191        e: &SignedEntry,
192        prev: Option<ContentId>,
193    ) -> Result<ContentId> {
194        if !e.node.parents().iter().copied().eq(prev) {
195            return Err(bad("broken parent link"));
196        }
197        let id = e
198            .node
199            .id()
200            .map_err(|err| MeshError::Encoding(err.to_string()))?;
201        user.verify(&message(&id), &e.sig.0)?;
202        Ok(id)
203    }
204
205    /// Refuse a log that is shorter than what the consumer `seen`, or whose
206    /// node at that position is not the head they saw (a fork). A log that is
207    /// itself invalid, or belongs to another user, is refused too.
208    ///
209    /// # Errors
210    /// [`MeshError::RevocationState`] on rollback, fork, wrong user, or empty `seen`.
211    pub fn extends(&self, seen: &Seen) -> Result<()> {
212        let state = self.verify()?;
213        if state.user != seen.user {
214            return Err(bad("log belongs to a different user"));
215        }
216        if seen.len == 0 || state.len < seen.len {
217            return Err(bad("log is shorter than what was seen (rollback)"));
218        }
219        let at = &self.entries[usize::try_from(seen.len - 1).map_err(|_| bad("seen too long"))?];
220        let id = at
221            .node
222            .id()
223            .map_err(|e| MeshError::Encoding(e.to_string()))?;
224        if id != seen.head {
225            return Err(bad("log forks from what was seen"));
226        }
227        Ok(())
228    }
229}
230
231impl CertChain {
232    /// Verify the chain, then check it against `state`: same user, **no link**
233    /// (leaf or any delegating parent) revoked, and every link valid at
234    /// `state.generation`. A chain scoped `Scope::All` ignores a generation
235    /// bump; revoke such an agent per agent.
236    ///
237    /// # Errors
238    /// [`MeshError::RevocationState`] for a different user;
239    /// [`MeshError::Revoked`] if any link is revoked; otherwise whatever
240    /// [`CertChain::verify_at`] returns.
241    pub fn verify_with(&self, state: &RevocationState) -> Result<()> {
242        if self.user_fingerprint() != state.user {
243            return Err(bad("chain belongs to a different user"));
244        }
245        let mut link = self;
246        loop {
247            let agent = link.agent_fingerprint();
248            if state.revoked.contains(&agent) {
249                return Err(MeshError::Revoked { agent });
250            }
251            match &link.issuer {
252                Issuer::User(_) => break,
253                Issuer::Agent { parent, .. } => link = parent,
254            }
255        }
256        self.verify_at(state.generation)
257    }
258}
259
260#[cfg(test)]
261mod tests {
262    use super::*;
263    use crate::{AgentKey, AgentMetadata, Caveats, Scope};
264
265    fn meta(caveats: Caveats) -> AgentMetadata {
266        AgentMetadata {
267            role: "r".into(),
268            host: "h".into(),
269            capabilities: vec![],
270            issued_at: "2026-10-26T00:00:00Z".into(),
271            expires_at: None,
272            caveats,
273        }
274    }
275
276    fn scoped(gen: u64) -> Caveats {
277        let mut c = Caveats::top();
278        c.valid_for_generation = Scope::Only([gen].into());
279        c
280    }
281
282    fn revoke(user: &UserKey, log: &mut RevocationLog, k: &AgentKey) {
283        let agent = k.fingerprint();
284        log.append(user, RevocationEntry::Revoke { agent }).unwrap();
285    }
286
287    fn is_state_err(r: Result<impl std::fmt::Debug>) -> bool {
288        matches!(r, Err(MeshError::RevocationState(_)))
289    }
290
291    #[test]
292    fn fresh_log_verifies_and_accepts_chain() {
293        let user = UserKey::generate();
294        let log = RevocationLog::genesis(&user).unwrap();
295        let st = log.verify().unwrap();
296        assert_eq!((st.len, st.generation), (1, 0));
297        let a = AgentKey::issue(&user, meta(Caveats::top()));
298        a.cert().verify_with(&st).unwrap();
299    }
300
301    #[test]
302    fn revoked_leaf_refused() {
303        let user = UserKey::generate();
304        let a = AgentKey::issue(&user, meta(Caveats::top()));
305        let mut log = RevocationLog::genesis(&user).unwrap();
306        revoke(&user, &mut log, &a);
307        let err = a.cert().verify_with(&log.verify().unwrap()).unwrap_err();
308        assert!(matches!(err, MeshError::Revoked { agent } if agent == a.fingerprint()));
309    }
310
311    #[test]
312    fn revoked_parent_refuses_delegated_child() {
313        let user = UserKey::generate();
314        let parent = AgentKey::issue(&user, meta(Caveats::top()));
315        let child = parent.delegate(meta(Caveats::top())).unwrap();
316        let mut log = RevocationLog::genesis(&user).unwrap();
317        revoke(&user, &mut log, &parent);
318        let err = child
319            .cert()
320            .verify_with(&log.verify().unwrap())
321            .unwrap_err();
322        assert!(matches!(err, MeshError::Revoked { agent } if agent == parent.fingerprint()));
323    }
324
325    #[test]
326    fn generation_bump_refuses_old_scope_but_not_all() {
327        let user = UserKey::generate();
328        let old = AgentKey::issue(&user, meta(scoped(0)));
329        let all = AgentKey::issue(&user, meta(Caveats::top()));
330        let mut log = RevocationLog::genesis(&user).unwrap();
331        log.append(&user, RevocationEntry::Generation { current: 1 })
332            .unwrap();
333        let st = log.verify().unwrap();
334        assert!(matches!(
335            old.cert().verify_with(&st),
336            Err(MeshError::Generation(_))
337        ));
338        all.cert().verify_with(&st).unwrap();
339        AgentKey::issue(&user, meta(scoped(1)))
340            .cert()
341            .verify_with(&st)
342            .unwrap();
343    }
344
345    #[test]
346    fn chain_of_another_user_refused() {
347        let user = UserKey::generate();
348        let a = AgentKey::issue(&UserKey::generate(), meta(Caveats::top()));
349        let st = RevocationLog::genesis(&user).unwrap().verify().unwrap();
350        assert!(is_state_err(a.cert().verify_with(&st)));
351    }
352
353    #[test]
354    fn log_signed_by_different_user_refused() {
355        let user = UserKey::generate();
356        let mut log = RevocationLog::genesis(&user).unwrap();
357        let other = UserKey::generate();
358        assert!(is_state_err(
359            log.append(&other, RevocationEntry::Generation { current: 1 })
360        ));
361        // forged: node signed by someone else under the genesis user's name
362        let node = MerkleNode::new(
363            RevocationEntry::Generation { current: 1 },
364            [log.verify().unwrap().head],
365        );
366        log.entries.push(sign_node(&other, node).unwrap());
367        assert!(matches!(log.verify(), Err(MeshError::BadSignature)));
368    }
369
370    #[test]
371    fn tampered_node_refused() {
372        let user = UserKey::generate();
373        let a = AgentKey::issue(&user, meta(Caveats::top()));
374        let mut log = RevocationLog::genesis(&user).unwrap();
375        revoke(&user, &mut log, &a);
376        let b = AgentKey::issue(&user, meta(Caveats::top()));
377        log.entries[1].node.payload = RevocationEntry::Revoke {
378            agent: b.fingerprint(),
379        };
380        assert!(matches!(log.verify(), Err(MeshError::BadSignature)));
381    }
382
383    #[test]
384    fn reordered_log_refused() {
385        let user = UserKey::generate();
386        let mut log = RevocationLog::genesis(&user).unwrap();
387        for g in 1..=2 {
388            log.append(&user, RevocationEntry::Generation { current: g })
389                .unwrap();
390        }
391        log.entries.swap(1, 2);
392        assert!(is_state_err(log.verify()));
393    }
394
395    #[test]
396    fn non_increasing_generation_refused() {
397        let user = UserKey::generate();
398        let mut log = RevocationLog::genesis(&user).unwrap();
399        log.append(&user, RevocationEntry::Generation { current: 2 })
400            .unwrap();
401        assert!(is_state_err(
402            log.append(&user, RevocationEntry::Generation { current: 2 })
403        ));
404        // properly parented and signed, but not increasing
405        let node = MerkleNode::new(
406            RevocationEntry::Generation { current: 1 },
407            [log.verify().unwrap().head],
408        );
409        log.entries.push(sign_node(&user, node).unwrap());
410        assert!(is_state_err(log.verify()));
411    }
412
413    #[test]
414    fn missing_genesis_refused() {
415        let user = UserKey::generate();
416        assert!(is_state_err(RevocationLog { entries: vec![] }.verify()));
417        let mut log = RevocationLog::genesis(&user).unwrap();
418        log.append(&user, RevocationEntry::Generation { current: 1 })
419            .unwrap();
420        log.entries.remove(0);
421        assert!(is_state_err(log.verify()));
422    }
423
424    #[test]
425    fn extends_refuses_shorter_and_forked_accepts_extension() {
426        let user = UserKey::generate();
427        let mut log = RevocationLog::genesis(&user).unwrap();
428        let base = log.clone();
429        log.append(&user, RevocationEntry::Generation { current: 1 })
430            .unwrap();
431        let seen = log.verify().unwrap().seen();
432        assert!(is_state_err(base.extends(&seen)));
433        let mut fork = base.clone();
434        fork.append(&user, RevocationEntry::Generation { current: 7 })
435            .unwrap();
436        assert!(is_state_err(fork.extends(&seen)));
437        let mut longer = log.clone();
438        longer
439            .append(&user, RevocationEntry::Generation { current: 2 })
440            .unwrap();
441        longer.extends(&seen).unwrap();
442        log.extends(&seen).unwrap();
443    }
444
445    #[test]
446    fn extends_refuses_other_user_and_json_roundtrips() {
447        let user = UserKey::generate();
448        let mut log = RevocationLog::genesis(&user).unwrap();
449        log.append(&user, RevocationEntry::Generation { current: 1 })
450            .unwrap();
451        let mut seen = log.verify().unwrap().seen();
452        let back: RevocationLog =
453            serde_json::from_str(&serde_json::to_string(&log).unwrap()).unwrap();
454        assert_eq!(back, log);
455        back.verify().unwrap();
456        seen.user = UserKey::generate().fingerprint();
457        assert!(is_state_err(log.extends(&seen)));
458    }
459
460    /// Domain separation: a node signed over bare CID bytes, or under the
461    /// Assertion domain, must not verify. Domains are spelled out here, not
462    /// taken from `message()`, so removing the tag there fails this test.
463    #[test]
464    fn signature_without_the_revocation_domain_is_refused() {
465        let user = UserKey::generate();
466        let base = RevocationLog::genesis(&user).unwrap();
467        let head = base.verify().unwrap().head;
468        let node = MerkleNode::new(RevocationEntry::Generation { current: 1 }, [head]);
469        let cid = node.id().unwrap().to_bytes();
470        let assertion = [b"agent-mesh/provenance/assertion/v1\0".as_slice(), &cid].concat();
471        for msg in [cid.clone(), assertion] {
472            let mut log = base.clone();
473            log.entries.push(SignedEntry {
474                node: node.clone(),
475                sig: SerdeSig(user.sign(&msg)),
476            });
477            assert!(matches!(log.verify(), Err(MeshError::BadSignature)));
478        }
479        // control: the right domain over the same node verifies
480        let good = [REVOCATION_DOMAIN, &cid].concat();
481        let mut log = base;
482        log.entries.push(SignedEntry {
483            node,
484            sig: SerdeSig(user.sign(&good)),
485        });
486        log.verify().unwrap();
487    }
488}
agent_mesh_protocol/revocation.rs

agent_mesh_protocol/
revocation.rs
