Subject: [Ntp] Byztime

From: Daniel Franke <[email-masked]>
Date: Thu, 25 Feb 2021 16:29:53 -0500

I'm happy to announce the release of Byztime, a protocol and implementation
for Byzantine-fault-tolerant time synchronization among a group of peers,
without reliance on any external time authority. This project has been a
couple years in the making at Akamai and I'm thrilled that it's finally
public and open source!

<https://github.com/akamai-contrib/byztimed>

The time kept by Byztime is simply a counter that advances at a rate of
something very close to one unit per second, such that all nodes are in
close agreement as to its current value. Byztime timestamps have no
well-defined epoch. If all nodes have correctly-set system clocks when
first initialized, then Byztime will initially match POSIX time, but will
eventually drift away from it since 1. there is no external source keeping
it in sync, and 2. Byztime's timescale lacks leap seconds.

Byztime's algorithm is focused on keeping its worst-case error — the
absolute distance between any two correct nodes' estimate of the current
time — as small as possible. It achieves this somewhat at the expense of
typical-case error, using only the single highest-quality time sample from
each peer rather than combining many samples to smooth out network jitter.
In the worst case, the difference between two correct nodes' clocks will
asymptotically converge toward 4δ + 4ερ, where δ is the one-way network
latency between the two farthest-spaced peers, ε is the (dimensionless)
drift rate of correct nodes' hardware clocks, and ρ is the polling
interval. If all nodes behave honestly, the bound improves to 2δ + 2ερ and
will be reached after a single round of the protocol rather than converging
asymptotically.

Byztimed runs completely independently of NTP, and a bad NTP time source
will not disrupt Byztime. This comes with a minor caveat: just before the
daemon shuts down it records the current offset between Byztime time and
system time, and uses this offset to re-initialize its estimate following a
reboot. The only time this particularly matters is if many nodes reboot
simultaneously and the network loses quorum. What happens in this case
depends somewhat on NTP and what order things start up in at boot time. If
Byztime starts before NTP starts and shuts down only after NTP shuts down,
then the continuity of the Byztime timescale will be as good as the RTC and
the CMOS battery of the restarting nodes, but no better. On the other hand
if NTP is allowed to stabilize the system clock before Byztime starts up,
then the continuity of the Byztime scales will be as good as its NTP
sources — which is probably a lot better than your RTC, but could be
arbitrarily bad if the NTP source is faulty. Again, this only becomes an
issue if Byztime loses quorum, meaning ⅓ or more of the network reboots at
once.

Byztime nodes use NTS to authenticate their peers (even though this is
probably a bit of overkill, since unlike NTP it's unlikely to need
the massive scale-out that NTS is designed to support).  As a result,
it currently relies on the system time for determining whether an X.509
certificate is expired. Once Roughtime matures a bit we may consider
integrating a Roughtime client into byztimed for certificate validation
purposes.

Byztime is too young a protocol to be thinking about standardization yet,
but I intend to write and submit a protocol spec for publication as an
Experimental RFC via the Independent Stream. I'll keep this WG updated on
any major milestones and I anticipate that the draft will pass through here
for conflict review.