Microsoft Researchers Suggest Method to Improve Bitcoin Transaction Propagation

[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...