This is a very simplified summary of the Microsoft Research paper “On Bitcoin and Red Balloons”. This summary is meant for people who already understand how the Bitcoin network and protocol function. For an overview of that see the Bitcoin Wikipedia page.
The flaw pointed out in the paper is that there is a negative incentive for miners to forward Bitcoin transactions. By not forwarding you increase the chance that you receive the transaction’s fee rather than another miner. This is not so much of an issue now as the fees usually total to much less than the 50BTC reward per block. But as the block reward diminishes in the future this negative incentive may become more of an issue.
The paper’s proposed solution is to reward nodes who forward transactions as well as nodes who solve the block in which the transaction is included. Each transaction would have a chain of its forwarding nodes attached to it. When a miner solves a block all nodes in the chains that lead the transactions in that block to the miner would be rewarded. The issue with this is that a single node can forward to itself many times to illegitimately gain more of the reward. This is called a Sybil attack.
Their solution to the Sybil attack is to give 0 reward to all nodes in a chain of forwards if the length of that chain is greater than H. This gives a negative incentive to create fake forwards to yourself in attempt to gain multiple rewards for a single transaction. Your best bet is to forward legitimately to other nodes and hope the transaction reaches a miner who solves it before the number of forwards is greater than H.
The paper determines optimal strategies in terms of values for H and the functions to divide the fee between nodes in the chain. But this is all modeled on directed trees (which have no cycles) rather than a random graph (which is what the Bitcoin network is like in reality) so it’s unknown how well it would work in practice. They leave work on random graphs for future research.
To clear up some common questions
What prevents nodes from faking/stripping the forward chain so that they can pretend as if they were the only forwarder?
The paper proposes changing the protocol so that you are must include the public key you are forwarding the transaction to and then signing it with your public key. So if the transaction was sending coins from coderrr -> sammy and the chain was coderrr, bob, alice, miner, it would look like this:
msg0 = sign_coderrr(coderrr->sammy, 1BTC, forwardto: bob) msg1 = sign_bob(msg0, forwardto: alice) msg2 = sign_alice(msg1, forwardto: miner)
Alice would not be able to recreate the initial message replacing alice for bob because she cannot sign as coderrr.
Please read the paper if you want details.
The goal here was just to summarize the paper to make it easier for people to get the gist of. I’m not arguing for or against the paper’s assumptions or conclusions.
Here is a bitcointalk forum discussion of how relevant this is to the actual Bitcoin network.