minerva

Fundamentally achieving ASIC resistant: A brief introduction to Truehash algorithm

As we all know, TrueChain adopted hybrid consensus technology, It uses PBFT as fast chain to process transactions and PoW as snailchain to supervise and elect the committee.

PoW algorithm was put forward by Cynthia Dwork and Moni Naor in 1993. The application scenario of it then was 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.

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. However, algorithm like Ethash and Equihash or others may merely 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 is 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.

The idea of avoiding the von neumann bottleneck is simple for operations with high uniqueness, such as the calculation of hash values, the idea is to abandon the von neumann architecture and write the algorithm directly into the calculation element to make it become ASIC. That is why ASIC has such an astonishing advantages of computing powers in calculating Bitcoin Sha-256d. Even then Ethash adopted the method of reading the big table, but essentially a computer program can still be hard -coded to calculation elements. Although there's memory grain around the ASIC but that can only increases the cost.

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.

Therefore,we must assure this mechanism is under the control of mining algorithm. And to achieve ASIC resistant fundamentally, the following rules must be satisfied:

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 specific design ideas are as follows

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.

The changing parts of Truehash

Change hash(v(nonce)) to hash(rho(g)*v(nonce)). As long as G (Truehash utilizes permutation group which contains 2048 elements) is complex enough, this algorithm collection will not be entirely hard-coded within the calculation elements. Because the algorithm will switch randomly, the bottleneck of von neumann will be inevitable.

The principle of Truehash's switching algorithm is that the group elements will be changed every 12 thousand PoW block. The production time of 12 thousand poW blocks is 83 days. The new group element information is composed of blocks 1-8192 in the previous cycle, and the composition method is generated by analyzing the hash values of blocks 11001-11256.

Because the hash value of the block is unpredictable in advance, it's impossible for anyone to know anything about the new algorithm until the 11256 block comes along. From the 11,257th block of the last cycle, to the algorithm being invalidated, there is only 88 days in total, so it makes no sense to produce ASIC in such a short period of time.