Pages:
Author

Topic: Anti ASIC/GPU/FPGA POW-algorithm. New (2019). - page 2. (Read 1230 times)

newbie
Activity: 23
Merit: 6
Ok let say on 10 minutes block you would create chunks of 10 sec of work, like first generating the total ring chain to be computed, then breaking it down to séries of sub ring chain, in sort that each sub chain need to hash its address or id with the previous work.

Now let say this miner id is not just the address, but an ip/address pair. Each time a new node appear on the network it register itself on the network, and put on the global list of miners id, each time a new block arrive this address/Ip pair is hashed with the new block signature and miners id sorted on this hash, and the first 60 are selected for the next block.

The Ip will be used to send the work to the miner and to send it to the next so Ip can checked in and out even if that wouldnt prevent 3 ips to collude to steal work.

It could be made stronger if all nodes do traceroute on miners and a consensus can be reached on topography of ips, i tend to think its a problem that has a degree of byzantine fault tolerance as any node can check the traceroute of other nodes and deduce if the traceroute sent by another node is incohérent, i think its a classic problem of graph theory with a byzantine fault tolerance, similar to this Techniques for Detection of Malicious Packet Drops in Networks   , taking in account that the topography doesn't have to be 100% accurate, but at least give sufficient probability that two nodes are not located too close to each others, and using some connectivity testing along path with a technique similar to the link. Some 'hard' consensus could be added if there is too much conflict above the byzantine fault tolerance of the system.

Would be a long shot, but wouldnt this garantee a certain degree of decentralisation ?

There are so many problems with this I don't even know where to start.

1. This scheme fails to provide the most important property: consensus. What happens if a node receives two different blocks, each with a correct set of 60 signatures? Which version of the blockchain is it going to choose? Note that this doesn't have to be malicious, it can be simply caused by a temporary network split.

2. You failed to explain what happens if one of the 60 selected miners doesn't respond, either maliciously or due to simply being offline.

3. Using IP addresses is a can of worms you don't want to open, trust me. Are you going to limit 1 unique address per IP address? Are you aware that sometimes thousands of people share the same external IP? Are you aware that network routing changes rapidly, sometimes several times per day? Do you know that a billion of IPv6 addresses can be rented for less than $1 per month? Have you thought about the privacy implications of linking coin addresses with physical network addresses?
full member
Activity: 322
Merit: 151
They're tactical
one miner get all the reward when he find the good nonce, and all the other work done for the block is useless.

The "useless" work is what makes the hashcash style PoW secure.

It still need a way spread the work in sort that you have this same kind of distribution of reward based on miner ID or address, except that the miner is just idle until he is given the work, and the distribution depends on another algorithm that define which address is going to do which part of the work for a given block, and all other miner just idle and do no work, so they don't 'loose' anything

Then the main question is what provides the incentive for miners to cooperate (and suffer the network latency penalty) rather than mine selfishly 100% of the time.

For example, if the block interval is 10 minutes, each stages takes 1 ms to calculate and the average network delay is 49 ms, we can support up to 12000 cooperating miners on the network. However, a selfish miner can calculate 600000 stages locally (with 600000 different addresses) and win the whole block reward every time because his blockchain contains more work than the cooperating blockchain.



Ok let say on 10 minutes block you would create chunks of 10 sec of work, like first generating the total ring chain to be computed, then breaking it down to séries of sub ring chain, in sort that each sub chain need to hash its address or id with the previous work.

Now let say this miner id is not just the address, but an ip/address pair. Each time a new node appear on the network it register itself on the network, and put on the global list of miners id, each time a new block arrive this address/Ip pair is hashed with the new block signature and miners id sorted on this hash, and the first 60 are selected for the next block.

The Ip will be used to send the work to the miner and to send it to the next so Ip can checked in and out even if that wouldnt prevent 3 ips to collude to steal work.

It could be made stronger if all nodes do traceroute on miners and a consensus can be reached on topography of ips, i tend to think its a problem that has a degree of byzantine fault tolerance as any node can check the traceroute of other nodes and deduce if the traceroute sent by another node is incohérent, i think its a classic problem of graph theory with a byzantine fault tolerance, similar to this Techniques for Detection of Malicious Packet Drops in Networks   , taking in account that the topography doesn't have to be 100% accurate, but at least give sufficient probability that two nodes are not located too close to each others, and using some connectivity testing along path with a technique similar to the link. Some 'hard' consensus could be added if there is too much conflict above the byzantine fault tolerance of the system.

Would be a long shot, but wouldnt this garantee a certain degree of decentralisation ?
newbie
Activity: 23
Merit: 6
one miner get all the reward when he find the good nonce, and all the other work done for the block is useless.

The "useless" work is what makes the hashcash style PoW secure.

It still need a way spread the work in sort that you have this same kind of distribution of reward based on miner ID or address, except that the miner is just idle until he is given the work, and the distribution depends on another algorithm that define which address is going to do which part of the work for a given block, and all other miner just idle and do no work, so they don't 'loose' anything

Then the main question is what provides the incentive for miners to cooperate (and suffer the network latency penalty) rather than mine selfishly 100% of the time.

For example, if the block interval is 10 minutes, each stages takes 1 ms to calculate and the average network delay is 49 ms, we can support up to 12000 cooperating miners on the network. However, a selfish miner can calculate 600000 stages locally (with 600000 different addresses) and win the whole block reward every time because his blockchain contains more work than the cooperating blockchain.

full member
Activity: 322
Merit: 151
They're tactical
the distribution of time between solutions must be exponential (since it's the only memoryless distribution), i.e. the probability of finding a solution at time t < T is:

This ok, but need to see the bigger picture of why these property makes it ideal proof of work.

The idea with the model you describe is the distribution of the reward is based on equal chance to win the reward for each unit of work done, with 99% of the work done that doesn't participate in the final solution, only one miner get all the reward when he find the good nonce, and all the other work done for the block is useless.

The idea of OP for reward distribution is clearly different because each unit of work done participate to the elaboration of the final proof and earn a reward. The problem is how to force the work to be shared between different miners to distribute the reward, as each unit of work has 100% chance of being rewarded, and the total amount of work is determined for a given block target time, the distribution must use another mechanism. If a miner is never allocated a "work slot", then he just idle and cost nothing, when he is allocated a "work slot", he compute the proof using the previous one from another miner and gain the reward.

It still need a way spread the work in sort that you have this same kind of distribution of reward based on miner ID or address, except that the miner is just idle until he is given the work, and the distribution depends on another algorithm that define which address is going to do which part of the work for a given block, and all other miner just idle and do no work, so they don't 'loose' anything, and you could have still same idea of the probability to given work to do in a time T will be evenly distributed between all miners, even if a single persons could spawn many miners.

It would still end with the same sort of calcultion except the C for core become a miner ID, and miner is idle until his ID is selected to mine a block.

It's not the same principle than bitcoin pow, but i think it could be viable , or not completely impossible to solve, but maybe i'm missing something.
newbie
Activity: 23
Merit: 6
In case it was not clear from the conversation above, I'm posting an informal proof:

If an algorithm is progress-free (or memoryless), the distribution of time between solutions must be exponential (since it's the only memoryless distribution), i.e. the probability of finding a solution at time t < T is:

Code:
P(t < T) = 1 - exp(-C*T)

for some constant C, which equals to the relative computational power.

If I have two equally powerful machines, then the probability that I find a solution at time t < T if I mine with both of them is:

Code:
P2(t < T) = 1 - (1 - P(t < T)) * (1 - P(t < T))
          = 1 - exp(-C*T) * exp(-C*T)
  = 1 - exp(-2*C*T)
    
which is exactly the same as the probability for a twice more powerful machine.

So progress-freeness implies perfect parallelizability.
full member
Activity: 322
Merit: 151
They're tactical
My main point is that you cannot have a permissionless proof of work system that's not parallelizable.

Really ? you have link to a book or paper explaining this ? Smiley
newbie
Activity: 23
Merit: 6
My main point is that you cannot have a permissionless proof of work system that's not parallelizable.
full member
Activity: 322
Merit: 151
They're tactical
Then it's not progress-free. The miner who starts first will always solve the block, which is not what you want in a decentralized cryptocurrency.


It's not progress-free, but the work can still be distributed on different addresses, selected evenly for each block. In the end it still have same property than progress-free work for decentralization of the mining. But it needs another system to distribute the work than the pow itself.
newbie
Activity: 23
Merit: 6
Why ? If each unit of work depend on the result of previous work, it's still non parallelizable ?

Then it's not progress-free. The miner who starts first will always solve the block, which is not what you want in a decentralized cryptocurrency.

Even if already it get to the point of not being able to distinguish many small miners from a big entity, they will still all mine with equal work-cost, which is already a win as i see it Smiley And its possible to find way to prevent it to a degree, or make it harder to do.

No, the large entity will mine more efficiently using many parallel calculations. The standard progress is: CPU -> GPU -> FPGA -> ASIC. On the blockchain, it will look like many small miners claiming the block reward, but in reality there will be no decentralization.
full member
Activity: 322
Merit: 151
They're tactical
If you make the unit of work small, you will achieve progress-freeness, but you will lose non-parallelizability.

Why ? If each unit of work depend on the result of previous work, it's still non parallelizable ?


"Proof of miner id" is susceptible to sybil attacks since you can't limit the generation of new addresses without some central authority.

In short, there is no way to distinguish many small miners from a single entity mining in parallel with many addresses.

I spent a fair bit of time researching this myself and I'm pretty sure it's a dead end.

Even if already it get to the point of not being able to distinguish many small miners from a big entity, they will still all mine with equal work-cost, which is already a win as i see it Smiley And its possible to find way to prevent it to a degree, or make it harder to do.


The principle in itself could be close to some onion routing as each node re encrypt the previous message, except it cycle back to the original point after a certain number of rounds. It would need to establish a route through nodes to compute all the work sequentially, adding their address to the computation.

But maybe the OP has a solution to this Smiley  need to wait a bit for updates Smiley
newbie
Activity: 23
Merit: 6
If you make the unit of work small, you will achieve progress-freeness, but you will lose non-parallelizability. "Proof of miner id" is susceptible to sybil attacks since you can't limit the generation of new addresses without some central authority.

In short, there is no way to distinguish many small miners from a single entity mining in parallel with many addresses.

I spent a fair bit of time researching this myself and I'm pretty sure it's a dead end.
full member
Activity: 322
Merit: 151
They're tactical
they will all take the same time to compute

Then it's not progress-free, which is a fundamental requirement for decentralized proof of work. PoW that is not progress-free will not work in practice because it encourages selfish mining, i.e. each miner will mine their own chain to avoid the network latency delay.


Its a problem i pointed before, but not sure it cannot be solved. I didnt see a full solution for this, but in theory it should still be possible to force a break down of the work, like forcing each ring to be computed with a different address, as it can still be broken into small pieces and the proof still need all the work to be done, and the minimal unit of work is very small, so maybe it can still be forced into small bits including network latency.

I still dont see a perfect solution for this, but i think it can be worked around. I think if a way To make poisson like distribution on the address or miner id can be found, it can replace the progress free problem up stream by forcing a break down of the work, it require zero initialisation time , and the minimal unit of work can be very small, so i think it would be equivalent. It still have same property than any miner id has equal chance to get a reward even with small computational power, even if it needs another mechanism to distribute the work than the pow itself.

It could be a system similar in some aspect to ourobos in cardanno, even if the difference is cardanno works with POS so the reward is related to the stake power of an address, and here the reward distribution would be more based on a "proof of miner id" than the pow itself, but then anyone with even small cpu power can participate and have equal chance to get reward with other miners, and its less vulnerable than POS to long range attack with the nothing at stake problem, even if i cant see a good way To avoid penalising miners with high network latency, without ending with problems if a node in the mining chain stop responding or have high latency to compute his part of the work.

Another potential problem i see is that the total pow is not going to scale with the number of miners, the amount of work to do to solve a full block will stay constant for a given block target, which will limit the maximum number of miner that can get a reward for a given block, so there is lower probability for a miner to get a reward in short time on a large network with lots of miners.

There are certain number of issue to study well, but i dont think its completely unsolvable even if it would more thinking and few more mechanism for it To work Well in practice.
newbie
Activity: 23
Merit: 6
they will all take the same time to compute

Then it's not progress-free, which is a fundamental requirement for decentralized proof of work. PoW that is not progress-free will not work in practice because it encourages selfish mining, i.e. each miner will mine their own chain to avoid the network latency delay.
full member
Activity: 322
Merit: 151
They're tactical
2. Even if you remove the timestamp and nonce from the block header, any miner can generate as many wallet addresses as they want to get unlimited parallelization.


Only one address will get the reward, and they cant work in parallel on the same chain, no ring chain can advance faster with parallelisation. They can compute differents ring chain in // with different address, they will all take the same time to compute, and only one reward, so there is no huge benefits To that. ( if i get it right Smiley )

The issue with the address spamming can become a problem to distribute the work across different miners, but even if there is address spamming, they will still have same cost/hash To compute the ring for each address, and everyone can address spam as well, so i think its solvable. In any case it comes back closer To 1 cpu one vote, even if someone with many addresses could get more work and reward in a pooled work, even with a single cpu, the number of cpu doesnt matter.


This idea is not new. Search for the "RSA timelock puzzle" - this is the most famous non-parallelizable proof of work. However, it only works when some central authority is generating the work. It is absolutely useless for decentralized consensus in cryptocurrencies.

There are many problems that can be solved only throught recursion, but its not cyclic like this, so it needs the solution to be known first, then puzzle made from it, for system like this where the solution is known first there are many way to have proof of work, but here the solution is not known first, but the work can still be verified in one step.
newbie
Activity: 23
Merit: 6
This idea is not new. Search for the "RSA timelock puzzle" - this is the most famous non-parallelizable proof of work. However, it only works when some central authority is generating the work. It is absolutely useless for decentralized consensus in cryptocurrencies.

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.

1. You need timestamps to adjust the difficulty of the PoW so you can keep an approximately constant block rate.
2. Even if you remove the timestamp and nonce from the block header, any miner can generate as many wallet addresses as they want to get unlimited parallelization.
full member
Activity: 322
Merit: 151
They're tactical
I made some code to find all possible rings, and storing them in a csv file
it's all the combination i found : https://github.com/NodixBlockchain/rbf/blob/master/keylst.csv
Also made a thing to generate loops path randomly and run the forward/backward thing, it seems to work  Smiley
I did some more testing, testing more combination of rings it doesn't seem too bad Smiley But there are probably some combination that works better than others.
Why did you spend time on this? This has already been done by me and it can be seen from my video. In addition, this is not necessary, because in this code 32-bit numbers will not be used, 256-bit numbers will be used there, and completely different keys are needed for them. Smiley

Just to do some testing Smiley but it seems ok Smiley but ok i wait for the full code Smiley

But it's not very long to compute, it took less than a minute to scan most possible value, even doing it four times with four different number to make sure there is no false positive.

Tested with many different combination of rings up To 1024 picked randomly seems To work Smiley
member
Activity: 264
Merit: 13
I made some code to find all possible rings, and storing them in a csv file
it's all the combination i found : https://github.com/NodixBlockchain/rbf/blob/master/keylst.csv
Also made a thing to generate loops path randomly and run the forward/backward thing, it seems to work  Smiley
I did some more testing, testing more combination of rings it doesn't seem too bad Smiley But there are probably some combination that works better than others.
Why did you spend time on this? This has already been done by me and it can be seen from my video. In addition, this is not necessary, because in this code 32-bit numbers will not be used, 256-bit numbers will be used there, and completely different keys are needed for them. Smiley
full member
Activity: 322
Merit: 151
They're tactical
I made some code to find all possible rings, and storing them in a csv file

it's all the combination i found : https://github.com/NodixBlockchain/rbf/blob/master/keylst.csv

Also made a thing to generate loops path randomly and run the forward/backward thing, it seems to work  Smiley

I did some more testing, testing more combination of rings it doesn't seem too bad Smiley But there are probably some combination that works better than others.
full member
Activity: 322
Merit: 151
They're tactical
Sha256 has very high entropy, zero regression or anything it has non linear components to cascade and amplify all the source entropy capped with a mod.
Good. I think I understand what you don’t understand. Let's do so - I'll finish the code today and shoot the last video. Then I will post the video and my code. You will take one ring from this code, BUT + take my hash function Mystique to it and use it to mask the starting number.
That is, your sequence should be like this:
Take a weak starting number, for example - 0x1 (256 bit, like in SHA256)
We perform its hashing through Mystigue.
We calculate one ring through RBF.
You then pass this combination through your tests and see what they show you.
OK?

Oki Smiley Can do more testing adding the hash, im always up to cracking a good number sequence Cheesy
member
Activity: 264
Merit: 13
Sha256 has very high entropy, zero regression or anything it has non linear components to cascade and amplify all the source entropy capped with a mod.
Good. I think I understand what you don’t understand. Let's do so - I'll finish the code today and shoot the last video. Then I will post the video and my code. You will take one ring from this code, BUT + take my hash function Mystique to it and use it to mask the starting number.
That is, your sequence should be like this:
Take a weak starting number, for example - 0x1 (256 bit, like in SHA256)
We perform its hashing through Mystigue.
We calculate one ring through RBF.
You then pass this combination through your tests and see what they show you.
OK?
Pages:
Jump to: