Skip to main content

coven_sync/
sequence_bootstrap.rs

1//! The key scan: the first store keys of an installation whose custody
2//! holds none, and the registration that follows its admission (§13), and
3//! the circle key a stuck slot waits on (§5.4, §12.1).
4
5use super::{next_slot, sequence_read::SlotStep, SequenceSync, Session};
6use crate::{
7    floor_object, object_input::ObjectInput, slot_object, snapshot_object::RoutedKey, SyncError,
8};
9use coven_crypto::{MemberIdentity, StoreKeyring};
10use coven_database::LoadStep;
11use coven_format::{floor::OriginalSlot, sealed_slot::SlotObjectPrefix};
12use coven_foundation::id_source::{CircleId, DeviceId, KeyId};
13use coven_foundation::progress::ProgressReport;
14use coven_merge::{Audience, Slot, SlotRange};
15use coven_storage::{ObjectPath, StorageFailure};
16
17/// What storage supplied to a member that holds no store key yet.
18pub(crate) enum Bootstrap {
19    /// Copies routed to this member opened these keys. They stay tentative
20    /// until the history introducing them authenticates.
21    Keys(StoreKeyring),
22    /// The sequence exists, but no copy for this member was found; reading
23    /// it needs this key.
24    Missing(KeyId),
25    /// No copy this member's pair opens was found, but one for the member
26    /// sealed to another pair was: its replacement's, which this pair can't
27    /// follow (§12.3).
28    Replaced,
29    /// Neither a floor nor a first slot exists.
30    Empty,
31}
32
33/// What the key scan reads of one slot.
34struct ScannedSlot {
35    prefix: SlotObjectPrefix,
36    /// The slot's bytes, when one of its boxes is sealed to a pair this
37    /// member holds.
38    copy: Option<OriginalSlot>,
39}
40
41/// How far the scan for the circle key a stuck slot waits on got.
42#[derive(Clone, Copy)]
43pub(crate) struct StuckScan {
44    /// The first slot the scan read: the one after the stop, or the floor's
45    /// first kept slot once retention has deleted the stop.
46    start: Slot,
47    /// The circle key it waits on.
48    key: KeyId,
49    /// The next slot the scan reads.
50    next: Slot,
51}
52
53/// How this member's binding stands in the applied history (§13).
54#[derive(Clone, Copy, Debug, PartialEq, Eq)]
55pub(crate) enum MemberBinding {
56    /// The member id is bound to this installation's pair, by `device`.
57    Bound { device: DeviceId },
58    /// The member id is absent from the applied history.
59    Absent,
60    /// The member id is bound to another pair.
61    Replaced,
62    /// The member was removed.
63    Removed,
64}
65
66impl SequenceSync {
67    /// Custody's keyring, or the store keys this member's own copies supply
68    /// when custody holds none (§13.1). A new installation's keys enter
69    /// custody with the slots that apply them. An installation that applied
70    /// history before custody lost its keys reconstructs that history with
71    /// the copies' keys; authenticating it admits them to custody (§12.1).
72    pub(crate) async fn ring(
73        &self,
74        session: &mut Session,
75        member: &MemberIdentity,
76    ) -> Result<StoreKeyring, SyncError> {
77        self.ring_reporting(session, member, None).await
78    }
79
80    /// The keyring as `ring` finds it, reporting a scan for this member's
81    /// copies to `progress`, when given, as loading's FindingKeys step
82    /// (§13.4).
83    async fn ring_reporting(
84        &self,
85        session: &mut Session,
86        member: &MemberIdentity,
87        progress: Option<&mut ProgressReport<LoadStep>>,
88    ) -> Result<StoreKeyring, SyncError> {
89        let mut ring = match self.keys.read()? {
90            Some(ring) => ring,
91            None => match self
92                .bootstrap_keys(session, member, progress.map(KeyScan::new).as_mut())
93                .await?
94            {
95                Bootstrap::Keys(ring) => ring,
96                Bootstrap::Missing(key) => {
97                    return Err(SyncError::KeyUnavailable { audience: Audience::Store, key })
98                }
99                Bootstrap::Replaced => {
100                    return Err(SyncError::MemberKeysReplaced { member: member.member() })
101                }
102                Bootstrap::Empty => {
103                    return Err(StorageFailure::NotFound
104                        .with_source("the store has neither a floor nor a first slot")
105                        .into())
106                }
107            },
108        };
109        self.restore_history(session, &mut ring, member).await?;
110        Ok(ring)
111    }
112
113    /// An installation that applied history before it held keys, such as a
114    /// join stopped while loading, reconstructs that history once keys open
115    /// it, so the bindings it applied count again (§12.1, §13.2).
116    pub(crate) async fn restore_history(
117        &self,
118        session: &mut Session,
119        ring: &mut StoreKeyring,
120        member: &MemberIdentity,
121    ) -> Result<(), SyncError> {
122        if session.locked {
123            let originals = self.database.original_slots().await?;
124            session.history = super::History::restore(&originals, self.store(), ring, member)?;
125            self.keys.persist(ring)?;
126            session.locked = false;
127        }
128        Ok(())
129    }
130
131    /// The store key that sealed this installation's newest applied original
132    /// while custody holds no store key: syncing needs it unlocked first (§12.4).
133    pub async fn missing_store_key(
134        database: &coven_database::StoreDatabase,
135        keys: &coven_crypto::custody::KeySession<StoreKeyring>,
136    ) -> Result<Option<KeyId>, SyncError> {
137        if keys.read()?.is_some() {
138            return Ok(None);
139        }
140        let Some(newest) =
141            database.original_slots().await?.into_iter().max_by_key(|original| original.slot)
142        else {
143            return Ok(None);
144        };
145        let length = coven_format::sealed_slot::SlotObjectPrefix::length(&newest.object)?;
146        let prefix = coven_format::sealed_slot::SlotObjectPrefix::decode(
147            newest.object.get(..length).ok_or(coven_format::Error::Truncated)?,
148        )?;
149        Ok(Some(prefix.key))
150    }
151
152    /// Open this member's store keys from their copies in storage, keep them
153    /// in custody and read forward, without sending (§12.1, E5). Loading's
154    /// steps go to `subscribe_progress` as they run (§13.4).
155    pub async fn unlock(&self) -> Result<(), SyncError> {
156        let mut session = self.session.lock().await;
157        self.unlock_reporting(&mut session, ProgressReport::of(&self.progress, self.clock.clone()))
158            .await
159    }
160
161    async fn unlock_reporting(
162        &self,
163        session: &mut Session,
164        mut progress: ProgressReport<LoadStep>,
165    ) -> Result<(), SyncError> {
166        let member = self.member.read()?.ok_or(StorageFailure::MemberKeysMissing)?;
167        let mut ring = self.ring_reporting(session, &member, Some(&mut progress)).await?;
168        self.read_forward_reporting(session, &mut ring, &member, Some(&mut progress)).await?;
169        self.keys.persist(&ring)?;
170        Ok(())
171    }
172
173    /// The first load of a store a join published once it found its
174    /// admission: read forward from nothing with the keys its copies opened,
175    /// reporting loading's steps into `progress`, then stop for good if the
176    /// history refused that admission (§13.2).
177    pub async fn load_joined(
178        &self,
179        progress: tokio::sync::watch::Sender<
180            Option<coven_foundation::progress::Progress<LoadStep>>,
181        >,
182    ) -> Result<(), SyncError> {
183        let mut session = self.session.lock().await;
184        self.unlock_reporting(&mut session, ProgressReport::new(progress, self.clock.clone()))
185            .await?;
186        let member = self.member.read()?.ok_or(StorageFailure::MemberKeysMissing)?;
187        self.check_admitted(&session, &member).await
188    }
189
190    /// Start the key scan after `slot`: a joiner's copies follow its invite.
191    pub(crate) fn scan_after(&self, session: &mut Session, after: u64) -> Result<(), SyncError> {
192        session.scanned = session.scanned.max(next_slot(after)?);
193        Ok(())
194    }
195
196    /// The floor supplies copies and the first kept slot before keys are held.
197    /// A miss rereads it, since retention may have passed the scan meanwhile.
198    /// This applies nothing and advances no applied slot. A scan without keys
199    /// keeps its position only on success; opened keys must remain discoverable
200    /// until authenticated history retains them in custody. A scan that reads
201    /// a slot reports to `scan`, when given, once it has found where the
202    /// sequence ends (§13.4).
203    pub(crate) async fn bootstrap_keys(
204        &self,
205        session: &mut Session,
206        member: &MemberIdentity,
207        mut scan: Option<&mut KeyScan<'_>>,
208    ) -> Result<Bootstrap, SyncError> {
209        let started = self.clock.elapsed();
210        let mut floors = 0;
211        let mut scanned = 0;
212        let mut bytes = 0;
213        let mut keys = Vec::new();
214        let mut needed = None;
215        let mut routed_past = false;
216        let mut next = session.scanned;
217        let mut missed = false;
218        loop {
219            let first = match floor_object::routed_keys(
220                &self.database,
221                self.storage.as_ref(),
222                &ObjectPath::floor(self.store()),
223                member,
224            )
225            .await?
226            {
227                Some(routing) => {
228                    floors += 1;
229                    needed = Some(routing.key);
230                    keys.extend(routing.keys);
231                    routed_past |= routing.routed_past;
232                    routing.first
233                }
234                None => Slot::FIRST,
235            };
236            if keys.iter().any(|key| matches!(key, RoutedKey::Store(_)))
237                || (missed && first <= next)
238            {
239                break;
240            }
241            next = next.max(first);
242            let mut reads = super::SlotReads::new(self, SlotRange::new(next, u64::MAX));
243            // The end of the sequence, found once this pass reads a slot.
244            let mut located = None;
245            while let Some(input) = reads.next().await? {
246                scanned += 1;
247                bytes += input.object().size;
248                let read = self.scan_slot(input, next, member).await?;
249                needed.get_or_insert(read.prefix.key);
250                // A key-copy slot's box, or an admission's (D9).
251                routed_past |= read.prefix.kind.boxes().any(|(_, copy)| {
252                    copy.routing.member == member.member() && !copy.routing.held_by(member)
253                });
254                if let Some(original) = &read.copy {
255                    keys.extend(crate::snapshot_object::routed(original, self.store(), member)?.0);
256                }
257                if let Some(scan) = scan.as_deref_mut() {
258                    let end = match located {
259                        Some(end) => end,
260                        None => *located.insert(self.locate_end(next.get()).await?),
261                    };
262                    scan.count(next.get(), end);
263                }
264                next = next_slot(next.get())?;
265            }
266            if keys.iter().any(|key| matches!(key, RoutedKey::Store(_))) {
267                break;
268            }
269            missed = true;
270        }
271        let mut ring: Option<StoreKeyring> = None;
272        let mut circles = Vec::new();
273        for key in keys {
274            match (key, &mut ring) {
275                (RoutedKey::Store(key), None) => ring = Some(StoreKeyring::new(key)),
276                (key @ RoutedKey::Store(_), Some(ring)) => key.insert(ring)?,
277                (key @ RoutedKey::Circle(_), _) => circles.push(key),
278            }
279        }
280        let result = match (ring, needed) {
281            (Some(mut ring), _) => {
282                for key in circles {
283                    key.insert(&mut ring)?;
284                }
285                Bootstrap::Keys(ring)
286            }
287            (None, _) if routed_past => Bootstrap::Replaced,
288            (None, Some(key)) => Bootstrap::Missing(key),
289            (None, None) => Bootstrap::Empty,
290        };
291        if !matches!(result, Bootstrap::Keys(_)) {
292            session.scanned = next;
293        }
294        tracing::info!(
295            found = matches!(result, Bootstrap::Keys(_)),
296            floors,
297            scanned_slots = scanned,
298            bytes,
299            time = ?(self.clock.elapsed() - started),
300            "read this member's store keys from their copies"
301        );
302        Ok(result)
303    }
304
305    /// Read what the key scan looks at in `slot`, whose bytes `input` holds:
306    /// its clear prefix, and its whole bytes when a box in it, a key copy's
307    /// or an admission's, is sealed to a pair this member holds (D9).
308    async fn scan_slot(
309        &self,
310        input: ObjectInput,
311        slot: Slot,
312        member: &MemberIdentity,
313    ) -> Result<ScannedSlot, SyncError> {
314        let path = self.path(slot);
315        let read = async {
316            let prefix = slot_object::clear_prefix(input.local_bytes().await?, &path)?;
317            let copy = if prefix.kind.boxes().any(|(_, copy)| copy.routing.held_by(member)) {
318                let object = slot_object::read_exact(
319                    &mut input.local_bytes().await?,
320                    (input.object().size).min(coven_format::sequence::MAX_BOUNDED_SLOT as u64)
321                        as usize,
322                    &path,
323                )?;
324                Some(OriginalSlot { slot, object })
325            } else {
326                None
327            };
328            Ok::<_, SyncError>(ScannedSlot { prefix, copy })
329        }
330        .await;
331        // The scan is done with the slot's bytes, read or refused: they stay
332        // for the reader that applies the slot, but count against the input
333        // budget only as bytes it may evict (§21.1).
334        input.release().await?;
335        read
336    }
337
338    /// Scan the slots from `start` for a copy of `circle`'s key `key`, sealed
339    /// to this member's pair, which a stuck slot waits on: from the slot
340    /// after the stop, or from the floor's first kept slot once retention has
341    /// deleted it. A copy found comes with the slot that carries it.
342    /// Reading in order never reaches a copy in a later slot, so this scan is
343    /// what ends the wait. `hash` is the key's applied commitment: the copy's
344    /// key is checked against it, so the key it gives is accepted at once
345    /// (§5.4, §12.1).
346    ///
347    /// The scan reads each slot's clear prefix and applies nothing. It goes
348    /// on from where an earlier scan for the same stop and key got, since
349    /// slots never change. At a slot whose prefix is damaged, or whose copy of
350    /// the key doesn't open or match, it stops without reading past it, and
351    /// the next scan starts there. A failed read fails it.
352    pub(crate) async fn scan_for_stuck_key(
353        &self,
354        session: &mut Session,
355        member: &MemberIdentity,
356        start: Slot,
357        circle: CircleId,
358        key: KeyId,
359        hash: &[u8; 32],
360    ) -> Result<Option<(Slot, RoutedKey)>, SyncError> {
361        let started = self.clock.elapsed();
362        let from = match session.stuck_scan {
363            Some(scan) if scan.start == start && scan.key == key => scan.next,
364            _ => start,
365        };
366        let mut next = from;
367        let mut reads = super::SlotReads::new(self, SlotRange::new(next, u64::MAX));
368        let found = loop {
369            let opened = async {
370                let Some(input) = reads.next().await? else {
371                    return Ok(None);
372                };
373                let read = self.scan_slot(input, next, member).await?;
374                let wanted = read.prefix.kind.boxes().any(|(_, copy)| {
375                    copy.routing.audience == Audience::Circle(circle) && copy.routing.key == key
376                });
377                let opened = match read.copy.filter(|_| wanted) {
378                    Some(original) => {
379                        crate::snapshot_object::routed(&original, self.store(), member)?
380                            .0
381                            .into_iter()
382                            .find(|opened| {
383                                matches!(opened, RoutedKey::Circle(found)
384                                    if found.circle() == circle && found.id() == key)
385                            })
386                    }
387                    None => None,
388                };
389                if let Some(opened) = &opened {
390                    opened.check_hash(hash).map_err(|error| {
391                        crate::write_object::damaged(
392                            &self.path(next),
393                            crate::Refusal::WrongIdentity {
394                                cause: Some(std::sync::Arc::new(error)),
395                            },
396                        )
397                    })?;
398                }
399                Ok::<_, SyncError>(Some(opened))
400            }
401            .await;
402            match opened {
403                // The end of the sequence.
404                Ok(None) => break None,
405                Ok(Some(opened)) => {
406                    let at = next;
407                    next = next_slot(next.get())?;
408                    if let Some(opened) = opened {
409                        break Some((at, opened));
410                    }
411                }
412                Err(error @ SyncError::Damaged(_)) => {
413                    tracing::warn!(
414                        slot = next.get(),
415                        "the scan for a stuck slot's circle key stops at a damaged slot: {error}"
416                    );
417                    break None;
418                }
419                Err(error) => {
420                    session.stuck_scan = Some(StuckScan { start, key, next });
421                    return Err(error);
422                }
423            }
424        };
425        session.stuck_scan = Some(StuckScan { start, key, next });
426        tracing::info!(
427            start = start.get(),
428            found = found.is_some(),
429            scanned_slots = next.get() - from.get(),
430            time = ?(self.clock.elapsed() - started),
431            "scanned ahead for the circle key a stuck slot needs"
432        );
433        Ok(found)
434    }
435
436    /// This member's binding in the applied history.
437    pub(crate) fn admission(&self, session: &Session, member: &MemberIdentity) -> MemberBinding {
438        let keys = member.keys().public_keys();
439        match session.history.state.members.get(&member.member()) {
440            None => MemberBinding::Absent,
441            Some(current) if current.removed => MemberBinding::Removed,
442            Some(current) if current.keys != keys => MemberBinding::Replaced,
443            Some(_) => match session
444                .history
445                .bindings
446                .iter()
447                .rev()
448                .find(|binding| binding.member == member.member() && binding.keys == keys)
449            {
450                Some(binding) => MemberBinding::Bound { device: binding.device },
451                None => MemberBinding::Replaced,
452            },
453        }
454    }
455}
456
457/// Loading's FindingKeys step across one operation's scans for this
458/// member's copies: a join's check may scan twice, and the second scan
459/// continues the first's count (§13.4).
460pub(crate) struct KeyScan<'a> {
461    progress: &'a mut ProgressReport<LoadStep>,
462    step: Option<SlotStep>,
463}
464
465impl<'a> KeyScan<'a> {
466    /// Report the scans into `progress`.
467    pub(crate) fn new(progress: &'a mut ProgressReport<LoadStep>) -> Self {
468        Self { progress, step: None }
469    }
470
471    /// Slot `at` is read, and the sequence is known to reach `end`. The step
472    /// begins at the first slot a scan reads.
473    fn count(&mut self, at: u64, end: u64) {
474        self.step.get_or_insert_with(|| SlotStep::new(LoadStep::FindingKeys, at - 1)).count(
475            self.progress,
476            at,
477            end,
478        );
479    }
480}
481
482impl SequenceSync {
483    /// Fail as `restorable` does once the applied history has replaced or
484    /// removed the pair this installation holds after binding it, as for a
485    /// device restoring from an old code (§13.1). A pair the history never
486    /// bound, such as a joiner's before its admission applies, has left
487    /// nothing.
488    pub(crate) fn check_left(
489        &self,
490        session: &Session,
491        member: &MemberIdentity,
492    ) -> Result<(), SyncError> {
493        match self.admission(session, member) {
494            admission @ (MemberBinding::Replaced | MemberBinding::Removed)
495                if self.pair_bound(session, member) =>
496            {
497                restorable(admission, member)
498            }
499            _ => Ok(()),
500        }
501    }
502}
503
504/// Check a restored member's pair before it can register: an old restore
505/// code cannot bind its keys back (§13.1).
506pub(crate) fn restorable(
507    admission: MemberBinding,
508    member: &MemberIdentity,
509) -> Result<(), SyncError> {
510    match admission {
511        MemberBinding::Bound { .. } => Ok(()),
512        MemberBinding::Removed => Err(SyncError::Removed(coven_database::Removal::Member)),
513        MemberBinding::Replaced => Err(SyncError::MemberKeysReplaced { member: member.member() }),
514        MemberBinding::Absent => Err(SyncError::Rejected(crate::OperationRejection::TargetGone(
515            crate::EntryTarget::Member(member.member()),
516        ))),
517    }
518}
519
520#[cfg(test)]
521#[path = "sequence_bootstrap_tests.rs"]
522mod tests;