Anti ASIC/GPU/FPGA POW-algorithm. New (2019).

[flamehowk]

Anti ASIC/GPU/FPGA/CLOUD/MAINFRAME POW-algorithm
Now mining is available to everyone...

Hello to all.
For several years I was thinking about how to make a POW algorithm that will be stable not only against ASIC devices, but also against GPU miners.
And I developed it!
Last night I successfully conducted the generation and confirmation of the first local chain of signatures to confirm the block (see screenshot below). Therefore, from today on, I will publish a description of the algorithm and parts of the C++ code.



The main decision.

The only reason that does not allow the crypto community to solve the problem of specialized devices is the adaptability of modern POW algorithms to parallel calculations.
This is where the ideal solution comes from - the calculation algorithm must be consistent and resistant to any possibility of performing calculations in parallel.

The first principle is cyclic calculations.

We must abandon hashing, which is now the main calculation algorithm for block signing. I propose replacing it with the Ring Bit Function (RBF), because it perfectly fulfills all the requirements for the POW algorithm.

POW algorithm requirements:
1) one-way function;
2) hard to calculate;
3) easy to check;
4) only sequential calculations.

Let me give you an example of RBF for a 32-bit number.



You see that after 8 rounds of such calculations, we again get the initial number. Since the calculations go in a ring, we can use them for the POW algorithm. For example, from the 1st to the 7th round is a search for the result of calculations. The 7th is the signature found. And the 8th round is a test of accuracy of calculations!



Moreover, this function is one-sided, that is, the inverse transformation is possible only by brute force.
Thus, for this type of computation, which I called the "Ring Bit Function", all 4 requirements for the POW algorithm are fulfilled.



If we talk about ordinary hashing, then parallel computations are possible in it, which allows the use of special devices to speed up computations.


(Thanks to IadixDev for the diagram.)

The ring size in RBF may be different. It depends on the combination of rotations and shifts that we apply. Some combinations do not create ring functions, so you must first check which combination works.



I will give some working examples for 32-bit numbers:

239 rounds
NewNum = (num >> 1) ^ (num <<< 1)

55117 rounds
NewNum = (num >> 1) ^ (num <<< 1) ^ (num >>> 3)

131069 rounds
NewNum = (num >> 1) ^ (num <<< 1) ^ (num >>> 13)

There are a lot of such combinations, which allows us to vary the level of computational complexity.

The second principle is Olympic rings.

One ring function can give us only one signature. But in order to find a “beautiful” signature, we need to calculate many ring functions. The fourth principle of the POW algorithm requires that all ring functions be connected. Since the calculations in the ring function are one-sided, when searching for a “beautiful” signature we move along the ring in one direction, and during verification, in the other. If we begin to calculate a new ring from an old signature using the same algorithm, then we will move along the same ring. To create a new ring from the old signature, we must change the algorithm to another. In this case, the chain of calculations will be similar to the Olympic rings (only longer - it will consist of hundreds or thousands of rings). Changing the calculation algorithm on each ring will help us increase the stability of our algorithm against ASIC devices.



To further complicate the algorithm against ASIC and FPGA devices, we will use masks at each transition from one ring to another. This masking algorithm is two-way. I called him Mystique.



The third principle is two-step signature.

However, an attacker can still increase his chances of receiving a block reward, since he can do parallel calculations based on different Merkle roots, as well as different points in time.
In order to eliminate this possibility, when calculating the signature, it is necessary to use only the data that cannot be calculated in parallel. At the same time, they must constantly change from block to block. Such data includes only the signature of the previous block and the block number.
Additionally, you need to fix the right of the miner to receive the reward, therefore, I propose to add the miner's wallet to the signature of the previous block, to which the reward for the block will be credited. All other data can be changed for the same block, so they are not suitable for calculating the signature.
However, all other data should also be fixed in the signature of the block.
To solve this problem, I suggest creating a block signature in two stages:

Stage 1.
Based on the signature of the previous block, block number, and miner wallet address, hashing is performed (for example, SHA256).
The resulting hash serves as a start for the main calculation when searching for a "beautiful" signature.

2 stage.
The signature found is only a pre-signature.
The pre-signature serves as a starting number for hashing, which receives all other block data - Merkle root, chain counter, timestamp, etc. as input.
We consider the resulting hash to be the signature of the block.
Thus, the miner will not be able to calculate the hash of the block until it finds the correct pre-signature. But finding it already makes no sense to calculate different hashes from different input data.

The fourth principle is self programming.

The latter principle allows maximum protection of calculations from ASIC devices. It is based on the idea that each input number is simultaneously a program by which it will be converted. Thus, each new calculation will be performed according to a unique program, which will not allow the use of ASIC devices to speed up the calculations.
To do this, it is necessary to divide the starting number into groups of several bits, and attach a certain sequence of transformations to the value of each group. This will best be illustrated by the example of the powerful one-way hash algorithm Mystique, which I developed specifically to enhance hash operations when computing a block. It uses various number conversions, examples of which you can see in the picture below. This algorithm will be considered separately, as it is an additional solution.



The problem is resolved.

Done. The problem of protecting the POW algorithm from ASIC / GPU / FPGA and other special devices is resolved. For greater strength of the algorithm, 256 bit numbers will be used in it.

What has already been done.

At the moment, the entire POW algorithm is developed and tested. The main algorithm code is implemented locally in C++.



What to do with it?

You can implement this algorithm in any cryptocurrency and it will be the best POW algorithm you have ever known.

Ring Bit Function. 1 part.
https://www.youtube.com/watch?v=yg-G6itsHpU&feature=youtu.be
An explanation of the new POW algorithm, which I call the Ring Bit Function (RBF), with C ++ code examples.

Ring Bit Function. 2 part.
https://www.youtube.com/watch?v=Ir9Ptfg0Nbg&feature=youtu.be
In this part we make a chain of RBF rings.

Ring Bit Function. 3 part.
https://www.youtube.com/watch?v=9-7NmuZXbdU&feature=youtu.be
An explanation of the new POW algorithm, which I call the Ring Bit Function (RBF), with C ++ code examples. In this part we will masking our chain of RBF rings.

Entropy of numbers in my algorithm (RBF).
https://www.youtube.com/watch?v=F3D1mgMJvuw&feature=youtu.be

[flamehowk]

Maybe I posted in the wrong thread?

[gold969]

Maybe I posted in the wrong thread?

 
   Hello! If you will transfer to another place, please leave a new address here, I would like to watch your development.


 p.s.  perhaps you have links to any other addresses related to your project?

[olkah]

if there is no possibility of mining coins using GPU or ASIC or CPU then how will pow yours mine the coin ?

[olkah]

most on a piece of paper to do the calculations and thus will be on your algorithm is mining 

[flamehowk]

if there is no possibility of mining coins using GPU or ASIC or CPU then how will pow yours mine the coin ?

Why did you include CPUs in this list? I did not say anything about this. My algorithm is ONLY for the CPU.

p.s.  perhaps you have links to any other addresses related to your project?

Only on russian...

[olkah]

if there is no possibility of mining coins using GPU or ASIC or CPU then how will pow yours mine the coin ?

Why did you include CPUs in this list? I did not say anything about this. My algorithm is ONLY for the CPU.

p.s.  perhaps you have links to any other addresses related to your project?

Only on russian...

I myself am Russian but I do not have such links
and what is the algorithm say for litecoin and miner ?

[flamehowk]

I myself am Russian but I do not have such links
and what is the algorithm say for litecoin and miner ?

He вoпpoc - вoт pyccкaя вeткa:
https://bitcointalk.org/index.php?topic=5208035.0

and what is the algorithm say for litecoin and miner ?

Do you want to rewrite Litecoin using this algorithm? Nobody can stop you from doing this. It will block the use of GPU / ASIC / FPGA in the source code of any cryptocurrency.

[Keltrentt]

This looks nice and promising. But you may also wanna take this to the Altcoin Discussion section for more exposure and also for more feedback from people.

Go here

https://bitcointalk.org/index.php?board=67.0;sort=first_post;desc

[flamehowk]

This looks nice and promising. But you may also wanna take this to the Altcoin Discussion section for more exposure and also for more feedback from people.

Go here

https://bitcointalk.org/index.php?board=67.0;sort=first_post;desc

I get it. Thank you. Now I will make a duplicate of the topic in the thread that you indicated.

[IadixDev]

Ok so if i understand correctly the first part, the idea is to use cyclic algorithm like rings, who have a known cycle length before it comes back to the initial number, and the miner need to provide the result at N-1 of the final result, prooving he has computed all the other values in the cycle before, and those rings can be combined to make longer proof that are still easy To check because only the last Step has To be computed by validator , is this correct ? and it cannot be parallelized because its lot of small sequential steps that depends on the previous result.

The third part the idea is to solve long range attack ? Like there only a single determinstic "seed" for each block height, which is also why its pool resistant as you explained in the other thread , because there can be only one problem to solve at each block height , so a huge mining rate doesnt give a big advantage for long range attack , as the only solution for this block has already been found before ?

The problem i would see with this approach is it mean if all miners have equal mining power, it would mean they will all find the block at the same time if they all have the same amount of computation to do no ?

With the original btc solo mining, all nodes have different tx in the mempool and work on different blocks with non linear solving time, so there is more chance one find a block before the other and make it easier to settle on longest chain.

It would be harder to get to a longest chain if all mining work is perfectly equal between all miners no ? The non linear solving time with the hash function still make it easy to have winners of the longest chain even with equal hash power. And game theory incitate to stay on the longest chain.

With your algorithm it is linear amount of computation for all miners no ?

Maybe using the 4th part also on the address to select the ring algorithm and forcing address change on each block. Maybe it could get less linear solving time.

Is it still supposed to work with constant block target time with the difficulty adjusting to keep time between blocks constant ?

[flamehowk]

Ok so if i understand correctly the first part, the idea is to use cyclic algorithm like rings, who have a known cycle length before it comes back to the initial number, and the miner need to provide the result at N-1 of the final result, prooving he has computed all the other values in the cycle before, and those rings can be combined to make longer proof that are still easy To check because only the last Step has To be computed by validator , is this correct ? and it cannot be parallelized because its lot of small sequential steps that depends on the previous result.

yep

The third part the idea is to solve long range attack ? Like there only a single determinstic "seed" for each block height, which is also why its pool resistant as you explained in the other thread , because there can be only one problem to solve at each block height , so a huge mining rate doesnt give a big advantage for long range attack , as the only solution for this block has already been found before ?

The problem i would see with this approach is it mean if all miners have equal mining power, it would mean they will all find the block at the same time if they all have the same amount of computation to do no ?

I think there is a misunderstanding.
The third principle protects against parallel computing. This is his main task.
For example, if we do not use the third principle, each miner can generate 1000 different headers for the same block. This is possible because any rearrangement of transactions in places gives a different Merkle root. For 2 transactions, you can get 2 different Merkle roots. For 3 transactions already - 6 different Merkle roots, etc. The same goes for the time stamp. The miner can adjust the time when he began to mine the block. And this means that he can create many headings in advance from different seconds.
Thus, if a miner immediately makes a lot of block headers, he can start doing calculations from all headers at once. For example, there are 1000 of them. I take 1000 cores on the video card and each core counts 1 version of the header. Then I have 1000 chances against 1 that I will quickly find the right pre-hash.
To avoid this possibility of parallel calculations, the header should start only from the data that cannot be changed. And this is the height of the previous block, the hash of the previous block and the address of the miner's wallet. This data cannot be parallelized. This is the secret - why you can not mine on all the cores of the CPU or GPU. Only 1 core for 1 IP address, which is associated with 1 wallet address.

How this can help against long-range attacks, I do not quite understand. Long-range attacks are more characteristic of POS algorithms. However, if we assume a long-range attack option for the POW algorithm, then I think that “fixing the accumulation of network complexity” and a short distance of recalculating the complexity of the network would be a much better way to deal with them.
How it works...

Let's say that the attacker started with the genesis block and, after making a long calculation, forced the blockchain to increase complexity. Then he begins to make quick calculations and generates many blocks at high speed. Thus, after some time, the height of the block that the attacker will generate will be greater than that of the real blockchain. In this case, the nodes can go to a longer chain of the attacker.
What would be the best way to deal with this?
It will be good if the distance between the blocks until the next recalculation of complexity is short. But this does not save 100%.
But accumulating network complexity is a 100% solution.

It looks simple. In each block, we fix the complexity of the network at which it was calculated. In the next block, we add the old complexity of the network with the new one and fix the sum of complexity. In the third block, we add the complexity of the new block to the old amount of complexity. Thus, the “heavy” block chain will always be heavier than the light blocks of the fraudulent chain. This is a good marker by which the network can fight long-range attacks.

Now about the benefits of the pool.
The pool in my algorithm cannot bring an advantage precisely because it is impossible to divide the range of search values ​​between miners. Since each miner can mine only from the header of the block that contains his wallet, and this value is hashed along with the hash of the previous block, for each miner the starting value will be unique, BUT - predetermined. The pool cannot allocate a range of values ​​from 8 to 12 to the first miner, and from 56 to 72 to the other, because each miner has a predetermined starting value. In addition, due to the fact that the spectrum of values ​​is distributed randomly in the ring of values, it also cannot be correctly divided.
For example, the first miner will have his range of values ​​not from 100 to 200, but from this set: {100, 282, 13, 86, 72, 254, 989.} These are his predetermined values ​​that he must pass. He can’t jump after 282 to 283 ... Do you understand?
And so for each miner.
Moreover, these values ​​are NOT KNOWN in advance !!! That is - they are predetermined, because they are determined by the algorithm. BUT! They are not known in advance.

Thus, the pool does not have any data that can allow it to make a competent distribution of the spectrum of calculations.
That's why I drew that when using my algorithm, each miner will have the same range of values ​​for searching a hash.
However, you should not be mistaken that such a situation will lead to the fact that all miners will find the hash value at the same time. Someone, after starting the calculation of the block, will not be able to find a suitable pre-hash even for 1000 years.
But this problem is also being solved. The algorithm will check for a new block in the chain. As soon as a message appears about a new block (of a higher height), the algorithm will immediately stop calculating the obsolete block and begin to calculate a new one.
I hope I clarified your doubt to you.

[IadixDev]

I hope I clarified your doubt to you.

Yes i think i get it, still need to give it more thoughts but it looks interesting.

So the rounds can still be distributed but they still need to be computed sequentially even if its by different miners to share the work, and needs a limit on the addresses that can be used for mining.

IP is not very good for this because it can become cheap and it would require that IP and its not possible for everyone to check if the Ip match the address, would be better with a solution that doesnt depend on IP.


But maybe need to find a way to register address for mining in way that cannot be spammed easily. Or another way to identify individual miners that would be costly to réplicate i think its not impossible though. Im thinking if every miner has it own different ring path that depends on his address in sort that it would cost something to start mining from a new address because of cumulated proof of work on a specific path that depends on an address. Or some way that would penalise changing address for the pow.

[IadixDev]

Ok i thought a bit more into it, in fact as long as it stay "solo mining" as un every miner compute the whole rings, it doesnt really matter if there 1000 merkle root and address because ultimately only one path get the reward and have more or less same deterministic computation time, and the work put in // is only wasted. Maybe there can be margin gain with // processor but the reward is not going to scale with the number of // units, where the cost will still scale linearly.

Its only when the work become distributed in several miners than one with many address could get a bigger share by computing several round.

But in fact is this really a problem ? Because anyway if you have something like ouroboros to select which address are going to be selected for sharing the work of the next block, creating many address can give more chances to have a share of the work and more reward, but anyone can create also many address so as long as the mechanism to select address is fair it doesnt really matter that every miner has a single address or not no ? Even Someone with lot of // processing unit still cant get a huge advantage no ? Especially that there is supposedly a limited number of round at a given difficulty so spamming with more address will not really give that much of an advantage to // processor anyway. Maybe im wrong though

Im still trying to find the way to force a fair distribution of the work but i think its possible.

[flamehowk]

Ok i thought a bit more into it, in fact as long as it stay "solo mining" as un every miner compute the whole rings, it doesnt really matter if there 1000 merkle root and address because ultimately only one path get the reward and have more or less same deterministic computation time, and the work put in // is only wasted.
Its only when the work become distributed in several miners than one with many address could get a bigger share by computing several round.
But in fact is this really a problem ? Because anyway if you have something like ouroboros to select which address are going to be selected for sharing the work of the next block, creating many address can give more chances to have a share of the work and more reward, but anyone can create also many address so as long as the mechanism to select address is fair it doesnt really matter that every miner has a single address or not no ? Even Someone with lot of // processing unit still cant get a huge advantage no ? Especially that there is supposedly a limited number of round at a given difficulty so spamming with more address will not really give that much of an advantage to // processor anyway. Maybe im wrong though
Im still trying to find the way to force a fair distribution of the work but i think its possible.

Ok
I see that you are looking for a serious solution. Then I will tell you a secret. Remember what I wrote about my first ICO project? VenusGEET ...?
So - in this project, all the problems of cryptocurrencies are solved radically. Everything is built there on completely different principles. Including in terms of economics. BUT! This project requires a lot of development time, which means that it need a lot of finance. Nobody will give me this money. Therefore, I decided so far to offer the community ONLY ONE algorithm that can be implemented in most cryptocurrencies, and which solves a really useful task.
This is necessary in order to solve the problem of my personal survival at the moment, and also allows me to earn a little trust from the crypto community.
Therefore, at the moment I am considering the application of this POW algorithm only to the cryptocurrency architecture that already exists, and which is now recognized. And in this architecture there are a lot of problems that are still not resolved. But I will not touch them. So far, I am focused on solving ONLY ONE of them.
If you are interested in a more global solution, then it will be solved fundamentally, but only after I can find funding for my VenusGEET project.

[NeuroticFish]

Maybe I posted in the wrong thread?

Since Monero is one of the coins that changes its algo to stay anti-ASIC I've posted in their thread a link to this.
Monero users did fund useful projects (useful for Monero), but I cannot tell if this is indeed good and it's indeed what Monero needs (since afaik Monero is CPU and GPU)

[Hueristic]

I hope I clarified your doubt to you.

Yes i think i get it, still need to give it more thoughts but it looks interesting.

So the rounds can still be distributed but they still need to be computed sequentially even if its by different miners to share the work, and needs a limit on the addresses that can be used for mining.

IP is not very good for this because it can become cheap and it would require that IP and its not possible for everyone to check if the Ip match the address, would be better with a solution that doesnt depend on IP.


But maybe need to find a way to register address for mining in way that cannot be spammed easily. Or another way to identify individual miners that would be costly to réplicate i think its not impossible though. Im thinking if every miner has it own different ring path that depends on his address in sort that it would cost something to start mining from a new address because of cumulated proof of work on a specific path that depends on an address. Or some way that would penalise changing address for the pow.

You bolded is contradictory as latency would factor in to such an extent that a sequential system cannot be timely distributed.

Whether or not this effects what is trying to be achieved here is beyond me but I figured i'd point that out.

Edit: OK, I see that each portion or these rings must be sequential and then they can be combined. Weird wording, maybe I'll delve into this later I have no time today.

[IadixDev]

I hope I clarified your doubt to you.

Yes i think i get it, still need to give it more thoughts but it looks interesting.

So the rounds can still be distributed but they still need to be computed sequentially even if its by different miners to share the work, and needs a limit on the addresses that can be used for mining.

IP is not very good for this because it can become cheap and it would require that IP and its not possible for everyone to check if the Ip match the address, would be better with a solution that doesnt depend on IP.


But maybe need to find a way to register address for mining in way that cannot be spammed easily. Or another way to identify individual miners that would be costly to réplicate i think its not impossible though. Im thinking if every miner has it own different ring path that depends on his address in sort that it would cost something to start mining from a new address because of cumulated proof of work on a specific path that depends on an address. Or some way that would penalise changing address for the pow.

You bolded is contradictory as latency would factor in to such an extent that a sequential system cannot be timely distributed.

Whether or not this effects what is trying to be achieved here is beyond me but I figured i'd point that out.

Edit: OK, I see that each portion or these rings must be sequential and then they can be combined. Weird wording, maybe I'll delve into this later I have no time today.

The total workload can still be distributed even if each round or ring is computed sequentially by different miners. The goal is not To scale the workload to the moon using // processing, on the contrary its To limit it using sequential computation.

I think the logic hold because sequential computational power is not increasing, asic are not especially fast in term of clocking and sequential processing, even google use same processor clocks than what you have in common computers, They just have millions of them, if the work load is limited To what can be computed sequentially it doesnt give a big advantage to group who can put together lot of computational power exploiting // processing.

As mining is a relativist game, the absolute amount of work doesnt matter, what matter is that an attacker cant beat 51% of the network power, it seems to be an interesting idea in this regard using determinist sequential proof of work.

The distribution is only To spread the cost and reward, not To increase the total work load.

[Febo]

For several years I was thinking about how to make a POW algorithm that will be stable not only against ASIC devices, but also against GPU miners.

Have you ever heard of RandomX? RandomX is not against anything. It just dont give advantage to anything. No one can build an ASIC that have double efficiency as top CPUs you can buy in computer stores all around the world.

Since Monero is one of the coins that changes its algo to stay anti-ASIC I've posted in their thread a link to this.

Monero should not change mining algo anymore. If RandomX works as is intended to that is it.

[NeuroticFish]

Monero should not change mining algo anymore. If RandomX works as is intended to that is it.

Maybe you're right. However, I remember the early days of Monero when it was thought to be CPU only. Then it evolved to the point they changed that algo in order to fight ASICs.
I don't know the internals of RandomX. But I think that it may be useful to keep an eye on projects like this, just in case the history is repeating.