Bitcoin Forum
April 21, 2014, 05:15:32 AM *
News: Due to the OpenSSL heartbleed bug, changing your forum password is recommended.
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 3 4 5 6 7  All
  Print  
Author Topic: Microsoft Researchers Suggest Method to Improve Bitcoin Transaction Propagation  (Read 11049 times)
nmat
Hero Member
*****
Offline Offline

Activity: 602


View Profile

Ignore
November 13, 2011, 03:46:42 AM
 #1

Quote
Bitcoin, which has been getting a large amount of public attention over the last year, represents a radical new approach to monetary systems which has appeared 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 fix 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. As the protocol is currently defined and implemented, it does not provide an incentive for nodes to broadcast transactions they are aware of. In fact, it provides a strong incentive not to do so. Our solution is to augment the protocol with a scheme that rewards information propagation

Paper at: http://research.microsoft.com/apps/pubs/default.aspx?id=156072
Source: http://www.thebitcointrader.com/2011/11/microsoft-researchers-suggest-method-to.html
Simplified summary: http://coderrr.wordpress.com/2011/11/13/simplified-summary-of-microsoft-researchs-bitcoin-paper-on-incentivizing-transaction-propagation/
1398057332
Hero Member
*
Offline Offline

Posts: 1398057332

View Profile Personal Message (Offline)

Ignore
1398057332
Reply with quote  #2

1398057332
Report to moderator
    mBitCASINOWIN BITCOINS IN OUR
24/7 LIVE DEALER CASINO

Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1398057332
Hero Member
*
Offline Offline

Posts: 1398057332

View Profile Personal Message (Offline)

Ignore
1398057332
Reply with quote  #2

1398057332
Report to moderator
1398057332
Hero Member
*
Offline Offline

Posts: 1398057332

View Profile Personal Message (Offline)

Ignore
1398057332
Reply with quote  #2

1398057332
Report to moderator
notme
Hero Member
*****
Offline Offline

Activity: 938


View Profile

Ignore
November 13, 2011, 03:51:28 AM
 #2

Quote
Bitcoin, which has been getting a large amount of public attention over the last year, represents a radical new approach to monetary systems which has appeared 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 fix 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. As the protocol is currently defined and implemented, it does not provide an incentive for nodes to broadcast transactions they are aware of. In fact, it provides a strong incentive not to do so. Our solution is to augment the protocol with a scheme that rewards information propagation

Paper: http://research.microsoft.com/pubs/156072/bitcoin.pdf
Source: http://www.thebitcointrader.com/2011/11/microsoft-researchers-suggest-method-to.html

They start with the assumption only miners relay transactions.  They use this to attempt to convince the reader of a need for their change.  Classic Microsoft "embrace and extend" where the extension is just there to break compatibility.

While no idea is perfect, some ideas are useful.
Programmer/Math Nerd
12jh3odyAAaR2XedPKZNCR4X4sebuotQzN
rjk
Sr. Member
****
Offline Offline

Activity: 420


1ngldh


View Profile

Ignore
November 13, 2011, 03:57:57 AM
 #3

Quote
Bitcoin, which has been getting a large amount of public attention over the last year, represents a radical new approach to monetary systems which has appeared 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 fix 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. As the protocol is currently defined and implemented, it does not provide an incentive for nodes to broadcast transactions they are aware of. In fact, it provides a strong incentive not to do so. Our solution is to augment the protocol with a scheme that rewards information propagation

Paper: http://research.microsoft.com/pubs/156072/bitcoin.pdf
Source: http://www.thebitcointrader.com/2011/11/microsoft-researchers-suggest-method-to.html

They start with the assumption only miners relay transactions.  They use this to attempt to convince the reader of a need for their change.  Classic Microsoft "embrace and extend" where the extension is just there to break compatibility.
I don't see that assumption when reading the paper. Did you read it or are you going by the very short snippet at the beginning of the thread?

Mining Rig Extraordinaire - the Trenton BPX6806 18-slot PCIe backplane [PICS] Dead project is dead, all hail the coming of the mighty ASIC!
nmat
Hero Member
*****
Offline Offline

Activity: 602


View Profile

Ignore
November 13, 2011, 04:02:14 AM
 #4

They start with the assumption only miners relay transactions.

That's exactly the opposite of what they wrote. What they are trying to improve is this: every node relays transactions, but only miners get paid (i.e. there is no incentive to relay a transaction. Actually, transaction fees are an incentive not to relay transactions)
niko
Hero Member
*****
Offline Offline

Activity: 742


There is more to Bitcoin than bitcoins.


View Profile

Ignore
November 13, 2011, 04:06:36 AM
 #5

I don't see that assumption when reading the paper. Did you read it or are you going by the very short snippet at the beginning of the thread?

My understanding after a few glances is that they base their work on the claim that nodes have the incentive NOT to broadcast the transaction (so that a node can increase its chances of getting the fees when it solves a block). This ignores the fact that clients broadcast transactions too.

Any publicity is good publicity?

They're there, in their room.
Your mining rig is on fire, yet you're very calm.
rjk
Sr. Member
****
Offline Offline

Activity: 420


1ngldh


View Profile

Ignore
November 13, 2011, 04:07:46 AM
 #6

They start with the assumption only miners relay transactions.

That's exactly the opposite of what they wrote. What they are trying to improve is this: every node relays transactions, but only miners get paid (i.e. there is no incentive to relay a transaction. Actually, transaction fees are an incentive not to relay transactions)

This is how I read it, yes.

Mining Rig Extraordinaire - the Trenton BPX6806 18-slot PCIe backplane [PICS] Dead project is dead, all hail the coming of the mighty ASIC!
casascius
Mike Caldwell
VIP
Hero Member
*
Offline Offline

Activity: 1204


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW

Ignore
November 13, 2011, 04:08:56 AM
 #7

I suppose this argument would be equivalent to saying in BitTorrent, that there is "no incentive" for people to seed files, therefore, eventually nobody will seed files and that BitTorrent will soon fail.

I am not sure that that'll be a problem in practice.  I think most people running a bitcoin node want to help the network succeed, and refusing to relay transactions (which are tiny in size and hardly a burden) just for the extremely remote chance that you'll get to be the only one to mine it into a block and collect the nickel transaction fee, just seems ridiculous to me.  If you hear about a transaction, it's just highly unlikely you're the only one who knows about it, since most nodes try to connect to 8 other nodes.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper wallets instead.
notme
Hero Member
*****
Offline Offline

Activity: 938


View Profile

Ignore
November 13, 2011, 04:22:56 AM
 #8

I don't see that assumption when reading the paper. Did you read it or are you going by the very short snippet at the beginning of the thread?

My understanding after a few glances is that they base their work on the claim that nodes have the incentive NOT to broadcast the transaction (so that a node can increase its chances of getting the fees when it solves a block). This ignores the fact that clients broadcast transactions too.

Any publicity is good publicity?

This.  They say people will cheat and not relay because they want the fees for themselves.

I don't see that assumption when reading the paper. Did you read it or are you going by the very short snippet at the beginning of the thread?

Yes, I read it.  The "problem" they are trying to solve (disincentive to relay) doesn't exist so long as non mining nodes continue to participate.  Non relaying nodes will be routed around, just like any other form of censorship on a highly connected network.

While no idea is perfect, some ideas are useful.
Programmer/Math Nerd
12jh3odyAAaR2XedPKZNCR4X4sebuotQzN
DeathAndTaxes
Donator
Hero Member
*
Offline Offline

Activity: 966



View Profile WWW

Ignore
November 13, 2011, 04:33:59 AM
 #9

They start with the assumption only miners relay transactions.  They use this to attempt to convince the reader of a need for their change.  Classic Microsoft "embrace and extend" where the extension is just there to break compatibility.

There is no such assumption.  Their points are valid.  They talk about the incentive to not-relay but they also talk about the lack of incentive to relay. We have actually seen a decrease in the number of nodes.  Why?  Many people don't see a need in having a client running all the time.  Why?  Oh yeah absolutely no incentive expect doing the "right thing" to help the network.   It is an interesting idea.  It likely is not viable to change the protocol but if non mining nodes had an incentive to support the network by propagation we likely would see 10x maybe 50x as many nodes globally and the network would be much stronger.

The p2p portion of the network relies on nodes sharing and relaying data but currently their is no incentive.  An individual can easily just use a eWallet or only run client when they want to send funds.  If that happens the network becomes weaker and easier to manipulate. 

Gerald Davis  CEO, Tangible Cryptography Inc.
BitSimple. A simpler way to buy and sell bitcoins
Littleshop
Hero Member
*****
Offline Offline

Activity: 1148



View Profile WWW

Ignore
November 13, 2011, 04:36:19 AM
 #10

Wow.  Microsoft is this interested in Bitcoin?

gmaxwell
Moderator
Hero Member
*
qt
Offline Offline

Activity: 1078


View Profile

Ignore
November 13, 2011, 04:46:27 AM
 #11

There is no such assumption.  There points are valid.  We have actually seen a decrease in the number of nodes.  Why?  Many people don't see a need in having a client running all the time.  Why?  Oh yeah absolutely no incentive expect doing the "right thing" to help the network.   It is an interesting idea.  It likely is not viable to change the protocol but if non mining nodes had an incentive to support the network by propagation we likely would see 10x maybe 50x as many nodes globally and the network would be much stronger.

But relaying for the sake of relaying doesn't really provide much value to the network besides providing more open ports— which are dirt cheap resources.

It would not increase the strength of the bitcoin distributed algorithm an ounce— that strength arises from validating the chain (which even offline clients will do when they come back online) and mining new blocks, not from flooding transactions.

I think it would be a _severe_ mistake to make the current crap P2P topology economically essential to the system.  The current p2p behavior is an artifact of the network bootstrapping behavior and we'd likely be better off with something else— fortunately the transport network is irrelevant distributed algorithm so we can have different transports (even many different transports being used at once)... though this wouldn't be true if there was some crazy incentive system baked into the transport.

Though we are for the moment stuck with the existing topology and we have, in the past, run short on listening nodes— If you want to create an incentive to have more of them— it's pretty simple. Run a lottery:  At random when a node gives you a transaction (perhaps a test transaction you originated someplace else in the network) give that node an IP transaction donation.  This can be run as a donation funded thing like the faucet— or better, miners can use the lottery to reward nodes for forwarding them TXN fee carrying transactions.  .. and this can be done without changing anything internal to bitcoin.

However I don't see _any_ evidence that an improvement in this area currently required. Moreover, if someone actually cared to improve things they should start by fixing UPNP so it doesn't time out shortly after startup. We'd probably get a significant boost in listening nodes that way.
DeathAndTaxes
Donator
Hero Member
*
Offline Offline

Activity: 966



View Profile WWW

Ignore
November 13, 2011, 04:53:46 AM
 #12

You don't see the frailty and lack of security if the number of nodes continues to drop.  A p2p network is resilient to attack by having huge number of redundant connections.  If that doesn't exist the fact that peers are untrusted can be exploited.

Attackers can create lots of "gatekeeper" nodes in an attempt to segregate the network enabling double spends by increasing the latency before each victim sees the other half. 

Also with small number of peers to choose from an attacker can gain information control over a victim.  While you have 8 connections (if firewalled) what is all 8 are the same attacker using geo-diverse server locations.  If that happens you only see what the attacker wants you to see.  Now that requires a large number of attack nodes relative to the number of "good" unfirewalled nodes.  Trying to pull that off on a network of 100,000 nodes is virtually impossible but against a network of only 2,000 nodes is far easier.

A p2p network must be distributed (not just the mining the ENTIRE network) and have very large number of nodes with interconnected mesh architecture.  Currently there is no reason for an individual to "assist" other than doing the right thing

Gerald Davis  CEO, Tangible Cryptography Inc.
BitSimple. A simpler way to buy and sell bitcoins
HostFat
Staff
Hero Member
*****
Offline Offline

Activity: 1330



View Profile WWW

Ignore
November 13, 2011, 05:08:25 AM
 #13

I hope that the Bitcoin team will give a look at this paper ...

Tip / Mancia / Donazione: Click! to Show
Bitmessage: BM-oqEkfpH9HA4vNYMdNmfyjR5zSMJ7pnU3Y
Bitcoin Foundation Italia
nmat
Hero Member
*****
Offline Offline

Activity: 602


View Profile

Ignore
November 13, 2011, 10:10:10 AM
 #14

Added a link to a simplified summary of the paper for those who don't want to read through all the math.
cbeast
Donator
Hero Member
*
Offline Offline

Activity: 1064

Bitcoin, Decorporated stockholder since 2011.


View Profile

Ignore
November 13, 2011, 10:25:52 AM
 #15

I suppose this argument would be equivalent to saying in BitTorrent, that there is "no incentive" for people to seed files, therefore, eventually nobody will seed files and that BitTorrent will soon fail.


We're already threatened by botnets and Mystery Miners, yet they find it's better to play along with a healthy Bitcoin network. I suppose if certain pools are seen to be not generating their fair share of Bitcoin blocks, then maybe it can be assumed they are gaming the system.

[edit 11/15/11] I love this thread. You guys will figure out what will happen with this project. I suspect there is little to worry about. After all, technology is continuously changing and the mining will go on at least another 10 years.

Any significantly advanced cryptocurrency is indistinguishable from Ponzi Tulips.
Mike Hearn
Hero Member
*****
expert
Offline Offline

Activity: 1232


View Profile

Ignore
November 13, 2011, 10:42:40 AM
 #16

It might be worth moving this thread to the Dev section.

This point has been discussed on the forum several times over the last couple of years. It's not a novel criticism though I'm glad the smart people at MSR are taking a hard look at Bitcoin. Hopefully they may see this thread and jump in with their thoughts.

Note that it's not just miners who have an incentive to not relay transactions. In theory, you could run a non-mining node that co-operates with a mining node. When you receive a transaction with a fee, you send it directly to the mining node and no others, in return for a small cut of the profits. It's unlikely to happen for a long time (if ever), as currently you could argue there's actually no incentive to include transactions at all - yet people still do.

I agree with Gregory, transaction broadcast is a simple and useful technique in the early days of the network, but if Bitcoin continues to grow and evolve we'll see a move away from it - it's often unnecessary, inefficient and has some strange incentive structures like the paper says. I'm not sure trying to fix it is the right approach.

What would replace it? I've argued in the past that senders should never attach fees because they aren't the one who actually cares about payment confirmation (they know they are trustworthy). Instead senders should send a free transaction directly to the receiver. They can then decide what to do with it - attach a fee (2nd tx) and broadcast, upload it directly to miners, or if you have high confidence in the sender to not double spend simply keep it around and pass it on to somebody else as part of a new payment.

Stefan has argued for an insurance company scheme in which merchants protect themselves against the risk of double spending by paying small premiums. In this setup, the receiver would have another option - transmit the received transaction straight to the insurance company. They'd verify it was valid and broadcast it in such a way that as many miners as possible are likely to receive it. Miners have incentives to connect directly to the insurance company nodes (or intermediate backbone nodes) and the insurance companies have incentives to make it easy for them. Broadcast over 10,000 connections really isn't a big deal for modern computers so I'm not worried about this kind of scalability.

Of course, this takes us a little bit further from the purist "zero trust" design that Satoshi was aiming for. Starting a new insurance company would (in the absence of functioning broadcast) be harder because you'd have to find all the miners. That doesn't worry me much - the long term future of mining is as a professional business, it's already gone that way to some extent, and all the incentives are aligned. Miners have an incentive to be visible and merchants/insurers have an incentive to seek them out. Whether that's done via a naive P2P broadcast or something more sophisticated, only time will tell.

12LMm82ZgAzf7yNDpPydEYxEr4Ap7XtSSK
phatsphere
Hero Member
*****
Offline Offline

Activity: 698


View Profile

Ignore
November 13, 2011, 11:13:46 AM
 #17

Wow.  Microsoft is this interested in Bitcoin?
Don't confuse microsoft with microsoft research. they are a completely different pair of shoes.

in case you want to be friends with my wallet, you have to send to 1HB9mgo3cdqBoC3jPemDpD8TPHFxcuQ8AD - http://www.bitcoin-austria.at/
FreeMoney
Hero Member
*****
Offline Offline

Activity: 1246


Strength in numbers


View Profile WWW

Ignore
November 13, 2011, 11:35:04 AM
 #18

Of course, this takes us a little bit further from the purist "zero trust" design that Satoshi was aiming for. Starting a new insurance company would (in the absence of functioning broadcast) be harder because you'd have to find all the miners. 

Miners will want to hear about the tx, no? Seems not like a problem at all.

Play Bitcoin Poker at sealswithclubs.eu. We're active and open to everyone.
becoin
Hero Member
*****
Offline Offline

Activity: 840



View Profile

Ignore
November 13, 2011, 11:53:04 AM
 #19

I suppose this argument would be equivalent to saying in BitTorrent, that there is "no incentive" for people to seed files
This is exactly what my wife is doing. She stops seeding to save bandwidth and to increase download speed.

therefore, eventually nobody will seed files and that BitTorrent will soon fail.
The incentive for bittorrent is getting copyrighted stuff for free. This why it won't fail. However, this is not the case with bicoin network!

18sNtvUmtW6nrQXfYt1wvviGockSWxhPBX
kokjo
Hero Member
*****
Offline Offline

Activity: 1022


You are WRONG! :D


View Profile

Ignore
November 13, 2011, 11:55:58 AM
 #20

I suppose this argument would be equivalent to saying in BitTorrent, that there is "no incentive" for people to seed files
This is exactly what my wife is doing. She stops seeding to save bandwidth and to increase download speed.

therefore, eventually nobody will seed files and that BitTorrent will soon fail.
The incentive for bittorrent is getting copyrighted stuff for free. This why it won't fail. However, this is not the case with bicoin network!

somebody still need to seed. and not just leech. the seed are getting nothing from it.

"The whole problem with the world is that fools and fanatics are always so certain of themselves and wiser people so full of doubts." -Bertrand Russell
Pages: [1] 2 3 4 5 6 7  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!