perspt_sdk/
independence.rs

1//! Measured validator dependence (PSP-9 system 8, Paper III Lemma 5.1 and
2//! Corollary 5.2).
3//!
4//! *"Correlation among redundant validators is measured, never assumed
5//! away."* This module computes, from matched labeled verdicts, each
6//! validator's miss rate `q_i`, the pairwise miss correlation `κ_ij`, the
7//! empirical pairwise joint miss, and the conservative conjunctive-ensemble
8//! bound `ρ_eff = min_{i<j} u_ij` over pairwise joint-miss **upper
9//! confidence bounds**.
10//!
11//! Statistics discipline (Gates R and T):
12//!
13//! * **Matched strata.** `q_i`, `q_j`, `κ_ij`, and the joint miss for a pair
14//!   are all computed over the same jointly evaluated candidate set.
15//! * **Degenerate marginals** (`q ∈ {0, 1}`) use the empirical joint miss
16//!   directly, as Lemma 5.1 requires; they are never assigned `κ = 0`.
17//! * **Exact only at n = 2.** For `n > 2` validators the bound is
18//!   deliberately conservative; it is never tightened by inferring
19//!   higher-order joints from pairwise correlations, and `n` is reported
20//!   beside it. A three-validator bound tighter than its best pair would be
21//!   a defect, not a better certificate.
22//! * **Point estimates are diagnostics.** A certified `ρ_eff` uses upper
23//!   confidence bounds and a minimum matched sample count; below it the
24//!   status is `insufficient evidence`, not a number.
25//! * **No energy attenuation.** Correlation controls the reported risk
26//!   bound; it never rewrites the fixed quadratic energy weights. The former
27//!   `attenuate_weight` helper is removed for that reason.
28
29use std::collections::BTreeMap;
30
31use serde::{Deserialize, Serialize};
32
33use crate::error::{Result, SdkError};
34
35/// One validator's verdict on one candidate: did it *miss* an unsafe state?
36///
37/// `missed == true` means the validator accepted a candidate later found
38/// unsafe — a false negative. Labels come from the delayed oracle (rollback
39/// boundary, regression residuals), never from contemporaneous agreement.
40#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
41pub struct VerdictRecord {
42    pub validator_id: String,
43    pub candidate_id: String,
44    pub missed: bool,
45}
46
47impl VerdictRecord {
48    pub fn new(
49        validator_id: impl Into<String>,
50        candidate_id: impl Into<String>,
51        missed: bool,
52    ) -> Self {
53        Self {
54            validator_id: validator_id.into(),
55            candidate_id: candidate_id.into(),
56            missed,
57        }
58    }
59}
60
61/// Matched-stratum statistics for one validator pair.
62#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
63pub struct PairStats {
64    /// Miss rates over the *matched* candidate set.
65    pub q_i: f64,
66    pub q_j: f64,
67    /// Phi correlation over matched misses; `None` for degenerate marginals,
68    /// which use the joint miss directly rather than a fabricated zero.
69    pub kappa: Option<f64>,
70    /// Empirical joint miss rate over the matched set (point diagnostic).
71    pub joint_miss: f64,
72    /// Conservative upper confidence bound on the joint miss (Hoeffding at
73    /// 95%): the value a certificate may use.
74    pub joint_miss_upper: f64,
75    /// Matched sample count.
76    pub samples: usize,
77}
78
79/// Certification status of the ensemble bound.
80#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
81#[serde(rename_all = "snake_case")]
82pub enum EnsembleCertification {
83    /// Every pair met the matched-sample floor; `rho_eff` uses upper bounds.
84    Certified,
85    /// Point diagnostics only; no risk certificate may be displayed.
86    InsufficientEvidence,
87}
88
89/// Independence statistics computed from the verdict ledger.
90#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
91pub struct IndependenceStats {
92    /// Per-validator miss rate over all of its verdicts (diagnostic only).
93    pub miss_rates: BTreeMap<String, f64>,
94    /// Matched-stratum pair statistics, keyed by ordered pair.
95    pub pairs: BTreeMap<(String, String), PairStats>,
96    /// `min_{i<j} u_ij` over pairwise joint-miss upper bounds, when
97    /// certified; the paper's conservative conjunctive bound.
98    pub rho_eff: Option<f64>,
99    /// Number of validators in the ensemble — reported beside the bound
100    /// because Corollary 5.2 is exact only at `n = 2`.
101    pub validators: usize,
102    pub certification: EnsembleCertification,
103}
104
105/// Standard deviation of a Bernoulli miss indicator: `σ = sqrt(q(1-q))`.
106pub fn miss_std(q: f64) -> f64 {
107    (q * (1.0 - q)).max(0.0).sqrt()
108}
109
110/// Lemma 5.1's exact pairwise joint miss: `q_i q_j + κ σ_i σ_j`.
111pub fn pairwise_joint_miss(q_i: f64, q_j: f64, kappa: f64) -> f64 {
112    q_i * q_j + kappa * miss_std(q_i) * miss_std(q_j)
113}
114
115/// Minimum matched samples per pair before a certificate may be issued.
116pub const DEFAULT_MIN_PAIR_SAMPLES: usize = 20;
117
118/// Compute independence statistics from a verdict ledger.
119pub fn compute(records: &[VerdictRecord]) -> Result<IndependenceStats> {
120    compute_with_floor(records, DEFAULT_MIN_PAIR_SAMPLES)
121}
122
123/// Compute with an explicit matched-sample floor for certification.
124pub fn compute_with_floor(
125    records: &[VerdictRecord],
126    min_pair_samples: usize,
127) -> Result<IndependenceStats> {
128    if records.is_empty() {
129        return Err(SdkError::Domain("no verdict records".into()));
130    }
131
132    let mut by_validator: BTreeMap<String, BTreeMap<String, bool>> = BTreeMap::new();
133    for r in records {
134        by_validator
135            .entry(r.validator_id.clone())
136            .or_default()
137            .insert(r.candidate_id.clone(), r.missed);
138    }
139
140    // Diagnostic-only marginal rates over each validator's full history.
141    let mut miss_rates = BTreeMap::new();
142    for (v, verdicts) in &by_validator {
143        let n = verdicts.len() as f64;
144        let misses = verdicts.values().filter(|&&m| m).count() as f64;
145        miss_rates.insert(v.clone(), misses / n);
146    }
147
148    let validators: Vec<&String> = by_validator.keys().collect();
149    let mut pairs = BTreeMap::new();
150    let mut rho_eff: Option<f64> = None;
151    let mut all_pairs_certified = !validators.is_empty() && validators.len() > 1;
152
153    for a in 0..validators.len() {
154        for b in (a + 1)..validators.len() {
155            let (vi, vj) = (validators[a], validators[b]);
156            let joint: Vec<(bool, bool)> = by_validator[vi]
157                .iter()
158                .filter_map(|(c, &m_i)| by_validator[vj].get(c).map(|&m_j| (m_i, m_j)))
159                .collect();
160            if joint.is_empty() {
161                all_pairs_certified = false;
162                continue;
163            }
164            let stats = pair_stats(&joint);
165            if stats.samples < min_pair_samples {
166                all_pairs_certified = false;
167            }
168            rho_eff = Some(match rho_eff {
169                Some(current) => current.min(stats.joint_miss_upper),
170                None => stats.joint_miss_upper,
171            });
172            pairs.insert((vi.clone(), vj.clone()), stats);
173        }
174    }
175
176    let certification = if all_pairs_certified && !pairs.is_empty() {
177        EnsembleCertification::Certified
178    } else {
179        EnsembleCertification::InsufficientEvidence
180    };
181    Ok(IndependenceStats {
182        miss_rates,
183        pairs,
184        // A bound may only be *displayed* when certified; the point value is
185        // still computed for diagnostics but gated here.
186        rho_eff: match certification {
187            EnsembleCertification::Certified => rho_eff,
188            EnsembleCertification::InsufficientEvidence => None,
189        },
190        validators: validators.len(),
191        certification,
192    })
193}
194
195/// Matched-stratum statistics for one pair's joint verdicts.
196fn pair_stats(joint: &[(bool, bool)]) -> PairStats {
197    let n = joint.len() as f64;
198    let q_i = joint.iter().filter(|&&(x, _)| x).count() as f64 / n;
199    let q_j = joint.iter().filter(|&&(_, y)| y).count() as f64 / n;
200    let joint_miss = joint.iter().filter(|&&(x, y)| x && y).count() as f64 / n;
201    let degenerate = q_i == 0.0 || q_i == 1.0 || q_j == 0.0 || q_j == 1.0;
202    let kappa = if degenerate {
203        None
204    } else {
205        Some(pearson_phi(joint))
206    };
207    // Hoeffding one-sided 95% upper bound: p̂ + sqrt(ln(1/0.05) / (2n)).
208    let joint_miss_upper = (joint_miss + ((1.0 / 0.05f64).ln() / (2.0 * n)).sqrt()).min(1.0);
209    PairStats {
210        q_i,
211        q_j,
212        kappa,
213        joint_miss,
214        joint_miss_upper,
215        samples: joint.len(),
216    }
217}
218
219/// Phi coefficient over paired miss indicators. Callers exclude degenerate
220/// marginals before calling.
221fn pearson_phi(pairs: &[(bool, bool)]) -> f64 {
222    let n = pairs.len() as f64;
223    let to_f = |b: bool| if b { 1.0 } else { 0.0 };
224    let mean_x: f64 = pairs.iter().map(|&(x, _)| to_f(x)).sum::<f64>() / n;
225    let mean_y: f64 = pairs.iter().map(|&(_, y)| to_f(y)).sum::<f64>() / n;
226    let (mut cov, mut var_x, mut var_y) = (0.0, 0.0, 0.0);
227    for &(x, y) in pairs {
228        let dx = to_f(x) - mean_x;
229        let dy = to_f(y) - mean_y;
230        cov += dx * dy;
231        var_x += dx * dx;
232        var_y += dy * dy;
233    }
234    if var_x <= f64::EPSILON || var_y <= f64::EPSILON {
235        return 0.0;
236    }
237    cov / (var_x.sqrt() * var_y.sqrt())
238}
239
240#[cfg(test)]
241mod tests {
242    use super::*;
243
244    #[test]
245    fn miss_std_matches_bernoulli() {
246        assert!((miss_std(0.5) - 0.5).abs() < 1e-12);
247        assert_eq!(miss_std(0.0), 0.0);
248        assert_eq!(miss_std(1.0), 0.0);
249    }
250
251    #[test]
252    fn lemma_5_1_reproduces_the_papers_mc3_arithmetic() {
253        // Paper III MC3: q = 0.1, kappa = 0.5 gives a joint miss of
254        // 0.01 + 0.5 * 0.09 = 0.055, not the independence product 0.01.
255        let joint = pairwise_joint_miss(0.1, 0.1, 0.5);
256        assert!((joint - 0.055).abs() < 1e-12, "{joint}");
257    }
258
259    #[test]
260    fn marginals_and_correlation_use_the_matched_stratum() {
261        // Validator a saw c1..c4; validator b saw only c1, c2. The pair's
262        // q_i must come from the matched {c1, c2}, not a's full history.
263        let records = vec![
264            VerdictRecord::new("a", "c1", true),
265            VerdictRecord::new("a", "c2", false),
266            VerdictRecord::new("a", "c3", false),
267            VerdictRecord::new("a", "c4", false),
268            VerdictRecord::new("b", "c1", true),
269            VerdictRecord::new("b", "c2", false),
270        ];
271        let stats = compute_with_floor(&records, 2).unwrap();
272        let pair = &stats.pairs[&("a".to_string(), "b".to_string())];
273        assert_eq!(pair.samples, 2);
274        assert!((pair.q_i - 0.5).abs() < 1e-12, "matched q_i, not 0.25");
275    }
276
277    #[test]
278    fn degenerate_marginals_use_the_joint_miss_never_kappa_zero() {
279        // Validator a never misses in the matched set: q_i = 0. Lemma 5.1
280        // requires the direct joint miss; kappa is not fabricated.
281        let records = vec![
282            VerdictRecord::new("a", "c1", false),
283            VerdictRecord::new("a", "c2", false),
284            VerdictRecord::new("b", "c1", true),
285            VerdictRecord::new("b", "c2", false),
286        ];
287        let stats = compute_with_floor(&records, 2).unwrap();
288        let pair = &stats.pairs[&("a".to_string(), "b".to_string())];
289        assert_eq!(pair.kappa, None);
290        assert_eq!(pair.joint_miss, 0.0);
291    }
292
293    #[test]
294    fn below_the_sample_floor_no_bound_is_displayed() {
295        let records = vec![
296            VerdictRecord::new("a", "c1", true),
297            VerdictRecord::new("b", "c1", true),
298        ];
299        let stats = compute(&records).unwrap();
300        assert_eq!(
301            stats.certification,
302            EnsembleCertification::InsufficientEvidence
303        );
304        assert_eq!(
305            stats.rho_eff, None,
306            "insufficient evidence displays no number"
307        );
308    }
309
310    #[test]
311    fn three_validator_bound_is_never_tighter_than_its_best_pair() {
312        // MC-T companion: with three validators, rho_eff equals the minimum
313        // pairwise upper bound — never anything smaller.
314        let mut records = Vec::new();
315        for i in 0..40 {
316            let candidate = format!("c{i}");
317            let a_miss = i % 10 == 0;
318            let b_miss = i % 10 == 0; // b correlates with a
319            let c_miss = i % 13 == 0; // c is mostly independent
320            records.push(VerdictRecord::new("a", &candidate, a_miss));
321            records.push(VerdictRecord::new("b", &candidate, b_miss));
322            records.push(VerdictRecord::new("c", &candidate, c_miss));
323        }
324        let stats = compute(&records).unwrap();
325        assert_eq!(stats.validators, 3);
326        assert_eq!(stats.certification, EnsembleCertification::Certified);
327        let best_pair = stats
328            .pairs
329            .values()
330            .map(|p| p.joint_miss_upper)
331            .fold(f64::INFINITY, f64::min);
332        assert_eq!(stats.rho_eff.unwrap(), best_pair);
333        // And the certified bound is conservative: at or above every pair's
334        // point estimate minimum.
335        let best_point = stats
336            .pairs
337            .values()
338            .map(|p| p.joint_miss)
339            .fold(f64::INFINITY, f64::min);
340        assert!(stats.rho_eff.unwrap() >= best_point);
341    }
342
343    #[test]
344    fn empty_ledger_is_error() {
345        assert!(compute(&[]).is_err());
346    }
347}
perspt_sdk/independence.rs

perspt_sdk/
independence.rs
