Blockchain Consensus Algorithms – Proof of Anything?

Blockchains have been proven over the last years to be stable distributed ledger technologies. Stable refers to the fact that they can recover from attacks and/or bugs without compromising their assets. They are most commonly known for enabling transaction with virtual cryptocurrencies not issued by a central authority. Popular examples are Bitcoin and Ethereum. However, both have been forked to create also alternative coins (Altcoins) having different features. For instance, Namecoin, the first fork of Bitcoin, is a cryptocurrency providing at the same time distributed domain name and identity without relying on a central authority. Thus, it is more resilient to censorship or potentially not democratically elected central authorities governing it.

Of course at the same time this new technology – as all new technologies – have some risk because they need to be properly understood by their users. Initial Coin Offers (ICO) that fork from popular blockchains (or not even do this) may be part of frauds or scams.

Hence, it is important to understand their key mechanisms and this blog post describes one of them: Establishing consensus of transactions happening on a blockchain. Without secure consensus it is possible to steal value (coins) or manipulate entries in the blockchain. The consensus is usually decided by a participant that can provide a proof of something. This something differ in the different consensus mechanisms.

About Blockchain Consensus

One should not confuse blockchain consensus with consensus in distributed systems. Consensus in distributed systems is about agreeing on a certain data value during computation. The idea is to reach a common state among several copies of data despite of failure, network partitioning or even manipulation by the replicas. Paxos and Raft are typical algorithms/protocols to reach consensus and they require to elect a leader, which can be anyone involved in the consensus and it stays as long as it not fails.

Blockchain consensus is an economic consensus which is different, the economic participants (which are in the end humans) have a common economic interest to reach economic consensus:

  • Preserve the value of their cryptocurrency assets. This especially means double-spending should not be allowed and can be detected.

  • Leader election: The entity deciding consensus on a given block in the blockchain gets superior benefits (besides value preservation). This means leader should change very frequently and a transparent mechanism for changing the leader should exist.

  • All participants of the economic consensus can verify that the leader made a correct decision (ie produced a valid block). This is also needed so that the leader cannot modify transactions , e.g. their value or destination.

  • Timely communication with all participants before the leader decides on a given block or for electing a leader is seen as infeasible.

  • Produce a block with high probability in given timeframes (e.g. within 10 minutes) to avoid that participants leave the blockchain due to lack to transfer their cryptocurrency assets at any given point in time.

Why would they have such an interest? They all have assets (financial/non-financial) that they want to preserve. Hence, most of the participants also do not have an incentive to cheat or that they fail to agree on a state of the ledger, because if cheating is detectable or preventable (and it is with an adequate blockchain consensus algorithm) then the value for all participants diminishes. Of course outsiders may want to destroy a blockchain and thus attack the whole blockchain, because they have no stake in it – this would be comparable to burning physical money of another currency.

Leader election is different here – the different participants do not necessarily trust each other and especially do not want that one stays leader for a long time, because the leader benefits heavily in economic terms, for example, fees that are charged and the leader can decide to include certain transaction only, e.g. those of a minority of peers (“friends”). This ultimately leads to a situation where they cannot preserve the value of their assets.

Additionally, it can happen in blockchains that participants do not agree on a common data value during computation and this leads to a fork of the blockchain. In this case this is temporary or permanent dependent on what the participants want. For instance, some participants may want – and that happen in the past – create a separate blockchain from one originally common blockchain with other participants (e.g. the split between Bitcoin Core and Bitcoin Classic or Ethereum Core and Ethereum Classic). Then, consensus might be based on different rules. In fact, such a situation has never been consider in distributed consensus.

As you can see blockchain consensus and consensus in distributed systems are very different. Economic, governance and human factors make it different from consensus in distributed systems. That is why successful blockchain consensus algorithms are fundamentally different from consensus algorithms in distributed systems. One famous example is the proof of work algorithm that is used in the Bitcoin Blockchain. Additionally, the application of consensus algorithms of distributed systems has not been very popular, although some blockchains try to employ them for closed networks with selected participants only, which makes using blockchain technology meaningless.

Algorithms for Proof of Anything

Proof of Work

Bitcoin as the first practical successful cryptocurrency introduced the Proof-of-Work (PoW). However, it was not the first one as the Bitcoin paper stated. HashCash and others have proposed a similar approach mainly to address the issue of junk mail. The idea there was that someone has to prove to that some investment have been taken before sending an email. This would make sending junk mails not rentable.

Basically the proof-of-work demonstrates that a participant has done some work and gets a reward.

For example, a simplified version of the proof-of-work in Bitcoin is that a block including relevant parts of the transaction are hashed and a random nonce is added to it so that the resulting hash is below a certain value (the difficulty).

PoW has the following characteristics:

  • It must be predictable hard to obtain. For example, Bitcoin has as a rule (which of course could be change if a majority would vote it) that on average every 10 minutes a new proof-of-work (ie a block) can be generated.

  • It must adapt to innovation. For instance, new more powerful hardware may make a proof-of -work obsolete if it does not become more difficult. If a PoW is generated to fast then the network can be subject to double-spending attacks or one participant might have a monopoly as a leader on the network. Additionally, it must be able to withstand new technology, such as Quantum Computers or ASICs.

  • It must adapt to network power. For example, if the difficulty grows too much and it is too hard to solve then cryptocurrency assets loose in value, because it will take too long to transfer ownership. Hence, difficulty of the PoW must be able to grow and shrink according to network capacity to solve it. This is the case for all cryptocurrencies including Bitcoin.

  • It should be equally difficult for anyone to generate it, ie there should be not a centralization of several entities that are able to generate a PoW. This is somehow not exactly a black and white thing, but more greyish, because even in Bitcoin this is currently not fully ensured due to the appearance of ASICs.

  • It must be extremely fast to verify that it has been done by any other participant.

  • It must not be possible to give completely new nodes a long fake chain to dissolve the network and make it attackable. In fact, Bitcoin contains checkpoints that are hardcoded as consensus rules, ie certain block hashes at given points in time are valid and thus new nodes can start validating from a later stage to early detect if a fake blockchain has been supplied to them or not. Since Bitcoin is Open Source this is a somewhat transparent mechanism to which all participants have to agree on.

Although most of the PoW systems are CPU bound, the characteristics do not prevent that it is bound by anything else, such as memory. Theoretically, one could also imagine other PoWs, such as based on information entropy, colliders, speed of light or quantum computing-specific aspects (example). However, such a PoW system must be available to all participants and satisfy the characteristics above. Nowadays most PoW systems are solving hash-based problems (e.g. SHA2-256, SHA3, Scrypt or mixtures of different hash algorithms).

One main critic point of PoW is that a lot of energy is “consumed”. I purposely do not write here wasted, because the PoW ensures functioning of the cryptocurrency and as we will see later no viable alternatives currently exists for public blockchains. Additionally, one should keep in mind that payment processing, clearing, physical money, credit cards, server energy etc. have also an energy footprint, but there has – at least known to me – never been a study on this to compare if the PoW is more energy hungry (first attempts exist, check cf. here).

However, there have been attempts to improve the PoW. For example, some cryptocurrency have as PoW a more or less meaningful problem (Proofs of Useful Work – PoUW), e.g. Primecoin searches for chains of prime numbers. Meaningful usually implies a mathematical problem, which is simple to describe, but fulfills some or even better all characteristics above. It needs to be simple to describe, because if it is complex to describe then it is complex to understand, difficult to test and prone to errors. Permacoin uses PoW for distributed storage of achival data, ie one needs to provide storage to solve the PoW. Gridcoin attempts to solve scientific problems.

Nevertheless, they may not be able to fulfill all the characteristics mentioned above, which explains their limited popularity for cryptocurrencies. However, there has never been – to my knowledge – a complete study and comparison of all these mechanisms including quality (testing!), ecological, economic and socio-economic effects.

Others try to reuse an existing PoW. In fact, in some sense the PoW is reused in Bitcoin, because if a transaction is included in a block its output can be reused in other transactions. Other approaches, such as merged mining, allow at the same time merging for different blockchains using the same work (e.g. Bitcoin and Namecoin).

Finally, another criticism of PoW is that it is slow. Usually the Bitcoin delay of 10 minutes on average for generating is cited. However, these 10 minutes are a deliberate decision by the originators of Bitcoin and is not a technological limit. In fact, at any time this could be changed by a majority to be more or less. However, having less time might have significant security and economic impact, which needs to be carefully weighted. Furthermore, with the existence of side-chains, such as the Lightning network, this rule can be probably avoided more elegantly and allow scaling to payment processing similar to popular payment networks.

Proof of Stake

Proof of Stake (PoS) is another way to establish economic consensus.

PoS is basically about voting on the next block in a blockchain based on the economic stake into the network. A stake could be for instance be determined based on a stake of a number of cryptocurrency assets in a locked deposit or the stake of CPU/memory/energy/etc. in the network. Variants of it includes differences between who can propose a new block (consensus) and who can vote on it. The idea is that someone who has a lot of stake will not do anything to endanger this stake, such as cheating, because then it would become less valuable.

However, PoS has not been as successful as Proof-of-Work. Currently, none of the large cryptocurrencies uses this. Nevertheless, for Ethereum it was initially assumed to be used instead of PoW (“Slasher”), but currently Ethereum only supports PoW (Ethash). The reason was according to the originators that proof-of-stake is non-trivial.

The characteristics of PoS are the following:

  • Votes on a new block are according to economic stake in the blockchain of a participant. However, it should be avoided that there is a centralization towards the “richest” participant. This is usually done by differentiating between block proposers (which might be random or according to another rule) and block validators (that have a stake)
  • Economic stake may change and is not fixed.
  • It should not be possible to revote once a vote has been done and exists in a network since some time, but not too long. It should not be possible to vote on several alternative chains of the same blockchain. This implies that the economic stake must be at risk in case of abuse (“nothing at stake problem”).
  • Nodes need to be online, ie connected to other nodes, to vote with a relevant stake.
  • The vote needs to terminate with an outcome (yes/no) after a certain short amount of time.

The main difference it seems is that reward for work is replaced by vote based on stakes. Somehow the PoS can be compared with shareholder votes.

One interesting question is how such stakes can be distributes initially. Some cryptocurrencies sell stakes on their initial offering for Fiat currencies or already working (“bootstrapped”) cryptocurrencies, such as Bitcoin. This has recently led to a number of fraud initial coin offerings (ICO). The reason is that it is virtually impossible for participants to find out if a cryptocurrency will be successfully adapted or not (or if it even exists), which implies a very high risk. Then, even afterwards wrong decisions can render a cryptocurrency valueless.

Several theoretical ideas have been proposed for PoS, but they rarely end up in public blockchains, because of the inherent issues which are non-trivial. It is significantly more complex to implement compared to a PoW in case of decentralized public blockchains. It involves potentially several roles (e.g. proposer, voter and validator) that need to communicate actively (in PoW it is passively). Furthermore, it can be (but not need to be) less transparent than PoW, because the stakes and their development over time might be difficult to monitor (here dedicated analytics software may help). Examples are the previously mentioned Slasher protocol, the new protocol proposed by Ethereum (Casper) or the minting by Peercoin (basically based on coin age).

Practical examples for PoS exists, such as Peercoin, but there is one disadvantage is that only one person (of unknown identity) has the ability to invalid any chain at any point in time from anywhere. The reason for this checkpointing mechanism was the nothing at stake problem. However, meanwhile this mechanism will be chnaged for Peercoin.

These practical examples are nonetheless not as successful currently as cryptocurrencies based on PoW.

However, it has also some advantages, such as potentially lower energy consumption or the setup of more sophisticated governance mechanisms (including everyone).

Proof of Burn

Proof of Burn (PoB) is currently only a theoretical concept that has appeared in the Bitcoin mailing lists as an alternative to PoW. It should be seen as work in progress, because it has not yet been written formally down and analyzed.

This should not be confused with burning coins of one cryptocurrency to create coins of another cryptocurrency. This would be a more complex scenario related to PoB.

PoB works as follows: Someone sends some amount of cryptocurrencies (e.g. Bitcoins) to a destination from which they cannot be used anymore, ie they become provable unspendable (hence the analogy of burning it). After a certain amount of time (e.g. two months) a participant can propose a new block and have as a proof the burned amount of cryptocurrency.

Some might ask why someone would do such a thing to spend money just to propose a new block. Remember what I said in the Proof-of-Work section: The proposer of a block gets superior benefits, such as transaction fees. Obviously, for this to work the burned amount of cryptocurrency must be lower then the transaction fees.

The proposal might not be as senseless as it looks like, because its supporters argue that even for PoW some money needs to be burned by buying equipment to do the proof of work.

Furthermore, it requires that a certain amount of cryptocurrency is already there (e.g. generated via PoW).

PoB has also further implications that are not yet well-understood. Very few preliminary implementations, such as Slimcoin based on Peercoin, exist that should be seen with care.

Proof of Elapsed Time

Proof of Elapsed Time (PoET) attempts to address the problem of proof-of-stake that random election of participants proposing blocks is needed to ensure that every participant has a fair chance to propose a block and thus generate superior benefits.

The idea is the following: Every participant requests a wait time from its local trusted enclave. The participant with the shortest wait time is next to propose a block, after it waited for the assigned waiting time.

Each local trusted enclave signs the function and the outcome so that other participants can verify that none has cheated on the wait time.

As such it seems and it has been claimed by the people proclaiming PoET that it fulfills the characteristics of PoS described above.

The concept was first proposed by Intel as part of its HyperLedger Sawtooth Open Source technology, which is no surprise, because it is another use case for its SGX technology providing the enclave.

Although the approach does not prevent mixing or using other secure enclaves besides the Intel one, it has – to my knowledge – not yet been proposed (e.g. based on AMD Secure Memory Encryption (SME)/Secure Encrypted Virtualization (SEV)).

There are some things that you need to be aware of using this approach:

  • The secure enclave is rather complex technology which makes breaking it potentially easier than cheating in PoW.

  • In order for participants to verify that a secure enclave has provided the value they rely on a third party trusted certification authority or web of trust that signs the keys of a secure enclave. Hence, there is a clear tendency towards centralization, which is avoided in other PoW or PoS scenarios.

Practical Byzantine Fault Tolerance

Practical Byzantine Fault Tolerance (PBFT) is a consensus algorithm which is normally used for consensus in distributed system and as argued before does not really fulfill the requirements for economic consensus in blockchains.

Since PBFT becomes infeasible in networks with a number of nodes due to the required communication, blockchain technologies using PBFT only rely on a trusted subnetwork of participants to establish consensus (e.g. unique node list for each participant in Ripple). This poses some problems:

  • How large should this list be and how should a “normal” participant know who to include in its trusted network?
  • How can a participant detect forks of the blockchain (e.g. servers changing their trusted subnetwork)?
  • What is the incentive for a participant to participate in a consensus? There is no transaction fee per se foreseen in the consensus.

PBFT is advocated by a few blockchain technologies, such as Ripple as described here or Stellar. There, the use case however is also slightly different, it is more about connecting large banking networks and not anyone as in other blockchain technologies. Hence, most of the questions stated before may have a clear convincing answer. Additionally, transaction fees are introduced by burning a certain amount of currency in each transaction – none of the participants has access to the burned amount of currency. This is used to avoid that the blockchain is flooded with large number of transactions to render it useless or to get economic benefits from it. Hence, for these kind of special blockchains with a specialized set of participants this mechanism can still make sense.

Conclusion

Blockchains have been proven as mature technologies as public examples, such as Bitcoin or Ethereum demonstrate. However, from an Economic perspective not all mechanisms are well understood, especially due to the huge variety of concepts and their rapid development. This had also let to frauds of fake cryptocurrencies and blockchains as part of certain initial coin offerings (ICO). Furthemore, different type of participants in different types of blockchains making it even more difficult to understand the context.

Although it seems that PoW is dominating now, it is more suitable for public blockchains independent of any central entity. This might not be desired, because a central entity can ensure with right policies that every participant as access to the blockchain, protected from other participants and the same rights as well as responsibilities, similar as it is already now with Fiat money. Hence, PoS systems may gain more traction because they have a more flexible governance model than PoW. They could evolve in a system of proof of mastery, e.g. a certain subset of participants in a blockchain proposes new blocks, because they have been delegated this task by all the other participants. This subset of participants will use open source software, analytics on the blockchain and provide transparent mechanisms as well as information to all the other participants that delegated their stake to them.

However, due to the inherent challenges of PoS, combined systems out of PoW/PoS/PoB may be ultimately the successful one. There seems to be a tendency towards this (e.g. Casper for the Ethereum blockchain). Given the different approaches a lot of different combinations are possible. For instance, one can have PoS for the “daily” business of creating blocks, but PoW for checkpointing the blockchain at certain points in time.

Nevertheless, all these systems can only be successful and transparent if powerful analytics software is available to any participant, so they can track the effectiveness of decisions within certain blockchain technologies and derive appropriate consequences out of it.

Keep in mind that not only the Proof of Anything (PoW, PoS, PoB etc.) is here a challenge, but also other powerful groups, such as developer who can write blockchain technology – they tend also towards centralization of a single group and they have a lot of power.

In the future, we will see more cross blockchain activities challenging how cryptocurrencies from one chain can end up in another chain (e.g. via PoB). Similar to the nowadays exchanges for Fiat money, there will be always the need for exchanging different cryptocurrencies. There will be not one cryptocurrency, but always many due to different interests of participants or embarkment on new technologies.

Furthermore, we will need to deal with automated non-human participants within the blockchain. Robots or “things” may have a certain amount of cryptocurrencies to perform tasks, e.g. an autonomous car that needs to pay highway tolls (assuming there is no reason anymore that an automated car is “owned” but exists on itself and makes money by bringing passengers from A to B). These types of participants may have different incentives/requirements of economic consensus.

Advertisements

1 thought on “Blockchain Consensus Algorithms – Proof of Anything?

  1. Great post. Thanks

    The idea that people can agree without having a middleman to trust is at the centre of all of this, the consensus algorithms do that. The idea has been made believable by Bitcoin, and now many others, using and evolving the blockchain technology.

    It is the next wave in the internet evolution. Services decentralised, distributed, secured, and everyone is controlling and policing it, unlike all the information that is currently under propriety of the Big techs google, amazon, facebook, twitter etc. They have the information and control, and they profit from it, while we have no say.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s