POW based blockchains systems Majority Attack TL;DR: With only 30% of network power a Majority Attack is possible and profitable. Am I missing anything?



Generally speaking, blockchains based on Proof-of-Work authentications are using amount of work as the weight of one's vote.

I will be talking specifically about bitcoin to simplify the discussion (Although I hate reading people who talks about cryptocurrency here).

A transaction is consider confirmed usually after 6 blocks have been mined above it. Mostly even 2 blocks are considered enough, but let's examine the secure decision of 6 block. Now assume I have 30% of the network power.

Me and the network have the same prefix of blockchain. At this point I'm beging to work and append to it my own blocks, ignoring the rest of the network. The chances I will manage to build a blockchain that is at least as long as longest chain in the network, by the time the transaction is "confirmed" - is roughly 15% (reference below).

That means I can revert my confirmed transactions 15% of the times. Now all I need is to earn more money on a reverted block than I'm paying for the total computing power. This is not impossible. If a "confirmed" block is even half-fulled with my transactions, the total amount of money can easily be 2 million usd (reference below).
Reverting at 15% success rate means at least one block every two hours (one block every ten minutes). 

But 2 hours of work only cost me about 140,000 usd.

Or more importantly: playing fair doesn't seem necessarily more profitable.

Playing by the rules for two hours equals today about 1.2 million usd income (If you own 30% of the network power).

It seems profitable to attack the system every now and then, even with 30% of network power.

(Obviously I rather revert a lot of "small" transactions than a huge one, so no one will get susplicious and wait for more confirmations.)

What am I missing?

A few points:
- I rather not address issues such as "an attacker can be easily found". This may, or may not, be true. But it's not relevant for the question: Is it possible and profitable to attack the network with 30% network power.
- If you are stating I'm not mistaken and this is true (which I doubt), please do specify your amount of familirity with the protocol and the security of the system.

Refernces:


Success rate with 30% network power (math here is simple but clumbsy to write down rigorously)
https://pastebin.com/RhnGi04W
A single block carry a few thousand bitcoins (namely, a few million usd)
https://blockchain.info/
Bitcoin value in usd
https://coinmarketcap.com/currencies/bitcoin
Profits and costs of the entire bitcoin network:
https://digiconomist.net/bitcoin-energy-consumption

(I assumed one hour of my working profits roughly: total_bitcoin_mining_income/365/24*0.3 
as I own 0.3 of the network power)
The attack you are describing is correct. This is an attack against the "Common Prefix" property of the blockchain, which roughly states that it should be hard for an adversary to cause two honest parties to adopt two different blockchains at the same time when they have diverged for more than k blocks, where k is a parameter. In your case, you have set k = 6.

In fact, the attack you are describing has been analyzed in Satoshi's original paper. If you look at the last section (11. Calculations), Satoshi calculates the probability of success of the attack you described. Specifically, he examines the probability of adversarial success for various values of the variable he calls q, which indicates the adversarial mining power. For your case, q = 0.3. Then he uses the variable z to indicate the number of blocks one waits prior to accepting a transaction as confirmed, in your case z = 6. In Satoshi's analysis, this follows a Poisson distribution and roughly the probability of adversarial success is indeed p ~= 0.15. In fact, Satoshi precisely calculates the case z = 5 and q = 0.3 and gets p = 0.1773.

In the original paper, there are certain z recommendations for how many blocks one should wait for to achieve an adversarial probability bound of p &lt; 0.1%. For q = 0.3, the minimum z that achieves this is z = 24. So, if you want to be able to withstand a 30% adversary, you must wait for 24 confirmations.

Satoshi's analysis is a bit rough, because it only takes one particular attack into account. Subsequent analyses have allowed us to quantify these probabilities against arbitrary adversaries, even unknown. The primary reference here is the Backbone analysis. In this paper, the Common Prefix property is stated precisely and proven to hold against arbitrary adversaries.

The Backbone analysis is an improvement over Satoshi's for several reasons. I will mention a few:


The probability distributions are specified precisely (as Binomial and Bernoulli distributions) and not approximately (as Poisson distributions).
The adversary is arbitrary and does not necessarily follow a strategy that we have predicted or know about.
The security is proven and not simply intuitively conjectured.
The system is modeled and analyzed precisely using theoretical computer science tools down to interactive Turing machines.


To see the Common Prefix statement precisely, look at Definition 3 (Common Prefix) under section 3.2 (Desired properties of the protocol). The fact that bitcoin has this property is proven in Section 4.2 (Common-Prefix property) under Theorem 15 (Common Prefix). There, a precise formula is given for k, the number of blocks you need to wait to know that the chain cannot be reorg'ed back to that point: k = ηκf. The variables η, κ, f are made precise in Section 4 (Analysis) under Table 1 (The parameters in our analysis). It is difficult to give concrete numbers to these variables, as they depend on the network health and performance as well as mining difficulty. For bitcoin, we have that κ = 256 is the bit length of the (mining) hash function. I estimate round duration to be, optimistically, about 10 seconds (time it takes for a large portion, say 90%, of the network to learn of a newly mined block header) and so since a block is found on average every 10 minutes, we have that f is about 0.0003 for bitcoin. I do not know how to estimate η precisely.

The point is that the Common Prefix theorem is attained for k when "the execution is typical" (typicality is established in Theorem 10), which depends on the parameters ηκ. A prerequisite for typicality is that the sequences of consecutive rounds examined are at least ηκ in length. The assumption that this quantity is large is needed to apply the Chernoff bounds to the Binomial distribution: Typicality is attained with overwhelming probability in this number. If this number is small, the probability is no longer overwhelming, and the security of the system can fail.

Such analyses are typical in cryptographic systems, including digital signatures, encryption schemes, zero-knowledge proofs, and so on. The adversary is capable of succeeding with a probability which is bounded by a function with one free variable: That free variable is the security parameter (ηκ in backbone's case) and the function is negligible in that parameter, meaning that the probability drops off exponentially as the parameter increases. In Bitcoin's case, the probability of double spending drops exponentially as the blockchain size on top increases, but is not negligible for k = 6, especially when the adversary is powerful.

To address your more concrete point that this is economically feasible: You are right that you can transfer $2M in a single bitcoin transaction. However, I find it unlikely that the recipient for such a transaction would consider it safe after k = 6; a value close to k = 25 must be used. It is sensible to accept lower values of k for smaller amounts and require larger values of k for larger amounts. While the exact probability is difficult to calculate, still most exchanges and other automated services accepting cryptocurrency payments apply reasonable bounds and I expect that they increase them for amounts that are in the millions of dollars (typically this is done by requiring human approval of a transaction for extremely high-value transactions, which definitely gives plenty of time for proper proof-of-work on top). The economic cost of forking the chain to cause block abandonment is briefly analyzed in the paper On bitcoin as a public randomness source. Given that analysis, one can balance the cost of forking the blockchain against the potential gains one could earn by performing a successful double spend, multiplied by the adversarial probability of success calculated from Backbone. This can allow a party to precisely determine their desired value of k for various monetary parameters, given precise adversarial bounds such as q = 0.3.

I know this answer was a bit technical and did not give many concrete numbers, but I hope it shed some light into why the attack you're describing is indeed possible even though we still would call it "negligible". Since you asked for my credentials, I am a PhD student in Cryptography focusing on the foundations of blockchain protocols at the Computer Science department of the University of Athens. Aggelos Kiayias, who wrote the Backbone paper, is my advisor (I did not contribute to that paper). As he is my teacher, I am quite familiar with his work, especially because we're using the model developed in backbone for subsequent work. I am a research fellow at IOHK where we are building the foundations of a cryptocurrency we call Cardano and analyzing it from a mathematical point of view. Probabilities of adversarial success in attempts to perform blockchain forks as well as their analysis come up in my own work in which I'm trying to construct sidechains interfacing multiple blockchains. We often prove negligibility bounds in these settings.