ASIC-Resistance, as its name suggests, is designed to resist ASIC, so that the advantages of the hardware itself are not so obvious. In this way, the high-performance miners will become useless, thus bringing a more fair and efficient mining environment to the entire worker community. Now, the algorithmic iteration on ASIC-Resistance will be discussed in this article.

 

Forward

In terms of blockchain, one of popular topics should be mining. In our previous chapters, we have discussed the basic principles of mining. From the level of software, it just means repeated hash calculation till the value is within the specified range.

But one issue may be easily overlooked, any calculations are only supported by the hardware. The one with higher performance will have faster calculation capability, and of course more “coins” will be mined. Such a hardware foundation is just the miner.

Therefore, the miner development is one of the important factors affecting the current blockchain industry. From the original CPU to the GPU, and now to the ASIC miner, every iteration has realized a qualitative leap in mining speed. Why should people devote time and energy on the miner development? Because mining itself is closely related to economic interests. Many companies, such as Bitmain and Innosilicon, have made great efforts in miner development.

At first glance, it’s the good news for the mining workers, but on the other hand, it has brought many negative effects to the entire industry:

• The process of mining is a hash rivalry, so the emergence of the high-performance miner has certainly raised the threshold of mining. Take the Bitcoin as an example, it’s almost impossible to mine any coins with a conventional PC. On the other hand, the high-performance miners are so expensive that it’s eventually become a game for a small group of people. As a matter of fact, it is true. Most hash has been controlled by a few mining farms and most bitcoins are only held by a few mining workers. Although bitcoin was originally designed to be decentralized, however, it eventually became “centralized.”
• The iteration of miners has improved the computing capability as well as the difficulty of mining. So, a lot of hardware resources and electricity have been wasted in the mining itself. Except for providing POW, mining itself is meaningless and it makes no contribution to the entire blockchain ecology. So, it ends up with the waste of resources.

To solve the aforesaid problems, some ASIC-Resistance hash algorithms have appeared in the current blockchain technology.

In fact, ASIC stands for Application-specific integrated circuit. In miner applications, it’s a customized computer designed for hash calculation. ASIC-Resistance, as its name suggests, is designed to resist ASIC, so that the advantages of the hardware itself are not so obvious. In this way, the high-performance miners will become useless, thus bringing a more fair and efficient mining environment to the entire worker community. Now, the algorithmic iteration on ASIC-Resistance will be discussed in this article.

First of all, we should know how the ASIC came into being? Why is the ASIC faster than the CPU of our computers? We must start from the working principle of the computer hardware first.

 

Triode Gate Circuit

It’s the figure of triode, which includes three poles B, C and E.

Generally, E is grounded and C is connected to voltage. The function of B is equivalent to a switch. If it’s electrified, the connection between C and E plays the equivalent role as a wire to flow the current directly. Without being electrified, C and E will naturally be disconnected. So, if we regard the C segment as the output, it is equivalent to inverting the input signal. That’s how NOT gate is created.

Such a simple component should not be underestimated. Countless such components are combined to form an integrated circuit, the so-called chip, which can realize various complicated functions. For example:

If A is electrified while B is not, then the Out will not be electrified because of the disconnection. Similarly, if B is electrified while A is not, it’s the same result. Only when both A and B are electrified simultaneously the Out signal will be generated. If we set the power-on as 1 and the power-off as 0, then the truth table will be listed as follows:

A	B	OUT
1	1	1
1	0	1
0	1	0
0	0	1

We will find: Out = A & B. This is the AND gate, which can realize the “AND” operation.

Since we have “AND gate”, there should be “OR gate” of course, which is shown as follows:

The “OR gate” means that so long as any input of A or B is regarded as 1, the output will be equal to 1. That is, if Out = A | B, the “OR” operation will be implemented.

So long as there are AND gate, OR gate and NOT gate, we can realize all the calculation functions by any combination. For example:

Based on the features of the three gates, we can get the truth table as follows:

A	B	OUT
1	0	1
0	1	1
0	0	0
1	1	0

We can find that Out = A + B. So, this is a simple adder and it’s easy to realize the carry function by connecting A and B to an AND gate, so that its output can be used as a carry. Since the addition is realized, will the subtraction be far behind? So, all the operations in mathematics, from the basic four arithmetic operations to the bit shift operation, to the more complex index and the root extraction can be achieved through the combination of these three kinds of gate circuits.

Apart from calculations, the gate circuits can also be combined into storage elements as follows:

Wherein, Out’ is the inversion of Out. We can see that when R and S are 0, the Out output can be fed back to “NOR 2” as the inversion of the input of Out’, so the state of Out’ can be maintained continuously. Similarly, since the Out’ is the input to Out, so the state of Out can also be maintained.

 

From CPU to ASIC

After the introduction of gate circuit, let’s focus on the CPU.

From a microscopic point of view, the CPU is also built up by a large number of such gate circuits, which is called VLSI (Very Large Scale Integration). However, the function it can implement is not just as simple as being used as a calculator. Since it needs to support complex operating system, apart from computation, it will build memory to record various instructions equipped with a translator to translate these instructions into a sequence of 0 and 1 which the machine can understand. Moreover, it will also play the role of a brain to communicate with various hardware in the computer such as GPU, sound card, memory, etc. as well as the data bus. As a result, its structure will be so complicated that it must consume a lot of gate circuits. For instance, Intel’s latest i7 processor owns as many as 1.4 billion triodes, and the function responsible for mathematical calculation actually only takes a small part.

The following is a simple CPU layout. The big block in the lower left corner is the memory which usually takes a lot of space!

Now suppose we only need to calculate one function? Then, the solution will be very easy. We only need to build a set of gate circuits based on the specific function algorithm to start calculation. For the rest space, we can copy this circuit for thousands of times to get thousands of cores. All these cores can support parallel calculation and, of course, the speed will also be increased by many times. That’s the original intention of the ASIC design.

The bitcoin mining is the process of changing the value of Nonce repeatedly until the output of its hash function is within the specified range.

For example, I started from 1 and added 1 every time till reached 10,000 so that the output met the requirements. Now, since the CPU has only a single core, it should be treated only one by one. If the ASIC has 10,000 cores, the entire workload can be divided into 10,000 parts and each core just calculates one number, so it’s 10,000 times faster compared with the single-core CPU. It’s like the house decoration. We can do it singlehandedly or hire a professional team. Of course, the efficiency of the latter will be much higher.

We have introduced the bitcoin hash algorithm called SHA256. The core of this algorithm is to split the whole input into 512-bit data blocks, and then perform the following operations for each one:

• Initial values of A to H are: the fractional part of the square root of 8 prime numbers in 2-19 (take the first 32 digits).
• W is the 64 fields extended from the data blocks: w[0…63]
• Ch(E,F,G) = (E & F) + (E’ & G), where E’ is the inverse of E
• Ma(A,B,C) = (A & B) + (A & C) + (B & C)
• Σ1(A) = (A >>> 2) + (A >>> 13) + (A >>> 22) , where “>>>” is the loop right shift operation
• Σ0(E) = (E >>> 6) + (E >>> 11) + (E >>> 25)

Once the loop ends, connect the A to H listed blow to get the final hash.

We can see what is involved in the whole operation process is the basic logic operation, so it can be realized by a combination of AND gate, OR gate and NOT gate. Moreover, the hash input of bitcoin is at most 80 bytes, so the size of the cache is negligible, which provides a good hotbed for customized ASIC miners.

Now, we have a problem. How can we improve the current hash algorithm if we want to prevent the ASIC miner?

Don’t forget what I have mentioned before, the memory will take a lot space. If each computer consumes a lot of memory for each calculation, then the memory of each core will need extra-large expansion to ensure enough storage space. Well, the entire PCB, of course, cannot bear so many cores and the hashrate is bound to reduce. For example, if the memory consumed by each calculation is expanded by 50 times, the size of the miners will be expanded by 500,000 times to maintain the current hash of 10,000 cores!

That’s obviously incredible. The single-core CPU itself has enough memory, so in the long run, the ASIC will naturally have no obvious advantages. Based on such a concept, the Scrypt algorithm came into being.

 

Scrypt Algorithm

In order to understand the Scrypt algorithm, we must first know about Rainbow Table Attack. In fact, it also exposes another weakness of the hash function.

Although the hash function such as SHA256 has no inverse function, the mapping relationship always exists so long as it is a function. For example, if you have many 6-digit passwords. Through the hash function (H), these passwords can be mapped to a set of hash values. In theory, we can store all these one-to-one relationships. Whenever a new hash value comes in, we can restore the corresponding password by looking up its corresponding pairing. However, the object you want to decrypt may not be as simple as a 6-digit password. Perhaps it’s a more complicated string. So, it is unrealistic to store all possibilities in a large table.

So smart hackers try to reduce the hash value to a fixed-length string by introducing a custom function (R), and then use the hash function (H) to change it into a new hash value. By repeating such operations, a hash chain of R, H, R, H….. will be formed. For such a hash chain, we only need to record the head and tail, which is shown as follows:

But if we just want to use a single R, the probability of a hash collision will be very high, which means that for different starting values, it may be brought together to an end point. To overcome such a problem and reduce the probability of collision, a variety of different Rs are generally used: R1, R2…Rk. That’s the rainbow table. Through the rainbow table attack, we can crack the input of hash function.

As the saying goes, there will always be flexible approach based on specific circumstances. The best way to crack the rainbow table attack is to mix a random string (Salt) in the input. For example:

Wherein, Password is the password to be encrypted, and Uc is the final hash value output.

As we can see, the generation of each U must be based on the value of the previous U. So long as there’s one mistake, the final output will be inconsistent. Salt will play a decisive role here. For hackers, the rainbow table needs to consider not only different passwords but also combinations with different Salts. According to different lengths of Salt, the complexity of the rainbow table is growing exponentially. For example, the length of Salt is 20, which means to expand more than 4 million times on the original basis! Obviously, the rainbow table is not feasible here.

The Scrypt algorithm also adopts one Salt, but the Salt is so huge that its size will reach almost 4000 bytes! Therefore, in the calculation process, at least 4,000 bytes of cache must be reserved to store such a Salt, which is almost 50 times larger than the 80 bytes of the original bitcoin hash function input! According to the previous analysis, the memory capacity must be expanded for ASIC while sacrificing the number of cores for parallel calculations. Therefore, this algorithm ultimately reduces the advantages of ASIC compared to ordinary computers.

Now, the Scrypt algorithm is adopted in Litecoin to provide POW during the mining process.

In addition to increasing memory consumption by implanting a huge Salt, we can also adopt another way to weaken the computation advantages of ASIC. That’s what will be discussed below, the Hashimoto algorithm.

 

Hashimoto Algorithm

Imagine if we can greatly weaken the role of computation in the hash algorithm, then the advantages of ASIC will no longer exist. Most of the hash algorithms always focus on how to hash, such as various shift operations, addition, subtraction, multiplication and division, so that the ASIC will have a chance for itself. However, what if the hash calculation only takes up a small percentage of the entire algorithm running time? In fact, Hashimoto just aims to occupy the largest percentage of algorithm running time with many I/O reads. The implementation of hashimoto in Python is shown as follows:

As we can see, the place where the hash is used is within just the second line. This algorithm is the selection of 64 transactions in the blocks through hash. Finally, by means of the shift addition, the ids of these transactions are added together to get the result. In fact, a lot of time has been spent on reading the transaction content of the blockchain (line 7), because we have to send a read request to the entire blockchain to get information about a transaction. To increase the reading speed, we must download the entire chain to the hard drive for convenient reading. That will be terabyte data!

People may wonder why ASIC can’t put the entire chain in a hard disc? Yes, we can put it on the hard disc just as the traditional computer can do. The advantage of ASIC is to speed up the calculation through a set of customized circuits. However, in terms of hard disc reading, it has no advantages at all. Just like the traditional computers, hard disc I/O reading and writing are limited. So, as for the hard disc, the performance of the ASIC is just as weak as that of the traditional CPU.

Now, the Hashimoto algorithm is also used in Ethereum 1.0.

 

Summary

Two hash algorithms are introduced here in the article. Some people may wonder if the ASIC miners will face the doomsday.

No, as an old saying goes: “While the priest climbs a foot, the devil climbs ten”. Software can restrict the hardware in a certain sense, but it cannot stop its development. Incredibly, the development of software and hardware is a contradiction in the blockchain. Both are constantly improving their upper limits in the process of mutual competition.