Microsoft Researchers Suggest Method to Improve Bitcoin Transaction Propagation

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

[1713910266]

1713910266

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