sp_domains/
offline_operators.rs

1//! Chernoff lower-tail threshold for Binomial(S, p).
2//!
3//! Threshold (additive Chernoff, lower tail):
4//!   Let μ = S * p, where S is slots_in_epoch and p is per-slot win probability.
5//!   t = sqrt( 2 * μ * ln(1/τ) )
6//!   r = floor( μ - t ), clamped to [0, S]
7//!
8//! Property:
9//!   For X ~ Binomial(S, p), `P[ X < r ] <= τ`  (conservative bound)
10//!   This holds for all p in `[0,1]` and any S.
11//!
12//! Notes:
13//! - Provide ln(1/τ) as a FixedU128 constant (precomputed off-chain).
14//! - Examples:
15//!   τ = 1%   => ln(100)   ≈ 4.605170185988092  -> inner ≈ 4_605_170_185_988_091_904
16//!   τ = 0.5% => ln(200)   ≈ 5.298317366548036  -> inner ≈ 5_298_317_366_548_036_000
17//!   τ = 0.1% => ln(1000)  ≈ 6.907755278982137  -> inner ≈ 6_907_755_278_982_137_000
18//! - To decide throughput relevance before calling this (cheap filter), compute
19//!   μ_floor = floor(S * p) and require μ_floor >= E_relevance (e.g., >= 10 for τ=1%).
20
21#[cfg(test)]
22mod tests;
23
24use crate::StakeWeight;
25use crate::bundle_producer_election::calculate_threshold;
26use core::cmp::max;
27use frame_support::pallet_prelude::{Decode, Encode, TypeInfo};
28use frame_support::{Deserialize, Serialize};
29use sp_arithmetic::traits::{One, SaturatedConversion, Saturating, UniqueSaturatedInto, Zero};
30use sp_arithmetic::{FixedPointNumber, FixedU128};
31use sp_core::{DecodeWithMemTracking, U256};
32
33/// For τ = 1%: ln(1/τ) = ln(100) ≈ 4.605170185988092
34/// Represent in FixedU128 by multiplying by 1e18 and rounding.
35pub const LN_1_OVER_TAU_1_PERCENT: FixedU128 = FixedU128::from_inner(4_605_170_185_988_091_904);
36
37// For τ = 0.5%: ln(1/τ) = ln(200) ≈ 5.298317366548036
38// Represent in FixedU128 by multiplying by 1e18 and rounding.
39pub const LN_1_OVER_TAU_0_5_PERCENT: FixedU128 = FixedU128::from_inner(5_298_317_366_548_036_608);
40
41/// Threshold for number of bundles operator can produce based on their stake share.
42/// Operators whose expected bundles from their threshold < E_BASE will not be checked
43/// since they are not throughput relevant.
44pub const E_BASE: u64 = 3;
45
46/// Minimum shortfall fraction relative to expected bundles to consider an operator offline.
47/// (numerator, denominator): operator is flagged only if submitted < expected * (den - num) / den.
48/// (1, 3) means 1/3 = 33% shortfall required (must submit < 67% of expected).
49/// Constraints: denominator > 0, numerator <= denominator.
50pub const OFFLINE_SHORTFALL_FRACTION: (u64, u64) = (1, 3);
51
52const _: () = assert!(OFFLINE_SHORTFALL_FRACTION.1 > 0);
53const _: () = assert!(OFFLINE_SHORTFALL_FRACTION.0 < OFFLINE_SHORTFALL_FRACTION.1);
54
55/// Extension trait for FixedU128 providing rounding to u64.
56trait FixedU128Ext {
57    /// Floor FixedU128 to u64.
58    fn to_u64_floor(self) -> u64;
59    /// Ceil FixedU128 to u64.
60    fn to_u64_ceil(self) -> u64;
61}
62
63impl FixedU128Ext for FixedU128 {
64    fn to_u64_floor(self) -> u64 {
65        (self.into_inner() / FixedU128::DIV).saturated_into()
66    }
67
68    fn to_u64_ceil(self) -> u64 {
69        self.into_inner().div_ceil(FixedU128::DIV).saturated_into()
70    }
71}
72
73// Exact per-slot win probability is p = threshold / 2^128.
74// Convert that to FixedU128 (1e18 scaling) using U256 intermediates.
75fn p_from_threshold(threshold: u128) -> FixedU128 {
76    // inner = floor(threshold * 1e18 / 2^128)
77    let num = U256::from(threshold).saturating_mul(U256::from(FixedU128::DIV));
78    let den = U256::from(1u128) << 128; // 2^128
79    FixedU128::from_inner((num / den).unique_saturated_into())
80}
81
82/// Chernoff lower-tail threshold r for Binomial(S, p), with false-positive at most τ.
83///
84/// Inputs:
85/// - slots_in_epoch: S (number of slots in the epoch)
86/// - p_slot: per-slot success probability p in FixedU128 (1e18 scaling)
87/// - ln_one_over_tau: ln(1/τ) in FixedU128 (1e18 scaling), precomputed off-chain
88///
89/// Returns:
90/// - r in [0, S], as u64
91///
92/// Formula:
93///   μ = S * p
94///   r = floor( μ - sqrt( 2 * μ * ln(1/τ) ) ), clamped to [0, S]
95///
96/// Guarantees:
97///   P_honest(X < r) <= τ for X ~ Binomial(S, p). Conservative (safe) bound.
98///
99/// Usage:
100///   let r = chernoff_threshold_fp(S, p, ln_1_over_tau);
101///   if observed_bundles < r { exclude } else { keep }
102fn chernoff_threshold_fp(
103    slots_in_epoch: u64,
104    p_slot: FixedU128,
105    ln_one_over_tau: FixedU128,
106) -> Option<u64> {
107    if slots_in_epoch == 0 || p_slot.is_zero() {
108        return Some(0);
109    }
110
111    if p_slot >= FixedU128::one() {
112        return Some(slots_in_epoch);
113    }
114
115    // μ = S * p
116    let mu = p_slot.saturating_mul(FixedU128::saturating_from_integer(slots_in_epoch));
117
118    // t = sqrt( 2 * μ * ln(1/τ) )
119    let t = FixedU128::from(2u128)
120        .saturating_mul(mu)
121        .saturating_mul(ln_one_over_tau)
122        .try_sqrt()?;
123
124    // r = floor( μ - t ), clamped to [0, S]
125    Some(
126        if mu > t {
127            mu.saturating_sub(t).to_u64_floor()
128        } else {
129            0
130        }
131        .clamp(0, slots_in_epoch),
132    )
133}
134
135/// Check if an operator is "throughput-relevant" this epoch:
136/// μ_floor = floor(S * p) >= E_relevance
137///
138/// Recommendation for τ = 1%:
139///   E_relevance >= ceil( 2 * ln(1/τ) ) = ceil(9.21) = 10
140fn is_throughput_relevant_fp(slots_in_epoch: u64, p_slot: FixedU128, e_relevance: u64) -> bool {
141    let mu = p_slot.saturating_mul(FixedU128::saturating_from_integer(slots_in_epoch));
142    let mu_floor = mu.to_u64_floor();
143    mu_floor >= e_relevance
144}
145
146// Compute E_relevance = ceil( max( E_BASE, 2 * ln(1/τ) ) ) in integer bundles.
147fn compute_e_relevance(ln_one_over_tau: FixedU128, e_base: u64) -> u64 {
148    let two_ln = FixedU128::saturating_from_integer(2)
149        .saturating_mul(ln_one_over_tau)
150        .to_u64_ceil();
151    max(e_base, two_ln)
152}
153
154/// Expectations for one operator at epoch end (slots-based, Chernoff-calibrated).
155#[derive(
156    TypeInfo,
157    Debug,
158    Encode,
159    Decode,
160    Clone,
161    PartialEq,
162    Eq,
163    Serialize,
164    Deserialize,
165    DecodeWithMemTracking,
166)]
167pub struct OperatorEpochExpectations {
168    /// floor(μ) = floor(S * p_slot_exact): integer expected bundles this epoch.
169    pub expected_bundles: u64,
170    /// Chernoff lower-bound r: minimum bundles to pass with false-positive ≤ τ.
171    pub min_required_bundles: u64,
172    /// Shortfall policy threshold: expected * (den - num) / den, using floor rounding.
173    /// Operator must submit fewer than this AND fewer than min_required_bundles to be flagged.
174    pub shortfall_threshold: u64,
175}
176
177/// Compute epoch-end expectations for an operator using the exact VRF threshold.
178/// Returns None if the operator is not throughput-relevant this epoch.
179///
180/// Flow is:
181/// - calculate_threshold(...) -> u128 threshold
182/// - p_from_threshold(threshold) -> FixedU128 per-slot probability
183/// - compute_e_relevance(ln_one_over_tau, e_base) -> u64 E_relevance
184/// - is_throughput_relevant_fp(S, p, E_relevance) -> bool
185/// - chernoff_threshold_fp(S, p, ln_one_over_tau) -> u64 r
186///
187/// Inputs:
188/// - slots_in_epoch: S
189/// - operator_stake, total_domain_stake: epoch-start stake snapshot
190/// - bundle_slot_probability: (theta_num, theta_den)
191/// - ln_one_over_tau: ln(1/τ) in FixedU128 (e.g., LN_1_OVER_TAU_1_PERCENT)
192/// - e_base: soft relevance floor (e.g., E_BASE)
193pub fn operator_expected_bundles_in_epoch(
194    slots_in_epoch: u64,
195    operator_stake: StakeWeight,
196    total_domain_stake: StakeWeight,
197    bundle_slot_probability: (u64, u64), // (theta_num, theta_den)
198    ln_one_over_tau: FixedU128,
199    e_base: u64,
200    shortfall_fraction: (u64, u64),
201) -> Option<OperatorEpochExpectations> {
202    if slots_in_epoch.is_zero() || shortfall_fraction.1 == 0 {
203        return None;
204    }
205
206    // Exact per-slot probability from runtime VRF threshold
207    let threshold =
208        calculate_threshold(operator_stake, total_domain_stake, bundle_slot_probability)?;
209    let p_slot = p_from_threshold(threshold);
210    if p_slot.is_zero() {
211        return None;
212    }
213
214    // Throughput relevance: μ_floor >= E_relevance
215    let e_rel = compute_e_relevance(ln_one_over_tau, e_base);
216    if !is_throughput_relevant_fp(slots_in_epoch, p_slot, e_rel) {
217        return None;
218    }
219
220    // Expected bundles (floor μ) and Chernoff lower-bound r
221    let mu_fp = p_slot.saturating_mul(FixedU128::saturating_from_integer(slots_in_epoch));
222    let expected_bundles = mu_fp.to_u64_floor();
223    let min_required_bundles = chernoff_threshold_fp(slots_in_epoch, p_slot, ln_one_over_tau)?;
224
225    // Shortfall policy gate: expected * (den - num) / den, floor rounding
226    let (sf_num, sf_den) = shortfall_fraction;
227    let shortfall_threshold =
228        expected_bundles.saturating_mul(sf_den.saturating_sub(sf_num)) / sf_den;
229
230    Some(OperatorEpochExpectations {
231        expected_bundles,
232        min_required_bundles,
233        shortfall_threshold,
234    })
235}
sp_domains/offline_operators.rs

sp_domains/
offline_operators.rs
