On Bitcoin and Red Balloons

In this letter we present a brief report of our recent research on information distribution mechanisms in networks [Babaioff et al. 2011]. We study scenarios in which all nodes that become aware of the information compete for the same prize, and thus have an incentive not to propagate information. Examples of such scenarios include the 2009 DARPA Network Challenge (finding red balloons), and raffles. We give special attention to one application domain, namely Bitcoin, a decentralized electronic currency system. We propose reward schemes that will remedy an incentives problem in Bitcoin in a Sybil-proof manner, with little payment overhead.