coven_protocol/
circle_roster.rs

1//! Signed Circle roster streams and causal assignment reduction.
2
3use std::collections::{BTreeMap, BTreeSet};
4
5use serde::{Deserialize, Serialize};
6
7use super::causal_grants::{
8    self, AuthorStreamId, CausalAssignment, CausalChange, CausalCoordinate, CausalEntry,
9    CausalGrantConflict, CausalGrantError, CausalGrantStatus, GrantRetirements, GrantState,
10    OwnerGrantBarrier,
11};
12use super::circle::{CircleId, CircleRole};
13use super::membership::MembershipGrantId;
14use super::store_commit::{ObjectHash, Signed, SignedBody, StoreDeviceRegistration, SuccessorLink};
15use crate::objects::ExactObjectRef;
16use coven_keys::keys::{self, UserKeypair};
17
18mod chain;
19mod conflict;
20mod reduction;
21
22pub use chain::CircleRosterChain;
23#[cfg(any(test, feature = "test-utils"))]
24pub use conflict::CircleRosterConflictResolutionBody;
25pub use conflict::CircleRosterConflictResolutionRef;
26pub use conflict::{
27    derive_circle_resolution_grant, resolve_circle_roster_conflict, CircleMaterializedRoster,
28    CircleRosterBranch, CircleRosterConflict, CircleRosterConflictResolution, CircleRosterStatus,
29    ResolvedCircleRoster,
30};
31
32const ROSTER_DOMAIN: &[u8] = b"coven.circle-roster.v1\0";
33const ROSTER_HEAD_DOMAIN: &[u8] = b"coven.circle-roster-head.v1\0";
34const ROSTER_RESOLUTION_DOMAIN: &[u8] = b"coven.circle-roster-conflict-resolution.v1\0";
35
36#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
37#[serde(deny_unknown_fields)]
38pub struct CircleRosterCoord {
39    pub author_pubkey: String,
40    pub device_id: String,
41    pub stream_id: AuthorStreamId,
42    pub author_owner_grant: MembershipGrantId,
43    pub seq: u64,
44    pub entry_hash: ObjectHash,
45}
46
47impl CircleRosterCoord {
48    pub fn stream_key(&self) -> CircleAuthorStreamKey {
49        CircleAuthorStreamKey {
50            author_pubkey: self.author_pubkey.clone(),
51            device_id: self.device_id.clone(),
52            stream_id: self.stream_id,
53            author_owner_grant: self.author_owner_grant.clone(),
54        }
55    }
56}
57
58impl CausalCoordinate for CircleRosterCoord {
59    type StreamKey = CircleAuthorStreamKey;
60
61    fn stream_key(&self) -> Self::StreamKey {
62        self.stream_key()
63    }
64
65    fn author_pubkey(&self) -> &str {
66        &self.author_pubkey
67    }
68
69    fn author_owner_grant(&self) -> &MembershipGrantId {
70        &self.author_owner_grant
71    }
72
73    fn seq(&self) -> u64 {
74        self.seq
75    }
76
77    fn entry_hash(&self) -> ObjectHash {
78        self.entry_hash
79    }
80}
81
82impl CausalAssignment for CircleRole {
83    fn is_owner(&self) -> bool {
84        *self == CircleRole::Owner
85    }
86}
87
88impl causal_grants::CausalHistoryEntry for CircleRosterEntry {
89    type Coord = CircleRosterCoord;
90
91    fn coord(&self) -> Self::Coord {
92        self.coord()
93    }
94
95    fn dependencies(&self) -> &[Self::Coord] {
96        &self.dependencies
97    }
98}
99
100#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
101#[serde(deny_unknown_fields)]
102pub struct CircleAuthorStreamKey {
103    pub author_pubkey: String,
104    pub device_id: String,
105    pub stream_id: AuthorStreamId,
106    pub author_owner_grant: MembershipGrantId,
107}
108
109#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
110#[serde(deny_unknown_fields)]
111pub struct CircleOwnerGrantBarrier {
112    pub observed_streams: Vec<CircleRosterCoord>,
113}
114
115#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
116#[serde(rename_all = "snake_case", deny_unknown_fields)]
117pub enum CircleRosterChange {
118    Founder {
119        member_pubkey: String,
120        grant_id: MembershipGrantId,
121    },
122    SetMember {
123        member_pubkey: String,
124        role: CircleRole,
125        grant_id: MembershipGrantId,
126        replaces: BTreeSet<MembershipGrantId>,
127        owner_barriers: BTreeMap<MembershipGrantId, CircleOwnerGrantBarrier>,
128    },
129    RemoveMember {
130        member_pubkey: String,
131        removes: BTreeSet<MembershipGrantId>,
132        owner_barriers: BTreeMap<MembershipGrantId, CircleOwnerGrantBarrier>,
133    },
134    ResolutionActivation {
135        resolution: CircleRosterConflictResolutionRef,
136    },
137}
138
139/// The wire body of one Circle roster entry. Every field here is signed.
140#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
141#[serde(deny_unknown_fields)]
142pub struct CircleRosterEntryBody {
143    pub store_root_hash: ObjectHash,
144    pub circle_id: CircleId,
145    pub author_pubkey: String,
146    pub device_id: String,
147    pub stream_id: AuthorStreamId,
148    pub author_owner_grant: MembershipGrantId,
149    pub seq: u64,
150    pub previous_hash: Option<ObjectHash>,
151    pub dependencies: Vec<CircleRosterCoord>,
152    pub resolution_dependencies: Vec<CircleRosterConflictResolutionRef>,
153    pub change: CircleRosterChange,
154}
155
156impl SignedBody for CircleRosterEntryBody {
157    const DOMAIN: &'static [u8] = ROSTER_DOMAIN;
158}
159
160pub type CircleRosterEntry = Signed<CircleRosterEntryBody>;
161
162impl CircleRosterEntry {
163    pub fn founder(
164        store_root_hash: ObjectHash,
165        circle_id: CircleId,
166        device_id: &str,
167        stream_id: AuthorStreamId,
168        owner_grant: MembershipGrantId,
169        signer: &dyn coven_keys::keys::IdentityKeyAuthority,
170    ) -> Self {
171        let author_pubkey = keys::public_key_hex(signer);
172        Signed::sign(
173            CircleRosterEntryBody {
174                store_root_hash,
175                circle_id,
176                author_pubkey: author_pubkey.clone(),
177                device_id: device_id.to_string(),
178                stream_id,
179                author_owner_grant: owner_grant.clone(),
180                seq: 1,
181                previous_hash: None,
182                dependencies: Vec::new(),
183                resolution_dependencies: Vec::new(),
184                change: CircleRosterChange::Founder {
185                    member_pubkey: author_pubkey,
186                    grant_id: owner_grant,
187                },
188            },
189            signer,
190        )
191    }
192
193    pub(crate) fn entry_hash(&self) -> ObjectHash {
194        self.hash()
195    }
196
197    pub fn coord(&self) -> CircleRosterCoord {
198        CircleRosterCoord {
199            author_pubkey: self.author_pubkey.clone(),
200            device_id: self.device_id.clone(),
201            stream_id: self.stream_id,
202            author_owner_grant: self.author_owner_grant.clone(),
203            seq: self.seq,
204            entry_hash: self.entry_hash(),
205        }
206    }
207
208    pub fn verify(&self) -> bool {
209        let own_stream = self.coord().stream_key();
210        let dependency_streams = || self.dependencies.iter().map(CircleRosterCoord::stream_key);
211        let position_is_valid = match &self.change {
212            CircleRosterChange::Founder {
213                member_pubkey,
214                grant_id,
215                ..
216            } => {
217                self.seq == 1
218                    && self.previous_hash.is_none()
219                    && self.dependencies.is_empty()
220                    && self.resolution_dependencies.is_empty()
221                    && member_pubkey == &self.author_pubkey
222                    && grant_id == &self.author_owner_grant
223            }
224            CircleRosterChange::ResolutionActivation { .. } => causal_grants::starts_author_stream(
225                self.seq,
226                self.previous_hash,
227                &own_stream,
228                dependency_streams(),
229            ),
230            CircleRosterChange::SetMember { .. } | CircleRosterChange::RemoveMember { .. } => {
231                causal_grants::author_stream_position_is_valid(
232                    self.seq,
233                    self.previous_hash,
234                    &own_stream,
235                    dependency_streams(),
236                )
237            }
238        };
239        !self.author_pubkey.is_empty()
240            && !self.device_id.is_empty()
241            && position_is_valid
242            && self
243                .dependencies
244                .windows(2)
245                .all(|pair| pair[0].stream_key() < pair[1].stream_key())
246            && self
247                .resolution_dependencies
248                .windows(2)
249                .all(|pair| pair[0] < pair[1])
250            && match &self.change {
251                CircleRosterChange::SetMember { owner_barriers, .. }
252                | CircleRosterChange::RemoveMember { owner_barriers, .. } => {
253                    owner_barriers.values().all(|barrier| {
254                        barrier
255                            .observed_streams
256                            .windows(2)
257                            .all(|pair| pair[0].stream_key() < pair[1].stream_key())
258                    })
259                }
260                CircleRosterChange::Founder { .. } => true,
261                CircleRosterChange::ResolutionActivation { resolution } => {
262                    resolution.resolver_pubkey == self.author_pubkey
263                        && self.author_owner_grant
264                            == derive_circle_resolution_grant(
265                                &resolution.conflict_hash,
266                                &resolution.resolver_pubkey,
267                            )
268                        && self
269                            .resolution_dependencies
270                            .binary_search(resolution)
271                            .is_ok()
272                }
273            }
274            && self.verify_by(&self.author_pubkey).is_ok()
275    }
276}
277
278/// The wire body of one Circle roster head. Every field here is signed.
279#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
280#[serde(deny_unknown_fields)]
281pub struct CircleRosterHeadBody {
282    pub store_root_hash: ObjectHash,
283    pub circle_id: CircleId,
284    pub author_pubkey: String,
285    pub device_id: String,
286    pub stream_id: AuthorStreamId,
287    pub author_owner_grant: MembershipGrantId,
288    pub seq: u64,
289    pub tip_hash: ObjectHash,
290    pub tip: ExactObjectRef,
291    pub successor: SuccessorLink,
292    pub resolutions: Vec<CircleRosterConflictResolutionRef>,
293}
294
295impl SignedBody for CircleRosterHeadBody {
296    const DOMAIN: &'static [u8] = ROSTER_HEAD_DOMAIN;
297}
298
299pub type CircleRosterHead = Signed<CircleRosterHeadBody>;
300
301impl CircleRosterHead {
302    pub fn signed(
303        entry: &CircleRosterEntry,
304        tip: ExactObjectRef,
305        successor: SuccessorLink,
306        signer: &UserKeypair,
307    ) -> Self {
308        Self::signed_with_resolutions(
309            entry,
310            tip,
311            successor,
312            entry.resolution_dependencies.clone(),
313            signer,
314        )
315    }
316
317    pub(crate) fn signed_with_resolutions(
318        entry: &CircleRosterEntry,
319        tip: ExactObjectRef,
320        successor: SuccessorLink,
321        resolutions: Vec<CircleRosterConflictResolutionRef>,
322        signer: &UserKeypair,
323    ) -> Self {
324        Signed::sign(
325            CircleRosterHeadBody {
326                store_root_hash: entry.store_root_hash,
327                circle_id: entry.circle_id,
328                author_pubkey: entry.author_pubkey.clone(),
329                device_id: entry.device_id.clone(),
330                stream_id: entry.stream_id,
331                author_owner_grant: entry.author_owner_grant.clone(),
332                seq: entry.seq,
333                tip_hash: entry.entry_hash(),
334                tip,
335                successor,
336                resolutions,
337            },
338            signer,
339        )
340    }
341
342    pub fn head_hash(&self) -> ObjectHash {
343        self.hash()
344    }
345
346    pub fn verify_for_registration(&self, registration: &StoreDeviceRegistration) -> bool {
347        self.seq > 0
348            && !self.device_id.is_empty()
349            && self.device_id == registration.device_id.to_string()
350            && self.resolutions.windows(2).all(|pair| pair[0] < pair[1])
351            && self.verify_by(&registration.device_signing_pubkey).is_ok()
352    }
353    pub fn entry_coord(&self) -> CircleRosterCoord {
354        CircleRosterCoord {
355            author_pubkey: self.author_pubkey.clone(),
356            device_id: self.device_id.clone(),
357            stream_id: self.stream_id,
358            author_owner_grant: self.author_owner_grant.clone(),
359            seq: self.seq,
360            entry_hash: self.tip_hash,
361        }
362    }
363}
364
365#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
366#[serde(deny_unknown_fields)]
367pub struct CircleRosterHeadRef {
368    pub coord: CircleRosterCoord,
369    pub head_hash: ObjectHash,
370    pub object: ExactObjectRef,
371}
372
373impl CircleRosterHeadRef {
374    pub fn from_stored_head(head: &CircleRosterHead, object: ExactObjectRef) -> Self {
375        Self {
376            coord: head.entry_coord(),
377            head_hash: head.head_hash(),
378            object,
379        }
380    }
381}
382
383#[derive(Debug, Clone)]
384pub struct ExactCircleRosterHead {
385    head: CircleRosterHead,
386    reference: CircleRosterHeadRef,
387}
388
389impl ExactCircleRosterHead {
390    pub fn bind(
391        head: CircleRosterHead,
392        reference: CircleRosterHeadRef,
393    ) -> Result<Self, CircleRosterError> {
394        if CircleRosterHeadRef::from_stored_head(&head, reference.object.clone()) != reference {
395            return Err(CircleRosterError::MissingConflictHeads);
396        }
397        Ok(Self { head, reference })
398    }
399
400    pub fn head(&self) -> &CircleRosterHead {
401        &self.head
402    }
403
404    pub fn reference(&self) -> &CircleRosterHeadRef {
405        &self.reference
406    }
407}
408
409#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
410#[serde(deny_unknown_fields)]
411pub struct MergeCircleRosterStateRef {
412    pub heads: Vec<CircleRosterHeadRef>,
413    pub resolutions: Vec<CircleRosterConflictResolutionRef>,
414    pub state_hash: ObjectHash,
415}
416
417pub(crate) type CircleRosterStateRef = MergeCircleRosterStateRef;
418
419#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
420#[serde(deny_unknown_fields)]
421pub struct CircleGrantRecord {
422    pub member_pubkey: String,
423    pub role: CircleRole,
424    pub creation_authority: CircleGrantCreationAuthority,
425}
426
427#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
428#[serde(rename_all = "snake_case", deny_unknown_fields)]
429pub enum CircleGrantCreationAuthority {
430    Entry(CircleRosterCoord),
431    ConflictResolution(CircleRosterConflictResolutionRef),
432}
433
434#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
435#[serde(rename_all = "snake_case", deny_unknown_fields)]
436pub enum CircleGrantRetirement {
437    Entry {
438        authority: CircleRosterCoord,
439        owner_barrier: Option<CircleOwnerGrantBarrier>,
440    },
441    ConflictResolution(CircleRosterConflictResolutionRef),
442}
443
444#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
445pub enum CircleRosterError {
446    #[error("Circle roster is empty")]
447    Empty,
448    #[error("Circle roster entry {0} has an invalid signature or position")]
449    InvalidEntry(usize),
450    #[error("Circle roster entry {index} belongs to another Store or Circle")]
451    ContextMismatch { index: usize },
452    #[error("Circle roster founder does not derive its Circle identity")]
453    InvalidFounderIdentity,
454    #[error("Circle roster signer {0} has no active Owner assignment")]
455    SignerIsNotOwner(String),
456    #[error("Circle roster member {0} has no active assignment")]
457    NotAMember(String),
458    #[error("Circle roster author stream contains a pruned suffix and cannot be extended")]
459    PrunedAuthorStream,
460    #[error("Circle roster sequence {current} has no representable successor")]
461    SequenceExhausted { current: u64 },
462    #[error("Circle roster has an unresolved semantic conflict")]
463    Conflict,
464    #[error("Circle roster conflict is missing its exact signed raw heads")]
465    MissingConflictHeads,
466    #[error("Circle roster conflict resolution does not name exact validated conflict evidence")]
467    InvalidConflictResolution,
468    #[error("checkpoint lacks the exact record for Circle grant {grant}")]
469    MissingCheckpointGrant { grant: MembershipGrantId },
470    #[error("checkpoint lacks retirement evidence for Circle grant {grant}")]
471    MissingCheckpointRetirementEvidence { grant: MembershipGrantId },
472    #[error("Circle roster causal history is empty")]
473    CausalEmpty,
474    #[error("Circle roster stream {stream:?} has conflicting entries at sequence {seq}")]
475    CausalConflictingSequence {
476        stream: CircleAuthorStreamKey,
477        seq: u64,
478    },
479    #[error("Circle roster stream {stream:?} is missing sequence {seq}")]
480    CausalMissingSequence {
481        stream: CircleAuthorStreamKey,
482        seq: u64,
483    },
484    #[error("Circle roster entry {index} has predecessor {actual:?}, expected {expected:?}")]
485    CausalBrokenStreamLink {
486        index: usize,
487        expected: Option<ObjectHash>,
488        actual: Option<ObjectHash>,
489    },
490    #[error("Circle roster entry {index} does not carry its exact own-stream dependency")]
491    CausalMissingOwnDependency { index: usize },
492    #[error("Circle roster entry {index} has a dependency under the wrong stream key")]
493    CausalDependencyStreamMismatch { index: usize },
494    #[error("Circle roster entry {index} depends on missing coordinate {dependency:?}")]
495    CausalMissingDependency {
496        index: usize,
497        dependency: CircleRosterCoord,
498    },
499    #[error("Circle roster dependency graph contains a cycle")]
500    CausalDependencyCycle,
501    #[error("Circle roster causal founder is invalid")]
502    CausalInvalidFounder,
503    #[error("Circle roster entry {index} author is not active under Owner grant {grant}")]
504    CausalAuthorGrantInactive {
505        index: usize,
506        grant: MembershipGrantId,
507    },
508    #[error("Circle roster entry {index} creates already-defined grant {grant}")]
509    CausalDuplicateGrant {
510        index: usize,
511        grant: MembershipGrantId,
512    },
513    #[error(
514        "Circle roster entry {index} replaces or removes grant {grant} owned by another member"
515    )]
516    CausalGrantOwnerMismatch {
517        index: usize,
518        grant: MembershipGrantId,
519    },
520    #[error("Circle roster entry {index} does not name the exact active grants for member {member_pubkey}")]
521    CausalGrantSetMismatch { index: usize, member_pubkey: String },
522    #[error("Circle roster entry {index} removes no exact grants")]
523    CausalEmptyRemoval { index: usize },
524    #[error("Circle roster entry {index} removes Owner grant {grant} without its exact observed frontier")]
525    CausalMissingOwnerRevocationBarrier {
526        index: usize,
527        grant: MembershipGrantId,
528    },
529    #[error("Circle roster entry {index} carries an invalid frontier for Owner grant {grant}")]
530    CausalInvalidOwnerRevocationBarrier {
531        index: usize,
532        grant: MembershipGrantId,
533    },
534    #[error("Circle roster causal history leaves no active Owner")]
535    CausalNoActiveOwner,
536    #[error(
537        "Circle roster revocation cycle has {sources} sources, exceeding the protocol limit of {maximum}"
538    )]
539    RevocationCycleTooWide { sources: usize, maximum: usize },
540}
541
542impl From<CausalGrantError<CircleRosterCoord>> for CircleRosterError {
543    fn from(error: CausalGrantError<CircleRosterCoord>) -> Self {
544        match error {
545            CausalGrantError::Empty => Self::CausalEmpty,
546            CausalGrantError::ConflictingSequence { stream, seq } => {
547                Self::CausalConflictingSequence { stream, seq }
548            }
549            CausalGrantError::MissingSequence { stream, seq } => {
550                Self::CausalMissingSequence { stream, seq }
551            }
552            CausalGrantError::BrokenStreamLink {
553                index,
554                expected,
555                actual,
556            } => Self::CausalBrokenStreamLink {
557                index,
558                expected,
559                actual,
560            },
561            CausalGrantError::MissingOwnDependency { index } => {
562                Self::CausalMissingOwnDependency { index }
563            }
564            CausalGrantError::DependencyStreamMismatch { index } => {
565                Self::CausalDependencyStreamMismatch { index }
566            }
567            CausalGrantError::MissingDependency { index, dependency } => {
568                Self::CausalMissingDependency { index, dependency }
569            }
570            CausalGrantError::DependencyCycle => Self::CausalDependencyCycle,
571            CausalGrantError::InvalidFounder => Self::CausalInvalidFounder,
572            CausalGrantError::AuthorGrantInactive { index, grant } => {
573                Self::CausalAuthorGrantInactive { index, grant }
574            }
575            CausalGrantError::DuplicateGrant { index, grant } => {
576                Self::CausalDuplicateGrant { index, grant }
577            }
578            CausalGrantError::GrantOwnerMismatch { index, grant } => {
579                Self::CausalGrantOwnerMismatch { index, grant }
580            }
581            CausalGrantError::GrantSetMismatch {
582                index,
583                member_pubkey,
584            } => Self::CausalGrantSetMismatch {
585                index,
586                member_pubkey,
587            },
588            CausalGrantError::EmptyRemoval { index } => Self::CausalEmptyRemoval { index },
589            CausalGrantError::MissingOwnerRevocationBarrier { index, grant } => {
590                Self::CausalMissingOwnerRevocationBarrier { index, grant }
591            }
592            CausalGrantError::InvalidOwnerRevocationBarrier { index, grant } => {
593                Self::CausalInvalidOwnerRevocationBarrier { index, grant }
594            }
595            CausalGrantError::NoActiveOwner => Self::CausalNoActiveOwner,
596            CausalGrantError::RevocationCycleTooWide { sources, maximum } => {
597                Self::RevocationCycleTooWide { sources, maximum }
598            }
599        }
600    }
601}
602
603#[cfg(test)]
604mod authority_tests;
coven_protocol/circle_roster.rs

coven_protocol/
circle_roster.rs
