#!/usr/bin/env python3
"""Reference implementation of the fleetmesh window evaluator and trust weighting.
Standard library only. Every constant is read from schema/constants.json rather
than hardcoded, so this file and the protocol version digest cannot disagree.
Exists to make the arithmetic executable. Writing it found three things the
specification referenced but never defined: class(overrun, divergence), the
per-tier limit ceilings, and the divergence tolerance that triggers S2.
"""
from __future__ import annotations
import math
from typing import Any, Mapping, Optional, Sequence
from ..wire import schema_files
C = schema_files.load_constants()
SEV_ORDER: list[str] = ['S0', 'S1', 'S2', 'S3', 'S4']
[docs]def counter_of(limit: str) -> str:
"""The receipt counter a limit is priced against. Most limits and counters
share a name; `grant.counter_of` in constants.json names the exceptions.
conn_rate was in every tier's ceilings and priced by nothing, because the
session counts sessions as conn_open and this looked a limit up by its own
name - the third constant found declared and never read, after dup_ratio
and max_clock_skew_seconds. The mapping is digested now, so an implementer
cannot miss it the way this one did."""
return C['grant'].get('counter_of', {}).get(limit, limit)
[docs]def outranks(tier: str, other: str) -> bool:
"""Whether `tier` sits above `other` on the ladder.
The order is tier_weight's, which is the one the specification already
ranks them by - a reporter's word is weighed by it - rather than a second
list that could disagree with the first. An unknown tier ranks lowest,
which is what probation means.
"""
w = C['trust']['tier_weight']
return w.get(tier, 0.0) > w.get(other, 0.0)
[docs]def ceilings(tier: str) -> Mapping[str, Any]:
"""Limit ceilings for a tier. dup_ratio is a quality signal and does not scale."""
t = dict(C['tier_limits'][tier])
t['dup_ratio'] = C['tier_limits']['dup_ratio']['all_tiers']
return t
[docs]def classify(overrun: float, divergence: float) -> str:
"""class(overrun, divergence) -> severity, for one limit.
The specification defines a window as the max over all limits of this
function and never defines the function, so the shape below is a choice.
A misreport is a floor of S2 and not a ceiling. Returning S2 the moment
divergence crossed its threshold - which is what this did - priced a peer
that overran its limit four times over and lied about it *below* the same
peer reporting it honestly, because honesty reaches S3 on overrun alone.
fleetmesh_core/peering/badpeer.py runs both, and the inversion is what it found. Lying must
never be the cheaper option, so divergence raises the class the overrun
already earned rather than replacing it.
"""
s = C['grant']['severity_classification']
if overrun >= s['S3_if_overrun_at_least']:
by_overrun = 'S3'
elif overrun >= s['S2_if_overrun_at_least']:
by_overrun = 'S2'
elif overrun >= s['S1_if_overrun_at_least']:
by_overrun = 'S1'
else:
by_overrun = 'S0'
if divergence > s['S2_if_divergence_above']:
return worse(by_overrun, 'S2')
return by_overrun
[docs]def worse(a: str, b: str) -> str:
return a if SEV_ORDER.index(a) >= SEV_ORDER.index(b) else b
[docs]def per_session(name: str) -> int:
"""What one session costs of this counter.
One for almost everything: a session is one connection, one request, one
of most things. Ranges are the exception and the number is not invented
here - `tier_limits.ranges_per_session` is where it was measured on the
alpha mesh and where it is already justified, and a second copy would be a
second thing to keep true.
"""
if name == 'sync_ranges':
return C['tier_limits']['ranges_per_session']
return 1
[docs]def evaluate_window(limits: Mapping[str, Any], measured: Mapping[str, int | float], claimed: Mapping[str, int | float]) -> Mapping[str, Any]:
"""Evaluate one closed window.
limits/measured/claimed are dicts keyed by limit name. Returns the window
severity and the per-limit detail that produced it.
"""
floor_frac = C['grant']['divergence_floor_fraction']
sessions = C['grant']['divergence_floor_sessions']
severity = 'S0'
detail: dict[str, Mapping[str, Any]] = {}
for name, limit in sorted(limits.items()):
if name == 'dup_ratio' or limit is None:
continue
m = _counter(measured, counter_of(name))
c = _counter(claimed, counter_of(name))
# A limit of zero sells nothing, so anything measured is an overrun of
# every class. It is reported as the S3 threshold rather than as
# infinity: infinity is not JSON, and the receipt and the report that
# cite this number have to be.
s3 = C['grant']['severity_classification']['S3_if_overrun_at_least']
overrun = max(0.0, (m / limit - 1)) if limit else (float(s3) if m else 0.0)
# The floor is a fraction of the limit OR this many SESSIONS of the
# counter, whichever is larger, and a counter below it is not evaluated
# for divergence at all - the rule dup_ratio below already followed and
# this one did not.
#
# A fraction alone collapses with the limit it is taken from, so an S2
# that quarters the limits lowers the floor that produced it and prices
# the same lost unit higher next window. A flat minimum was tried first
# and was the right shape at the wrong size: the quantum in which
# measurement is lost is a session, and one session is one request but
# sixteen ranges, so a single number is twenty sessions of headroom for
# one counter and one and a quarter for another. The same lost session
# then priced S0 against a trusted peer and S2 against a member peer in
# the same hour, on identical arithmetic.
#
# In sessions, one lost session is at or under divergence_tolerance by
# construction, whatever the counter and whatever the tier.
#
# Overrun is untouched. It is measured against the limit and needs no
# sample size: one request over a ceiling of zero is an overrun at any
# volume, and quietness must never buy room to exceed a grant.
floor = max(limit * floor_frac, per_session(name) * sessions)
divergence = abs(m - c) / max(m, floor) if m >= floor else 0.0
s = classify(overrun, divergence)
detail[name] = {'measured': m, 'claimed': c, 'limit': limit,
'overrun': round(overrun, 6),
'divergence': round(divergence, 6), 'severity': s}
severity = worse(severity, s)
# dup_ratio is a ratio and not a counter. It has no line in the grant, so
# AIMD never scales it, and its ceiling is the same at every tier. The
# receiver alone knows what it already held, so there is no claim to
# compare against and no divergence term: the ratio is priced on overrun
# alone. Under the same floor that guards divergence, a ratio over a
# handful of events is noise and is not evaluated.
if 'dups_sent' in measured and 'events_in' in measured:
ceiling = C['tier_limits']['dup_ratio']['all_tiers']
delivered = measured['events_in']
floor = max((limits.get('events_in') or 0) * floor_frac, per_session('events_in') * sessions)
if delivered >= floor:
ratio = float(measured['dups_sent']) / delivered
overrun = max(0.0, ratio / ceiling - 1)
s = classify(overrun, 0.0)
detail['dup_ratio'] = {'measured': round(ratio, 6), 'claimed': None,
'limit': ceiling, 'overrun': round(overrun, 6),
'divergence': 0.0, 'severity': s,
'over': measured['dups_sent'], 'of': delivered}
severity = worse(severity, s)
return {'severity': severity, 'per_limit': detail}
[docs]def within(limits: Mapping[str, Any], tier: str) -> Mapping[str, Any]:
"""Hold a limit set inside the ceilings of the tier it is written at.
constants.json states the invariant plainly: a grant MAY set any limit
lower than its tier ceiling and MUST NOT set one higher. `_write_grant`
applies it at first issue and the remedy never did. S2 quarters the limits
and drops the tier to probation, and `max(probation, v * 0.25)` is a floor,
so for any peer above probation it did nothing at all: an anchor came out
of an S2 holding 12,000 events an hour at a tier whose ceiling is 300 -
forty times over - and held it for as long as it produced nothing
measurable, because an unevaluated window never adjusts anything. The next
clean window then dropped it from 12,000 to 300 in one step, which was the
same defect seen from the other side.
Applied on the way out of every branch, the remedy cannot leave a grant its
own tier forbids, and a grant that somehow arrived in that state is
repaired by the next adjustment rather than surviving it.
"""
ceil = ceilings(tier)
return {k: (min(v, ceil[k]) if k in ceil else v) for k, v in limits.items()}
[docs]def strain(limit_name: str, limit: int | float, used: Optional[Mapping[str, int | float]]) -> float:
"""How much of one limit the closed window actually carried, in [0, 1].
An S0 window can reach 1.1 of a limit and still be clean, so the ratio is
clipped: a peering is not owed extra growth for the tolerance.
"""
if not limit or limit <= 0 or not used:
return 0.0
measured = used.get(counter_of(limit_name), 0)
return max(0.0, min(1.0, float(measured) / float(limit)))
[docs]def step_fraction(limit_name: str, limit: int | float, used: Optional[Mapping[str, int | float]]) -> float:
"""The additive step for one limit, as a fraction of its tier ceiling.
Wood is laid down where the strain was. The step used to be a flat fraction
of the ceiling whatever the window carried, so a peering moving one event an
hour grew exactly as fast as one running at its limit: capacity was priced
in windows rather than in work, and the cheapest route to a large grant was
to be present and idle. It is scaled by use now, with a floor - a quiet
peering still creeps upward, because a tree does grow without wind and it
grows tall and slender and cannot stand.
"""
g = C['grant']
if not g.get('aimd_increase_is_load_weighted'):
return float(g['aimd_increase_fraction'])
return max(float(g['aimd_min_increase_fraction']),
float(g['aimd_increase_fraction']) * strain(limit_name, limit, used))
[docs]def as_limits(d: Mapping[str, Any]) -> dict[str, int]:
"""Grant limits, as integers, rounded DOWN.
canonical.numbers says it plainly: integers, written as plain decimal
digits, and the only fractions anywhere in this protocol are in
constants.json itself. A commitment is taken over canonical(grant), so a
float in a limit is not a cosmetic problem - two implementations may
serialise 3.7999999999999994 differently and the commitment stops
verifying.
It never mattered until the arithmetic stopped being flat. The old step was
a fixed fraction of a ceiling and always clamped to it, so every limit came
out an integer by luck; a step scaled by strain, a decay, and a capacity
shed all produce fractions. Found on a live node an hour after the first
deploy, in a grant reading conn_rate 3.7999999999999994.
Down and not nearest, so a limit is never larger than what the ladder
decided. Down means towards minus infinity for negatives too
(math.floor), so -0.5 becomes -1 rather than 0: a limit is never
rounded up past what was decided, whichever side of zero it sits.
Anything that is not a real number raises ValueError naming the key.
A grant is committed to and verified by its canonical bytes, so a
string or None that slipped through here would be signed into a
commitment nobody can reason about; refusing is the honest answer.
"""
out: dict[str, int] = {}
for k, v in d.items():
if isinstance(v, bool) or not isinstance(v, (int, float)):
raise ValueError('limit %r is not a number: %r' % (k, v))
if v != v or v in (float('inf'), float('-inf')):
raise ValueError('limit %r is not finite: %r' % (k, v))
out[k] = math.floor(v)
return out
[docs]def opening_limits(tier: str) -> dict[str, int]:
"""What a fresh grant at a tier carries.
Volume opens at a fraction of the ceiling so that carrying load is what
earns the rest; a grant that opened at the full ceiling left the additive
increase nothing to do, which is why nothing in this protocol grew. The
structural limits open at the ceiling, because a peer needs enough plumbing
to demonstrate anything at all: what is earned is volume, never the right to
open a session.
"""
g = C['grant']
ceil = ceilings(tier)
frac, applies = g['opening_limit_fraction'], set(g['opening_applies_to'])
return as_limits({k: (v * frac if k in applies else v)
for k, v in ceil.items() if k != 'dup_ratio'})
[docs]def decay(limits: Mapping[str, int | float], tier: str, fraction: Optional[float] = None) -> dict[str, int]:
"""Give back what disuse has not earned, down to where a stranger starts.
The pair to growth, and the reason growth may be allowed to reach a ceiling
at all. A limit moved up on a clean window and down on a fault and never
decayed, so capacity earned in one busy week sat there a year later as
surface nobody was watching.
The floor is the tier's opening limits, never lower: what a peer has not
used it gives back, and what every peering is given it keeps. The structural
limits open at the ceiling, so they never decay - an error budget that
wasted away would trip on the first bad hour.
"""
f = C['grant']['decay_fraction'] if fraction is None else fraction
floor = opening_limits(tier)
return as_limits({k: max(floor[k], v * f) if k in floor else v for k, v in limits.items()})
[docs]def adjust(limits: Mapping[str, int | float], tier: str, severity: str, used: Optional[Mapping[str, int | float]] = None) -> tuple[dict[str, int], str, str]:
"""Apply the ladder's remedy to a limit set. Returns (limits, tier, note).
`used` is the closed window's measured counters, and the clean branch grows
each limit in proportion to how much of it that window carried. An
evaluation that offers none gets the minimum step and never the full one:
absent evidence of load is not evidence of load.
Every branch returns limits inside the ceilings of the tier it returns, so
a grant's tier and the numbers beside it can never disagree.
"""
g = C['grant']
if severity not in SEV_ORDER:
raise ValueError('severity %r is not on the ladder' % (severity,))
if tier not in C['tier_limits'] or tier == 'dup_ratio':
raise ValueError('tier %r is not a tier' % (tier,))
probation = ceilings('probation')
if severity == 'S0':
ceil, floor = ceilings(tier), opening_limits(tier)
out: dict[str, float | int] = {}
gave_back = False
for k, v in limits.items():
if k not in ceil:
out[k] = v
continue
# A limit this window MEASURED nothing for, sitting above where a
# peering opens, gives some of itself back rather than creeping up.
# Below the opening value the floor step still applies, because a
# peering that is merely new must not be frozen.
#
# `used is None` is not a measurement of zero. An evaluation that
# offers no counters gets the floor step and no decay, for the same
# reason it does not get the full step: absent evidence of load is
# not evidence of load, in either direction. This is the rule the
# window arithmetic already applies to an absent claim.
if used is not None and strain(k, v, used) == 0.0:
if v > floor.get(k, 0):
out[k] = max(floor[k], v * g['decay_fraction'])
gave_back = True
else:
# At or below where a peering opens and carrying nothing:
# left exactly where it is. Stepping up here and decaying
# back next window made an idle grant flutter across the
# opening value for ever, and every crossing published a
# kind 30801 and sent the subject an amend. That is the
# flapping the capacity ladder has hysteresis to avoid, in
# the one place it had none. A limit that measured zero has
# demonstrated nothing and is owed nothing.
out[k] = v
else:
out[k] = v + ceil[k] * step_fraction(k, v, used)
return (as_limits(within(out, tier)), tier,
'additive increase, and decay on what went unused' if gave_back
else 'additive increase')
if severity == 'S1':
return (as_limits(within({k: max(probation.get(k, 0), v * g['aimd_decrease_s1'])
for k, v in limits.items()}, tier)), tier, 'halved')
if severity == 'S2':
# Once the tier is probation the quartering is dead arithmetic: a
# quarter of any higher tier's limit is still far above what probation
# allows, so the ceiling is always what binds. S2 does not leave a peer
# a quarter of what it had. It makes it a stranger again.
return (as_limits(within({k: max(probation.get(k, 0), v * g['aimd_decrease_s2'])
for k, v in limits.items()}, 'probation')),
'probation', 'reduced to the probation ceiling, tier to probation')
if severity == 'S3':
return ({k: 0 for k in limits}, tier,
'zero for %d hours, then probation' % g['s3_zero_hours'])
# S4, and only S4: an unknown severity was refused above. It used to fall
# through to here, so a misspelt severity revoked the grant.
return ({k: 0 for k in limits}, 'revoked', 'revoked')
[docs]def reporter_weight(tier_of_reporter: str, clean_windows: int, contradicted: int = 0, evaluated: int = 0) -> float:
t = C['trust']
tw = t['tier_weight'].get(tier_of_reporter, 0.0)
age = min(1.0, clean_windows / float(t['age_factor_windows']))
fr = (contradicted / float(evaluated)) if evaluated else float(t['false_report_rate_when_undefined'])
return float(tw * age * (1 - fr))
[docs]def view(own_severity: str, reports: Sequence[Mapping[str, Any]]) -> str:
"""Most severe finding backed by at least theta of weight, or my own if worse.
reports: [{'severity': 'S2', 'weight': 0.6}, ...]. Deliberately not a mean:
the severity scale is ordinal and its remedies are nothing like evenly spaced.
"""
# Fixed point, in millionths. Weights are published to six decimals, and
# a sum of floats is not the same number on every runtime: CPython 3.12
# compensates its sum() and reaches exactly 1.0 where a naive left fold
# gets 0.999999999, which is one implementation finding a sybil and the
# other not, on the same reports. Integers add the same way everywhere.
theta = _micro(C['trust']['view_threshold_theta'])
if own_severity not in SEV_ORDER:
raise ValueError('severity %r is not one of %s' % (own_severity, SEV_ORDER))
# A report whose severity is not on the scale backs nothing: it is one
# reporter's defect, and refusing the whole view over it would let one
# malformed report hide every well-formed one. A report that is not an
# object, or whose weight is not a number, is refused: that is the
# caller's shape, not a reporter's claim.
for r in reports:
if not isinstance(r, Mapping):
raise TypeError('a report is an object')
_micro(r.get('weight'))
reports = [r for r in reports if r.get('severity') in SEV_ORDER]
result = 'S0'
for s in ['S4', 'S3', 'S2', 'S1']:
backing = sum(_micro(r['weight']) for r in reports
if SEV_ORDER.index(r['severity']) >= SEV_ORDER.index(s))
if backing >= theta:
result = s
break
return worse(result, own_severity)
def _counter(m: Mapping[str, Any], k: str) -> int | float:
"""A counter is a number; absent or null is zero. A string is refused,
never read as zero: a receipt that says "events_in": "lots" is malformed,
and treating it as nothing would price an overrun as clean."""
v = m.get(k)
if v is None:
return 0
if isinstance(v, bool) or not isinstance(v, (int, float)):
raise ValueError('counter %r is not a number: %r' % (k, v))
return v
def _micro(x: Any) -> int:
"""A weight in millionths, rounded half away from zero as the vectors are."""
if isinstance(x, bool) or not isinstance(x, (int, float)):
raise TypeError('a weight is a number')
return int(round(float(x) * 1_000_000))