Our "New" Equihash: Equihash-BTG


#1

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:


A Brief Update on the Pending Upgrade
Network Upgrade at block height (536200), approximately July 1st, 2018
#2

Bonus Content: The Complexities

Why does an <n,k> like <144,5> require more memory than <200,9>?

The Equihash algorithm does, as part of the process, two major functions:

First, it makes a huge amount of data by creating a huge number of strings with a hash (Blake2b), and then Second, it uses that data with an algorithm (Wagner’s) which requires all of that data to be around.

So, how many strings? It’s found with the formula:

image

So, for <200,9>, that’s 2 ^ ( (200 / (9+1) ) + 1), or 2 to the 21st power, or 2,097,152.strings.

But for <144,5>, that’s 2 ^ ( (144 / (5+1) ) + 1), or 2 to the 25th power, or 33,554,432 strings.

This is sixteen times more. This means more required memory just to make the algorithm possible. And with either set of parameters, finding solutions efficiently requires several times that amount of memory - remember, using half as much memory causes a 1000 X penalty in performance.)

What else changes?

That’s not the only thing that changes with these simple parameters:

image

Each of these is, from our perspective, an improvement.

Writing an efficient miner to use these new parameters turns out to be a lot of work - the optimized code for <144,5> is very different than the setup for <200,9>, which means the writers of mining software have a tough job, but they’re already hard at work. Their new mining software may be less efficient at first, and improve over time - but that’s OK, it’s still fair when everyone has access to the software and can run it on their GPUs.

Miner Revenue

Some people are concerned that the new <144,5> parameters will produce fewer hashes per second - a lower hashrate - and that this will mean less revenue for miners. Not true! Sure, the hashrate will be lower, but all miners will be producing at the same lower rate when mining BTG, so it’s still a fair distribution based on power contribution. The net revenue for mining will stay the same - 12.5 BTG per block - and it will still be distributed among roughly the same number of miners after the mining market re-balances. In the end, the profitability will be roughly the same as before the fork.

If miners are slow to come over to the new software necessary to mine BTG, then the few who come over first will simply earn much higher revenue. If only half the current miners come over, they’ll be earning twice as much! That won’t last long, as more miners will come over to take part. In the end, we expect to have about the same number of miners after the upgrade as we did before. Since the reward is staying the same - 12.5 coins per block - any change in overall mining revenue will be a result of changes in the price of BTG, something which is decided on the open market.


Action items to prevent future attacks
#3

Thank you. Great article. How will we know which miners support the new equihash-btg ?

Dave


#4

We’ll be releasing an open-source mining implementation which supports Equihash-BTG; the providers of 3rd-party mining software should make it fairly obvious if they’re updating their software to support BTG or releasing a new version specific to BTG.

It turns out to be non-trivial to optimize a miner for <144,5> even if you’ve already optimized a miner for <200,9> - the requirements are quite different, and certain techniques are unavailable.

There may be somewhat limited options for miners right at the time of the fork, but we’re confident that more miners will become available soon afterwards, even if they’re not in time for the first block on the new algorithm.


#5

I have just one question. Will the 3GB video card be able to mine efficiently BTG? You said 2.5GB is enough, but there is some video RAM reserved by the OS (esp. WIndows 10). Similar situation happened recently with ETH, when the DAG file reached 2.5GB, the cards stopped.


#6

the entire plan sounds amazing to me. My cards shall be put to work. :sunny:


#7

if something like this happens i will gladly move my miners to Linux based os like ETH os for example or u can still use some old version of windows or if u need to use your miner as a work PC or for game plays there is always a option to go for dual boot


#8

Thank you. Where do we watch for this release? The blog? Keen to get going on the new implementation the second it’s ready :smiley: I have my 6 NVIDIA GTX 1070 cards ready to go! :smiley:

Dave


#9

@davecoates, details will probably be visible on Github first, but perhaps here on the Forum, depending on when PRs and etc. hit.

As soon as things are published on the Forum, we’ll surely be tweeting. Formal Blog Post and a related email blast will follow soon after.

Since we’re providing at least 7 days between publication and the update (perhaps more, depending on how partners respond), you’ll have plenty of time to fire up your miners on testnet to be sure they’re ready to roll.

In the days before and after the fork block where we switch algos, you’ll need to keep your eyes tuned to all the places where your favorite miner devs report about their software… there may be a bit of an “efficiency race” as they work to improve their tuning for <144,5>. It’s not easy. In fact, <144,5> was the original preference for Zcash:

Additionally, it happened that even the sufficiently low-memory parameters n=144, k=5 resulted in the solver taking too long to complete (about 50 seconds with the inefficient algorithm and code available at the time) given the target block interval (2.5 minutes). This prompted Zcash to switch to the current n=200, k=9 parameters, which reduced the (inefficient) zcashd’s solver’s run time by about a factor of 1.5 (to about 35 seconds), and at the time this happened to make all the difference for the mining on testnet to start working correctly. The memory requirements of zcashd’s solver have stayed roughly the same with this change

from Solar Designer, in An analysis of Zcash’s use of the Equihash proof-of-work scheme. (see link in OP.)

I expect some decent competition in the closed-source miner developer market, so the “best miner” title may change a few times in the near future.


#10

Well, no mention of btcz BitcoinZ that made this? or developed this and has it’s own miner and implementation? and forking on June 15th? hummmmm.


#11

don’t you mean zhash?


#12

All of the references cited in my Opening Post date from 2016, long before the BTG project or the BTCZ project existed.

Yes, BTCZ intends to fork on June 15th (and this fork is an upgrade that will not result in a new coin); we’re well aware of this because we’re actively interacting with the BTCZ team, as well as other coin teams in the Equihash space.

Attempts to sow division here are going to fail.

In fact, I’ve been privately encouraging miner developers to try to hit the June 15th target. I have privately stressed that although it may be difficult to meet the June 15th date for BTCZ, it’s well worth trying, and even if they miss that date, BTG will be using the same parameters very soon after, so it’s a great investment of development time. We’re doing our best to encourage development by everyone in the space, for everyone in the space.

Bear in mind that most people who mine, long-term, will probably not use the reference implementation provided by BTG or by BTCZ - we’re all working to encourage the ecosystem of 3rd-party developers.

No, Zhash uses a different internal personalization than Equihash-BTG, although both of our implementations use the <144,5> parameter set for the Equihash algorithm. The personalization is intentional to make it more difficult for attackers to redirect hashpower maliciously; this will be especially important for coins with smaller hashrates.


#13

Hi! Please help to set up the miner! I can’t find the right program! And my pool (supernova) has not yet added settings!


#14

Supernova was ready for the Upgrade. They list several mining programs and the correct settings here:
https://btg.suprnova.cc/index.php?page=gettingstarted

I suggest going to Discord or Telegram for real-time help with problems.


#15

Thank you! guys (supernova) a long time working, settings still had through the official website to download the program!