Why X16R (Random) is ASIC-resistant

background

The evolution history of hash algorithms used in cryptocurrencies is roughly: from Bitcoin's SHA256, to Litecoin's Scrypt, then Ethereum's Ethash, Dash's X11, and later X13, X15, and X17.

X16R is the next generation algorithm in this evolution.

The purpose of changing the algorithm is to reduce the impact of dedicated hardware on the mining ecosystem.

Bitcoin was originally designed to be mined by ordinary computers around the world.

As the value of Bitcoin increases, hardware designed for parallel processing begins to show advantages.

Thus, mining entered the GPU era.

As the economic benefits of mining improve further, it becomes economically feasible to use programmable hardware, such as field-programmable gate arrays (FPGAs), which have advantages over CPUs and GPUs.

The next step is to manufacture chips specifically designed for mining.

Application-specific integrated circuits (ASICs) have become so dominant in mining that mining equipment using other technologies will become impractical.

Eventually, as equipment continued to upgrade, mining entered the era of faster and more energy-efficient ASICs.

Unfortunately, this shift brought with it the problem of mining centralization.

While anyone can order these ASIC devices, those who are geographically closer to the manufacturer can enjoy the benefits of shorter logistics times. Electricity is a significant part of the cost of mining, and having access to cheap electricity is very important.

China has a large number of ASIC miner manufacturers and has access to cheap electricity in certain provinces, which will inevitably lead to mining being concentrated here.

confrontation

One solution to reduce the impact of ASIC miners is to use a memory-intensive hashing algorithm. Litecoin's Scrypt and ZCash's Equihash use this approach. Although some miners use ASIC miners to calculate Scrypt, this advantage is not great compared to the advantage of ASIC over GPU under the SHA256 algorithm. There are no ASIC miners for Equihash yet.

Another method is to connect multiple hash algorithms in series, and the output of one hash algorithm will be used as the input of the next hash algorithm. Dash (originally known as DarkCoin) adopted this idea and designed the X11 algorithm. X11 connects 11 hash algorithms in series to increase the difficulty of ASIC development.

This method once prevented the emergence of ASIC, but now there are many manufacturers producing mining machines for the X11 algorithm.

Similar to X11, some other currencies use X13, X15, and even X17, which combines 17 hash algorithms in series.

It is still possible to design an ASIC by chaining hash algorithms in a fixed order. Chaining more hash algorithms in series can increase the difficulty of developing an ASIC. Like X11, X13, X15, and X17 all use a fixed hash algorithm chaining order, but only change the number and type of hash algorithms.

It is likely that such algorithms will be broken faster and faster, and ASIC manufacturers will only need to implement each hashing algorithm one by one and combine them as needed.

Dawn

The X16R algorithm solves this problem by constantly disrupting the order in which hash algorithms are connected.

X16R uses 15 proven hash algorithms in X15, plus SHA512. However, the order of the 16 hash algorithms in series changes dynamically based on the hash value of the previous block.

This dynamic order change does not make it impossible to design an ASIC. However, it requires the ASIC to do more adaptation for the additional inputs. These operations can be easily done by CPUs and GPUs. The dynamic order change also prevents ASIC manufacturers from producing X16R miners by simply expanding X11 and X15 miners.

The concatenation order of the 16 hash algorithms of X16R is determined by the last 8 bytes (16 bits in hexadecimal) of the hash value of the previous block.

The hashing algorithms involved are as follows:

• 0=blake

• 1 = BMW

• 2=groestl

• 3=jh

• 4=keccak

• 5=skein

• 6=luffa

• 7=cubehash

• 8=shavite

• 9=simd

• A=echo

• B=hamsi

• C=fugue

• D=shabal

• E=whirlpool

• F=sha512

For example:

The hash value of the previous block is:

0000000000000000007e8a29f052ac2870045ae3970270f9 7da00919b8e86287

The last 8 bytes are: 0x7da00919b8e86287

Each hexadecimal digit determines a hash algorithm. The hash algorithm order of the next block X16R is:

1. cubehash(7)

2. shabal(d)

3. echo(a)

4. blake(0)

5. blake(0)

6. simd(9)

7. BMW(1)

8. simd(9)

9. hamsi(b)

10. shavite(8)

11. whirlpool(e)

12. shavite(8)

13. luffa(6)

14. groestl(2)

15. shavite(8)

16. cubehash(7)

Some hash algorithms take longer to compute than others, as shown in the table above.

Differences in computation time will be averaged out through random matching of algorithms when mining blocks.

Implications

The test platform for the X16R algorithm is Ravencoin, which was launched on January 3, 2018, the ninth anniversary of the release of Bitcoin. Ravencoin is the reference implementation of X16R, defining the number, type, and order of hash algorithms, as well as the bytes used in the previous block to determine the order of hash algorithms.

Based on Bitcoin, Ravencoin modified the issuance rules, block time and PoW algorithm.

The idea of ​​X16R can be expanded to include Scrypt, Equihash and other ASIC-resistant algorithms to ensure that anyone can use an existing idle computer to mine. For each cryptocurrency, the order, type, and number of hashing algorithms can be easily changed to prevent ASIC manufacturers from designing mining machines that can mine a class of cryptocurrencies like the X11 algorithm.

think

Why can X16R's dynamic change of hash algorithm order resist ASIC?

We mentioned earlier that X11's approach of piling up the number of algorithms was eventually conquered by ASIC, because as long as the price of the currency is high enough, manufacturers will invest manpower and material resources to implement the 11 hash algorithms one by one using ASIC, and then combine them together.

During operation, each hash algorithm module can run in a pipeline, and at every moment, 100% chip utilization can be achieved, as shown below.

For X11 with 11 hash algorithms, ASIC can provide circuits for 11 hash functions. At all times, these 11 hash function circuits are working and processing different parts of the 11 tasks at the same time.

X16R adds many challenges when performing PoW calculations on each block:

• Each hash algorithm is called an undetermined number of times

• Hash functions have undefined ordering

For pre-designed ASIC mining machines, once the chip is taped out, the number of hash functions it contains and the amount of computing resources for each hash function are determined.

For X16R, since the last 8 bytes of the hash value of the previous block can be considered completely random, we can calculate the number and probability of hash function types involved for each block as follows:

 Type of hash function involved Probability 1 8.673617379884035e-19
2 4.263126310299903e-13
3 1.3008292880367645e-09
4 4.0680219586149147e-07
5 3.114800294252984e-05
6 0.0008548354163772504
7 0.010257933523243057
8 0.060249156768226245
9 0.1847133772998888
10 0.30522511853905976
11 0.273508450268678
12 0.13029987021900835
13 0.03130843802212624
14 0.0034140224047796153
15 0.00013610720550616406
16 1.1342267125513672e-06

Under weighted average, each block operation involves an average of 10.3 hash functions. Assuming that the hardware implementation of each hash function requires the same chip area, the chip utilization is about 64.4%, which is the upper limit of the average utilization. In other words, at any time, about 36% of the circuits on the chip will be wasted.

At the same time, since each hash function is used an uncertain number of times and in an uncertain order in the calculation, it is even more difficult to design an efficient pipeline.

If you want to increase the parallelism of the pipeline, you need more redundant computing units, which will result in lower chip utilization.

If you want to improve chip utilization, it will inevitably intensify resource contention, reduce parallelism, and affect performance.

All this just increases the difficulty. When the price of the currency is high enough, ASIC can still gain certain advantages.

However, as long as this advantage is not too huge compared to GPU, it will still help to alleviate the trend of computing power centralization.

Integrated circuits are actually composed of transistors to form a number of gate circuits, which realize various functions through combination.

Has anyone ever thought that if there is a device that can dynamically combine these gate circuits to achieve various functions as needed, wouldn’t it be possible to fully utilize the entire chip at all times?

FPGA is one such device.

Although X16R can resist ASIC, it is almost powerless against FPGA. Every time the previous block is generated, the type of hash function used in the next block, the number of times each hash function is called, and the order of hash function calls are determined.

FPGA can be quickly reprogrammed to allocate the number of gates to be used for each hash function, so that the chip resources can be fully utilized for calculations.

References:

X16R ASIC Resistant by Design ravencoin.org