Game of Coding: Enabling Sybil Resistant Decentralized Machine Learning

Decentralized machine learning (DeML) has emerged as a promising paradigm that democratizes access to AI, and motivates a wide range of users to participate and benefit from its applications. However, DeML faces fundamental challenges, particularly the computational limitations of underlying blockchain-based decentralized computing platforms. Verifiable computing solutions have been proposed to address this issue, but their applicability is limited due to the resource-intensive proof generation process and their reliance on exact computations within finite fields. Similarly, leveraging redundancy through error-correcting codes is constrained by significant trust assumption in coding theory, which requires the number of honest nodes to exceed adversarial nodes by a certain margin - a condition that is difficult to achieve and guarantee in decentralized systems. To address these challenges, the game of coding framework has been introduced, providing valuable insights for decentralized applications like DeML within trust-minimized, incentive-driven 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. In this paper, we generalize the game of coding framework to scenarios with N≥ 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, in contrast to conventional coding theory, which results in zero liveness in trust-minimized settings.