#adversary-structures

共收录 1 条相关安全情报。

← 返回所有主题
👥 作者: Mose Mizrahi, Roger Wattenhofer

本文研究多参与方容错共识问题,特别关注一般性(非阈值)对手模型下的通信复杂度下界。作者基于有限射影几何构造了一个无限族 Z_proj^{n,d} 的对手结构,该结构满足 Q^d 条件(即任意 d 个对手集合的并集不覆盖全部参与者)。对于这类对手结构,作者证明:在无错误、R 轮协议中,实现 L 比特输入的交互一致性(interactive consistency)需要 Ω(L·n^{2+1/d}) 比特的期望通信量;而拜占庭同意(byzantine agreement)和广播(broadcast)则需要 Ω(L·n^{1+1/d}) 比特。在异步网络中,可靠广播和拜占庭同意也需要 Ω(L·n^{1+1/d}) 比特的期望通信量。此外,相关构造 Z_2-proj^{n,d} 使核心集合同意(core set agreement)需要 Ω(L·n^{2+1/d}) 比特。这些异步下界对发送遗漏(send-omission)对手成立,且即使协议使用密码学也无法避免。其核心论据是:如果某个法定人数(quorum)的非故障方达成一致输出并终止,那么他们在终止前发送的消息必须足以让法定人数之外的方也能以相同输出终止。令人惊讶的是,如果不需要参与者在输出后停止发送消息,则这些下界不再成立。作者设计了一个非终止的容忍遗漏的可靠广播协议,可针对任意参数 δ>1 调整,通信成本为 (1 + 1/(δ-1))·L·n + O(δ·n^2·log(δ·n)) 比特,这一结果本身具有独立意义。最后,作者展示了如何在满足 Q^d 条件下以 O(L·n^{1+1/d} + n^2·log n) 比特实现终止,从而证明异步下界是紧的。本文为一般对手结构下的共识协议通信复杂度提供了重要的理论界限,对分布式系统安全性设计具有指导意义。

💡 推荐理由: 该研究揭示了非阈值对手模型下共识协议通信复杂度的本质下界,为设计更安全的分布式系统提供了理论依据,有助于安全工程师理解攻击者能力对协议效率的深远影响。

🎯 建议动作: 研究跟进

排序因子: 来自 arXiv 其他板块 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.5)