3
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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})$? $\endgroup$ – Cort Ammon Jun 24 '18 at 21:34
  • 2
    $\begingroup$ 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. $\endgroup$ – SEJPM Jun 25 '18 at 17:09
  • $\begingroup$ 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 $\endgroup$ – Mohamed Ismail Jun 27 '18 at 2:09
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mohamed Ismail Jun 25 '18 at 4:21
  • $\begingroup$ 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. $\endgroup$ – Mayank Jun 25 '18 at 8:39
  • $\begingroup$ The number of leading zeros still don't give you a solution, it just tells how difficult will it be to find a solution. $\endgroup$ – Mayank Jun 25 '18 at 8:39
  • $\begingroup$ 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 $\endgroup$ – Mohamed Ismail Jun 26 '18 at 8:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.