This lectures describes what ASIC resistant puzzles are since this is a widely researched topic in puzzles. I also completely diverted from the lecture notes by bringing up a topic I’ve been following closely which is ProgPOW in Ethereum. This is a proposal for introducing another (potential) ASIC resistant puzzle for Ethereum.
Questions answered in this Post:
- What and why do ASIC resistant puzzles matter?
- Memory Hard Problems
- Memory Hard Problems: Scrypt
- Memory Hard Problems: Cuckoo Hash Cycles
- ProgPOW: Ethereum discussion
Why care about ASIC resistant puzzles?
A bit of a backstory, Bitcoin used to be mined by individuals. Home computers that weren’t fancy could be miners and win the block rewards. Nowadays, that’s pretty much impossible. Companies running giant mining rigs running specialized hardware dominate the network now. ASIC stands for Application-Specific Integrated Circuit and describes the specialized hardware now used to mine Bitcoin and some other cryptocurrencies. Because of this shift, people have proposed alternatives to democratize mining. Is there a way to allow the average consumer the ability to participate once again in mining? ASIC resistant boils down to if allowing specialized hardware to have an intrinsic advantage when participating (mining) for a network.
Based on the above description, it’s clear that one goal of ASIC resistant puzzles is to lower the barrier to entry. This allows potentially any idle hardware could be used to contribute to supporting a blockchain network.
Another goal, in a similar strain, is reducing the monopoly by big manufacturing firms. The creators of the mining hardware have an unfair advantage. If they’ve created the new hardware and then mine Bitcoin with it for a few months, buyers are essentially getting a second-hand piece of hardware. Given that the difficulty level changes over time, it’s thought that when newer hardware is first used, it performs better and then overtimes the reward decreases. The lecturer uses the term “burn-in” advantage to describe the “use before sell” approach. Thus the new approach would be to reduce difference between future hardware and existing custom ASICs which would allow for longevity with the hardware and reduce this “burn-in” advantage.
Tangent on Mining Ecosystem: Work by Siacoin
Ok, not sure if you’re like me, but when I hear Siacoin my first thought was not cryptocurrency. However, they’ve written and done compelling work looking at the ASIC industry. Siacoin is building online network for distributed storage. They created ASICs for their own Sia mining somewhat related to Bitmain’s ASIC release and documented their journey. “The vast majority of ASIC-resistant algorithms were designed by software engineers making assumptions about the limitations of custom hardware. ” This quote alone makes me skeptical whenever people claim that something is ASIC resistant. Further down, I mentioned about ProgPOW for Ethereum and feel comforted that they are seeking a 3rd party audit. The article touches about Monero secret mining which again targets a real world example that this lecture discussed.
Memory Hard Problems
Memory hard problems is a type of puzzle that is ASIC resistant. It uses the idea known since the 80s that cost and performance in memory is more stable than for processors. As time has progressed processing has increased exponentially while memory and storage have increased at a slower rate. Thus if you pick a puzzle based on processing than it’s more likely to change significantly and older versions will have worse performance than a puzzle that was memory or storage intensive. He brings up Moore’s Law briefly when mentioning the exponential improvement.
Scrypt – Colin Percival
One potential memory hard hash function is called Scrypt by Colin Percival (2009). Scrypt is similar to the Bitcoin puzzle but instead of using SHA2, it replaces the function with the scrypt algorithm. It has a trade-off with constant time/memory. It can be computed with a certain amount of fixed memory, any smaller, it will require more time. In addition, it has already been adopted by a known cryptocurrency, Litecoin. Scrypt is used in other application such as for password hashing. Thus the lecturer mentions another benefit to this approach is that if there were issues other people have eyes on this mechanism to look for vulnerabilities.
Scrypt Steps
- Fill memory with random values
- Read from the memory in random order
The lecturer then dives into a step-by-step example of how the algorithm works. The algorithm, per the lecturer, was memory hard because if you reduce memory by half, then the number of computational steps increase by 1.5x. One disadvantage is that it requires N steps and N memory to check. In addition, scrypt ASICs unfortunately already exist. There was an interesting thread posted on Bitcointalk which I’ve linked here. It points out that scrypt does use SHA256 but the algorithm happens to be memory intensive. Given that in 2013, the cryptocurrencies using this algorithm were low value and low liquidity, manufacturers were not incentivized to build FPGA and ASIC when GPUs already do much of the needed work. I’ve found newer academic articles proving that scrypt is maximally memory-hard. However, based on what I’ve read, cryptocurrencies may not have achieved the right parameters, specifically the actual memory size, to achieve ASIC resistance which some suggested was due to support GPU miners. Again, I’ve provided my sources, but admittedly I don’t understand the proofs well enough to make a well-substantiated argument.
Cuckoo Hash Cycles – John Tromp + More
Next, we look at Cuckoo hash cycles by John Tromp (2014). It has a clear improvement to Scrypt in that it’s cheap to verify where before verification would require the same amount of memory as solving. For a certain memory size, you still compute the hash function. However, instead of having to look through the entire memory space, you just need to check if there is a cycle of size K where K is less than N.
There are more complex functions that people are researching which Miller mentions. Specifically X11 which as indicated in the name uses 11 different hash functions. The other is called a moving target which builds on changing the puzzle periodically. As with most lectures, Miller also provides a counter argument on why perhaps the current algorithm is sufficient.
ProgPOW: Programmable Proof of Work for Ethereum
Per EIP-1057, “Proof-of-Work algorithm to replace Ethash that utilizes almost all parts of commodity GPUs”. Clear and concise. The goal as mentioned for ASIC Resistance is to allow commodity GPUs to be used for Proof of Work mining. Having a custom ASIC would not be beneficial. The primarily discussion that I’ve read about has little to do with the new algorithm or when it will be implemented. Most conversation has been around getting the algorithm audited. There seems to be consensus around whether people see it as useful.
Counter Argument: Maybe ASIC Resistant isn’t needed now
The argument simply is that Bitcoin mining ASICs aren’t changing very much anyway. Thus the first argument brought up with Moore’s law, is maybe not as needed. Processing is not increasing at that much of an exponential rate that necessitates the shift to memory intensive algorithms. The difference between the bigger and smaller ASICs is how many copies of the same SHA2 function the hardware holds.
Similar to where the lecturer mentioned that ASIC resistant wasn’t needed, the most recent BTC forks have also had a similar discussion.
https://news.bitcoin.com/cryptocurrency-projects-aiming-to-be-asic-resistant-have-little-success/
Tangent on Memory Hard Problems
Just a quick note, I wasn’t able to find many resources outside of those related to this course talking about memory hard problems that weren’t cryptography intensive. A. Biryukov from the University of Luxembourg has published two papers relating memory-hard and cryptocurrencies though. If you’re interested, I’ve left links to both papers, Fast and Tradeoff-Resilient Memory-Hard Functions for Cryptocurrencies and Password Hashing and Tradeoff Cryptoanalysis of Memory-Hard Functions
Wrap Up
ASIC resistance
- seeks to make it more appealing to mine with regular consumer devices than it is today
- response to centralization of Bitcoin mining