Proof of work (PoW) algorithms generally have no notion of progress, instead they are more like playing the lottery millions of times until you win. L

Controlling Variance in Proof-of-Work Algorithms

submited by
Style Pass
2023-05-30 12:00:05

Proof of work (PoW) algorithms generally have no notion of progress, instead they are more like playing the lottery millions of times until you win. Losing a million times doesn’t influence your chances of winning the next one.

That’s ok and probably even desirable for applications like a cryptocurrency mining, but undesirable for an application like hashcash in which the proof of work is used as a payment for say, signing up for a website. We created an open source, more user-friendly captcha based on proof of work. It is important that this captcha takes roughly the same amount of computation for any given user to complete, and even more important that there are no outliers.

In the lottery example there are no guarantees, one user might win on the first attempt, and another may need many attempts. Before we dive into specifics and the simple solution, let’s explore the properties of a good proof of work problem.

A PoW that would be “hash this string 1 million times” would be expensive to compute, but just as expensive to verify. Instead most PoW algorithms make the user search for a needle in a haystack: we generate a puzzle string p, and ask the user to find a nonce q such that the hash of p and q concatenated meets some rare criteria. If we use a good hash function, any input string is just as likely to meet this criteria as another.

Leave a Comment