Skip to content

Proof-of-Work (PoW)

links: DSS TOC - Preliminaries - Index

Concept

The idea of a Proof of Work (PoW) is to be able to proof that some work has been done. I can proof to the teacher that I did some work by giving her an answer to a question she gave me.

The Proof of Work scheme looks as follows:

  • \(solve(p,d,f)\) \(\rightarrow\) \(s\):
    • \(p\) for puzzle: This is the problem to be solved which shall demonstrate that work was done.
    • \(d\) for difficulty: The problems difficulty must be adjustable, so that the PoW remains usable in the future. It's a requirement regarding the solution.
    • \(f\) for function: The underlying function of the puzzle which helps to solve it. \(f\) must take the puzzle and the solution as input. The result must be equal to the difficulty \(d\).
  • \(verify(p,d,s,f)\) \(\rightarrow\) \(True | False\):
    • \(p\) for puzzle: The puzzle which was to be solved.
    • \(d\) for difficulty: The problems difficulty.
    • \(s\) for solution: The solution obtained by solve.
    • \(f\) for function: The function which defines the problem to be solved.

Given this scheme we can say that: \(verify(p,d,solve(p,d,f),f) = True\), iff \(f\) solves the problem such that given \(p\) and \(s\) as input result in \(d\) The PoW therefore lies in finding a solution \(s\) which as parameter of the function \(f\) results in a definable difficulty \(d\) when combined with puzzle \(p\).

Hashcash

Hashcash was the first implementation of a PoW which works as follows:

\(f\) = SHA256(\(p\) || \(s\)), (|| is the concatenation operation) \(p\) = bit string \(d\) = number of leading zero bits in solution

When we want to solve the following problem:

\(d = 2\) \(p = 01001100011\)

we would try to find a solution \(s\), so that:

001... = SHA256(01001100011 | \(s\))

Puzzle-Friendliness

The PoW is predestinated to use hash functions. Especially if the hash function is puzzle-friendly. A hash function is puzzle-friendly if there is no better way of solving the puzzle \(d = hash(p || s)\), than just randomly trying. This comes because a hash is easy to calculate but hard (or impossible) to invert. This makes verification easy but solving the puzzle hard.

links: DSS TOC - Preliminaries - Index