Proof-of-Work

Partial hash inversion

We introduced the approach of Proof-of-Work in this lesson as a countermeasure against Denial-of-Service 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 blockchain-based systems to ensure the integrity of the ledger.

Proof-of-Work

A Proof-of-Work is a cryptographic puzzle used to ensure that a party has performed a certain amount of work (Krzysztof Okupski (2016)Krzysztof Okupski. Bitcoin developer reference. http://enetium.com/resources/ Bitcoin.pdf, Jul 2016. Accessed: 2018-07-02.).

Back (2002)Adam Back. Hashcash-a denial of service counter-measure. Technical report, 2002. describes the main property of a noninteractive Proof-of-Work as the solution of the problem which should be parameterizable expensive to compute, but computationally efficient to be verified by any third party without access to any trapdoor information.

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 Proof-of-Work mechanism has to fulfill the following characteristics (Aljosha Judmayer et al. (2017)Aljosha Judmayer, Nicholas Stifter, Katharina Krombholz, Edgar Weippl, Elisa Bertino, and Ravi Sandhu. Blocks and Chains: Introduction to Bitcoin, Cryptocurrencies, and Their Consensus Mechanisms. Synthesis Lectures on Information Security, Privacy, and Trust. San Rafael, CA, 2017. Morgan Claypool.):

1. The PoW is computationally efficient to verify.

2. The PoW is computationally difficult to generate.

3. The difficulty to compute the PoW is adjustable.

4. The probability for a user to find a valid PoW is proportional to their share of invested resources.

In Back (2002)Adam Back. Hashcash-a denial of service counter-measure. Technical report, 2002., proposed the use of partial hash inversion as a hash puzzle, where one has to apply a hash function to data that’s combined with an arbitrary number called a nonce, whereas the nonce needs to be varied until the resulting hash value fulfills given restrictions, whereas the restrictions are normally fulfilled if the resulting hash starts with at least a certain number of $0$ bits.

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 brute-force 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” (Krzysztof Okupski (2016)Krzysztof Okupski. Bitcoin developer reference. http://enetium.com/resources/ Bitcoin.pdf, Jul 2016. Accessed: 2018-07-02.).

---

Algorithm 7

Solving the Proof-of-Work

---

Required: $n \ge 0$

$\quad$ while $H(m \| n)>T$ do

$\qquad$ $n\leftarrow n+1$

$\quad$ end while

$\quad$ $solution \leftarrow n$

---