I. PoW’s dilemma
Satoshi Nakamoto invented Bitcoin in 2008 in the purpose of creating a decentralized financial system that everybody can get involved in freely. However, since the appearance of ASIC, calculation power are accumulated in the hands of minority, and is putting the decentralization in jeopardy. Following bitcoin, many first generation cryptos adopted PoW algorithm, and one of the fight they can not avoid is ASIC. However, most of the solutions simply increase the difficulties of the algorithms for the design of ASIC , or reduce the ROI of ASIC and GPU to make it less attractive. Nevertheless, these solutions never fundamentally realize ASIC resistance. Moreover, with the rising price of Bitcoins, ASIC manufactures could easily find a way to defeat these algorithms driven by economic interests.
Victims of ASIC:
** April 4th, 2018, after XMR voting for hardfork, Antminer X can not work
The victims above only listed several famous coins, whereas there are plenty of coins monopolized by ASIC. Projects with PoW are constantly defeated by ASIC manufactures. Facing the challenge, projects seeks solutions in other two ways:
1. Led by Casper, EOS, ADA and NEO, many coins replaced PoW protocol with PoS or DPoS.
2. Coins like XMR decided to hard fork every 6 moths, and wishing to change Algorithm through this way.
The former totally abandoned PoW while the latter did destroy a bulk of ASIC every time it hard forked, nevertheless, these miners could easily fork many counterfeit coins by themselves.
So is the final fate of PoW a failure to ASIC? Obviously not, but PoW needs to solve a lot of problems of its own before its rebirth. Here, we’d like to focus on the breakthroughs in Mining algorithm and come up with a set of basic algorithm that can fundamentally resist ASIC.
II. The previous and present life ASIC
PoW algorithm was put forward by Cynthia Dwork and Moni Naor in 1993. The application scenario of it then is to resist the attack of ddos and email spam. In 1999, Jacobsson came up with partial hash inversion algorithm which is also the method that Satoshi Nakamoto utilized in bitcoin network.
In 2008, Satoshi Nakamoto created Bitcoin network aiming to create a decentralized financial mechanism that everyone could participate freely. One of the biggest challenges then is to build decentralized ledger among different nodes who have no trust between each other beforehand.
The basic algorithm of Bitcoin is as follows:
Bitcoin circulate a variate “nonce” to calculate hash value with no break. When hash is lesser than the preset degree of difficulty, the mining process is a success. One of the features of this algorithm is the simpleness of the inner mining loop, it only needs repetition, therefore this algorithm can achieve to be highly parallel hence produces an opportunity for the ASIC to get in. Because of the high cost of ASIC, it’s not cost effective when the price of the coins is low. However, up till 2013, with the rapid growth of Bitcoin’s price, more people are willing to pay more for hash power, and here comes the ASIC era.
III. How to achieve ASIC resistant fundamentally
Take a look at the coins that issued after the bitcion, it is not hard to see that blockchain developers are experimenting different kinds of mining algorithm to achieve ASIC resistant. And it turns out to be that all the attempts are failed. their whole idea is to adding the computation against the shortcomings of ASIC to make the algorithms harder. For example, the original algorithm of Ethash caught on ASIC’s shortcomings of Insufficient memory, they added a “reading big table” session. For this problems, Bitmain’s Antminer E mining machinery adds a circle of DDR3 Micron produced by ESMT company （Elite Semiconductor Memory Technology）, through this it can prevent the calculation of reading big tables in the Ethash algorithm.
Ethash and Equihash or others may delay the appearance time of ASIC at best but cannot fundamentally resist ASIC. For further research, we must understand why CPU/GPU is way much slower than ASIC. And the main reason is that von Neumann architecture adopted for Diversity calculation.
Von Neumann architecture is roughly divided into three parts, that is internal storage, control unit and calculating element. The operation program and data are written in DDR and will be transferred to the calculation element when performing calculations. The computational bottleneck caused by transmission bandwidth is called the von neumann bottleneck.
To avoid the von neumann bottleneck is simple for the operation of single algorithm, the idea is to write the algorithm directly into the calculation element to bypass von neumann bottleneck. That is why ASIC has such an astonishing advantages of computing powers in Bitcoin Sha-256d.
In order to achieve ASIC resistant fundamentally, we can borrow the experience from Monero, that is periodic algorithm changing design. The problems with Monero is the unprofessional voting for hard fork by the community. And the biggest problem with them is that no one knows if the project team (they can manipulate the voting results easily) prepared ASIC for new algorithm.
1. Command S as a collection of algorithm, all algorithms in S must pass through the von neumann bottleneck.
2. Algorithm will change every T blocks, and the changing methods must meet up with the condition of Verifiable and unpredictable.
3. No human intervention in algorithm switching.
The implementation of Truehash is to set G as a group, for every group member g, make rho_V(G) be the showcase of G in vector space V. In ordinary mining algorithm, when calculate blockheade, nonce and other information with operations like padding and so on, there will form a Vector nonce. By the exhaustion of different nonce to find the results that are less than the difficulty coefficient. Truehash’s change is in part to change the hash(v(nonce)) to hash(rho(g)*v(nonce)). As long as G is complex enough (Truehash USES the permutation group S_2048, which has 2048! ) The algorithm set cannot all be written into the cell. Because the algorithm will switch randomly, the bottleneck of von neumann will be inevitable.
The switching principle of Truehash algorithm is to change the group elements every 12 thousand PoW block, the production time of 12 thousand blocks is 83 days. The information of new group elements is consisted of the first to 8192th blocks of the previous period. And the composing pattern is to analyze the 11001th — 11256th blocks’s hash value. Because of the unpredictability of the hash, no one can be aware of any information related to the new algorithm. From the 11257th block of last period until it goes invalid, there’s an 88 days interval, and it makes no sense to produce a ASIC in such a short time.
Command v = v(blockheader, prevhash, nonce) as the binary vector of n’s length, generally speaking, V includes blockheader, hash and other informations of the front block and nonce information of each loop.
Command d as the preset coefficient of difficulty, the difficulty is higher as d goes bigger.
- Ordinary PoW algorithms execute pseudo-code
for nonce = 1:2^n
h = hash(v(nonce))
if h < [2^n / d]
2. pseudo-code executed by ASIC resistant algorithm
for nonce = 1:2^n
h = hash(rho(g)*(v(nonce)))
if h < [2^n / d]
· Of which g∈G，rho(g) is a signify of G on Z_2^n. To achieving fundamentally ASIC resistant, the following features must be included:
1. von neumann bottleneck must be inevitable when calculate all g∈G’s
2. Every fixed block of rho(g) must automatically switch to rho(g‘)
3. The relation between g and g’ must meet the Verifiable but unpredictable conditions.