[Ethereum] Is “Proof-of-work” a subset of “Byzantine fault tolerance (BFT)”

The PoW algorithm used in Frontier and Homestead is called Ethash, and it was created specifically for Ethereum.

The primary reason for constructing a new proof of work function instead of using an existing one was to attack the problem of mining centralisation, where a small group of hardware companies or mining operations acquire a disproportionately large amount of power to impact or manipulate the network (should they so choose). The economic forces within existing networks (such as Bitcoin and Litecoin) make centralisation of mining efforts highly profitable, in part due to the possibility for producing ASICs, specialised chips specifically designed to outperform standardised computer hardware by many orders of magnitude in hashing performance. Other factors that promote mining centralisation, such as handling of orphaned blocks, are tackled separately within the Ethereum protocol. By specifically designing an "ASIC-resistant" PoW algorithm, the Ethereum team hopes to reduce economic incentives for mining centralisation in Ethereum, at least until a secure PoS algorithm can be designed and deployed.

The way that Ethash aims to provide a PoW algorithm for which commodity hardware is already highly optimised (and hence creation of an ASIC, which is expensive, will yield very little advantage over simply using the latest commodity hardware) is by emphasising a property called memory hardness. Memory hardness essentially means that your performance is limited by how fast your computer can move data around in memory rather than by how fast it can perform calculating operations. Consumer graphics cards compete very strongly in this area, which means that a potential ASIC designer can't easily do better: if they had a new idea for improving memory bandwidth it would be more profitable to sell that idea to a graphics card company than to design a mining ASIC for it. And in any case the mainstream computer industry has large teams devoted to this problem already.

Let us start by what they have in common: they are both algorithms for reaching consensus on the blockchain.

Without going into too much details, we need consensus because anyone can create a block; while we only want an unique chain, so we want a way to decide which block we should trust.

Proof of work has the nice property that you can use Bayes' Theorem and the laws of Thermodynamics to prove that a given block has indeed required a certain amount of work to be mined. That way, users can simply pick the longest valid chain with the highest amount of work as the correct chain.

But this implies that Proof of Work is extremely inefficient in term of energy, and therefore also very expensive; which incentivize miners to centralize the hashing power -- obviously not desirable for a network whose goal is to minimize the need to trust third parties.

Proof of Stake isn't about mining, it's about validating. In effect blocks still need to be created by someone, and who gets to create the next block depends on the specific Proof of Stake algorithm, but the selection process must have some kind of randomness, or at least distribute voting shares properly (otherwise we revert to a centralized system).

In PoS, each validator owns some stake in the network, ether in the case of Ethereum, that they bond. Bonding stake means you deposit some money into the network, and in some sense use it as a collateral to vouch for a block. In PoW you know a chain is valid because lots of work is behind it, while in PoS you trust the chain with the highest collateral.

There are important differences between the various Proof of Stake algorithms that are being developed. This question is about PoW vs. PoS so I'm keeping the answer very general.

Ethereum is going to use Casper, where the stake of malicious validators is going to get (partially) slashed, for example if they sign two (competing) blocks with too high a probability.