use std::collections::BTreeMap;
use std::collections::BTreeSet;
use std::collections::VecDeque;
use std::sync::atomic::AtomicU64;
use std::sync::atomic::Ordering;
use std::time::Duration;
pub const DEFAULT_MAX_VERIFICATION_BYTES: u64 = 17_179_869_184;
pub const DEFAULT_MAX_VERIFICATION_ENTRIES: u64 = 200_000;
pub const DEFAULT_MAX_COMPLETE_VERIFICATION_PASS: Duration = Duration::from_secs(720);
pub const RESERVED_VERIFICATION_BYTES_PER_SECOND: u64 = 33_554_432;
pub const RESERVED_VERIFICATION_ENTRIES_PER_SECOND: u64 = 1_000;
pub const MAX_CURRENT_UNVERIFIED_AGE: Duration = Duration::from_secs(900);
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct MonotonicInstant(pub u64);
impl MonotonicInstant {
pub fn plus(self, delta: Duration) -> Self {
Self(self.0 + u64::try_from(delta.as_millis()).expect("delta fits in u64 millis"))
}
}
fn age_millis() -> u64 {
u64::try_from(MAX_CURRENT_UNVERIFIED_AGE.as_millis()).expect("age fits in u64 millis")
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct PolicyVersion(pub u64);
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct VerificationScopeReceiptId(pub(crate) u64);
static NEXT_RECEIPT: AtomicU64 = AtomicU64::new(1);
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum VerificationRefusal {
OverdueLatched,
NotWholeScope {
missing: usize,
extra: usize,
mismatched: usize,
},
ProofFenced,
WorkBeyondCaps,
PolicyMismatch,
FeasibilityNotForThisScope,
NonCurrent(NonCurrentCause),
ScopeDirty,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum NonCurrentCause {
OverdueLatched,
ReservationLost,
PolicyMismatch,
}
#[derive(Debug)]
pub struct VerificationScopeReceipt {
id: VerificationScopeReceiptId,
policy: PolicyVersion,
entries: BTreeMap<u64, u64>,
}
impl VerificationScopeReceipt {
pub fn seal(policy: PolicyVersion, entries: BTreeMap<u64, u64>) -> Self {
Self {
id: VerificationScopeReceiptId(NEXT_RECEIPT.fetch_add(1, Ordering::Relaxed)),
policy,
entries,
}
}
pub fn receipt_id(&self) -> VerificationScopeReceiptId {
self.id
}
pub fn len(&self) -> usize {
self.entries.len()
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
}
#[derive(Debug)]
pub struct VerificationWorkBound {
scope_receipt: VerificationScopeReceiptId,
bound: Duration,
}
impl VerificationWorkBound {
pub fn for_scope(
receipt: &VerificationScopeReceipt,
verification_bytes: u64,
verification_entries: u64,
) -> Result<Self, VerificationRefusal> {
if verification_bytes > DEFAULT_MAX_VERIFICATION_BYTES
|| verification_entries > DEFAULT_MAX_VERIFICATION_ENTRIES
{
return Err(VerificationRefusal::WorkBeyondCaps);
}
let seconds = verification_bytes.div_ceil(RESERVED_VERIFICATION_BYTES_PER_SECOND)
+ verification_entries.div_ceil(RESERVED_VERIFICATION_ENTRIES_PER_SECOND);
Ok(Self {
scope_receipt: receipt.id,
bound: Duration::from_secs(seconds),
})
}
pub fn bound(&self) -> Duration {
self.bound
}
}
#[derive(Debug)]
pub struct VerificationFeasibilityReceipt {
work: VerificationWorkBound,
}
impl VerificationFeasibilityReceipt {
pub fn reserve(work: VerificationWorkBound) -> Self {
Self { work }
}
fn scope_receipt(&self) -> VerificationScopeReceiptId {
self.work.scope_receipt
}
}
#[derive(Debug)]
pub struct VerificationRecord {
receipt: VerificationScopeReceiptId,
}
#[derive(Debug)]
pub struct RollingPass {
receipt: VerificationScopeReceiptId,
scope: BTreeMap<u64, u64>,
verified: BTreeMap<u64, u64>,
}
impl RollingPass {
pub fn verify_chunk(
&mut self,
observed: BTreeMap<u64, u64>,
) -> Result<(), VerificationRefusal> {
self.verified.extend(observed);
Ok(())
}
pub fn remaining(&self) -> BTreeSet<u64> {
self.scope
.keys()
.filter(|id| !self.verified.contains_key(id))
.copied()
.collect()
}
pub fn complete(self) -> Result<VerificationRecord, VerificationRefusal> {
let missing = self
.scope
.keys()
.filter(|id| !self.verified.contains_key(id))
.count();
let extra = self
.verified
.keys()
.filter(|id| !self.scope.contains_key(id))
.count();
let mismatched = self
.scope
.iter()
.filter(|(id, stamp)| self.verified.get(id).is_some_and(|seen| seen != *stamp))
.count();
if missing + extra + mismatched > 0 {
return Err(VerificationRefusal::NotWholeScope {
missing,
extra,
mismatched,
});
}
Ok(VerificationRecord {
receipt: self.receipt,
})
}
}
#[derive(Debug, Default)]
pub struct PassScheduler {
queue: VecDeque<u64>,
}
impl PassScheduler {
pub fn new() -> Self {
Self::default()
}
pub fn register(&mut self, pass_id: u64) {
self.queue.push_back(pass_id);
}
pub fn next_grant(&mut self) -> Option<u64> {
let granted = self.queue.pop_front()?;
self.queue.push_back(granted);
Some(granted)
}
}
#[derive(Debug)]
pub struct RollingVerifier {
receipt: VerificationScopeReceipt,
_feasibility: VerificationFeasibilityReceipt,
verified_at: MonotonicInstant,
non_current: Option<NonCurrentCause>,
scope_dirty: bool,
}
impl RollingVerifier {
pub fn promote(
receipt: VerificationScopeReceipt,
feasibility: VerificationFeasibilityReceipt,
now: MonotonicInstant,
) -> Result<Self, VerificationRefusal> {
if feasibility.scope_receipt() != receipt.id {
return Err(VerificationRefusal::FeasibilityNotForThisScope);
}
Ok(Self {
receipt,
_feasibility: feasibility,
verified_at: now,
non_current: None,
scope_dirty: false,
})
}
pub fn begin_pass(
&mut self,
policy: PolicyVersion,
) -> Result<RollingPass, VerificationRefusal> {
if policy != self.receipt.policy {
if self.non_current.is_none() {
self.non_current = Some(NonCurrentCause::PolicyMismatch);
}
return Err(VerificationRefusal::PolicyMismatch);
}
match self.non_current {
None | Some(NonCurrentCause::OverdueLatched) => Ok(RollingPass {
receipt: self.receipt.id,
scope: self.receipt.entries.clone(),
verified: BTreeMap::new(),
}),
Some(cause) => Err(VerificationRefusal::NonCurrent(cause)),
}
}
pub fn is_current(&self, now: MonotonicInstant) -> bool {
self.non_current.is_none() && now.0 < self.verified_at.0 + age_millis()
}
pub fn acquire_strict(&mut self, now: MonotonicInstant) -> Result<(), VerificationRefusal> {
match self.non_current {
Some(NonCurrentCause::OverdueLatched) => Err(VerificationRefusal::OverdueLatched),
Some(cause) => Err(VerificationRefusal::NonCurrent(cause)),
None => {
if now.0 >= self.verified_at.0 + age_millis() {
self.non_current = Some(NonCurrentCause::OverdueLatched);
return Err(VerificationRefusal::OverdueLatched);
}
Ok(())
}
}
}
pub fn advance(
&mut self,
record: VerificationRecord,
now: MonotonicInstant,
) -> Result<(), VerificationRefusal> {
if record.receipt != self.receipt.id {
return Err(VerificationRefusal::ProofFenced);
}
if self.scope_dirty {
return Err(VerificationRefusal::ScopeDirty);
}
match self.non_current {
None | Some(NonCurrentCause::OverdueLatched) => {
self.non_current = None;
self.verified_at = now;
Ok(())
}
Some(cause) => Err(VerificationRefusal::NonCurrent(cause)),
}
}
pub fn refresh_scope(
&mut self,
receipt: VerificationScopeReceipt,
) -> Result<(), VerificationRefusal> {
if receipt.policy != self.receipt.policy {
if self.non_current.is_none() {
self.non_current = Some(NonCurrentCause::PolicyMismatch);
}
return Err(VerificationRefusal::PolicyMismatch);
}
self.receipt = receipt;
self.scope_dirty = false;
Ok(())
}
pub fn observe_rewrite(&mut self, entry: u64, stamp: u64) {
match self.receipt.entries.get(&entry) {
Some(sealed) if *sealed == stamp => {}
_ => self.scope_dirty = true,
}
}
pub fn reservation_lost(&mut self) {
self.non_current = Some(NonCurrentCause::ReservationLost);
}
pub fn non_current_cause(&self) -> Option<NonCurrentCause> {
self.non_current
}
pub fn re_scout(
&mut self,
receipt: VerificationScopeReceipt,
feasibility: VerificationFeasibilityReceipt,
now: MonotonicInstant,
) -> Result<(), VerificationRefusal> {
if feasibility.scope_receipt() != receipt.id {
return Err(VerificationRefusal::FeasibilityNotForThisScope);
}
self.receipt = receipt;
self._feasibility = feasibility;
self.verified_at = now;
self.non_current = None;
self.scope_dirty = false;
Ok(())
}
}