Computer Science Colloquium

On Bitcoin and Red Balloons

Moshe Babaioff, Microsoft Research Silicon Valley

January 27, 2014 11:30AM
Warren Weaver hall, 1302
251 Mercer Street
New York, NY 10012

Spring 2014 Colloquia Calendar

Host

Richard Cole

Synopsis

Joint work with Shahar Dobzinski, Sigal Oren, and Aviv Zohar

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 {\em
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. As the protocol is currently defined
and implemented, it does not provide an incentive for nodes to
broadcast transactions they are aware of. In fact, it provides an
incentive not to do so. 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.

You can find the paper at: http://arxiv.org/abs/1111.2626
http://research.microsoft.com/apps/pubs/?id=156072
A short description appeared in ACM SIGecom Exchanges:
http://www.sigecom.org/exchanges/volume_10/3/BABAIOFF.pdf


top | contact webmaster