Multivalued Consensus: General Adversaries Require More Communication
Mose Mizrahi, Roger Wattenhofer
cs.DC, cs.CR, cs.IT
2026-08-19
ETH 苏黎世用射影几何构造敌手结构，证明容一般敌手的拜占庭共识通信量下界从 Ω(Ln) 升到 Ω(Ln^{1+1/d})；节点输出后不停机即可用接近 Ln 的通信量逃过异步下界。
容错共识的标准设定是门槛敌手：最多 t 个节点出错，t < n/3 或 t < n/2 时任务可解。现实的信任假设未必这么整齐，于是有更一般的刻画：敌手结构 Z，一个集合族，敌手能腐化其中任意一个集合的全部节点。Z 满足 Q^d 条件（任意 d 个集合都盖不住全体节点）时任务仍可解。
可行性早有定论，效率没有。同步二值拜占庭共识在 t < n/3 下有 O(n²) 比特协议，换成 Q³ 敌手已知最好的是 O(n³)。更尖锐的问题在长输入：L 比特输入时，门槛敌手下 Ω(Ln) 这个「每个节点都得学到输出」的下界是紧的；一般敌手下纠删码那套摊薄带宽的技巧会失灵，因为保证正确的节点数可能掉到 O(1)，编码符号长度随之爆炸。这篇要回答：这种代价上涨是技巧不够，还是本质如此。
答案靠构造一个具体的最坏敌手。作者用 d 维有限射影几何 PG(d,q)（q = Θ(n^{1/d})）构造敌手结构族 Zproj：每个节点是射影空间里的一个点，每个超平面对应一支法定人数，敌手可腐化任一超平面之外的节点。妙处在于每个点落在 Θ(n^{-1/d}·|S|) 个超平面上，大量法定人数高度重叠，每支又都很小。
下界证明是熵论证加双计数。以可靠广播为例：发送者的 L 比特输入均匀随机，敌手把法定人数 U 之外的消息全部延迟，U 里的节点只能在不听到外界的情况下输出并终止。此后对每支法定人数 S 和每个外部节点 i，S 的节点在终止前必须给 i 发 Ω(L) 比特：从 S 的视角看，除 S∪{i} 外可能全是坏节点，i 只能靠 S 的消息学到一个均匀随机值，信息论上少于 Ω(L) 比特学不会。全部 (S, i) 对的通信合计 Ω(|S|·Ln)，而每个节点只属于 Θ(n^{-1/d}·|S|) 支 S，一笔通信最多被数这么多次，除一下就是 Ω(Ln^{1+1/d})。
五个任务五个下界，异步侧只需要 send-omission 故障（比拜占庭弱），即使协议用密码学也绕不开。
最反直觉的发现在终止性上。作者设计了一个非终止的可靠广播协议 PullCast：节点输出后不停机，继续按需响应别的节点对纠删码符号的拉取请求，请求动态指向响应快的节点，类似 BitTorrent 的下载逻辑。它对任意 general-omission 敌手完美安全，通信量 (1 + 1/(δ-1))Ln + O(δn² log(δn)) 比特，δ 取大就任意接近 Ln。这直接击穿了 Ω(Ln^{1+1/d}) 下界，说明下界的命门在「终止」：终止协议里法定人数 U 必须向看不到的节点盲发冗余，非终止协议可以等人来拉。配套还有一个终止化协议 Term：在 Q^d 条件下，任何一致输出之后加 O(Ln^{1+1/d} + n² log n) 比特就能让所有人终止。这和异步下界正好对上，证明异步侧的界是紧的。
| 任务 | 设定 | 下界 | 门槛敌手对照 |
| 交互一致性 | 同步、无错、d≥3 | Ω(Ln^{2+1/d}) | Ω(Ln²)，输出长度决定 |
| 拜占庭共识/广播 | 同步、无错、d≥3 | Ω(Ln^{1+1/d}) | Ω(Ln)，紧 |
| 可靠广播 | 异步、send-omission、d≥1 | Ω(Ln^{1+1/d}) | Ω(Ln)，紧 |
| 异步拜占庭共识 | send-omission、d≥2 | Ω(Ln^{1+1/d}) | Ω(Ln) |
| 核心集共识 | 异步、send-omission、d≥2 | Ω(Ln^{2+1/d}) | Ω(Ln²) |
正面结果两笔：PullCast 通信量 (1 + 1/(δ-1))Ln + O(δn²log(δn))，延迟 2(δ-1)n-1；Term 终止化附加 O(Ln^{1+1/d} + n²log n)，两者相加把异步下界顶满。顺带推翻了 Locher 的 (1.5-o(1))Ln 下界对非终止协议的适用性，PullCast 在更强的故障模型下做到了低于 1.5Ln。
联盟链、跨机构协作这类场景的信任假设往往是「这几家不会一起坏」而非「最多坏三分之一」，正是一般敌手结构。这篇给出第一个系统的量化答案：细粒度信任假设下，长值共识的通信成本要乘一个 n^{1/d} 因子，d 是信任假设的阶数。纠删码带宽优化不能照搬门槛模型的做法。
「不终止就能便宜」对实践有直接启发：长驻服务（状态机副本、流式广播）本来就不停机，PullCast 式拉取协议正好落在豁免区，能拿到接近 Ln 的最优通信量。
同步下界只对无错（error-free）协议成立。允许以可忽略概率失败时，已有 O(Ln + κ·poly(n)) 的协议对所有敌手结构成立，输入哈希把「比对输入是否一致」变得很便宜，下界直接失效。这个要求在实践里偏严格，同步结果的理论意义大于工程意义。
下界对输入长度 L 有下限要求（如 L = Ω(Rn^{1-1/d})），原因是节点可以拿「沉默」编码元数据；作者也承认，消息强制带发送方/轮次标签或改用熵度量即可去掉这个限制，说明界有一部分是建模选择撑起来的。同步侧紧性只是猜想。敌手结构只对素数幂相关的特定 n 值存在，不过这些 n 值的间隔随 n 增大趋于 1。PullCast 延迟 2(δ-1)n-1，要拿到接近 Ln 的通信量得取 δ 接近 1，延迟随之变成 Θ(n) 跳，未必能接受。