Tight Bound on Incnetive Ratio for Sybil Attack in Resource Sharing System

In this article, we discuss the Sybil attack on a sharing-based economic system where each participant contributes its own resource for all to share. Such an attack is possible especially in the cloud computing model where agents can exchange information with the cloud and obtain aggregated information from it. We are interested in the robustness of the market equilibrium mechanism against such an attack. We adopt the incentive ratio to measure the gain that a participant can make by splitting its identity and reconstructing communication connections with others. On one hand, we show that no player can increase more than root 2 times its original share in the market equilibrium solution by characterizing the worst case, in which a strategic agent can obtain the maximal gain in utility by playing the Sybil attack. On the other hand, the bound of root 2 is proved to be tight by constructing a proper instance. We also simulate on a series of random graphs and observe that the incentive ratio was no more than two in the general setting.

Automated summary

This article discusses the Sybil attack in a sharing-based economic system and examines the robustness of the market equilibrium mechanism against such an attack. By measuring the incentive ratio, it is found that no participant can increase their share by more than root 2 times in the market equilibrium solution.