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/// Threshold for number of bundles operator can produce based on their stake share.
38/// Operators whose expected bundles from their threshold < E_BASE will not be checked
39/// since they are not throughput relevant.
40pub const E_BASE: u64 = 3;
41
42/// Extension trait for FixedU128 providing rounding to u64.
43trait FixedU128Ext {
44    /// Floor FixedU128 to u64.
45    fn to_u64_floor(self) -> u64;
46    /// Ceil FixedU128 to u64.
47    fn to_u64_ceil(self) -> u64;
48}
49
50impl FixedU128Ext for FixedU128 {
51    fn to_u64_floor(self) -> u64 {
52        (self.into_inner() / FixedU128::DIV).saturated_into()
53    }
54
55    fn to_u64_ceil(self) -> u64 {
56        self.into_inner().div_ceil(FixedU128::DIV).saturated_into()
57    }
58}
59
60// Exact per-slot win probability is p = threshold / 2^128.
61// Convert that to FixedU128 (1e18 scaling) using U256 intermediates.
62fn p_from_threshold(threshold: u128) -> FixedU128 {
63    // inner = floor(threshold * 1e18 / 2^128)
64    let num = U256::from(threshold).saturating_mul(U256::from(FixedU128::DIV));
65    let den = U256::from(1u128) << 128; // 2^128
66    FixedU128::from_inner((num / den).unique_saturated_into())
67}
68
69/// Chernoff lower-tail threshold r for Binomial(S, p), with false-positive at most τ.
70///
71/// Inputs:
72/// - slots_in_epoch: S (number of slots in the epoch)
73/// - p_slot: per-slot success probability p in FixedU128 (1e18 scaling)
74/// - ln_one_over_tau: ln(1/τ) in FixedU128 (1e18 scaling), precomputed off-chain
75///
76/// Returns:
77/// - r in [0, S], as u64
78///
79/// Formula:
80///   μ = S * p
81///   r = floor( μ - sqrt( 2 * μ * ln(1/τ) ) ), clamped to [0, S]
82///
83/// Guarantees:
84///   P_honest(X < r) <= τ for X ~ Binomial(S, p). Conservative (safe) bound.
85///
86/// Usage:
87///   let r = chernoff_threshold_fp(S, p, ln_1_over_tau);
88///   if observed_bundles < r { exclude } else { keep }
89fn chernoff_threshold_fp(
90    slots_in_epoch: u64,
91    p_slot: FixedU128,
92    ln_one_over_tau: FixedU128,
93) -> Option<u64> {
94    if slots_in_epoch == 0 || p_slot.is_zero() {
95        return Some(0);
96    }
97
98    if p_slot >= FixedU128::one() {
99        return Some(slots_in_epoch);
100    }
101
102    // μ = S * p
103    let mu = p_slot.saturating_mul(FixedU128::saturating_from_integer(slots_in_epoch));
104
105    // t = sqrt( 2 * μ * ln(1/τ) )
106    let t = FixedU128::from(2u128)
107        .saturating_mul(mu)
108        .saturating_mul(ln_one_over_tau)
109        .try_sqrt()?;
110
111    // r = floor( μ - t ), clamped to [0, S]
112    Some(
113        if mu > t {
114            mu.saturating_sub(t).to_u64_floor()
115        } else {
116            0
117        }
118        .clamp(0, slots_in_epoch),
119    )
120}
121
122/// Check if an operator is "throughput-relevant" this epoch:
123/// μ_floor = floor(S * p) >= E_relevance
124///
125/// Recommendation for τ = 1%:
126///   E_relevance >= ceil( 2 * ln(1/τ) ) = ceil(9.21) = 10
127fn is_throughput_relevant_fp(slots_in_epoch: u64, p_slot: FixedU128, e_relevance: u64) -> bool {
128    let mu = p_slot.saturating_mul(FixedU128::saturating_from_integer(slots_in_epoch));
129    let mu_floor = mu.to_u64_floor();
130    mu_floor >= e_relevance
131}
132
133// Compute E_relevance = ceil( max( E_BASE, 2 * ln(1/τ) ) ) in integer bundles.
134fn compute_e_relevance(ln_one_over_tau: FixedU128, e_base: u64) -> u64 {
135    let two_ln = FixedU128::saturating_from_integer(2)
136        .saturating_mul(ln_one_over_tau)
137        .to_u64_ceil();
138    max(e_base, two_ln)
139}
140
141/// Expectations for one operator at epoch end (slots-based, Chernoff-calibrated).
142#[derive(
143    TypeInfo,
144    Debug,
145    Encode,
146    Decode,
147    Clone,
148    PartialEq,
149    Eq,
150    Serialize,
151    Deserialize,
152    DecodeWithMemTracking,
153)]
154pub struct OperatorEpochExpectations {
155    /// floor(μ) = floor(S * p_slot_exact): integer expected bundles this epoch.
156    pub expected_bundles: u64,
157    /// Chernoff lower-bound r: minimum bundles to pass with false-positive ≤ τ.
158    pub min_required_bundles: u64,
159}
160
161/// Compute epoch-end expectations for an operator using the exact VRF threshold.
162/// Returns None if the operator is not throughput-relevant this epoch.
163///
164/// Flow is:
165/// - calculate_threshold(...) -> u128 threshold
166/// - p_from_threshold(threshold) -> FixedU128 per-slot probability
167/// - compute_e_relevance(ln_one_over_tau, e_base) -> u64 E_relevance
168/// - is_throughput_relevant_fp(S, p, E_relevance) -> bool
169/// - chernoff_threshold_fp(S, p, ln_one_over_tau) -> u64 r
170///
171/// Inputs:
172/// - slots_in_epoch: S
173/// - operator_stake, total_domain_stake: epoch-start stake snapshot
174/// - bundle_slot_probability: (theta_num, theta_den)
175/// - ln_one_over_tau: ln(1/τ) in FixedU128 (e.g., LN_1_OVER_TAU_1_PERCENT)
176/// - e_base: soft relevance floor (e.g., E_BASE)
177pub fn operator_expected_bundles_in_epoch(
178    slots_in_epoch: u64,
179    operator_stake: StakeWeight,
180    total_domain_stake: StakeWeight,
181    bundle_slot_probability: (u64, u64), // (theta_num, theta_den)
182    ln_one_over_tau: FixedU128,
183    e_base: u64,
184) -> Option<OperatorEpochExpectations> {
185    if slots_in_epoch.is_zero() {
186        return None;
187    }
188
189    // Exact per-slot probability from runtime VRF threshold
190    let threshold =
191        calculate_threshold(operator_stake, total_domain_stake, bundle_slot_probability)?;
192    let p_slot = p_from_threshold(threshold);
193    if p_slot.is_zero() {
194        return None;
195    }
196
197    // Throughput relevance: μ_floor >= E_relevance
198    let e_rel = compute_e_relevance(ln_one_over_tau, e_base);
199    if !is_throughput_relevant_fp(slots_in_epoch, p_slot, e_rel) {
200        return None;
201    }
202
203    // Expected bundles (floor μ) and Chernoff lower-bound r
204    let mu_fp = p_slot.saturating_mul(FixedU128::saturating_from_integer(slots_in_epoch));
205    let expected_bundles = mu_fp.to_u64_floor();
206    let min_required_bundles = chernoff_threshold_fp(slots_in_epoch, p_slot, ln_one_over_tau)?;
207
208    Some(OperatorEpochExpectations {
209        expected_bundles,
210        min_required_bundles,
211    })
212}
sp_domains/offline_operators.rs

sp_domains/
offline_operators.rs
