Proof-of-work System - Proof-of-work Variants

Proof-of-work Variants

There are two classes of proof-of-work protocols.

• Challenge-response protocols assume a direct interactive link between the requester and the provider. The provider chooses a challenge, say an item in a set with a property, the requester finds the relevant response in the set, which is sent back and checked by the provider. As the challenge is chosen on the spot by the provider, its difficulty can be adapted to its current load. The work on the requester side may be bounded if the challenge-response protocol has a known solution (chosen by the provider), or known to exist within a bounded search space.

• Solution-verification protocols do not assume such a link: as a result the problem must be self-imposed before a solution is sought by the requester, and the provider must check both the problem choice and the found solution. Most such schemes are unbounded probabilistic iterative procedures such as Hashcash.

Known-solution protocols tend to have slightly lower variance than unbounded probabilistic protocols, because the variance of a rectangular distribution is lower than the variance of a Poisson distribution (with the same mean). A generic technique for reducing variance is to use multiple independent sub-challenges, as the average of multiple samples will have lower variance.

There are also fixed-cost functions such as the time-lock puzzle.

Moreover, the underlying functions used by these schemes may be:

• CPU-bound where the computation runs at the speed of the processor, which greatly varies in time, as well as from high-end server to low-end portable devices.
• Memory-bound where the computation speed is bound by main memory accesses (either latency or bandwidth), the performance of which is expected to be less sensitive to hardware evolution.
• Network-bound if the client must performs few computations but must collect some tokens from various remote servers before querying the final service provider. In this sense the work is not actually performed by the requester, but it incurs delays anyway because of the latency to get the required tokens.

Finally, some POW systems offer shortcut computations that allow participants who know a secret, typically a private key, to generate cheap POWs. The rationale is that mailing-list holders may generate stamps for every recipient without incurring a high cost. Whether such a feature is desirable depends on the usage scenario.