Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Notes about “On Bitcoin and Red Balloons”

 By Moshe Babaioff, Shahar Dobzinski, Sigal Oren, and Aviv Zohar

Our paper “On Bitcoin and Red Balloons” has attracted some attention recently after being noticed by members of the Bitcoin community. Since the paper itself was written for theoretical computer scientists and is mathematical in nature, we give here a more simplified summary aimed at those that are more familiar with Bitcoin.

A small disclaimer that we wish to make clear: Two of the co-authors are affiliated with Microsoft Research and the other two are affiliated with Cornell. Both Microsoft and Cornell allow researchers a great deal of freedom in choosing their research topics. We have decided to research Bitcoin as part of our personal research agenda. Our opinions are just that – our own.

· What is the paper about?

· Is there a major flaw in Bitcoin? How severe is the problem?

· Should we care? Why worry about a problem that hasn’t come up yet?

· How costly is it to relay transactions? Won’t altruistic members of the Bitcoin network relay transactions as they do now?

· What exactly is the proposed solution?

· Is the solution optimal? What are the costs?

What is the paper about?

The paper deals with incentives to propagate information in networks. It suggests a way of structuring payments to nodes that will add incentives to relay information. One of the application domains is within the Bitcoin protocol. While Bitcoin is the prominent example discussed in the paper, it is only one application domain, and we believe the issue is of general interest in other settings as well.

Our work suggests that the Bitcoin protocol currently lacks strong incentives for transaction propagation, and in some cases there is even a strong incentive not to propagate transactions in the network. According to the protocol, Mining nodes that authorize transactions in the Bitcoin system will eventually be paid solely with transaction fees that are associated with each transaction they confirm. They learn about transactions from each other. If nodes that initiate transactions manage to reach all miners directly, then there is no problem. However, Bitcoin works better when there is a large distributed network of miners and it may be difficult to reach all of them. We point out that miners will be enticed to keep the knowledge of transactions to themselves in order to give themselves a higher chance of getting the fees associated with those specific transactions (they cannot help it if others spread the transaction around, but if they can slow things down by delaying propagation and may benefit, then they may be tempted to do so). If many miners start to act along these lines Bitcoin transactions will take a long time to get accepted by the network.

back to top

Is there a major flaw in Bitcoin? How severe is the problem?

Bitcoin is a new system that faces many challenges, and the project’s developers are working hard to constantly improve it. Obviously, Bitcoin is currently functioning. Transactions get relayed in the network both by miners and by non-mining nodes. So we suspect the problem is not currently occurring or is not severe at the moment. We are more interested in how Bitcoin will have to be structured if it succeeds and needs to be scaled up. The incentive problem that we point to becomes more pronounced under these circumstances, and will appear as the costs of relaying transactions and authenticating them increase, and as money creation inside the protocol decreases. We think that if Bitcoin really succeeds the costs of relaying transactions will be very high and that this may cause “regular” non-mining nodes not to relay information (except for sending out transactions that they themselves initiated). Miners or other entities that profit from Bitcoin directly can afford the higher costs and can handle the load provided that they have incentives to propagate information. We therefore propose to add these incentives before they become an issue.

back to top

Should we care? Why worry about a problem that hasn’t come up yet?

We think that it is best to take care of potential problems before they occur. Even if we over-estimate the severity of the problem, it is still worthwhile to have solutions ready in advance.

Since Bitcoin is a form of currency, and the value of a currency today is greatly impacted by people’s beliefs about its future, we think Bitcoin will benefit from early discovery of potential flaws and from suggested solutions that will add to the confidence in the currency.

back to top

How costly is it to relay transactions? Won’t altruistic members of the Bitcoin network relay transactions as they do now?

Bitcoin is supported by many dedicated and enthusiastic individuals that are interested in its success. They are investing a great deal of time and effort and even contribute some of their personal computational resources to the network. While altruistic behavior may alleviate the problem, we think it’s preferable to base Bitcoin on stronger foundations. We worry that as costs increase there will be fewer people that will be willing to contribute.

Supose that Bitcoin becomes really successful, and that many people use it daily. Both the number of transactions and its value increase. For example, consider the scenario outlined in Bitcoin’s wiki page on scalability in which it grows to have the same number of transactions per second as Visa (in some scenarios this is even a low estimate). With the current protocol, each transaction in the network gets sent to the entire network. For this scenario, the estimated size of a block of approved transactions is around 1 GB, which means that each node that stores the block-history will need to store many gigabytes of data and handle traffic on the order of 1 GB every 10 minutes (the bandwidth requirement is not too bad really). In addition, nodes will have to verify transactions that they relay, which means that the cryptographic signatures associated with each transaction will need to be checked. This is computationally expensive.

If relaying nodes do not store the block-history and do not check the signatures, they will be forced to relay unverified transactions. This means that they can be used to amplify denial of service attacks on the network (attackers will just generate many fake transactions that relay nodes will then flood to the entire network).

These costs are rather high and lead to a sort of a “tragedy of the commons” scenario. The entire network is better off if everyone relays information, but each node alone bears a relatively high cost when doing so. On the other hand, if a node stops relaying transactions, it does not cause a great deal of damage on its own (perhaps it expects other nodes around it to relay transactions in its stead), so individual users may decide to avoid the costs.

Mining nodes, on the other hand, can afford to set aside dedicated machines that will handle the load associated with transaction propagation, and with the other requirements from nodes. For them, this is just part of the cost of mining, but as we stressed above, they potentially gain from keeping transactions to themselves.

back to top

What exactly is the proposed solution?

We propose a fairly simple approach: to pay nodes for relaying transactions. A similar method was used in DARPA’s network challenge by the winning team from MIT. We propose that nodes on the path to the final authenticating node be compensated for their efforts. This incentivizes nodes to relay transactions to as many neighbors as they can, hoping to collect the payoff in case that neighbor (or someone it relayed the message to) ends up authorizing the transaction.

Keeping with the spirit of Bitcoin, most of the effort in the paper is devoted to making the payment scheme robust to ‘Sybil attacks’: If we’re not careful, it may be possible to relay transactions back and forth between nodes that are owned by the same miner, and thus rob everyone else of most of the distribution payments.

Payments are handled very much like transaction fees are handled today – they are embedded in the block-chain, and cryptographic signatures ensure that everyone gets their due rewards.

We offer several variants of the payment scheme. Here is one such variant:

The initiating node offers a fee of x Bitcoins (x can be less than 1 Bitcoin). Half of the fee will be used to pay the miner that eventually manages to authorize the block. The rest will be divided by nodes on the path to that miner. The initiating node additionally picks the number of hops the transaction will be allowed to propagate (let’s call this H). Nodes that are more than H hops away will not be paid at all (and will probably not distribute further). This limitation on propagation seems strange but is really at the heart of the incentive scheme (Usually a small number of hops is sufficient to reach large portions of the network if it is well connected).

The exact payment that each node along the path to the authorizer then gets is 1/H of the distribution fee (I.e, x/(2H) per node). Any remaining distribution payments go directly to the authorizing node as an additional payment. In the paper we show (by proving game-theoretic statements) that this scheme has sufficient incentives for propagation as long as the originating node managed to send the transaction to enough neighbors.

back to top

Is the solution optimal? What are the costs?

Our proposed solution is not free of costs, and better solutions may exist.

First, we require small additional payments for rewarding propagation (but these are not large compared to the mining rewards).

Second, we add some complexity to the protocol. The chain along which messages are relayed becomes embedded in the blocks, and thus increases their size. In addition, more cryptographic signatures need to be validated when the message is passed along.

We hope that future research will address these issues, and perhaps propose other solutions.

back to top