visibility.rs (21240B)
1 //! Deterministic current-visibility reduction over immutable event truth. 2 3 use std::collections::{BTreeMap, BTreeSet}; 4 5 use radroots_event::{ 6 EventId, SignedEvent, 7 envelope::event_head::{ 8 CurrentEventHead, EventHeadCandidateResult, EventHeadCoordinate, EventHeadDecision, 9 event_head_candidate_for_nip01_event, select_event_head, 10 }, 11 envelope::kind::KIND_DELETION_REQUEST, 12 id::Nip01Coordinate, 13 }; 14 use sha2::{Digest, Sha256}; 15 16 use super::{ 17 AdmissionStage, EventPosition, SourceGeneration, VisibilityDigest, VisibilitySnapshot, 18 }; 19 use crate::Error; 20 21 #[doc(hidden)] 22 pub struct VisibilityInput<'a> { 23 position: EventPosition, 24 event: &'a SignedEvent, 25 stage: AdmissionStage, 26 } 27 28 impl<'a> VisibilityInput<'a> { 29 #[doc(hidden)] 30 pub const fn new( 31 position: EventPosition, 32 event: &'a SignedEvent, 33 stage: AdmissionStage, 34 ) -> Self { 35 Self { 36 position, 37 event, 38 stage, 39 } 40 } 41 } 42 43 #[doc(hidden)] 44 pub struct VisibilityEvaluation { 45 snapshot: VisibilitySnapshot, 46 visible: BTreeSet<EventId>, 47 } 48 49 impl VisibilityEvaluation { 50 #[doc(hidden)] 51 pub fn is_visible(&self, event_id: &EventId) -> bool { 52 self.visible.contains(event_id) 53 } 54 55 #[doc(hidden)] 56 pub const fn snapshot(&self) -> &VisibilitySnapshot { 57 &self.snapshot 58 } 59 60 #[doc(hidden)] 61 pub fn into_snapshot(self) -> VisibilitySnapshot { 62 self.snapshot 63 } 64 } 65 66 #[derive(Clone)] 67 struct Candidate<'a> { 68 position: EventPosition, 69 event: &'a SignedEvent, 70 coordinate: Option<EventHeadCoordinate>, 71 ephemeral: bool, 72 } 73 74 struct DeletionRequest { 75 request_id: EventId, 76 author: [u8; 32], 77 created_at: u64, 78 event_targets: BTreeSet<EventId>, 79 address_targets: BTreeSet<Nip01Coordinate>, 80 } 81 82 #[doc(hidden)] 83 pub fn evaluate_visibility<'a>( 84 generation: SourceGeneration, 85 inputs: impl IntoIterator<Item = VisibilityInput<'a>>, 86 ) -> Result<VisibilityEvaluation, Error> { 87 let mut candidates = Vec::new(); 88 let mut deletion_requests = Vec::new(); 89 let mut heads = BTreeMap::<EventHeadCoordinate, CurrentEventHead>::new(); 90 91 for input in inputs { 92 if input.position.generation() != generation { 93 return Err(Error::CorruptStoredEvent); 94 } 95 if input.stage == AdmissionStage::Raw { 96 continue; 97 } 98 let envelope = input.event.envelope(); 99 if input.stage == AdmissionStage::Visible && envelope.kind_u32() == KIND_DELETION_REQUEST { 100 deletion_requests.push(parse_deletion_request(input.event)?); 101 } 102 let (coordinate, ephemeral) = match event_head_candidate_for_nip01_event(envelope) { 103 EventHeadCandidateResult::Candidate(candidate) => { 104 let coordinate = candidate.coordinate.clone(); 105 match select_event_head(candidate, heads.get(&coordinate)) { 106 EventHeadDecision::Applied(head) => { 107 heads.insert(coordinate.clone(), head); 108 } 109 EventHeadDecision::SkippedDuplicate 110 | EventHeadDecision::SkippedOlder 111 | EventHeadDecision::SkippedSameTimestampHigherEventId => {} 112 EventHeadDecision::CoordinateMismatch => { 113 return Err(Error::CorruptStoredEvent); 114 } 115 } 116 (Some(coordinate), false) 117 } 118 EventHeadCandidateResult::NotHeadSelected => (None, false), 119 EventHeadCandidateResult::NotPersisted => (None, true), 120 EventHeadCandidateResult::Malformed(_) => return Err(Error::CorruptStoredEvent), 121 }; 122 if input.stage != AdmissionStage::Visible { 123 continue; 124 } 125 candidates.push(Candidate { 126 position: input.position, 127 event: input.event, 128 coordinate, 129 ephemeral, 130 }); 131 } 132 133 candidates.sort_by_key(|candidate| candidate.position.sequence()); 134 deletion_requests.sort_by_key(|request| request.request_id); 135 136 let mut visible = BTreeSet::new(); 137 let mut suppressed = BTreeSet::new(); 138 let mut superseded = BTreeSet::new(); 139 for candidate in candidates { 140 let event_id = *candidate.event.id(); 141 if candidate.ephemeral { 142 suppressed.insert(event_id); 143 continue; 144 } 145 if candidate.coordinate.as_ref().is_some_and(|coordinate| { 146 heads 147 .get(coordinate) 148 .is_none_or(|head| head.event_id != event_id) 149 }) { 150 superseded.insert(event_id); 151 continue; 152 } 153 if is_suppressed(candidate.event, &deletion_requests) { 154 suppressed.insert(event_id); 155 } else { 156 visible.insert(event_id); 157 } 158 } 159 160 let current_heads = heads.into_values().collect::<Vec<_>>(); 161 let deletion_request_ids = deletion_requests 162 .iter() 163 .map(|request| request.request_id) 164 .collect::<Vec<_>>(); 165 let visible_event_ids = visible.iter().copied().collect::<Vec<_>>(); 166 let suppressed_event_ids = suppressed.into_iter().collect::<Vec<_>>(); 167 let superseded_event_ids = superseded.into_iter().collect::<Vec<_>>(); 168 let digest = visibility_digest( 169 generation, 170 current_heads.as_slice(), 171 deletion_request_ids.as_slice(), 172 visible_event_ids.as_slice(), 173 suppressed_event_ids.as_slice(), 174 superseded_event_ids.as_slice(), 175 )?; 176 Ok(VisibilityEvaluation { 177 snapshot: VisibilitySnapshot::new( 178 generation, 179 current_heads, 180 deletion_request_ids, 181 visible_event_ids, 182 suppressed_event_ids, 183 superseded_event_ids, 184 digest, 185 ), 186 visible, 187 }) 188 } 189 190 fn parse_deletion_request(event: &SignedEvent) -> Result<DeletionRequest, Error> { 191 let mut event_targets = BTreeSet::new(); 192 let mut address_targets = BTreeSet::new(); 193 for tag in event.envelope().tag_slices() { 194 match tag.as_slice().first().map(String::as_str) { 195 Some("e") => { 196 let value = tag.as_slice().get(1).ok_or(Error::CorruptStoredEvent)?; 197 event_targets.insert(EventId::parse(value).map_err(|_| Error::CorruptStoredEvent)?); 198 } 199 Some("a") => { 200 let value = tag.as_slice().get(1).ok_or(Error::CorruptStoredEvent)?; 201 address_targets 202 .insert(Nip01Coordinate::parse(value).map_err(|_| Error::CorruptStoredEvent)?); 203 } 204 _ => {} 205 } 206 } 207 if event_targets.is_empty() && address_targets.is_empty() { 208 return Err(Error::CorruptStoredEvent); 209 } 210 Ok(DeletionRequest { 211 request_id: *event.id(), 212 author: *event.envelope().author().as_bytes(), 213 created_at: event.envelope().created_at_u64(), 214 event_targets, 215 address_targets, 216 }) 217 } 218 219 fn is_suppressed(target: &SignedEvent, requests: &[DeletionRequest]) -> bool { 220 let target_event = target.envelope(); 221 if target_event.kind_u32() == KIND_DELETION_REQUEST { 222 return false; 223 } 224 let coordinate = event_coordinate(target_event); 225 requests.iter().any(|request| { 226 let request_event_id_match = request.event_targets.contains(target_event.id()); 227 let request_coordinate_match = coordinate.as_ref().is_some_and(|coordinate| { 228 request.address_targets.contains(coordinate) 229 && target_event.created_at_u64() <= request.created_at 230 }); 231 (request_event_id_match || request_coordinate_match) 232 && request.author == *target_event.author().as_bytes() 233 }) 234 } 235 236 fn event_coordinate(event: &radroots_event::Event) -> Option<Nip01Coordinate> { 237 let kind = event.kind_u32(); 238 let identifier = match event.kind_class() { 239 radroots_event::envelope::EventKindClass::Replaceable => "", 240 radroots_event::envelope::EventKindClass::Addressable => event 241 .tag_slices() 242 .iter() 243 .find(|tag| tag.as_slice().first().is_some_and(|name| name == "d"))? 244 .as_slice() 245 .get(1)? 246 .as_str(), 247 radroots_event::envelope::EventKindClass::Regular 248 | radroots_event::envelope::EventKindClass::Ephemeral => return None, 249 }; 250 Nip01Coordinate::parse(format!("{kind}:{}:{identifier}", event.author())).ok() 251 } 252 253 fn visibility_digest( 254 generation: SourceGeneration, 255 heads: &[CurrentEventHead], 256 deletion_requests: &[EventId], 257 visible: &[EventId], 258 suppressed: &[EventId], 259 superseded: &[EventId], 260 ) -> Result<VisibilityDigest, Error> { 261 let mut digest = Sha256::new(); 262 digest.update(b"radroots.storage.visibility.v1\0"); 263 digest.update(generation.as_bytes()); 264 for head in heads { 265 digest.update(b"head\0"); 266 match &head.coordinate { 267 EventHeadCoordinate::Replaceable { kind, pubkey } => { 268 digest.update(b"replaceable\0"); 269 digest.update(kind.to_be_bytes()); 270 digest.update(pubkey.as_bytes()); 271 } 272 EventHeadCoordinate::Addressable { 273 kind, 274 pubkey, 275 d_tag, 276 } => { 277 digest.update(b"addressable\0"); 278 digest.update(kind.to_be_bytes()); 279 digest.update(pubkey.as_bytes()); 280 let d_tag_length = 281 u64::try_from(d_tag.len()).map_err(|_| Error::CorruptStoredEvent)?; 282 digest.update(d_tag_length.to_be_bytes()); 283 digest.update(d_tag.as_bytes()); 284 } 285 } 286 digest.update(head.event_id.as_bytes()); 287 digest.update(head.created_at.to_be_bytes()); 288 } 289 update_event_ids(&mut digest, b"deletion\0", deletion_requests); 290 update_event_ids(&mut digest, b"visible\0", visible); 291 update_event_ids(&mut digest, b"suppressed\0", suppressed); 292 update_event_ids(&mut digest, b"superseded\0", superseded); 293 Ok(VisibilityDigest::new(digest.finalize().into())) 294 } 295 296 fn update_event_ids(digest: &mut Sha256, prefix: &[u8], event_ids: &[EventId]) { 297 for event_id in event_ids { 298 digest.update(prefix); 299 digest.update(event_id.as_bytes()); 300 } 301 } 302 303 #[cfg(test)] 304 mod tests { 305 use super::*; 306 use radroots_event::wire::Nip01EventWire; 307 308 const AUTHOR: &str = "585591529da0bab31b3b1b1f986611cf5f435dca84f978c89ee8a40cca7103df"; 309 const OTHER_AUTHOR: &str = "79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798"; 310 311 fn signed_event( 312 author: &str, 313 created_at: u64, 314 kind: u32, 315 tags: Vec<Vec<&str>>, 316 content: &str, 317 ) -> SignedEvent { 318 let tags = tags 319 .into_iter() 320 .map(|tag| tag.into_iter().map(str::to_owned).collect::<Vec<_>>()) 321 .collect::<Vec<_>>(); 322 let mut wire = Nip01EventWire { 323 id: "0".repeat(64), 324 pubkey: author.to_owned(), 325 created_at, 326 kind, 327 tags, 328 content: content.to_owned(), 329 sig: "42".repeat(64), 330 extra: Default::default(), 331 }; 332 wire.id = wire.computed_event_id().expect("event id").to_hex(); 333 let raw_json = serde_json::json!({ 334 "id": &wire.id, 335 "pubkey": &wire.pubkey, 336 "created_at": wire.created_at, 337 "kind": wire.kind, 338 "tags": &wire.tags, 339 "content": &wire.content, 340 "sig": &wire.sig, 341 }) 342 .to_string(); 343 SignedEvent::from_wire_verified_id(wire, raw_json).expect("signed event") 344 } 345 346 fn evaluate<'a>( 347 events: impl IntoIterator<Item = (&'a SignedEvent, AdmissionStage)>, 348 ) -> VisibilityEvaluation { 349 let generation = SourceGeneration::new([7; 32]).expect("generation"); 350 evaluate_visibility( 351 generation, 352 events 353 .into_iter() 354 .enumerate() 355 .map(|(index, (event, stage))| { 356 let sequence = u64::try_from(index) 357 .expect("index") 358 .checked_add(1) 359 .and_then(|value| super::super::EventSequence::new(value).ok()) 360 .expect("sequence"); 361 VisibilityInput::new(EventPosition::new(generation, sequence), event, stage) 362 }), 363 ) 364 .expect("visibility") 365 } 366 367 #[test] 368 fn verified_head_supersedes_visible_payload_without_becoming_visible() { 369 for (kind, tags) in [(0, vec![]), (30_023, vec![vec!["d", "same"]])] { 370 let old = signed_event(AUTHOR, 10, kind, tags.clone(), r#"{"name":"old"}"#); 371 let invalid = signed_event(AUTHOR, 20, kind, tags, "malformed payload"); 372 let before = evaluate([ 373 (&old, AdmissionStage::Visible), 374 (&invalid, AdmissionStage::Raw), 375 ]); 376 assert!(before.is_visible(old.id())); 377 let after = evaluate([ 378 (&old, AdmissionStage::Visible), 379 (&invalid, AdmissionStage::Verified), 380 ]); 381 assert!(!after.is_visible(old.id())); 382 assert!(!after.is_visible(invalid.id())); 383 assert_eq!(after.snapshot().current_heads()[0].event_id, *invalid.id()); 384 assert_eq!(after.snapshot().superseded_event_ids(), &[*old.id()]); 385 assert_ne!(before.snapshot().digest(), after.snapshot().digest()); 386 let reverse = evaluate([ 387 (&invalid, AdmissionStage::Verified), 388 (&old, AdmissionStage::Visible), 389 ]); 390 assert_eq!(after.snapshot(), reverse.snapshot()); 391 } 392 } 393 394 #[test] 395 fn verified_heads_keep_canonical_ties_and_empty_address_coordinates() { 396 let a = signed_event(AUTHOR, 10, 30_023, vec![], "a"); 397 let b = signed_event(AUTHOR, 10, 30_023, vec![vec!["d", ""]], "b"); 398 let (winner, loser) = if a.id() < b.id() { (&a, &b) } else { (&b, &a) }; 399 let result = evaluate([ 400 (loser, AdmissionStage::Visible), 401 (winner, AdmissionStage::Verified), 402 ]); 403 assert_eq!(result.snapshot().current_heads().len(), 1); 404 assert_eq!(result.snapshot().current_heads()[0].event_id, *winner.id()); 405 assert!(result.snapshot().visible_event_ids().is_empty()); 406 let reverse = evaluate([ 407 (winner, AdmissionStage::Verified), 408 (loser, AdmissionStage::Visible), 409 ]); 410 assert_eq!(result.snapshot(), reverse.snapshot()); 411 let visible_winner = evaluate([ 412 (winner, AdmissionStage::Visible), 413 (loser, AdmissionStage::Verified), 414 ]); 415 assert!(visible_winner.is_visible(winner.id())); 416 assert!(!visible_winner.is_visible(loser.id())); 417 } 418 419 #[test] 420 fn verified_deletion_has_no_authority_and_valid_deletion_precedes_target() { 421 let target = signed_event(AUTHOR, 10, 0, vec![], "profile"); 422 let deletion = signed_event( 423 AUTHOR, 424 20, 425 5, 426 vec![vec!["e", target.id().to_hex().as_str()]], 427 "", 428 ); 429 let forged = signed_event( 430 OTHER_AUTHOR, 431 20, 432 5, 433 vec![vec!["e", target.id().to_hex().as_str()]], 434 "", 435 ); 436 let malformed = signed_event(AUTHOR, 30, 5, vec![], ""); 437 for stage in [AdmissionStage::Raw, AdmissionStage::Verified] { 438 let result = evaluate([ 439 (&deletion, stage), 440 (&malformed, stage), 441 (&forged, AdmissionStage::Visible), 442 (&target, AdmissionStage::Visible), 443 ]); 444 assert!(result.is_visible(target.id())); 445 assert_eq!(result.snapshot().deletion_request_ids(), &[*forged.id()]); 446 } 447 let result = evaluate([ 448 (&deletion, AdmissionStage::Visible), 449 (&target, AdmissionStage::Visible), 450 ]); 451 assert!(!result.is_visible(target.id())); 452 assert_eq!(result.snapshot().suppressed_event_ids(), &[*target.id()]); 453 } 454 455 #[test] 456 fn selected_head_is_stable_and_a_deleted_head_does_not_resurrect() { 457 let old = signed_event(AUTHOR, 10, 0, vec![], r#"{"name":"old"}"#); 458 let current = signed_event(AUTHOR, 20, 0, vec![], r#"{"name":"current"}"#); 459 let deletion = signed_event( 460 AUTHOR, 461 30, 462 KIND_DELETION_REQUEST, 463 vec![vec!["e", current.id().to_hex().as_str()]], 464 "", 465 ); 466 let evaluation = evaluate([ 467 (&old, AdmissionStage::Visible), 468 (¤t, AdmissionStage::Visible), 469 (&deletion, AdmissionStage::Visible), 470 ]); 471 472 assert!(!evaluation.is_visible(old.id())); 473 assert!(!evaluation.is_visible(current.id())); 474 assert!(evaluation.is_visible(deletion.id())); 475 assert_eq!(evaluation.snapshot().superseded_event_ids(), &[*old.id()]); 476 assert_eq!( 477 evaluation.snapshot().suppressed_event_ids(), 478 &[*current.id()] 479 ); 480 assert_eq!( 481 evaluation.snapshot().current_heads()[0].event_id, 482 *current.id() 483 ); 484 } 485 486 #[test] 487 fn address_cutoff_allows_a_later_replacement_and_wrong_author_is_ineffective() { 488 let old = signed_event(AUTHOR, 10, 30_023, vec![vec!["d", "farm-update"]], "old"); 489 let wrong_author_deletion = signed_event( 490 OTHER_AUTHOR, 491 15, 492 KIND_DELETION_REQUEST, 493 vec![vec!["a", format!("30023:{AUTHOR}:farm-update").as_str()]], 494 "", 495 ); 496 let cutoff = signed_event( 497 AUTHOR, 498 20, 499 KIND_DELETION_REQUEST, 500 vec![vec!["a", format!("30023:{AUTHOR}:farm-update").as_str()]], 501 "", 502 ); 503 let later = signed_event(AUTHOR, 30, 30_023, vec![vec!["d", "farm-update"]], "later"); 504 let evaluation = evaluate([ 505 (&old, AdmissionStage::Visible), 506 (&wrong_author_deletion, AdmissionStage::Visible), 507 (&cutoff, AdmissionStage::Visible), 508 (&later, AdmissionStage::Visible), 509 ]); 510 511 assert!(evaluation.is_visible(later.id())); 512 assert!(evaluation.is_visible(wrong_author_deletion.id())); 513 assert!(evaluation.is_visible(cutoff.id())); 514 assert!(!evaluation.is_visible(old.id())); 515 assert_eq!( 516 evaluation.snapshot().current_heads()[0].event_id, 517 *later.id() 518 ); 519 } 520 521 #[test] 522 fn rebuild_is_order_independent_and_ignores_nonvisible_admissions() { 523 let visible = signed_event(AUTHOR, 10, 1, vec![], "visible"); 524 let excluded = signed_event(AUTHOR, 20, 1, vec![], "excluded"); 525 let ephemeral = signed_event(AUTHOR, 30, 20_000, vec![], "ephemeral"); 526 let first = evaluate([ 527 (&visible, AdmissionStage::Visible), 528 (&excluded, AdmissionStage::Verified), 529 (&ephemeral, AdmissionStage::Visible), 530 ]); 531 let second = evaluate([ 532 (&ephemeral, AdmissionStage::Visible), 533 (&excluded, AdmissionStage::Verified), 534 (&visible, AdmissionStage::Visible), 535 ]); 536 537 assert!(first.is_visible(visible.id())); 538 assert!(!first.is_visible(excluded.id())); 539 assert!(!first.is_visible(ephemeral.id())); 540 assert_eq!(first.snapshot().digest(), second.snapshot().digest()); 541 assert_eq!(first.snapshot(), second.snapshot()); 542 } 543 544 #[test] 545 fn deletion_requests_without_targets_fail_closed() { 546 let deletion = signed_event(AUTHOR, 10, KIND_DELETION_REQUEST, vec![], ""); 547 let generation = SourceGeneration::new([7; 32]).expect("generation"); 548 let position = EventPosition::new( 549 generation, 550 super::super::EventSequence::new(1).expect("sequence"), 551 ); 552 553 let error = evaluate_visibility( 554 generation, 555 [VisibilityInput::new( 556 position, 557 &deletion, 558 AdmissionStage::Visible, 559 )], 560 ) 561 .err() 562 .expect("targetless deletion must fail"); 563 564 assert_eq!(error, Error::CorruptStoredEvent); 565 } 566 567 #[test] 568 fn events_from_another_generation_fail_closed() { 569 let event = signed_event(AUTHOR, 10, 1, vec![], "event"); 570 let requested_generation = SourceGeneration::new([7; 32]).expect("generation"); 571 let stored_generation = SourceGeneration::new([8; 32]).expect("generation"); 572 let position = EventPosition::new( 573 stored_generation, 574 super::super::EventSequence::new(1).expect("sequence"), 575 ); 576 577 let error = evaluate_visibility( 578 requested_generation, 579 [VisibilityInput::new( 580 position, 581 &event, 582 AdmissionStage::Visible, 583 )], 584 ) 585 .err() 586 .expect("cross-generation visibility input must fail"); 587 588 assert_eq!(error, Error::CorruptStoredEvent); 589 } 590 }