lib

Core libraries for Radroots
git clone https://radroots.dev/git/lib.git
Log | Files | Refs | README

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 }