International Association
for Cryptologic Research

Several new services incentivize clients to compete in

solving large computation tasks in exchange for financial rewards.

This model of competitive distributed computation enables every

user connected to the Internet to participate in a game in which

he splits his computation power among a set of competing pools

-- the game is called a computation power splitting game. We

formally model this game and show its utility in analyzing the

security of pool protocols that dictate how financial rewards are

shared among the members of a pool.

As a case study, we analyze the Bitcoin cryptocurrency

which attracts computing power roughly equivalent to billions

of desktop machines, over 70% of which is organized into public

pools. We show that existing pool reward sharing protocols

are insecure in our game-theoretic analysis, when considering

a single attack strategy called the \"block withholding attack\".

This attack is a topic of debate, initially thought to be ill-

incentivized in today\'s pool protocols: i.e., causing a net loss

to the attacker, and later argued to be always profitable. Our

analysis shows that the attack is always well-incentivized in the

long-run, but may not be so for a short duration. This implies that

existing pool protocols are insecure, and if the attack is conducted

systematically, Bitcoin pools could lose millions of dollars worth

in months. The equilibrium state is a mixed strategy--that is--in

equilibrium all clients are incentivized to probabilistically attack

to maximize their payoffs rather than participate honestly. As

a result, the overall capacity of the Bitcoin network is under-

utilized.