Quote from: tracyspacy on February 12, 2018, 11:25:41 PM

I have studied most common consensus algorithms. Here is the summary, maybe for someone it will be helpful. My goal is to describe every specific consensus briefly so everyone can easily understand it.
*Please let me know if I have wrote something wrong, or maybe you are aware of interesting algorithm, I have missed.

Proof of Work - very short, cuz it's well-known.

Bitcoin - to generate a new block miner must generate hash of the new block header that is in line with given requirements.
https://bitcoin.org/en/developer-guide#proof-of-work
https://bitcoin.org/en/developer-reference#block-headers
Others: Ethereum, Litecoin etc.

Hybrid of Proof of Work and Proof of Stake

Decred- Blocks are created about every 5 minutes. Nodes in the network looking for a solution with a known difficulty to create a block (PoW). Once the solution is found it is broadcast to the network. The network then verifies the solution. Stakeholders who have locked some DCR in return for a ticket* now have the chance to vote on the block (PoS). 5 tickets are chosen pseudo-randomly from the ticket pool and if at least 3 of 5 vote yes the block is permanently added to the blockchain. Both miners and voters are compensated with DCR : PoS - 30% and PoW - 60% of about 30 new Decred issued with a block. * 1 ticket = ability to cast 1 vote. Stakeholders must wait an average of 28 days (8,192 blocks) to vote their tickets.
https://docs.decred.org

Proof of Stake

Nxt- The more tokens are held by account, the greater chance that account will earn the right to generate a block. The total reward received as a result of block generation is the sum of the transaction fees located within the block.
Three values are key to determining which account is eligible to generate a block, which account earns the right to generate a block, and which block is taken to be the authoritative one in times of conflict: base target value, target value and cumulative difficulty. Each block on the chain has a generation signature parameter. To participate in the block's forging process, an active account digitally signs the generation signature of the previous block with its own public key. This creates a 64-byte signature, which is then hashed using SHA256. The first 8 bytes of the resulting hash are converted to a number, referred to as the account hit. The hit is compared to the current target value(active balance). If the computed hit is lower than the target, then the next block can be generated.
https://www.dropbox.com/s/cbuwrorf672c0yy/NxtWhitepaper_v122_rev4.pdf
https://nxtwiki.org/wiki/Whitepaper:Nxt

Peercoin (chain-based proof of stake) - coin age parameter. Hybrid PoW and PoS algorithm. The longer your Peercoins have been stationary in your account (to a maximum of 90 days), the more power (coin age) they have to mint a block. The act of minting a block requires the consumption of coin age value, and the network determines consensus by selecting the chain with the largest total consumed coin age. Reward - minting + 1% yearly.
https://peercoin.net/assets/paper/peercoin-paper.pdf

Reddcoin (Proof of stake Velocity) - quite similar to Peercoin, difference: not linear coin-aging function (new coins gain weight quickly, and old coins gain weight increasingly slowly) to encourage Nodes Activity. Node with most coin age weight have a bigger chance to create block. To create block Node should calculate right hash. Block reward - interest on the weighted age of coins/ 5% annual interest in PoSV phase.
https://www.reddcoin.com/papers/PoSV.pdf
agroff.github.io/posv/

Ethereum (Casper) - uses modified BFT consensus. Blocks will be created using PoW. In the Casper Phase 1 implementation for Ethereum, the proposal mechanism" is the existing proof of work chain, modified to have a greatly reduced block reward. Blocks will be validated by set of Validators. Block is finalised when 2/3 of validators voted for it (not the number of validators is counted, but their deposit size). Block creator rewarded with Block Reward + Transaction FEES.
https://ethresear.ch/t/latest-casper-basics-tear-it-apart/151
https://github.com/ethereum/research/blob/master/papers/other_casper/casper_basic_structure.pdf

Lisk (Delegated Proof-of-stake) - Lisk stakeholders vote with vote transaction (the weight of the vote depends on the amount of Lisk the stakeholder possess) and choose 101 Delegates, who create all blocks in the blockchain. One delegate creates 1 block within 1 round (1 round contains 101 blocks) -> At the beginning of each round, each delegate is assigned a slot indicating their position in the block generation process -> Delegate includes up to 25 transactions into the block, signs it and broadcasts it to the network -> As >51% of available peers agreed that this block is acceptable to be created (Broadhash consensus), a new block is added to the blockchain. *Any account may become a delegate, but only accounts with the required stake (no info how much) are allowed to generate blocks. Block reward - minted Lisks and transaction fees (fees for all 101 blocks are collected firstly and then are divided between delegates). Blocks appears every 10 sec.
https://docs.lisk.io/docs/the-lisk-protocol-consensus

Cardano (Ouroboros Proof of Stake) - Blocks(slots) are created by Slot Leaders. Slot Leaders for N Epoch are chosen during n-1 Epoch. Slot Leaders are elected from the group of ADA stakeholders who have enough stake. Election process consist of 3 phases: Commitment phase: each elector generates a random value (secret), signs it and commit as message to network (other electors) saved in to block. -> Reveal phase: Each elector sends special value to open a commitment, all this values (opening) are put into the block. -> Recovery phase: each elector verifies that commitments and openings match and extracts the secrets and forms a SEED (randomly generated bytes string based on secrets). All electors get the same SEED. -> Follow the Satoshi algorithm : Elector who have coin which corresponded to SEED become a SLOT LEADER and get a right to create a block. Slot Leader is rewarded with minted ADA and transactions Fee.
https://cardanodocs.com/cardano/proof-of-stake/
storeofvalueblog.com/posts/a-deep-dive-into-cardano/
https://cardanodocs.com/cardano/transaction-fees/

Tezos (Proof Of Stake) - generic and self-amending crypto-ledger. At the beginning of each cycle (2048 blocks), a random seed is derived from numbers that block miners chose and committed to in the penultimate cycle, and revealed in the last. -> Using this random seed, a follow the coin strategy (similar to follow-the-satoshi) is used to allocate mining rights and signing rights to stakeholders for the next cycle*. -> Blocks are mined by a random stakeholder (the miner) and includes multiple signatures of the previous block provided by random stakeholders (the signers).
Mining and signing both offer a small reward but also require making a one cycle safety deposit to be forfeited in the event of a double mining or double signing.
* the more coins (rolls) you have - the more your chance to be a miner/signer.
https://www.tezos.com/static/papers/white_paper.pdf

Tendermint (Byzantine Fault Tolerance) - A proposal is signed and published by the designated proposer at each round. The proposer is chosen by a deterministic and non-choking round robin selection algorithm that selects proposers in proportion to their voting power. The proposer create the block, that should be validated by >2/3 of Validators, as follow: Propose -> Prevote -> Precommit -> Commit. Proposer rewarded with Transaction FEES.
https://tendermint.readthedocs.io/en/master/specification/byzantine-consensus-algorithm.html#proposals
https://tendermint.com/static/docs/tendermint.pdf

Tron (Byzantine Fault Tolerance) - This blockhain is still on development stage. Consensus algorithm = PoS + BFT (similar to Tendermint): PoS algorithm chooses a node as Proposer, this node has the power to generate a block. -> Proposer broadcasts a block that it want to release. -> Block enters the Prevote stage. It takes >2/3 of nodes' confirmations to enter the next stage. -> As the block is prevoted, it enters Precommit stage and needs >2/3 of node's confirmation to go further. -> As >2/3 of nodes have precommited the block it's commited to the blockchain with height +1. New blocks appears every 15 sec.
wiki.tron.network/en/latest/introduction.html#consensus
https://o836fhe91.qnssl.com/tron/whitebook/TronWhitepaper_en.pdf

NEO (Delegated Byzantine Fault Tolerance) - Consensus nodes* are elected by NEO holders -> The Speaker is identified (based on algorithm) -> He broadcasts proposal to create block -> Each Delegate (other consensus nodes) validates proposal -> Each Delegate sends response to other Delegates -> Delegate reaches consensus after receiving 2/3 positive responses -> Each Delegate signs the block and publishes it-> Each Delegate receives a full block. Block reward 6 GAS distributed proportionally in accordance with the NEO holding ratio among NEO holders. Speaker rewarded with transaction fees (mostly 0).
* Stake 1000 GAS to nominate yourself for Bookkeeping(Consensus Node)
docs.neo.org/en-us/node/consensus.html#1-list-of-terms
docs.neo.org/en-us/

EOS (Delegated Proof of Stake) - those who hold tokens on a blockchain adopting the EOS.IO software may select* block producers through a continuous approval voting system and anyone may choose to participate in block production and will be given an opportunity to produce blocks proportional to the total votes they have received relative to all other producers. At the start of each round 21 unique block producers are chosen. The top 20 by total approval are automatically chosen every round and the last producer is chosen proportional to their number of votes relative to other producers. Block should be confirmed by 2/3 or more of elected Block producers. Block Producer rewarded with Block rewards.
*the more EOS tokens a stakeholder owns, the greater their voting power
https://github.com/EOSIO/Documentation/blob/master/TechnicalWhitePaper.md#transaction-confirmation
https://blog.cosmos.network/consensus-compare-tendermint-bft-vs-eos-dpos-46c5bca7204b

The XRP Ledger Consensus Process

Ripple - Each node receives transaction from external applications -> Each Node forms public list of all valid (not included into last ledger (=block)) transactions aka (Candidate Set) -> Nodes merge its candidate set with UNLs(Unique Node List) candidate sets and vote on the veracity of all transactions (1st round of consensus) -> all transactions that received at least 50% votes are passed on the next round (many rounds may take place) -> final round of consensus requires that min 80% of Nodes UNL agreeing on transactions. It means that at least 80% of Validating nodes should have same Candidate SET of transactions -> after that each Validating node computes a new ledger (=block) with all transactions (with 80% UNL agreement) and calculate ledger hash, signs and broadcasts -> All Validating nodes compare their ledgers hash -> Nodes of the network recognize a ledger instance as validated when a 80% of the peers have signed and broadcast the same validation hash. -> Process repeats. Ledger creation process lasts 5 sec(?). Each transaction includes transaction fee (min 0,00001 XRP) which is destroyed. No block rewards.
https://ripple.com/build/xrp-ledger-consensus-process/#footnote_from_5
https://ripple.com/files/ripple_consensus_whitepaper.pdf

The Stellar consensus protocol

Stellar (Federated Byzantine Agreement) - quit similar to Ripple. Key difference - quorum slice.
https://medium.com/a-stellar-journey/on-worldwide-consensus-359e9eb3e949
https://www.stellar.org/papers/stellar-consensus-protocol.pdf
https://www.stellar.org/stories/adventures-in-galactic-consensus-chapter-1/

Proof of Authority

VeChain - currently Ethash (PoW). Future implementation - POA. Transactions and blocks are validated by approved accounts, known as validators. The chain has to be signed off by the majority of authorities, in which case it becomes a part of the permanent record.
https://cdn.vechain.com/vechain_ico_ideas_of_development_en.pdf
https://www.reddit.com/r/Vechain/wiki/index
https://github.com/paritytech/parity/wiki/Proof-of-Authority-Chains

Proof of Burn

Slimcoin - to get the right to write blocks Node should burn amount of coins. The more coins Node burns more chances it has to create blocks (for long period) -> Nodes address gets a score called Effective Burnt Coins that determines chance to find blocks. Block creator rewarded with block rewards.
slimco.in/proof-of-burn-eli5/

Proof of Importance

NEM - Only accounts that have min 10k vested coins are eligible to harvest (create a block). Accounts with higher importance scores have higher probabilities of harvesting a block. The higher amount of vested coins, the higher the accounts Importance score. And the higher amount of transactions that satisfy following conditions: - transactions sum min 1k coins, - transactions made within last 30 days, - recipient have 10k vested coins too, - the higher accounts Important score. Harvester is rewarded with fees for the transactions in the block. A new block is created approx. every 65 sec.
https://nem.io/wp-content/themes/nem/files/NEM_techRef.pdf
https://nem.io/investors/harvesting-and-poi/#proof-of-importance

Proof of Devotion

Nebulas (Proof of Devotion + BFT) - quite similar to POI, the PoD selects the accounts with high influence. All accounts are ranked according to their liquidity and propagation (Nebulas Rank) -> Top-ranked accounts are selected -> Chosen accounts pay deposit and are qualified as the blocks Validators* -> Algorithm pseudo-randomly chooses block Proposer -> After a new block is proposed, Validators Set (each Validator is charged a deposit) participate in a round of BFT-Style voting to verify block (1. Prepare stage -> 2. Commit Stage. Validators should have > 2/3 of total deposits to validate Block) -> Block is added. Block rewards : each Validator rewarded with 1 NAS.
*Validators Set is dynamic, changes in Set may occur after Epoch change.
https://nebulas.io/docs/NebulasTechnicalWhitepaper.pdf
https://github.com/nebulasio/wiki/wiki

IOTA Algorithm

IOTA - uses DAG (Directed Acyclic Graph) instead of blockchain (TANGLE equal to Ledger). Graph consist of transactions (not blocks). To issue a new transaction Node must approve 2 random other Transactions (not confirmed). Each transaction should be validate n(?) times. By validating PAST(2) transactions whole Network achieves Consensus. in Order to issue transaction Node: 1. Sign transaction with private key 2. choose two other Transactions to validate based on MCMC(Markov chain Monte Carlo) algorithm, check if 2 transactions are valid (node will never approve conflicting transactions) 3. make some PoW(similar to HashCash). -> New Transaction broadcasted to Network. Node dont receive reward or fee.
https://iota.readme.io/docs/what-is-iota
iota.org/IOTA_Whitepaper.pdf

PBFT + PoW

Yobicash - uses PBFT and also PoW. Nodes reach consensus on transactions by querying other nodes. A node asks its peers about the state of a transaction: if it is known or not, and if it is a doublespending transaction or not. As follow : Node receives new transaction -> Checks if valid -> queries all known nodes for missing transactions (check if already in DAG ) -> queries 2/3 nodes for doublepsending and possibility -> if everything is ok add to DAG. Reward - nodes receive transaction fees + minting coins.
https://yobicash.org/whitepaper.pdf

Proof of Space/Proof of Capacity

Filecoin (Power Fault Tolerance) - the probability that the network elects a miner(Leader) to create a new block (it is referred to as the voting power of the miner) is proportional to storage currently in use in relation to the rest of the network. Each node has Power - storage in use verified with Proof of Spacetime by nodes. Leaders extend the chain by creating a block and propagating it to the network. There can be an empty block (when no leader). A block is committed if the majority of the participants add their weight on the chain where the block belongs to, by extending the chain or by signing blocks. Block creator rewarded with Block reward + transaction fees.
https://filecoin.io/filecoin.pdf

Proof of Elapsed Time

Hyperledger Sawtooth - Goal - to solve BFT Validating Nodes limitation. Works only with intels SGX. PoET uses a random leader election model or a lottery based election model based on SGX, where the protocol randomly selects the next leader to finalize the block. Every validator requests a wait time from an enclave (a trusted function). -> The validator with the shortest wait time for a particular transaction block is elected the leader. -> The BlockPublisher is responsible for creating candidate blocks to extend the current chain. He takes direction from the consensus algorithm for when to create a block and when to publish a block. He creates, Finalizes, Signs Block and broadcast it -> Block Validators check block -> Block is created on top of blockchain.
https://software.intel.com/en-us/blogs/2017/10/05/2017-a-summer-of-consensus
https://www.persistent.com/wp-content/uploads/2017/04/WP-Understanding-Blockchain-Consensus-Models.pdf
https://sawtooth.hyperledger.org/docs/core/releases/latest/architecture/poet.html#introduction
https://sawtooth.hyperledger.org/docs/core/releases/latest/architecture/journal.html

Other

Byteball (Delegated Byzantine Fault Tolerance) - only verified nodes are allowed to be Validation nodes (list of requirements*). Users choose in transaction set of 12 Validating nodes. Validating nodes(Witnesses) receive transaction fees.
*https://github.com/byteball/byteball-witness
https://byteball.org/Byteball.pdf

Nano - uses DAG, PoW (HashCash). Nano uses a block-lattice structure. Each account has its own blockchain (account-chain) equivalent to the accounts transaction/balance history. To add transaction user should make some HashCash PoW -> When user creates transaction Send Block appears on his blockchain and Receive block appears on Recipients blockchain. -> Peers in View receive Block -> Peers verify block (Double spending and check if already in the ledger) -> Peers achieve consensus and add block. In case of Fork (when 2 or more signed blocks reference the same previous block): Nano network resolves forks via a balance-weighted voting system where representative nodes vote for the block they observe, as >50% of weighted votes received, consensus achieved and block is retained in the Nodes ledger (block that lose the vote is discarded).
https://nano.org/en/whitepaper
https://github.com/nanocurrency/raiblocks/wiki/Block-lattice
https://github.com/nanocurrency/raiblocks/wiki/Double-spending-and-confirmation

Holochain - uses distributed hash table (DHT). Instead of trying to manage global consensus for every change to a huge blockchain ledger, every participant has their own signed hash chain. In case of multi-party transaction, it is signed to each party's chain. Each party signs the exact same transaction with links to each of their previous chain entries. After data is signed to local chains, it is shared to a DHT where every neighbor node validate it.
Any consensus algorithms can be built on top of Holochain.
https://github.com/metacurrency/holochain/blob/whitepaper/holochain.pdf
https://developer.holochain.net/FAQ

Komodo ('Delegated' Delayed Proof of Work (dPoW)) - end-to-end blockchain solutions. DPoW consensus mechanism does not recognize The Longest Chain Rule to resolve a conflict in the network, instead the dPoW looks to backups it inserted previously into the chosen PoW blockchain. The process of inserting backups of Komodo transactions into a secure PoW is notarization. Notarisation is performed by the elected notary nodes. Roughly every ten minutes, the notary nodes perform a special block hash mined on the Komodo blockchain and take note of the overall Komodo blockchain height. The notary nodes process this specifc block so that their signatures are cryptographically included within the content of the notarized data. There are sixty-four notary nodes elected by a stake-weighted vote, where ownership of KMD represents stake in the election. They are a special type of blockchain miner, having certain features in their underlying code that enable them to maintain an effective and cost-efcient blockchain and they periodically receives the privilege to mine a block on easy difculty.
https://komodoplatform.com/en/whitepaper/2018-02-14-Komodo-White-Paper-Full.pdf

This is really great, here is a visual summary

Credits to 101blockchains.com