# POW with Linear time to solve it?

Any suggestions for A Proof-of-Work algorithm in literature so that the time required for solving it is linear with the puzzle difficulty ??

• Could you not answer "yes" by taking any existing PoW algorithm with a time required for solving that is exponential with puzzle difficulty, and relabeling puzzle difficulty with $\text{difficulty}^\prime=\exp(\text{difficulty})$? Jun 24, 2018 at 21:34
• Instead of using eg leading zeroes you could also use "hash output must be smaller than x" which scales linearly in difficulty with $2^h-x$ with $h$ being the hash output size. Jun 25, 2018 at 17:09
• could you explain more, or give me an example for a such a POW algorithm ?? to give you an example of problme I am working on: I am building an application that require the difficulty (the number of leading zeros) to be directly proptional in some way to the Time of solving the puzzle. For example if it takes to get d=0 , Time may be 10 second. But to get d=00 , time will be 20 seconds. I wanna a POW that is used as a time meter Jun 27, 2018 at 2:09

I don't think an algorithm like that would exist. For PoW to facilitate a random slot leader for block generation, it has to be necessary that the PoW puzzle is really hard to solve by anyone and that no deterministic polynomial time algorithms exist which promise a solution to that puzzle, because if they would then I think that a person with a faster rig and a faster processor would solve the PoW puzzle the fastest and become the slot leader every time.
Since I have already stated that there shouldn't exist any deterministic algorithm to solve the puzzle in polynomial time, this means that the best that anyone contending for becoming the slot leader can do is to try the probabilistic approach and wish that their random nonce solves the puzzle faster than anyone else.
It is just because of this randomized (probabilistic) nature of the solution to the puzzle that the very slot leader elected is random in nature.
If you know about complexity classes of P and NP, then you will realize that if PoW is linearly solvable then it lies in P, whereas it should lie in NP i.e. given an oracle which takes all the correct steps and makes all the correct choices (meaning that selects the random nonce correctly every time) every time, then the problem is polynomial time. This means that given a solution, you can verify that the nonce is correct in polynomial time but you cannot solve the puzzle in polynomial time.

• But I if there is a way to know the time that is used to get an answer to the puzzle that is directly proportional to number of leading zeros in the Puzzle`s Solution. Jun 25, 2018 at 4:21
• The number of leading zeros will only tell you that how difficult the puzzle is i.e. how many of the random choices will succeed. The lesser the number of leading zeros the more the number of random nonces which will solve the puzzle and the easier it is to find the solution. Jun 25, 2018 at 8:39
• The number of leading zeros still don't give you a solution, it just tells how difficult will it be to find a solution. Jun 25, 2018 at 8:39
• Ok. I am building an application that require the difficulty (the number of leading zeros) to be directly proptional in some way to the Time of solving the puzzle. For example if it takes to get d=0 , Time may be 10 second. But to get d=00 , time will be 20 seconds. I wanna a POW that is used as a time meter Jun 26, 2018 at 8:45