1use std::collections::{BTreeMap, BTreeSet};
2
3use anyhow::{Context, Result, anyhow};
4use ed25519_dalek::{Signature, Signer, SigningKey, VerifyingKey};
5use rusqlite::{Connection, OptionalExtension, params};
6use serde::{Deserialize, Serialize};
7use sha2::{Digest, Sha256};
8
9use super::hex;
10use super::identity::IdentityTag;
11use super::record::{put_len, put_str};
12use crate::sqlite_store::SqliteStore;
13
14const REVOCATION_DOMAIN: &[u8] = b"second-brain device revocation v1";
15const REVOCATION_ID_DOMAIN: &[u8] = b"second-brain device revocation id v1";
16const FRAME_FLOOR_PREFIX: &str = "frame_floor:";
17
18#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
23pub struct Revocation {
24 pub identity_tag: String,
25 pub revoker: String,
26 pub target: String,
27 pub keep: BTreeSet<String>,
28 pub created_at_micros: i64,
29}
30
31#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
32pub struct SignedRevocation {
33 pub revocation: Revocation,
34 #[serde(with = "super::record::hex_array")]
35 pub signature: [u8; 64],
36}
37
38impl Revocation {
39 pub fn signing_bytes(&self) -> Vec<u8> {
40 let mut out = Vec::with_capacity(128);
41 out.extend_from_slice(REVOCATION_DOMAIN);
42 put_str(&mut out, &self.identity_tag);
43 put_str(&mut out, &self.revoker);
44 put_str(&mut out, &self.target);
45 put_len(&mut out, self.keep.len());
46 for id in &self.keep {
47 put_str(&mut out, id);
48 }
49 out.extend_from_slice(&self.created_at_micros.to_be_bytes());
50 out
51 }
52
53 pub fn sign(self, key: &SigningKey) -> SignedRevocation {
54 let signature: Signature = key.sign(&self.signing_bytes());
55 SignedRevocation {
56 revocation: self,
57 signature: signature.to_bytes(),
58 }
59 }
60}
61
62impl SignedRevocation {
63 pub fn id(&self) -> String {
66 let digest = Sha256::new()
67 .chain_update(REVOCATION_ID_DOMAIN)
68 .chain_update(self.revocation.signing_bytes())
69 .finalize();
70 hex(&digest[..16])
71 }
72
73 pub fn verify(&self, revoker_key: &VerifyingKey) -> Result<()> {
74 revoker_key
75 .verify_strict(
76 &self.revocation.signing_bytes(),
77 &Signature::from_bytes(&self.signature),
78 )
79 .map_err(|_| {
80 anyhow!(
81 "the revocation of {} by {} does not verify under the revoker's key",
82 self.revocation.target,
83 self.revocation.revoker
84 )
85 })
86 }
87}
88
89#[derive(Serialize, Deserialize, Clone, Debug, Default, PartialEq, Eq)]
92pub struct EpochCause {
93 #[serde(default)]
94 pub revocations: BTreeSet<String>,
95 #[serde(default, skip_serializing_if = "BTreeSet::is_empty")]
96 pub retirements: BTreeSet<String>,
97}
98
99impl EpochCause {
100 pub fn is_empty(&self) -> bool {
101 self.revocations.is_empty() && self.retirements.is_empty()
102 }
103
104 pub fn to_json(&self) -> Result<String> {
105 serde_json::to_string(self).context("encoding an epoch cause")
106 }
107
108 pub fn from_stored(cause: Option<&str>) -> Result<Self> {
110 match cause {
111 None => Ok(Self::default()),
112 Some(text) => serde_json::from_str(text).context("decoding an epoch cause"),
113 }
114 }
115}
116
117pub fn revoked_by(
120 first_signers: &BTreeMap<String, BTreeSet<String>>,
121 revocations: &[&Revocation],
122) -> BTreeSet<String> {
123 let mut all = BTreeSet::new();
124 for revocation in revocations {
125 let mut reached = BTreeSet::from([revocation.target.clone()]);
126 loop {
127 let before = reached.len();
128 for (id, signers) in first_signers {
129 if !reached.contains(id)
130 && !revocation.keep.contains(id)
131 && signers.iter().any(|signer| reached.contains(signer))
132 {
133 reached.insert(id.clone());
134 }
135 }
136 if reached.len() == before {
137 break;
138 }
139 }
140 all.extend(reached);
141 }
142 all
143}
144
145impl SqliteStore {
146 pub fn put_revocation(
152 &self,
153 signed: &SignedRevocation,
154 revoker_key: &VerifyingKey,
155 ) -> Result<bool> {
156 signed.verify(revoker_key)?;
157 let id = signed.id();
158 let target = &signed.revocation.target;
159 self.with_txn(|tx| {
160 let stored: Option<Option<String>> = tx
161 .query_row(
162 "SELECT revocation FROM machines WHERE id = ?1",
163 params![target],
164 |r| r.get(0),
165 )
166 .optional()?;
167 let mut held = parse_revocations(stored.flatten().as_deref())?;
168 if held.iter().any(|r| r.id() == id) {
169 return Ok(false);
170 }
171 held.push(signed.clone());
172 held.sort_by_key(SignedRevocation::id);
173 tx.execute(
174 "INSERT INTO machines (id, revocation) VALUES (?1, ?2) \
175 ON CONFLICT(id) DO UPDATE SET revocation = excluded.revocation",
176 params![target, serde_json::to_string(&held)?],
177 )?;
178 Ok(true)
179 })
180 }
181
182 pub fn revocations(&self, tag: &IdentityTag) -> Result<Vec<SignedRevocation>> {
183 let conn = self.reader();
184 let mut stmt =
185 conn.prepare("SELECT revocation FROM machines WHERE revocation IS NOT NULL")?;
186 let rows = stmt.query_map([], |r| r.get::<_, String>(0))?;
187 let mut held = Vec::new();
188 for text in rows {
189 held.extend(
190 parse_revocations(Some(&text?))?
191 .into_iter()
192 .filter(|r| r.revocation.identity_tag == tag.as_str()),
193 );
194 }
195 held.sort_by_key(SignedRevocation::id);
196 Ok(held)
197 }
198
199 pub fn revoked_by_rule(
202 &self,
203 tag: &IdentityTag,
204 extra: Option<&Revocation>,
205 ) -> Result<BTreeSet<String>> {
206 let first_signers = self.first_signers(tag)?;
207 let stored = self.revocations(tag)?;
208 let mut rules: Vec<&Revocation> = stored.iter().map(|s| &s.revocation).collect();
209 rules.extend(extra);
210 Ok(revoked_by(&first_signers, &rules))
211 }
212
213 pub fn revokers_of(&self, tag: &IdentityTag, machine_id: &str) -> Result<BTreeSet<String>> {
216 let first_signers = self.first_signers(tag)?;
217 Ok(self
218 .revocations(tag)?
219 .into_iter()
220 .filter(|s| revoked_by(&first_signers, &[&s.revocation]).contains(machine_id))
221 .map(|s| s.revocation.revoker)
222 .collect())
223 }
224
225 fn first_signers(&self, tag: &IdentityTag) -> Result<BTreeMap<String, BTreeSet<String>>> {
226 Ok(self
227 .device_records()?
228 .into_iter()
229 .filter(|row| row.first.record.identity_tag == tag.as_str())
230 .map(|row| {
231 let id = row.first.record.machine_id;
232 let signers = row
233 .first
234 .signatures
235 .into_iter()
236 .map(|s| s.signer)
237 .filter(|signer| *signer != id)
238 .collect();
239 (id, signers)
240 })
241 .collect())
242 }
243
244 pub fn apply_revocations(&self, tag: &IdentityTag) -> Result<Vec<String>> {
248 let reached = self.revoked_by_rule(tag, None)?;
249 self.with_txn(|tx| {
250 let mut newly = Vec::new();
251 for id in reached {
252 for table in ["peer_acks", "peer_pins"] {
253 tx.execute(
254 &format!("DELETE FROM {table} WHERE peer_id = ?1"),
255 params![id],
256 )?;
257 }
258 let marked = tx.execute(
259 "UPDATE machines SET revoked = 1 WHERE id = ?1 AND revoked = 0",
260 params![id],
261 )?;
262 if marked > 0 {
263 newly.push(id);
264 }
265 }
266 Ok(newly)
267 })
268 }
269
270 pub fn frame_floor(&self, tag: &IdentityTag, peer: &str) -> Result<Option<u32>> {
272 read_frame_floor(&self.reader(), &frame_floor_key(tag, peer))
273 }
274
275 pub fn raise_frame_floor(&self, tag: &IdentityTag, peer: &str, number: u32) -> Result<bool> {
278 let key = frame_floor_key(tag, peer);
279 self.with_txn(|tx| {
280 if read_frame_floor(tx, &key)?.is_some_and(|floor| floor >= number) {
281 return Ok(false);
282 }
283 tx.execute(
284 "INSERT OR REPLACE INTO index_meta (key, value) VALUES (?1, ?2)",
285 params![key, number.to_string()],
286 )?;
287 Ok(true)
288 })
289 }
290}
291
292fn parse_revocations(text: Option<&str>) -> Result<Vec<SignedRevocation>> {
293 match text {
294 None => Ok(Vec::new()),
295 Some(text) => serde_json::from_str(text).context("decoding a stored revocation"),
296 }
297}
298
299fn frame_floor_key(tag: &IdentityTag, peer: &str) -> String {
300 format!("{FRAME_FLOOR_PREFIX}{}:{peer}", tag.as_str())
301}
302
303fn read_frame_floor(conn: &Connection, key: &str) -> Result<Option<u32>> {
304 let value: Option<String> = conn
305 .query_row(
306 "SELECT value FROM index_meta WHERE key = ?1",
307 params![key],
308 |r| r.get(0),
309 )
310 .optional()?;
311 value
312 .map(|v| v.parse().with_context(|| format!("stored {key} is {v:?}")))
313 .transpose()
314}
315
316#[cfg(test)]
317mod tests {
318 use super::*;
319 use crate::keys::record::DeviceRecord;
320
321 const TAG: &str = "f-tag";
322
323 fn key(seed: u8) -> SigningKey {
324 SigningKey::from_bytes(&[seed; 32])
325 }
326
327 fn revocation(revoker: &str, target: &str, keep: &[&str]) -> Revocation {
328 Revocation {
329 identity_tag: TAG.to_string(),
330 revoker: revoker.to_string(),
331 target: target.to_string(),
332 keep: keep.iter().map(|s| s.to_string()).collect(),
333 created_at_micros: 1_000,
334 }
335 }
336
337 fn signers(entries: &[(&str, &[&str])]) -> BTreeMap<String, BTreeSet<String>> {
338 entries
339 .iter()
340 .map(|(id, by)| (id.to_string(), by.iter().map(|s| s.to_string()).collect()))
341 .collect()
342 }
343
344 fn ids(set: &BTreeSet<String>) -> Vec<&str> {
345 set.iter().map(String::as_str).collect()
346 }
347
348 #[test]
349 fn a_signed_revocation_verifies_and_tampering_any_field_breaks_it() {
350 let revoker = key(1);
351 let signed = revocation("a", "c", &["b"]).sign(&revoker);
352 signed.verify(&revoker.verifying_key()).unwrap();
353 assert!(signed.verify(&key(2).verifying_key()).is_err());
354
355 let cases: [(&str, fn(&mut Revocation)); 6] = [
356 ("identity", |r| r.identity_tag = "f-other".into()),
357 ("revoker", |r| r.revoker = "b".into()),
358 ("target", |r| r.target = "b".into()),
359 ("keep added", |r| {
360 r.keep.insert("d".into());
361 }),
362 ("keep removed", |r| r.keep.clear()),
363 ("time", |r| r.created_at_micros += 1),
364 ];
365 for (field, tamper) in cases {
366 let mut edited = signed.clone();
367 tamper(&mut edited.revocation);
368 assert!(
369 edited.verify(&revoker.verifying_key()).is_err(),
370 "tampered {field} still verifies"
371 );
372 assert_ne!(edited.id(), signed.id(), "tampered {field} keeps the id");
373 }
374 }
375
376 #[test]
377 fn signed_revocations_round_trip_through_json() {
378 let signed = revocation("a", "c", &["b", "d"]).sign(&key(1));
379 let text = serde_json::to_string(&signed).unwrap();
380 let back: SignedRevocation = serde_json::from_str(&text).unwrap();
381 assert_eq!(back, signed);
382 assert_eq!(back.id(), signed.id());
383 back.verify(&key(1).verifying_key()).unwrap();
384 }
385
386 #[test]
387 fn the_rule_reaches_the_target_and_what_it_signed_transitively_except_kept_ids() {
388 let lineage = signers(&[
389 ("a", &[]),
390 ("b", &["a"]),
391 ("c", &["b"]),
392 ("d", &["c"]),
393 ("e", &["a"]),
394 ("f", &["b"]),
395 ("g", &["b", "e"]),
396 ("h", &["c", "f"]),
397 ]);
398 let cases: [(&str, Revocation, &[&str]); 7] = [
399 ("leaf", revocation("a", "d", &[]), &["d"]),
400 (
401 "transitive",
402 revocation("a", "b", &[]),
403 &["b", "c", "d", "f", "g", "h"],
404 ),
405 (
406 "a kept device stops the descent through it",
407 revocation("a", "b", &["c", "f"]),
408 &["b", "g"],
409 ),
410 (
411 "a device below a kept one is still reached by another path",
412 revocation("a", "b", &["c"]),
413 &["b", "f", "g", "h"],
414 ),
415 (
416 "the target is revoked even when kept",
417 revocation("a", "d", &["d"]),
418 &["d"],
419 ),
420 ("unknown target", revocation("a", "x", &[]), &["x"]),
421 (
422 "the founder reaches everything not kept",
423 revocation("b", "a", &["b"]),
424 &["a", "e", "g"],
425 ),
426 ];
427 for (name, rule, expected) in cases {
428 assert_eq!(
429 ids(&revoked_by(&lineage, &[&rule])),
430 expected.to_vec(),
431 "{name}"
432 );
433 }
434 }
435
436 #[test]
437 fn revocations_apply_as_a_union_whatever_revoked_their_revoker() {
438 let lineage = signers(&[("a", &[]), ("b", &["a"]), ("c", &["a"]), ("t", &["a"])]);
439 let thief = revocation("t", "a", &["t", "b", "c"]);
440 let owner = revocation("a", "t", &["a"]);
441 for order in [[&thief, &owner], [&owner, &thief]] {
442 assert_eq!(ids(&revoked_by(&lineage, &order)), ["a", "t"]);
443 }
444 }
445
446 fn row(id: &str, own: &SigningKey) -> DeviceRecord {
447 DeviceRecord {
448 machine_id: id.to_string(),
449 identity_tag: TAG.to_string(),
450 version: 1,
451 name: format!("{id}-name"),
452 age_recipient: "age1recipient".to_string(),
453 ssh_public_key: "ssh-ed25519 AAAA".to_string(),
454 signing_public_key: own.verifying_key().to_bytes(),
455 recovery_fingerprints: Vec::new(),
456 ssh_login: None,
457 ssh_port: None,
458 ssh_host_key: None,
459 }
460 }
461
462 fn store_with_chain() -> SqliteStore {
463 let store = SqliteStore::in_memory("a".to_string()).unwrap();
464 let (a, b, c) = (key(1), key(2), key(3));
465 store
466 .insert_first_device_record(&row("a", &a).sign("a", &a), "a", &a.verifying_key())
467 .unwrap();
468 store
469 .insert_first_device_record(&row("b", &b).sign("a", &a), "a", &a.verifying_key())
470 .unwrap();
471 store
472 .insert_first_device_record(&row("c", &c).sign("b", &b), "b", &b.verifying_key())
473 .unwrap();
474 store
475 }
476
477 fn revoked(store: &SqliteStore) -> Vec<String> {
478 store
479 .device_records()
480 .unwrap()
481 .into_iter()
482 .filter(|r| r.revoked)
483 .map(|r| r.current.record.machine_id)
484 .collect()
485 }
486
487 #[test]
488 fn a_stored_revocation_marks_its_reach_once_and_stays() {
489 let store = store_with_chain();
490 let tag = IdentityTag::from(TAG.to_string());
491 let signed = revocation("a", "b", &["a"]).sign(&key(1));
492 assert!(
493 store
494 .put_revocation(&signed, &key(9).verifying_key())
495 .is_err()
496 );
497 assert!(store.revocations(&tag).unwrap().is_empty());
498
499 assert!(
500 store
501 .put_revocation(&signed, &key(1).verifying_key())
502 .unwrap()
503 );
504 assert!(
505 !store
506 .put_revocation(&signed, &key(1).verifying_key())
507 .unwrap()
508 );
509 assert_eq!(store.revocations(&tag).unwrap(), vec![signed.clone()]);
510 assert!(
511 store
512 .revocations(&IdentityTag::from("f-other".to_string()))
513 .unwrap()
514 .is_empty()
515 );
516
517 assert_eq!(store.apply_revocations(&tag).unwrap(), ["b", "c"]);
518 assert!(store.apply_revocations(&tag).unwrap().is_empty());
519 assert_eq!(revoked(&store), ["b", "c"]);
520 }
521
522 #[test]
523 fn a_device_learned_after_the_revocation_is_reached_by_it() {
524 let store = store_with_chain();
525 let tag = IdentityTag::from(TAG.to_string());
526 store
527 .put_revocation(
528 &revocation("a", "c", &["a"]).sign(&key(1)),
529 &key(1).verifying_key(),
530 )
531 .unwrap();
532 store.apply_revocations(&tag).unwrap();
533
534 let (c, d) = (key(3), key(4));
535 store
536 .insert_first_device_record(&row("d", &d).sign("c", &c), "c", &c.verifying_key())
537 .unwrap();
538 assert_eq!(store.apply_revocations(&tag).unwrap(), ["d"]);
539 assert_eq!(revoked(&store), ["c", "d"]);
540 }
541
542 #[test]
543 fn a_revocation_of_an_unseen_device_waits_on_a_bare_row() {
544 let store = store_with_chain();
545 let tag = IdentityTag::from(TAG.to_string());
546 let signed = revocation("a", "x", &["a"]).sign(&key(1));
547 store
548 .put_revocation(&signed, &key(1).verifying_key())
549 .unwrap();
550 assert_eq!(store.apply_revocations(&tag).unwrap(), ["x"]);
551 assert!(store.device_record("x").unwrap().is_none());
552 assert_eq!(store.revocations(&tag).unwrap(), vec![signed]);
553
554 let x = key(5);
555 store
556 .insert_first_device_record(
557 &row("x", &x).sign("a", &key(1)),
558 "a",
559 &key(1).verifying_key(),
560 )
561 .unwrap();
562 assert!(store.device_record("x").unwrap().unwrap().revoked);
563 }
564
565 #[test]
566 fn revoked_by_rule_previews_an_extra_revocation_without_storing_it() {
567 let store = store_with_chain();
568 let tag = IdentityTag::from(TAG.to_string());
569 let extra = revocation("a", "b", &["a"]);
570 assert_eq!(
571 ids(&store.revoked_by_rule(&tag, Some(&extra)).unwrap()),
572 ["b", "c"]
573 );
574 assert!(store.revoked_by_rule(&tag, None).unwrap().is_empty());
575 assert!(revoked(&store).is_empty());
576 }
577
578 #[test]
579 fn a_frame_floor_only_rises_and_belongs_to_one_identity() {
580 let store = SqliteStore::in_memory("a".to_string()).unwrap();
581 let tag = IdentityTag::from(TAG.to_string());
582 let other = IdentityTag::from("f-other".to_string());
583 assert_eq!(store.frame_floor(&tag, "b").unwrap(), None);
584 assert!(store.raise_frame_floor(&tag, "b", 3).unwrap());
585 assert!(!store.raise_frame_floor(&tag, "b", 2).unwrap());
586 assert!(!store.raise_frame_floor(&tag, "b", 3).unwrap());
587 assert_eq!(store.frame_floor(&tag, "b").unwrap(), Some(3));
588 assert_eq!(store.frame_floor(&tag, "c").unwrap(), None);
589 assert_eq!(store.frame_floor(&other, "b").unwrap(), None);
590 }
591
592 #[test]
593 fn revoked_devices_lose_their_log_floor_acks_and_pins() {
594 let store = store_with_chain();
595 let tag = IdentityTag::from(TAG.to_string());
596 for peer in ["b", "c"] {
597 store.record_peer_ack(peer, 5, 1).unwrap();
598 store.pin_peer(peer, 5).unwrap();
599 }
600 store
601 .put_revocation(
602 &revocation("a", "c", &["a"]).sign(&key(1)),
603 &key(1).verifying_key(),
604 )
605 .unwrap();
606 store.apply_revocations(&tag).unwrap();
607 let peers = |table: &str| -> Vec<String> {
608 let conn = store.reader();
609 let mut stmt = conn
610 .prepare(&format!("SELECT peer_id FROM {table} ORDER BY peer_id"))
611 .unwrap();
612 stmt.query_map([], |r| r.get(0))
613 .unwrap()
614 .map(Result::unwrap)
615 .collect()
616 };
617 assert_eq!(peers("peer_acks"), ["b"]);
618 assert_eq!(peers("peer_pins"), ["b"]);
619 }
620
621 #[test]
622 fn revokers_of_names_whose_rules_reach_a_device() {
623 let store = store_with_chain();
624 let tag = IdentityTag::from(TAG.to_string());
625 store
626 .put_revocation(
627 &revocation("a", "b", &["a"]).sign(&key(1)),
628 &key(1).verifying_key(),
629 )
630 .unwrap();
631 assert_eq!(ids(&store.revokers_of(&tag, "c").unwrap()), ["a"]);
632 assert!(store.revokers_of(&tag, "a").unwrap().is_empty());
633 }
634
635 #[test]
636 fn an_epoch_cause_round_trips_and_a_missing_one_is_empty() {
637 let cause = EpochCause {
638 revocations: ["r1".to_string(), "r2".to_string()].into(),
639 retirements: Default::default(),
640 };
641 let text = cause.to_json().unwrap();
642 assert_eq!(text, r#"{"revocations":["r1","r2"]}"#);
643 assert_eq!(EpochCause::from_stored(Some(&text)).unwrap(), cause);
644 let retired = EpochCause {
645 retirements: ["0123456789abcdef".to_string()].into(),
646 ..Default::default()
647 };
648 assert!(!retired.is_empty());
649 let text = retired.to_json().unwrap();
650 assert_eq!(EpochCause::from_stored(Some(&text)).unwrap(), retired);
651 assert!(EpochCause::from_stored(None).unwrap().is_empty());
652 assert!(EpochCause::from_stored(Some("{")).is_err());
653 }
654}