4 ms·

The article itself lacks details on what proof of work actually is - based on your answer I’m assuming compute rather than captcha. Is there any example algorit

The article itself lacks details on what proof of work actually is - based on your answer I’m assuming compute rather than captcha. Is there any example algorithms that are easy to understand? I’m curious to see an algo that’s expensive for the client but cheap for the server to verify, I assume it involves reversing an equation or similar?

whimsicalism 3y ago
Pretty much any NP problem that we can't currently solve in polynomial time, ie. prime factorization - can be a PoW. I'm not sure which are specialized for GPU-resistance, probably not prime factorization given it can be parallelized
checkdrain 3y ago
Equihash (Birthday Problem): Memory Hardness https://en.m.wikipedia.org/wiki/Equihash https://en.m.wikipedia.org/wiki/Equihash RandomX (Execution of a random program): Memory Hardness (Inc. cache sizes), Speculative Execution/Branching, ILP, some sort of chaining https://github.com/tevador/RandomX/blob/master/doc/design.md https://github.com/tevador/RandomX/blob/master/doc/design.md Edit: these are examples of CPU-bound PoW. But the general idea with PoW is that you have some hash-like function H() with no known inverse function such that the only feasible way to determine the output is just running the function. The client runs H(x) with a different input x every time. If the output is a high enough number, the server lets the client though. The server runs H() to verify, and this is easy to parallelize. But in order to get through the server, the client must run H() many times on average. Also server provides a salt to prevent the client from reusing their old hashes. And the server usually indicates how high the output of H() must be (this is called the difficulty).
- tromp 3y ago
  > But the general idea with PoW is that you have some hash-like function H() No; that's a particular PoW algorithm called Hashcash [1]. There are other, asymmetric ones, where PoW verification is different from a solution attempt, including the Equi-X PoW that ToR is implementing. [1] https://en.wikipedia.org/wiki/Hashcash https://en.wikipedia.org/wiki/Hashcash
  - hsbauauvhabzb 3y ago
    Thanks, these are all very interesting. I’ll probably consider giving these a try for some use cases.
codetrotter 3y ago
One of the most known compute based PoW algorithms is the one used by Bitcoin. Basically it goes like this: You are challenged to use some piece of data given to you, and to add some data to it, which will produce a hash with a given number of leading zeroes. For example let’s say I challenge you to find a sha3 hash of (“response to codetrotter for comment 37255449 on HN” + any data of your choosing), with difficulty set to 3. Meaning that in order for me to accept the hash, it has to have at least three leading zeroes. The higher the difficulty, the higher number of leading zeroes I ask for from you. Which in turn means it will take you more time to find. Because the only way to find a fitting hash is to try a bunch of different data until you find a fitting hash. The neat thing is that while it takes a lot of time for you to find a matching hash, it is trivially simple for me to validate your claim when you’ve found a matching hash. For this kind of PoW, people have developed software that runs on GPU faster than most CPU can do. And then they developed specialised hardware to be even faster - ASICs. That in turn is where memory-based algorithms come into play. To make the people with GPUs and ASICs not have an advantage over others.

whimsicalism 3y ago

Pretty much any NP problem that we can't currently solve in polynomial time, ie. prime factorization - can be a PoW. I'm not sure which are specialized for GPU-resistance, probably not prime factorization given it can be parallelized

checkdrain 3y ago

Equihash (Birthday Problem): Memory Hardness https://en.m.wikipedia.org/wiki/Equihash https://en.m.wikipedia.org/wiki/Equihash RandomX (Execution of a random program): Memory Hardness (Inc. cache sizes), Speculative Execution/Branching, ILP, some sort of chaining https://github.com/tevador/RandomX/blob/master/doc/design.md https://github.com/tevador/RandomX/blob/master/doc/design.md Edit: these are examples of CPU-bound PoW. But the general idea with PoW is that you have some hash-like function H() with no known inverse function such that the only feasible way to determine the output is just running the function. The client runs H(x) with a different input x every time. If the output is a high enough number, the server lets the client though. The server runs H() to verify, and this is easy to parallelize. But in order to get through the server, the client must run H() many times on average. Also server provides a salt to prevent the client from reusing their old hashes. And the server usually indicates how high the output of H() must be (this is called the difficulty).

tromp 3y ago
> But the general idea with PoW is that you have some hash-like function H() No; that's a particular PoW algorithm called Hashcash [1]. There are other, asymmetric ones, where PoW verification is different from a solution attempt, including the Equi-X PoW that ToR is implementing. [1] https://en.wikipedia.org/wiki/Hashcash https://en.wikipedia.org/wiki/Hashcash
- hsbauauvhabzb 3y ago
  Thanks, these are all very interesting. I’ll probably consider giving these a try for some use cases.

codetrotter 3y ago

One of the most known compute based PoW algorithms is the one used by Bitcoin. Basically it goes like this: You are challenged to use some piece of data given to you, and to add some data to it, which will produce a hash with a given number of leading zeroes. For example let’s say I challenge you to find a sha3 hash of (“response to codetrotter for comment 37255449 on HN” + any data of your choosing), with difficulty set to 3. Meaning that in order for me to accept the hash, it has to have at least three leading zeroes. The higher the difficulty, the higher number of leading zeroes I ask for from you. Which in turn means it will take you more time to find. Because the only way to find a fitting hash is to try a bunch of different data until you find a fitting hash. The neat thing is that while it takes a lot of time for you to find a matching hash, it is trivially simple for me to validate your claim when you’ve found a matching hash. For this kind of PoW, people have developed software that runs on GPU faster than most CPU can do. And then they developed specialised hardware to be even faster - ASICs. That in turn is where memory-based algorithms come into play. To make the people with GPUs and ASICs not have an advantage over others.