the Block Discarding Attack / shellfish mining

[Carlton Banks]

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.

[1713463285]

1713463285

[1713463285]

1713463285

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

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.

[revans]

Isn't shellfish mining generally called 'fishing'?

[iddo]

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]

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]

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]

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]

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]

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

[iddo]

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]

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.

[cunicula]

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]

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]

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]

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.

[xan_The_Dragon]

is this suppose to be different than selfish mining?

[King Lear]

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]

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]

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

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]

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.