Topic: Majority is not Enough: Bitcoin Mining is Vulnerable - page 3. (Read 51045 times)

The "exploit" he "discovered" has been discussed in 2010 on these very forums.

I hope he sold all his coins before publishing in an attempt to buy back during some kind of crash. I don't doubt the credentials of the guys who discovered this exploit, but the way they released the information in sensational terms is suspect.

They will not. What for?

Based on his behaviour over the last few days, I give him an 8/10 for douchebag.

He's eligible for a perfect score if it turns out he posts on this forum as "revans" and if he's in any way related to the DDoS attempts on the exchanges and charting sites yesterday.

So these two guys at Cornell University, an associate professor and a post-doc, publish a paper on Arxiv about what they believe to be a flaw in Bitcoin.

Rather than quietly and tastefully wait for some feedback on their ideas, the professor immediately Tweets "You heard it here first: now is a good time to sell your Bitcoins."  He then proceeds to blog "Bitcoin is Broken."  News outlets, seeing no reason to believe two guys with PhDs employed by prestigious Cornell University are spraying FUD with a large diameter hose, run with the story that a fatal flaw has been discovered in Bitcoin, and its collapse is iminent.

The central thesis of his paper is that you can make mining slightly more profitable by picking when to make public blocks you have mined, and that this will cause miners to join your pool until it increases to a size which threatens the decentralized nature of the Bitcoin cryptocurrency.

Now we've discussed the threat posed by large mining pools for years, and it makes little difference whether they attract clients by gaming the mining protocol, paying a premium for shares, promising a share of the windfall profits that result when they reach 51%, or giving away free toasters.

It is generally accepted that such shenanigans would be noticed by the community before any harm was done, and appropriate policies adopted.  Therefore, it is unlikely people will make the investment to try such things, only to have them nipped in the bud forthwith.

The professor reacts to skepticism about his attack by saying that all rebuttals must "include math" to be seriously considered, and goes on and on about the great burden he endures by having to put up with the stupid.

He deletes critical blog comments claiming they contain "profanity," which apparently includes the word "fraud" and Will Rogers quotes.  After a few days of being slow-roasted on the spit of Bitcoin community displeasure, he defiantly declares" I used to think that money brought out the worst in people, until I saw Bitcoin."

The reaction of the developers to the idea that this attack poses some serious real threat to Bitcoin has been somewhere between "yawn" and "snooze."

Now the paper is interesting, and it has resulted in some serious discussions about how such an attack might play out, although there are some questions whether the methodology is a perfect fit to the problem being described.  Had it simply been released without the accompanying egregious self-promotion and predictions of Bitcoin demise, it probably would have been warmly received, and constructive feedback cheerfully provided.

This whole scenario is like a guy walking up to show everyone a marvelous anti-gravity car he has invented.  He describes the engine in detail with complicated fluid dynamic equations and state diagrams, and refuses to entertain any rebuttals of his design methodology which don't use these tools.  Meanwhile, a less technical crowd has gathered, and noticed there is no hose connecting the engine to the fuel tank.



 

Mined Block Reference Nodes

Latency. A thousand curses to latency! It's the reason this thread exists, a questionable attack vector. It's the source of orphaned blocks and lost revenue. Need I mention the continuing block size problem is due to -- you got it -- latency.

If we could get rid of latency the above problems would vanish! What a relief that would be. It may be possible.

When I conceived Mined Block Reference Nodes (MBRNs) in answer to people questioning Litecoin's reduced block time I thought they might come to exist with any blockchain of continued success. I hadn't worked out the details but the prospect seemed promising. This latest issue caused me to think more carefully.

A MBRN does not require a protocol change. They are not an integral part of the network. Whether they exist or not provides incremental, but not critical improvement overall, like hashrate variance.

A MBRN offers miners two key things: the quickest indication of a new valid block, and the largest list of nodes having it.

How to Build a Mined Block Reference Node

The incentive for building a MBRN, and there can be many, is probably altruistic but can include profit. I see this as a web app over http which I think has benefits, like easy use of DNS which can be useful as I'll describe.

An administrator starts with a tipping wallet address. Just as miners expect users to tip fees for valuable service, a MBRN expects this of miners. Reducing orphaned blocks and increasing network performance means the same level hashrate security with less revenue due power companies, a direct savings.

There can be different configurations but a simple dedicated hosted server is probably fine. The app may serve thousands of requests per second, but isn't function or computation complex.

The admin publishes rules of good behavior and keeps a couple whitelists. There are three (high demand) interactions with a node: query for new block, push new block, and query node list; plus the threat of DDOS so whitelists are needed. Querying for a new block may be limited to once say per 5-10 seconds, and returns the highest block number known.

When accepting a pushed block the node screens and prioritizes by whitelist -- IP addresses that provided a valid block prior -- as this is bandwidth and resource significant. Considering the effects miners will desire to stay within the good graces of a MBRN, and bad actors will be quickly identified.

When new blocks are recognized the height number is updated and the MBRN directly serves maybe the last 2 or 3 blocks on a first come first served basis. For each querying node served the MBRN keeps a constantly growing list of known nodes having the block, starting with itself. Every node calls back to the MBRN when they receive the block; they have incentive to do so because they have started mining on top of it and don't want it orphaned. In this way the knowledge about and dissemination of any new block spreads quickly and exponentially, while not requiring significant bandwidth up or down from the MBRN.

Multiple MBRNs may communicate with each other in the spirit of altruism; and tipping for good service provides a market check and balance for weeding out bad actors.

DDOS

Bitcoin ecosystem websites have already been victims of DDOS and a MBRN would be a target too. As I said in an argument with DeathAndTaxes on this subject that attack's strain on a website usually occurs with the database -- often the same fault under legitimate higher than expected traffic. However, the difficulties in dealing with DDOS as a website will be different than for a MBRN. A website can't predict user behavior and usually has multiple pages of various process complexity to serve reliably. Neither of those are true for a MBRN. Normal websites also can't predict which IP addresses to expect on a regular basis. Here again a MBRN has an advantage. I believe a MBRN can defend well against DDOS for these reasons, but also by being nimble.

Bitcoin websites are finding ways to mitigate DDOS. I'm increasingly seeing use of Cloudflare, for example, which works by sitting at DNS level and handling attacks from there. This is a strategy MBRNs can use too as Cloudflare compiles all the bad actor IP addresses it sees naturally. Their DDOS protection starts at around $200 per month. Take that with the cost of a dedicated server and you have only a few hundred dollars per month expense to run a MBRN, while probably at least that in tips. There are other anti-DDOS configurations I've thought about too, some also involving DNS management, say with EasyDNS.com (situated well globally), to load balance across multiple hosts if desired, because the app is so simple. This is in consideration of what DeathAndTaxes mentioned about severe bandwith impacting DDOS. The answer to that is distribution, and is easily managed with DNS for example, or a CDN like Akamai as I mentioned prior and which MTGox now subscribes to.

Block Size

A final consideration is block size. If this model works in practice imagine how it impacts block size. A key argument against raising the block size limit is it results in the best connected, ie the best funded, eventually dominating won blocks which is supposedly random. This puts far less pressure on network connection for even the smallest miner.

I think that covers it.

The selfish mining pool makes an upfront investment and gets what exactly for this? Is there some state authority protecting the selfish pool from competition?

If you pay money to do X and I can not pay money and still capture the benefit from X, then you will never pay money to do X. The existence of the PPS pools implies that the selfish pool has to front some cash at the outset to retain miners.

If you are going to tell me that other selfish pools cannot enter and steal miners from selfish pool (1), then I am going to tell you that this implies that it is worth operating an honest PPS pool to fight a selfish mining pool by paying out more than it earns. You are essentially saying that the game is dynamic and that it is valuable to retain miners and carry them into the next period. If so, it can be worthwhile to do so at a loss.


Honestly, though I think the free entry into pools scenario is more realistic.

I'm not sure I follow. Yes, the selfish mining pool needs an upfront investment. But - again, if we assume this attack is valid - it has the prospect of earning more than it pays to its miners, because it's using the selfish approach.

The most any mining pool can pay per share is block_rewards/num_shares, which would mean it's paying out all its income to the miners - zero profit. If a selfish mining pool can earn 50% of the block rewards while only needing 40% of the network hashrate (which the paper claims), it can afford to pay more per share than an honest mining pool (which only gets 40% of the block rewards with 40% of the network hashrate).

As far as I can see, an honest PPS pool somehow "fighting" selfish mining pools by paying out more than it earns, only means that the selfish pool needs to wait until the honest pool has no more money.

Time isn't really an issue, the only condition behind the decision in withholding an alternate chain is the difference in block height. See below for checkpoints but they don't change this much.


No: Bitcoin nodes accept to rewind the chain by any length if the replacement chain is longer.
That said the official Bitcoin client has checkpoints to avoid arbitrary long rewrites: you can't rewind past the last checkpoint. New versions of the official Bitcoin client often come with new, more recent checkpoints.

Agreed.  The image that comes to mind is the guy selling his method for beating the stock market.  If it worked, he wouldn't need to sell it.

Surely it would be simpler and more empirical to simply create a selfish miner and let it loose and see what happens

I'm calling for (and have pledged a bounty for) a network simulator with latency.

I don't believe for a minute that this is economically efficient based on the output of an iterated finite state machine.  Gamma is not a property of the network, it emerges unpredictably during each race from the chaos of the network.

Ehh, if an honest mining pool earns zero profit, then there is free entry in the creation of mining pools and miners switch between pools readily. In this case the selfish pool can't earn a profit either. Someone else can just establish another selfish pool that offers a slightly better deal to miners. Miners will all migrate to the new selfish pool. Repeat until profits reach zero.

The selfish pool would have to undercut PPS pools' margins to enter in the beginning (otherwise it couldn't attract any miners). Since the selfish pool has lower mining output, this requires an upfront investment. The selfish pool has to take a loss to begin with. If there are no profits to be had and you have to take a loss upfront, then you would never see a selfish pool in practice. It is just money down the drain.

If an honest mining pool earns positive profit, then there are some barriers to entry and that probably means miners are more reluctant to switch between pools. In this case, you have a lock-in affect. Just having an event that causes everyone to switch to your pool is a substantial gain for the PPS pool operator. It is worth taking a loss to establish yourself as the dominant pool. If you were the dominant pool to begin with, it is also worth taking a loss to defend this position. I do not think such a lock-in would apply to the selfish pool (the lock-in is probably mostly about trust and people would quite reasonably distrust this entity)

Finally, there is no reason to assume that the honest mining pool plays honest. The PPS pool could also just perform a 51% attack on the selfish mining pool. I think a temporary retaliation would be accepted by the community. Such a tit-for-tat sets a good precedent. In this case, the PPS pool can earn large profits from conducting the attack. These could be split between the PPS miners and everyone else.

The real problem is if someone malicious does a 51% attack, but this has always been a problem and it has nothing to do with selfish mining. There have always been ways of using pools to create a 51% mass of hashing power to execute such an attack (see the loyalty program discussed above). The selfish pool business is an irrelevant non-issue. If you are not concerned about the loyalty program (which is a dominant strategy under extremely general assumptions), then you should definitely not be concern about the sibyl attack (which would cost the attacker money upfront and probably fail in practice)

What can I do to help?  I've tried to understand the topic.  To me it seems like there's a pretty small window (if any?) through which delayed block announcing can gain any advantage.  Clearly delaying too long is nonsense.  When is the block chain considered fixed?  Is 6 blocks the number of blocks required to be considered immutable?  Even with 100% of the hashing power no one can go back and rewrite the chain before some point, right?  If a new very fast miner comes along and picks some historic point in the chain and computes a longer fork, i.e. they catch up to the rest of the miners (an impressive amount of computing power), are the rest of us obliged to accept it?

What I do see is the need for a reliable and vigorous development community to respond/handle each and every threat.  How can we ensure that community is and remains reliable and isn't compromised?  I am willing to run a variant of the client if it would help secure Bitcoin against delayed block announcing.  Or I will ignore the threat if the consensus of the development community points in that direction.  How can we be sure what the consensus is?

I'm not convinced by the PPS pool-argument either. As far as I can see - given that the selfish mining thing actually works - a PPS pool operator has two choices:

1. Investing in something that can, in a best case scenario, give him zero profit (an honest mining pool), and in a worst case scenario make him lose money (if the selfish pool wins)

2. Creating a selfish mining pool that can actually earn a positive profit, but also make him lose money

Which will he choose?

Work can be wasted whenever orphan blocks are produced. Orphan blocks do not contribute to network security, they do not pay their creators, and they are not relayed to the rest of the network.



If you are trying to achieve gamma=1 then yes, the signal that you need to act is also the signal that you have already lost. But unless I am the VERY LAST node on the network to receive this block, it may be possible for me to get my block to other nodes that have not yet seen the honest block and in this way recruit at least some of the honest miners to work on my chain. Even if you do not agree with this seemingly obvious statement, it DOESN'T MATTER. Because as I am getting tired of pointing out, the attack still works for gamma=0. This is the case where we assume that I was indeed the very last node to receive the block and not a single honest node will compute a single hash on my block in the case of a tie. In this magical case I need 33% of network hash-power to earn excess rewards.


Nope still wrong. In my simulation, nodes get allocated to mine on one block or the other with a probability of gamma of being assigned to the attacking block (you've got the logic of gamma reversed by the way) and I replicated their results perfectly. What is more, for the interesting cases gamma=0 and gamma=1, the two approaches are exactly the same.

I don't really want to argue this point. As I have repeatedly stated I think that gamma->1 is extremely pessimistic and probably not achievable in the current network. But that is a red herring. The fact is that gamma->0 is extremely optimistic and even under those circumstances, the attack works. No Sybil attack is needed, so I wish we could stop discussing whether the Sybil attack is possible.

Thanks for pointing this out Meni. Based on the post, it looks like he is taking a more thoughtful approach to the topic.

Well done, you got me.  Work can be wasted if done at the wrong end of the chain.  If you read on to the end though, I clarify that expression.


What may have tripped me up was the way they describe gamma on the various pages.  When I was reading the paper, I was struggling to find a unifying theme for all of the ways they use gamma.  It seems to be a choice on one page, and then an expression of the natural race between competing blocks on the next.

In regards to latency, you seem to be missing a very important aspect of reality on the bitcoin network.  If you are sitting on a block, waiting for the rest of the network to find one so that you can publish yours, the signal that you need to act is also the signal that you have already lost.  Don't feel bad, this entire paper was written because of the same misunderstanding.  You can not win races by waiting for the rest of the network to pass you.


I agree with you so much that I traveled back in time to do it.  What is fully deterministic in their model is everything else.  When a new block is found, gamma of the network switches to it, while 1-gamma switches to the attack block.  This is not reality.



When you run to the press, you tell the world that you are no longer interested in civil peer review.  

And the "cave" or the countermeasure in this case is that one or more of the honest guys should bleed money operating a PPS pool at a loss until the attacker goes away. Errrm, yes that sounds like it will work.

Lear, who has independently done much higher-quality research on the same issue, has posted a sample of his results:
https://bitcointalksearch.org/topic/the-block-discarding-attack-shellfish-mining-325824

I recommend staying tuned for his complete work, which can serve as a more fertile ground for further discussion on the topic.