Inside Grin's approach to resisting ASICs

Leo Zhang

By Leo Zhang

"...in which I show that hardware is soft, a transient expression of ideas, and those ideas are more durable than the hardware itself. And in which I trace the layered paradigms that make possible digital machines made with billions of transistors."

--Edward Ashford Lee, Plato and the Nerd

The explosion of cryptocurrency ASIC miners have made ASIC-resistance one of the most widely-debated topics of this year. Project teams who argue against ASICs have taken various approaches towards resisting them; one common approach is to implement memory-hard hashing algorithm, pushing the cost of manufacturing specialized mining machines higher and reducing their efficiency over off-the-shelf equipment.

In modern computer architecture, CPU and memory communicate through a data bus. In the recent decades the speed of CPU and size of memory have improved much faster than the throughput between them, leading to a phenomenon known as Von Neumann bottleneck. Hashing algorithms such as Ethereum's Ethash, Zcash's Equihash, and Grin's Cuckoo Cycle all to some extent take advantage of this characteristic in design.

Integrating on-chip memory on ASIC is expensive. Around 2014 when ASIC miners were first commercialized, the tactic of using memory-hard algorithms to resist ASICs made sense due to the higher cost of RAM. In the past few years, the sharp decline of RAM cost makes it possible for ASIC designers to manufacture machines for these networks at increasingly low cost. Memory-hard algorithms cannot keep ASICs at bay indefinitely.

Grin's Cuckoo Cycle takes a slightly different approach than previous memory-hard algorithms. It essentially tries to find certain subgraphs in large, pseudo-random graphs; or, in the author John Tromp's own words:

Imagine two countries, each with a billion cities, and imagine picking a billion border crossing roads that connect a random city in one country to a random city in the other country (the PoW actually uses a cheaply computed hash function to map the nonce, road number, and country to a city). We are asked if there is cycle of 42 roads visiting 42 different cities. If someone hands you a nonce and 42 road numbers, it is indeed easy to verify, requiring negligible time and memory.

When the concept was first published in 2015, it was considered "ASIC-resistant" because designing an ASIC miner requires well over 1 GB of SRAM, which is rather expensive when used as embedded. Recently, as the Grin project captures more attention, the community found out there are ASICs under development even before the project is launched yet, because the cost of old requirement for memory is no longer a hurdle. In an effort to include GPU miners on the network, the dev team proposed modifying the hashing algorithm to make it much more memory-hard.

Proof of work update
(Grin)

Screenshot-from-2018-08-27-19-23-20

Equihash is currently used by Zcash, Horizen (ZenCash), Bitcoin Gold and a few others. The algorithm is based on generalized birthday problem. The combination of two cryptographically significant parameters N and K, will determine how long it requires to find a solution as well as how large the solution is. For instance, ZEC, ZEN, and ZCL are based on Equihash (N=200,K=9), which mean the minimal requirement is around 140MB (watch a review of Z9 mini here). After suffering the 51% attack in May, Bitcoin Gold switched to Equihash (N=144,K=5), which would require 2.5GB. The combination (N=108,K=3) proposed for Equigrin requires roughly 7GB, making it the most memory-hard algorithm on the market right now.

z9organs

(Source: Z9 Chip Teardown, Bitcoin Gold forum, by MentalNomad)

Technical Updates

Gravity
(LaurenMT)

"Based on this observation and two important properties of Bitcoin’s PoW (its global and cumulative effects) we’ve formalized the utility of PoW with a very simple mathematical formula defining the total number of bitcoin.days secured by the system.

At last, we have derived two metrics which both suggest that contrary to a widespread opinion, Bitcoin’s PoW is actually becoming more and more efficient."

How much does it cost to run DApp in 2018
(Hackernoon, by Igor Yalovoy)

"Let’s see how much they would spend in one year. 90'000 transactions would cost you ~90 ETH/~$27'000 with an average cost of transaction ~0.001 ETH/$0.03. Again that might be more or less depending on which gas price used. If you have time-critical dApp like an exchange, gas price probably will be high. If you have dApp for which it is okay to have transactions to commit for a few hours then you can save a lot of transactions fees."

Ravencoin - Dark Gravity Wave
(Tron Black)

"The difficulty algorithm change will take place on block 338778 on mainnet. We’ve tested this switch from Bitcoin’s 2016 look-back to a 180 block DGW look-back on testnet4. Version 2.04 is available for download."

GlobalFoundries stops all 7nm development: opts to focus on specialized processes
(AnandTech, by Anton Shilov and Ian Cutress)

"Along with the cancellation of the 7LP, GlobalFoundries essentially canned all pathfinding and research operations for 5 nm and 3 nm nodes. The company will continue to work with the IBM Research Alliance (in Albany, NY) until the end of this year, but GlobalFoundries is not sure it makes sense to invest in R&D for ‘bleeding edge’ nodes given that it does not plan to use them any time soon."

News & Commentary

It's getting harder to pump up prices in cryptocurrency markets
(Bloomberg, by Matthew Leising)

"Tether has created $515 million of new tokens this month, according to blockchain data. All of those new Tethers were sent to Bitfinex, the data show. That’s backed up by the Chainalysis report. 'After issuance, all Tether passes through the Bitfinex trading platform, Tether’s only direct client,' Chainalysis said. From Bitfinex, about 80 percent of the Tether is then moved to six other exchanges: Bittrex, Poloniex, Huboi, OKEx, Binance and Kraken."

Looking back at a list of crypto-analysts' price predictions for 2018