Bitcoin Forum

Saw this on reddit first, reading paper, thought I should share:

http://arxiv.org/abs/1311.0243

http://www.reddit.com/r/Bitcoin/comments/1puk1a/arxiv_paper_majority_is_not_enough_bitcoin_mining/

Fascinating...reading still right now...but if I get this correct - the concept is that you're mining on something big like btcguild, and copying the entire block header onto your own private pool of work; at the same time, your miner is accepting work and not submitting valid shares to btcguild yet it submits them to the private duplicated pool. 

Anytime a Valid Share is found to have met minimum difficulty and discovers a block, it submits this from the private pool and broadcasts to the network?  Network accepts this and the private pool is fed the newly minted coins instead of btcguild?

Saw this on reddit first, reading paper, thought I should share:

http://arxiv.org/abs/1311.0243

http://www.reddit.com/r/Bitcoin/comments/1puk1a/arxiv_paper_majority_is_not_enough_bitcoin_mining/

Thoughts?

Point 0 is just a workaround right?

Saw this on reddit first, reading paper, thought I should share:

http://arxiv.org/abs/1311.0243

http://www.reddit.com/r/Bitcoin/comments/1puk1a/arxiv_paper_majority_is_not_enough_bitcoin_mining/

The contribution of the paper (to my thinking, at least) is to assume that an attacker can also sybil attack the network, and in doing so can run nodes which will release blocks produced by the attacking miners in response to hearing a new block from the honest miners. So where the sybil attack is successful the delay does not confer a disadvantage and then the attack works (with increasing effectiveness the more effective the sybiling is and the more hashrate the attacker has).

The additional protective measure would be that any chain reorg of n blocks is delayed n seconds.  During that wait period, if another better chain reorg is received, it is processed in the same way. After one period expires, the chain reorg is applied, and a new best chain is created. If a block that extends a waiting chain is received, then the waiting lapse is restarted from zero for that chain. ...

Currently the first block that arrives is picked by miners so the "secretives" have incencitive to "delay public blocks", an incentive to listen in on other mining pools "detect early public block announcement to quick react to it" and to try and inject/publish their secretive block as fast as possible towards other miners that have not yet received a new block.

Excuse my naiveté, but I was under the impression that the software which coordinates the mining effort of a pool between the pool miners is NOT responsible for claiming the mining prize, but that each lowly pool miner - should he find the correct hash - claims the prize to an account belonging to the pool and immediately broadcasts his success. This way, immediate broadcasting of the new block is assured, and keeping stuff secret would never happen.

A miner in a traditional pool doesn't have the information needed to publish a block on his own. He has to submit the header w/ nonce to the pool, and then the pool broadcasts the block.

Since the algorithm for "Selfish Mining" is now public, all miners have an opportunity to employ it if they feel it gives them an advantage.  So the notion that there is only a single pool of colluding miners growing as other miners join it to reap its advantages is moot.

something we may need some time in the future as the profit margins in mining become lower.

Profit margins will go up when the transaction rate gets high enough to generate significant transaction fees compared to the block subsidy.

b) increased transaction rates mean more money spent on overhead, rather than the hashing power that keeps bitcoin secure

Yeah, well there's a huge amount of room for optimization there that currently isn't being done.

Either the transaction rate goes up high enough to pay for all this mining infrastructure or else Bitcoin dies.

I just printed out the paper and read it.

Since the algorithm for "Selfish Mining" is now public, all miners have an opportunity to employ it if they feel it gives them an advantage.  So the notion that there is only a single pool of colluding miners growing as other miners join it to reap its advantages is moot.

Initially the colluding pool is a small fraction of total hashrate, and therefore has a vanishingly small probability of being able to mine consecutive blocks on its private chain.  So the only thing it can do is force other people to waste time by delaying publication when it mines a block, and some fraction of the time, its block wins over the public block, and people who have attempted to append to that block lose their work.

This seems to me to be such a small epsilon in the hashing activity that no one is really going to care, and no one is going to bother to do Selfish Mining.  The work to reward ratio here is pretty large.

So basically, "Nothing to See Here," and no modification to the Bitcoin protocol is needed.

your blocks ends up increasing the risk that you get orphaned since nodes prefer the first block they heard.

In the case of two branches of the same length, we artificially divide the non-pool miners such that a ratio of γ of them mine on the pool’s branch and the rest mine on the other branch.

I think this assumption of theirs is the flaw.

Successful pools do not build on the first block they hear; they build on the most difficult block they hear.

If you rerun their calculations under that assumption, the cost of losing the work done on their second block in the private two-block chain swamps out any possible benefit.

If the end-user bitcoin-qt client is using the "first block heard" rather than "most difficult block heard", then it's a bug, and one that is already fixed on the network nodes that matter most for security (the mining pools and large solo miners).

Blocks that are not near a difficulty change will always have the same difficulty.

No, the difficulty of a block is binomially distributed.

The minimum difficulty required for a block to be valid is the thing that stays the same.  Within that 2016-block window the actual difficulty of various blocks varies above that threshold.

It would be less ambiguous if you said, "Successful pools do not build on the first block they hear; they build on the block with the highest work they hear."

Umm WTF are you talking about? Try reading it again, only this time whilst not high on Bitcrack. Maths + human nature= a selfish mining future and the end of Cultcoin. In a sense the popularity you so longed Bitcoin to have has destroyed it as peer review is demonstrating just how architecturally boken Bitcoin is.

This is an academic exercise

Well, we're splitting hairs here, but technically I might have gotten lucky and not worked very hard to find a block whose hash, in binary, ends with 250 zeroes in a row (outrageously high difficulty).

But yeah we're talking about the same thing.

Do you have a specific criticism?

You are welcome to set up a selfish mining rig and prove me wrong.  Unless you have sufficient hash power to be mining blocks very frequently, no one is even going to notice you exist.

This is an academic exercise with very tiny practical implications, and in any case, a very small threat on the long list of threats.

I think this assumption of theirs is the flaw.

Successful pools do not build on the first block they hear; they build on the most difficult block they hear.

Here is a solution we did not put in the paper due to space constraints
that should alleviate your concern:

Instead of locally choosing a block at random, have a deterministic
pseudo-random mechanism for choosing between competing chains. E.g., take
the one whose last block hash is smaller. This way all miners choose the
same chain, and the guarantees of our solution hold.

"Difficulty" and "target" are actual technical terms with precise definitions in the block protocol.

Google news is showing a number of articles which amount to FUD, which are multiplying like gremlins.
Perhaps the Bitcoin Foundation should put up a short rebuttal / press release encapsulating some of the information in this thread. While the Eyal paper has some merit - it is certainly not a situation of "'Bitcoin Is Broken' And Could Collapse"

Bitcoin flaw could let group take control of currency
CNNMoney - ‎3 hours ago‎
The flaw is due to the nature of how bitcoins are created -- people "mine" them by solving a complex puzzle with their computers. If used correctly, the system is set up so that someone guesses correctly every 10 minutes, and the winner gets 25 bitcoins.
http://money.cnn.com/2013/11/04/technology/bitcoin-flaw/

Bitcoin Researchers: You Can Game the System
Mashable - ‎10 hours ago‎
Computer science researchers at Cornell University claim to have found a way to subvert the system driving production of the digital currency Bitcoin. The researchers call their technique “selfish mining,” through which individuals or groups of Bitcoin miners ...
http://mashable.com/2013/11/04/bitcoin-cornell-researchers/

Researchers Say 'Bitcoin Is Broken' And Could Collapse
Yahoo!7 News - ‎1 hour ago‎
The problem is with how people "mine" bitcoins. Mining is how bitcoins are created. Most people don't mine bitcoins anymore. They buy them or take them as payment. But some people are in the business of mining coins with special bitcoin-mining computers ...
http://au.finance.yahoo.com/news/researchers-bitcoin-broken-could-collapse-014448102.html

Cornell Researchers Found a Way to Game Bitcoin
RYOT - ‎2 hours ago‎
It's entirely likely and understandable, despite our better efforts to bombard you with Bitcoin stories recently, that you still don't know what Bitcoin is. (To be honest, 92 articles about it later we still don't fully grasp it.) But all you need to know is that it's digital ...
Bitcoin open to takeover, researchers discover with new algorithm
http://www.ryot.org/cornell-researchers-claim-able-game-bitcoin/456361

Science Daily (press release) - ‎58 minutes ago‎
Nov. 4, 2013 — A major flaw that has gone unrealized until now leaves the $1.5 billion Bitcoin market open to manipulation and a potential takeover, according to a new study by two Cornell University computer scientists.
http://www.sciencedaily.com/releases/2013/11/131104112234.htm

This is a statistical fallacy. Two blocks will always be equally difficult when they were mined with the same target.

What you mean to say is that clients prefer to choose the block with the least block hash.

  0xffffffffffffffffffff0000
  0x000000000000000000000000000f0000

That is an accurate headline. Bitcoin is fundamentally broken per these findings, and significant exploitation of these findings (which given human nature and financial incentives is inevitable) Bitcoin will collapse. Bitcoiners can issue all the press releases attempting to debunk this reality as they like, it won't change a damn thing. The only question is how quickly this exploitation happens, and how rapidly it poisons the whole network

Fun times ahead.

You can't seriously think

That is an accurate headline. Bitcoin is fundamentally broken per these findings, and significant exploitation of these findings (which given human nature and financial incentives is inevitable) Bitcoin will collapse. Bitcoiners can issue all the press releases attempting to debunk this reality as they like, it won't change a damn thing. The only question is how quickly this exploitation happens, and how rapidly it poisons the whole network

You're wrong: nobody does that

E.g., take
the one whose last block hash is smaller. This way all miners choose the
same chain, and the guarantees of our solution hold.

Nodes always consider the longest chain to be the correct one and will keep working on extending it. If two nodes broadcast different versions of the next block simultaneously, some nodes may receive one or the other first. In that case, they work on the first one they received, but save the other branch in case it becomes longer. The tie will be broken when the next proof- of-work is found and one branch becomes longer; the nodes that were working on the other branch will then switch to the longer one.

This is a definitional fallacy.



What you mean is the most difficulty, which is not the same as the numerical block hash.  The natural numbers less than 2^256 are a total order, but difficulty is a partial order on block hashes.

You can't seriously think that a mining pool waiting to announce its blocks until they invalidate the maximum amount of other peoples' computation is going to significantly perturb the network unless that mining pool already has a non-trivial fraction of the total hashrate.

The network is hardly in any danger of being poisoned.

 

What are you talking about?

Your view assumes Bitcoin is a static thing; Bitcoin can be changed in response to this attack

What the Bitcoin Foundation should be doing is releasing a press release welcoming the Cornell researchers competent analysis of the flaws in the system, while pointing out that one of the strengths of Bitcoin is that flaws can be corrected if a clear majority of Bitcoin users choose to change the software they run.

My ELI5 explanation that I posed to bitcoin-development might help people understand the attack:

Alice is a miner with some amount of hashing power. She has the ability to detect new blocks on the network extremely effectively because she has controls a lot of nodes with low-latency, high-bandwidth connections; in short she has unusually good knowledge of the state of the network. She is also very good at publishing her blocks and getting them to the majority of hashing power in very little time; she has unusually good connectivity to all miners. (again low-latency and high bandwidth)

She's so good at this that when she finds a new block, she keeps it a secret! She can get away with this because she knows that the moment any other miner, like Bob, finds a block, she can immediately broadcast it to the rest of the network before the other block propagates. Instead of building on Bob's blocks, almost everyone builds on Alice's block, having seen it first, depriving Bob of the revenue. Gradually Alice gets more and more miners because all the other pools don't pay out as much as Alice's pool does. This eventually leads to Alice having a majority of hashing power, or if not that due to social pressure, a majority of the mining revenue.

Google news is showing a number of articles which amount to FUD, and are multiplying like gremlins.
Perhaps the Bitcoin Foundation should put up a short rebuttal / press release encapsulating some of the information in this thread. While the Eyal paper has some merit - it is certainly not a situation of "'Bitcoin Is Broken' And Could Collapse"
...

Well so far the Bitcoin community of cultists have done little but accuse the researchers of being part of a government plot to destroy Bitcoin, and some idiot has even put a Bitcoin bounty on their heads.

As to changing client software, it will ameliorate the problem, but it cannot fix it.

By now, the Bitcoin market has priced in this information.  Bitcoin is at $239 on Mt. Gox.

Your view assumes Bitcoin is a static thing; Bitcoin can be changed in response to this attack

What the Bitcoin Foundation should be doing is releasing a press release welcoming the Cornell researchers competent analysis of the flaws in the system, while pointing out that one of the strengths of Bitcoin is that flaws can be corrected if a clear majority of Bitcoin users choose to change the software they run.

This problem as I see it is non-existent. As I've talked about before Mining Block References (MBRs) can tremendously reduce latency which would squash this attack.

You deleted my example; that may be the source of your confusion…

Here, look at it in fixed-width font, with some emphasis:


  0xffffffffffffffffffffffffffff0000
  0x000000000000000000000000000f0000


See how they have the same number of trailing zeroes?  For any target you choose, either both will match it or neither will.  Yet these two numbers are not equal.  Therefore difficulty is creates a partial order (http://en.wikipedia.org/wiki/Partially_ordered_set) on block hashes.  On the other hand "less than" is a total order (https://www.google.com/search?client=safari&rls=en&q=total+order&ie=UTF-8&oe=UTF-8) on block hashes.

We only need a majority of miners to change. Any fix would be completely transparent to users.

1) Make the nonce long enough that the extraNonce field is no longer needed in the coinbase transaction.

All ASIC will be broken so basically no one will follow this hardfork.

All ASICs get replaced after a few months anyway, so it would be no problem to define it 6-12 months in the future before implementing it.

The arm-race won't last indefinitely and it will eventually slow down. I don't see any chance to change the format of the 80bytes header unless absolutely needed, e.g. SHA256 weakened or timestamp overflow in the far future

if you have already found TWO blocks privately (for whatever reason)... then it would ALWAYS be better to continue mining in private, right? Because as soon as the network finds one block, you can reveal your two... and if you find three, then you can keep going and only reveal your hand when the network finds n-1 blocks. Am I thinking correctly?

Umm, well apart from the fact that the cost for any rogue government or bank to bring down Bitcoin has now decreased dramatically, I think you are naive to think that selfish mining won't become the norm.

I think this assumption of theirs is the flaw.

Nodes prefer the first heard among those with otherwise equal work.

How often does it happen that two miners simultaneously find a block with exactly equal work values?

Ok, what about that problem:

Some guy with deep pocket (government?) establish a very stable mining pool with the best
protection agaisnt ddos and with the lowest network latency possible and welcomes everybody to mine with 0% (or even negative) fee.

So, eventually he will get 51% of hashing power, will not he?
And he even do not need to exploit the problem discussed in this thread, he can just be the honest mining pool.

a slightly different question:

how would we detect if such an attack is taking place?

As far as I understand, the attacking miner would have a slightly higher
ratio of blocks broadcast in pairs. That is, normally if his block rate  is alpha
then  rate for pairs should be alpha^2,  but if he is running the attack this value would
be slightly but significantly higher, and depends on gamma (how successful he is with
his sybil attack). It'd take a long time to detect though

Do you have a specific criticism?

You are welcome to set up a selfish mining rig and prove me wrong.  Unless you have sufficient hash power to be mining blocks very frequently, no one is even going to notice you exist.

This is an academic exercise with very tiny practical implications, and in any case, a very small threat on the long list of threats.

Your analysis is pretty incomplete. Their success at winning that "fast as possible" race, along with their total hashrate, is essential. Otherwise a delay is a pure loss.

1) Make the nonce long enough that the extraNonce field is no longer needed in the coinbase transaction.

2) Now it's possible for miners to broadcast their Merkle tree as soon as they start hashing (10 minutes on average before they finish)

3) When they find a valid hash, now they only need to broadcast the block header because the rest of the network has (usually) already received and validated the Merkle tree.

4) Block header propagation is very fast and not dependent of the size of the blocks.

...
You deleted my example; that may be the source of your confusion…

Here, look at it in fixed-width font, with some emphasis:


  0xffffffffffffffffffffffffffff0000
  0x000000000000000000000000000f0000


See how they have the same number of trailing zeroes?  For any target you choose, either both will match it or neither will.  Yet these two numbers are not equal.  Therefore difficulty is creates a partial order (http://en.wikipedia.org/wiki/Partially_ordered_set) on block hashes.  On the other hand "less than" is a total order (https://www.google.com/search?client=safari&rls=en&q=total+order&ie=UTF-8&oe=UTF-8) on block hashes.

...
It's indeed a bit more complex than the article (who's link is now broken, apperently the pdf converter crashed... update: v1 seems to still be available, v1 is from 1 november, v2 seems to have crashed, v2 is from 4 november) seems to make out
...

I feel that this post might be the solution to this 33% attack.

I originally thought of it as a way of more efficiently scaling to very large block sizes, but it might have the added effect of making this attack more difficult too.

I feel that this post might be the solution to this 33% attack.

As a valid block must be pre-broadcasted in the step 2), earlier than a certain time period, and there is a single time system globally, the Selfish Miner's private block should not be seen as valid if it has no pre-broadcasted Merkle tree.

This precautions essentially makes everyone can announce a block no faster than a certain speed, so that we can constrain the centralization of Bitcoin mining power.

The interesting points of this solution are to minimize the advantage of the low latency connection of the selfish miner.

When the part of a block that must be rapidly broadcast is reduced to less than 100 bytes (regardless of the actual size of the block), propagation times are going to be so low that selfish miner will have a more difficult time responding in time to pull off the attack.

The high-frequency-trading industry begs to differ.

Their proposed solution, which is offered without extensive analysis, is to relay all blocks, even late ones, and then choose the preferred block in ties at random. Ignoring collateral vulnerabilities which a hasty implementations of forward-all might create, I believe this proposal has a problem in that it creates a selfishness advantage even without any sybil attack at all, so long as the selfish miner has enough hashrate.

The high frequency trading industry operates within a few mile radius, because what they do is sensitive to speed-of-light delays.

That doesn't work as effectively when mining is spread out all over the globe.

1) Make the nonce long enough that the extraNonce field is no longer needed in the coinbase transaction.
2) Now it's possible for miners to broadcast their Merkle tree as soon as they start hashing (10 minutes on average before they finish)
3) When they find a valid hash, now they only need to broadcast the block header because the rest of the network has (usually) already received and validated the Merkle tree.
4) Block header propagation is very fast and not dependent of the size of the blocks.

3) Once difficulty falls, the lower difficulty is open to all.

Would I be right in thinking that this attack is made easier by Bitcoin's rather relaxed approach to timestamps?

Would incorporating the lexicographical ordering of all timestamps help when choosing between chains?

No. Timestamps don't come into this at all. (And most suggestions to tighten timestamps result in (usually minor) vulnerabilities)

Not in the slightest.

Why not? It penalises those who hold back blocks. I'm not saying this doesn't lead to other problems, but simply saying "not in the slightest" without elaborating isn't very helpful.

I believe thats missing the point. The honest miners are being orphaned much more often than the selfish one. The new difficulty isn't "open" to you when you're being disproportionally orphaned.

1. You solve a problem and create several others which are significantly more intractable. Bad engineering.

Changing the header is absolutely not required to pre-forward the block. You simply pre-forward it along with a pointer to where the extra nonce goes, and when you solve it you send the resulting timestamp,nonce,extra nonce for substitution— even less data than the header in the most efficient case.  P2Pool already implements block pre-forwarding (though not that aggressively: rather than deny the ability to add transactions, it preforwards transactions and then sends the Merkle tree+header+extranonce) .

However, "10 minutes on average before they finish" isn't right... the whole network produces a block in that time, not each miner. Sending data only once every block per miner, instead of incrementally, would also massively delay transactions— the delays is not something we should encourage. Preforwarding also uses a LOT of extra bandwidth, because each non-successful miner is constantly broadcasting block data too.

In any case, I think making block propagation faster is useful generally— but you don't need to change _anything_ about Bitcoin to do it. You just need to make a little fast-block-daemon which runs its own protocol to relay blocks and that could be run in parallel to the current p2p network.

It's almost a bit orthogonal though, since a better positioned miner still has a _latency_ advantage. Making the data smaller doesn't beat the speed of light.

What other problems would it create and why are they more intractable?

Despite the overhyped headline, this paper is important. It's part of a (long past due) movement towards modeling "rational participation" in Bitcoin. We are (surprisingly?) in a blind spot here as far as theoretical foundations go (the 30+ years of research in distributed systems, game theory, etc., have not looked at anything resembling Bitcoin). We do not yet have a sound way to argue that "Bitcoin (or X variant thereof) surely works," nor any impossibility results saying "nothing resembling Bitcoin can ever work."
 
Main points:
- Bitcoin is clearly *intended* to be incentive-compatible and encourage correct behavior. However the whitepaper only gives a proof for the "51% honest" model, which is unrealistic/trivial (if we just assume everyone's honest, there's no need for rewards in the first place). Even in this easy model, Bitcoin is novel among byzantine consensus protocols. Academics *should* have worked on this twenty years ago, but missed it! (except for this 2005 tech report (http://www.cs.yale.edu/research/techreports/tr1332.pdf))
- Practically speaking, we still seem to have a while to figure this stuff out before any systemic economic collapse will manifest. Even the mining pools still run bitcoind, not RationalMiner software. For the time being, majority honest is a reasonable approximation.
- Even if a 51% majority has limited ability to profit or attack, a systematic trend towards enabling 51% attacks would be a design flaw and existential threat. So we really need to find and fix things like this.
 
This paper fits neatly into a class of papers/posts that point out a particular way in which Bitcoin is not incentive-compatible (to call it an *attack* is just cyberhype), yet a simple fix (typically just to the messaging layer) is often at hand.
- Bitcoin and Red Balloons (https://research.microsoft.com/pubs/156072/bitcoin.pdf). There's no incentive for peers to relay transactions. Solution: bribe your peer conditional on the transaction getting accepted, now it's their problem too.
- This paper: If a mining pool is confident in its ability to detect and out-propagate competing blocks, then it can profit by witholding blocks until the last minute, making everyone else waste work. Solution: relay faster so no peer can get this advantage, or use random tie-breaking so this attack can't be pulled off consistently (the following two examples are me plugging my own posts). Regardless of propagation, a miner with more than 33% of the network's hashpower can profit disproportionately by witholding one block at a time. [edited, due to author pointing out this was oversimplified].
- https://gist.github.com/amiller/cf9af3fbc23a629d3084 An anomalously large single transaction fee would encourage miners to fight over the previous block, rather than building on each other's work. Solution: remove the 100-block coinbase maturity rule, which actually prevents a simple cooperative equilibrium where you take a cut of the huge fee for yourself and leave the rest for the next miners to fight over.
- https://bitcointalk.org/index.php?topic=309073.0 Natural economies of scale mean that "outsourced hosted mining" will be more cost effective and might drive out other participants, leading to more centralized control of resources, susceptible to coercion etc. Solution: a modified puzzle using (efficient) zero-knowledge proofs would make hosted mining (and mining pools, incidentally) impractical.
 
There are other similar "attacks" along the lines of "this may be a problem when people eventually run RationalMiner rather than HonestSatoshiReferenceClient", but for which the solutions are less obvious...
- Feather forking: https://bitcointalk.org/index.php?topic=312668.0  a small cartel of miners that want to enforce a transaction black-list could easily make it so that rational participants indifferent to the blacklist would rather appease the cartel than resist it. Possible solution: Adam Back is thinking very hard about how to make miners verify the correctness of transactions without learning anything else about them.
- Kroll. et al (http://www.weis2013.econinfosec.org/papers/KrollDaveyFeltenWEIS2013.pdf): Following *any* of the rules is at best a *focal point*, and slight rule tweaks like inflating the 21 million limit (just by a little bit) are probably a lot more plausible and easier to pull off than most people think. Possible solution: no idea
 
But we're still just scratching the surface of incentive-alignment glitches like this. Bitcoin will overcome the problems with easy fixes. I hope (but am skeptical) that if there's a bigger fix required, we can work it out and adopt it without waiting until it's too late and having to restart from scratch.
 
Above all, I wish we had a strong theoretical model we could use to knock out entire classes of problems rather than pointing them out and patching them one at a time. By analogy, the academic cryptography community did such a great job of moving from ad hoc ciphers to "provable security" that the mainstream security mantra is "don't roll your own crypto" unless you've proved a theorem first. Maybe someday they'll say the same thing about rolling your own incentive-consensus protocols. But the work hasn't been done yet, and we're currently still in the dark ages.

...
Low latency connection itself is expensive, and we can nullify its advantage by relaying unverified block headers. People will always assume a block header is valid unless it is proven otherwise, and always mine on top of the first seen header. (I think creating invalid block header is very expensive and no one is trying to do this. Any stats for this?)
...

1) Make the nonce long enough that the extraNonce field is no longer needed in the coinbase transaction.

2) Now it's possible for miners to broadcast their Merkle tree as soon as they start hashing (10 minutes on average before they finish)

3) When they find a valid hash, now they only need to broadcast the block header because the rest of the network has (usually) already received and validated the Merkle tree.

4) Block header propagation is very fast and not dependent of the size of the blocks.

Whatever though. Continue to get yourselves worked up about an erroneous result.

what part of my post indicated that I was "worked up"?

The paper does not consider multiple selfish mining pools fighting against one another.

For simplicity, and without loss of generality, we assume that miners are divided into two groups, a colluding minority pool that follows the selfish mining strategy, and a majority that follows the honest mining strategy (others).

It's not possible for pools to do this without miner cooperation - for example, by them using the stratum protocol. As long as miners are taking advantage of the GBT protocol (https://en.bitcoin.it/wiki/Getblocktemplate), this attack is not possible since the miner finding the block will announce it to the network themselves.

Which is fine so long as Bitcoin's central bank's client remains the defacto standard. As other mining strategies are discovered there will be ore and more clients available running forked mining code.

Which is fine so long as Bitcoin's central bank's client

Huh?

You are surely aware that the organisation that controls (writes and maintains) the Bitcoin client used by the majority basically controls Bitcoin.

You are surely aware that the organisation that controls (writes and maintains) the Bitcoin client used by the majority basically controls Bitcoin.

You are surely aware that the organisation that controls (writes and maintains) the Bitcoin client used by the majority basically controls Bitcoin.

I'm surprised you don't have this guy ignored already. Typical "everything about bitcoin is bad but I'm not going to understand what I am talking about" troll.

Now back to something interesting, like GBT. I didn't know you could use it to also push the block to the network yourself. Genius.

Would it be possible to reduce the centralised power from large pools through the following method?

- The pool simply provides the miner with the pool's payout address
- The miner can build whatever block they want, so long as it contains a coinbase output which pays the pool with amount (BLOCK_REWARD - MINER_BONUS).
- The miner bonus is a second output added to the coinbase transaction which the miner can pay to him/herself.  It could be 1% of the block reward or something like that.  This gives the miner a direct financial incentive to publish blocks they find immediately.
- The pool accepts the work from the miner so long as it contains the coinbase transaction that pays the pool.

* Possibly there could be some variation on this protocol so that the miner doesn't have to track transactions and build their own merkle tree.  Eg. the pool operator could provide a suggested merkle tree to the miner, and the miner just has to communicate any desired changes back to the pool operator, which reduces the bandwidth required.

This is essentially what GBT aims to do.

http://hackingdistributed.com/2013/11/04/bitcoin-is-broken/

From your perspective, if the Bitcoin community does not buy your bug fix,

you would be incentivized to selfish mine yourself and reap the benefits.

Do that and prove that Bitcoin is fragile. If it really is, then a newer, better one will appear.

If you do not do it, it means you're a fraud.

I have done some financial analysis to see how fast an attacker can get benefit from this attack. Let's the total network hashing rate is stable. At the beginning of the attack, he will always loss some mining revenue as the diff is fixed and he will lose some blocks when he is trying to broadcasting his double blocks. And his attack will make the growth of blockchain slow.

If the attacker owns 30% of the network hashing power, according to the formula of on the paper ten, he will make the blockchain grows 1.8x slower than if not attacked. Assuming 50% of the block attacker broadcasts accepted,  The revenue speed of the attacker will be influenced. He will loss 40% of his revenue if he had not attack, which is to make other honest miner mine even less and more slower. If the attack continues to next diff period, the attacker start to enjoy the benefit. He will earn more than 9% if he had not attack.


The attack invest 1.8*14=25 days time and 40% of the mining revenue (3600*25*30%*40%=10800 BTC, assuming still 25 btc per block), and he can earn more than 100BTC everyday, which earns investment in 111 days, during which time the whole community finds out his naughty behavior and make a hard-fork.

So, not a very wisdom attacker.

Please check whether my logic is right or wrong by independent calculation. Assuming the total net work hashrate is stable to make analysis simpler. First the attacker has to invest time and losing mining revenue to slow down other people, however the diff is fixed during the time, he is losing money to attack the network. The chain will grow extremely slower during the attack. The attacker suffers with other honest miner together, much longer than 14 days. If he is wealth enough and willing enough, Diff lowers, and he starts to harvest the benefit.  However, the time to make his investment back is very long, and before he can earn back his investment, the community will have already make a hard-fork.

Ideally I'd like to think about it carefully, read the paper a few times, and run some simulations before commenting, but I'll likely be tied up at the IETF all week and people are already panicking and pushing for hasty changes in response to this which may be ill-advised, so I'm going to offer some preliminary comments here.

+1

+1

This is the kind of analysis that I think we need more of before jumping to the conclusion that there is actually a problem that needs to be fixed. I'm not claiming that HorseRider is correct, but his logic looks plausible and I tend to listen harder to reasonable people who say things like "please check whether my logic is right".

Fresh coindesk article summarizing the situation

http://www.coindesk.com/bitcoin-mining-network-vulnerability/

Unfortunately, it seems to get many facts wrong too...

• The timestamp in the block header is entirely ignored, and the block-discovered-first isn't reported at all (nodes know which they saw first, and that's all they care about)
• No mention of the fact that there are many better sybil attacks should sybil-ing be possible.
• The proposed solution doesn't limit pools to 25% (this isn't even theoretically possible).

This paper is game theory fail.

Fail A
1) The benefit from selfish mining comes from future reductions in difficulty.
2) Until the reduction in difficulty happens, the selfish miner (like other miners) incurs losses.
3) Once difficulty falls, the lower difficulty is open to all. Some other selfish pool could step in and reap all the benefits. Socialized gains; private losses (and socialized losses). Doesn't seem rational unless you have some reason to believe that you can beat pools that copy the strategy. If you try to do the strategy and succeed in lowering difficulty, but ultimately some other pool comes out on top, then you will take losses.

Fail B
Some pools offer PPS. As long as these pools commit to keep up their PPS scheme, miners will migrate to these pools in the event of the attack. This causes the attack to fail. Sure the PPS pools bleed coin in the beginning, but in the end they end up with more miners and the attack gets resolved. If you put this in a economic model with switching costs [i.e. people stay at a pool unless there is a significant benefit from switching], the attack is a probably a net win for the honest PPS pools.
To retain miners, the attacker would need to switch to a PPS system as well. But then he is essentially creating bad luck and insuring people against it simultaneously. This attack is a surefire way to bleed coin.

Combine this with Fail A and you can see that the entire paper is fail.

This process runs away and leads any pool  that starts with >33% to end up with >50%, at which point the classic 51% attack becomes possible.

Please do run your simulations.  When you do, make sure that you faithfully simulate a network with latency.  The word latency exists in their paper exactly one time, as a casual aside in the solution section, which should immediately set alarm bells ringing in all of our heads.  In addition, they seem to suffer from the strange notion that work in bitcoin can be wasted. 

Let me start with latency.  As far as I can tell from the paper, their "simulation" (and here you should imagine me doing very sarcastic air quotes) involves a network where the evil miners have magically found a way to detect the competing block in the honest miner's memory, before it has begins to spread on the network.  Gamma seems to play some sort of role here, but the meaning of it seems to change from page to page.  Or at the very least between pages 8 and 11.  Can anyone give me a good justification for abusing this poor variable in this way?

The charts are very illuminating.  In figure 2, each of the simulation points is exactly on the calculated line.  This is a dead giveaway.  The only way that can happen is if their model is fully deterministic except for mining function.

The real gold of this paper comes on page 13.  On page 13 they handwave over the latency issue by pointing out that an attacker could insert itself between every other node on the network.  Let me just sum up a few years of discussion on this topic...

Of course, everyone instantly sees how silly that is, so they had to dress it up in pseudo-scientific gibberish so that people would click on their crappy website and check out the douchebag's glamour shot.

So that's the 51% attack mentioned in Satoshi's paper. I can't see any originality here

You need to model this as a dynamic game with entry and exit. They do not do this. The methodology is inappropriate to the problem at hand. They are not qualified for this. This is an industrial organization problem, not a computer science problem.
Done appropriately you would almost certiainly end up with multiple equilibria and sensitivity to assumptions about entry costs for pools and switching costs for individual miners. Game theory tells you very little of use for these types of problems.

You need to model this as a dynamic game with entry and exit. They do not do this. The methodology is inappropriate tIn any case, this is all artificial since there are ways of achieving the same aim without any upfront cost. It is hard to sensibly analyze a costly attack approach when cost-free attack approaches that achieve the same aim are available.

Consider a loyalty program where you record each worker's cumulative contribution to the pool. In the event the pool acquires 51%, you divide the 50% of surplus attack revenue according to some function of current hashing power and historical contributions. The loyalty program has no upfront cost at all. As long as the attack has a nonzero chance of succeeeing, the dominant strategy is to always join the pool. The more people join the more attractive joining becomes.

If it were an interesing problem, yes. But it is not an interesting or relevant problem.

The upfront cost comes from yielding fewer blocks than average and either driving rational miners to PPS pools (and thus failing) or subsidizing miners by offering PPS yourself. 

As stated earlier, I agree that the existence of PPS pools makes this attack much less viable. But the existence of (reasonably priced) PPS pools is an assumption. Nothing in the protocol requires or guarantees it.

It is allowed by the protocol. That is all that is needed. I don't understand the use of game theory in computer science. It is always an attacker vs. A bunch of honest chaps who sit by and let themselves get fleeced. If someone can pop up and say "hey, honest chaps, let's take shelter in that cave. We will be better off and safe if we all go together." Then it's reasonable to guess that this is actually what will happen.

The problem is when there is an attack with no effective countermeasures. As in the true 51% attack. You know, the one that is actually a real problem.

If I boot up my multi TH mining rig and start mining blocks from the genesis block onward, is my work not wasted? Does it contribute to network security? Will I earn any block rewards for the blocks I mine? As far as the rest of the network is concerned, I might as well not exist.

I have taken a look and cannot for the life of me understand what is confusing you. Gamma is defined quite clearly:"We denote by gamma the ratio of honest miners that choose to mine on the [selfish] pool's block, and the other (1-gamma) of the non-pool miners mine on the other branch." The variable is consistently used with this meaning. And your assertion that "the evil miners have magically found a way to detect the competing block in the honest miner's memory, before it has begins to spread on the network." is plainly false. The situation that you describe would correspond to a gamma of 0 (the worst case). But even when gamma is 1 (i.e. "the honest miners have magically found a way to always work on the honest block in the case of a tie") the attack works for an attacker with >33% of network hash power. I find the researchers' claim that a gamma of 1 is attainable by an attacker in the current bitcoin network to be tenuous at best, but this is not that important, since the attack works even for the best case where gamma=0.

BS I replicated this result and I can guarantee you that the mining function is not deterministic. Besides, your premise is laughable. How accurately can you really read that chart? Enough to say that the simulated results are within 1% of the predicted values? 0.1%? You can easily get simulation results accurate to a fraction of that in a modest amount of time on a dated single core machine. I know because I tried.

Strawman. Nowhere on page 13 do they suggest that or anything that I can interpret as being equivalent to an attacker being required to "insert itself between every other node on the network". If you disagree please post the relevant quote. As stated earlier, I find their assertion that gamma close to 1 is attainable to be tenuous, but this is just a misrepresentation of their position.

But a savvy pool operator can perform a sybil attack on honest miners by adding
a signicant number of zero-power miners to the Bitcoin miner network. These
virtual miners act as advance sensors by participating in data dissemination,
but do not mine new blocks.

Real mature. This is peer-review, is it?

Lear, who has independently done much higher-quality research on the same issue, has posted a sample of his results:
https://bitcointalk.org/index.php?topic=325824

I recommend staying tuned for his complete work, which can serve as a more fertile ground for further discussion on 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.

"every other node" was hyperbole, but not far off from what it would really take.  If the bitcoin network was laid out like an efficient mesh on a flat sheet, you wouldn't need many sensors.  But the bitcoin network is tangled up like a wad of Christmas lights.

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. ::)

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?

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.

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

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?

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.

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.


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.

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.

So, how long before these idiots make a public apology/resign?

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.

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.

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.

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

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

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.



 

Here is the tweet about selling bitcoins: https://twitter.com/el33th4xor/status/397219415025934336

It is clear now they are not acting in good faith. Apparently they have no idea at all there's something wrong with their extreme arrogance and spreading factual lies and FUD.

They can't even get their lies straight between the two of them - https://twitter.com/el33th4xor/status/397827176759697408

I am an academic myself and I think telling people to sell their bitcoins definitely crosses a line when it comes to intellectual discourse.

I wonder if Cornell professors are accountable for lapses in ethical academic behaviour?

Call me old fashioned but I thought a research paper normally involves research (here: discourse with core dev), and also involves peer review before publishing. Or has Cornell abandoned such archaic practices?

I wonder if Cornell professors are accountable for lapses in ethical academic behaviour?

Even though it's a little taboo to mention, the truth is: Bitcoin's developer abandoned the project years ago and disappeared into thin air. If he was still around he would be actively evolving the coin and addressing issues like this one in a clever manner. Bitcoin without Satoshi is like Apple without Jobs.

To my understanding, the only coin actively developing a 51% defense is Goldcoin whose developer is actively building upon Satoshi's unfinished work.

Even though it's a little taboo to mention, the truth is: Bitcoin's developer abandoned the project years ago and disappeared into thin air. If he was still around he would be actively evolving the coin and addressing issues like this one in a clever manner. Bitcoin without Satoshi is like Apple without Jobs.

To my understanding, the only coin actively developing a 51% defense is Goldcoin whose developer is actively building upon Satoshi's unfinished work.

...
Low latency connection itself is expensive, and we can nullify its advantage by relaying unverified block headers. People will always assume a block header is valid unless it is proven otherwise, and always mine on top of the first seen header. (I think creating invalid block header is very expensive and no one is trying to do this. Any stats for this?)
...

Let's just hope it's not the same developers responsible for keeping this forum running. J/K :P

For example, in the Prisoner's Dilemma, both players cooperating is not a Nash equilibrium. The only Nash equilibrium is given by both players defecting, which is also a mutual minmax profile. The folk theorem says that, in the infinitely repeated version of the game, provided players are sufficiently patient, there is a Nash equilibrium such that both players cooperate on the equilibrium path.

Thank you for your analysis. That's what I felt from the beginning about that "strategy". Miners do not care (so much) about the number of coins they get than about the number of stuff they can buy with them.

However, does it apply to someone who wants to destroy Bitcoin ?
Is it easier with this strategy than with a traditional "51% attack" ?

In my opinion, bitcoin cannot survive if the US gov't decides to take the ax to it.

Don't you think that also depends on what the EU, Russia and China do?

So you admit not knowing who the Bitcoin developers and the forum admin are and state that Bitcoin is "abandoned" a few posts apart?

What I said was, "Bitcoin's developer abandoned the project years ago and disappeared into thin air". I think this is a well-established fact.
[/quote

And his replacement went running straight to the CIA

I dunno. I guess I expect the EU to go along with whatever the US says.
I expect China to ban bitcoin if/once it gets really big regardless of what happens elsewhere.
I don't fell informed enough to speculate about the rest of the world.

Just to be clear i don't think the us will ban bitcoin. Say what you like i still believe that the us provides the world's leading environment for innovation. They are not so stupid as to fuck this up.

Probably. But it was never very difficult to begin with. Moreover there are other ways of destroying bitcoin that make much more sense.

Say I'm the US gov't out to destroy bitcoin.

Step 1) Make it illegal and start rounding people up. Watch price plummet.
Step 2) Buy up hardware and conduct 51% attack on the cheap to neutralize remaining participants. [Once price plummets the used ASIC devices will be very, very cheap.]

In my opinion, bitcoin cannot survive if the US gov't decides to take the ax to it. I don't think this is going to happen. I also don't think that it will make sense for a private actor to do this. (many different guys will benefit from burying bitcoin, but they are not going to be able to coordinate an attack aside from lobbying gov't. Going it alone and destroying bitcoin is not going to be sufficiently profitable to any one company to make it worthwhile.)

The bigger danger is the falling block reward. If this is not addressed, it will cause problems in the long term (i.e. say starting 10 or 20 years from now).

I'd like to think that people will agree to proof of stake before surrendering bitcoin to government or corporate management, but you may be right. People are extremely stubborn and consensus is a damned hard thing to obtain.

Proof of stake has thus far proven unworkable.

The main problem with Proof of Stake appears to be that is that there is nothing at stake:  In PoW systems you burn energy to mine, and that mining is only worth while if the chain your mining on survives long term, so you are generally incentive mine the chain most likely to survive. In PoS the rational strategy is to mine all possible forks constantly, because doing so costs you nothing.

That page is pretty embarrassing.   There is absolutely no mention of the fundamental flaw in PoS consensus which none of your proposals have addressed:  As of yet none of the proof of stake proposals are workable because there is nothing at stake!   If someone is PoS mining it is in their best interest to attempt to concurrently build an honest chain as well as all possible attack forks just in case one of them happens to win.  Under most schemes this is the profit maximizing move, in all I've seen so far its at least neutral.  Mining an attack under PoW actually involves _spending_ something and taking the risk other miners will extend it. PoW works because your work is at stake so even a very small amount of honest miners make mercenary rational miners behave honestly too.

Moreover, I don't see why you argue here that it better aligns incentives. Parties can't mine PoW without having a validating node (or face the extreme risk other miners will toss them off on forks).  All it does is redistribute control, which might be useful— if not for the fact that it makes attacking more attractive for selfish participants.   I was hopeful of these techniques but as of yet I don't see how any can be workable.

Probably. But it was never very difficult to begin with. Moreover there are other ways of destroying bitcoin that make much more sense.

Say I'm the US gov't out to destroy bitcoin.

Step 1) Make it illegal and start rounding people up. Watch price plummet.
Step 2) Buy up hardware and conduct 51% attack on the cheap to neutralize remaining participants. [Once price plummets the used ASIC devices will be very, very cheap.]

In my opinion, bitcoin cannot survive if the US gov't decides to take the ax to it. I don't think this is going to happen. I also don't think that it will make sense for a private actor to do this. (many different guys will benefit from burying bitcoin, but they are not going to be able to coordinate an attack aside from lobbying gov't. Going it alone and destroying bitcoin is not going to be sufficiently profitable to any one company to make it worthwhile.)

The bigger danger is the falling block reward. If this is not addressed, it will cause problems in the long term (i.e. say starting 10 or 20 years from now).

Proof of stake has thus far proven unworkable.

The main problem with Proof of Stake appears to be that is that there is nothing at stake:  In PoW systems you burn energy to mine, and that mining is only worth while if the chain your mining on survives long term, so you are generally incentive mine the chain most likely to survive. In PoS the rational strategy is to mine all possible forks constantly, because doing so costs you nothing.

My proposal very clearly and explicitly penalizes stakeholders who try to sign conflicting blocks. This line has been there for 1.5 years - "If an address signs two conflicting blocks, its weight is reset to 0. This is to limit the power of malicious stakeholders. "

I'm not saying this will work perfectly, but to claim that no consideration has been made to this issue is, as cunicula says, dishonest.

Research into PoS methods is still ongoing.

Recently, a dire prediction came out from a couple of computer science researchers about bitcoin's security. Game theory says  'We're all Doomed' or so they claim.

This is eerily similar to what happened when game theory was first applied to the study of nuclear war. Early researchers modeled nuclear war as a winner take all game. In this story, once a nuke drops, one of players is erased from the map. Game over for them. If you face certain and immediate obliteration, the only workable strategy turns out to be a pre-emptive strike. The CIA found this quite alarming!

Later, as the study of games became more advanced, the model was tweaked to add a bit of realism. Instead of obliterating the enemy, the nuke just harms them and they have an opportunity to strike back in the next round. With this simple twist, the game becomes like "Groundhog Day"; there is never any end to it.

When we play a game over and over again new kinds of strategies emerge. The most familiar one is tit for tat retaliation. "If I got nuked last year, I'll nuke back this year. If I didn't get nuked, then I won't nuke back this year."
This strategy is both familiar in everyday life and famous in theory. That's because it works. Under tit for tat, you can avoid getting nuked by maintaining an arsenal, but never using it.

Okay, so what about bitcoin. The authors of "Majority is not enough..." analyze bitcoin as a static one-off game just like early researchers considering nuclear war. Unsurprisingly, they issue dire predictions. In their one-off world, there is never any way of retaliating against bad actors. Players just pick between "attack" and "honest." It should be no surprise that the unconditional pacifist strategy is never successful. Indeed, always attack is the only possible equilibrium in a one-off setting.
Most people can see this intuitively, even if they have never studied game theory.

Let's add in some realism. In particular, let's think about mining every day instead of just as a one-off event. This allows for retaliation. Suppose instead we play, "if some anonymous guy fucked us by playing selfish yesterday, then we will also play selfish because it makes no sense to keep getting fucked." and "if no one played selfish yesterday, then we will play honest."

This strategy (where we condition actions on previous play) is an incentive compatible subgame perfect nash equilibrium. Yes, you heard it, the authors' claimed key contribution is erroneous and stems from a fundamental and elementary misunderstanding of game theory. Cooperation is sustainable as long as we retaliate against the bad guys.

Now, wait you say, we don't know who the bad guys are. How can we retaliate? This is the magic point. We don't need to know who the bad guys are to hurt them. If 25% of hashing power is doing selfish mining, we may not know who the bad guys are, but we do know that they own an ASIC (unless you think 25% of ASICs can be simultaneously liquidated within a single day at fair market value). The ASIC they own is valuable. When we play selfish, we turn into a paperweight. And that is how retaliation works. Players respond to selfish play by turning selfish and this causes all ASIC owners to take capital losses. The market value of their equipment depreciates with bitcoin prices. Ownership of ASICs means that miners cannot help but have a permanent stake in the system. 

Now, wait you say, this will also hurt innocent players who were not involved in the attack. Even though retaliation harms innocent people, it is still the best option for people who have been attacked. War hurts innocent people. But fighting back is the only possible equilibrium response after an attack occurs (one can set a threshold for a response, but there's always a tipping point where rational people have had enough and choose to fight back.)

Okay, so let's review and make things more concrete. Let's see. Say there is some consensus threshold for a 'successful attack.' You can ask Gavin exactly what the threshold is. Maybe we'd allow him to determine this. I would guess it is around the level that makes a short-term attack earn positive profit.

Consider a miner's options:

If I join an attack and the attack succeeds, tomorrow and the day after that and possibly for all days following we will have selfish mining. Should I care? Yes, today, my ASIC is expensive. Not worth a day of profits, if tomorrow all I have left are a day's worth of selfish mining income in USD and a brand new paperweight.

If I join an attack and the attack fails, then tomorrow we will still have happy days, but I will not have gained any short-term profit from participation. In fact I will have lost revenue. So clearly this is also a no go.

That leaves us with the last option: honest mining. Assume that everyone else approached the problem like me. You can see by reading most comments that they do (even if they don't formally understand why).

If I do not join an attack, then I will earn a fair profit and, as long as everyone else has approached the problem rationally, then tomorrow we will have more happy days of honest mining. And the next day too and the day after...

So what's my dominant strategy? Be honest until someone attacks me and then retaliate as necessary. There are many different sustainable ways of organizing retaliation besides tit for tat. Norms on how to retaliate vary across societies. I trust that the community, and Gavin in particular, could make reasonable judgements on this front. And that is all we need to succeed.

tl;dr bitcoin only has to worry about terrorists; rational miners will never attack, ever*. *(as long as there is modest mining reward)

If you'd like to see some math on this topic, then check out:

http://www.scribd.com/doc/182399858/Cunicula-s-game-theory-primer-pdf

PS. I could use help on the authors' site, 
hackingdistributed.com

The author is aware of my critique, but is refusing to respond. In fact, he deleted the link to my pdf the first time I posted it. As a community, I'd appreciate help in demanding a response from him. Go to the blog and ask questions about how repeated play and retaliation affect his results. When you see these questions, upvote them.

If the community will not help, then I will have to go the long route of posting a formal academic comment on arxiv. This is time consuming. Because I am an economist, arxiv has no positive benefits for my reputation or career. I'm asking for some help so that we can get this addressed in the media and blogosphere without a prolonged academic back and forth.

I understand how the weight is reset to 0. But I can't understand how signature fees will be distributed.
If there's a thread discussing it, please point it to me. Thanks.

The main problem is the BTC loosers, the people that had a sizeable amount of BTC stored and that now have nothing. It will then be time to steal it or to sell them anything for BTC or to retaliate somehow. So no, Bitcoin mining is not vulnerable. Bitcoins are a risky investment.

I don't think even the authors claim this attack can be used to take bitcoins away from those who already have them.

I think you mean you don't do that.




This is not a new idea at all.  As far as public postings, it's been on this page on the bitcoin wiki (https://en.bitcoin.it/wiki/Thin_Client_Security) for at least six months, and there was definitely a mention of it on bitcoin-dev about a year ago (I will post the reference when I find it).  And, as I've mentioned, it's pervasive in the modified clients used by large mining operations, although those are not public so you're welcome to shout "liar liar pants on fire" all you like and I won't get upset :)



I think the people who wrote this paper took Satoshi's original whitepaper too literally:


Mining strategy has evolved and adapted, as it must in any incentive-driven system.  For example, Satoshi's whitepaper predicted that transaction fees would be a meaningful incentive, and it's pretty obvious it hasn't turned out that way.

So this is more of a miners issue right?  How are orphan block rewards handled now?  What I mean is if I solve a block and get the reward and go gamble it at satoshi dice immediately does this "attack" somehow nullify that block reward afterwards and basically I succeeded at a double spend?  Or the block never hits the blockchain and the "attack" is designed for me to waste my hashing power?

As I understand it, the block reward cannot be spent right away.  There have to be a certain number of blocks built upon it, 6?, before it can be spent.

1: If the solution were to randomize what chain to work on in a tie, why wouldn't the selfish pool
try to create multiple chains by having subpools work on finding hashes for separate blocks?

2: In general, holding on to a block for some period after finding it, looks like a potential advantage
is working on the next block.  Why not have all the nodes do this as normal operation?