论文标题
最佳时钟与签名同步
Optimal Clock Synchronization with Signatures
论文作者
论文摘要
通过增加可以容忍的故障当事方的数量，可以使用加密签名来增加针对对抗攻击的分布式系统的弹性。尽管这是对共识进行了充分研究的良好研究，但即使在完全连接的系统中，它在容忍故障时钟同步的背景下也没有得到充实的态度。在这里，尽管本地时钟率在$ 1 $ 1 $和$ \ vartheta> 1 $之间变化，但需要$ n $ node系统的诚实派对来计算小偏偏的输出时钟（即最大相位偏移），而端到端通信延迟在$ d-u $ $ d $之间以及来自恶意派别的干扰。到目前为止，只有知道偏斜$ d $的时钟脉冲才能使用$ \ lceil n/2 \ rceil-1 $（podc`1 19）产生（琐碎的最佳）弹性，在$ \ lceil n/3 \ rceil-1 $中的紧密界限改进，而无需签名而没有签名。 `85）。由于通常$ d \ gg u $和$ \ vartheta-1 \ ll 1 $，因此即使在无故障情况下也适用于$ u+（\ vartheta-1）d $的下限（ipl`01）。 我们证明了$θ（u+（\ vartheta-1）d）$的上限和下限的偏差范围从$ \ lceil n/3 \ rceil $到$ \ lceil n/2 \ rceil-1 $。在对手不能伪造标志的假设下，显示上限的算法是确定性的。即使时钟最初是完美同步的，下边界也存在，诚实节点之间的消息延迟，$ \ vartheta $任意接近一个，并且同步算法是随机的。这对试图利用签名提供更健壮时间的网络设计师具有至关重要的影响。与没有签名的设置相反，他们必须确保攻击者无法轻松绕过具有故障端点的链接延迟上的下限。
Cryptographic signatures can be used to increase the resilience of distributed systems against adversarial attacks, by increasing the number of faulty parties that can be tolerated. While this is well-studied for consensus, it has been underexplored in the context of fault-tolerant clock synchronization, even in fully connected systems. Here, the honest parties of an $n$-node system are required to compute output clocks of small skew (i.e., maximum phase offset) despite local clock rates varying between $1$ and $\vartheta>1$, end-to-end communication delays varying between $d-u$ and $d$, and the interference from malicious parties. So far, it is only known that clock pulses of skew $d$ can be generated with (trivially optimal) resilience of $\lceil n/2\rceil-1$ (PODC `19), improving over the tight bound of $\lceil n/3\rceil-1$ holding without signatures for \emph{any} skew bound (STOC `84, PODC `85). Since typically $d\gg u$ and $\vartheta-1\ll 1$, this is far from the lower bound of $u+(\vartheta-1)d$ that applies even in the fault-free case (IPL `01). We prove matching upper and lower bounds of $Θ(u+(\vartheta-1)d)$ on the skew for the resilience range from $\lceil n/3\rceil$ to $\lceil n/2\rceil-1$. The algorithm showing the upper bound is, under the assumption that the adversary cannot forge signatures, deterministic. The lower bound holds even if clocks are initially perfectly synchronized, message delays between honest nodes are known, $\vartheta$ is arbitrarily close to one, and the synchronization algorithm is randomized. This has crucial implications for network designers that seek to leverage signatures for providing more robust time. In contrast to the setting without signatures, they must ensure that an attacker cannot easily bypass the lower bound on the delay on links with a faulty endpoint.
