ProofofWork
Learn how the PoW is used in blockchainbased systems to ensure the integrity of the ledger.
Partial hash inversion
We introduced the approach of ProofofWork in this lesson as a countermeasure against DenialofService or Sybil attacks, where we referred to the mechanism as a hash puzzle that needs to be solved in order to provide evidence to a verifier that a prover has invested a certain amount of computational resources into a specific task. In this section, we show how the PoW is used in blockchainbased systems to ensure the integrity of the ledger.
ProofofWork
A ProofofWork is a cryptographic puzzle used to ensure that a party has performed a certain amount of work (
Furthermore, he claims that a PoW should require a bounded probabilistic cost, meaning that the computational puzzle can only be solved by trial and error and thus the solution can be found in a predictable expected time, whereas there is an upper bound on the cost of finding a solution.
Characteristics of PoW
A ProofofWork mechanism has to fulfill the following characteristics (

The PoW is computationally efficient to verify.

The PoW is computationally difficult to generate.

The difficulty to compute the PoW is adjustable.

The probability for a user to find a valid PoW is proportional to their share of invested resources.
In
Nonce
A nonce (number only used once) is an arbitrary number used only once in a cryptographic communication.
Difficulty
The difficulty $D$ is the number of leading zeros the hash value has to produce in order to solve the hash puzzle.
Note: The difficulty is chosen such that the network mines new blocks in a predetermined, expected time interval. Thus, the difficulty must be adjustable since the hash power of the whole system is inconstant.
In numerical terms, one needs to find a hash value that’s less than a predefined threshold what is called the target.
Target
The target $T$ is the threshold below which the resulting hash value must be in order to solve the hash puzzle.
It’s obvious that decreasing the target increases the difficulty of finding a suitable hash inversion, hence the task of finding a suitable hash less than the target becomes more and more difficult, i.e., the target and the difficulty are inversely related.
Partial hash inversion PoW
Let $H(\cdot)$ be a cryptographic hash function, $T$ the target, $m$ a message and $n$ an arbitrary nonce. Then, $n$ is the solution of the PoW if
$H(m \ n) \leqslant T.$
Note: Every nonce $n$ that produces an output $H(m \ n)$ that’s below or equal to a certain target value $T$ is considered as a valid solution to the PoW.
Since the hash function $H(\cdot)$ is preimage resistant, inequality in the above equation can only be solved by bruteforce search, which means that solving the PoW requires guessing a nonce $n$. If the hash value fulfills the specifications of the target, the hash puzzle is solved, i.e., we’ve found a suitable nonce $n$, otherwise, we’ll modify the nonce (usually by incrementing it by one) and try again until the solution is found. Algorithm 7 shows how the PoW can be solved. Since any hash function is evenly distributed, every hash value has the same probability, thus we can conclude that finding a solution to a PoW is a “probabilistic process with a success probability depending on the predefined difficulty” (
Algorithm 7
Solving the ProofofWork
Required: $n \ge 0$
$\quad$ while $H(m \ n)>T$ do
$\qquad$ $n\leftarrow n+1$
$\quad$ end while
$\quad$ $solution \leftarrow n$
Get handson with 1200+ tech skills courses.