Ethereum, Bitcoin, DDOS/DOS and CAP theorem

dana-edwards (74)in #ethereum • 8 years ago (edited)

enter image description here

Introduction

In a recent article titled "Ethereum's DAO Wars Soft Fork is a Potential DoS Vector" from information security researchers we learn about how the soft fork opens up Ethereum to attack. In that article they outline how Ethereum may be be vulnerable to DOS. In my article I will claim that both Ethereum and Bitcoin are both vulnerable to DDOS/DOS and that because of CAP theorem no decentralized network can ever satisfy the three requirements; consistency, availability, and partition tolerance.

What is CAP theorem?

CAP theorem states that in any distributed computing network it is impossible to provide more than two out of the three guarantees. In essence you must always pick two and sacrifice one (consistency, availability, partition tolerance). Consistency means all nodes receive the same data at the same time, so a write will update all nodes immediately. Availability means every node is guaranteed to get a success or failure response. Partition tolerance means the network continues to work even when there is a message loss or partial failure.

Bitcoin and CAP theorem

A brief recap:

CAP theorem states that it is impossible for a decentralized computer system to simultaneously provide all three guarantees:

Consistency (all nodes see the same data at the same time). In other words all nodes get responses which make sense.
Availability (every request receives a response about whether it succeeds of fails).
Partition tolerance (the system continues to operate despite arbitrary partitioning due to network failures).

Paul Kernfield writes:

*“In order to enforce consistency, the system must be able to detect a partition. Most distributed systems are able to do this pretty easily, but... most systems are not Bitcoin!

Probably the simplest way to detect partitions is to choose a master node and declare that the canonical copy of the data set lives on the master. A transaction is considered confirmed when the master node confirms it. Bitcoin can't use this, because then it would be easy to shut down or manipulate the whole system by getting at the master node.

Bitcoin does not meet the criteria to invalidate CAP theorem

Bitcoin only temporarily achieves consistency and cannot guarantee it. Over time through the consensus process the confirmations build into a hierarchy of truth. As you gain more confirmations of your transactions then the validity of your transaction improves. After 6 transactions it is considered irreversibly true and this means you have a snowball effect building consistency over time. Eventually you can say all nodes see the same data but it’s not immediate. In Bitcoin consistency was sacrificed and the best we can say is that it is eventually consistent because in Bitcoin if you wait long enough eventually the consistency returns.

Bitcoin sacrifices availability. It sacrifices consistency if it has partition tolerance because it cannot have both at the same time.

Paxos on the other hand has consistency and partition tolerance guaranteed but sacrifices availability. Paxos is an alternative consensus protocol which achieved consistency by preserving and replicating state machines. Paxos with this approach has the advantage of consistency and partition tolerance because state replication is a lossless approach.

A quote from the author TPTB_need_war states:

The point that page makes is that validating Ethereum contracts MUST be slow because nothing can be validated >with parallel computation. I am making an additional and more damning point. That is since each contract WITHIN a >block has to be executed to completion before the next (i.e. no parallelization) this also means that the result of the >block chain state will be potentially different depending on which order the contracts are ordered in the block. But >note that such order is completely arbitrary (because there is no synchrony in distributed systems, i.e. there is no >way to prove which transaction arrived first during the block period since each node will have a different ordering >due to variance in network propagation). The becomes an insoluble problem due to chain reorganizations (unless everyone waits for umpteen confirmations before validating anything but then how do we order the blocks...etc...see next paragraph). Also we can't assume that contracts in one partition don't affect a
contract in another partition due to externalities, e.g. for example the result of a contract causes an external action which causes the execution of another contract. The point of computation is that it is not bounded at the block chain!!!!!!!!!!!!!!!!!!!!!! Thus if thus if the block period is not infinitesimally small (or especially as the block period grows larger), then the indeterminism that is introduced can cause contracts to >behave randomly if they were not designed to handle such indeterminisn. Or worse yet, the validators on different >partitions will be in predicament where if there are two or more orderings that are incompatible from different >partitions and thus the block chain can't be unified and diverges into forks. The externalities problem is entirely unfixable. Period! The only way to fix it is to not verify smart contracts on a >block chain and instead only record the directed acyclic graph asset transfers on the block chain as the section >"Smart contracts in >public blockchains" explains. This means the entire premise of Ethereum is impossible. >Fugetaboutit. Stick a fork in >it. It is going to $0 their funding will run out and the game is over.

Based on his post it would appear that he believes Ethereum is built on faulty theoretical premises. In fact this highlights the divide between the intuitionist vs formalist faction in the crypto community today. The fact that Ethereum is Turing complete may in fact be the very feature which dooms the smart contract functionality which Ethereum was designed for. It may also not be possible to scale Ethereum due to the slowness and great difficulty associated with dealing with Turing complete smart contracts. The approach to smart contracts taken by Ethereum is not formally verified, and it is not known how Ethereum will scale.

Smart contracts on Ethereum get around the halting problem through gas. Gas puts a limit on every smart contract so that every smart contract essentially grows old and dies. An infinite smart contract is not possible because the smart contract would run out of gas and die. At the same time Ethereum suffers from perhaps a fatal flaw in that it cannot handle concurrency.

In a quote from an article on Multichain:

“To use formal computer science terminology, Ethereum transactions must be strictly totally ordered, meaning that >the relative order between every pair of transactions must be defined. By contrast, bitcoin transactions form a >directed acyclic graph which is only partially ordered, meaning that some ambiguity in transaction ordering is >allowed. When it comes to concurrency, this makes all the difference in the world.”

To my knowledge there is nothing Ethereum can do to solve this problem to scale up it’s on blockchain computation. The only answer is to do off chain computation which can scale but then you still have the slowdown from the smart contracts over time. Casper may be an attempt to scale but risks remain due to the Turing complete nature of the smart contracts on Ethereum. As The DAO has shown, it is exceptionally difficult to create reliable smart contracts and code complexity makes auditing increasingly difficult.

Blockchains may evolve into Proofchains

Formalist mathematicians led by the likes of Ohad Asor and Lucius Meredith have independently put forth a hypotheses which may alter the evolution of the blockchain and change it conceptually over time as formalists gain influence. The formalist approach is called correct by construction and in specific Lucius Meredith in his paper on linear types lays forth a new more formal way of thinking about what a blockchain is. The primary insight that both Ohad Asor and Lucius Meredith contribute is based on the Curry Howard isomorphism which states that programs are proofs. Lucius Meredith elucidates even further by discussing in his paper how linear proofs can be operations on a blockchain which itself is a proof.

Ohad Asor is building Tauchain which is as far as I know the first attempt at building a proofchain. I will state that in my opinion proofchains will be fundamentally more powerful than blockchains. In a proofchain you have the logic built in, and as with an app store where you have a catalog of programs the proofchain will offer a catalog of proofs. The difference is that a proofchain will be logically consistent, decidable, and a proof is formally verified. This means no need to use gas to solve the halting problem because the halting problem is solved by the consistent and decidable logic at the cost of Turing completeness.

Ethereum and Bitcoin are inherently vulnerable to DOS attacks

enter image description here
It is necessary to mention that Bitcoin and Ethereum are both vulnerable to DOS attacks. Bitcoin on it's weaknesses page (does Ethereum have a similar page yet?) states DDOS is a vulnerability and lists restricting the blocksize to 1 megabyte as a protocol rule to diminish the threat. I am highly skeptical that the blocksize cap will help protect Bitcoin from DDOS attacks.

Ethereum on the other hand is vulnerable to a different category of DOS. The computational DOS attack is described below:

At a high level, recall that Ethereum miners are currently protected from DoS attacks by gas payments: the more computation they perform, the more gas they collect, and the more money an attacker has to spend. But with the soft fork in place, miners are in a new position where they end up having to perform substantial work without collecting any compensation, at no penalty to the attacker. The soft fork creates a new and fundamentally different class of transactions in contrast with those that currently exist within the protocol. Currently, transactions either complete successfully and cause a state transition, or run into an exception, in which case state is reverted but the maximum possible gas is still charged. With the soft fork, transactions which interact with a DAO will not fit within these two classes: they will fail execution but no gas will be charged. This must inevitably be the case in any soft fork that aims to freeze the stolen funds; since the protocol does not specify a “DAO Interaction Exception,” miners must either include the transaction in their block along with all of its resultant state changes, or they must exclude the transaction entirely, and forfeit any gas reward. Attempts to include a transaction without its proper state transitions will cause the block to be invalid and not propagated by other nodes. This provides an enormous amount of amplification to the attacker.

This attack vector is opened specifically by the implementation of the soft fork. It exploits the fact that computation on Ethereum is inherently very expensive and that there is no gas payments to provide economic limits. The authors of the article state that in the case of a DOS attack the end result could be that the Ethereum community is forced to decide to either no-fork or hard fork. I would say this is a likely scenario but that it also would not be in the best interest of the attacker to do that because it could very well push the community to hard fork. The outcome of this is anyone's guess.

References