Bitcoin Forum
March 19, 2024, 07:19:58 AM *
News: Latest Bitcoin Core release: 26.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1] 2 3 4 5 6 7 »  All
  Print  
Author Topic: Microsoft Researchers Suggest Method to Improve Bitcoin Transaction Propagation  (Read 17532 times)
nmat (OP)
Hero Member
*****
Offline Offline

Activity: 602
Merit: 501


View Profile
November 13, 2011, 03:46:42 AM
Last edit: November 13, 2011, 10:08:55 AM by nmat
 #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/
1710832798
Hero Member
*
Offline Offline

Posts: 1710832798

View Profile Personal Message (Offline)

Ignore
1710832798
Reply with quote  #2

1710832798
Report to moderator
1710832798
Hero Member
*
Offline Offline

Posts: 1710832798

View Profile Personal Message (Offline)

Ignore
1710832798
Reply with quote  #2

1710832798
Report to moderator
1710832798
Hero Member
*
Offline Offline

Posts: 1710832798

View Profile Personal Message (Offline)

Ignore
1710832798
Reply with quote  #2

1710832798
Report to moderator
There are several different types of Bitcoin clients. The most secure are full nodes like Bitcoin Core, which will follow the rules of the network no matter what miners do. Even if every miner decided to create 1000 bitcoins per block, full nodes would stick to the rules and reject those blocks.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1710832798
Hero Member
*
Offline Offline

Posts: 1710832798

View Profile Personal Message (Offline)

Ignore
1710832798
Reply with quote  #2

1710832798
Report to moderator
1710832798
Hero Member
*
Offline Offline

Posts: 1710832798

View Profile Personal Message (Offline)

Ignore
1710832798
Reply with quote  #2

1710832798
Report to moderator
1710832798
Hero Member
*
Offline Offline

Posts: 1710832798

View Profile Personal Message (Offline)

Ignore
1710832798
Reply with quote  #2

1710832798
Report to moderator
notme
Legendary
*
Offline Offline

Activity: 1904
Merit: 1002


View Profile
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.

https://www.bitcoin.org/bitcoin.pdf
While no idea is perfect, some ideas are useful.
rjk
Sr. Member
****
Offline Offline

Activity: 448
Merit: 250


1ngldh


View Profile
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 (OP)
Hero Member
*****
Offline Offline

Activity: 602
Merit: 501


View Profile
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: 756
Merit: 501


There is more to Bitcoin than bitcoins.


View Profile
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: 448
Merit: 250


1ngldh


View Profile
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
Legendary
*
Offline Offline

Activity: 1386
Merit: 1135


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


View Profile WWW
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 or hardware wallets instead.
notme
Legendary
*
Offline Offline

Activity: 1904
Merit: 1002


View Profile
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.

https://www.bitcoin.org/bitcoin.pdf
While no idea is perfect, some ideas are useful.
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218
Merit: 1063


Gerald Davis


View Profile
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. 
Littleshop
Legendary
*
Offline Offline

Activity: 1372
Merit: 1003



View Profile WWW
November 13, 2011, 04:36:19 AM
 #10

Wow.  Microsoft is this interested in Bitcoin?

gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4158
Merit: 8343



View Profile WWW
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
Legendary
*
Offline Offline

Activity: 1218
Merit: 1063


Gerald Davis


View Profile
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
HostFat
Staff
Legendary
*
Offline Offline

Activity: 4200
Merit: 1202


I support freedom of choice


View Profile WWW
November 13, 2011, 05:08:25 AM
 #13

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

NON DO ASSISTENZA PRIVATA - http://hostfatmind.com
nmat (OP)
Hero Member
*****
Offline Offline

Activity: 602
Merit: 501


View Profile
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
Legendary
*
Offline Offline

Activity: 1736
Merit: 1006

Let's talk governance, lipstick, and pigs.


View Profile
November 13, 2011, 10:25:52 AM
Last edit: November 15, 2011, 11:45:20 PM by cbeast
 #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
Legendary
*
expert
Offline Offline

Activity: 1526
Merit: 1078


View Profile
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.
phatsphere
Hero Member
*****
Offline Offline

Activity: 763
Merit: 500


View Profile
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.
FreeMoney
Legendary
*
Offline Offline

Activity: 1246
Merit: 1014


Strength in numbers


View Profile WWW
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
Legendary
*
Offline Offline

Activity: 3431
Merit: 1233



View Profile
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!
kokjo
Legendary
*
Offline Offline

Activity: 1050
Merit: 1000

You are WRONG!


View Profile
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:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!