<p>I'm one of the authors of the paper you mention. We've written a summary of the paper aimed at the Bitcoin community in the hopes that it will help people to better understand the paper.</p>

<p>I hope this helps you as well. </p>

<p>Here is a link to the summary:
<a href="http://research.microsoft.com/en-us/people/avivz/bitcoin_red_balloons_summary.aspx" rel="noreferrer">http://research.microsoft.com/en-us/people/avivz/bitcoin_red_balloons_summary.aspx</a></p>

CC BY-SA 3.0
2011-11-17T17:54:08.880Z
Your paper analyzes a 'problem' that arises only due to the assumptions it makes. There is *no* problem unless you assume that nodes respond to the incentive not to send transactions but don't respond to the incentive to receive them. That is an irrational assumption, and in fact your proposed solution it merely to discard the assumption. Why would you assume people would hold onto transactions without also assuming they would sell them? It is strictly this assumption that creates the problem. **Both** incentives arise concurrently. Why assume only one is acted on?
David Schwartz
CC BY-SA 3.0
2011-11-18T11:12:44.397Z
Aviv, your summary has a condescending tone and still willfully ignores the fact that only a tiny fraction of the nodes on the P2P network do any mining -- the rest of the nodes have no incentive at all to withhold transactions.
eldentyrell
CC BY-SA 3.0
2011-11-19T20:42:14.927Z
@eldentyrell I don't see the tone you describe. Besides, the tone shouldn't matter. The summary clearly states "So we suspect the problem is not currently occurring or is not severe at the moment", so the key thing to understand is whether it could potentially become a problem in the future (especially given that mining must at some stage change from hobbyist to commercial scale unless the fundamental architecture is changed).
Highly Irregular
CC BY-SA 3.0
2011-11-17T07:15:13.867Z
2011-11-17T07:15:13.867Z
Aviv Zohar
<p>All you have to do is broadcast your transaction to a few major mining nodes. Whichever mines a block first will have every incentive to include your transaction.</p>

<p>It is a silly argument anyway. To precisely the same extent nodes are incentivized not to share their transactions with others, nodes are incentivized to get transactions from others. It should cancel out perfectly</p>

<p>It it's is worth X for you to get a transaction from me, I may not give it to you for much less than X. But why wouldn't you be willing to give me just a bit less than X for it?</p>

<blockquote>
  <p>... it sound[s] like there is incentive for miners to not pass on transactions as they would eventually get the transaction fee when they next solve a block ...</p>
</blockquote>

<p>That's absurd. The longer you hold onto a transaction, the less it's worth. You have no way to know how many other nodes have that transaction, and as soon as any miner includes the transaction in a block it is worthless. You have an incentive to get as much for the transaction as you can as quickly as possible from as many nodes as possible.</p>

CC BY-SA 3.0
2011-11-16T20:57:05.333Z
"All you have to do is broadcast your transaction to a few major mining nodes" - but this isn't currently the default behaviour, is it? That said, I don't actually know how the client does determine who to connect to!
Highly Irregular
CC BY-SA 3.0
2011-11-16T20:58:23.337Z
"To precisely the same extent nodes are incentivized not to share their transactions with others, nodes are incentivized to get transactions from others. It should cancel out perfectly." - this doesn't cancel out at all. It provides an incentive to receive but not send.
Highly Irregular
CC BY-SA 3.0
2011-11-16T23:58:40.393Z
@HighlyIrregular Same thing. The more incentive I have to buy coffee, the more incentive my local stores have to sell it. If you don't assume people respond to incentives, there's no problem. If you do, you have to assume people will respond to the incentive to receive transactions, likely by inducing others to send them transactions, those others will in turn respond to that incentive.
David Schwartz
CC BY-SA 3.0
2011-11-17T22:27:18.887Z
The coffee analogy doesn't work because there's an incentive for both parties in that case; the customer gets the coffee and the shop earns some money. With transactions, a miner has a monetary incentive to receive them, but no monetary incentive to pass them on as far as I can tell.
Highly Irregular
CC BY-SA 3.0
2011-11-17T22:32:52.817Z
@HighlyIrregular You're missing the whole point. Forget about money, don't assume you know the answer. All you know is that the shop has coffee and that the coffee has value to the customer. The customer now has an incentive to try to get the shop to part with the coffee. The shop now has an incentive to try to get the coffee to the customer. In both cases, the incentive is to get some of the value of the coffee to the customer. The natural result of these incentives is the sale of the coffee (or trade or whatever). But all you need are the two matched incentives, then something will result.
David Schwartz
CC BY-SA 3.0
2011-11-17T22:33:21.133Z
To get that there's a problem here, you'd have to assume that the two incentives somehow both go unsatisfied by all possible mechanisms. That's a completely idiotic assumption. In this case, the transaction's value drops to zero as soon as any miner includes it in a block, so they have a strong incentive to resolve the situation *fast* -- otherwise, they both lose out. (It's like the coffee is about to spoil. They'll work out some deal. The shop may even loan the customer money to buy the coffee!)
David Schwartz
CC BY-SA 3.0
2011-11-18T00:45:15.080Z
"The shop now has an incentive to try to get the coffee to the customer" - I don't see how the shop has that incentive unless the shop is giving away free coffee for the good of society (ie it has some motive beyond the profit motive). To stretch the analogy a little further, a Bitcoin client has an incentive to notify as many coffee shops as possible that it wants a coffee asap (and is offering $x for it), but while coffee shop A is trying to race to make the cup of coffee it's in shop A's best interests to NOT tell shop B about the fact that the client is offering $x for coffee.
Highly Irregular
CC BY-SA 3.0
2011-11-18T00:55:55.300Z
@HighlyIrregular If the coffee shop does not get the coffee to the customer, it cannot get any value from the fact that the customer wants the coffee. If the coffee shop does get the coffee to the customer, it can extract a fair share of the value of the coffee to the customer. (Again, forget about the money. It so happens that the way customers and coffee shops react to the incentives is by exchanging money. That doesn't matter. The point is, they react to the incentives.)
David Schwartz
CC BY-SA 3.0
2011-11-18T00:56:12.413Z
let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/1810/discussion-between-david-schwartz-and-highly-irregular)
David Schwartz
CC BY-SA 3.0
2011-11-21T08:50:10.410Z
Have added a comment to the question summarising my perspective of the results of our discussion.
Highly Irregular
CC BY-SA 3.0
2011-11-16T02:31:13.360Z
2011-11-16T16:44:40.657Z
2011-11-16T16:44:40.657Z
David Schwartz
<p><strong>This is a non-issue.</strong>  The Microsoft paper did not appear in a peer-reviewed venue (journal or conference).</p>

<p>There are (at least) two parts to the bitcoin network: the peer-to-peer transaction broadcasting network and the miners.  <strong>Only the miners have a disincentive to propagate transactions.  The overwhelming majority of the nodes on the internet running bitcoind are not mining</strong> or else are doing trivial amounts of CPU-mining because their admin forgot to use the -gen=0 flag.</p>

<p>If so-called "CPU-friendly" cryptocurrencies like "Tenberix" achieve their goals (which is doubtful) they may be vulnerable to this problem since they are intended to avoid the sort of specialized-miner situation that bitcoin embraces.</p>

CC BY-SA 3.0
2011-11-16T21:01:21.087Z
"The overwhelming majority of the nodes on the internet running bitcoind are not mining". I think this may well nullify the problem, but is it guaranteed? Is it possible for a malicious miner with many app instances (say, spread throughout a botnet) to get enough connections to a client to prevent the transaction being propagated as it should? I don't know how the client app decides who to connect to, and this could determine whether or not there's a vulnerability
Highly Irregular
CC BY-SA 3.0
2011-11-17T07:09:16.320Z
Irregular, If you can prevent somebody from talking to the Internet, you can prevent them from using Bitcoin.  However, this is a "problem" that is not unique to Bitcoin...
eldentyrell
CC BY-SA 3.0
2011-11-17T22:23:53.433Z
That's not what I meant - what I mean is: is it possible to target a particular client to try to fill up all its connections with malicious nodes?
Highly Irregular
CC BY-SA 3.0
2011-11-18T06:34:00.170Z
@HighlyIrregular You can fill up all its inbound connection slots, but then you're just preventing it from helping others. It will still make whatever number of outbound connections it is configured to make to nodes of its choosing.
David Schwartz
CC BY-SA 3.0
2011-11-16T01:37:16.760Z
2011-11-16T01:37:16.760Z
eldentyrell
<p>Once the 50BTC per block rewards have halved many times and the transaction fees start to become the primary reward for miners, it sound like there is incentive for miners to not pass on transactions as they would eventually get the transaction fee when they next solve a block. I just read about this in Slashdot -</p>

<p>This slashdot article:
<a href="http://science.slashdot.org/story/11/11/15/0456206/researchers-locate-flaw-in-bitcoin-protocol">http://science.slashdot.org/story/11/11/15/0456206/researchers-locate-flaw-in-bitcoin-protocol</a></p>

<p>Refers to another article, being:
<a href="http://coderrr.wordpress.com/2011/11/13/simplified-summary-of-microsoft-researchs-bitcoin-paper-on-incentivizing-transaction-propagation/">http://coderrr.wordpress.com/2011/11/13/simplified-summary-of-microsoft-researchs-bitcoin-paper-on-incentivizing-transaction-propagation/</a>
and a research paper produced by Microsoft (who would've thought they're interested in Bitcoins!?):
<a href="http://research.microsoft.com/pubs/156072/bitcoin.pdf">http://research.microsoft.com/pubs/156072/bitcoin.pdf</a></p>

<p>An obvious solution to the described problem is to reward nodes for sharing transactions, but this (as I understand it) leads to a "Sybil attack" where the attacker tries to gain an increased share of the rewards by sharing the transaction amongst other nodes controlled by the attacker.</p>

<p>The rest of the research paper seems to have a proposed solution, but it's beyond my understanding!</p>

<p><strong>Is this really a problem with the existing Bitcoin protocol? If yes, does the research paper have a genuine workable solution? Is it possible to describe that solution in laymen's terms?</strong></p>

CC BY-SA 3.0
2011-11-21T08:49:04.997Z
After much discussion with David Schwartz, my understanding is: Currently there are so many nodes (miners and not) spreading transactions that there's no issue. If the situation changed, non-miners still have the (strong) incentive to spread their transactions as widely as possible, and miners have an incentive to ensure that they get them quickly. Simple changes to the way bitcoin works or even transaction distribution services would ensure that the 2 parties (miners & non-miners) get in touch. ie each party has an incentive to get something working. If correct, can someone summarise this?
Highly Irregular
<attack><mining-theory><transaction-propagation>
Flaw in Bitcoin protocol regarding incentives to share transactions
Highly Irregular
# Flaw in Bitcoin protocol regarding incentives to share transactions

(Asked by: username_0 on 2011-11-16)

Once the 50BTC per block rewards have halved many times and the transaction fees start to become the primary reward for miners, it sound like there is incentive for miners to not pass on transactions as they would eventually get the transaction fee when they next solve a block. I just read about this in Slashdot -

This slashdot article:
<http://science.slashdot.org/story/11/11/15/0456206/researchers-locate-flaw-in-bitcoin-protocol>

Refers to another article, being:
<http://coderrr.wordpress.com/2011/11/13/simplified-summary-of-microsoft-researchs-bitcoin-paper-on-incentivizing-transaction-propagation/>
and a research paper produced by Microsoft (who would've thought they're interested in Bitcoins!?):
<http://research.microsoft.com/pubs/156072/bitcoin.pdf>

An obvious solution to the described problem is to reward nodes for sharing transactions, but this (as I understand it) leads to a "Sybil attack" where the attacker tries to gain an increased share of the rewards by sharing the transaction amongst other nodes controlled by the attacker.

The rest of the research paper seems to have a proposed solution, but it's beyond my understanding!

**Is this really a problem with the existing Bitcoin protocol? If yes, does the research paper have a genuine workable solution? Is it possible to describe that solution in laymen's terms?**

**Tags:** attack, mining-theory, transaction-propagation

> **Comments:**
> **username_0**: After much discussion with username_2 username_2, my understanding is: Currently there are so many nodes (miners and not) spreading transactions that there's no issue. If the situation changed, non-miners still have the (strong) incentive to spread their transactions as widely as possible, and miners have an incentive to ensure that they get them quickly. Simple changes to the way bitcoin works or even transaction distribution services would ensure that the 2 parties (miners & non-miners) get in touch. ie each party has an incentive to get something working. If correct, can someone summarise this?  

---

## 3 answers

### Answer by username_3 on 2011-11-16. Score: 6 | Accepted answer

**This is a non-issue.** The Microsoft paper did not appear in a peer-reviewed venue (journal or conference).

There are (at least) two parts to the bitcoin network: the peer-to-peer transaction broadcasting network and the miners. **Only the miners have a disincentive to propagate transactions. The overwhelming majority of the nodes on the internet running bitcoind are not mining** or else are doing trivial amounts of CPU-mining because their admin forgot to use the -gen=0 flag.

If so-called "CPU-friendly" cryptocurrencies like "Tenberix" achieve their goals (which is doubtful) they may be vulnerable to this problem since they are intended to avoid the sort of specialized-miner situation that bitcoin embraces.

> **Comments:**
> **username_0**: "The overwhelming majority of the nodes on the internet running bitcoind are not mining". I think this may well nullify the problem, but is it guaranteed? Is it possible for a malicious miner with many app instances (say, spread throughout a botnet) to get enough connections to a client to prevent the transaction being propagated as it should? I don't know how the client app decides who to connect to, and this could determine whether or not there's a vulnerability  
> **username_3**: username_0, If you can prevent somebody from talking to the Internet, you can prevent them from using Bitcoin.  However, this is a "problem" that is not unique to Bitcoin...  
> **username_0**: That's not what I meant - what I mean is: is it possible to target a particular client to try to fill up all its connections with malicious nodes?  
> **username_2**: @username_0 You can fill up all its inbound connection slots, but then you're just preventing it from helping others. It will still make whatever number of outbound connections it is configured to make to nodes of its choosing.  

---

### Answer by username_1 on 2011-11-17. Score: 5

I'm one of the authors of the paper you mention. We've written a summary of the paper aimed at the Bitcoin community in the hopes that it will help people to better understand the paper.

I hope this helps you as well.

Here is a link to the summary:
<http://research.microsoft.com/en-us/people/avivz/bitcoin_red_balloons_summary.aspx>

> **Comments:**
> **username_2**: Your paper analyzes a 'problem' that arises only due to the assumptions it makes. There is *no* problem unless you assume that nodes respond to the incentive not to send transactions but don't respond to the incentive to receive them. That is an irrational assumption, and in fact your proposed solution it merely to discard the assumption. Why would you assume people would hold onto transactions without also assuming they would sell them? It is strictly this assumption that creates the problem. **Both** incentives arise concurrently. Why assume only one is acted on?  
> **username_3**: username_1, your summary has a condescending tone and still willfully ignores the fact that only a tiny fraction of the nodes on the P2P network do any mining -- the rest of the nodes have no incentive at all to withhold transactions.  
> **username_0**: @username_3 I don't see the tone you describe. Besides, the tone shouldn't matter. The summary clearly states "So we suspect the problem is not currently occurring or is not severe at the moment", so the key thing to understand is whether it could potentially become a problem in the future (especially given that mining must at some stage change from hobbyist to commercial scale unless the fundamental architecture is changed).  

---

### Answer by username_2 on 2011-11-16. Score: 2

All you have to do is broadcast your transaction to a few major mining nodes. Whichever mines a block first will have every incentive to include your transaction.

It is a silly argument anyway. To precisely the same extent nodes are incentivized not to share their transactions with others, nodes are incentivized to get transactions from others. It should cancel out perfectly

It it's is worth X for you to get a transaction from me, I may not give it to you for much less than X. But why wouldn't you be willing to give me just a bit less than X for it?

> ... it sound[s] like there is incentive for miners to not pass on transactions as they would eventually get the transaction fee when they next solve a block ...

That's absurd. The longer you hold onto a transaction, the less it's worth. You have no way to know how many other nodes have that transaction, and as soon as any miner includes the transaction in a block it is worthless. You have an incentive to get as much for the transaction as you can as quickly as possible from as many nodes as possible.

> **Comments:**
> **username_0**: "All you have to do is broadcast your transaction to a few major mining nodes" - but this isn't currently the default behaviour, is it? That said, I don't actually know how the client does determine who to connect to!  
> **username_0**: "To precisely the same extent nodes are incentivized not to share their transactions with others, nodes are incentivized to get transactions from others. It should cancel out perfectly." - this doesn't cancel out at all. It provides an incentive to receive but not send.  
> **username_2**: @username_0 Same thing. The more incentive I have to buy coffee, the more incentive my local stores have to sell it. If you don't assume people respond to incentives, there's no problem. If you do, you have to assume people will respond to the incentive to receive transactions, likely by inducing others to send them transactions, those others will in turn respond to that incentive.  
> **username_0**: The coffee analogy doesn't work because there's an incentive for both parties in that case; the customer gets the coffee and the shop earns some money. With transactions, a miner has a monetary incentive to receive them, but no monetary incentive to pass them on as far as I can tell.  
> **username_2**: @username_0 You're missing the whole point. Forget about money, don't assume you know the answer. All you know is that the shop has coffee and that the coffee has value to the customer. The customer now has an incentive to try to get the shop to part with the coffee. The shop now has an incentive to try to get the coffee to the customer. In both cases, the incentive is to get some of the value of the coffee to the customer. The natural result of these incentives is the sale of the coffee (or trade or whatever). But all you need are the two matched incentives, then something will result.  
> **username_2**: To get that there's a problem here, you'd have to assume that the two incentives somehow both go unsatisfied by all possible mechanisms. That's a completely idiotic assumption. In this case, the transaction's value drops to zero as soon as any miner includes it in a block, so they have a strong incentive to resolve the situation *fast* -- otherwise, they both lose out. (It's like the coffee is about to spoil. They'll work out some deal. The shop may even loan the customer money to buy the coffee!)  
> **username_0**: "The shop now has an incentive to try to get the coffee to the customer" - I don't see how the shop has that incentive unless the shop is giving away free coffee for the good of society (ie it has some motive beyond the profit motive). To stretch the analogy a little further, a Bitcoin client has an incentive to notify as many coffee shops as possible that it wants a coffee asap (and is offering $x for it), but while coffee shop A is trying to race to make the cup of coffee it's in shop A's best interests to NOT tell shop B about the fact that the client is offering $x for coffee.  
> **username_2**: @username_0 If the coffee shop does not get the coffee to the customer, it cannot get any value from the fact that the customer wants the coffee. If the coffee shop does get the coffee to the customer, it can extract a fair share of the value of the coffee to the customer. (Again, forget about the money. It so happens that the way customers and coffee shops react to the incentives is by exchanging money. That doesn't matter. The point is, they react to the incentives.)  
> **username_2**: let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/1810/discussion-between-username_2-username_2-and-username_0-username_0)  
> **username_0**: Have added a comment to the question summarising my perspective of the results of our discussion.  

---

