crates/estate-clock/src/decide.rs
//! Samples in, one decision out. Pure — no socket, no clock, no syscall.
//!
//! A time-sync bug is an **arithmetic** bug: an off-by-one in a quorum, a
//! comparison that lets one hostile host through, a sanity bound that is not a
//! bound. So the arithmetic lives here with nothing else in it.
//!
//! # Why the median, and what a hostile source can do
//!
//! Against three sources the median is one of the two that agree: a liar can
//! only be the smallest or the largest, and to be the *middle* it has to sit
//! between two honest answers — roughly right, which is to say harmless. What a
//! liar **can** do is drag the set apart until fewer than the quorum sit within
//! [`AGREEMENT_MS`] of the median; then this refuses and the clock is left
//! alone. Refusing is the safe direction: a wrong clock refuses genuine
//! credentials, a clock moved by an attacker accepts forged ones.
//!
//! The median is an **observed value, never an average of two**: every value
//! this can apply is one some named source is on record for.
//!
//! # The quorum, and the one-source case
//!
//! [`quorum_for`]: with several configured sources, two must agree — one host
//! that is wrong, or lying, is invisible inside a single sample. With exactly
//! **one** configured source, one answer decides. That is not a weaker rule
//! slipped in: it is the site having named its single root of time, and on the
//! appliance that source is the front's *signed* answer to a nonce the appliance
//! chose ([`crate::peer`]) — the signature is what a quorum would otherwise buy.
//! A requirement of two that one configured source can never meet would be a
//! clock that is never set, which is the defect this crate closes.
/// How many sources must agree when more than one is configured.
pub const QUORUM: usize = 2;
/// How far two samples may sit apart and still count as agreeing. Thirty
/// seconds: far wider than an HTTP date's rounding plus a round trip, far
/// narrower than the five-minute credential window.
pub const AGREEMENT_MS: i64 = 30_000;
/// Below this the clock is reported right and not touched. An HTTP date is
/// second-resolution, so anything under two seconds is inside the source's own
/// rounding — noise, not information.
pub const MIN_CORRECTION_MS: i64 = 2_000;
/// The floor of the sanity window: `Thu, 01 Jan 2026 00:00:00 GMT`. Nothing that
/// runs this code existed before it.
pub const EARLIEST_SANE_UNIX: i64 = 1_767_225_600;
/// The ceiling: `Mon, 01 Jan 2046 00:00:00 GMT`. An edit in 2045 is a much
/// smaller problem than accepting a source that says 2145 and expiring every
/// certificate on the box.
pub const LATEST_SANE_UNIX: i64 = 2_398_377_600;
/// One source's answer, reduced to the numbers that matter.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Sample {
/// The source's label, for the report.
pub source: String,
/// What the source thinks the epoch millisecond is.
pub source_unix_ms: i64,
/// `source - local` in milliseconds, at the instant of the read. Negative
/// means this box is **fast**.
pub offset_ms: i64,
}
/// What [`decide`] concluded, and what it threw away getting there.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Verdict {
pub decision: Decision,
/// Samples outside the sanity window, with the epoch millisecond each claimed.
pub insane: Vec<(String, i64)>,
}
/// The four things that can be true after the sources have answered.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Decision {
/// Correct the clock by `offset_ms`. `agreed` names the sources that voted.
Correct { offset_ms: i64, agreed: Vec<String> },
/// The sources agree with this box to within [`MIN_CORRECTION_MS`].
AlreadyRight { offset_ms: i64, agreed: Vec<String> },
/// Fewer usable samples than the quorum.
NoQuorum { had: usize, needed: usize },
/// Samples came back and could not be reconciled.
Disagree {
spread_ms: i64,
offsets: Vec<(String, i64)>,
},
}
/// Every configured source's answer, and the verdict over the good ones.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Poll {
/// One entry per configured source, in configuration order: the sample, or
/// `(label, why it contributed nothing)`.
pub answers: Vec<Result<Sample, (String, String)>>,
pub verdict: Verdict,
}
impl Poll {
/// Decide over `answers` with the quorum for that many configured sources.
pub fn over(answers: Vec<Result<Sample, (String, String)>>) -> Poll {
let samples: Vec<Sample> = answers
.iter()
.filter_map(|a| a.as_ref().ok().cloned())
.collect();
let verdict = decide(&samples, quorum_for(answers.len()));
Poll { answers, verdict }
}
}
/// The quorum for a list of `configured` sources. See the module note.
pub fn quorum_for(configured: usize) -> usize {
if configured <= 1 {
1
} else {
QUORUM
}
}
/// Whether an epoch second is one a working source could plausibly have said.
pub fn is_sane(unix_s: i64) -> bool {
(EARLIEST_SANE_UNIX..=LATEST_SANE_UNIX).contains(&unix_s)
}
fn median(values: &[i64]) -> i64 {
let mut sorted = values.to_vec();
sorted.sort_unstable();
sorted[sorted.len() / 2]
}
/// Turn the samples into a decision, needing `quorum` agreeing survivors.
pub fn decide(samples: &[Sample], quorum: usize) -> Verdict {
let quorum = quorum.max(1);
let mut insane = Vec::new();
let mut sane = Vec::new();
for sample in samples {
if is_sane(sample.source_unix_ms.div_euclid(1_000)) {
sane.push(sample.clone());
} else {
insane.push((sample.source.clone(), sample.source_unix_ms));
}
}
if sane.len() < quorum {
return Verdict {
decision: Decision::NoQuorum {
had: sane.len(),
needed: quorum,
},
insane,
};
}
let offsets: Vec<i64> = sane.iter().map(|s| s.offset_ms).collect();
let middle = median(&offsets);
let agreed: Vec<&Sample> = sane
.iter()
.filter(|s| (s.offset_ms - middle).abs() <= AGREEMENT_MS)
.collect();
if agreed.len() < quorum {
let spread_ms =
offsets.iter().max().copied().unwrap_or(0) - offsets.iter().min().copied().unwrap_or(0);
return Verdict {
decision: Decision::Disagree {
spread_ms,
offsets: sane
.iter()
.map(|s| (s.source.clone(), s.offset_ms))
.collect(),
},
insane,
};
}
let voted: Vec<String> = agreed.iter().map(|s| s.source.clone()).collect();
let offset_ms = median(&agreed.iter().map(|s| s.offset_ms).collect::<Vec<_>>());
let decision = if offset_ms.abs() < MIN_CORRECTION_MS {
Decision::AlreadyRight {
offset_ms,
agreed: voted,
}
} else {
Decision::Correct {
offset_ms,
agreed: voted,
}
};
Verdict { decision, insane }
}
#[cfg(test)]
mod tests {
use super::*;
const NOW_MS: i64 = 1_789_000_000_000; // mid-2026
fn at(source: &str, unix_ms: i64, offset_ms: i64) -> Sample {
Sample {
source: source.to_owned(),
source_unix_ms: unix_ms,
offset_ms,
}
}
#[test]
fn the_two_hour_boot_offset_is_corrected_and_signed_the_way_the_appliance_reads_it() {
// Measured: the box is 7200 s FAST, so every source is behind it and
// the correction is negative.
let samples = vec![
at("a", NOW_MS, -7_200_000),
at("b", NOW_MS, -7_199_900),
at("c", NOW_MS, -7_200_100),
];
let Verdict { decision, insane } = decide(&samples, quorum_for(3));
assert!(insane.is_empty());
assert_eq!(
decision,
Decision::Correct {
offset_ms: -7_200_000,
agreed: vec!["a".into(), "b".into(), "c".into()]
}
);
}
#[test]
fn with_several_sources_configured_one_answer_is_never_a_quorum() {
let samples = vec![at("only", NOW_MS, -7_200_000)];
assert_eq!(
decide(&samples, quorum_for(3)).decision,
Decision::NoQuorum { had: 1, needed: 2 }
);
assert_eq!(
decide(&[], quorum_for(1)).decision,
Decision::NoQuorum { had: 0, needed: 1 }
);
}
#[test]
fn with_exactly_one_source_configured_its_answer_decides() {
// The appliance's configuration on gunnar.rs: one signed peer.
assert_eq!(quorum_for(1), 1);
let samples = vec![at("peer://10.13.8.99:50123", NOW_MS, -7_199_500)];
assert!(matches!(
decide(&samples, quorum_for(1)).decision,
Decision::Correct {
offset_ms: -7_199_500,
..
}
));
}
#[test]
fn the_sanity_bounds_still_apply_to_a_single_trusted_source() {
// A correctly signed 1970 is still 1970. A signature proves who said it,
// not that they were right.
let samples = vec![at("peer://10.13.8.99:50123", 0, -NOW_MS)];
let verdict = decide(&samples, quorum_for(1));
assert_eq!(
verdict.insane,
vec![("peer://10.13.8.99:50123".to_owned(), 0)]
);
assert_eq!(verdict.decision, Decision::NoQuorum { had: 0, needed: 1 });
}
#[test]
fn a_source_that_says_1970_is_refused_and_does_not_count_towards_the_quorum() {
let samples = vec![at("broken", 0, -NOW_MS), at("good", NOW_MS, -7_200_000)];
let Verdict { decision, insane } = decide(&samples, quorum_for(2));
assert_eq!(insane, vec![("broken".to_owned(), 0)]);
assert_eq!(decision, Decision::NoQuorum { had: 1, needed: 2 });
}
#[test]
fn a_source_that_says_2145_is_refused_the_same_way() {
let year_2145_ms = 5_522_000_000_000_i64;
let samples = vec![
at("a", NOW_MS, 0),
at("b", NOW_MS, 0),
at("future", year_2145_ms, year_2145_ms - NOW_MS),
];
let Verdict { decision, insane } = decide(&samples, quorum_for(3));
assert_eq!(insane, vec![("future".to_owned(), year_2145_ms)]);
assert!(matches!(decision, Decision::AlreadyRight { .. }));
}
#[test]
fn one_hostile_source_among_three_cannot_move_the_answer() {
let samples = vec![
at("honest-a", NOW_MS, -7_200_000),
at("honest-b", NOW_MS, -7_199_500),
at("hostile", NOW_MS + 86_400_000, 86_400_000),
];
match decide(&samples, quorum_for(3)).decision {
Decision::Correct { offset_ms, agreed } => {
assert_eq!(offset_ms, -7_199_500, "the median is an honest sample");
assert!(!agreed.iter().any(|s| s == "hostile"));
}
other => panic!("the honest majority must carry, got {other:?}"),
}
}
#[test]
fn two_sources_that_disagree_are_refused_rather_than_averaged() {
let samples = vec![at("a", NOW_MS, -7_200_000), at("b", NOW_MS, 0)];
match decide(&samples, quorum_for(2)).decision {
Decision::Disagree { spread_ms, offsets } => {
assert_eq!(spread_ms, 7_200_000);
assert_eq!(offsets.len(), 2);
}
other => panic!("a 2 h spread across two sources must refuse, got {other:?}"),
}
}
#[test]
fn three_sources_that_all_disagree_refuse_rather_than_pick_the_middle_one() {
let samples = vec![
at("a", NOW_MS, -7_200_000),
at("b", NOW_MS, 0),
at("c", NOW_MS, 7_200_000),
];
assert!(matches!(
decide(&samples, quorum_for(3)).decision,
Decision::Disagree { .. }
));
}
#[test]
fn a_clock_already_right_is_not_corrected_by_rounding() {
let samples = vec![at("a", NOW_MS, 900), at("b", NOW_MS, -400)];
match decide(&samples, quorum_for(2)).decision {
Decision::AlreadyRight { offset_ms, .. } => assert_eq!(offset_ms, 900),
other => panic!("sub-second noise must not be a correction, got {other:?}"),
}
}
#[test]
fn the_smallest_offset_that_is_still_a_correction_is_the_minimum() {
let under = vec![at("a", NOW_MS, MIN_CORRECTION_MS - 1)];
assert!(matches!(
decide(&under, 1).decision,
Decision::AlreadyRight { .. }
));
let over = vec![at("a", NOW_MS, -MIN_CORRECTION_MS)];
assert!(matches!(
decide(&over, 1).decision,
Decision::Correct { .. }
));
}
#[test]
fn the_chosen_offset_is_always_one_a_named_source_actually_said() {
let samples = vec![at("a", NOW_MS, -10_000), at("b", NOW_MS, -30_000)];
match decide(&samples, quorum_for(2)).decision {
Decision::Correct { offset_ms, .. } => assert!(
offset_ms == -10_000 || offset_ms == -30_000,
"{offset_ms} is an average, not an observation"
),
other => panic!("20 s apart is inside the agreement window, got {other:?}"),
}
}
}