//! A reference operator that admits payments and soft withdrawals and closes each epoch. use commonware_clearing::bajillion::{ Admission, Amount, Amounts, AssemblyError, Close, Epoch, Flow, FlowError, Limits, Namespace, Queue, Request, RequestError, Row, State, Withdrawal, }; use commonware_codec::Encode as _; use commonware_cryptography::{Digest, Hasher, PublicKey, Signer}; use commonware_parallel::Sequential; use core::{ hash::Hash, sync::atomic::{AtomicUsize, Ordering}, }; use std::collections::BTreeMap; /// Why the operator refused a request, a soft withdrawal, or a close. #[derive(Debug, thiserror::Error)] pub enum Refusal { /// Admitting it would take the close past the operator's limits. #[error("admitting it would take the close past the operator's limits")] Full, /// The batch exceeds what the sender can still spend in the epoch. #[error("the batch exceeds what the sender can still spend in the epoch")] InsufficientBalance, /// The soft withdrawal or the queue is for another epoch. #[error("wrong epoch: expected {expected}, found {found}")] WrongEpoch { /// The epoch the operator admits in. expected: Epoch, /// The epoch found. found: Epoch, }, /// The soft withdrawal's signature does not verify. #[error("invalid withdrawal signature")] InvalidWithdrawal, /// The next epoch does not fit. #[error("epoch overflow")] Overflow, /// The request does not verify or extend the sender's record. #[error(transparent)] Request(#[from] RequestError), /// The rows and withdrawals do not assemble into a close. #[error(transparent)] Assembly(#[from] AssemblyError), /// A flow of the close does not settle. #[error(transparent)] Flow(#[from] FlowError), } /// Per-account records that count their lookups. The count is not part of the records' identity, /// and it is atomic so the records can be read from several threads. #[derive(Debug)] pub struct Records { entries: BTreeMap, reads: AtomicUsize, } impl Default for Records { fn default() -> Self { Self { entries: BTreeMap::new(), reads: AtomicUsize::new(0), } } } impl Clone for Records { fn clone(&self) -> Self { Self { entries: self.entries.clone(), reads: AtomicUsize::new(self.reads.load(Ordering::Relaxed)), } } } impl PartialEq for Records { fn eq(&self, other: &Self) -> bool { self.entries == other.entries } } impl Eq for Records {} impl Hash for Records { fn hash(&self, state: &mut S) { self.entries.hash(state); } } impl Records { /// Returns the record of `key`, counting the lookup. fn get(&self, key: &K) -> Option<&V> { self.reads.fetch_add(1, Ordering::Relaxed); self.entries.get(key) } /// Returns how many lookups the records served. fn reads(&self) -> usize { self.reads.load(Ordering::Relaxed) } } /// A sender's latest countersigned state in the current epoch, with its payment map and the /// sender's signature over it. #[derive(Clone, Debug, PartialEq, Eq, Hash)] pub struct Admitted { /// The countersigned state. pub state: State, /// The payment map the state commits to. pub payments: Amounts, /// The sender's signature over the state. pub signature: P::Signature, } /// What the operator persists (O7). A restart resumes from it alone. #[derive(Clone, Debug, PartialEq, Eq)] pub struct Persisted { /// Epoch the operator admits in. pub epoch: Epoch, /// Every positive balance as of the last close the operator applied. pub balances: Records, /// Root of each sender's row in the close of the epoch before. pub previous: Records, /// Each sender's latest admission in the epoch, persisted before its acknowledgement is /// released. pub admitted: Records>, /// The soft withdrawals collected in the epoch, keyed by account, amount, and tag. pub withdrawals: BTreeMap<(P, A, u64), Withdrawal>, /// The last close, persisted before it is released so a restart can release it again. pub released: Option>, } impl Hash for Persisted { fn hash(&self, state: &mut S) { let Self { epoch, balances, previous, admitted, withdrawals, released, } = self; epoch.hash(state); balances.hash(state); previous.hash(state); admitted.hash(state); withdrawals.hash(state); released.as_ref().map(|close| close.encode()).hash(state); } } /// An operator that serves every account and applies each close it assembles at once. /// /// Its balances follow the posted closes only if every close it assembles posts. Two operators /// are equal when they persisted the same records. pub struct Operator { signer: K, namespace: Namespace, limits: Limits, persisted: Persisted, } // The hasher is a type parameter only, so the derived impl would bound it. impl Clone for Operator { fn clone(&self) -> Self { Self { signer: self.signer.clone(), namespace: self.namespace.clone(), limits: self.limits, persisted: self.persisted.clone(), } } } impl PartialEq for Operator { fn eq(&self, other: &Self) -> bool { self.persisted == other.persisted } } impl Eq for Operator {} impl Hash for Operator { fn hash(&self, state: &mut S) { self.persisted.hash(state); } } impl Operator { /// Returns an operator admitting in the first epoch, with no balances. pub fn new(signer: K, namespace: Namespace, limits: Limits) -> Self { let persisted = Persisted { epoch: 1, balances: Records::default(), previous: Records::default(), admitted: Records::default(), withdrawals: BTreeMap::new(), released: None, }; Self::restart(signer, namespace, limits, persisted) } /// Returns an operator resuming from what it persisted. pub const fn restart( signer: K, namespace: Namespace, limits: Limits, persisted: Persisted, ) -> Self { Self { signer, namespace, limits, persisted, } } /// Returns what the operator persisted. pub const fn persisted(&self) -> &Persisted { &self.persisted } /// Returns the epoch the operator admits in. pub const fn epoch(&self) -> Epoch { self.persisted.epoch } /// Returns how many times the operator looked up an account's balance, previous row root, or /// admission. pub fn reads(&self) -> usize { self.persisted.balances.reads() + self.persisted.previous.reads() + self.persisted.admitted.reads() } /// Returns the account's balance as of the last close. pub fn balance(&self, account: &P) -> A { self.persisted .balances .get(account) .copied() .unwrap_or(A::ZERO) } /// Returns what the account can still pay in the current epoch, its balance less what it /// already paid. Incoming payments count only once a close settles them. pub fn live(&self, account: &P) -> A { let paid = self.payments(account).map_or(A::ZERO, |payments| { payments .total() .expect("an admitted map must fit an amount") }); self.balance(account) .checked_sub(paid) .expect("admitted payments must not exceed the balance") } /// Returns the account's countersigned payment map in the current epoch. pub fn payments(&self, account: &P) -> Option<&Amounts> { self.persisted .admitted .get(account) .map(|admitted| &admitted.payments) } /// Returns the rows of the current epoch. pub fn rows(&self) -> impl Iterator> + '_ { self.persisted .admitted .entries .values() .map(|admitted| Row { account: admitted.state.account.clone(), payments: admitted.payments.clone(), signature: admitted.signature.clone(), }) } /// Returns the soft withdrawals collected in the current epoch. pub fn withdrawals(&self) -> impl Iterator> { self.persisted.withdrawals.values() } /// Countersigns the state `request` asks for in the current epoch. /// /// A retry of the latest countersigned state is countersigned again and pays nothing twice. A /// new state is admitted only within the limits and the sender's live balance, and persisted /// before its acknowledgement is released. pub fn accept(&mut self, request: &Request) -> Result { // The signature is checked before any record of the sender is looked up, so a forged // request causes no read and is refused alike whatever the account holds or paid. let verified = request.verify::(&self.namespace, self.persisted.epoch)?; // The state must repeat or extend the sender's latest admission in the epoch, on top of // its row root in the close of the epoch before or the empty map's root (O2, O4). let empty = Amounts::::empty().root::(); let previous = self .persisted .previous .get(&request.account) .unwrap_or(&empty); let latest = self.persisted.admitted.get(&request.account); let admission = verified.admit::( latest.map(|latest| (&latest.state, &latest.payments)), previous, )?; let state = match admission { Admission::Retry(state) => state, Admission::New { state, payments, signature, } => { // A new state must fit the close's limits and the sender's live balance (O3, O5), // and it is recorded before its acknowledgement is released (O7). if (latest.is_none() && self.persisted.admitted.entries.len() >= self.limits.rows) || payments.len() > self.limits.receivers { return Err(Refusal::Full); } let live = self.live(&request.account); if request.batch.total().is_none_or(|total| total > live) { return Err(Refusal::InsufficientBalance); } let admitted = Admitted { state: state.clone(), payments, signature, }; self.persisted .admitted .entries .insert(request.account.clone(), admitted); state } }; Ok(state.acknowledge(&self.signer, &self.namespace)) } /// Drops `account`'s admission in the current epoch, as an operator that broke O7 would after a /// crash. The close of the epoch then omits the countersigned state. pub fn forget(&mut self, account: &P) { self.persisted.admitted.entries.remove(account); } /// Collects a soft withdrawal for the current epoch. Collecting one again has no effect. pub fn withdraw(&mut self, withdrawal: Withdrawal) -> Result<(), Refusal> { let epoch = self.persisted.epoch; if withdrawal.epoch != epoch { return Err(Refusal::WrongEpoch { expected: epoch, found: withdrawal.epoch, }); } if !withdrawal.verify(&self.namespace) { return Err(Refusal::InvalidWithdrawal); } // A request already collected stays as it is, and a new one must fit the limits (O5). let request = ( withdrawal.account.clone(), withdrawal.amount, withdrawal.tag, ); let withdrawals = &mut self.persisted.withdrawals; if !withdrawals.contains_key(&request) && withdrawals.len() >= self.limits.withdrawals { return Err(Refusal::Full); } withdrawals.entry(request).or_insert(withdrawal); Ok(()) } /// Closes the current epoch, processing the oldest `deposits` and `forced_withdrawals` /// requests in `queue`, applies every flow of the close to the balances, and opens the next /// epoch. The close is persisted before it is returned for release. A refusal leaves the /// operator unchanged. #[allow(clippy::type_complexity)] pub fn close( &mut self, queue: &Queue, deposits: u64, forced_withdrawals: u64, ) -> Result<(Close, Vec<(P, Flow)>), Refusal> { let epoch = self.persisted.epoch; if queue.epoch != epoch { return Err(Refusal::WrongEpoch { expected: epoch, found: queue.epoch, }); } let next = epoch.checked_add(1).ok_or(Refusal::Overflow)?; let (close, flows) = Close::assemble::( &self.signer, &self.namespace, queue, self.rows(), self.withdrawals().cloned(), deposits, forced_withdrawals, &Sequential, )?; // Every flow settles before anything changes, so a refusal leaves the operator unchanged. let settled = flows .iter() .map(|(account, flow)| { let balance = flow.settle(self.balance(account))?.balance; Ok((account.clone(), balance)) }) .collect::, FlowError>>()?; // Every flow of the close applies at once, with the close's row roots, before anything of // the next epoch is admitted. let persisted = &mut self.persisted; for (account, balance) in settled { if balance == A::ZERO { persisted.balances.entries.remove(&account); } else { persisted.balances.entries.insert(account, balance); } } persisted.previous.entries = close .rows() .iter() .map(|row| (row.account.clone(), row.payments.root::())) .collect(); persisted.epoch = next; persisted.admitted.entries.clear(); persisted.withdrawals.clear(); persisted.released = Some(close.clone()); Ok((close, flows)) } }