Alternatives to Proof of Work: Part 1

Alternatives to Proof of Work: Part 1

- 5 mins

What is Blockchain Consensus

A blockchain can be thought of as a community driven ledger for a cryptocurrency. It logs every transaction and keeps track of who has how many “coins”. These ledgers are broken into blocks, each block pointing back to the previous one. As of March 29, 2017 the average number of transactions per block is about 2000.

blockchain

Now these blocks, before being commited to the chain, must be approved. Since there is no central authority, this must be done through a group consensus. Obviously there must be some way to hold people accountable to checking transactions honostly, and not trying to approve bad or perhaps malicious transactions.

As an example scenario without some checks and balances:

The above is an example of what’s called Double Spending.

A naive solution to this problem is to require a certain number of people to approve blocks. Although an easy attack would be to create many false identities, all of whom approve the block your transaction is in. This is called the Sybil Attack.

Many of the following consensus protocols are based off of this naive solution, but they add on a cost to approving blocks, so that a single person can’t freely create new identities. With this cost there must be some kind of award, in order to incentivize people to approve blocks. This reward is usually some of the networks cryptocurrencies, either taken from transaction fees, or created from scratch.


Proof of Work

Overview

One method to prevent users from using multiple fake identities on the network in order to approve their bad transactions is to include some sort of cost to approving. The basic idea of proof of work is to force users to do some amount of computational work before they can sign off on a block. A malicious user can easily fake multiple identities, but they cannot fake computational work.

The basic proof of work algorithm bitcoin uses is based off of a similar algorithm called hashcash. Some key elements of both bitcoins algorithm and the hashcash algorithm is that they are:

  1. publicly auditable - anyone can check the result of the proof of work to see that it is correct
  2. non-interactive - the server doesn’t need to issue some challenge to the user. The user picks the challenge themselves
  3. trapdoor free - there is no known solution to the challenge beforehand
  4. unbounded probabalistic cost - It could theoretically take forever to solve the challenge

Bitcoin’s proof of work algorithm is based on the SHA-256 hashing algorithm. You are given a block of transactions, and after making sure that every transaction is possible given the previous blocks, you create a header for this block. This header consists of…

  1. Version
  2. Hash of previous block’s header
  3. Hash of all transactions in current block
  4. Current timestamp
  5. Current target (explained later)
  6. Nonce (explained later)

Now your goal is to find a hash of this header, that is less than a certain target number. The only values that you can change is the 32 bit nonce at the end. Normally you would start with a nonce of 0 and increment every try, but it doesn’t really matter.

Since SHA-256 is a one way function, meaning you can’t work backwards from a hash to a particular starting number, and there is no way to predict what you are going to get until you calculate it, the only way to try and find a nonce that produces a hash below the target is by brute force. Once you do find a correct nonce that produces a hash below the target number, you can broadcast the block with the correct header, and receive your payment.

There must be some way to incetivize people to confirm that transactions are valid, and this is done by paying them in bitcoin every time they successfuly confirm a block. These bitcoins come from transaction fees, and are created out of thin air. This is how the network of bitcoin grows.

The target value is a result of an algorithm based on previous blocks time to mine, and the goal is to mine a block every 10 minutes. So as computers get more powerful the target number can get smaller and smaller, making a successful hash harder and harder to find.

Pros

Cons

rss facebook twitter github youtube mail spotify lastfm instagram linkedin google google-plus pinterest medium vimeo stackoverflow reddit quora