用博弈论设计抗伪造的去中心化机器学习系统,无需高度信任
Game of Coding: Sybil Resistant Decentralized Machine Learning with Minimal Trust Assumption
- 基于博弈论构建去中心化数据恢复机制,激励节点诚实参与
- 证明攻击者越多收益不增,系统具备抗伪造能力(Sybil Resistance)
- 揭示诚实节点过多反降低效率的反直觉现象,提供优化策略
编码理论在通信、计算和存储系统中对保障数据完整性和可靠性至关重要。然而,其传统方法依赖于对诚实节点数量需超过攻击节点的可信假设,在新兴去中心化系统中面临信任稀缺的挑战。为此,本文提出“博弈编码”框架,将数据恢复过程建模为激励导向的博弈:只要系统保持运行(live),参与节点即可获得奖励。这促使攻击者通过确保解码器成功恢复数据(即使带误差)来最大化自身收益。本文将该框架推广至任意 N ≥ 2 个节点场景,发现:(i) 攻击者在均衡状态下的收益随攻击节点增加而递减,实现抗伪造能力;(ii) 增加诚实节点并不总提升解码器收益,存在反直觉效应,并提出算法识别与缓解;(iii) 明确了解码器与攻击者的最优策略,系统在均衡下实现更强的持续运行性。
原文摘要 · Abstract (English)
Coding theory plays a crucial role in ensuring data integrity and reliability across various domains, from communication to computation and storage systems. However, its reliance on trust assumptions for data recovery, which requires the number of honest nodes to exceed adversarial nodes by a certain margin, poses significant challenges, particularly in emerging decentralized systems where trust is a scarce resource. To address this, the game of coding framework was introduced, offering insights into strategies for data recovery within incentive-oriented environments. In such environments, participant nodes are rewarded as long as the system remains functional (live). This incentivizes adversaries to maximize their rewards (utility) by ensuring that the decoder, as the data collector (DC), successfully recovers the data, preferably with a high estimation error. This rational behavior is leveraged in a game-theoretic framework, where the equilibrium leads to a robust and resilient system, referred to as the game of coding. The focus of the earliest version of the game of coding was limited to scenarios involving only two nodes. In this paper, we generalize the game of coding framework to scenarios with $N \ge 2$ nodes, exploring critical aspects of system behavior. Specifically, we (i) demonstrate that the adversary's utility at equilibrium is non-increasing with additional adversarial nodes, ensuring no gain for the adversary and no pain for the DC, thus establishing the game of coding framework's Sybil resistance; (ii) show that increasing the number of honest nodes does not always enhance the DC's utility, providing examples and proposing an algorithm to identify and mitigate this counterintuitive effect; and (iii) outline the optimal strategies for both the DC and the adversary, demonstrating that the system achieves enhanced liveness at equilibrium.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。