List of Byzantine Consensus Algorithms


#1

This is a list of the different known algorithms/methods that allow you to arrive at a consensus with a large number of computers, where part of the computers might be broken or malicious.

This post has been made a Community Wiki, so you can update it with more information.

Unpermissioned

These allow any computers to join the network at any time, and also allow them to leave at any time later on.

Proof of Work

Uses cryptographic hashing as a ‘lottery’-algorithm, where a new block of transactions can only be made by spending time (measured in CPU power) to ensure a hash is found that starts with enough numbers of zeroes.

Advantages:

  • Has seen wide-spread use.
  • Is relatively certain to be secure. (Although this has not been completely proven mathematically).

DIsadvantages:

  • Requires a significant amount of energy, and this is an [Arms Race](https://en.wikipedia.org/wiki/Arms_race#Other_uses:. More miners mean less mining reward for each and everyone of the miners, so everyone tries to stay ahead relative to the others. The network is not significantly more secure with 10 Thash/s vs 10 Ghash/s.
  • It is relatively slow (and this is necessary for it to be used properly?), and exact time until next block cannot be predicted as this is based on probabilities.

Used in

… and many more cryptocurrencies.

Proof of Stake

The creator of the next block is chosen via various combinations of randomized algorithms combined with wealth or age (i.e. the stake).

Advantages

  • A lot more efficient than Proof of Work systems
  • The people who guard the network are the ones who have the most to lose, which can be seen as aligning interests of the network with the block-creator.

Disadvantages

  • Non-trivial to implement properly.
  • ‘Keeps the poor poor and makes the rich even richer.’

Used In

???

Proof of Burn

People who want to create a new block of transactions destroy some of their current funds.

Advantages

  • Can be done very efficiently.

Disadvantages

  • Not widely known yet, so unknown what problems with this approach are.
  • Might feel counter-intuitive to many people.

Used in

Ripple’s Consensus

In Ripple, nodes all receive new transactions as they come in, and every couple of seconds vote on an ordering of all transactions they know. Nodes exchange information with the nodes on their own ‘Unique Nodes List’ (UNL) which is (supposed to be) a representative sample of the population of all nodes

In multiple rounds of voting, the network will quickly converge to the transactions that are valid and currently propagated through the network enough. Because of the use of the UNL, a lot less traffic is necessary as with complete gossip protocols, and it also is easy for all nodes to monitor each-other (and punish cheaters).

Advantages

  • Very efficient.
  • Very scalable.
  • If less than 80% of the nodes are honest, no transactions at all can be added anymore. (And non-honest nodes can be removed from your UNL). Only when less than 20% of the nodes are honest, can malformed transactions be created in the network.
  • Someone can cheat only once, and then all honest nodes will remove that node from their UNL, making that node worthless.

Disadvantages

  • Your security depends fully on how well you constructed your Unique Nodes List.

Used In

IOTA’s Tangle

Instead of a chain of blocks, the Tangle builds a Directed Acyclic Graph. New transactions need to confirm (refer back to) at least two earlier transactions, and you are incentivized to pick multiple, and especially recent transactions that already have a higher score, because this influences the score of your own transaction.

Using this procedure, it is possible to create a full ordering of all transactions in a way that nobody can predict the ordering beforehand.

Advantages

  • Becomes faster when more people use it.

Disadvantages

  • Still very young protocol, new attacks might still be found.
  • Complex to implement properly.

Proof of Elapsed Time (Requires proprietary Intel hardware).

This seems like a replacement for Proof-of-Work, whereas a special computer chip instruction is used instead of the PoW hashing. However, this only works when you have such a special chip, and it requires putting your trust in the company Intel.

Also, it is currently unclear why it would be impossible to fake a PoET-response.

Used in

Permissioned

Paxos/Multipaxos Classical Byzantine Fault Tolerance

This kind of Consensus has been known for more than 30 years, and was the first variant that was conceived.

In the basic protocol, a node that wants to alter the state of the network sends a request to all nodes using a nonce. Since the network always contains an odd number of nodes, if multiple nodes do this at the same time, only one of them will find out that they have a majority-response.

After doing this, the node can send a second message to all nodes with the actual data to be stored.

This procedure can be repeated many times. The first step of the procedure is also known as ‘electing a leader’.

Advantages

  • Very well known, and enjoys wide-spread usage.
  • Works well for a small number of nodes.
  • A lot of variants of this procedure exist that are optimized for different specific use-cases.

Disadvantages

  • Not scalable, since node needs to communicate with all other nodes.

Used by

Hashgraph

In the Hashgraph, every node sends to a random other node all information it knows that it believes the other node does not have at this time (including information it got from other nodes). This is called ‘gossip about gossip’. New transaction-groups (‘ledgers’) point back to earlier ones that the node knows. By counting how many transactions are visible by a supermajority of the network and how they well are connected to prior transactions, all nodes are able to reach the same conclusion of ordering without extra communication (‘virtual voting’).

Advantages

  • Very fast, very efficient in network bandwidth.
  • The resulting graph is easier to prune than most other ledger structures.

Disadvantages

  • (Currently) requires all nodes to be known at network start, and 2/3 of nodes to be online at all times.

Used in


#2

Some Distributed Ledgers I want to add to this list, as soon as I know more about them.
(So feel free to add them yourself if you know how they work) are

  • Sovrin, which claims to be a ‘public permissioned distributed ledger’.
  • R3 Concord / Corda. (Information about this is somehow hard to find.)

#3

Under Proof of Stake you left “???” for what uses that type of consensus algorithm, I know Cardano plans on using PoS and so does Ethereum later next year. Plenty of smaller currencies use PoS also, for instance ChainLink (LINK) uses PoS for its decentralized oracle service.

The algorithm that Cardano uses is called “Ouroboros” plenty of cited papers on that.


#4

Thank you very much, @Camio! I think it is a very good idea to add a ‘planned’ section in the Proof of Stake implementations list.

Today I also learned that NEM uses a variant of PoS they call ‘Proof of Importance’, but I’ll first finish their whitepaper before writing anything about it ^^’.

I’ll investigate ChainLink and also Cardano/Ouroborous. :smile:

:heart: