coderrr

November 13, 2011

Simplified Summary of Microsoft Research’s Bitcoin Paper on Incentivizing Transaction Propagation

Filed under: bitcoin, slashdotted — Tags: , — coderrr @ 8:51 am

Shameless Plug: Hide your IP while connected to the Bitcoin P2P network with a VPN Service.

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.

5 Comments »

  1. [...] by coderrr [link] [3 comments] Tweet This Post Sunday, November 13th, 2011 [...]

    Pingback by Simplified Summary of Microsoft Research’s Bitcoin Paper on Incentivizing Transaction Propagation | Bitcoin News — November 13, 2011 @ 7:41 pm

  2. [...] a Microsoft Bitcoin-dolgozatának, a “Bitcoinról és vörös ballonokról”-nak (“On Bitcoin and Red Balloons“). Olyan embereknek írom, akik már értik magának a Bitcoin hálózatának és a [...]

    Pingback by Röviden a Microsoft Bitcoin-ötletéről | Magyar Bitcoin Portál — November 14, 2011 @ 7:23 pm

  3. [...] by WP Greet Box WordPress PluginMicrosoft Research has identified what it thinks may be a flaw in the system: Namely, there’s an incentive for miners not to forward Bitcoin transactions. [...]

    Pingback by Is Bitcoin Flawed? Microsoft Research Says Maybe | Digitivity — November 15, 2011 @ 11:27 am

  4. This could be legit or it could be a way for Microsoft et al. to put a back door in Bit Coin to identify users. Don’t be wowed by technobable. Find out the facts.

    Comment by Anonymous — November 16, 2011 @ 3:46 am


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Silver is the New Black Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 28 other followers

%d bloggers like this: