Research on distributed consensus has surged with the invention of Bitcoin and Blockchain.
In these special cases we are looking for a distributed consensus algorithm that can scale to a number of nodes comparable to the size of the internet. Nodes can crash or have byzantine failures at any given time. Messages are delivered asynchronously without knowing an upper bound of time one message delivery can take. And there are no exact synchronized clocks available.
The FLP impossibility result suggests that this is not possible.
The Bitcoin Whitepaper by Satoshi Nakamoto provides a solution to this problem by regarding consensus as something that is never definitive but the probability of a value being accepted by all members grows exponentially with the number of confirmations. However the proof-of-work algorithm provided in this paper requires lots of computational power and is very energy hungry.
That is why the PPCoin Paper suggests a new approach called proof-of-stake that solves consensus in a similar fashion, but distributing voting power according to the amount of "stake" someone has in the system instead of how much computing power someone has. However, Proof-of-Stake is vulnerable to the long-range-attack. An attacker can convince honest nodes that a long chain of confirmations he/she produced by themselves is the official chain. PPCoin solves this problem by introducing centralized checkpoints.
Does anyone know of a decentralized solution to the long-range-attack in consensus protocols that doesn't use proof-of-work?
I know of these other protocols: (but none of them have a real solution to this problem)
- Tendermint expects 2/3rds of all bonded validators to sign a block confirmation before it is accepted. I believe that this will not scale to a node set as big as the internet.
- Slasher / Casper: the ethereum developers have presented many ideas and found flaws in all of them. Currently there are two different versions of Casper around, but none of them are formally described completely.
- Ripple uses unique node lists that have to fulfill certain properties of interconnectedness for the protocol to work. But they don't have an algorithm that supports creation of these unique node lists that way.
Do you know any other protocols that might be worth a look? Or have an idea of your own for solving this problem?