Source-linked AI summary
On Bitcoin and Red Balloons
Moshe Babaioff, Shahar Dobzinski, Sigal Oren, Aviv Zohar
TL;DR
The paper studies how reward competition can discourage information propagation in decentralized systems, focusing on Bitcoin’s transaction network and its vulnerability to Sybil identities. It models propagation and authorization, proposes reward schemes analyzed through iterated elimination of dominated strategies, and shows both a successful low-overhead scheme and an impossibility result for dominant-strategy mechanisms.
Problem
Bitcoin’s fee incentive can cause informed nodes to withhold transactions to avoid competition, while any corrective reward scheme must also resist Sybil attacks.
Method
The paper models transaction distribution and authorization in a tree-based network and analyzes reward schemes using iterated elimination of dominated strategies.
Results
The hybrid scheme induces propagation and no duplication when t ≥14, with expected total payments at most 3; no Sybil-proof dominant-strategy scheme achieves these behaviors at depth 3 or less.
Takeaways & Limitations
Rewarding propagation can address Bitcoin’s withholding incentive with Sybil-proofness and small payment overhead, although dominant-strategy implementation is impossible in the stated setting.
Takeaways & Limitations
The protocol must account for Sybil attacks because false identities are easy to spoof, so identity-majority reward schemes are unsuitable.
Abstract
from arXiv · showhide
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.
1. INTRODUCTION
The paper identifies a general conflict between propagating information and preserving reward opportunities, then applies it to Bitcoin’s transaction network and Sybil-sensitive incentives.
- Information-propagation incentives: $2,000 per balloon and descending recruiter rewards motivated participants to find balloons and spread information about the DARPA challenge.The MIT team paid $1,000 to the direct recruiter, $500 to that recruiter’s recruiter, and so on.
- Information-propagation incentives: Raffles create the same tension: organizers want broad awareness, while ticket holders want fewer competitors and higher winning chances.The paper cites Expedia’s FriendTrips as an implemented raffle that increases winning probability with successful recruitment.
- Bitcoin’s transaction network: Bitcoin uses a peer-to-peer network in which nodes propagate, verify, and computationally authorize signed transactions before the network agrees on them.Successful authorization requires solving a computationally hard problem and broadcasting the resulting proof.
- Bitcoin’s incentive problem: Any propagation reward must discourage Sybil attacks because declared identities are easy to spoof, whereas Bitcoin relies on majority processing power.The paper therefore treats Sybil-proofness as a required protocol property.
- Model setup: The model separates transaction distribution from computation, with nodes first receiving the transaction and then attempting authorization.Only one transaction is assumed to be awaiting authorization in the simplified model.
A Simplified Model.
The simplified model represents propagation through directed trees and authorization by informed nodes, then specifies the incentive properties a successful reward scheme should achieve.
- Distribution network: The distribution network is modeled as a forest of d-ary directed trees of height H, with t transaction-receiving roots and n = t · d^(H−1) total nodes.Information flows from each seed toward the leaves, and node depth counts positions from the tree root.
- Distribution network: Nodes may relay the transaction to children after adding arbitrary fake identities, but clones do not change their available neighbors.A node’s behavior can depend on the chain length above it, including false identities created by ancestors.
- Authorization phase: In the computation phase, every informed real node attempts authorization, and each of k informed nodes has probability 1/k of authorizing first.Fake identities do not increase the probability of winning; rewards follow the declared authorizing chain.
- Authorization phase: The model assumes expectation-maximizing players whose utilities are determined by expected rewards under the random authorizer.Expectation is taken over the random selection of the authorizing node.
- Design requirements: A successful scheme should induce propagation without duplication, inform most nodes, use small rewards, and minimize the number of seeds.These requirements combine behavioral incentives, network coverage, and payment overhead.
Our Results.
The paper develops reward schemes that make information propagation and non-duplication survive iterated elimination of dominated strategies while addressing Sybil attacks and payment overhead. Its hybrid scheme achieves these properties with a constant number of seeds and expected total payments at most 3, whereas no Sybil-proof scheme can make them dominant strategies for all nodes at depth 3 or less when H ≥3.
- Almost uniform schemes: Almost uniform schemes reward nodes along an authorizing chain and, with Ω(β^-1) seeds, retain only propagation and non-duplication strategies under every elimination order.A separate elimination order removes all other strategy profiles.
- Solution concept: Iterated removal of dominated strategies repeatedly eliminates strategies dominated relative to the other players’ surviving strategies, although surviving sets can depend on elimination order.The paper proves that propagation and non-duplication profiles survive regardless of order in its setting.
- Economic intuition: The analysis uses relay rewards to make reducing descendant competition potentially unprofitable when a descendant might authorize the transaction.With sufficient external competition, nodes prefer distributing to children and increasing potential distribution rewards; this process leads to full distribution without duplication.
- Parameter choices: For β = 1, the almost-uniform scheme uses a constant number of seeds with total payment O(H), while the second highlighted scheme requires Ω(H) seeds and has total payment 2.These are the two parameter choices identified as particularly interesting.
- Hybrid scheme: The hybrid scheme combines constant-seed initial distribution with a later tree-distribution scheme, yielding constant overhead and rewards of 1/H to most aware nodes in the successful chain.The construction first uses a (1, 1 + log_d H)-almost-uniform scheme, then a (1/H, H)-almost-uniform scheme.
- Main theorem: With t ≥14 seeds, only strategies exhibiting information propagation and no duplication survive an appropriate elimination order, and expected total payments are at most 3.The resulting scheme is described as having low overhead, Sybil-proofness, and incentives to propagate information in equilibrium.
- Impossibility result: The paper shows that, for H ≥3, no Sybil-proof reward scheme makes propagation and non-duplication dominant strategies for every node at depth 3 or less.Thus the stronger dominant-strategy equilibrium target is unattainable under the stated condition.
Related Work.
The paper situates its incentive-based information-propagation model among work on search, recruitment, advertising, and propagation detection. It distinguishes its game-theoretic, Sybil-proof setting and proposes a low-cost reward scheme for forest-structured networks.
- Related Work: Kleinberg and Raghavan reward nodes for relaying information and nodes along the path, whereas this paper studies a different model.Their model assumes nodes either possess the sought-after information or do not.
- Related Work: Douceur and Moscibroda study recruitment mechanisms and impossibility results, but do not analyze participants’ strategies using a game-theoretic solution concept.
- Related Work: Emek et al. reward forwarding in social advertising, whereas this paper awards only nodes on the chain leading to a successful authorizer.
- Related Work: Other work detects propagation events without incentives, including analysis of propagation in cellular call data.
- Related Work: This paper proposes a low-cost, Sybil-proof reward scheme that incentivizes information propagation in a forest of complete d-ary trees.
Future Research.
The paper leaves broader network models, heterogeneous processing power, implementation, and empirical experimentation for future research.
- Future Research: Future analysis should consider random d-regular graphs, which may better capture peer-to-peer networks.
- Future Research: Future models should allow nodes to have different processing power and authorization probabilities.The passage specifies node-specific CPU values as the basis for authorization probability.
- Future Research: Implementation and empirical experimentation are left to future research.
2. NEW REWARD SCHEMES
The paper develops reward schemes that make information propagation and non-duplication survive iterated elimination of dominated strategies. The Hybrid scheme combines almost-uniform schemes to achieve these incentives with constant seeds and low payment overhead.
- The Hybrid Scheme: The Hybrid scheme requires only a constant number of seeds and constant payment overhead while selecting propagation without duplication.These are the paper’s stated main properties of the construction.
- Almost-Uniform Schemes: Almost-uniform schemes pay the authorizer 1 + β · (H −h + 1), pay other chain nodes β, and pay nothing when the chain exceeds H.The authorizer’s reward mimics the reward from duplicating to reach the target chain length.
- Proof Framework: With at least 7 seeds and 2β−1 + 6 additional aware nodes, only profiles with propagation and no duplication survive every iterated removal of weakly dominated strategies.There is also an elimination order in which only those profiles survive.
- The Hybrid Scheme: The Hybrid scheme combines a (1/H, H)-almost-uniform scheme on A seeds with a (1, 1 + log H)-almost-uniform scheme on B seeds.The construction sets |A| = t − 7 and |B| = 7.
- Proof Framework: A node’s strategy of using l(v)−ϕ−1 identities for a child is dominated by reducing that identity count under the stated number of outside aware nodes.The dominance argument supports eliminating duplication strategies through successive subgames.
3. IMPOSSIBILITY RESULT FOR DOMINANT STRATEGY MECHANISMS
The paper shows that no Sybil-proof reward scheme can make information propagation and no duplication dominant strategies for nodes at depth 3 or less. This impossibility follows from a contradiction involving rewards at different chain levels.
- No Sybil-proof reward scheme makes information propagation and no duplication dominant strategies for all nodes at depth 3 or less.
- The proof assumes a scenario where only the seed propagates information and direct children follow conditional duplication strategies.
- When the seed propagates information to its children, its utility is r1,1 + d · r3,3 under the specified response strategies.
- Dominant-strategy requirements impose an inequality comparing propagation without duplication against duplication by the seed.
- The contradiction relies on Lemma 3.2, which requires r2,3 > 0 under Sybil-proofness and dominant propagation without duplication.
A. A BRIEF OVERVIEW OF BITCOIN
This section gives a deliberately brief overview of Bitcoin’s protocol. Its purpose is to motivate the paper’s modeling choices rather than provide a complete description.
- The Bitcoin overview is explicitly incomplete and is intended to support understanding of the paper’s modeling choices.
- The section refers readers to Nakamoto 2008 and the Bitcoin wiki for a complete protocol description.
- The overview explains why the proposed reward schemes can be implemented within the existing Bitcoin protocol.
A.1. Signing Transactions and Public Key Cryptography
Bitcoin uses public-key cryptography to authenticate transfers and relies on a transaction history that prevents double spending. Banks traditionally maintained this ownership record, while Bitcoin uses a peer-to-peer network.
- Alice signs a transaction with her private key, allowing everyone to verify that she initiated it.
- Bob is identified as the transfer target through his public key.
- A record of coin ownership is required to transfer ownership and prevent Alice from spending the same money twice.
- Banks traditionally maintained ownership records and often charged high fees, including for international transfers.
A.2. Agreeing on the History by Majority of Processing Power
Bitcoin validates transactions through a peer-to-peer network whose nodes build and authorize linked blocks. The accepted history is determined by processing power, with nodes adopting the longer authorized chain.
- Bitcoin uses a peer-to-peer network and processing-power majority rather than numerical node majority to establish transaction history.
- Nodes forward signed transactions, verify their validity, and add valid transactions to blocks they attempt to authorize.
- Authorized blocks form a chain because each block includes the hash of the previously authorized block.
- When a node authorizes a block, it broadcasts the block and proof of work to the network.
- If nodes receive two authorized blocks, they adopt the block belonging to the longer chain.
- The probability that malicious nodes change the accepted history decreases as their fraction of processing power decreases.
A.3. Transaction Fees
Bitcoin allocates rewards to encourage network participation and transaction authorization. As block rewards decline, transaction fees become increasingly important, with the protocol supporting fee specification and structured fee schemes.
- Rewards incentivize nodes to participate in Bitcoin’s peer-to-peer network and invest effort in authorizing transactions.
- Block authorizers initially receive a fixed bitcoin reward, but protocol-specified reductions in money creation require alternative rewards over time.
- Transaction initiators specify an authorization fee in the transaction record, alongside the transfer details, before cryptographically signing it.
- Any (β, H)-almost uniform scheme can be implemented by creating seed-specific transaction records that specify β, H, and a coin amount f.When a node in the seed-rooted tree authorizes the transaction, the total fee is (1 + β · H) · f.