Wednesday, April 12, 2017

MyriadCoin : The Untold Story of the Invincible Blockchain

One of my favorite security mechanisms built into a cryptocurrency is the concept of the Multi-Algorithm PoW.  This means separate, floating difficulties that automatically adjust to ensure that miners on all algorithms get paid out equally.

The first coin I ever saw do this was RuCoin, released back in 2011, which worked with sha256 and scrypt.  I first heard about it in 2013 at the Bitcoin conference in San Jose.  ASIC miners for Bitcoin were finally starting to ship, and there was quite a bit of discussion around whether or not Bitcoin should switch up its Proof of Work algorithm, and exactly how it should do that.  As a huge proponent of trust agility, this idea that a cryptocoin could have two PoW algorithms with independently floating difficulties really blew my mind.  To extend on that, I really liked the idea of pluggable PoW algorithms that could be added and removed from a blockchain as needed, and could be reincentivized on a schedule.

Enter the Myriad

For some reason, RuCoin never released source, and eventually RuCoin died, but in early 2014, the hero of our story arrived, and it was called MyriadCoin.


Myriad was really interesting to me because it didn't just have two PoW algorithms, it had *five*, all floating independently.  To understand why this is a massive security advancement, you first need to understand how 51% attacks are executed.

How to perform an effective 51% attack:

ASIC Coin: One of the key threat actors in this scenario is a nation state able to manufacture custom ASICs to attack a network.  Algorithms that are ASIC friendly are, by design, extremely cheap to implement in hardware.  This also means that the security of the network is 100% dependent on the production lines of ASIC manufacturers who may or may not be open to the public about their product.

GPU Coin: These coins have algorithms that are a bit more expensive to implement in hardware.  The cheapest way for an attacker to attack a GPU Coin would likely be to spin up the required number of GPUs in Amazon's EC2 environment for just long enough to perform a double spend.

CPU Coin:  These coins bring crypto currencies back to their roots, as the most efficient way to mine these coins is on a CPU.  Usually this means that they require significant amounts of memory, or memory bandwidth, that isn't generally available on GPUs.  Unfortunately, what this means is that an attacker with a large botnet would not have a lot of trouble dominating the network for short periods of time, since they often can control 10s of millions of CPUs at any given time.

How MyriadCoin defends against 51% attacks:

Here's where the magic happens.  MyriadCoin has five different proof of work algorithms that all adjust difficulty dynamically.  Two of them ASIC algorithms, two of them GPU algorithms, and one of them a CPU algorithm.

sha256/scrypt: First up, sha256 and scrypt, our favorite PoW algorithms from Bitcoin and Litecoin.  MyriadCoin can also be merge mined with Bitcoin and Litecoin, so you can use your ASICs to mine Bitcoin and Litecoin, and also get some extra MYR on the side for free.

groestl/skein: Groestl and Skein were actually both SHA3 finalists, and the SHA-3 competition required that the algorithms could be cheaply implemented in hardware.  This means that they could be mined with FPGAs, or even ASICs some day, but they are currently being mined with GPUs.

yescrypt: I take some personal pride in this one.  YesCrypt is a CPU centric hashing algorithm created by SolarDesigner, infosec legend and creator of the John The Ripper password cracking toolset.  It was created for the Password Hashing Competition and was a finalist.  It was heavily inspired by scrypt, with a lot of extra defenses against TMTO attacks.  When MyriadCoin launched, an algorithm called Qubit was sitting in this spot, but I pushed for yescrypt pretty heavily on IRC and Reddit for a long time, and it finally got included.

The important part of this is that for any feasible 51% attack, an attacker would need to pin down at least three of the five algorithms, and very few attackers are capable of such feats.  Nation states who might be able to attack ASIC algorithms, and corporations who might be able to attack GPU algorithms, typically don't have the ability to operate large botnets, and those with the ability to operate large botnets generally don't have the physical presence required to operate large GPU or ASIC mines.  Furthermore, for any attack of extended duration, any algorithms that are getting pinned down would be deprioritized during the regular difficulty adjustments, so even pinning down three algorithms would not work for long.

The Tragedy of Vertcoin

A interesting case study in this area is that of Vertcoin.  It has had not one, but two major PoW changes in its history.  The first to run from ASIC mining, and the second to curb the threat of botnet takeovers.  Vertcoin was marketed, from the beginning, as the GPU forever coin.  It launched with a modified version of the scrypt algorithm that used an N-value of 11 rather than the N-value of 10, used by Litecoin, Doge, etc.  They also had the ability to easily bump to higher N values as needed for some extra memory requirements to presumably avoid the impending ASIC apocalypse that Litecoin and family were facing.

Unfortunately, in a move that no one expected, when KnC released their Titan ASIC miner for Litecoin, they included with it hardware support for a TMTO attack (mentioned earlier when discussing yescrypt) that effectively made the Titan miner work on Scrypt coins of any N value, notably targeting Vertcoin.

At that point, Vertcoin had no choice but to fork, and switch to a Password Hashing Competition finalist, Lyra2.  This worked well, but this wasn't the end of their problems.  Lyra2 was designed to be run on CPUs, so it became so popular on Botnets that they needed to fork once again in 2015 after it became clear that a single botnet was controlling more than 50% of the mining power.

Lessons for Bitcoin

With all this AsicBoost drama, and renewed talk of PoW switching, I still think that if this ever were to happen on the Bitcoin blockchain, there would need to be a gradual transition.  Maybe at first 99% of the mining rewards would still go to the SHA256 miners, and 1% would go to MAGICHASH, the magical perfect PoW algorithm that everyone wants to switch to.  The cut received by MAGICHASH could be gradually increased, and after a year it could be 50/50 rewards, and after two years, SHA256 could be phased out completely.  Of course, if the Bitcoin community can't even agree how to scale block size, it's hard to imagine that they'll be modifying their PoW algorithm any time soon.