Lecture 8 - Alternative consensus

Puzzle solutions are probabilistic proof of work. A typical puzzle utilization function can be modeled as P(challenge, randomness - nonce, difficulty, …) -> true/false

P(c, r, d) for Bitcoin is SHA256^2(c, r, d) <= 2^256-d

There are many objections to this. It wastes resources on a meaningless computation, it is highly parallelizable and has returns of scale, randomness, long wait time between blocks, and leads to the creation of the mining pools. It is possible to redesign the system to make mining pools impossible but that would lead to only big players doing the mining. The centralized signing also eliminates all these issues and “private blockchain” is just a misnomer for a centralized blockchain.

Improvements (Cosigning)

1. Cosigning in Ripple - consensus k out of n
2. Cosigning in Stellar - arbitrary topology of who has to sign before something is trusted

Improvements (Block throughput)

BTC: one block every 10 mins Testnet: one block every 5 mins If block production rate is increased then there will be more forks leading to stale blocks. Current stale block rate is 1%. If the stale block rate increases, the cost of 51% attack goes down drastically. For example, if the stale block rate is 50% then the network efficiency is halved, so, a 51% attack only requires 33% of the network power to execute. Ethereum avoids this issue by using GHOST which not only includes the parent blocks but the uncle blocks as well. This allows Ethereum to have a block throughput of one block every 15 seconds.

Improvements ( Bitcoin-NG)

Between two majors blocks A and B signed by Ka and Kb, we can have micro blocks. 40% mining fee of each micro block will go to Ka and 60% to Kb. Due to some attack(???), Ka can only receive < 42% mining fee.

Features of SHA-256

1. Anonymous
2. Progress-free - Probability of success is linearly proportional to time and mining power invested. Note that SAH256-squared is not progress-free.
3. Fast to verify
4. Supports precise difficulty adjustments
5. Compact specification

Improvements (ASIC-Resistance)

The eventual goal is to minimize advantage a custom ASIC has over a PC. There are a few possible approaches.

1. Complex algorithms or advanced CPU instruction set - For example, X11 took 11 SHA-3 finalists and applies them in succession.
2. Memory Hardness - ASICs cannot have too much memory. For example, Litecoin uses scrypt which references previously calculated values and requires a 16KB buffer. The worst part is that the verification is as slow as computation. Also, Litecoin ASIC mining advantage over Litecoin PC mining is higher than Bitcoin. An important problem is to come up with an algorithm which is memory-hard to compute but memory-easy to verify. Cuckoo hash works but is apparently broken.
3. Moving target - Change the hash functions every few months. The question then remains is that who picks the new hash functions.

Do we want ASIC resistance

1. ASIC miners, due to their investment, are most loyal to the crypto they are mining.
2. ASIC resistant cryptocurrency can be attacked via botnets or rented resources on the cloud.

Improvements (Proof of Storage)

Store something useful like the library of Congress. (ashishb’s note: Filecoin came out later)

Improvements (Useful Proof of work)

Rather than do the SHA256 calculation, perform useful work like SETI@Home or Folding@Home. Not all solutions are equally likely though. An example is PrimeCoin, where the proof of work is to calculate Cunnigham chain, p1, p2, … pk, such that, pi = 2 * p(i-1) + 1. The goal is to find a chain whose length is determined by the difficulty level. p1 is composed of a value from the previous block and a nonce.

Improvements (Proof of stake)

Based on the stake one can vote on the blockchain. This can lead to oligopoly. Peercoin implements the proof of stake. H(c, r) <= 2^(256 - d - s) where s is the coin stake which consists of the sum of the coins with each coin holding being weighted by the time it was last use. So, a crypto puzzle is easier for someone who is sitting on the coins for a while.

Improvements (Proof of Deposit)

Choose a time to such that the fund movement is not allowed for the ti time frame, and then you are allowed to mine.

Nothing at stake problem

All vanilla proof of stake consensus suffers from nothing at stake problem. In case of proof of work, you can only mine on one chain at a time. In case of proof of stake, since no resources are involved, one can build on as many chains in parallel as possible. Slasher mechanisms have been designed to punish anyone caught doing this.

Improvements (Round-robin signing)

NXT coin uses this approach where a signer is elected every key block and can sign a set of blocks between the two key blocks. All signers have to be online and the new signer is the owner of the coin r such that r = H(H(b1) || H(b2) || H(b3) …). Chance of being a miner is proportional to how much you own. If you skip a signer, you lose money (???)

Improvements (Casper)

Casper is Ethereum’s planned proof of stake. There will be node validators who will put tickets on the fork. One fork will win and everyone else will lose money.