causal.rs (12856B)
1 //! Bounded causal checks over declared records. The caller must authenticate 2 //! every original source and bind complete local coverage to a store checkpoint. 3 //! A complete result grants no participant permission or physical stock effect. 4 use super::{CommerceContent, CommerceType}; 5 use crate::{OrderId, PublicKey, RecordId, SourceId, ThreadId}; 6 use alloc::{ 7 boxed::Box, 8 collections::{BTreeMap, BTreeSet}, 9 vec, 10 vec::Vec, 11 }; 12 use core::fmt; 13 mod request; 14 pub use request::{InitialRequestClaim, RequestClaimError, prepare_initial_request}; 15 mod replacement; 16 pub use replacement::{ 17 ReplacementTermsClaim, ReplacementTermsError, ReplacementTermsSelection, 18 prepare_replacement_terms, 19 }; 20 21 /// One exact bilateral order scope, including seller quotes in its null-order 22 /// author chain. The scope itself is untrusted data, not evidence coverage. 23 #[derive(Clone, Copy, Debug, Eq, PartialEq)] 24 pub struct CausalScope { 25 thread: ThreadId, 26 order: OrderId, 27 buyer: PublicKey, 28 seller: PublicKey, 29 } 30 impl CausalScope { 31 /// Requires distinct parties. Original participant authentication is separate. 32 pub fn new( 33 thread: ThreadId, 34 order: OrderId, 35 buyer: PublicKey, 36 seller: PublicKey, 37 ) -> Result<Self, CausalError> { 38 if buyer == seller { 39 return Err(CausalError::InvalidScope); 40 } 41 Ok(Self { 42 thread, 43 order, 44 buyer, 45 seller, 46 }) 47 } 48 /// Checks exact declared thread, participants and selected/null quote order. 49 pub fn contains(self, content: &CommerceContent) -> bool { 50 let header = content.header(); 51 header.thread_id() == self.thread 52 && header.buyer() == self.buyer 53 && header.seller() == self.seller 54 && (header.order_id() == Some(self.order) 55 || (header.order_id().is_none() && content.record_type() == CommerceType::Quote)) 56 } 57 /// Returns the exact declared thread. 58 pub const fn thread_id(self) -> ThreadId { 59 self.thread 60 } 61 /// Returns the exact declared order. 62 pub const fn order_id(self) -> OrderId { 63 self.order 64 } 65 /// Returns the exact declared buyer. 66 pub const fn buyer(self) -> PublicKey { 67 self.buyer 68 } 69 /// Returns the exact declared seller. 70 pub const fn seller(self) -> PublicKey { 71 self.seller 72 } 73 } 74 75 /// A borrowed content/identity claim. Hash, carrier signature and recipient 76 /// authentication must precede use; constructing this value does none of them. 77 #[derive(Clone, Copy)] 78 pub struct CausalRecord<'a> { 79 id: RecordId, 80 content: &'a CommerceContent, 81 } 82 impl<'a> CausalRecord<'a> { 83 /// Returns the asserted identity, without checking its canonical hash. 84 pub const fn record_id(self) -> RecordId { 85 self.id 86 } 87 /// Borrows the original complete content claim without authenticating it. 88 pub const fn content(self) -> &'a CommerceContent { 89 self.content 90 } 91 /// Borrows the complete content so duplicate identity comparisons cannot 92 /// accidentally ignore a changed payload. No source bytes are copied. 93 pub const fn new(id: RecordId, content: &'a CommerceContent) -> Self { 94 Self { id, content } 95 } 96 } 97 impl fmt::Debug for CausalRecord<'_> { 98 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 99 f.write_str("CausalRecord(<untrusted claim>)") 100 } 101 } 102 103 /// Local causal classification; even Complete is not business actionability. 104 #[derive(Clone, Copy, Debug, Eq, PartialEq)] 105 pub enum CausalReadiness { 106 /// All supplied required sources and author links are present and acyclic. 107 Complete, 108 /// Exact source identities are missing; fetch them before reducing actions. 109 MissingHistory, 110 /// An authenticated but uninterpreted source prevents a complete reduction. 111 Uninterpreted, 112 /// An author fork, inconsistent predecessor or causal cycle is exposed. 113 Conflicted, 114 } 115 /// Deterministic, input-order-independent local coverage result. Original 116 /// evidence and installed agreement state remain owned by their caller/store. 117 #[derive(Clone, Eq, PartialEq)] 118 pub struct CausalAnalysis { 119 readiness: CausalReadiness, 120 buyer_head: Option<RecordId>, 121 seller_head: Option<RecordId>, 122 quote_head: Option<RecordId>, 123 missing: Box<[SourceId]>, 124 conflicts: Box<[RecordId]>, 125 uninterpreted: Box<[SourceId]>, 126 cycle: bool, 127 } 128 impl CausalAnalysis { 129 /// Exact local coverage classification, without current business permission. 130 pub const fn readiness(&self) -> CausalReadiness { 131 self.readiness 132 } 133 /// Last contiguous uncontested buyer author-chain claim in the selected order. 134 pub const fn buyer_head(&self) -> Option<RecordId> { 135 self.buyer_head 136 } 137 /// Last contiguous uncontested seller author-chain claim in the selected order. 138 pub const fn seller_head(&self) -> Option<RecordId> { 139 self.seller_head 140 } 141 /// Last contiguous uncontested seller quote in the null-order chain. 142 pub const fn quote_head(&self) -> Option<RecordId> { 143 self.quote_head 144 } 145 /// Sorted unique exact missing references. No empty-state inference is made. 146 pub fn missing(&self) -> &[SourceId] { 147 &self.missing 148 } 149 /// Sorted exact conflicting records, including known-cycle descendants. 150 pub fn conflicts(&self) -> &[RecordId] { 151 &self.conflicts 152 } 153 /// Original retained uninterpreted identities that require reconciliation. 154 pub fn uninterpreted(&self) -> &[SourceId] { 155 &self.uninterpreted 156 } 157 /// Whether the supplied known-record dependency graph contains a cycle. 158 pub const fn has_cycle(&self) -> bool { 159 self.cycle 160 } 161 } 162 impl fmt::Debug for CausalAnalysis { 163 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 164 f.write_str("CausalAnalysis(<private coverage>)") 165 } 166 } 167 /// Explicit resource/identity/scope failure, without private source contents. 168 #[derive(Clone, Copy, Debug, Eq, PartialEq)] 169 #[non_exhaustive] 170 pub enum CausalError { 171 /// More than the contracted bounded records/source references were supplied. 172 LimitExceeded, 173 /// A supplied known record belongs to another thread, order or participant pair. 174 InvalidScope, 175 /// One asserted logical identity names different complete content. 176 IdentityConflict, 177 } 178 impl fmt::Display for CausalError { 179 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 180 f.write_str(match self { 181 Self::LimitExceeded => "causal graph limit exceeded", 182 Self::InvalidScope => "causal scope differs", 183 Self::IdentityConflict => "causal record identity conflict", 184 }) 185 } 186 } 187 impl core::error::Error for CausalError {} 188 189 /// Maximum known records in one complete scoped causal evaluation. Larger 190 /// histories refuse explicitly; they are never silently truncated or paged as 191 /// though the first page were complete. Durable unrelated history is not capped. 192 pub const MAX_CAUSAL_RECORDS: usize = 1000; 193 /// Maximum separately verified external/uninterpreted source identities. 194 pub const MAX_CAUSAL_SOURCES: usize = MAX_CAUSAL_RECORDS * 8; 195 196 fn source(id: RecordId) -> SourceId { 197 SourceId::from_bytes(id.into_bytes()) 198 } 199 200 /// Checks the complete supplied local scoped graph with no recursion or clock. 201 /// External sources cannot stand in for an author predecessor. Uninterpreted 202 /// authenticated evidence remains a barrier, including when no known node 203 /// happens to reference it. Source completeness/authenticity remains a mandatory 204 /// store/ingress obligation; this pure function cannot discover omitted records. 205 pub fn analyze( 206 scope: CausalScope, 207 records: &[CausalRecord<'_>], 208 external_sources: &[SourceId], 209 uninterpreted_sources: &[SourceId], 210 ) -> Result<CausalAnalysis, CausalError> { 211 if records.len() > MAX_CAUSAL_RECORDS 212 || external_sources.len() > MAX_CAUSAL_SOURCES 213 || uninterpreted_sources.len() > MAX_CAUSAL_SOURCES 214 { 215 return Err(CausalError::LimitExceeded); 216 } 217 let mut unique = BTreeMap::<SourceId, CausalRecord<'_>>::new(); 218 for record in records { 219 if !scope.contains(record.content) { 220 return Err(CausalError::InvalidScope); 221 } 222 if let Some(previous) = unique.insert(source(record.id), *record) 223 && previous.content != record.content 224 { 225 return Err(CausalError::IdentityConflict); 226 } 227 } 228 // Stable identity ordering makes traversal and diagnostics independent of 229 // relay arrival order and caller ordering. No timestamp wins a private fork. 230 let nodes: Vec<_> = unique.values().copied().collect(); 231 let positions: BTreeMap<_, _> = nodes 232 .iter() 233 .enumerate() 234 .map(|(index, node)| (source(node.id), index)) 235 .collect(); 236 let external: BTreeSet<_> = external_sources.iter().copied().collect(); 237 let uninterpreted: BTreeSet<_> = uninterpreted_sources.iter().copied().collect(); 238 let mut slots = BTreeMap::new(); 239 let mut conflicts = BTreeSet::new(); 240 let mut missing = BTreeSet::new(); 241 for node in &nodes { 242 let header = node.content.header(); 243 let slot = ( 244 header.author(), 245 header.order_id(), 246 header.author_sequence().get(), 247 ); 248 if let Some(prior) = slots.insert(slot, node.id) { 249 conflicts.insert(prior); 250 conflicts.insert(node.id); 251 } 252 for parent in header.parents() { 253 if !positions.contains_key(parent) 254 && !external.contains(parent) 255 && !uninterpreted.contains(parent) 256 { 257 missing.insert(*parent); 258 } 259 } 260 if let Some(previous) = header.author_previous() { 261 if let Some(index) = positions.get(&source(previous)) { 262 let prior = nodes[*index].content.header(); 263 if prior.author() != header.author() 264 || prior.thread_id() != header.thread_id() 265 || prior.order_id() != header.order_id() 266 || prior.buyer() != header.buyer() 267 || prior.seller() != header.seller() 268 || prior.author_sequence().get().checked_add(1) 269 != Some(header.author_sequence().get()) 270 { 271 conflicts.insert(node.id); 272 } 273 } else { 274 // A generic existing source or uninterpreted carrier cannot 275 // prove the declared predecessor's author/scope/sequence. 276 missing.insert(source(previous)); 277 } 278 } 279 } 280 // Iterative topological traversal bounds both stack and work by the explicit 281 // record budget. Missing external parents are reported separately; they do 282 // not manufacture a false cycle in the known dependency subgraph. 283 let mut visited = vec![false; nodes.len()]; 284 loop { 285 let mut progress = false; 286 for (index, node) in nodes.iter().enumerate() { 287 if !visited[index] 288 && node 289 .content 290 .header() 291 .parents() 292 .iter() 293 .all(|parent| positions.get(parent).is_none_or(|parent| visited[*parent])) 294 { 295 visited[index] = true; 296 progress = true; 297 } 298 } 299 if !progress { 300 break; 301 } 302 } 303 let cycle = visited.iter().any(|visited| !visited); 304 for (node, visited) in nodes.iter().zip(&visited) { 305 if !visited { 306 conflicts.insert(node.id); 307 } 308 } 309 let head = |author, order| { 310 let mut previous = None; 311 let mut sequence = 1; 312 while let Some(id) = slots.get(&(author, order, sequence)).copied() { 313 let node = &nodes[positions[&source(id)]]; 314 if conflicts.contains(&id) || node.content.header().author_previous() != previous { 315 break; 316 } 317 previous = Some(id); 318 sequence += 1; 319 } 320 previous 321 }; 322 let readiness = if !conflicts.is_empty() { 323 CausalReadiness::Conflicted 324 } else if !uninterpreted.is_empty() { 325 CausalReadiness::Uninterpreted 326 } else if !missing.is_empty() { 327 CausalReadiness::MissingHistory 328 } else { 329 CausalReadiness::Complete 330 }; 331 Ok(CausalAnalysis { 332 readiness, 333 buyer_head: head(scope.buyer, Some(scope.order)), 334 seller_head: head(scope.seller, Some(scope.order)), 335 quote_head: head(scope.seller, None), 336 missing: missing.into_iter().collect(), 337 conflicts: conflicts.into_iter().collect(), 338 uninterpreted: uninterpreted.into_iter().collect(), 339 cycle, 340 }) 341 }