⚼Modified X16R algorithm proposal for constant hash rate in short time
Interpretation Lens V. a0.01
As we all know, instead of using memory intensive hashing algorithm, like Scrypt, Equihash and Ethash, to minimize the impact of ASIC miner, X16R employs another strategy: randomly reordering a sequential [list of] hashing algorithms based on the last 8 bytes in the previous block hash value.
This reordering doesn’t make an ASIC impossible to build, but it does require that the ASIC adapts to additional input, which is more easily accomplished by a CPU or GPU. the reordering also prevents a simple extension of the current X11 ASICs or future X15 ASICs
— the X16R white paper.
Since X16R does not rely on memory intensive hashing algorithms it is easy for miners to mine coins employing idle compute power. In addition, the reordering of the algorithms can easily be modified with each coin in mind so as to keep purpose-built hardware [ASIC] manufacturer from easily entering the ecosystem, which in turn keeps miners engaged and hashing power distributed.
As a successful anti-ASIC PoW algorithm, X16R is employed by many coins. However, we still found a small issue inherent to it; the GPU may not be able to reach its full potential when mining coins under this algorithm. We found the hash rate fluctuates within short timespans so we spent a bit of time looking for the reason behind it.
In the X16R white paper, we found a interesting chart which shows the relative running time per sub hashing algorithms. Apparently each of the 16 sub hashing algorithms have different running time. A different combination of these sub hashing algorithms is used for each block based on previous block hash value. It appears that each such combination ends up executing in different amounts of time due to this feature and that is why the hash rate fluctuates.
To test this hypothesis we collected data on over 8000 RVN blocks which employs X16R as its POW algorithm. Based on this data we sought to compare the relative running time between consecutive blocks.
Since the combination of sub hashing algorithms is fixed during the mining of a block, the running time for a single nonce is enough for our analysis. Based on the collected hash info and relative running time listed in the white paper we plotted the running time variation Versus ejected blocks (FIG2).
It appears that running time variation is seen as blocks ejected one-on-one. In fact for GPU-run mining software a range of nonce values are assigned to it.
We can obtain the hash rate metric for the block if we simply multiply a factor (equivalent to the nonce range) with its nonce’s running time and divide by 1.
Mathematically it is easy to conclude that the GPU hash rate has similar variations.
Using this data we plotted a histogram (FIG3) in order to find more detailed info on this phenomenon. It reflects the distribution of the running time and resembles a normal density function whose mean is about 3.45*10⁴ cycles, which happens to be the mean value of the running time for a single nonce.
It is easy to find more than 250 blocks having such running time per nonce but there’s also a non-negligible amount of blocks with running time close to 2.2*10⁴, or 4.2*2¹⁰ (cycles), the worst being that the running time of the latter is twice as long as the former’s. It seems the variance of the running time is too high for these block’s data. In fact such an ‘upside-down-bowl’ shaped density function has such properties: the wider the bowl, the bigger the variance of the distribution.
The side effects of the large fluctuation of the hash rate are:
a) The entire network’s hashing rate fluctuates in short timespan due to its delay in adapting to the difficulty thus making the block mining time vary on a per block basis. Furthermore, Proof of Work inherently introduces randomness into block running time therefore coins using X16R algorithm further increase such hash rate fluctuation which in turn impacts the confirmation of the average transaction confirmation time.
b) For miners who use [desktop] computers to mine coins employing X16R this hash rate fluctuation means not all power is participating in the mining activity which is a strong incentive for them to transit into platforms whose algorithms can more fully explore their hash rate, maximizing profit.
b.2) This is even more the case for those using GPU farms for mining — as they don’t have enough power supply margin.
Decreasing the distribution of the ‘upside-down-bowl’ becomes an intuitive requirement since it would be equivalent to keeping the hash rate constant which is the desire in this scenario.
The X16R algorithm is largely accepted as well-performant; as such, any changes to it should be kept as tiny as possible even when attempting to improve it. We attempted to find a solution which mitigates the hash rate fluctuation.
Our strategy consists of increasing the number of combinations of sub hashing algorithms in each block instead of assigning a fixed one. With a highly increased number of random combinations per block the running times of the sub hashing algorithms are averaged, in turn, the hash rate fluctuation is mitigated during block ordering.
In detail, to get a different combination for each nonce we add a keccak_256 calculation for each nonce value: the last 8 bytes of the previously calculated hash result are used for determining the combination of those 16 sub hashing algorithms.
It is easy to see, most of the original X16R is kept and only the source of the random order is changed. What’s more, the more the nonces are tried for block mining, more constancy of the hash rate is perceived during one block’s time.
In order to visualize what we proposed, assume 1000 nonces have been tried for block mining. FIG4 shows the average hash rate for each nonce. The hash rate becomes almost steady and the ‘upside-down-bowl’ shape is narrowed in comparison to the previous one, which also represents variance decrease.
Additionally, this new proposal keeps ASIC mining platforms from further penetrating this ecosystem.
The contents of this post are a derivative, iterated atop someone else’s research, data, pictures and text. We waiver all our rights over it but you remain limited by the original work’s license, while we cannot provide legal counsel, we highly recommend you go directly to the original source before publishing or otherwise commercializing derivatives from this work.
ORIGINAL SOURCE: Modified X16R algorithm proposal|r/Ravencoin on Reddit | https://www.reddit.com/r/Ravencoin/comments/bhyrxv/modified_x16r_algorithm_proposal_for_constant/ | 27th of April, 2019, 19:00 |
- X16R algorithm explained | r/NiceHash on Reddit | 27th of April, 2019, 23:07
- X16R ASIC Resistant by Design white paper | Ravencoin | 27th of April, 2019, 23:11
- Application-specific integrated circuit | Wikipedia The Free Encyclopedia | 27th of April, 2019, 23:20
- Nonce Definition | unblock.net |27th of April, 2019, 23:40
- Variance | Wikipedia The Free Encyclopedia | 27th of April, 2019, 23:50
If you know little of cryptocurrencies but would like to learn, we highly recommend the unblock.net blog, their UX is one of the best ever known to humankind and they have easy browsing of terms and their definitions — very propaedeutic!
⚛ SystemsNexus is Ivan Flecha et al.
We bridge people and explain the world.
Celebrating my 200m views with the tallest building in San Francisco covered by fog
— Denys Nevozhai