What (tf) is Proof of work, Proof of stake, Proof of importance, Proof of burn and others?

How to achieve correctness in a decentralized environment?

Being decentralised and having no financial authority to validate the transaction, cryptocurrencies rely on cryptography (hence name cryptocurrency) to validate transactions and ownership of funds, achieve distributed consensus, validity and correctness.

Following sections describe most used ways to determine correctness:

Proof of work

Proof of work approach binds a certain amount of work to be performed for every single operation in order for the operation to be performed. In essence, that work is useless for the operation itself but it is used to deter malicious users from altering the history of the open ledger. Given that underlying technology is a blockchain (chained blocks of transactions), a user can’t just change one record. A user would need to change every record made after that one, and in order to validate all those changes, a user would need to perform required work for all of those changes. (1)

Surely good way to prove the work

Idea is that if operation is valid, amount of required work for one transaction is certainly insignificant, but if malicious user wants to change history of the open ledger, amount of work multiplies and exponentially rises effort up to point where is not viable to do it and decreases real benefit for that user to perform malicious operation, which makes ledger and transactions in it immutable.

Initially developed for combating network service abuse like denial of service attacks or spamming, (2) this method became most known and most used method for cryptocurrency validation.

This method is criticized from the environmental point of view as it requires constantly increasing, a high computational process which results in high energy consumption. By one estimate from 2014, a network of nodes used for processing Bitcoin transactions might consume as much electric power as the entire country of Ireland. (3)

In simple words:
Proof of work protection means the computer is required to do mathematical work for every transaction it approves (called mining) which is not a problem for valid transactions but would make rewriting history impractical and very expensive.

Proof of stake

Proof of stake algorithm nominates users not participating in the transaction to validate and approve that transaction. Users are selected randomly and unpredictably from a group of users that are having the largest amount of funds in given cryptocurrency, which means they have the biggest stake. The idea is that those users having collateral would be most interested in the legality of that cryptocurrency hence they would not validate random malicious transaction they don’t participate in.

The advantage of Proof of stake over the Proof of work is that it does not require computationally intensive mathematical puzzles and with that, it uses significantly less computational power and energy. (4)

This method is however vulnerable to so-called “nothing at stake” attacks, in which attackers could cash out the stake and rewrite the history from the point where they still had the stake. (5) To minimise the possibility of those attacks some cryptocurrency networks perform occasional Proof of work verifications to establish irreversible checkpoints.

Above process of verification would, of course, happen by use of computer software, a user would not approve and validate transactions manually.

In simple words:
Proof of stake means approval of transactions is assigned to users with the largest amount of funds or largest stake as it would be irrational they would approve random malicious transactions.

Proof of importance

This approach builds on top of the Proof of stake but adds additional requirement when choosing the user that will verify the transaction. Along with considering the volume of funds user currently possess in given cryptocurrency, it also considers previous history or number of valid and approved transactions user made in given currency, hence adding to user’s trustworthiness. (6) (7)

Proof of Importance — the more you have the more you want to protect it

It solves the potential problem of Proof of stake where a malicious user could buy large amounts of cryptocurrency in order to increase chances to be chosen for validation. (8)

In simple words:
Proof of importance extends Proof of stake by considering also how many transactions user made when assigning the task of approving transactions.

Proof of burn

Similar to Proof of work this approach aims to make irrational and expensive for the malicious user to change information in the open ledger but at the same time inexpensive and simple for all other users to verify that verification was done.

Instead of giving the miner specific work to do this approach specifies that user will send small amount of underlying asset to verifiable unknown and unused address, which is usually predefined at the beginning of the ledger. Coins sent to that address are practically destroyed, not possible to be used by anyone (hence word burning) and makes expensive for anyone to change the history by altering previously approved blocks and all succeeding blocks. On the other side, every other node can easily verify if block was properly validated by checking whether the user that validated the block made the transaction to the unused address. (9) (10)

Throwing the money to prove the value

Interestingly this method has two additional implementations:

  • bootstrapping two currencies — new currency can be bootstrapped on top of the other currency when it is defined that for each verified block in chain small amount of bootstrapped currency needs to be spent. (11)
  • reducing supply — if during Initial Coin Offering (ICO) definite amount of coins is created and offered for sale, authors of that currency can decide to burn remaining unsold coins to decrease supply and influence raise in the value of the coin. That approach might not be necessary for currency where coins are created automatically so that supply is adjusted or if the value of the coin at the end of ICO is not crucial. (12)
In simple words:
This approach obligates spending a small amount of underlying asset - coins in order to validate blocks and transactions in it, making it expensive and irrational to make changes in the history of the open ledger.

The Ripple Protocol Consensus Algorithm (RPCA)

As described in the RPCA whitepaper aim of this algorithm is to resolve the issue of low latency connected with above-mentioned ways of approving transactions due to the fact that in RPCA nodes don’t have to come to consensus synchronously. (13) Low latency is achieved by enabling each participant to maintain own list of trusted nodes or own subnetwork in other words. That means consensus needs to be achieved only with nodes in user’s list of trusted nodes instead of nodes participating in the whole network, decreasing the time needed to achieve consensus. Each node can be cryptographically identified so it is possible for each user to participate only with nodes that user trusts. (14) (15)

This approach brought a lot of controversies as cryptocurrency was initially defined as means to be completely decentralised enabling monetary transactions without the need to trust any other peers, which is why some call it alt-currency instead of cryptocurrency. (16)

Initially, users are presented with a list of the random nodes, decreasing the possibility of nodes colluding with each other on malicious activity. A user can modify that default list. (17) List of trusted nodes is not symmetrical meaning that nodes user trusts don’t necessarily mean will return back in equal trust, each user defines own list of trusted nodes. Hence, each user is motivated to perform and verify valid transactions as opposite behaviour would soon raise the flags and potentially would result in removal from lists of trusted nodes other users have and isolating the rouge node.

Resolving conflicts on distributed and decentralized ledger requires a “geek” solution

This algorithm uses Byzantine agreement system with a difference that it gives users option to control which users will participate in transaction verification instead of enabling random users to join the subnetwork. This behaviour counteracts so-called Sybil attacks where malicious users join the subnetwork multiple times in order to avoid system’s failure tolerance.

In order to achieve consensus algorithm (RPCA), is applied every few seconds by nodes, each node takes all valid transactions and makes them public as “candidate set”. Each node processes the candidate sets from its list of trusted nodes and votes on whether transactions are valid. Transactions that receive 80% of positive votes are considered valid and are added to the ledger and small amount of coin will be destroyed in order to prevent the abuse of the network (proof of burn). (18) Transactions that receive a minimum-required percentage of positive votes are transferred for next round of voting. Minimum-required percentage increases with each round of voting and pending transactions either eventually get up to 80% of positive votes or get discarded. (19)

Both RPCA and SCP feature modest computing and financial requirements, lowering the barrier for participating nodes as a difference to, for example, proof of work which rewards best performing nodes in the network. This means opening up financial systems to users in developing countries.

In simple words:
RPCA doesn't require transactions to be approved by all nodes in the network. Each user has a list of node it trusts for approval of transactions, but system does provide at the beginning default list of nodes

Stellar Consensus Protocol (SCP)

This protocol describes a way of achieving consensus authors call federated Byzantine agreement (FBA). (20)

As with any other Byzantine agreement protocol, this protocol features fast processing of transactions because transactions are not validated with all nodes but rather with a smaller subnetwork of nodes. The difference is that instead of each node choosing own list of trusted nodes in SCP any node can join any node as trusted provided it complies with rules. (21) (22)

The protocol specifies functions to maintain network’s safety (ability to achieve consensus and to recognise ill-behaved nodes) and liveness (ability to add new values without being blocked by ill-behaved nodes). (23)

Nodes that are participating in the validation of block will verify transactions using Proof of burn approach. (24)

In simple words:
SCP also doesn't require transactions to be approved by all nodes in the network. But instead of each user choosing nodes, it trusts for approval of transactions, any node can join any other node to process its transactions. Mathematical functions provided by this protocol are used to control the validity of nodes.

The Tangle (directed acyclic graph — DAG)

Instead of rewarding users for their validation of transactions, this protocol required users to cooperate in the validation of two or more transactions chosen by the algorithm in order to be granted the right to make one transaction (25) and in essence is not truly blockchain technology as it uses directed acyclic graph (26) but is included in this research as it provides the platform for IOTA and its underlying cryptocurrency MIOTA.

The intention was to reduce the cost of making transactions which would be appealing to the systems with a large number of low transactions (micro-payments). (27)

A node will not approve conflicting transactions and in order to validate the transaction, a node must do mathematical work similar to what Proof of work describes.

In simple words:
Nodes do the work similar to the proof of work but are not incentivised to perform validation of transactions. Instead, for every two processed transactions, a node is granted with the right to make one own transaction.

  1. “Proof of work” May 15, 2016. Bitcoin Wiki.
  2. “Pricing via Processing, Or, Combatting Junk Mail, Advances in Cryptology”. CRYPTO’92: Lecture Notes in Computer Science №740. Springer: 139–147. Author: Dwork, Cynthia; Naor, Moni (1993).
  3. “Bitcoin mining and its energy footprint” June 27, 2013. IEEE Authors: Karl J. O’Dwyer — Hamilton Inst., Nat. Univ. of Ireland, Maynooth, Ireland and David Malone — Hamilton Inst., Nat. Univ. of Ireland, Maynooth, Ireland
  4. “Nxt Network Energy and Cost Efficiency Analysis” (PDF). Retrieved January 3, 2015. Author: Matthew Czarnek
  5. “Hard Problems of Cryptocurrencies”. December 19, 2017. Ethereum
  6. “NCDawareRank: a novel ranking method that exploits the decomposable structure of the web” February 08, 2013 WSDM ’13 Proceedings of the sixth ACM international conference on Web search and data mining. Authors: Athanasios N. Nikolakopoulos — University of Patras & Computer Technology Institute and Press Diophantus, Patra, Greece and John D. Garofalakis — University of Patras & Computer Technology Institute and Press Diophantus, Patra, Greece
  7. “Proof of Importance”, Retrieved: February 2, 2018. Smith And Crown Research Group
  8. “Proof-of-Importance: How NEM is Going to Add Reputations to the Blockchain” March 13, 2015. Coin Telegraph. Author: Alireza Beikverdi
  9. “Slimcoin — A Peer-to-Peer Crypto-Currency with Proof-of-Burn — Mining without Powerful Hardware” May 17, 2014. Author pseudonym: P4Titan (p4titan@anche.no, slimcoin@anche.no)
  10. “How does Proof of Burn work?” January 3, 2017. Author pseudonym: UTF-8
  11. “Proof of burn: Use for bootstrapping” January 15, 2018. Bitcoin Wiki
  12. “Why Burn Cryptocurrencies?” November 24, 2017. Invest In Blockchain. Author: Jorn van Zwanenburg — technology and innovation MBA graduate
  13. “The Ripple Protocol Consensus Algorithm” 2014. Ripple Labs Inc. Authors: David Schwartz — david@ripple.com, Noah Youngs — nyoungs@nyu.edu and Arthur Britto — arthur@ripple.com
  14. “Two US banks are ready to embrace the Ripple protocol, allowing instant global money transfers” Sep 24, 2014. Gigaom, Knowingly, Inc. Author: Biz Carson
  15. “Ripple Labs Banks $3.5M for Open-Source Payments System and Virtual Currency”. Dow Jones & Company. Retrieved January 28, 2014.
  16. “$100 Billion Controversy: XRP’s Surge Raises Hard Questions for Ripple”. January 4, 2018. CoinDesk. Authors: Michael del Castillo & Bailey Reutzel
  17. Liu, Alec. [^ “Introducing Ripple”. February 26, 2013. Bitcoin Magazine. Author: Buterin, Vitalik
  18. “Fees (Disambiguation) — In the Ledger — Neutral Fees” Retrieved: February 2, 2018, Ripple.
  19. “The XRP Ledger Consensus Process” Retrieved: May 9, 2015. Ripple. Authors: Dave Cohen, David Schwartz, and Arthur Britto.
  20. The Stellar Consensus Protocol: A Federated Model for Internet-level Consensus, February 25, 2016, Stellar Development Foundation. Author: David Mazières
  21. How Stellar works Retrieved: February 2, 2018. Stellar.
  22. The New Stellar Consensus Protocol Could Permit Faster and Cheaper Transactions April 17, 2015. Bitcoin Magazine. Author: Giulio Prisco
  23. A New Competitor for Bitcoin Aims to Be Faster and Safer April 15, 2015. MIT Technology Review. Tom Simonite — https://twitter.com/@tsimonite
  24. Fees | Stellar Developers Retrieved on February 2, 2018. Stellar.
  25. The Tangle, Version 1.3 October 1, 2017. Author: Serguei Popov — serguei.popov@iota.org
  26. Directed Acyclic Graph DAG (Tangle) is not Blockchain April, 2017. Satoshi Watch. Author: Jabba-Q
  27. IOTA Tangle: Introductory overview of white paper for Beginners Sep 27, 2017. Author: Jeff Hu — https://twitter.com/jj1385jeff85051