Any solution to the Byzantine General's Problem can be used as a consensus method to base a distributed ledger on.
Why then, did Satoshi Nakamoto choose for the super-expensive (in electricity and CPU cycles) Proof-Of-Work?
I can think of these reasons:
- Proof of Work takes time, which means that blocks take time. (But nowadays this is actually a drawback?)
- Miners are paid out by the PoW. (But couldn't this work in a Multi-Paxos environment as well, where basically all miners would like to become leader for the next round?)
- A Proof-of-Work chain will still work if the network netsplits into two pieces. This will create separate blocks in each half of the network, actually being a problem when the two halves are joined again (because then one of the two chains is discarded, which, if the netsplit took multiple minutes before healing, means that people and external systems might have acted based on their now-invalid balances.)
Clearly these reasons are not good enough. So what real reasons are there to use Proof-of-Work over e.g. Multi-Paxos or another 'classical' solution to the Byzantine Generals Problem?