Bitcoin Forum
August 09, 2022, 07:30:37 PM *
News: Latest Bitcoin Core release: 23.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: 1 2 3 [All]
  Print  
Author Topic: the Block Discarding Attack / shellfish mining  (Read 28529 times)
King Lear
Newbie
*
Offline Offline

Activity: 23
Merit: 0


View Profile
November 06, 2013, 12:44:54 AM
 #1

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 Smiley

Lear. 
1660073437
Hero Member
*
Offline Offline

Posts: 1660073437

View Profile Personal Message (Offline)

Ignore
1660073437
Reply with quote  #2

1660073437
Report to moderator
1660073437
Hero Member
*
Offline Offline

Posts: 1660073437

View Profile Personal Message (Offline)

Ignore
1660073437
Reply with quote  #2

1660073437
Report to moderator
1660073437
Hero Member
*
Offline Offline

Posts: 1660073437

View Profile Personal Message (Offline)

Ignore
1660073437
Reply with quote  #2

1660073437
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1660073437
Hero Member
*
Offline Offline

Posts: 1660073437

View Profile Personal Message (Offline)

Ignore
1660073437
Reply with quote  #2

1660073437
Report to moderator
1660073437
Hero Member
*
Offline Offline

Posts: 1660073437

View Profile Personal Message (Offline)

Ignore
1660073437
Reply with quote  #2

1660073437
Report to moderator
1660073437
Hero Member
*
Offline Offline

Posts: 1660073437

View Profile Personal Message (Offline)

Ignore
1660073437
Reply with quote  #2

1660073437
Report to moderator
King Lear
Newbie
*
Offline Offline

Activity: 23
Merit: 0


View Profile
November 06, 2013, 12:56:53 AM
 #2

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
Sr. Member
****
Offline Offline

Activity: 320
Merit: 250



View Profile
November 06, 2013, 01:49:02 AM
 #3

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

Feeling generous? Like my post? Leave a tip at BTC: 1NZJ8cceqEiKDZGAJged2vNGCyfFMUEYPt
tacoman71
Sr. Member
****
Offline Offline

Activity: 320
Merit: 250



View Profile
November 06, 2013, 01:50:51 AM
 #4

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

Feeling generous? Like my post? Leave a tip at BTC: 1NZJ8cceqEiKDZGAJged2vNGCyfFMUEYPt
balanghai
Sr. Member
****
Offline Offline

Activity: 364
Merit: 253


View Profile
November 06, 2013, 09:21:52 AM
 #5

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
Hero Member
*****
Offline Offline

Activity: 938
Merit: 1009


View Profile
November 06, 2013, 10:18:43 AM
 #6

Hmmmm, shellfish. Now I'm hungry.
grich
Newbie
*
Offline Offline

Activity: 29
Merit: 0


View Profile
November 06, 2013, 10:22:50 AM
 #7

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
Legendary
*
Offline Offline

Activity: 1470
Merit: 1004


Bringing Legendary Har® to you since 1952


View Profile
November 06, 2013, 12:34:06 PM
 #8

Professional shellfish with delivery, always on time !

Meni Rosenfeld
Donator
Legendary
*
expert
Offline Offline

Activity: 2058
Merit: 1029



View Profile WWW
November 06, 2013, 12:36:11 PM
 #9

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.

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
gyverlb
Hero Member
*****
Offline Offline

Activity: 896
Merit: 1000



View Profile
November 06, 2013, 01:10:24 PM
 #10

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.

P2pool tuning guide
Trade BTC for €/$ at bitcoin.de (referral), it's cheaper and faster (acts as escrow and lets the buyers do bank transfers).
Tip: 17bdPfKXXvr7zETKRkPG14dEjfgBt5k2dd
Meni Rosenfeld
Donator
Legendary
*
expert
Offline Offline

Activity: 2058
Merit: 1029



View Profile WWW
November 06, 2013, 01:13:33 PM
 #11

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.

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
cunicula
Legendary
*
Offline Offline

Activity: 1050
Merit: 1003


View Profile
November 06, 2013, 01:33:46 PM
 #12

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
Legendary
*
Offline Offline

Activity: 1050
Merit: 1003


View Profile
November 06, 2013, 01:35:47 PM
 #13


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
Hero Member
*****
Offline Offline

Activity: 896
Merit: 1000



View Profile
November 06, 2013, 01:37:08 PM
 #14

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.

P2pool tuning guide
Trade BTC for €/$ at bitcoin.de (referral), it's cheaper and faster (acts as escrow and lets the buyers do bank transfers).
Tip: 17bdPfKXXvr7zETKRkPG14dEjfgBt5k2dd
Meni Rosenfeld
Donator
Legendary
*
expert
Offline Offline

Activity: 2058
Merit: 1029



View Profile WWW
November 06, 2013, 02:03:42 PM
 #15


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

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
Sukrim
Legendary
*
Offline Offline

Activity: 2618
Merit: 1006


View Profile
November 06, 2013, 02:57:39 PM
 #16

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.

https://www.coinlend.org <-- automated lending at various exchanges.
https://www.bitfinex.com <-- Trade BTC for other currencies and vice versa.
CIYAM
Legendary
*
Offline Offline

Activity: 1890
Merit: 1023


Ian Knowles - CIYAM Lead Developer


View Profile WWW
November 06, 2013, 03:00:21 PM
 #17

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

With CIYAM anyone can create 100% generated C++ web applications in literally minutes.

GPG Public Key | 1ciyam3htJit1feGa26p2wQ4aw6KFTejU
Meni Rosenfeld
Donator
Legendary
*
expert
Offline Offline

Activity: 2058
Merit: 1029



View Profile WWW
November 06, 2013, 04:31:08 PM
 #18

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.

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
Sukrim
Legendary
*
Offline Offline

Activity: 2618
Merit: 1006


View Profile
November 06, 2013, 04:54:11 PM
 #19

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.

https://www.coinlend.org <-- automated lending at various exchanges.
https://www.bitfinex.com <-- Trade BTC for other currencies and vice versa.
revans
Sr. Member
****
Offline Offline

Activity: 336
Merit: 250


View Profile
November 06, 2013, 04:56:57 PM
 #20

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.
Carlton Banks
Legendary
*
Offline Offline

Activity: 3276
Merit: 2844



View Profile
November 06, 2013, 05:07:48 PM
 #21

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.

Unless the operator owns a substantial amount of his pool's hashing power, but that starts to blur the lines of whether you call them a pool or a large solo miner with hangers on.

Puts the efficacy of the Discard/Selfish attack into even more questionable territory, as only large solo miners can hope to pull it off. And they also need to hope they can beat all odds of throwing away more good block solutions to honest miners than they can possibly build privately forked blocks onto.

This is an attack against your own mining success. If an attacker succeeded, they can only do so with multiple failed attempts, and the failed attempts can only add up to an overall net loss of mining rewards. The practicalities of Discard/Selfish attack are self-inhibiting; the honest miners will gain more than they lose as a consequence of how frequently they can solve a block that the attacker is withholding.

Vires in numeris
Meni Rosenfeld
Donator
Legendary
*
expert
Offline Offline

Activity: 2058
Merit: 1029



View Profile WWW
November 06, 2013, 06:57:43 PM
 #22

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.
The ideology underpinning Bitcoin is that:

1. The monetary supply should be fixed, neither inflating nor shrinking (too much)
2. The inflation schedule is chosen first, and the technology conforms to it. Here we would have a technological consideration affecting the monetary base.

1EofoZNBhWQ3kxfKnvWkhtMns4AivZArhr   |   Who am I?   |   bitcoin-otc WoT
Bitcoil - Exchange bitcoins for ILS (thread)   |   Israel Bitcoin community homepage (thread)
Analysis of Bitcoin Pooled Mining Reward Systems (thread, summary)  |   PureMining - Infinite-term, deterministic mining bond
revans
Sr. Member
****
Offline Offline

Activity: 336
Merit: 250


View Profile
November 06, 2013, 07:06:43 PM
 #23

Isn't shellfish mining generally called 'fishing'?
iddo
Sr. Member
****
Offline Offline

Activity: 360
Merit: 251


View Profile
November 06, 2013, 10:45:08 PM
 #24

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 can also confirm that Lear has discussed with me these observations (with elaborate details) and his upcoming academic paper on this topic, about two weeks before the paper by Eyal and Sirer was made public.
BTW, the word "published" is a little confusing in this context, it's more clear to say that it's "self-published" for now. Maybe their publicity stunts (like that "Bitcoin is broken" blog post) will interfere with the supposedly anonymous review process for publication, though I doubt that it would.
King Lear
Newbie
*
Offline Offline

Activity: 23
Merit: 0


View Profile
November 07, 2013, 02:42:20 AM
 #25

Thank you all for your support!

I know you are curious for my declared more accurate analysis, but unfortunately I have a full time job and some university classes, so clearly writing everything is done slowly. The Cornell guys have already published ahead of me so now I have no reason to write my paper in a rush.

However, I am posting here a simplification of part of my analysis. I'm trying to emphasize the real nature of the attack as an attack by solo miners, based on the key point which is the adaptive difficulty adjustment.

As for the possible variations of the fork-punishing countermeasure, I am not concerned with the possibility of money destruction. It already gets destructed each time someone loos his keys! I think the specific variation should be simple and elegant, as well as more secure. The extra security of the fork-punishment is not totally complete, and varies between different implementation. A careful mathematical analysis should be made to choose the best option.

Lear.
King Lear
Newbie
*
Offline Offline

Activity: 23
Merit: 0


View Profile
November 07, 2013, 02:48:27 AM
 #26

So here is the simplified explanation, based in part on my draft:

--------------------------------------------------------------------

The block discarding attack

We shall first describe the attack in subsection 3.1 w.r.t the Bitcoin protocol; in subsection 3.2 we adjust and improve the attack to the PoA protocol; and then in section 3.3 we suggest to introduce a fork-punishment protocols change as a countermeasure.

[3.1]
The attack is based on the assumption that the attacker can achieve "Network Superiority" by maintaining many direct network connections, much above the average of a single user. As explained in the previous section, when two blocks are released around the same time, the one that will be propagated faster has much higher chance to be eventually confirmed. The ability to make one's block be propagated much faster is part of what we regard as network superiority, while the other part is the ability to become instantly aware of any new released block in the network.   

Propagation of blocks is relatively slow – the average time it takes for a node to be informed of a new block is 12.6 seconds – since propagation delay composes both of the data transmissions time and the blocks verification time (a node verifies each block before it propagates it to its neighbors). Therefore, an attacker that maintains many slave nodes all across the network which are programmed to propagate her blocks without verification and to send her new received blocks without verification, is most definitely expected to acquire network superiority. That is, as long as the network is homogeneous, as the distributed Bitcoin network is supposed to be. Propagation of the attacker's block can be accelerated even farther by composing empty or relatively short blocks, whose verification (by the non-slave nodes) is faster.

Assuming an attacker with 0 < p < 1/2 fraction of the total hash power achieves total network superiority, meaning she is instantly informed of any new released block and her generated blocks always win the race when they are release on the same time as a competitor block. Then the attacker will lose nothing by holding each new generated block until a competitor is found and then release it immediately, and while holding the block treating it like it was already got into the chain, i.e. mining the next block on top of the temporary-secret block.

When normally the attacker generates x blocks and the rest of the network generates y blocks, each one of the blocks is mined on top of the previous generated one, so the chain eventually grows by x+y more blocks. However in time of attack, if the attacker generates x blocks and the rest y blocks, then all of the attacker's blocks will eventually get into the chain while only y-x of the other blocks will get into the chain, so the chain eventually grows by only y more blocks:

Each block of the attacker is released when another block is found and hence it is used to "replace" the competitive block within the chain. So if the attacker mine x blocks, x blocks of the rest of the network will be discarded, and replaced by the attacker's blocks. The total block-chain growing rate will be as if the attacker don’t mine at all, that is (1-p) times the normal rate.

Difficulty adjustment then lowers the difficulty so there will be approximately the same number of generated blocks within the same period, however the total share of the attacker's blocks out of the block-chain is now raised from p to p/(1-p). Lows of economy dictates that the cost of hash-power invested into mining should be around the expected reward. The expected reward of the non-attacker miners is now only (1-2p)/(1-p) times than before, so the total hash-power of the honest miners is about to decline as more miners leave the game.
 
By essence that means the attacker's share of the total hash-power is about to exceed p, so that the attack becomes more efficient and hence there are more miners to leave the game… the process can halt on some equilibrium or continue until all honest miners leave.

To analyze the exact outcome let b be the hash-power of the attacker, g the initial hash-power of the honest network, and h > 0 the new hash-power of the honest network when a possible equilibrium is reached. For simplicity let the hash-power unit we used be such that b + g = 1, or equivalently b = p.

Lows of economy dictate that in any stable situation, the cost of hash-power invested by an honest miner should be approximately the same as the expected reward. Hence the expected number of (eventually confirmed) mined blocks per a hash-power unit of an honest miner in the equilibrium state is the same as what the expected number of mined blocks per a hash-power unit was before the attack.

Since the total hash-power of confirmed blocks in the equilibrium state is h, we get
(g/(b+g))/g = ((h – b) / h) / h.
By convention b+g =1, so we get h^2 = h –b, or h = 1/2(1+sqrt(1-4b)).
That means the fraction of the attacker out of the new total hash-power is
b/(h+b) = 2p / (2p + 1 + sqrt(1-4p))

for p = 1/4 that means 1/4 of the initial hah-power has left, attacker has 1/3 fraction of the new hash-power and gets twice as much block rewarding as before, and the difficulty is half than before. For 0 < p < 1/4, the attacker gain more rewards than before but less than twice, and for p > 1/4 the equilibrium is obviously impossible, meaning the process will not halt until all honest miners leaves the network.

In practice total network superiority can never be achieved, so the analysis should include a probability w < 1 of the attacker winning a block race. Interestingly, the attack is reasonable even were w is explicitly lower than 1, but the most accurate analysis is complex.
When w != 1, there is a hierarchy of Block-Discarding-Attack strategies, of whom the "s(h)elfish mining" is just the first one. My complete analysis that explains everything will be published soon.

Meanwhile, I want to stress some points:

1.   As I said, the attack is currently infeasible with any of its versions.
2.   Since the attack is based on secrecy, it is not applicable to pools. Moreover, the dynamic process of the theoretic attack does not involves transfer of miners from one pool to another, but a gradually quitting of honest miners due to unprofitability.
3.   The difficulty adjustment is the key point of the attack.
4.   On any not purely theoretic scenario, equilibrium will be achieved, and the security impact of that is the increased vulnerability of the system to a second attacker, since the total block-chain hash-power is reduced. The first attacker is unable to harm the system whatsoever.
5.   On the purely theoretical scenario where the attacker deports all other miners, she can harm the system by lunching a DoS attack. Double-spending attack, however, is more problematic since the moment the Block-Discarding attacker stops mining linearly, all the ex-miners will happily start mining again, and are expected to gain awesome rewards due to the lower difficulty.   

Lear
cunicula
Legendary
*
Offline Offline

Activity: 1050
Merit: 1003


View Profile
November 07, 2013, 10:12:21 PM
 #27

You might be interested in my take on the issue (quite different from a computer science perspective). For me the crux of the matter is that miners own ASICs.
ASICs are an illiquid asset, so miners care about what happens to their market value.

This implies that the static game framework is completely inappropriate for analyzing this problem. The game is repeated. Here is my analysis:

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

Warning: I do not suffer fools gladly.
revans
Sr. Member
****
Offline Offline

Activity: 336
Merit: 250


View Profile
November 07, 2013, 10:47:40 PM
 #28

You might be interested in my take on the issue (quite different from a computer science perspective). For me the crux of the matter is that miners own ASICs.
ASICs are an illiquid asset, so miners care about what happens to their market value.

This implies that the static game framework is completely inappropriate for analyzing this problem. The game is repeated. Here is my analysis:

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

Warning: I do not suffer fools gladly.


You must find yourself insufferable.

A lot of hand waving nonsense which doesn't even address the attack vector detailed in the paper it claims to address.
gyverlb
Hero Member
*****
Offline Offline

Activity: 896
Merit: 1000



View Profile
November 07, 2013, 11:39:01 PM
 #29

You might be interested in my take on the issue (quite different from a computer science perspective). For me the crux of the matter is that miners own ASICs.
ASICs are an illiquid asset, so miners care about what happens to their market value.

This implies that the static game framework is completely inappropriate for analyzing this problem. The game is repeated. Here is my analysis:

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

Warning: I do not suffer fools gladly.


You must find yourself insufferable.

A lot of hand waving nonsense which doesn't even address the attack vector detailed in the paper it claims to address.

What, revans? Are you going to request a mathematical proof too?

If you see nonsense in canicula's post you might want to think twice about writing it for all to see, especially those who understood his point...

P2pool tuning guide
Trade BTC for €/$ at bitcoin.de (referral), it's cheaper and faster (acts as escrow and lets the buyers do bank transfers).
Tip: 17bdPfKXXvr7zETKRkPG14dEjfgBt5k2dd
iddo
Sr. Member
****
Offline Offline

Activity: 360
Merit: 251


View Profile
November 07, 2013, 11:48:01 PM
 #30

You might be interested in my take on the issue (quite different from a computer science perspective). For me the crux of the matter is that miners own ASICs.
ASICs are an illiquid asset, so miners care about what happens to their market value.

This implies that the static game framework is completely inappropriate for analyzing this problem. The game is repeated. Here is my analysis:

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

I haven't read your analysis yet, but I wanted to mention that there exist ASIC-resistant hash functions that cryptocurrencies can utilize for PoW (which would imply that the mining hardware does have resale value). So if your analysis is 100% correct, it will indeed apply to Bitcoin, but not to cryptocurrencies in general. Therefore Lear's academic paper can still have merit.
Sukrim
Legendary
*
Offline Offline

Activity: 2618
Merit: 1006


View Profile
November 08, 2013, 12:40:51 AM
 #31

ASIC resistant? I doubt that... (remember when Litecoin was called GPU resistant?)

There are PoW schemes that are probably very hard or more expensive to mine on ASICs, however I doubt that there will be any single PoW algorithm that is faster on a CPU than on an ASIC. It might take longer until it is economically feasible to create such ASICs but once this point is reached, it will be done.

https://www.coinlend.org <-- automated lending at various exchanges.
https://www.bitfinex.com <-- Trade BTC for other currencies and vice versa.
cunicula
Legendary
*
Offline Offline

Activity: 1050
Merit: 1003


View Profile
November 08, 2013, 04:17:25 AM
Last edit: November 08, 2013, 03:55:54 PM by cunicula
 #32

I'm sorry. I do not mean any disrespect towards king lear. He seems like a nice thoughtful chap doing geat work. It seems like all the bitcoiners I like best are somehow located in israel. Mazel tov! (I'm not jewish myself though).

I like some of the ideas for fixes king lear suggests and expect that they will also have applications for his resarch on pure proof of stake systems as well.

As for these other two guys, they are abusing analysis of an algorithm to make unfounded predictions about human behavior. When I see stupidity, I tend to get enraged. I'm sorry about any collateral damage this causes.

As for this revans character, to the extent that my bomb exploded in his face the mission was a success.

Yes, revans, I did not specifically address your algorithm. That's because your algorithm tells us nothing new about the incentives behind bitcoin mining. The subgame for each period is a prisoner's dilemma if you are wrong about selfish mining. The subgame for each period is a prisoner's dilemma if you are right about selfish mining. Bravo!

 You are analysing competition between algorithms. Do not confuse this with the analysis of human behavior. To do this you need to worry about time preferences, include miner assets as state variables, consider effects on asset and output prices, etc. I suggest that you walk over to the economics department next time you write a paper on behavioral issues. You could get some useful feedback there.
cunicula
Legendary
*
Offline Offline

Activity: 1050
Merit: 1003


View Profile
November 08, 2013, 04:27:44 AM
 #33

I haven't read your analysis yet, but I wanted to mention that there exist ASIC-resistant hash functions that cryptocurrencies can utilize for PoW (which would imply that the mining hardware does have resale value). So if your analysis is 100% correct, it will indeed apply to Bitcoin, but not to cryptocurrencies in general. Therefore Lear's academic paper can still have merit.

Yes, I agree completely (see the end of the pdf). You see this is why I like you guys!
revans
Sr. Member
****
Offline Offline

Activity: 336
Merit: 250


View Profile
November 08, 2013, 01:12:44 PM
 #34

I'm sorry. I do not mean any disrespect towards king lear. He seems like a nice thoughtful chap doing geat work. It seems like all the bitcoiners I like best are somehow located in israel. Mazel tov! (I'm not jewish myself though).

I like some of the ideas for fixes king lear suggests and expect that they will also have applications for his resarch on pure proof of stake systems as well.

As for these other two guys, they are abusing analysis of an algorithm to make unfounded predictions about human behavior. When I see stupidity, I tend to get enraged. I'm sorry about any collateral damage this causes.

As for this revans character, to the extent that my bomb exploded in his face the mission was a success.

Yes, revans, I did not specifically address your algorithm. That's because your algorithm tells us nothing new about the incentives behind bitcoin mining. The subgame for each period is a prisoner's dilemna if you are wrong about selfish mining. The subgame for each period is a prisoner's dilemna if you are right about selfish mining. Bravo!

 You are analyzing competition between algorithms. Do not confuse this with the analysis of human behavior. To do this you need to worry about time preferences, include miner assets as state variables, consider effects on asset and output prices, etc. I suggest that you walk over to the economics department next time you write a paper on behavioral issues. You could get good some useful feeeback there.

 
The paper was not written by me, I merely read and understood its implications. Your clearly did not.
NewLiberty
Legendary
*
Offline Offline

Activity: 1204
Merit: 1001


Gresham's Lawyer


View Profile WWW
November 08, 2013, 03:24:54 PM
 #35

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.

There are a variety of magical abilities to propagate blocks faster.  These include both network acceleration and denial of service technologies.  A well planned attack process would utilize both and if sufficient value is to be gained (say through a massive short position, or long on alternatives) high speed network links to NNIs adjacent to supernodes globally would be sufficient.  The denial of service elements can be defended against to some extent, investment in HSN to NNI, not so much defended but potentially create a technology race.  Though the racers are more likely to be the attackers than the honest nodes.  
At some point network investment ROI will be less expensive than hash-power ROI for attacks.  It is generally easier to attack than to defend.

FREE MONEY1 Bitcoin for Silver and Gold NewLibertyDollar.com and now BITCOIN SPECIE (silver 1 ozt) shows value by QR
Bulk premiums as low as .0012 BTC "BETTER, MORE COLLECTIBLE, AND CHEAPER THAN SILVER EAGLES" 1Free of Government
xan_The_Dragon
Sr. Member
****
Offline Offline

Activity: 322
Merit: 250


I AM A DRAGON


View Profile
November 13, 2013, 07:12:35 PM
 #36

is this suppose to be different than selfish mining?

MfFMEpgL5Ma9C2yw6iSsSX4QcbSVzjm6iK
King Lear
Newbie
*
Offline Offline

Activity: 23
Merit: 0


View Profile
November 18, 2013, 04:40:00 PM
 #37

Hi Cunicula,

First, I'm sorry for not responding for long periods of time. I have just read your analysis, which I like very much. Although I basically agree with you, I would like to make some notes:

1.   When theoretically analyzing a system, I do think it is wise to make as few assumptions about the external-to-the-system-world as possible. Yet while doing so you must be careful when you derive conclusions about the real world (e.g. aggressively spamming the web with "Bitcoin is broken" nonsense is a great example of a wrong attitude).

2.   As I said, I am not considering the (many) Block-Discarding-Attack strategies as applicable to pools, while the Cornell guys does. So game-theoretic equilibriums are interesting in my opinion only as a mean to analyze the expected reaction of the pools and the small miners to a theoretical block-discarding attack operated by a  big strong *solo miner*.

3.   It is hard to estimate your beta variable (the long-term post attack worth of a Bitcoin in terms of the current value). The attack might not decrease the value much, as long as there is no massive double spending or massive denial of service. If the attacker's motives are increased rewards, than she is likely to choose not to do those thinks.

4.   It is possible that the attacker have external motives, i.e. she can benefits from harming the system, say if she has interest in competitive money. In fact the most likely scenario of lunching such attack I can think of is where a government tries to fight the black market by DoS-ing Bitcoin. If so, all assumption about supposedly-rationality of the attacker becomes invalid.

5.   Another assumption that I prefer not to introduce to the theoretical analysis is the illiquidity of ASICs. You noted yourself that a PoW crypto-currency with the same structure of Bitcoin might be more vulnerably if it use the more liquid CPUs, and I would like to note that a SHA-256 ASIC can be turned to mining of other crypto-currencies:

If some SHA-256 alt-coin is attacked than miners (including the attacker) can leave for Bitcoin if the attack destroys the alt-coin. In case Bitcoin itself is attacked and destroyed, then a new (hopefully more secure) crypto-currency can be expected to replace it. Furthermore, this crypto-currency is expected to be based on SHA-256 since currently the SHA-256 ASICs are widely spread. 

Yet I note in my paper, regarding the theoretically possible gradual leaving of honest miners, that in practice the resulted equilibrium is about to be less biased toward the attacker since the cost of mining is divided between the liquid electricity and the less liquid machinery. (BTW I was looking exactly for the term "illiquidity" to explain that. My English is not so great, e.g. "shellfish mining", and so is my knowledge of economy).

Lear.
cunicula
Legendary
*
Offline Offline

Activity: 1050
Merit: 1003


View Profile
November 19, 2013, 09:21:45 AM
 #38

Hey lear,

I would like to do a more sophisticated/thorough analysis to post on arxiv, but don't want to release anything in my own name.
The pdf is just me typing for an hour after drinking too much whisky. I can be professional too.

 Also, you could present the issues in a more natural way for a CS audience. You could also discuss the technical details of the attack. I think i get it, but i have no training or expertise in computer science. Do you have any interest in collaborating on this?You could publish it in your own name if you like, or alternatively, you could credit me under a pseudonym.

You don't have to give me a definite answer now and can back out later if you say yes.
cunicula
Legendary
*
Offline Offline

Activity: 1050
Merit: 1003


View Profile
November 21, 2013, 07:30:25 AM
Last edit: November 21, 2013, 05:36:13 PM by cunicula
 #39

BTW, this Emin Gün Sirer guy is really a class act. Check out this email I got from him (bolded the really funny part where he threatens to sue me
and yes I do live in Singapore):
Quote
Hey there,

I noticed that you're posting the same comment in unrelated
discussions. As per Point #18 in
http://hackingdistributed.com/2013/11/14/response-to-feedback-on-selfish-mining/
this is plain old spam. It reduces the value of the discussion section
for everyone. Please refrain from doing this. We'll be marking such
comments as spam, where they get sent to a bin that no one sees.

Keep in mind that you are a guest on my blog. I opened up some space
for engagement with the greater Bitcoin community. You have been using
that space mostly to be obnoxious. Others have been complaining about
the inanity that is oozing out of the comments section, and I've been
getting complaints specifically about you.

In certain countries, such as Singapore, comments of the kind you've
posted would be considered defamation. You can look up the associated
punishments for such conduct.


You must also realize just how common it is for new grad students, as
well as second-rate researchers, to be dismissive of others' work,
while they themselves provide nothing of value to the discussion.
Almost all your comments that have any content are full of
undocumented assumptions.

I urge you to adopt a more civil tone. If you do not shape up, and
continue to deface the site from behind a thin veil of supposed
anonymity,  I'll be taking more drastic measures, starting with
blacklisting your account.
darkmule
Legendary
*
Offline Offline

Activity: 1176
Merit: 1005



View Profile
November 21, 2013, 06:09:43 PM
 #40

BTW, this Emin Gün Sirer guy is really a class act. Check out this email I got from him (bolded the really funny part where he threatens to sue me
and yes I do live in Singapore):

I've been giving this guy the benefit of the doubt since this story came out, but I think that is pretty much out the window.

What an asshole.
bernard75
Legendary
*
Offline Offline

Activity: 1316
Merit: 1003



View Profile
November 21, 2013, 06:42:08 PM
 #41

How does he know you live in Singapore?
King Lear
Newbie
*
Offline Offline

Activity: 23
Merit: 0


View Profile
November 26, 2013, 12:40:01 PM
 #42

Hi Cunicula,

I have recently submitted a manuscript to some workshop. Indeed it is not finished and can be improved (hopefully I would be able to do so if it will be accepted), however the essential improvement should be the exclusions of some less important calculations and additions of more intuitive explanations (Currently the paper has no proper introduction). Hence I don’t think it will be a good idea to include yet another aspect to the paper (i.e. the economic game theoretic point of view). Yet I would definitely like to see a paper of yours fully dedicated to this important point of view.

Some other field in which I think we might collaborate is purely proof of stake designs. I have some immature ideas, and if I hopefully have the time I plan to think about them on the upcoming days and would like to hear your opinions. In case we will come to a sparkly design, we can write a paper and even try to form a development team in order to make it a real coin.

Anyway, if we write something together I think credit should be given to you even if you prefer to use a pseudonym. And by the way, I am not much of a computer scientist myself: I am a student for mathematics, and have never written a CS paper yet. 

Lear
Pages: 1 2 3 [All]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!