  Many large decentralized systems rely on information propagation to ensure
their proper function. We examine a common scenario in which only participants
that are aware of the information can compete for some reward, and thus
informed participants have an incentive not to propagate information to others.
One recent example in which such tension arises is the 2009 DARPA Network
Challenge (finding red balloons). We focus on another prominent example:
Bitcoin, a decentralized electronic currency system.
  Bitcoin represents a radical new approach to monetary systems. It has been
getting a large amount of public attention over the last year, both in policy
discussions and in the popular press. Its cryptographic fundamentals have
largely held up even as its usage has become increasingly widespread. We find,
however, that it exhibits a fundamental problem of a different nature, based on
how its incentives are structured. We propose a modification to the protocol
that can eliminate this problem.
  Bitcoin relies on a peer-to-peer network to track transactions that are
performed with the currency. For this purpose, every transaction a node learns
about should be transmitted to its neighbors in the network. The current
implemented protocol provides an incentive to nodes to not broadcast
transactions they are aware of. Our solution is to augment the protocol with a
scheme that rewards information propagation. Since clones are easy to create in
the Bitcoin system, an important feature of our scheme is Sybil-proofness.
  We show that our proposed scheme succeeds in setting the correct incentives,
that it is Sybil-proof, and that it requires only a small payment overhead, all
this is achieved with iterated elimination of dominated strategies. We
complement this result by showing that there are no reward schemes in which
information propagation and no self-cloning is a dominant strategy.
