Topic: the Block Discarding Attack / shellfish mining (Read 28693 times)

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

How does he know you 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.

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

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.

is this suppose to be different than selfish mining?

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.

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

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

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.

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.

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.

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

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.

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.

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

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.

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.

Isn't shellfish mining generally called 'fishing'?