Partial synchrony for free? New bounds for Byzantine agreement via a generic transformation across network models

拜占庭共识允许n个进程决定一个共同的价值，尽管可能出现任意故障。经典的Dolev-Reischuk界定指出，任何确定性的拜占庭共识解决方案都需要交换Ω(n^2)比特。近年来，在部分同步网络中，确定性的拜占庭协议取得了巨大进展，最先进的加密解决方案实现了O(n^2κ)比特（其中κ是安全参数），并且几乎达到了下限。相比之下，对于同步网络，最优解法已经在三十多年前就已知，具有O(n^2)比特，没有加密，但具有相同的容错能力。这个网络模型中的差距能否被消除呢？ 本文介绍了Repeater，这是第一个将拜占庭协议从同步转换为部分同步的通用转换方法。Repeater是模块化的，依赖于现有的和新的算法子模块。通过正确选择模块，Repeater不需要额外的加密，具有最优的弹性（n=3t+1，其中t是最大故障数量），对于固定大小的输入，保留了转换同步算法的最坏情况下每个进程的比特复杂度。借助Repeater，我们提出了第一个部分同步算法，它实现了最优的比特复杂度（O(n^2)比特），抵抗计算上无限制的对手（没有加密），并且具有最优的弹性（n=3t+1），从而表明在部分同步中Dolev-Reischuk界限是紧的。此外，我们还为长输入调整了Repeater，引入了几个新算法，改进了复杂度，并减弱了（或完全消除了）加密假设。

本文试图解决在同步和部分同步网络中拜占庭一致性算法的比特复杂度差异问题。

本文提出了Repeater，这是一种从同步到部分同步的通用转换方法，可以将已有的同步算法转换为部分同步算法。Repeater是模块化的，可以利用现有和新的算法作为子模块。通过正确选择模块，Repeater不需要额外的加密，具有最优的鲁棒性（n = 3t + 1，其中t是最大故障数），并且对于恒定大小的输入，保持了转换后的同步算法的最坏情况下每个进程的比特复杂度。利用Repeater，本文提出了第一个部分同步算法，它实现了最优比特复杂度（O（n ^ 2）比特），抵抗计算上无限制的对手（无需加密），并且具有最优的鲁棒性（n = 3t + 1），从而表明在部分同步中Dolev-Reischuk界限是紧的。此外，本文还针对长输入调整了Repeater，引入了几个新算法，这些算法具有改进的复杂度和较弱的（或完全不存在的）加密假设。

本文提出了Repeater，这是第一个从同步到部分同步的通用转换方法；提出的部分同步算法实现了最优比特复杂度，抵抗计算上无限制的对手，具有最优的鲁棒性；引入了几个新算法，这些算法具有改进的复杂度和较弱的加密假设。

最近的相关研究包括：1. Partial synchronous Byzantine agreement revisited; 2. Byzantine agreement in partial synchrony without authentication; 3. Byzantine agreement with a rational adversary.