Skip to main content

hop_consensus/
lib.rs

1#![forbid(unsafe_code)]
2#![deny(missing_docs)]
3//! Bounded deterministic sequencing for HOP channel actions.
4//!
5//! This crate does not implement distributed consensus. It provides a local
6//! sequencing contract that a replicated consensus protocol can drive.
7
8use std::collections::{HashSet, VecDeque};
9
10use hop_actions::{hash_action, Action};
11use hop_channels::{Channel, ChannelError};
12
13/// Default maximum number of actions waiting in memory.
14pub const DEFAULT_QUEUE_CAPACITY: usize = 10_000;
15
16/// An immutable prefix plan produced from the current queue.
17#[derive(Clone, Debug, PartialEq, Eq)]
18pub struct Plan {
19    /// Planned actions in deterministic application order.
20    pub actions: Vec<Action>,
21}
22
23/// Receipt for an action committed to a channel.
24#[derive(Clone, Debug, PartialEq, Eq)]
25pub struct Receipt {
26    /// Canonical action hash.
27    pub action_hash: [u8; 32],
28    /// Channel height after the action committed.
29    pub height: u64,
30}
31
32/// Result of applying a valid queue plan.
33#[derive(Debug)]
34pub struct ApplyReport {
35    /// Receipts for the committed prefix.
36    pub receipts: Vec<Receipt>,
37    /// Failure that stopped application, if any.
38    pub failure: Option<ChannelError>,
39}
40
41/// Sequencer admission or plan errors.
42#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
43#[non_exhaustive]
44pub enum SequencerError {
45    /// The bounded queue has reached its configured capacity.
46    #[error("sequencer queue is full")]
47    QueueFull,
48    /// The same canonical action is already pending.
49    #[error("action is already pending")]
50    DuplicatePending,
51    /// The supplied plan is not an exact prefix of the current queue.
52    #[error("plan is stale or does not match the pending queue")]
53    StalePlan,
54}
55
56/// Contract implemented by deterministic local action sequencers.
57pub trait Consensus {
58    /// Admits one action and returns its canonical identifier.
59    fn admit(&mut self, action: Action) -> Result<[u8; 32], SequencerError>;
60    /// Plans at most `limit` actions from the current queue prefix.
61    fn plan(&self, limit: usize) -> Plan;
62    /// Applies an exact plan, retaining the failed action and unattempted suffix.
63    fn apply_plan(
64        &mut self,
65        plan: Plan,
66        channel: &mut Channel,
67    ) -> Result<ApplyReport, SequencerError>;
68}
69
70/// A bounded, in-memory, first-in-first-out HOP action sequencer.
71pub struct DeterministicSequencer {
72    capacity: usize,
73    queue: VecDeque<Action>,
74    pending: HashSet<[u8; 32]>,
75}
76
77impl DeterministicSequencer {
78    /// Creates a sequencer with a nonzero bounded capacity.
79    pub fn with_capacity(capacity: usize) -> Self {
80        Self {
81            capacity,
82            queue: VecDeque::new(),
83            pending: HashSet::new(),
84        }
85    }
86
87    /// Returns the number of pending actions.
88    pub fn len(&self) -> usize {
89        self.queue.len()
90    }
91
92    /// Returns whether no actions are pending.
93    pub fn is_empty(&self) -> bool {
94        self.queue.is_empty()
95    }
96
97    /// Returns the configured queue capacity.
98    pub const fn capacity(&self) -> usize {
99        self.capacity
100    }
101}
102
103impl Default for DeterministicSequencer {
104    fn default() -> Self {
105        Self::with_capacity(DEFAULT_QUEUE_CAPACITY)
106    }
107}
108
109impl Consensus for DeterministicSequencer {
110    fn admit(&mut self, action: Action) -> Result<[u8; 32], SequencerError> {
111        if self.queue.len() >= self.capacity {
112            return Err(SequencerError::QueueFull);
113        }
114        let hash = hash_action(&action);
115        if !self.pending.insert(hash) {
116            return Err(SequencerError::DuplicatePending);
117        }
118        self.queue.push_back(action);
119        Ok(hash)
120    }
121
122    fn plan(&self, limit: usize) -> Plan {
123        Plan {
124            actions: self.queue.iter().take(limit).cloned().collect(),
125        }
126    }
127
128    fn apply_plan(
129        &mut self,
130        plan: Plan,
131        channel: &mut Channel,
132    ) -> Result<ApplyReport, SequencerError> {
133        if plan.actions.len() > self.queue.len()
134            || plan
135                .actions
136                .iter()
137                .zip(&self.queue)
138                .any(|(planned, queued)| hash_action(planned) != hash_action(queued))
139        {
140            return Err(SequencerError::StalePlan);
141        }
142
143        let mut receipts = Vec::with_capacity(plan.actions.len());
144        for planned in plan.actions {
145            if let Err(error) = channel.apply(&planned) {
146                return Ok(ApplyReport {
147                    receipts,
148                    failure: Some(error),
149                });
150            }
151            self.queue.pop_front();
152            let action_hash = hash_action(&planned);
153            self.pending.remove(&action_hash);
154            receipts.push(Receipt {
155                action_hash,
156                height: channel.height(),
157            });
158        }
159        Ok(ApplyReport {
160            receipts,
161            failure: None,
162        })
163    }
164}
165
166/// Backward-compatible name for the deterministic local sequencer.
167pub type SimpleConsensus = DeterministicSequencer;
168
169#[cfg(test)]
170mod tests {
171    use super::*;
172    use hop_core::{CompanionMatrix, Field};
173
174    fn action(coefficients: Vec<u64>, nonce: u64) -> Action {
175        Action {
176            g_coeffs: coefficients,
177            nonce,
178            mask_row0: None,
179        }
180    }
181
182    fn channel() -> Channel {
183        Channel::try_open(
184            CompanionMatrix::try_from_coeffs(&[4, 3, 2]).unwrap(),
185            vec![Field::one(), Field::zero(), Field::zero()],
186            [7; 32],
187        )
188        .unwrap()
189    }
190
191    #[test]
192    fn applies_only_the_planned_prefix_and_uses_channel_height() {
193        let mut sequencer = DeterministicSequencer::with_capacity(3);
194        sequencer.admit(action(vec![1], 1)).unwrap();
195        sequencer.admit(action(vec![0, 1], 2)).unwrap();
196        let plan = sequencer.plan(1);
197        let mut channel = channel();
198        let report = sequencer.apply_plan(plan, &mut channel).unwrap();
199        assert!(report.failure.is_none());
200        assert_eq!(report.receipts[0].height, 1);
201        assert_eq!(sequencer.len(), 1);
202    }
203
204    #[test]
205    fn rejects_duplicates_capacity_overflow_and_stale_plans() {
206        let mut sequencer = DeterministicSequencer::with_capacity(2);
207        let first = action(vec![1], 1);
208        sequencer.admit(first.clone()).unwrap();
209        assert_eq!(
210            sequencer.admit(first),
211            Err(SequencerError::DuplicatePending)
212        );
213        sequencer.admit(action(vec![0, 1], 3)).unwrap();
214        assert_eq!(
215            sequencer.admit(action(vec![3], 4)),
216            Err(SequencerError::QueueFull)
217        );
218        let stale = Plan {
219            actions: vec![action(vec![2], 2)],
220        };
221        assert_eq!(
222            sequencer.apply_plan(stale, &mut channel()).unwrap_err(),
223            SequencerError::StalePlan
224        );
225    }
226}