Proof of what? Part 1 — Beginner

The math you skipped in the whitepapers. Different Consensus protocols.

This will go through each of the main solutions to the Byzantine Generals Problem that Bitcoin and other cryptocurrencies aim to solve.

Why do we need to solve this?

Let’s do a quick background on the blockchain. Here are two analogies:

1. Imagine a group of accountants in a room all ready to take notes. Randomly (depending on the different consensus protocols that we’ll talk about below), one of them gets up and goes to the front of the room and announces a list of transactions and how to record them. Everyone agrees and writes it down. If someone leaves, nobody will care because everyone else still has the same list of transactions.
2. There is a google sheet/public ledger that everyone has access to add, but not update or delete (append only). It has three columns: from, to and amount. If I want to see how many coins somebody, say Joe, has, I look at all the times Joe sent coins (from = “Joe”) subtracted from all the coins Joe received ( to = “Joe”). When you want to send money, you put the transaction (from, to, amount) into another sheet (often called the mempool) and wait for a verified user to put your transaction into the main sheet/ledger.

These are simplified analogies, but they will help us dive into relevant content. The main question we will answer in this article is (in the context of our analogies)“who gets to go to the front of the room?” or “who gets to add transactions/be verified?”

We need the people who add transactions to have an incentive to only submit valid transactions and make sure that when somebody new comes into the room, they only receive the correct history.

Let’s start with proof of work (the OG for cryptocurrencies) and work our way through a couple others:

Proof of Work (PoW):

How do you prove that you’ve done computational work?:

If I wanted to prove that I’ve done work, I would have to compute something that

1. I know can’t be cheated and
2. is easy for everyone to verify.

A couple options are:

• factoring large numbers or
• picking a random number that’s been selected.

The problem with the first case is that we don’t know how much work is expected when the problem is given, unless everyone does the work and reports.

Ultimately, we are looking for a computational puzzle that is easy to verify that a possible solution is correct, but hard to generate that solution.

The one used in Bitcoin is defined as follows:

Find X, such that Hash(X) < Z

Here X = Header = previous block + all_transactions_of_block + nonce

and Z is the target which is 2²⁵⁶ / difficulty.

A Hash Function is a function that maps, seemingly randomly, inputs to outputs. You can try the one Bitcoin uses here. See that even a one character change, completely changes the output in a seemingly random way.

A nonce is similar to a random extra number. Here we use it so that we can keep trying solutions until Hash(X) < Z. As we keep incrementing the nonce, we will get different results for Hash(X).

When you mine, you keep increasing the nonce (say 1,2,3,4,5,….) until you find a solution or someone else does.

h = Hash(Header)

If (h < target) then mine block

Otherwise try a new nonce

Bitcoin chooses SHA256 as its hash function.

In all_transactions_of_block, the miner includes a transaction with their unique public address (called the coinbase transaction), so that the solution is unique for the miner and can’t be stolen without recomputing the work. (Hence the proof of work)

The cryptocurrency code automatically adjusts the difficulty (currently every 2016 blocks for Bitcoin) so that the expected value to find a solution by one of the nodes is the “block time” (currently 10 minutes for Bitcoin).

Proof of Burn (PoB):

In this consensus protocol, miners have to show that they’ve “burned” coins. Something that is expensive to them, but not physically materially wasteful.

In one implementation, we can generate an address that is the “burn” address. The burn address, is one that nobody has the keys for. This would mean, if you send coins there, nobody can ever spend them. They are theoretically eliminated from the ecosystem (AKA “Burned”).

We do have to wait a certain amount of time so that miners aren’t incentivized to re-org the chain. (Why we wait will be explained in part 2).

The math here can be done in many ways, one possible way:

h = Hash( previous hash + all_transactions_of_block + nonce )

if ( h <2²⁵⁶ * f(burned_amount) / difficulty ) then mine block

otherwise try again

If

f(burned_coins) = 1

Then we are at PoW, if:

f(burned_coins) = 1+burned_coins

Then we are at PoW for all those that haven’t burned and those that did get a boost.

Here, once you have burned a coin, you can only use that proof (that you’ve burned your coins) a limited number of times.

To achieve this, we make the proof valid for:

• “x” number of blocks (how many times you can use the proof)
• from “n” blocks ago (how long you have to wait until you can start using it)

f(burned_coins) = 1+(# of coins burned { n, n-1, n-2, …. n-(x-1)} blocks ago for this address)

Eww, that math was ugly, lets look at some practical examples:

if x = 1 and n = 5.

f(burned_coins) = 1 +(# of coins burned 5 blocks ago for this address)

If x = 2 and n = 5

f(burned_coins) = 1 +(# of coins burned 5 or 6 blocks ago for this address)

If x = 3 and n = 5

f(burned_coins) = 1 +(# of coins burned 5 or 6 or 7 blocks ago for this address)

If you burn 1 coin, it is twice as easy for, if you burn 2 coins it will be 1/3 as easy, if you burn k coins, it will be 1/(k+1) easier for you than those who haven’t burned.

After proving the miner proves that they’ve burned coins, the miner is rewarded with the opportunity to mine coins more easily in the future.

Proof Of Stake (PoS):

There are many ways to do proof of stake, a good main case is:

h = Hash( previous hash + address + timestamp )

if ( h < 2²⁵⁶ * address_balance / difficulty ) then mine block

otherwise wait for next second

Here, there is no nonce, so you can only try once per timestamp (only one hash done per second per node). Second the more coins you have, the easier the puzzle will be. This is because we have address_balance (the amount of coins the miner has) multiplied on the right hand side so that our hash has a higher likelihood of being under the target (2²⁵⁶ * address_balance / difficulty). Hence the stake in proof of stake.

Proof of Stake Velocity (PoSV) or Proof of Activity (PoA):

Proof of activity is an extension of PoS with the caveat that it encourages users to spend their coins (or hold instead of spend, which we’ll discuss later) instead of holding them staked.

Remember in PoS we had:

h < 2²⁵⁶ * address_balance / difficulty

Now, we do something a bit different:

h < 2²⁵⁶ * f(coins_in_address) / difficulty

Where f is a function that will increase the newer your coins are. So if you mine with recently acquired coins, they will be less valuable to a mining than coin held for a long time. Once a coin is spent then the counter restarts.

One way to value the “age” of a coin:

Age( Coin ) = coin / number_of_blocks_since_it_arrived

To compute f(coins_in_address), you sum the age of all coins in that address.

Assume the below miners using our example definition of “Age”

1. Miner_A is mining (staking) with 1 coin from 2 block ago,
2. Miner_B is mining (staking) with 1 coin from 1 block ago

In the next block:

Age(Miner_A) = 1 / 2 = .5

Age(Miner_B) = 1 / 1 = 1

This means that Miner_B has twice the likelihood of mining the next block than Miner_A, since Miner_B’s coin’s age is twice Miner_A’s.

As you can imagine, how you do define: Age( Coin ), will matter a lot to the economic dynamics of the system.

You could do the opposite:

Age( Coin ) = coin * number_of_blocks_since_it_arrived

By multiplying instead of adding, the longer you hold, the older your coins become.

Using our previous example

Age(Miner_A) = 1 * 2 = 2

Age(Miner_B) = 1 * 1 = 1

This means that Miner_A has twice the likelihood of mining the next block than Miner_B, since Miner_A’s coin’s age is twice Miner_B’s.

This will incentive people to never move their coins.

Proof Of Storage/Capacity (PoC) :

Prerequisites: Merkle Trees, Merkle Proofs, Modular Arithmetic, Endurance :)

How do you prove to someone that you’re actually holding a file?

Choose file F that is very large.

Compute the merkle tree of F by dividing F into k buckets.

NB = Size( Buckets ) = Size(F) / k

The resulting merkle tree leaves are from each bucket and everyone agrees on the merkle root: MR_F

If we want to prove that the user is actually storing the file. What we can do is randomly pick leaves and ask the user to provide the merkle proof for each of those random leaves. As a validator, we only need to store MR_F (the root of the merkle tree).

Now lets get back to using PoC in mining:

A miner stores a portion of the File F, say F_m.

F_m is generated from:

F_m is a list of data buckets. For each index of the list, here is the formula to compute that data bucket that will correspond to that index.

F_m[i] = F[ Hash( public_key + i ) mod (Number of Buckets) ]

Where i is iterated until they run out of room; Iterated ML (Miner Limit) times.

We have to add the mod NB so that the hash corresponds to a portion of the file.

Lets give an example:

• NB = 5
• F = “abcde”
• The buckets are: [ “a”,”b”,”c”,”d”,”e”]
• I have room to store 2 buckets (Miner Limit = ML =2)

I will store:

• F_m = [ F_m[1], F_m[2] ]
• F_m[1] = F[ Hash( public_key + 1 ) mod 5 ]
• F_m[2] = F[ Hash( public_key + 2 ) mod 5 ]

If NB is large compared to ML for all miners, then we can create a simple mining puzzle.

We generate a set of buckets equal to some minimum size, say MB (for minimum_buckets):

F_MB[i] = F[ Hash( previous_hash+ timestamp + i) mod NB ]

The winners are all the people who are storing F_MB completely. Meaning, since F_m (the part of the file you are storing) > F_MB (the part generated), if the part you are storing contains the entire part generated, you have mined a block.

To show that you have stored F_MB, you must send back (F_MB[i],merkle proof) for all indices. This proves you have stored the generated portion.

If nobody has gotten it in that timestamp, we try again at the next timestamp.

The difficulty adjustment is the minimum amount of storage needed for a proof.

A few challenges to consider:

1. What happens if two people are winners?
2. How big do we make NB?
3. How big do we make F?
4. How do we choose F?
5. What about latency of sending F_MB ?

This is the most basic form of PoC. We will dive into a more complicated version in Part 2.

This marks the end of part 1. In the next post, we review how different mining parameters might effect the network. We will evaluate possible attack vectors and vulnerabilities.