the Block Discarding Attack / shellfish mining

[King Lear]

Dear community of Bitcoiners,

My name is Lear Bahack and I am an Israeli student for mathematics working lately on Bitcoin security analysis and possible constructions of pure proof-of-stake crypto-coins.

Today I had to pinch myself several times because I felt like I am in a bad dream: several months ago I thought of two less-than-50% hash-power theoretical attacks, and waited quietly until November 13th, the IEEE Security and Privacy conference submission deadline. Meanwhile another team has publicly published a simultaneously obtained research, regarding my "Block-Discarding-Attack" which they call shellfish-mining.

The authors propagated their independently obtained results in a rush, in order to make artificial panic around the world. Intentionally misleading blog post written by the authors and titled "Bitcoin is Broken", claims that a pool having 25% of the total hash power can destroy the Bitcoin system right now. Well, this is simply untrue. I can only hope the authors did so in order to promote their first-published paper and not as a way to make easy money, by exploiting the volatile exchange rate.

So there are several things need to be said:

1.   First of all, the attack is not new. Both me and the other researchers independently discovered the attack on 2013, however the idea have been tracked to a thread of this forum as early as 2010: https://bitcointalk.org/index.php?topic=2227.msg30064#msg30064, https://bitcointalk.org/index.php?topic=2227.msg30083#msg30083.

The idea has long being forgotten since it was obvious to this thread's participants that the idea is definitely unpractical.

A careful mathematical analysis done recently by both me and the other researchers shows that a solo miner with more than 25% of the total hash power and a magical ability to propagate her/his block faster than all other miners, will be able to make mining for the honest miners unprofitable, and theoretically become the only miner.

Although of highly theoretical importance, the Block-Discarding-Attack / Shellfish mining strategy is not an actual threat!

2.   The attack is based on secretly holding new mined blocks while trying to mine the next block on top of a secret one. Hence, it is obviously not applicable to pools. A pool must share the secrete block with each of its anonymous members, that could be anyone including the blockchain.info website.

3.   As mentioned, I have found another completely different less than 50% hash-power attack, based on innovative idea I will publish soon. Moreover, my mathematical analysis shows that the shellfish-mining strategy is only a one of many block-discarding attack strategies, and that some of them are theoretically applicable especially to some alt-coins. Nevertheless I hereby declare that all attacks are of theoretical importance only!

4.   Arguably a Bitcoin protocol change should be made to countermeasure the Block-Discarding-attack. Although the threat is mostly theoretic, indeed it is better to be on the safe side. The other researchers suggest a possible change that will make all network nodes propagate any block they have received, even if there is more than just one. 

While this proposal is possible, I suggest a different solution aimed to punish the attacker who intentionally creating forks. My fork-punishment solution is simple to implement and is not based upon asking the users to increase their amount of transmitted data (which they have an incentive not to do).

Let's call a pair of two blocks mined on top of the same older block a "fork evidence". I suggest that a block composer that includes a fork evidence as part of his/her block, where one of the evidence forked blocks is a predecessor of the newly composed block, will be rewarded half of the reward goes to the forked block, and the forked block owner will be totally disrewarded.

This option should obviously be limited to, say, 10 blocks ahead of the fork. This way the reward will not be frizzed longer than it is frizzed now, and an attacker from the future having an improved hash-rate with respect to the past, will not be able to easily create forks and get rewarded.

Attacker (from the present) will have no immediate incentive to artificially make forks since she/he is expected to lose at least half of a block-reward per a fork. However, attacker willing to temporary loses a lot for performing eventually profitable attack, can still do so theoretically.

5.   Although I am much frustrated about it, I acknowledge the fact that the other researchers published their results first. We should all respect them for that, although I hope the next time a theoretical attack will be found, researchers will not publish misleading information but the most accurate information.

I will be posting here soon about my improved results. Meanwhile I will just say don’t panic. We have no reason to

Lear. 

[King Lear]

Technically I am a newbie, so unable to post this text at a more appropriate forum, such as the technical forum. Will it be possible to transmit this thread out of the newbies forum? it was written mainly to the technical-oriented audience.
Another possibility is if someone seeing this thread will kindly agree to copy-paste it to a new opened thread on my behalf.

[tacoman71]

Seems interesting. So basically we have to worry about a 25% attack now?

[tacoman71]

Isn't this the same attack discovered by Cornell students? http://arxiv.org/pdf/1311.0243v1.pdf

[balanghai]

Thanks for sharing this! I'm almost certain that some of the news circulated about bitcoin is only made to take advantage of the volatility and thus making it easier for them to outwit regular traders.

[greyhawk]

Hmmmm, shellfish. Now I'm hungry.

[grich]

I suggest that a block composer that includes a fork evidence as part of his/her block, where one of the evidence forked blocks is a predecessor of the newly composed block, will be rewarded half of the reward goes to the forked block, and the forked block owner will be totally disrewarded.

....

Attacker (from the present) will have no immediate incentive to artificially make forks since she/he is expected to lose at least half of a block-reward per a fork. However, attacker willing to temporary loses a lot for performing eventually profitable attack, can still do so theoretically.

You can't say "reward" for orphan blocks: you get the reward only for the blocks in the main chain.

Suppose Attacker and Network are in race. 1) If Attacker already has the second block in his sleeve (without the evidence of the fork) he publishes it and wins the race, taking full reward for both blocks. By the rule of cummulative work, everybody switches to that branch. 2) If Network finds the second block first -- Attacker gets nothing irrespectively of the evidence's presence in that block.

[ShadowOfHarbringer]

Professional shellfish with delivery, always on time !

[Meni Rosenfeld]

I can confirm that Lear has discussed with me the results of his research a day before the paper by Eyal and Sirer was published.

I suggest that a block composer that includes a fork evidence as part of his/her block, where one of the evidence forked blocks is a predecessor of the newly composed block, will be rewarded half of the reward goes to the forked block, and the forked block owner will be totally disrewarded.

If I understand this correctly, some coins will be destroyed in the process, which is not what we want.

[gyverlb]

I can confirm that Lear has discussed with me the results of his research a day before the paper by Eyal and Sirer was published.

I suggest that a block composer that includes a fork evidence as part of his/her block, where one of the evidence forked blocks is a predecessor of the newly composed block, will be rewarded half of the reward goes to the forked block, and the forked block owner will be totally disrewarded.

If I understand this correctly, some coins will be destroyed in the process, which is not what we want.

My understanding is that half the coins from the "forked block" would change hands so they won't really be destroyed (or maybe you don't write about value destroyed but actual txouts being destroyed?).

There are problems though:

• you'll probably have to invalidate all previous outputs (there's not always only one the block can distribute the reward to multiple addresses) of the previous blocks and recreate new ones, I'm not familiar with the bitcoin code enough to be certain but I think it can be a very invasive change (new opcodes? new logic for getblocktemplate?): quite risky
• some dust will be lost as some outputs wouldn't be multiple of 2 satoshis

These are only difficulties which can be overcome, the solution seems to make sense.

Edit: the dust being lost can be solved by giving one satoshi more one side of the split, so that's not really a problem.

[Meni Rosenfeld]

I can confirm that Lear has discussed with me the results of his research a day before the paper by Eyal and Sirer was published.

I suggest that a block composer that includes a fork evidence as part of his/her block, where one of the evidence forked blocks is a predecessor of the newly composed block, will be rewarded half of the reward goes to the forked block, and the forked block owner will be totally disrewarded.

If I understand this correctly, some coins will be destroyed in the process, which is not what we want.

My understanding is that half the coins from the "forked block" would change hands so there won't really be destroyed (or maybe you don't write about value destroyed but actual txouts being destroyed?).

There are problems though:

• you'll probably have to invalidate all previous outputs (there's not always only one the block can distribute the reward to multiple addresses) of the previous blocks and recreate new ones, I'm not familiar with the bitcoin code enough to be certain but Idestroyed think it can be a very invasive change (new opcodes? new logic for getblocktemplate?): quite risky
• some dust will be lost as some outputs wouldn't be multiple of 2 satoshis

These are only difficulties which can be overcome, the solution seems to make sense.

Edit: the dust being lost can be solved by giving one satoshi more one side of the split, so that's not really a problem.

I meant value destroyed, it looks like Lear is suggesting the whistleblower will get half and the original block finder will get nothing, which means half is destroyed.

The protocol says that coinbase needs to mature for 100 blocks before it can be spent, so there is no problem with changing the recipient before this time.

[cunicula]

Sounds like a reasonable assessment.

Very much looking forward to hearing about your work on proof of stake. If you ever have anything to circulate for comments, please let me know.
I am not trying to publish anything, so don't be concerned on that front. It's not a useful kind of publication for someone in the economics field.

[cunicula]

I meant value destroyed, it looks like Lear is suggesting the whistleblower will get half and the original block finder will get nothing, which means half is destroyed.

The protocol says that coinbase needs to mature for 100 blocks before it can be spent, so there is no problem with changing the recipient before this time.

If destruction is taboo, then you could always divide the destroyed coins across say the next 100 blocks as fees. It should be as good as destroying them for incentive purposes (if it isn't you have a 51% attacker and are surely already fucked).

[gyverlb]

I meant value destroyed, it looks like Lear is suggesting the whistleblower will get half and the original block finder will get nothing, which means half is destroyed.

You are right. I read again and obviously my initial reading was not careful enough.
That said there are 2 blocks in a fork with the same height if both blocks have 50% invalidated and 50% moved there won't be a loss of value at height+1. I'm not sure if it's what Lear describes.
In my opinion loss of value is a problem only if the loss changes the total amount of final BTC in existence. If the solution means that at a given height there wouldn't be any change of total coins created then I don't see a problem.

[Meni Rosenfeld]

I meant value destroyed, it looks like Lear is suggesting the whistleblower will get half and the original block finder will get nothing, which means half is destroyed.

The protocol says that coinbase needs to mature for 100 blocks before it can be spent, so there is no problem with changing the recipient before this time.

If destruction is taboo, then you could always divide the destroyed coins across say the next 100 blocks as fees. It should be as good as destroying them for incentive purposes (if it isn't you have a 51% attacker and are surely already fucked).

That should work but it's a deeper change. (I suggested something similar in https://bitcointalk.org/index.php?topic=80387).

[Sukrim]

By the way, the strategy was called "selfish" mining, in the sense of being selfish or acting in only one's own interest potentially on the expense of others.

2.   The attack is based on secretly holding new mined blocks while trying to mine the next block on top of a secret one. Hence, it is obviously not applicable to pools. A pool must share the secrete block with each of its anonymous members, that could be anyone including the blockchain.info website.

No, that is not the case - the only people that know that a winning nonce has been found are the pool operator and the person that mined this winning share. As there are a LOT of miners in a pool, it is highly unlikely that this is detectable by the miners themselves, unless they collude and check their nonces. The pool then can choose to reveal the block ("honest" miners are advised to do this as soon as possible to as many high hashrate miners as possible, sorted by hash rate - blockchain.info and other highly connected peers might only be useful to reach parts of the network you don't have a low latency, high bandwidth connection with). There is no way for a miner to know that a block was found or that the merkle root just changed because the pool server included another transaction.

Let's call a pair of two blocks mined on top of the same older block a "fork evidence". I suggest that a block composer that includes a fork evidence as part of his/her block, where one of the evidence forked blocks is a predecessor of the newly composed block, will be rewarded half of the reward goes to the forked block, and the forked block owner will be totally disrewarded.

This option should obviously be limited to, say, 10 blocks ahead of the fork. This way the reward will not be frizzed longer than it is frizzed now, and an attacker from the future having an improved hash-rate with respect to the past, will not be able to easily create forks and get rewarded.

Difficulty can have changed by up to a 4 times increase in the past 10 blocks...

Also this give a strong disincentive to communicate forks you know about to others, to reap the rewards. Also: Where does the reward come from?

5.   Although I am much frustrated about it, I acknowledge the fact that the other researchers published their results first. We should all respect them for that, although I hope the next time a theoretical attack will be found, researchers will not publish misleading information but the most accurate information.

Next time, I hope anyone bothering to write a paper first presents their findings here or with selected highly knowledgeable developers/members before doing the actual work of compiling something based on wrong or weak premises.

If Bitcoin really worked like they assumed in their paper, the attack really would work. It doesn't however and I hope your unpublished (but hopefully already discussed in private with several members here...) attack also takes into account how the actual Bitcoin network and it's miners are connected instead of assuming that sibyl attacks are easily possible.

[CIYAM]

By the way, the strategy was called "selfish" mining, in the sense of being selfish or acting in only one's own interest potentially on the expense of others.

It's a pity that the OP thinks that "shellfish" is more interesting (seriously OP - could you edit your title as it just looks plain silly).

[Meni Rosenfeld]

By the way, the strategy was called "selfish" mining, in the sense of being selfish or acting in only one's own interest potentially on the expense of others.

He knows. His ability to access the internet is poor and thus it can take some time for him to fix the typos and respond to comments.

2.   The attack is based on secretly holding new mined blocks while trying to mine the next block on top of a secret one. Hence, it is obviously not applicable to pools. A pool must share the secrete block with each of its anonymous members, that could be anyone including the blockchain.info website.

No, that is not the case - the only people that know that a winning nonce has been found are the pool operator and the person that mined this winning share. As there are a LOT of miners in a pool, it is highly unlikely that this is detectable by the miners themselves, unless they collude and check their nonces. The pool then can choose to reveal the block ("honest" miners are advised to do this as soon as possible to as many high hashrate miners as possible, sorted by hash rate - blockchain.info and other highly connected peers might only be useful to reach parts of the network you don't have a low latency, high bandwidth connection with). There is no way for a miner to know that a block was found or that the merkle root just changed because the pool server included another transaction.

The pool operator doesn't have to share that he found a block... But if he wants to carry out the attack as described, he needs to start mining on top of the block he just found. To do that he needs to submit to all of his miners a header that builds on the newly found block. So a pool-based attacker does need to share the hidden blocks with his miners.

Let's call a pair of two blocks mined on top of the same older block a "fork evidence". I suggest that a block composer that includes a fork evidence as part of his/her block, where one of the evidence forked blocks is a predecessor of the newly composed block, will be rewarded half of the reward goes to the forked block, and the forked block owner will be totally disrewarded.

This option should obviously be limited to, say, 10 blocks ahead of the fork. This way the reward will not be frizzed longer than it is frizzed now, and an attacker from the future having an improved hash-rate with respect to the past, will not be able to easily create forks and get rewarded.

Difficulty can have changed by up to a 4 times increase in the past 10 blocks...

I think that's a good point, we may need to tweak the whistleblowing reward to be balanced against the difficulty ratio.

In fact if we do rollover transaction fees, the whistleblowing reward actually can be very small.

Also this give a strong disincentive to communicate forks you know about to others, to reap the rewards.

I don't see how that's a problem.

Also: Where does the reward come from?

It's deducted from the reward of the block that has an orphan brother. That's actually the main point, disincentivizing creating forks.

[Sukrim]

The pool operator doesn't have to share that he found a block... But if he wants to carry out the attack as described, he needs to start mining on top of the block he just found. To do that he needs to submit to all of his miners a header that builds on the newly found block. So a pool-based attacker does need to share the hidden blocks with his miners.

Maybe this could be prevented in the future with homomorphic encryption, though I agree that it would be easy to register just a simple worker on all pools and then you know when they found blocks.

Also: Where does the reward come from?

It's deducted from the reward of the block that has an orphan brother. That's actually the main point, disincentivizing creating forks.

Could one then "wage war" against a pool by trying to fork their blocks? On the other hand, if you then create a fork, you also need to tell everybody else about it, so they actually do claim the forking reward or your work was in vain. You cannot even assume that the others will propagate the fork to miners you don't know until the first one that knows about the fork claims a reward as they will not want to tell each other... and then the reward was taken anyways.

100 blocks (or rather a number slightly smaller than this) might be a good time frame, as it is anyways not possible to spend anything from new blocks for this amount of time. I'm not too sure how reorganization events would be handled then though, especially with a split close to 50:50, where 2 chains compete over a longer period of time and dead forks suddenly become alive again.

[revans]

I can confirm that Lear has discussed with me the results of his research a day before the paper by Eyal and Sirer was published.

I suggest that a block composer that includes a fork evidence as part of his/her block, where one of the evidence forked blocks is a predecessor of the newly composed block, will be rewarded half of the reward goes to the forked block, and the forked block owner will be totally disrewarded.

If I understand this correctly, some coins will be destroyed in the process, which is not what we want.

Why not?


Seems fairly consistent with the deflationary ideology underpinning Bitcoin.