Skip to main content

arachne_routing/
lib.rs

1//! Payload-independent, workspace-scoped pub/sub routing.
2//!
3//! This module does NOT authenticate identities or authorize policy changes.
4//! The caller must verify policy snapshots and bind every operation's PeerId
5//! to its authenticated origin. A transport session alone is insufficient for
6//! forwarded messages. No encryption, persistence or delivery guarantee is implied.
7mod publication;
8pub use publication::PublicationContext;
9
10use std::collections::{BTreeMap, BTreeSet};
11
12pub type WorkspaceId = [u8; 32];
13/// Authenticated endpoint key, not a workspace member or human identity.
14pub type PeerId = [u8; 32];
15
16const MAX_WORKSPACES: usize = 32;
17const MAX_ENDPOINTS: usize = 4096;
18const MAX_TOPICS_PER_PEER: usize = 64;
19
20#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
21pub struct Topic(String);
22
23impl Topic {
24    /// Exact, case-sensitive topics. Wildcards are not supported.
25    pub fn new(value: impl Into<String>) -> Result<Self, Error> {
26        let value = value.into();
27        if value.is_empty()
28            || value.len() > 128
29            || value.split('/').any(str::is_empty)
30            || !value
31                .bytes()
32                .all(|b| b.is_ascii_alphanumeric() || b"/-_.".contains(&b))
33        {
34            return Err(Error::InvalidTopic);
35        }
36        Ok(Self(value))
37    }
38
39    pub fn as_str(&self) -> &str {
40        &self.0
41    }
42}
43
44/// Topic authorization is independent from subscription interest.
45#[derive(Debug, Clone)]
46pub enum Permissions {
47    AllTopics,
48    Selected {
49        publish: BTreeSet<Topic>,
50        subscribe: BTreeSet<Topic>,
51    },
52}
53impl Default for Permissions {
54    fn default() -> Self {
55        Self::Selected {
56            publish: BTreeSet::new(),
57            subscribe: BTreeSet::new(),
58        }
59    }
60}
61impl Permissions {
62    fn can_publish(&self, topic: &Topic) -> bool {
63        match self {
64            Self::AllTopics => true,
65            Self::Selected { publish, .. } => publish.contains(topic),
66        }
67    }
68    fn can_subscribe(&self, topic: &Topic) -> bool {
69        match self {
70            Self::AllTopics => true,
71            Self::Selected { subscribe, .. } => subscribe.contains(topic),
72        }
73    }
74    fn within_bounds(&self) -> bool {
75        match self {
76            Self::AllTopics => true,
77            Self::Selected { publish, subscribe } => {
78                publish.len() <= MAX_TOPICS_PER_PEER && subscribe.len() <= MAX_TOPICS_PER_PEER
79            }
80        }
81    }
82}
83
84#[derive(Debug, Clone, Copy, PartialEq, Eq)]
85pub enum Error {
86    InvalidTopic,
87    LimitExceeded,
88    UnknownWorkspace,
89    WrongPolicyRevision,
90    Denied,
91}
92
93impl std::fmt::Display for Error {
94    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
95        write!(formatter, "{self:?}")
96    }
97}
98impl std::error::Error for Error {}
99
100struct Workspace {
101    revision: u64,
102    endpoint_permissions: BTreeMap<PeerId, Permissions>,
103    subscriptions: BTreeMap<PeerId, BTreeSet<Topic>>,
104}
105
106#[derive(Default)]
107pub struct RoutingTable {
108    workspaces: BTreeMap<WorkspaceId, Workspace>,
109}
110
111impl RoutingTable {
112    /// Authorized transport endpoints for an already verified policy revision.
113    /// This is bootstrap input, never evidence that an endpoint is online.
114    pub fn authorized_endpoints(
115        &self,
116        workspace: WorkspaceId,
117        revision: u64,
118    ) -> Result<Vec<PeerId>, Error> {
119        let state = self
120            .workspaces
121            .get(&workspace)
122            .ok_or(Error::UnknownWorkspace)?;
123        if state.revision != revision {
124            return Err(Error::WrongPolicyRevision);
125        }
126        Ok(state.endpoint_permissions.keys().copied().collect())
127    }
128
129    /// Check an authenticated transport endpoint against the current policy.
130    pub fn authorizes_endpoint(
131        &self,
132        workspace: WorkspaceId,
133        revision: u64,
134        peer: PeerId,
135    ) -> Result<(), Error> {
136        let state = self
137            .workspaces
138            .get(&workspace)
139            .ok_or(Error::UnknownWorkspace)?;
140        if state.revision != revision {
141            return Err(Error::WrongPolicyRevision);
142        }
143        if state.endpoint_permissions.contains_key(&peer) {
144            Ok(())
145        } else {
146            Err(Error::Denied)
147        }
148    }
149
150    /// Publishers to notify about an authorized subscriber's interest.
151    pub fn publishers(
152        &self,
153        workspace: WorkspaceId,
154        revision: u64,
155        subscriber: PeerId,
156        topic: &Topic,
157    ) -> Result<Vec<PeerId>, Error> {
158        let state = self
159            .workspaces
160            .get(&workspace)
161            .ok_or(Error::UnknownWorkspace)?;
162        if state.revision != revision {
163            return Err(Error::WrongPolicyRevision);
164        }
165        if !state
166            .endpoint_permissions
167            .get(&subscriber)
168            .is_some_and(|access| access.can_subscribe(topic))
169        {
170            return Err(Error::Denied);
171        }
172        Ok(state
173            .endpoint_permissions
174            .iter()
175            .filter_map(|(peer, access)| access.can_publish(topic).then_some(*peer))
176            .collect())
177    }
178
179    /// Atomically install an externally verified policy snapshot. Revisions must
180    /// increase strictly. Revocation also removes now-unauthorized interests.
181    /// The caller must persist accepted revisions to prevent rollback on restart.
182    /// This revision describes authorization, not a cryptographic epoch. The map
183    /// is an endpoint permission projection, not the workspace member registry.
184    pub fn install_verified_policy(
185        &mut self,
186        workspace: WorkspaceId,
187        revision: u64,
188        endpoint_permissions: BTreeMap<PeerId, Permissions>,
189    ) -> Result<(), Error> {
190        if endpoint_permissions.len() > MAX_ENDPOINTS
191            || endpoint_permissions.values().any(|p| !p.within_bounds())
192            || (!self.workspaces.contains_key(&workspace)
193                && self.workspaces.len() >= MAX_WORKSPACES)
194        {
195            return Err(Error::LimitExceeded);
196        }
197        if self
198            .workspaces
199            .get(&workspace)
200            .is_some_and(|old| revision <= old.revision)
201        {
202            return Err(Error::WrongPolicyRevision);
203        }
204        let mut subscriptions = self
205            .workspaces
206            .remove(&workspace)
207            .map(|old| old.subscriptions)
208            .unwrap_or_default();
209        subscriptions.retain(|peer, topics| {
210            if let Some(access) = endpoint_permissions.get(peer) {
211                topics.retain(|topic| access.can_subscribe(topic));
212                !topics.is_empty()
213            } else {
214                false
215            }
216        });
217        self.workspaces.insert(
218            workspace,
219            Workspace {
220                revision,
221                endpoint_permissions,
222                subscriptions,
223            },
224        );
225        Ok(())
226    }
227
228    pub fn subscribe(
229        &mut self,
230        workspace: WorkspaceId,
231        revision: u64,
232        peer: PeerId,
233        topic: Topic,
234    ) -> Result<(), Error> {
235        let state = self
236            .workspaces
237            .get_mut(&workspace)
238            .ok_or(Error::UnknownWorkspace)?;
239        if state.revision != revision {
240            return Err(Error::WrongPolicyRevision);
241        }
242        if !state
243            .endpoint_permissions
244            .get(&peer)
245            .is_some_and(|access| access.can_subscribe(&topic))
246        {
247            return Err(Error::Denied);
248        }
249        let topics = state.subscriptions.entry(peer).or_default();
250        if topics.len() >= MAX_TOPICS_PER_PEER && !topics.contains(&topic) {
251            return Err(Error::LimitExceeded);
252        }
253        topics.insert(topic);
254        Ok(())
255    }
256
257    pub fn unsubscribe(
258        &mut self,
259        workspace: WorkspaceId,
260        revision: u64,
261        peer: PeerId,
262        topic: &Topic,
263    ) -> Result<(), Error> {
264        let state = self
265            .workspaces
266            .get_mut(&workspace)
267            .ok_or(Error::UnknownWorkspace)?;
268        if state.revision != revision {
269            return Err(Error::WrongPolicyRevision);
270        }
271        if !state.endpoint_permissions.contains_key(&peer) {
272            return Err(Error::Denied);
273        }
274        if let Some(topics) = state.subscriptions.get_mut(&peer) {
275            topics.remove(topic);
276            if topics.is_empty() {
277                state.subscriptions.remove(&peer);
278            }
279        }
280        Ok(())
281    }
282
283    /// Current interest only; authorization remains a separate policy check.
284    pub fn subscribed(
285        &self,
286        workspace: WorkspaceId,
287        revision: u64,
288        peer: PeerId,
289        topic: &Topic,
290    ) -> Result<bool, Error> {
291        let state = self
292            .workspaces
293            .get(&workspace)
294            .ok_or(Error::UnknownWorkspace)?;
295        if state.revision != revision {
296            return Err(Error::WrongPolicyRevision);
297        }
298        if !state
299            .endpoint_permissions
300            .get(&peer)
301            .is_some_and(|access| access.can_subscribe(topic))
302        {
303            return Err(Error::Denied);
304        }
305        Ok(state
306            .subscriptions
307            .get(&peer)
308            .is_some_and(|topics| topics.contains(topic)))
309    }
310
311    /// Select authorized current subscribers; never fall back to workspace-wide
312    /// broadcast. Self is included when subscribed. Routing creates no delivery
313    /// receipt, retention, queue or duplicate-suppression promise.
314    pub fn recipients(
315        &self,
316        workspace: WorkspaceId,
317        revision: u64,
318        sender: PeerId,
319        topic: &Topic,
320    ) -> Result<Vec<PeerId>, Error> {
321        let state = self
322            .workspaces
323            .get(&workspace)
324            .ok_or(Error::UnknownWorkspace)?;
325        if state.revision != revision {
326            return Err(Error::WrongPolicyRevision);
327        }
328        if !state
329            .endpoint_permissions
330            .get(&sender)
331            .is_some_and(|access| access.can_publish(topic))
332        {
333            return Err(Error::Denied);
334        }
335        // ponytail: scan subscribed peers; add a topic index when measured fanout warrants it.
336        Ok(state
337            .subscriptions
338            .iter()
339            .filter_map(|(peer, topics)| topics.contains(topic).then_some(*peer))
340            .collect())
341    }
342
343    /// Validate an explicit endpoint audience, then intersect it with current
344    /// subscriptions. The caller resolves members from a verified roster.
345    pub fn direct_recipients(
346        &self,
347        workspace: WorkspaceId,
348        revision: u64,
349        sender: PeerId,
350        topic: &Topic,
351        recipients: &[PeerId],
352    ) -> Result<Vec<PeerId>, Error> {
353        let state = self
354            .workspaces
355            .get(&workspace)
356            .ok_or(Error::UnknownWorkspace)?;
357        if state.revision != revision {
358            return Err(Error::WrongPolicyRevision);
359        }
360        if recipients.is_empty()
361            || recipients.len() > MAX_ENDPOINTS
362            || recipients.windows(2).any(|pair| pair[0] >= pair[1])
363        {
364            return Err(Error::Denied);
365        }
366        if !state
367            .endpoint_permissions
368            .get(&sender)
369            .is_some_and(|access| access.can_publish(topic))
370        {
371            return Err(Error::Denied);
372        }
373        if recipients.iter().any(|peer| {
374            !state
375                .endpoint_permissions
376                .get(peer)
377                .is_some_and(|access| access.can_subscribe(topic))
378        }) {
379            return Err(Error::Denied);
380        }
381        Ok(recipients
382            .iter()
383            .copied()
384            .filter(|peer| {
385                state
386                    .subscriptions
387                    .get(peer)
388                    .is_some_and(|topics| topics.contains(topic))
389            })
390            .collect())
391    }
392}
393
394#[test]
395fn all_member_access_still_requires_bounded_explicit_interests() {
396    let mut table = RoutingTable::default();
397    let workspace = [1; 32];
398    let topic = Topic::new("feeds/new-stream").unwrap();
399    table
400        .install_verified_policy(
401            workspace,
402            1,
403            BTreeMap::from([
404                ([1; 32], Permissions::AllTopics),
405                ([2; 32], Permissions::AllTopics),
406            ]),
407        )
408        .unwrap();
409    assert!(
410        table
411            .recipients(workspace, 1, [1; 32], &topic)
412            .unwrap()
413            .is_empty()
414    );
415    table
416        .subscribe(workspace, 1, [2; 32], topic.clone())
417        .unwrap();
418    assert_eq!(
419        table.recipients(workspace, 1, [1; 32], &topic).unwrap(),
420        vec![[2; 32]]
421    );
422    assert!(
423        table
424            .subscribe(workspace, 1, [3; 32], topic.clone())
425            .is_err()
426    );
427    assert!(table.recipients([9; 32], 1, [1; 32], &topic).is_err());
428    table.unsubscribe(workspace, 1, [2; 32], &topic).unwrap();
429    assert!(
430        table
431            .recipients(workspace, 1, [1; 32], &topic)
432            .unwrap()
433            .is_empty()
434    );
435    for n in 0..MAX_TOPICS_PER_PEER {
436        table
437            .subscribe(
438                workspace,
439                1,
440                [2; 32],
441                Topic::new(format!("feeds/{n}")).unwrap(),
442            )
443            .unwrap();
444    }
445    assert_eq!(
446        table.subscribe(workspace, 1, [2; 32], topic.clone()),
447        Err(Error::LimitExceeded)
448    );
449    let retained_topic = Topic::new("feeds/0").unwrap();
450    assert_eq!(
451        table
452            .recipients(workspace, 1, [1; 32], &retained_topic)
453            .unwrap(),
454        vec![[2; 32]]
455    );
456    table
457        .install_verified_policy(
458            workspace,
459            2,
460            BTreeMap::from([([1; 32], Permissions::AllTopics)]),
461        )
462        .unwrap();
463    assert!(
464        table
465            .recipients(workspace, 2, [1; 32], &topic)
466            .unwrap()
467            .is_empty()
468    );
469    assert!(
470        table
471            .recipients(workspace, 2, [1; 32], &retained_topic)
472            .unwrap()
473            .is_empty()
474    );
475    assert!(table.subscribe(workspace, 2, [2; 32], topic).is_err());
476}