[Ntp] Byztime

Daniel Franke <dfoxfranke@gmail.com> Thu, 25 February 2021 21:30 UTC

Return-Path: <dfoxfranke@gmail.com>
X-Original-To: ntp@ietfa.amsl.com
Delivered-To: ntp@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id A5A9B3A0B8F for <ntp@ietfa.amsl.com>; Thu, 25 Feb 2021 13:30:07 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level:
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id FROqPCJ3iwx4 for <ntp@ietfa.amsl.com>; Thu, 25 Feb 2021 13:30:05 -0800 (PST)
Received: from mail-pf1-x436.google.com (mail-pf1-x436.google.com [IPv6:2607:f8b0:4864:20::436]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B0E423A0B70 for <ntp@ietf.org>; Thu, 25 Feb 2021 13:30:05 -0800 (PST)
Received: by mail-pf1-x436.google.com with SMTP id r5so4461882pfh.13 for <ntp@ietf.org>; Thu, 25 Feb 2021 13:30:05 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=Smj4dSGvvLGYqfCb7Q2poDrKUi+6x6zYShOT3swhyFo=; b=FZIMHrg0oOy1Hi66qS8t9n43PtmrS1T48LL4K8pa3d4WHLF8hfVZ6Qj1S1EaggjjE0 +mhUiDrREGu16+hYn9H9eW66wqpjHsgFCVZuWw6OJ2/OSx0Z4EQ4hUyZKF9NSzj2oGM8 QPs62vGRASLrkG2ylJkk1YNLd5qaHzvgRL09JA6YmLu6kpHhnw/TBqfYBOVOrhXJ5I2K QmybugmsczvP/agr0262gcb/ipdSiZvWJYtgTcU/ZTNICpRsmVQtsF5C5QNKgrh5N7Yc ygIsaLeWJ7qa+ohp1aOmm3/8JgIz0d8pwScOOcCVja5WM04rdMFKFYZTepASIfGriB2N DvbA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=Smj4dSGvvLGYqfCb7Q2poDrKUi+6x6zYShOT3swhyFo=; b=aEh8U3wG6pdlnv9jUiuz26fmiV4pExAFmAWTSEslOzs9L8gbz74q6MUZ7Dv2w7i1zy s0CpSU5QDFutzQJ6EWF5PgyQPlAGYccEXtfOR4mlB5fUYJnVaZrM8tqEvNTjLBw4aqxs aaftuuYLXm1fTGK9QyuXij9AXR4mlXgCKn3ivTdnZAj3jSmshUd/I1/yM70a29N44S51 IOW1U9wIffo6KVOFc4f2aAOEtCCTcoNJwqrbHqapqv2BYQagtUtPOMHRxJaZVh7bK55d 1/5USrWKYtO5czuceiVnmIIcoEVk3K+cYRGTAozHgLYMWkoae5/Nvi4EKzvcwj7MGfyV bRqQ==
X-Gm-Message-State: AOAM531PUDo3yCJmstdMxEgMqHqvaJ8APP4vMCXF5SFMeS3U4jhGBQM4 HY1MPJR4l55MQEM1WTehd5s94R5SHxGMBSE/BFjRKhXuc2h4Zw==
X-Google-Smtp-Source: ABdhPJwBGGWnDg5rHabXvjGx1g/3+vBZY2MnIStBh9VKk9c7jJTx3uoo5yqPEG+kkWH9E5WVlvD7FO4YMOrhVKjtF6g=
X-Received: by 2002:aa7:8184:0:b029:1e5:1e7a:bcc0 with SMTP id g4-20020aa781840000b02901e51e7abcc0mr5199690pfi.73.1614288604702; Thu, 25 Feb 2021 13:30:04 -0800 (PST)
MIME-Version: 1.0
From: Daniel Franke <dfoxfranke@gmail.com>
Date: Thu, 25 Feb 2021 16:29:53 -0500
Message-ID: <CAJm83bC4UibDT3yivOYbR7hPkAYO1BMscmFCBUkQNpBNCrZNGg@mail.gmail.com>
To: NTP WG <ntp@ietf.org>
Content-Type: multipart/alternative; boundary="000000000000d9297305bc2fda1f"
Archived-At: <https://mailarchive.ietf.org/arch/msg/ntp/MNub8IngCTA9caSP5J5YNJT65tY>
Subject: [Ntp] Byztime
X-BeenThere: ntp@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: <ntp.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/ntp>, <mailto:ntp-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/ntp/>
List-Post: <mailto:ntp@ietf.org>
List-Help: <mailto:ntp-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/ntp>, <mailto:ntp-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 25 Feb 2021 21:30:08 -0000

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.