Summary:
The current Equihash is used by many different coins without any personalization. It was originally developed by Zcash and uses the parameter set <200,9>. We are going to upgrade to Equihash with a different parameter set, <144,5>, with some customization. We’ll call it “Equihash-BTG," for now. This will keep our blockchain ASIC-resistant and add a great measure of safety from 51% attacks, for now.
About Equihash
Equihash, which was first developed and used by Zcash, was designed from the beginning to be an “ASIC-resistant” Proof of Work algorithm. An important paper by Biryukov and Khovratovich makes this clear:
In this paper we solve this open problem and show how to construct an asymmetric proof-of-work (PoW) based on a computationally hard problem, which requires a lot of memory to generate a proof (called “memory-hardness” feature) but is instant to verify. Our primary proposal Equihash is a PoW based on the generalized birthday problem and enhanced Wagner’s algorithm for it.
From: Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem
The idea was to achieve this by making the algorithm “memory-hard.” What does this mean, and why does it matter?
A memory-hard algorithm is one which requires a lot of memory to be able to run. It simply won’t work on hardware that doesn’t have enough memory.
When making an ASIC - an Application-Specific Integrated Circuit - adding memory is very expensive, and the more memory you need, the more expensive it gets. With a high enough memory requirement, building a “single-chip solver” on an ASIC becomes so expensive that it’s impossible to profit.
Equihash is designed to be just such an algorithm - it requires a lot of memory as a minimum requirement to run, and it needs several times that memory to run efficiently. (If you use half the ideal amount of memory, it’s 1000 times slower.)
Exactly how much memory is required? It depends on a couple of parameters.
The current Equihash: <200,9>
Equihash is the name for the general algorithm, and the exact implementation depends on two parameters, < n, k >. The common Equihash coins run on Equihash <200,9>, so n = 200 and k = 9… this setup is currently used interchangeably by Bitcoin Gold, Zcash, Zencash, and many other Equihash-based coins.
This Equihash requires a minimum of 50 MB of memory but can run much faster with 144 MB of memory. These memory requirements were previously sufficient to prevent building an ASIC, based on the comparison of ASIC cost to coin value a year or two ago. Since then, Zcash - which was worth $30 in Feb of 2017 - has grown to be worth over $250, and now there are multiple coins that can be mined with the same Equihash. Meanwhile, the cost of transistors in an ASIC has gone down.
Equihash <200,9> required too expensive an ASIC to mine $30 coins in the past… but times have changed and an ASIC has arrived.
But this doesn’t mean that Equihash is defeated - just that Equihash <200,9>.
Equihash-BTG: <144,5>
We’ll be adopting the new parameters, <144,5> for Equihash-BTG. Although these numbers are smaller than <200,9>, it means the algorithm actually requires dramatically more memory to run - so much more that we believe ASICs will be impossibly unprofitable for quite some time. The <144,5> parameters require a minimum of 700 MB to run and use about 2.5 GB to run efficiently (that’s 17 times larger!) This should be too expensive to produce with an ASIC right now, while most graphics cards that miners use already have that much memory or more.
In fact, the amount of memory required for Equihash-BTG pretty much forces the use of DRAM, which calls for a dramatically different design than a single-chip solver for regular Equihash. Even if a specialty miner is developed for the Equihash-BTG, it will not have as dramatic an advantage over a GPU as the specialty Equihash <200,9> miners. This significantly decreases the threat ASICs can pose to our network. This resolves our security problem in the short term, and gives us time to consider other alternatives for the longer term, if necessary.
The new <144,5> parameters in Equihash-BTG provide a few other advantages over (200, 9):
- Smaller solution size (100 B vs 1344 B)
- (saves a little space)
- Faster validation (32 vs 512 rounds)
- (allows full nodes to confirm a solution is valid more quickly)
While we know that this parameter change is not a permanent fix - this one change won’t stop ASICs forever - we know it will solve our problem for now. We’ve already seen the innards of the Z9 Equihash miner, and we know that it doesn’t have enough memory to be effective with Equihash-BTG, so we’re no longer concerned that the Z9 might be capable of competing with our Community of GPU miners. The design is not memory-upgradeable with conventional DRAM sticks of memory - and even if someone made an ASIC with DRAM, it will likely be severely limited by the speed of communication with the memory, not the processing power - which put it in the same “class” of hardware as a GPU.
Equihash-BTG, with the <144,5> parameters, will dramatically minimize the possible performance gap between GPU and ASICs, and it makes it unlikely we’ll see a single-chip solver any time soon without some sort of semiconductor breakthrough that might make it a profitable target for specialty hardware.
References: