Microsoft Researchers Suggest Method to Improve Bitcoin Transaction Propagation

[nmat]

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/

[1714260518]

1714260518

[1714260518]

1714260518

[1714260518]

1714260518

[notme]

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.

[rjk]

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?

[nmat]

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]

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?

[rjk]

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.

[casascius]

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.

[notme]

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.

[DeathAndTaxes]

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]

Wow.  Microsoft is this interested in Bitcoin?

[gmaxwell]

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]

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]

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

[nmat]

Added a link to a simplified summary of the paper for those who don't want to read through all the math.

[cbeast]

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.

[Mike Hearn]

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]

Wow.  Microsoft is this interested in Bitcoin?

Don't confuse microsoft with microsoft research. they are a completely different pair of shoes.

[FreeMoney]

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.

[becoin]

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]

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.

[P4man]

Wow.  Microsoft is this interested in Bitcoin?

Don't confuse microsoft with microsoft research. they are a completely different pair of shoes.

They still work for microsoft. I have to agree with Littleshop, I find this extremely interesting, if not shocking. Im not naive, I dont expect this will result in microsoft's application store accepting bitcoins next year, but still, MS -even their research department- taking it seriously is not insignificant.

[theymos]

Long-term I expect there to be a simple network among full nodes (probably mostly miners and big sites), and a fancy overlay network that most clients connect to. The overlay network will be used to get transactions from clients to full nodes and from full nodes to the involved clients. The purpose of this is to minimize load on both full nodes and clients. Complex incentive and anti-abuse techniques can be used here.

Clients may also be given the option to connect to one or more servers that perform the same function as the overlay network. Some servers may have fees.

In any case, both miners and senders really want to get/send transactions, so I'm sure something good will be worked out.

[wareen]

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

They get more information about the people who download and maybe that's exactly what they're after

[herzmeister]

yap Microsoft Research is like Google Labs.

Bitcoin could surely be interesting for Microsoft as a way to compete with Google wallet, they could use it in their XBox/Live services etc...

But for sure it doesn't mean anything. For example there's the phenomenally successful MS Research's Gestalt project which allows web pages to use other languages like Ruby or Python instead of JavaScript simply by using it inside script tags. It shook the foundations of this world, didn't it. I mean who wouldn't love to have more choice. It requires Silverlight or Moonlight (Mono) to be installed though, and folks don't like it just because it's Microsoft, and it probably also fell apart because of internal power struggles and strategy shifts within Microsoft.

So same thing can happen for anything they try to do with Bitcoin.

[becoin]

Of course, this takes us a little bit further from the purist "zero trust" design that Satoshi was aiming for.

Satoshi was aiming at CPU power, not GPU power!

Every monetary system not only serves real economy but is an economy of its own. This is valid for the bitcoin network as well. Giving the control in the hands of a dozen of mining pools is not different to giving the control of current fiat money monetary system in the hands of a dozen bank cartels. The bitcoin protocol should be changed to discourage pool mining! Never forget, bitcoin is about decentralization not centralization!

[BTCurious]

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.

For normal transactions, maybe not. But if I ran a miner, and got a transaction with a fee of 50 bitcoins, I would surely keep it to myself. Which is a bit counterproductive, given that such a high fee is intended to get fast verification...

[kokjo]

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.

For normal transactions, maybe not. But if I ran a miner, and got a transaction with a fee of 50 bitcoins, I would surely keep it to myself. Which is a bit counterproductive, given that such a high fee is intended to get fast verification...

problem: you can't keep it to yourself.
why: its broadcasted.

also the bitcoin network its in its baby state right now. in the future, we might see that we are connecting directly to miner pools, are send them the transactions. or sending txs to hubs, that are connected to alot of miners.
remember that bitcoin has just begun.

[Steve]

I think an important point that this paper misses is that while there is an incentive for miners to keep fee bearing transactions to themselves, all non-mining nodes (which presumably exist to either send or receive bitcoins) have a very strong incentive to relay both blocks and transactions.  As the recipient of bitcoins, what matters to you is that you can later spend those bitcoins.  For that reason, you will want to make sure you stay in sync with the rest of the network and that the rest of the network stays in sync with you.  For transactions that are generally broadcast into the network, I have no doubt that they'll quickly propagate to the vast majority of nodes, including miners…again, there is a strong incentive for "transactional" (non mining) nodes to do this.  In fact, were it not for the need to break ties regarding conflicting transactions, bitcoin wouldn't need miners or a block chain (ignoring the need to introduce new coins into circulation).  In such a block-chainless world, all you would care about is "checking in" with your favorite merchants and exchanges to make sure they recognize a transaction as being valid.  Again, a strong incentive to relay transactions and stay in sync with the network.

As Mike Hearn points out, it is the recipient of bitcoins that has an incentive for a transaction to be included in a block…the sender doesn't care.  For this reason, I think we'll eventually get to a point where most fee bearing transactions are the second in a sequence of two transactions.  The first transaction is the actual transfer to the recipient and does not include a fee, the second transaction is a spend back to one's self with a fee attached.  For transactions between trusted parties, this second transaction may never be created because the parties don't really care how long it takes for it to appear in a block since they trust each other.  In cases where the two parties don't trust each other, fees will be used to ensure the transaction is included in a block in a timely manner.  Since these transactions are spends back to one's self, you can create multiple versions of the second transaction with differing fees.  They would conflict with one another, but since they are all sending funds back to yourself, you don't really care…you just want one of them to make it into a block as soon as possible.  Why you might want to do this is explained in the following paragraph.

Large mining pools that might want to charge a premium to have transactions included in their blocks may provide an interface to directly submit transactions.  They will certainly keep those transactions for themselves.  However, nothing stops the submitter from broadcasting that transaction to other pools, or broadcasting a conflicting transaction that pays a lower fee to other pools (or to the network in general).  In fact, it is advantageous if the pool doesn't forward the transaction since it provides an opportunity for the originator of the transaction to create multiple variations of the same transaction that award lesser or no fees.  Another miner could pick up one of the lesser fee transactions and it would have the affect of reducing the overall transaction costs.  Larger pools could command higher fees up to a point where the fees become so great that people stop submitting transactions to that pool.  Miners will gravitate to the pools that optimize their fee structure such that they consistently payout the highest rewards.  Pools could even have a fee schedule such that they sit on lower fee transactions for a period of time before including them.  As the fee goes higher, they include the transactions sooner.

So, I guess to sum it up…not only do I think it's not a problem that miners do not have an incentive to forward fee bearing transactions, I think it might actually be necessary to create a real marketplace for transaction processing.

[Steve]

Of course, this takes us a little bit further from the purist "zero trust" design that Satoshi was aiming for.

Satoshi was aiming at CPU power, not GPU power!

Every monetary system not only serves real economy but is an economy of its own. This is valid for the bitcoin network as well. Giving the control in the hands of a dozen of mining pools is not different to giving the control of current fiat money monetary system in the hands of a dozen bank cartels. The bitcoin protocol should be changed to discourage pool mining! Never forget, bitcoin is about decentralization not centralization!

This is an irrational fear.  Mining pools do not control the actual mining hardware.  All that's necessary is close monitoring the behavior of the pools with regard to transaction inclusion and better mining software that can automatically switch between pools or start mining solo if a pool goes offline or starts behaving in a manner inconsistent with the goal of securing bitcoin transactions.

[becoin]

As Mike Hearn points out, it is the recipient of bitcoins that has an incentive for a transaction to be included in a block…the sender doesn't care.

A transaction is a transaction if only it is included in the block chain. All the rest is just expressed intention for a transaction... What you basically say is that the seller is more interested in a transaction than the buyer?! Sorry, I can't agree.

[Steve]

As Mike Hearn points out, it is the recipient of bitcoins that has an incentive for a transaction to be included in a block…the sender doesn't care.

A transaction is a transaction if only it is included in the block chain. All the rest is just expressed intention for a transaction

If you've ever attempted a double spend, you'll know that transactions matter long before they make it into the block chain.  It's the feasibility of a successful double spend that decreases as a transaction becomes more deeply embedded in the block chain, but a double spend is still tricky to pull off even without the block chain.  So, indeed, a transaction is a transaction from the moment it is broadcast to the p2p network.

... What you basically say is that the seller is more interested in a transaction than the buyer?! Sorry, I can't agree.

No, what I'm saying is that the recipient of bitcoins has an incentive to get that transaction into the block chain because that improves the marketability of those bitcoins.  The sender certainly cares about the transaction because presumably they are receiving something from the other party in exchange for their bitcoins, but the sender has no reason to distrust themselves and therefore no need to have the transaction appear in the block chain.

[becoin]

No, what I'm saying is that the recipient of bitcoins has an incentive to get that transaction into the block chain because that improves the marketability of those bitcoins. 

This is just another way of saying that bitcoins are more precious than goods purchased with those bitcoins. What about the "marketability" of goods purchased with bitcoins?

[cypherdoc]

No, what I'm saying is that the recipient of bitcoins has an incentive to get that transaction into the block chain because that improves the marketability of those bitcoins. 

This is just another way of saying that bitcoins are more precious than goods purchased with those bitcoins. What about the "marketability" of goods purchased with bitcoins?

this is not a question of the relative value of the merchandise vs the btc used to buy them.  it is about the seller having every reason to ensure that the "money" used to buy his goods is real and not already spent elsewhere thus his motivation to broadcast the tx as widely as possible as soon as possible with or w/o a fee attached in order to get the tx verified into his receiving address.

[MysteryMiner]

Incentive to send or don't send transactions. You are talking like there is option in Bitcoin client to chooze that behaviour. Someone actually need to write the modified version of Bitcoin client and majority of users need to download and install that version instead of original. There is modified DC++ clients available that does not share anything they are pretending to share, but 99.8% users run well behaving DC++ and are sharing the files.

[cypherdoc]

i skimmed through the original paper.  lotsa mathematics attempting to model human behavior.  its impossible.  if it were, the quants on Wall St would never sustain losses.  people do all sorts of unpredictable things depending on the situation.  this is why investing is so difficult.

[DeathAndTaxes]

Incentive to send or don't send transactions. You are talking like there is option in Bitcoin client to chooze that behaviour. Someone actually need to write the modified version of Bitcoin client and majority of users need to download and install that version instead of original. There is modified DC++ clients available that does not share anything they are pretending to share, but 99.8% users run well behaving DC++ and are sharing the files.

Or they simply don't use the client at all.  Or only leave it running when they want to send/receive a transaction.  The number of nodes online has been declining for some time.

[becoin]

it is about the seller having every reason to ensure that the "money" used to buy his goods is real and not already spent elsewhere thus his motivation to broadcast the tx as widely as possible as soon as possible with or w/o a fee attached in order to get the tx verified into his receiving address.

It is just the same with the buyer... I'll paraphrase your above mentioned statement:

it is about the buyer having every reason to ensure that the "goods" he purchased are under his ownership and not already purchased by someone else thus his motivation to broadcast the tx as widely as possible as soon as possible with or w/o a fee attached in order to get the tx verified and included into the block chain.

This is why the buyer and the seller have exactly the same interest broadcasting the tx they have made!

[Mageant]

I think if some miners started actually behaving like this (not relaying transactions) then people would notice and they would get a bad reputation.
So at least for mining pools there would be disincentive to do this (which make up the bulk of the hashing power).

[m0mchil]

Hmm... I don't rebroadcast transactions in order to keep more of the fees for myself. But fees are denominated in... BTC. By not supporting the network and eventually breaking it, BTC will tend to have value of... right, zero. So, I don't really have an incentive to maintain cooperating node?

Confused.

[dree12]

Hmm... I don't rebroadcast transactions in order to keep more of the fees for myself. But fees are denominated in... BTC. By not supporting the network and eventually breaking it, BTC will tend to have value of... right, zero. So, I don't really have an incentive to maintain cooperating node?

Confused.

Your own impact on the breaking of the network is near zero. The impact of all the nodes is what matters - think about it: why would you waste time voting in an uncompetitive election that it is clear who will win?

I don't agree completely, as humans are irrational. But a bloc of robots using bitcoin will, unless utilizing superrationality strategies, suppress broadcasting the average transaction.

[BeeCee1]

I think Microsoft's assumption of a directed graph oversimplifies things to the extent that in invalidates their research.  In short, a node always has an incentive to try and follow the chain back towards the source to insert themselves higher in the chain and to shorten it.  This gives them a larger reward.

Acording to their  paper, each node in the chain up to a depth of 'H' gets a reward B.  The node that solves the block gets a fixed reward plus some additonal reward based on how much shorter than H the chain was "1+(H-L+1)B"  This means the shorter the chain is, the greater the reward that goes to  the miner.  For simplicity, lets take H to be 4 and a chain of the full length:

NodeA
NodeB
NodeC
NodeD

NodeD solves the transaction so gets a reward of 1+(4-4+1)*B = 1+B. The total reward would be B for NodeA, NodeB, and NodeC and 2B for NodeD for a total of 1+4B.  However, if NodeD were able to contact NodeA directly the chain would be:

NodeA
NodeD

Node D again solves the transaction but this time its reward is 1+(4-2+1)*B = 1+3B with nodeA getting the remaining B, the total reward is still 1+4B.

Initially NodeD doesn't know how to contact NodeA, it only has a public key not an IP address, however, over time, as NodeD sees more transactions it will be able to associate particular keys with particular IP addresss.  For instance, in the first example, NodeD learned what NodeC's ip address is since it got the transaction directly from it.  In the event that NodeD didn't know how to contact any other nodes in the chain, it would be to its advantage to contact every node it knows and ask for the transaction in the hopes that one peer would be part of a shorter chain, this could greatly increase the amount of traffic that goes over the network.

The stated goal of the paper was to incentivise forwarding of transactions by paying intermediate nodes.  Intermediate nodes, however, would be cut out of the chain fairly quickly so would have the same incentive they have today (which is none, but that may not stop them from forwarding).

This scheme could have a perverse effect though.  Right now you can't gain any real advantage by trying to monopolize the connections a node has.  Under this proposal you would.  If all the nodes connected to a particular originating node were controlled by you, you couldn't be cut out of the chain since no one would know how to contact the originating node.  Instead of encouraging more peers by providing them with fees, it would encourage more centralization.

[MysteryMiner]

Incentive to send or don't send transactions. You are talking like there is option in Bitcoin client to chooze that behaviour. Someone actually need to write the modified version of Bitcoin client and majority of users need to download and install that version instead of original. There is modified DC++ clients available that does not share anything they are pretending to share, but 99.8% users run well behaving DC++ and are sharing the files.

Or they simply don't use the client at all.  Or only leave it running when they want to send/receive a transaction.  The number of nodes online has been declining for some time.

Not running client all the time? This generally is similar to Bitcoin network geting attacked by large goverment or probably even ANO and only one or two nations have Bitcoin network in operable state. The network are resistant to such attacks as I read long time ago. Does simply not running Bitcoint client all the time affects the network at all?

[DeathAndTaxes]

Or they simply don't use the client at all.  Or only leave it running when they want to send/receive a transaction.  The number of nodes online has been declining for some time.

Not running client all the time? This generally is similar to Bitcoin network geting attacked by large goverment or probably even ANO and only one or two nations have Bitcoin network in operable state. The network are resistant to such attacks as I read long time ago. Does simply not running Bitcoint client all the time affects the network at all?

Um it isn't that hard.  A node is only a node when the client is running.   If you have 100K users but they on average only have the client running for 2 minutes a day then in effect at any particular time you only have a couple hundred nodes running.  It has nothing to do w/ a govt attacking Bitcoin. 

[gmaxwell]

This scheme could have a perverse effect though.  Right now you can't gain any real advantage by trying to monopolize the connections a node has.  Under this proposal you would.  If all the nodes connected to a particular originating node were controlled by you, you couldn't be cut out of the chain since no one would know how to contact the originating node.  Instead of encouraging more peers by providing them with fees, it would encourage more centralization.

Yup.  Often providing payment perverts incentives too.  forwarding txn is so damn cheap that lots of people will do it for 'free' (just the compensation of helping the network overall).... once you start paying people won't forward txn that have too many hops for them to get paid on anymore.

Another thing not discussed in the embodiment of the payment chain.   Here is how it would have to work:

Today you construct SIGN_A(TX()) and that gets flooded. Under this system you'd have to instead construct   SIGN_A(TX()+PEER_X)  for each of your X peers. Then, peer B for example would construct   SIGN_B(SIGN_A(TX()+PEER_B)+PEER_C)  .. and C would construct SIGN_C(SIGN_B(SIGN_A(TX()+PEER_B)+PEER_C)+PEER_D)  ... and so on.  So each hop would now require $HOPS expensive signature validations, plus an expensive signing operation per next-hop peer, and would also add ~130 bytes of data (the next public key and a signature).  Just two hops would easily more than double the computational and storage cost of the transaction.

It's a neat area of research, but I'm doubtful that its actually applicable to bitcoin.

[asdf]

I raised the issue of nodes withholding transactions earlier in this thread:
https://bitcointalk.org/index.php?topic=5024.0
Some concluded that the market would produce transaction relay subscription services.

On a related note; what if the fees were changed so that the miner solving the block is rewarded with the fees from the block that he builds on instead of the block he mined? This would remove the incentive to withhold transactions, because the miner's reward is no tied to the transactions that a miner accepts.

[avivz]

Hi Everyone,

I’m one of the authors of the paper “On Bitcoin and Red Balloons”. I’ve been following the discussion in this thread with great interest. We are very happy to get comments from the Bitcoin community and to discuss our work. We were pleasantly surprised to see that the community found our paper so fast (on the very day it was uploaded to the website).

I would love to respond to some of the great comments you guys have already made (I would have jumped in sooner, but it took a while to get a whitelisted account that would allow me to post to the forums). Before starting, I would like to say that while I do work for Microsoft, my comments do not reflect the company’s policy or strategy in any way. Microsoft Researchers are allowed a great deal of freedom in choosing their research topics, and thus our personal interest in Bitcoin should not necessarily be interpreted as interest by the company – it is our personal research agenda.  My co-authors and I do find BitCoin a fascinating endeavor, and we would personally like to see it succeed.

One of the first points I would like to address is the suggestion that Bitcoin can survive by relying on non-mining relay nodes that volunteer to transfer transaction information.  It is certainly true that at Bitcoin’s current size the requirements from relay nodes are very modest, and that there are many volunteers. However, we are interested in forming a stronger foundation for Bitcoin even as it scales up. I’ve been looking at the scalability page on the wiki (https://en.bitcoin.it/wiki/Scalability), and I think the requirements from nodes suggested there (taking Visa’s transaction volume as an approximate target) can be heavily taxing on nodes. At these high transaction volumes it seems like nodes need a great deal of processing power, storage, and bandwidth (the latter  being perhaps the least of their concerns) even without the potential costs of mining. These requirements are certainly affordable by someone who mines Bitcoins commercially, but I’m not sure you’d like to base the future of the currency on the hopes that many nodes will contribute so many resources freely.

Even in BitTorrent, which was mentioned above as a system in which people contribute resources altruistically, there are many complaints about non-contributing members. In fact, a great deal of BitTorrent activity is conducted in closed communities that more carefully monitor the contribution of members. Besides that, BitTorrent is much less crucial than a monetary system. If your file has no seeders then it’s not that big of a deal, but if the monetary system is shaky, it may have terrible consequences.

One more comment to asdf:  Your suggestion of paying miners with the fees gathered in the previous block is interesting. But wouldn’t that change the incentives miners when choosing which transactions to accept or reject? Or the incentives of buyers to give a transaction-fee? Right now, the miner that is currently working on a block can decide to reject a specific transaction (due to insufficient fees) but if that miner doesn’t directly get the fee from the current block, why would we trust him to accept transactions “properly”? For example, He may choose not to add any transactions at all, and save up on processing power needed for verification.

I hope to hear more interesting comments from community members. Our paper is written for an audience of theoretical computer scientists (which are more familiar with game-theoretic aspects but less familiar with Bitcoin) and we are very interested in the complementary viewpoint of Bitcoin practitioners.

Thanks!

[makomk]

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?

At some point, nodes will have an incentive not to broadcast transactions too - once blocks start reaching the maximum amount of free transactions, they can improve the odds that their transactions get in by not relaying everyone else's.

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.

True, though BitTorrent has incentives to upload chunks of a file that you're currently downloading which at provides some limit on freeloading. In practice if you want a public file to remain seeded for long you do have to provide seeds yourself though. (Interestingly, Microsoft Research did come up with something they claimed was better than BitTorrent a while ago and apparently failed to quite understand how that worked.)

[pointbiz]

I think a bitcoin node is walking in the dark, piecing together reality by touching (sending) and feeling (receiving) transactions and blocks. You only feel confident in what you know if everyone else knows it too. That's why you send (influence) and receive (listen) freely. So you have confidence in the value of your bitcoins.

[asdf]

One more comment to asdf:  Your suggestion of paying miners with the fees gathered in the previous block is interesting. But wouldn’t that change the incentives miners when choosing which transactions to accept or reject? Or the incentives of buyers to give a transaction-fee? Right now, the miner that is currently working on a block can decide to reject a specific transaction (due to insufficient fees) but if that miner doesn’t directly get the fee from the current block, why would we trust him to accept transactions “properly”? For example, He may choose not to add any transactions at all, and save up on processing power needed for verification.

It would certainly change the incentives of miners to accept transactions. A miner will have to add some value to the block otherwise no one else will build on it. He might also reject low fee transactions to put upward pressure on fee prices. These two opposing forces will set a market price for fees, which may also address this problem: https://bitcointalk.org/index.php?topic=6284.200

It's also a trivial change to implement, although It may be infeasible at this point to alter the existing system. So far it seems to me like a positive alteration to bitcoin. More debate would be appreciated.

I only skimmed over the paper. Looks interesting.

[finway]

For now , mining business is focusing on "Generating Coins",
when it reduces again and again,
mining business will focus on collecting "Transaction fees".
Problem solved.

[avivz]

It would certainly change the incentives of miners to accept transactions. A miner will have to add some value to the block otherwise no one else will build on it. He might also reject low fee transactions to put upward pressure on fee prices. These two opposing forces will set a market price for fees, which may also address this problem: https://bitcointalk.org/index.php?topic=6284.200

But then wouldn't a miner still have a dis-incentive to propagate information on transactions? If I can keep transactions to myself, and add them to a block that I generated (and thereby increase the block's value compared to other blocks my competitors may be producing), others will prefer to build upon my block and may even abandon ones that were found earlier (that offered lower rewards).

I'm not sure if I can clearly see the optimal behavior of a miner under such circumstances, but this is certainly food for thought.

[nmat]

But then wouldn't a miner still have a dis-incentive to propagate information on transactions? If I can keep transactions to myself, and add them to a block that I generated (and thereby increase the block's value compared to other blocks my competitors may be producing), others will prefer to build upon my block and may even abandon ones that were found earlier (that offered lower rewards).

I'm not sure if I can clearly see the optimal behavior of a miner under such circumstances, but this is certainly food for thought.

I am more worried about the no-incentive for clients than with the dis-incentive for miners. With a good network of forwarding nodes, everybody will know about most transactions and miners won't really profit much from holding them. There's a slim chance that they will find the next block anyway. Running a network with few forwarding nodes might be a problem though because the network becomes more vulnerable to a few attacks described by DeathAndTaxes a few pages ago.

[becoin]

I am more worried about the no-incentive for clients than with the dis-incentive for miners.

I'm worried by my own observations too. People start the bitcoin client if they have to send/receive bitcoins and once recent blocks are downloaded they stop and exit.

Our society is based on a voting system, one man one vote. No one should be encourage to purchase votes. Unfortunately, this is exactly what is happening with pool mining. Mining pools are incentivised to purchase workers' votes. Bitcoin is hostage of a dozen mining pools.

If changes in the bitcoin protocol need to be made that will discourage pool mining, how would you convince mining pools to assist you do something that is against their interest?

[P4man]

Meh, you dont usually vote laws, you vote for representatives. Pools would be like that. And its easier to change pools than representatives

[pointbiz]

I guess my point was missed...

I didn't read the paper just the summary but if you read the words of Satoshi he explains that it's not a trivial problem to collect fees for transactions and the approach the paper authors take is naive (sorry). I'm glad some people at MS research are interested in Bitcoin but Satoshi has a mental muscle the rest of us can only wish for.

Next you'll be researching how to re-introduce lost coins because you don't understand the divisibility of the currency units.

The incentive to broadcast and listen for transactions and blocks is to make sure you KNOW everything that everyone else KNOWS. If you hoard information it becomes stale and worthless.

[gmaxwell]

I guess my point was missed...

I didn't read the paper just the summary but if you read the words of Satoshi he explains that it's not a trivial problem to collect fees for transactions and the approach the paper authors take is naive (sorry). I'm glad some people at MS research are interested in Bitcoin but Satoshi has a mental muscle the rest of us can only wish for.

This isn't really fair.   And the tree-rewards system is interesting on its own merit, even if it never turns out to be something useful for bitcoin.  Complaining about this is kinda like complaining that double-geometric payout schemes for mining pools are pointless because there are non-score based ways around the problems proportional pools have.

[becoin]

Meh, you dont usually vote laws, you vote for representatives.

We do! It is called referendum (aka plebiscite).

A referendum (also known as a plebiscite or a vote on a ballot question) is a direct vote in which an entire electorate is asked to either accept or reject a particular proposal. This may result in the adoption of a new constitution, a constitutional amendment, a law, the recall of an elected official or simply a specific government policy. It is a form of direct democracy.

Voting for representatives is a form of centralization. Decentralization means direct democracy. Never forget, bitcoin is about decentralization not centralization!

[becoin]

I'm glad some people at MS research are interested in Bitcoin but Satoshi has a mental muscle the rest of us can only wish for.

My respect for the idea and initial implementation, but Satoshi (whoever he/they are) missed many things. One thing they missed is that every monetary system is an economy of its own and that every economy is based upon a system of incentives. Transaction fees and how they are defined is one weak spot in bitcoin protocol! And this is a fundamental question.

[DeathAndTaxes]

The incentive to broadcast and listen for transactions and blocks is to make sure you KNOW everything that everyone else KNOWS. If you hoard information it becomes stale and worthless.

So why is the number of nodes dropping?  Obviously there isn't "enough" incentive.

[HostFat]

Has Gavin left a message about this topic somewhere?

[Gavin Andresen]

Has Gavin left a message about this topic somewhere?

No, I've been busy. Although I have in the past said that I'm worried about long-term incentives for relaying transactions (and am not worried at all about the block reward dropping and being replaced by fees).

I skimmed the paper, and I'm really pleased to see very smart people thinking hard about the incentive structures built-in to Bitcoin. I think most people see all the digital signatures and peer-to-peer networking technology but miss that much of the brilliance of Bitcoin is how the incentives are designed.

Overall, I think the paper is most valuable as a demonstration of how to prove that a particular solution to the problem could work-- whether or not the particular solution the authors propose (rewarding the relaying nodes) is the "best" solution I'm not sure -- there are lots of dimensions of 'goodness' here -- lowest cost, fastest transaction confirmations, easiest to implement, most compatible with the network we have now, etc.

A while ago I proposed another potential solution:  have relaying clients drop their connection to 'greedy' nodes. If you have a node that sends you new blocks but isn't relaying you new transactions, maybe drop your connection to it and ban it's IP address from re-connecting to you for a while. Or maybe don't relay (or relay after delaying a couple of minutes) new-block messages that you first see from that node.  The idea is that a mild dis-incentive should be sufficient to encourage nodes to do the right thing and relay all valid transactions and blocks.

Figuring out "isn't relaying you new transactions" in a spoof-proof way would be a little tricky-- you want to see real transactions, not miner-generated "I'm pretending to be a good network citizen" transactions. A scheme where you relay transactions to half of your peers and then monitor the other half to see if you receive the transaction back from them should work to detect nodes that are relaying many-fewer-than-normal transactions or blocks.


I've also said repeatedly in the past I'd like to see more diversity in the networks used to transmit bitcoin transactions/blocks (with bridges between them so we're all working on the same block-chain). There doesn't have to be just one right answer to this problem, and I would love to see people simulate or experiment with variations on the existing network protocol or radically different protocols.

[finway]

Punish the bad guy? 

[kazoo]

As with all things bitcoin, I am hesitant to chime up in the discussion without doing more research, but I have also always had the feeling that transaction processing is not properly incentivized. There are (at least) two major operations in the bitcoin network: currency generation and transaction processing. I think the generation part is remarkably viable, and well conceived, especially in this nascent stage.

But while transaction processing costs money to perform, it does not seem to be incentivized properly. While there are concrete rewards for generating currency, there is no corresponding concrete and immediate reward for processing the transaction, and voting in transaction approvals. This might be a real obstacle in general acceptance, and some of the root cause behind all of the "so where can I use this" kind of questions we hear all the time.

In this case, I believe that these researchers seem to have found a structural imperfection causing a block where there should be a flow. The health of this community really depends on identifying all such cases.

[Mageant]

IMHO we can keep this in mind but we shouldn't fix it before it actually has become a problem.

[avivz]

Has Gavin left a message about this topic somewhere?

Overall, I think the paper is most valuable as a demonstration of how to prove that a particular solution to the problem could work-- whether or not the particular solution the authors propose (rewarding the relaying nodes) is the "best" solution I'm not sure -- there are lots of dimensions of 'goodness' here -- lowest cost, fastest transaction confirmations, easiest to implement, most compatible with the network we have now, etc.

A while ago I proposed another potential solution:  have relaying clients drop their connection to 'greedy' nodes. If you have a node that sends you new blocks but isn't relaying you new transactions, maybe drop your connection to it and ban it's IP address from re-connecting to you for a while. Or maybe don't relay (or relay after delaying a couple of minutes) new-block messages that you first see from that node.  The idea is that a mild dis-incentive should be sufficient to encourage nodes to do the right thing and relay all valid transactions and blocks.

(I'm one of the co-authors of the paper)
The paper is an academic work (submitted to a conference in theoretical computer science which is heavily mathematical) and so naturally we had a great deal of focus on the proofs. From a practical aspect we are aware that the scheme we suggest has some costs (such as inflated block sizes) and we certainly wouldn't presume to have the definitive answer. We've entertained other incentive schemes as we were writing our paper, and we are stlll exploring some of the alternatives.

We've also thought a bit about the tit-for-tat incentives you've suggested (relaying transactions only to nodes that relay transactions to you) and that seems like it may work too. One of the potential hurdles is that many times two connected nodes have different gains and losses from relaying a transaction. For example: a small miner that is connected to node that controls more processing power is at a disadvantage. Every time the small miner would relay a message it would be adding a great deal of competition, and thus potentially loosing more. On the other hand, more powerful miners (e.g., mining pools) may still manage to learn about enough transactions by sharing information internally and would not relay a lot externally.  

[DeathAndTaxes]

But while transaction processing costs money to perform, it does not seem to be incentivized properly. While there are concrete rewards for generating currency, there is no corresponding concrete and immediate reward for processing the transaction, and voting in transaction approvals. This might be a real obstacle in general acceptance, and some of the root cause behind all of the "so where can I use this" kind of questions we hear all the time.

You seem to equate mining = generating bitcoins when that isn't true.  Mining = hashing transactions into irreversable* blocks is part of transaction processing.

I do agree that the other parts seem to be neglected.

The entire processing chain involves
1) Validating & relaying transactions
2) Hashing transactions into blocks
3) Validating & relaying blocks. 

Currently only step #2 is compensated but it IS part of transaction processing.





* well technically very difficult to reverse

[Steve]

I don't see the problem with incentives for relaying transactions.  Every non mining node has a very strong incentive to relay transactions.  When you are the recipient of bitcoins, you need to make an assessment of whether that transaction is marketable to the rest of the network.  To do that effectively, you need to be as in sync with the rest of the network as possible.  That means not only receiving transactions, but also relaying them (because, you never know, you might be the first and only one to receive a given transaction…if you don't relay it, you risk getting out of sync and thinking later transactions that you see are valid when the rest of the network does not agree with you).

[dree12]

I don't see the problem with incentives for relaying transactions.  Every non mining node has a very strong incentive to relay transactions.  When you are the recipient of bitcoins, you need to make an assessment of whether that transaction is marketable to the rest of the network.  To do that effectively, you need to be as in sync with the rest of the network as possible.  That means not only receiving transactions, but also relaying them (because, you never know, you might be the first and only one to receive a given transaction…if you don't relay it, you risk getting out of sync and thinking later transactions that you see are valid when the rest of the network does not agree with you).

(emphasis mine)

That part isn't valid because if the blockchain never accepts the transaction, it never existed. Your client wouldn't think it existed at all because it follows the blockchain. To clarify, a client can simple delete the transaction and nothing would be out-of sync. If the transaction does get included, your blockchain will have it.

[John Tobey]

I've read the simplified summary (thanks).  The issue, if one exists, is certainly not worth changing the "protocol" (block acceptance rules).

Users want their transactions to get into blocks.  So they pay miners (perhaps indirectly) to include them.  Problem solved!  The payment need not be in the form of transaction fees.  Matching currency users with miners is far beyond the proper scope of block validation.  Ask Mr. Market for a solution.  Hint: entrepreneur talks to pool ops and users, develops service, takes a cut.

Or did I misread it?

[Steve]

I don't see the problem with incentives for relaying transactions.  Every non mining node has a very strong incentive to relay transactions.  When you are the recipient of bitcoins, you need to make an assessment of whether that transaction is marketable to the rest of the network.  To do that effectively, you need to be as in sync with the rest of the network as possible.  That means not only receiving transactions, but also relaying them (because, you never know, you might be the first and only one to receive a given transaction…if you don't relay it, you risk getting out of sync and thinking later transactions that you see are valid when the rest of the network does not agree with you).

(emphasis mine)

That part isn't valid because if the blockchain never accepts the transaction, it never existed. Your client wouldn't think it existed at all because it follows the blockchain. To clarify, a client can simple delete the transaction and nothing would be out-of sync. If the transaction does get included, your blockchain will have it.

Nodes want to be in sync with the rest of the network, even for transactions that have not yet made it into a block.  The reason is that with such knowledge, you can make a risk assessment regarding whether a given transaction is likely to make it into the block chain.  Again, I assert that there is plenty of incentive to relay transactions.

[Luke-Jr]

More FUD: http://www.theregister.co.uk/2011/11/15/bitcoin_flaw/

Perhaps the Microsoft research team could provide a clarification that this isn't a present issue and can easily be fixed in the future, for linking from the main page on bitcoin.org?

[paraipan]

More FUD: http://www.theregister.co.uk/2011/11/15/bitcoin_flaw/

Perhaps the Microsoft research team could provide a clarification that this isn't a present issue and can easily be fixed in the future, for linking from the main page on bitcoin.org?

+1, or some ppl would start to think the paper was written to push some obscure agenda... me included

[dree12]

That means not only receiving transactions, but also relaying them (because, you never know, you might be the first and only one to receive a given transaction…if you don't relay it, you risk getting out of sync and thinking later transactions that you see are valid when the rest of the network does not agree with you).

(emphasis mine)

That part isn't valid because if the blockchain never accepts the transaction, it never existed. Your client wouldn't think it existed at all because it follows the blockchain. To clarify, a client can simple delete the transaction and nothing would be out-of sync. If the transaction does get included, your blockchain will have it.

Nodes want to be in sync with the rest of the network, even for transactions that have not yet made it into a block.  The reason is that with such knowledge, you can make a risk assessment regarding whether a given transaction is likely to make it into the block chain.  Again, I assert that there is plenty of incentive to relay transactions.

I might be being a little unclear (or you are ), but what I meant is that the average node isn't a merchant: they have no need to relay transactions that don't involve them. No risk assessment needs to be made, as even if you do relay a transaction this isn't a guarentee it exists.

[paraipan]

That means not only receiving transactions, but also relaying them (because, you never know, you might be the first and only one to receive a given transaction…if you don't relay it, you risk getting out of sync and thinking later transactions that you see are valid when the rest of the network does not agree with you).

(emphasis mine)

That part isn't valid because if the blockchain never accepts the transaction, it never existed. Your client wouldn't think it existed at all because it follows the blockchain. To clarify, a client can simple delete the transaction and nothing would be out-of sync. If the transaction does get included, your blockchain will have it.

Nodes want to be in sync with the rest of the network, even for transactions that have not yet made it into a block.  The reason is that with such knowledge, you can make a risk assessment regarding whether a given transaction is likely to make it into the block chain.  Again, I assert that there is plenty of incentive to relay transactions.

I might be being a little unclear (or you are ), but what I meant is that the average node isn't a merchant: they have no need to relay transactions that don't involve them. No risk assessment needs to be made, as even if you do relay a transaction this isn't a guarentee it exists.

sorry to interrupt, i just read your reply 4 times to understand something dree12...

...average node isn't a merchant...

= wrong assumption, 50% of non miner nodes are "merchants" at any given time. Me accepting coins for a sale or service for example

...even if you do relay a transaction this isn't a guarentee it exists.

= client-servers are validating transactions against the blockchain before relaying them, so your point is... ?

As days pass i just realize Satoshi left us with more than a nice little experiment to play with  

[pointbiz]

Let's assume there will always be those who connect and broadcast transactions to other nodes as a form of charity. Then there are known mining pools connected with known charity nodes. Miners (including laptop GPUs) who auto-rotate GPU power to different pools. Transactions are being freely broadcast between these nodes (and everyone else... let's call them wallet nodes).

That describes the network today and transactions normally get into the next one or two blocks after being broadcast.  If in the future there are unacceptable delays in your transaction getting into a block. A voluntary overlay protocol can be added without any change to the existing bitcoin protocol.

The Protocol:
Bitcoin transactions can be arranged such that a 'special payment' can be made to one known mining pool donation address, on top of whatever amount is being sent to the recipient bitcoin address; and on top of the transaction fee attached that goes to the node/pool who solves the block. This 'special payment' will act as an incentive for the known mining pool to broadcast the transaction to the charity nodes. Since other mining pools and wallet nodes are connected with charity nodes then they will discover the transaction as well. One can intentionally initiate a double spend race between two versions of the same transaction each with a different 'special payment' mining pool recipient.


Thoughts?

[phatsphere]

Thoughts?

Personally, I think it's a very bad idea to start tackling a problem that doesn't even exist yet. Right now, mining pools don't act evil in a way that degrades the entire network, because  it would shrink the confidence into this whole experiment even more and they get less out of all this, too. Please, let's focus on things like wallet safety, UX, network stability/scalability and so on, especially on problem that exist right now.

[dree12]

That means not only receiving transactions, but also relaying them (because, you never know, you might be the first and only one to receive a given transaction…if you don't relay it, you risk getting out of sync and thinking later transactions that you see are valid when the rest of the network does not agree with you).

(emphasis mine)

That part isn't valid because if the blockchain never accepts the transaction, it never existed. Your client wouldn't think it existed at all because it follows the blockchain. To clarify, a client can simple delete the transaction and nothing would be out-of sync. If the transaction does get included, your blockchain will have it.

Nodes want to be in sync with the rest of the network, even for transactions that have not yet made it into a block.  The reason is that with such knowledge, you can make a risk assessment regarding whether a given transaction is likely to make it into the block chain.  Again, I assert that there is plenty of incentive to relay transactions.

I might be being a little unclear (or you are ), but what I meant is that the average node isn't a merchant: they have no need to relay transactions that don't involve them. No risk assessment needs to be made, as even if you do relay a transaction this isn't a guarentee it exists.

sorry to interrupt, i just read your reply 4 times to understand something dree12...

...average node isn't a merchant...

= wrong assumption, 50% of non miner nodes are "merchants" at any given time. Me accepting coins for a sale or service for example

No, if Bitcoin were to be widely used most non-miner nodes would have jobs. There is no incentive to relay transactions that don't concern them at all.

My point is that relaying a transaction is useless if it doesn't concern you. If those txs get included in the chain, so be it - you haven't lost anything. Otherwise, you delayed a transaction not belonging to you, making yours get comfirmed faster.

[paraipan]

.....................................................................
No, if Bitcoin were to be widely used most non-miner nodes would have jobs. There is no incentive to relay transactions that don't concern them at all.

My point is that relaying a transaction is useless if it doesn't concern you. If those txs get included in the chain, so be it - you haven't lost anything. Otherwise, you delayed a transaction not belonging to you, making yours get comfirmed faster.

yeah, guess you could tell that to RIP protocol creators too, or all the women in the world that like gossiping just for the sport.
MS research ppl forgot that we're social beings and the bitcoin software actually mimics that on the network. A single node will not have to relay all possible transactions ever, only the ones it hears from it's "nearby" neighbors.
I would personally keep reading on sociology books or network protocols to make a good start in bitcoin

[DeathAndTaxes]

.....................................................................
No, if Bitcoin were to be widely used most non-miner nodes would have jobs. There is no incentive to relay transactions that don't concern them at all.

My point is that relaying a transaction is useless if it doesn't concern you. If those txs get included in the chain, so be it - you haven't lost anything. Otherwise, you delayed a transaction not belonging to you, making yours get comfirmed faster.

yeah, guess you could tell that to RIP protocol creators too, or all the women in the world that like gossiping just for the sport.
MS research ppl forgot that we're social beings and the bitcoin software actually mimics that on the network. A single node will not have to relay all possible transactions ever, only the ones it hears from it's "nearby" neighbors.
I would personally keep reading on sociology books or network protocols to make a good start in bitcoin

nodes aren't social.  No human is sitting behind the screen going "oh wow look at that transaction".  Hell most users are completely unaware of the fact that transactions are even being relayed.  Thus just like most users don't stay logged into Paypal 24/7/365 they won't feel the need to run client all the time or even run a client at all.

[paraipan]

.....................................................................
No, if Bitcoin were to be widely used most non-miner nodes would have jobs. There is no incentive to relay transactions that don't concern them at all.

My point is that relaying a transaction is useless if it doesn't concern you. If those txs get included in the chain, so be it - you haven't lost anything. Otherwise, you delayed a transaction not belonging to you, making yours get comfirmed faster.

yeah, guess you could tell that to RIP protocol creators too, or all the women in the world that like gossiping just for the sport.
MS research ppl forgot that we're social beings and the bitcoin software actually mimics that on the network. A single node will not have to relay all possible transactions ever, only the ones it hears from it's "nearby" neighbors.
I would personally keep reading on sociology books or network protocols to make a good start in bitcoin

nodes aren't social.  No human is sitting behind the screen going "oh wow look at that transaction".  Hell most users are completely unaware of the fact that transactions are even being relayed.  Thus just like most users don't stay logged into Paypal 24/7/365 they won't feel the need to run client all the time or even run a client at all.

sometimes i can't manage to explain things in a simple manner, imagine the nodes of the software as the social beings doing the "oh wow look at that transaction" all the time not the humans behind them, they pass each other up to date "gossip" hoping some hard working "miner" will confirm it so they can take it for granted. We do it all the time in our day to day lives, pass gossip between each other until it's "confirmed" in mass-media.
Pls don't compare paypal with bitcoin... it's a different system altogether

edit: after little research of my own i just found out that we have one of the most capable researchers at MS are looking for fixes into bitcoin "flaws". Aviv Zohar is even bragging about it, i just share this with all of you with no incentive whatsoever

Just got my five minutes of SlashDot fame along with +Shahar Dobzinski, +Sigal Oren, and +Moshe Babaioff. We are on the front page!

Researchers Locate Flaw In Bitcoin Protocol - Slashdot
An anonymous reader writes "Researchers at Microsoft Research and Cornell identified a potential flaw in Bitcoin's transaction propagation. In a recent paper they show how miner nodes in the Bitcoin n...

[Steve]

No, if Bitcoin were to be widely used most non-miner nodes would have jobs. There is no incentive to relay transactions that don't concern them at all.

Incorrect.  You never know what transactions might precede a transaction that sends bitcoins to an address you control.  Therefore, you are potentially interested in every transaction and have a need to stay in sync with the rest of the network.  If you control address C and there is a sequence of two transactions, A->B then B->C and you don't relay the first one, you increase the chance that the network settles on a transaction that conflicts with A->B and you'll miss out on B->C (or worse, you'll think it's a valid transaction when the rest of the network has already rejected it).

[dree12]

No, if Bitcoin were to be widely used most non-miner nodes would have jobs. There is no incentive to relay transactions that don't concern them at all.

Incorrect.  You never know what transactions might precede a transaction that sends bitcoins to an address you control.  Therefore, you are potentially interested in every transaction and have a need to stay in sync with the rest of the network.  If you control address C and there is a sequence of two transactions, A->B then B->C and you don't relay the first one, you increase the chance that the network settles on a transaction that conflicts with A->B and you'll miss out on B->C (or worse, you'll think it's a valid transaction when the rest of the network has already rejected it).

The default client only sends transactions with at least one confirmation, so this is an entire non-issue.

[blueadept]

The default client only sends transactions with at least one confirmation, so this is an entire non-issue.

The default client only originates transactions where the inputs have at least one confirmation. It relays all transactions that follow the rules.

[dree12]

The default client only sends transactions with at least one confirmation, so this is an entire non-issue.

The default client only originates transactions where the inputs have at least one confirmation. It relays all transactions that follow the rules.

This is what I meant. You do not need to worry about a transaction until it acually becomes included in a block.

[paraipan]

The default client only sends transactions with at least one confirmation, so this is an entire non-issue.

The default client only originates transactions where the inputs have at least one confirmation. It relays all transactions that follow the rules.

This is what I meant. You do not need to worry about a transaction until it actually becomes included in a block.

lol, didn't really want to post but this is to funny to resist... q: how would you relay a sole transaction when it's part of a block ?

[blueadept]

The default client only sends transactions with at least one confirmation, so this is an entire non-issue.

The default client only originates transactions where the inputs have at least one confirmation. It relays all transactions that follow the rules.

This is what I meant. You do not need to worry about a transaction until it actually becomes included in a block.

lol, didn't really want to post but this is to funny to resist... q: how would you relay a sole transaction when it's part of a block ?

No, I get what he's saying now. If you're looking to use the output from a transaction before that transaction is included in a block, you can't do that with the mainline client; therefore, the mainline client has no incentive to relay non-confirmed transactions.

But if you're using the mainline client already, you're relaying. You can modify it to not relay, but you could just as easily modify it to originate transactions with unconfirmed outputs as their inputs.

[dree12]

The default client only sends transactions with at least one confirmation, so this is an entire non-issue.

The default client only originates transactions where the inputs have at least one confirmation. It relays all transactions that follow the rules.

This is what I meant. You do not need to worry about a transaction until it actually becomes included in a block.

lol, didn't really want to post but this is to funny to resist... q: how would you relay a sole transaction when it's part of a block ?

My statement is simply that you do not need to relay a transaction not involving you. This was in response to Steve's point that you need to know the "future ledger" in case of it concerning you later, and my responce was that you can worry about it once it is in a block.

The default client only sends transactions with at least one confirmation, so this is an entire non-issue.

The default client only originates transactions where the inputs have at least one confirmation. It relays all transactions that follow the rules.

This is what I meant. You do not need to worry about a transaction until it actually becomes included in a block.

lol, didn't really want to post but this is to funny to resist... q: how would you relay a sole transaction when it's part of a block ?

No, I get what he's saying now. If you're looking to use the output from a transaction before that transaction is included in a block, you can't do that with the mainline client; therefore, the mainline client has no incentive to relay non-confirmed transactions.

But if you're using the mainline client already, you're relaying. You can modify it to not relay, but you could just as easily modify it to originate transactions with unconfirmed outputs.

No, I'm saying there is no need to know the output until it is included in a block.

[pointbiz]

There are people at Microsoft who are paid full time to do research. Why didn't they discover Bitcoin? There was 7 years of opportunity and the bitgold proposal was released in 2005. That would have been the greatest in-game currency system for MS who is one of the biggest video game companies on the planet.

Their research is being painted as 'discovering a fatal flaw' instead of the reality of 'a bad suggestion to try and improve the bitcoin protocol'. I posted a back of the envelope idea that IMHO would work better than their proposal if bitcoin were to encounter the problem they suggest will happen. I suggest the folks at MS don't understand P2P.

Let me ask a related question, what is the incentive for nodes to broadcast blocks that do not directly include a BTC transfer to an address they posess?

Specifically, there are the incentives to have a P2P currency. The incentive to keep the value of coins you possess. The incentive to know the truth and influence the truth and remotely store the truth on the network. The incentive to not be discovered to be behaving unfairly. These incentives are weighed with the incentive to hoard a transaction.

Perhaps they can go back to the drawing board and work out a math model designed for a graph that matches the graph of the bitcoin network.

Regardless of the intention of the authors of the paper, the premise of the paper is being used as FUD.

[kazoo]

But while transaction processing costs money to perform, it does not seem to be incentivized properly. While there are concrete rewards for generating currency, there is no corresponding concrete and immediate reward for processing the transaction, and voting in transaction approvals. This might be a real obstacle in general acceptance, and some of the root cause behind all of the "so where can I use this" kind of questions we hear all the time.

You seem to equate mining = generating bitcoins when that isn't true.  Mining = hashing transactions into irreversable* blocks is part of transaction processing.

I do agree that the other parts seem to be neglected.

The entire processing chain involves
1) Validating & relaying transactions
2) Hashing transactions into blocks
3) Validating & relaying blocks. 

Currently only step #2 is compensated but it IS part of transaction processing.

Yes, I agree I did seem to be making it appear as that was my understanding. I think I have a bit more refined notion of mining, but probably not by much.

My point was to differentiate mining and transaction processing kinds of activities, even though these are intertwined. So I attempt to draw a bright line, where there really is none.

The reason for trying to even make this distinction is that my impression is that there are (or were) a lot of people interested in getting into mining, while transaction processing has a lot fewer players. Mining is much simpler, requiring less sophistication and design than improving transaction processing. So we see a lot more effort in mining, and less in convenience and acceptance. If there were even a tenth as much progress in building transaction infrastructure as there has been in mining, bitcoins would be more commonly used than they are now.

[finway]

If there were even a tenth as much progress in building transaction infrastructure as there has been in mining, bitcoins would be more commonly used than they are now.

Agree with you.

[notme]

If there were even a tenth as much progress in building transaction infrastructure as there has been in mining, bitcoins would be more commonly used than they are now.

Agree with you.

Development takes time.  I've been working on a project part time for about 9 months that will accept bitcoin payments from day one.  I've switched to full time on it but there's still a few months to go before we'll be ready for launch.  Most people who know about bitcoin heard about it more recently than me, so I can only assume they are a little further behind unless they already were working on a project they could easily add bitcoin to.

[avivz]

Hi everyone,

I'm one of the authors of the paper being discussed here.

Following suggestions from some people here in the forum and elsewhere, and in an attempt to clarify some of the points we make in the paper we've posted a summary of the paper aimed at the Bitcoin community. We hope this helps understand our paper a little better, and that this balances some of the more sensational headlines that were out there regarding our work.

http://research.microsoft.com/en-us/people/avivz/bitcoin_red_balloons_summary.aspx

[casascius]

We offer several variants of the payment scheme. Here is one such variant:

The initiating node offers a fee of x Bitcoins (x can be less than 1 Bitcoin). Half of the fee will be used to pay the miner that eventually manages to authorize the block. The rest will be divided by nodes on the path to that miner. The initiating node additionally picks the number of hops the transaction will be allowed to propagate (let’s call this H). Nodes that are more than H hops away will not be paid at all (and will probably not distribute further). This limitation on propagation seems strange but is really at the heart of the incentive scheme (Usually a small number of hops is sufficient to reach large portions of the network if it is well connected).

I see this as a non-starter, because the resources (disk, bandwidth) required to record all of this splitting of the fee will actually be multiple times more than the original transaction, a resource cost imposed on all nodes on the entire network.  Because instead of recording one entry in the block chain, now you're recording five or ten.

What would be a realistic, practical, nobrainer solution that I am sure will quickly be thought of if this ever becomes a problem, is a few honest nodes with a lot of bandwidth and an interest in the success of Bitcoin as a whole, will publish their IP's and say "Connect to me".  You as a client can connect to as many nodes as you want, but you only really need one well-connected node to talk to the majority of the network, and then...zzzz....business as usual.

I am enthusiastic enough about Bitcoin to be willing to run one, and I have the resources to run one myself, and I am just one guy with far less than 1% of the total bitcoins out there.  It would be drop dead simple too: 1) set up a machine, 2) run bitcoin, 3) publish the IP.  Surely I can't be the only person out there who would be so "altruistic" as to do this.

If you really want to write a paper on a real weakness of Bitcoin as currently implemented, what you really should pursue is the fact that bitcoin's resource consumption increases exponentially as transaction volume increases linearly, and that it's likely to see a scenario where it bursts in popularity for some reason and then suddenly becomes almost completely unusable (Gnutella style) because it is being crushed under its own weight.  Its only means of survival would be to require high fees for transactions so all but the largest transactions would become prohibitive (the same way that fed wires are great for buying a house, but not soda pop), and then become the backbone for a bunch of smaller private payment systems that merely use Bitcoin as backing and as a method to settle aggregated transactions between one another.  This could really happen, and few would disagree.

[avivz]

What would be a realistic, practical, nobrainer solution that I am sure will quickly be thought of if this ever becomes a problem, is a few honest nodes with a lot of bandwidth and an interest in the success of Bitcoin as a whole, will publish their IP's and say "Connect to me".  You as a client can connect to as many nodes as you want, but you only really need one well-connected node to talk to the majority of the network, and then...zzzz....business as usual.

Why isn't the same argument of "relying on altruists" applied to mining as well? We can take your line of thinking and ask oruselves "Why pay miners"? After all, a small bunch of people interested in the currency will contribute all the resources one needs to verify transactions.

The problem with this argument is that if transaction authentication is left in the hands of a few, they can exploit the system in order to make money. The same applies to transaction propagation: If a few nodes control the flow of information to the entire miner network they can exploit the system for their own benefits.

Bitcoin's great leap is that it incentivizes many miners that keep tabs on each other. We simply argue that it should similarly incentivize a large diversity of transaction distribution channels. Just like anyone can make money by mining, we think that everyone should be able to make money from transaction propagation. This inherently breaks any possible monopoly.

It's true that the solution we offer is not without costs. Most of the increase in block sizes is due to the fact that we esentially "micro-pay" each node for each successful transaction relay, and each payment is saved individually in the blocks. In contrast to that, mining is easier to reward -- only one miner per block. I suspect that it's not impossible to pay for several relaying actions at once as well, and that the associated increase in block size can be reduced (perhaps only reward nodes for relaying in some probabilistic manner using a form of lottery and then there will be less need to remember entire referal chains).

If you really want to write a paper on a real weakness of Bitcoin as currently implemented, what you really should pursue is the fact that bitcoin's resource consumption increases exponentially as transaction volume increases linearly, and that it's likely to see a scenario where it bursts in popularity for some reason and then suddenly becomes almost completely unusable (Gnutella style) because it is being crushed under its own weight. 

I don't see where there is an exponential increase in resource consumption from a linear increase in volume. Could you elaborate?

[Steve]

If you really want to write a paper on a real weakness of Bitcoin as currently implemented, what you really should pursue is the fact that bitcoin's resource consumption increases exponentially as transaction volume increases linearly, and that it's likely to see a scenario where it bursts in popularity for some reason and then suddenly becomes almost completely unusable (Gnutella style) because it is being crushed under its own weight. 

I don't see where there is an exponential increase in resource consumption from a linear increase in volume. Could you elaborate?

I don't see it either…the overall amount of work being performed for a given transactions increases as the number of nodes increases, but it's not exponential.  The mesh topology of node inter-connections means that there is an exponential increase in a subset of the communications protocol, however INV messages are quite small.  The work the network performs as a whole to validate a transaction is also not exponential as the number of transactions increases (given a constant number of nodes in the network).

[DeathAndTaxes]

I am enthusiastic enough about Bitcoin to be willing to run one, and I have the resources to run one myself, and I am just one guy with far less than 1% of the total bitcoins out there.  It would be drop dead simple too: 1) set up a machine, 2) run bitcoin, 3) publish the IP.  Surely I can't be the only person out there who would be so "altruistic" as to do this.

At today transaction volume levels sure it is a negligible cost however to validate and relay transaction at something like Paypal level volume would require significant resources. 

Paypal has peak daily processing of about 100 tps.  VISA is roughly 40x as large so just keep that in mind.

Currently 1 Bitcoin transaction is ~0.5KB but with rise of contracts one would expect transactions to become more complex.  Say in future the average transaction is 2KB.  100 tps * 2KB = 200KB/s or 1600 kps or 1.6Mbps to a single peer.  To maintain connections to just 20 peers would require at peak 32Mbps.  To maintain connections to 100 peers would require 160Mbps.

A modern quad-core CPU can validate about 80 transactions per second however the node needs to also re-verify blocks so it potentially verifies each transaction twice making throughput 40 tps    100+ transactions per second would thus require multiple CPUs (not multiple cores either server grade quad CPU systems or multiple systems).  VISA scale transaction volume would require either an entire datacenter of servers or some heavy GPU acceleration.  Imagine mining 24/7/365 with all the heat, noise and electrical cost that involves (plus 1 million fold increase in bandwidth requirements) except you would be just taking a 100% loss on that because it is uncompensated and only miners get compensated for putting transactions in blocks.

At Paypal level transaction volume a block would be about 120MB.  At VISA scale transaction volume a block would be 4.8GB.  One years worth of block chain would require 6TB and 252TB of storage respectively.

So yeah setting up a node for the common good when tps is <1 is one thing.  Doing it without compensation where it requires real resources is another.  Especially under such a scenario miners would be well compensated for their work, work that would be impossible without the compensation free transaction routing.

Before I get flamed: this isn't to indicate I think Bitcoin is dead or can't scale however putting 100% of compensation on one component of the network and making the rest of it free simply means people will be dedicated to pursuing the portion that is compensated.  It is an unsustainable dynamic.  Luckily we have plenty of time to consider the issue as it is likely decades before Bitcoin even reaches Paypal level of acceptance.

[Steve]

The default client only originates transactions where the inputs have at least one confirmation. It relays all transactions that follow the rules.

This is what I meant. You do not need to worry about a transaction until it actually becomes included in a block.

That's true of the default client, but not true of all nodes and is a perfectly valid thing to do (and there are a number of cases I can think of where you'd want/need to do this).  I think overall what I would say is that the cost of relaying a transaction is tiny (I expect the vast majority of the time you're just passing along a small INV message… but I don't have stats to back that up) and all things being equal, staying in sync with the network and having accurate intelligence about what is happening far outweighs the small cost of relaying (especially for certain types of nodes).  But, even if you don't find that to be compelling, the small cost of relaying a transaction is tiny in comparison with the benefit it has for the network and by extension the value of bitcoin itself.  I still don't think there is an incentive problem here…even if all miners never forwarded fee bearing transactions, I don't think we'd have a problem.  

It may even be a simpler method of creating healthy market for transaction processing than the rube goldberg machinery that Microsoft proposes.  You could for example submit fee bearing transactions directly to the mining pools (who don't forward them)…you could create several different versions of a transaction, each with a different fee depending on what different pools are charging…the one that wins collects the fee and the other transactions are discarded (because they are conflicting).  You could also submit a zero fee version to the network at large..the pools would have to beat the rest of the network at large to collect their fee.

[Steve]

Before I get flamed: this isn't to indicate I think Bitcoin is dead or can't scale however putting 100% of compensation on one component of the network and making the rest of it free simply means people will be dedicated to pursuing the portion that is compensated.  It is an unsustainable dynamic.  Luckily we have plenty of time to consider the issue as it is likely decades before Bitcoin even reaches Paypal level of acceptance.

Of course, by that time, your average cell phone might have 200 TB of storage, capable of 20Gbps data communications, powered by nuclear fusion and cost less per month than your average fast food meal (but you'll still have to pay extra for text messaging).

[casascius]

Why isn't the same argument of "relying on altruists" applied to mining as well? We can take your line of thinking and ask oruselves "Why pay miners"? After all, a small bunch of people interested in the currency will contribute all the resources one needs to verify transactions.

Miners are providing a service: they're memorializing transactions in the block chain, which hardens them against double spending.  They don't have to do it.  If they refuse to, the transactions will sit unconfirmed.

The problem with this argument is that if transaction authentication is left in the hands of a few, they can exploit the system in order to make money. The same applies to transaction propagation: If a few nodes control the flow of information to the entire miner network they can exploit the system for their own benefits.

I believe the scenario of a "few" nodes controlling all the flow of information is highly unlikely to happen.  The vast majority of nodes aren't mining and have absolutely no incentive to withhold transactions.  They are just average joe schmoes running the Bitcoin client.  Each one of those links up to at least 8 peers.  So a swarm of 100,000 nodes could, for simplicity's sake, have 400,000 connections between them (100,000 * 8/2).  Fewer than 5% of those nodes are likely to be mining and would see any benefit to refusing to relay valid transactions.  The other 95% have no reason to run what amounts to a crippled client that contributes to network disruption with no benefit to them.  What's the odds that all of any given node's 8+ connections are going to coincidentally go to people who see an advantage to withholding transactions, and are doing it?  Pretty small, in my opinion.

Let's assume that in the future, running the client becomes infeasible and only miners run clients.  So, 100% of the nodes are miners and are refusing to relay transactions.  I, as someone who wants to execute a transaction, could easily send my transaction to each of them myself.  Just the same way your bank separately reports your history to Experian, Equifax, and TransUnion separately.  Given the a transaction size of 0.5 KB, it would be painless for my computer to submit that to a hundred different nodes if necessary.  They could go in UDP packets and be blasted out in the blind.

Bitcoin's great leap is that it incentivizes many miners that keep tabs on each other. We simply argue that it should similarly incentivize a large diversity of transaction distribution channels. Just like anyone can make money by mining, we think that everyone should be able to make money from transaction propagation. This inherently breaks any possible monopoly.

I don't believe that any of the developers would take this idea seriously because it comes with a large resource burden to solve a problem nobody (other than you guys, of course) believe exists.  If for every big transaction, we need to add (and relay) 9 little transactions just to make sure the miners make a penny, we have suddenly increased the resource cost tenfold, and imposed that increased cost upon every node.  It would be ridiculous and self-destructive.  Each transaction has the same resource cost on the network, whether big or small.  Miners don't want to collectively consume 4.5 KB of disk space - per miner - to make sure that a few of them collect a penny for the service of storing and forwarding a 0.5 KB transaction.

If you really want to write a paper on a real weakness of Bitcoin as currently implemented, what you really should pursue is the fact that bitcoin's resource consumption increases exponentially as transaction volume increases linearly, and that it's likely to see a scenario where it bursts in popularity for some reason and then suddenly becomes almost completely unusable (Gnutella style) because it is being crushed under its own weight.  

I don't see where there is an exponential increase in resource consumption from a linear increase in volume. Could you elaborate?

In my view, this is the elephant in the room - in comparison, the "miners won't want to relay" problem is like the distant comet that might or might not hit us.

Presently, all nodes must store and forward all transactions.  If twenty people start their own Bitcoin blockchain and sell each other some snacks, there will never be a problem.

But if scaled to the US size of Visa in its current form, where you could buy sodapop and candybars from vending machines with Bitcoin, every vending machine in the US would need to hear about any time any other vending machine anywhere in the US sold a snack, and would need a gadzookabyte hard drive to store it all.  This would obviously be unsustainable, since I don't know how many snacks are sold every second, but if I needed to download 0.5 KB over my internet connection each time anyone anywhere bought a snack, my internet connection would be useless.  The block chain as we know it now is absolutely unusable for wide scale micropayments - it's only usable that way today because there's plenty of as-yet unused room.  A four-lane highway with a couple cars per mile, if you will.

I refer to this as exponential growth by considering the total number of terabytes of disk space consumed and the total amount of bandwidth consumed in the aggregate passing all these transactions across all nodes, taking into account a vague assumption that transaction volume is correlated with the number of nodes on the network.  That, and the more people that enter the world of Bitcoin and the more potential counterparties they can pay with Bitcoin, the more transactions we will see per participant.

Scaled to Visa proportions, Bitcoin and its blockchain would be useful only the same way Fedwire is useful now - as the backbone that moves large amounts of funds between banks, and which is prohibitive for all but the largest everyday transactions.  The market (miners, that is) would price the transaction fee such that it would be senseless to add entries to the blockchain to buy sodapop - sort of like paying $20 to send a wire for a $1 soda.

On the other hand, everyday transactions with Bitcoin would be possible by using smaller private "banks" that internally accounted for all of the transactions amongst each other, and used Bitcoin as backing.  These wouldn't be cryptographic transactions, they would just be the same sort of internal transactions like me using PayPal to send part of my PayPal balance to you.  Presumably, there could be many such online payment services, with a standardized agreement to push small payments across one another's network and settle up later (the same way competing telcom carriers and long-distance companies handoff phone calls to one another).  The blockchain would only become involved when these internal banks needed to settle their aggregated obligations to one another, or in the event of large transactions where it makes sense for the transactor to cover the fee, just like a bankwire today.

I don't believe Bitcoin would need to get to Visa proportions to suddenly encounter its practical transaction volume limits.  If it suddenly became the preferred way to pay for online gambling, or to buy services to get around a national firewall, or access to adult material, it could find itself bumping up against that limitation rather quickly.

[Steve]

On the other hand, everyday transactions with Bitcoin would be possible by using smaller private "banks" that internally accounted for all of the transactions amongst each other, and used Bitcoin as backing.  These wouldn't be cryptographic transactions, they would just be the same sort of internal transactions like me using PayPal to send part of my PayPal balance to you.  Presumably, there could be many such online payment services, with a standardized agreement to push small payments across one another's network and settle up later (the same way competing telcom carriers and long-distance companies handoff phone calls to one another).  The blockchain would only become involved when these internal banks needed to settle their aggregated obligations to one another, or in the event of large transactions where it makes sense for the transactor to cover the fee, just like a bankwire today.

I'm pretty sure this is the way things will go.  The cost of transactions will rise to a point where there is an incentive to minimize the volume of block chain transactions.  I don't think using account based solutions is the best way however.  Instead, I think privately issued coins that have most of the properties of bitcoin, but don't require mining, is the way to go (transactions can just be verified with the issuer(s) rather than replicating a block chain everywhere).  This is similar to the role that gold serves today.  Using gold directly for transactions is cost prohibitive and thus people use various paper instruments for transactions while maintaining gold as reserves.  Debt (as well as equity and various forms of paper) are also a necessary complement to bitcoin to allow the effective monetary supply to expand & contract with market demand (which will also serve to help stabilize the value of bitcoin).

[cbeast]

There may be alterior motives to leave clients connected. Clients can be created that serve as postage, notary, courier tracking, etc. using Bitcoin for other functions besides simple transactions.

[MatthewLM]

Many users that download the software wont know how to disable relaying or care. Not a problem.

[DeathAndTaxes]

Many users that download the software wont know how to disable relaying or care. Not a problem.

Many users will never download the software or will only turn it on when they want to send or receive funds.  I think many people fail to understand the network, computational, and storage requirement of being an active node.  Not at this token <1 transaction per second but at any real sustained transaction volume.

When relaying starting requiring a couple hundred dollars a year in electricity, consumes terrabytes of disk space, produces more heat than a spaceheater, and results in your ISP throttling you due to 'excessive' bandwidth users will learn.  If they don't learn except to see more usage of 'lite wallets' and 'ewallets' and the number of nodes continue to shrink.

[MatthewLM]

Aren't people correct by pointing out that other p2p networks work just fine? And bitcoin works fine at the moment.

[notme]

Many users that download the software wont know how to disable relaying or care. Not a problem.

Many users will never download the software or will only turn it on when they want to send or receive funds.  I think many people fail to understand the network, computational, and storage requirement of being an active node.  Not at this token <1 transaction per second but at any real sustained transaction volume.

When relaying starting requiring a couple hundred dollars a year in electricity, consumes terrabytes of disk space, produces more heat than a spaceheater, and results in your ISP throttling you due to 'excessive' bandwidth users will learn.  If they don't learn except to see more usage of 'lite wallets' and 'ewallets' and the number of nodes continue to shrink.

I hope one day we can get back to paying for the bandwidth you want with the right to fully utilize it as well as resell a portion of it.  Dialup sucked for the speed, but the openness enforced by the regulations over phone lines is what allowed the rise of the Internet.  Bandwidth caps and government-enforced ISP level censorship will be it's downfall.

[casascius]

I hope one day we can get back to paying for the bandwidth you want with the right to fully utilize it as well as resell a portion of it.  Dialup sucked for the speed, but the openness enforced by the regulations over phone lines is what allowed the rise of the Internet.  Bandwidth caps and government-enforced ISP level censorship will be it's downfall.

I think we are already there.  Call your ISP and ask what service offerings they have for small office / home office.  You'll probably find that you can get access to any amount of bandwidth at a price.  Sure, you were probably expecting to consume unlimited bandwidth at max speed, pay the low residential rate and offer it to your neighbors, just like some kids go to daycare and assume access to lots of toys means the toys are all theirs.  Even under dialup, your phone company and ISP were free to enforce rules against constant connectivity, even if yours didn't.  Your ISP has got to make money to stay in business too, it's OK for them to set policies on shared resources.

[finway]

There's no incentive to OpenSource, Linux, Bitcoin.   

Not everything is paid to do.

[cbeast]

I hope one day we can get back to paying for the bandwidth you want with the right to fully utilize it as well as resell a portion of it.  Dialup sucked for the speed, but the openness enforced by the regulations over phone lines is what allowed the rise of the Internet.  Bandwidth caps and government-enforced ISP level censorship will be it's downfall.

I think we are already there.  Call your ISP and ask what service offerings they have for small office / home office.  You'll probably find that you can get access to any amount of bandwidth at a price.  Sure, you were probably expecting to consume unlimited bandwidth at max speed, pay the low residential rate and offer it to your neighbors, just like some kids go to daycare and assume access to lots of toys means the toys are all theirs.  Even under dialup, your phone company and ISP were free to enforce rules against constant connectivity, even if yours didn't.  Your ISP has got to make money to stay in business too, it's OK for them to set policies on shared resources.

I think he's talking about Network Neutrality. I am concerned that financial excuses may be used for censorship and exclude a great many people to internet resources. I don't think Bitcoin would use enough bandwidth to concern any ISP, but that wouldn't stop them from trying to block it. Fortunately, there are many ways for Bitcoin to adapt to get around the slow acting ISPs.

[ShadowOfHarbringer]

I hope one day we can get back to paying for the bandwidth you want with the right to fully utilize it as well as resell a portion of it.  Dialup sucked for the speed, but the openness enforced by the regulations over phone lines is what allowed the rise of the Internet.  Bandwidth caps and government-enforced ISP level censorship will be it's downfall.

I think we are already there.  Call your ISP and ask what service offerings they have for small office / home office.  You'll probably find that you can get access to any amount of bandwidth at a price.  Sure, you were probably expecting to consume unlimited bandwidth at max speed, pay the low residential rate and offer it to your neighbors, just like some kids go to daycare and assume access to lots of toys means the toys are all theirs.  Even under dialup, your phone company and ISP were free to enforce rules against constant connectivity, even if yours didn't.  Your ISP has got to make money to stay in business too, it's OK for them to set policies on shared resources.

You must be living in USA, UK or Australia.

Here, in central europe ALL wired broadband plans are unlimited and this is considered a standard. Of course mobile/wireless ones are always limited, but i guess that's normal & understandable.

It seems that in some things, "developing" countries are more advanced than "developed" countries. Curious.

[Technomage]

Do people actually leave their Bitcoin clients open? I understand the problem for users who do this, but nobody is forcing people to do that. I'm willing to bet that when this problem is relevant (when we see 1000 transactions per second, compared to the 6000 per day we see now) the network will work FINE even if nobody leaves their clients open when they don't use them. The network would still have thousands of active nodes online every second, even if they're not active for long.

The issue with blockchain size is a real one but we already have lite clients for mobile phones etc.. there are a lot of possible solutions to tackle the problem of too large blockchain. And as long as the computing requirements of verifying transactions isn't too massive for regular PC's to handle, it's fine. If it's more than they can handle, then we have a problem.

[BTCurious]

I don't know enough detail to form a proper opinion on this, but I can answer a personal question:

Do people actually leave their Bitcoin clients open?

Yup. I always have it open. Never bothered to close it, really.
I do mine in a pool as well, but I believe that's unrelated.

[cypherdoc]

from the paper:  "We think that if Bitcoin really succeeds the costs of relaying transactions will be very high and that this may cause “regular” non-mining nodes not to relay information (except for sending out transactions that they themselves initiated)."

i disagree.  i leave 4 separate clients open and i don't even mine.  i do it for philosophical reasons to "help" the network.  doesn't cost me anything.

[casascius]

I leave bitcoind running as well, for a selfish non-altruistic reason: I hate waiting for the blockchain to update when I go to use it.  It's slower than hell if you have to wait, and a total non-burden if it stays running.  I selfishly disallow incoming connections, but would quickly reverse that if I heard echoes of people having trouble finding open nodes to connect to.

[pointbiz]

I leave bitcoind running as well, for a selfish non-altruistic reason: I hate waiting for the blockchain to update when I go to use it.  It's slower than hell if you have to wait, and a total non-burden if it stays running.

+1

[paraipan]

I leave bitcoind running as well, for a selfish non-altruistic reason: I hate waiting for the blockchain to update when I go to use it.  It's slower than hell if you have to wait, and a total non-burden if it stays running.

+1

+1

[ShadowOfHarbringer]

I leave bitcoind running as well, for a selfish non-altruistic reason: I hate waiting for the blockchain to update when I go to use it.  It's slower than hell if you have to wait, and a total non-burden if it stays running.

+1

+1

+1

I also do have multiple clients on few servers running currently.

[becoin]

i leave 4 separate clients open and i don't even mine.  i do it for philosophical reasons to "help" the network.  doesn't cost me anything.

Everything costs something!

If bitcoin becomes fully fledged monetary system things like enthusiasm, altruism, philanthropy and philosophy will not be enough to secure its future! After all, it is about money! All tricks will be used both technically and economically to game the system and abuse it. Every expense that is possible to avoid paying will not be paid by participating agents in the network! There is no doubt about that... The big question here is whether all those avoidable expenses are fundamental incentives to keep bicoin network running?

[kazoo]

i leave 4 separate clients open and i don't even mine.  i do it for philosophical reasons to "help" the network.  doesn't cost me anything.

Everything costs something!

If bitcoin becomes fully fledged monetary system things like enthusiasm, altruism, philanthropy and philosophy will not be enough to secure its future! After all, it is about money! All tricks will be used both technically and economically to game the system and abuse it. Every expense that is possible to avoid paying will not be paid by participating agents in the network! There is no doubt about that... The big question here is whether all those avoidable expenses are fundamental incentives to keep bicoin network running?

I think this is the most important point. As a concept for a community, bitcoin has been better at making miners than at evangelists and transaction processors. I see this as a game that has made winners out of miners, but is missing players, now. This is a shortcoming of the system of incentives.

[notme]

i leave 4 separate clients open and i don't even mine.  i do it for philosophical reasons to "help" the network.  doesn't cost me anything.

Everything costs something!

If bitcoin becomes fully fledged monetary system things like enthusiasm, altruism, philanthropy and philosophy will not be enough to secure its future! After all, it is about money! All tricks will be used both technically and economically to game the system and abuse it. Every expense that is possible to avoid paying will not be paid by participating agents in the network! There is no doubt about that... The big question here is whether all those avoidable expenses are fundamental incentives to keep bicoin network running?

I think this is the most important point. As a concept for a community, bitcoin has been better at making miners than at evangelists and transaction processors. I see this as a game that has made winners out of miners, but is missing players, now. This is a shortcoming of the system of incentives.

Miners are transaction processors.  Mining is how they are verified.

[manifold]

Hi, I read some of the posts and I try to summarize it for later readers, and please correct me if I say something wrong:
1. There could be a problem if  out of some reasons there aren't enough people relaying transactions. Example: Bitcoin gets to Visa proportions and only miners have the hardware requirements to receive/relaying transactions. They will (of course) not relay transactions if there is no incentive.

Solutions:
1) Pay all (or statistically some) node that relayed transactions somehow
2) Punish the (greedy) nodes, by cutting connections to them. Then a miner not relaying transactions will receive much less transactions (he could include in his own block)


My Comment:
I think that it it very important to think about it. The solution 2) wouldn't require a change of protocol (I think) and is a quick and easy way to get everyone to relay transactions (even if the network is just composed of miners (due to hardware requirements)).

1) would certainly open a whole lot of new set of problems/attacs, but If REALLY carefully thought through would solve the problem more elegantly than 2).

An other point to 2): Instead of counting how many transactions a node relays (to determine if they are greedy), maybe it should count how much transactions fees they are relaying (just an idea...  but I don't know if that is better or worse, than counting the number)


Ok. It's good that we think about it, thanks to the guys from MS (yes I run Linux)!

[cbeast]

i leave 4 separate clients open and i don't even mine.  i do it for philosophical reasons to "help" the network.  doesn't cost me anything.

Everything costs something!

If bitcoin becomes fully fledged monetary system things like enthusiasm, altruism, philanthropy and philosophy will not be enough to secure its future! After all, it is about money! All tricks will be used both technically and economically to game the system and abuse it. Every expense that is possible to avoid paying will not be paid by participating agents in the network! There is no doubt about that... The big question here is whether all those avoidable expenses are fundamental incentives to keep bicoin network running?

I don't think of the Bitcoin client as simply a way to spend Bitcoin, even though that's about all it is at the moment. I think of my computers as machines for (sometimes monkey) business. If you want a productive business, you find ways to keep your machinery running 24/7. I think that will be the goal of software designers to craft tools using Bitcoin to stay on making money. I'm not talking about mining, but real world businesses that will depend on a robust Bitcoin network.

[edit]
I wouldn't be surprised if M$, Google, Facebook, Mozilla, Apple, (pardon my bias) etc. doesn't have NDAs regarding major development for BTC based apps. I can't imagine big ballers not creating Open Transaction servers, microtransactions, anti-spam postage based email, deed of title apps, escrow based courier services, and probably hundreds of other unique products and services that take advantage of Bitcoin's unique properties.

[cypherdoc]

i leave 4 separate clients open and i don't even mine.  i do it for philosophical reasons to "help" the network.  doesn't cost me anything.

Everything costs something!

If bitcoin becomes fully fledged monetary system things like enthusiasm, altruism, philanthropy and philosophy will not be enough to secure its future! After all, it is about money! All tricks will be used both technically and economically to game the system and abuse it. Every expense that is possible to avoid paying will not be paid by participating agents in the network! There is no doubt about that... The big question here is whether all those avoidable expenses are fundamental incentives to keep bicoin network running?

I don't think of the Bitcoin client as simply a way to spend Bitcoin, even though that's about all it is at the moment. I think of my computers as machines for (sometimes monkey) business. If you want a productive business, you find ways to keep your machinery running 24/7. I think that will be the goal of software designers to craft tools using Bitcoin to stay on making money. I'm not talking about mining, but real world businesses that will depend on a robust Bitcoin network.

[edit]
I wouldn't be surprised if M$, Google, Facebook, Mozilla, Apple, (pardon my bias) etc. doesn't have NDAs regarding major development for BTC based apps. I can't imagine big ballers not creating Open Transaction servers, microtransactions, anti-spam postage based email, deed of title apps, escrow based courier services, and probably hundreds of other unique products and services that take advantage of Bitcoin's unique properties.

very, very interesting insight.  i hadn't thought about that.  if we are all so fascinated by this technology, how could the big boys not be?  i know of several PhD mathematicians, computer geeks, and economists who are fascinated with Bitcoin and these are precisely the type of ppl who'd be employed by these large players.  if they're smart they would be getting ready for the snowball effect.

[cypherdoc]

i leave 4 separate clients open and i don't even mine.  i do it for philosophical reasons to "help" the network.  doesn't cost me anything.

Everything costs something!

If bitcoin becomes fully fledged monetary system things like enthusiasm, altruism, philanthropy and philosophy will not be enough to secure its future! After all, it is about money! All tricks will be used both technically and economically to game the system and abuse it. Every expense that is possible to avoid paying will not be paid by participating agents in the network! There is no doubt about that... The big question here is whether all those avoidable expenses are fundamental incentives to keep bicoin network running?

maybe i should frame it differently.  i also have an economic incentive to leave my computers on to support the network.  i have a substantial investment in Bitcoin as do many others who compose the network.  its about taking care of one's money.  you don't just leave it out on the front lawn for anyone to take.  you build a safe in a remote area of your house and fortify it to the extent you feel comfortable.  you may buy a few guns also just in case.  it may cost me a few cents to keep those computers on but i want to take care of my money!

[dree12]

i leave 4 separate clients open and i don't even mine.  i do it for philosophical reasons to "help" the network.  doesn't cost me anything.

Everything costs something!

If bitcoin becomes fully fledged monetary system things like enthusiasm, altruism, philanthropy and philosophy will not be enough to secure its future! After all, it is about money! All tricks will be used both technically and economically to game the system and abuse it. Every expense that is possible to avoid paying will not be paid by participating agents in the network! There is no doubt about that... The big question here is whether all those avoidable expenses are fundamental incentives to keep bicoin network running?

maybe i should frame it differently.  i also have an economic incentive to leave my computers on to support the network.  i have a substantial investment in Bitcoin as do many others who compose the network.  its about taking care of one's money.  you don't just leave it out on the front lawn for anyone to take.  you build a safe in a remote area of your house and fortify it to the extent you feel comfortable.  you may buy a few guns also just in case.  it may cost me a few cents to keep those computers on but i want to take care of my money!

But like it or not, if Bitcoin goes viral you are nothing. You are one of 7 billion. The cost to keep your computers on is a few cents; the expected risk for not doing so is your entire bitcoin stash... divided by 7 billion. The economic incentive is outweighed by the disincentive.