Proof of Work (PoW)

Proof of work (POW, PoW) is a principle for protecting network systems from abuse of services (for example, from DoS attacks or the organizing of spam mailings), based on requiring the client to perform some sufficiently lengthy piece of work (finding the solution to a problem), the result of which is easily and quickly verified on the server side (see one-way function). The main feature of the computations used lies in the asymmetry of the time cost — finding the solution takes significant time, while verification is very fast . Such schemes are also known as a client puzzle (client puzzle function), a computational puzzle (computational puzzle function), or a CPU pricing function.

This method of protection should not be confused with CAPTCHAs, which pose tasks that are easy for a human but difficult or altogether unsolvable for a computer. Proof of work is originally oriented toward finding a solution via a known algorithm within some finite time, but verifying the resulting solution requires a relatively small number of operations. POW technology has seen its widest adoption and development in cryptocurrency systems.

History

The requirement of proof of work was first put forward in the article “Pricing via Processing or Combatting Junk Mail” in 1993. The authors proposed the following idea: to access a shared resource, a user must compute some function that is quite complex and resource-intensive, yet solvable within an acceptable amount of time. Computing the function on the client side must be far harder than verifying the result on the server side. One of the mandatory requirements for the function is its non-amortizability — finding several solutions should take time proportional to their number. The authors assumed that such extra computations would not hinder the sending of a few ordinary letters from an average user's computer, but that the need for constant computation would make sending spam very resource-intensive. According to independent estimates, such systems in practice lead to a substantial restriction on the number of letters that can be sent per day from a single computer .

In 1997, Adam Back launched the Hashcash project, dedicated to spam protection. The task was formulated as follows: “Find a value x such that the hash SHA(x) contains N leading zero bits.”

In 1999 the term Proof-of-Work appeared — it was used in the article “Proofs of Work and Bread Pudding Protocols” (authors — Markus Jakobsson and Ari Juels) in the journal Communications and Multimedia Security .

On August 16, 2004, Hal Finney, in his letter on the cypherpunks forum, proposed using a reusable proof of work (Reusable-Proofs-of-Work, RPOW, RPoW) to set up an electronic currency .

Soon afterward, Satoshi Nakamoto proposed the Bitcoin cryptocurrency, in which proof of work is used to significantly complicate double-spending. It was proposed to find the hash of a block of information via the SHA-256 function by selecting parameters so that a given number of the result's leading bits would be zero. Later, other cryptocurrencies (for example, Litecoin) began using KDFs such as scrypt, bcrypt, PBKDF2 and others instead of SHA-256 .

One popular system, used in Hashcash , uses partial hash inversion to prove that work was done, as a goodwill token for sending an email . For example, the following header represents about 2 ⁵² hash computations for sending a message

This is verified with a single computation, by checking that the SHA-1 hash of the stamp (without the header name, X-Hashcash: including the colon and any number of spaces following it up to the digit '1') begins with 52 binary zeros, that is, 13 hexadecimal zeros:

Whether PoW systems can really solve a specific denial-of-service problem, such as the spam problem, is a matter of debate; the system should make sending spam intrusively unproductive for the spammer, while also not hindering legitimate users from sending their messages. In other words, a genuine user should not run into any difficulty when sending email, but an email spammer would have to spend significant computing power to send many emails at once. Proof-of-Work systems are used as primitives by other, more complex cryptographic systems, such as Bitcoin, which uses a system similar to Hashcash.

Variants

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

• Protocols using challenge-response assume direct interactive communication between the requesting party (the client) and the provider (the server). The provider chooses a task, say, an element of a set with a given property, and the requester finds the matching answer in the set, which is sent back and checked by the provider. Since the task is chosen by the provider on the spot, its difficulty can be adapted to the current load. The work on the requester's side can be limited if the challenge-response protocol has a known solution (chosen by the provider) or is known to lie within a bounded search space.

• Protocols based on solution verification do not assume such communication: as a result the problem must be self-imposed before the requester finds a solution, and the provider must verify both the choice of the problem and the solution found. Most such schemes are unbounded probabilistic iterative procedures, such as Hashcash .

Protocols with known solutions 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). ^{[ additional explanation needed ]} A common method of reducing variance is to use several independent subtasks, since the average of several 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 can be:

• CPU-bound, where computations are performed at processor speed, which varies greatly over time , and also across the range from high-performance servers to entry-level portable devices.
• Memory-bound ^[10], where the speed of computation is limited by access to main memory (either by latency or by bandwidth), whose performance is expected to be less sensitive to the evolution of hardware.
• Network-bound ^[11], if the client must perform several computations but must also collect certain tokens from remote servers before making its request to the final service provider. In this sense the work is not really performed by the initiator of the request, but delays still arise anyway, from the latency involved in obtaining the required tokens.

Finally, some PoW systems offer fast computations that allow participants who know a secret, usually a private key, to generate cheap PoWs. The reason is that mailing-list holders can create stamps for each recipient without incurring large costs. Whether such a feature is desirable depends on the use case.

Examples of functions used

A list of the most common functions used in proof-of-work systems:

• Partial hash inversion. The best-known application is the Hashcash system, which uses partial hash inversion when sending email. Computing the header for a single letter requires about 2⁵² hash computations, which must be recomputed for every new letter. At the same time, checking the correctness of the computed code is fast — a single SHA-1 computation is performed against a pre-prepared stamp. ^[10]
• Functions based on Merkle trees.^[11] The best-known example of this approach can be found in the Bitcoin system, where multi-level hashing is used as proof of work — the hash of the previous block becomes an element of the next one. This makes it impossible to change a block without changing the hashes of all subsequent blocks. At the same time, verifying the integrity of the whole chain is limited to a single computation of the hashes of the current block and the previous one. A hash is accepted as valid only if the value of the hash sum is less than the value of a special parameter that determines mining difficulty. Finding such a hash sum requires repeatedly recomputing it while iterating over arbitrary values of the nonce parameter.^[12]
• Quadratic residue modulo a large prime number^[13]
• Signature under the Fiat—Shamir protocol^[13]
• A function based on the Diffie—Hellman protocol^[14]
• Memory-bound function (en:Memory bound function)^[15]
• Cuckoo hashing^[16]

Potential vulnerabilities and attacks on POW-based information systems

Experts continue to debate whether POW protection is sufficiently effective against DoS attacks and spam^[17][18].

51% attack

In its early days, Bitcoin, like many other cryptocurrencies, is vulnerable to a “51% attack”: if an attacker controls more than half of all the computing power on the network, they gain the ability to confirm only their own blocks while ignoring everyone else's, letting them obtain 100% of all bitcoins produced, as well as block any transactions. Alternatively, the attacker can rewrite the entire history of block generation starting from some point in the past. As a result, they can catch up with and overtake the current blockchain, making their own version the valid one. As a consequence, money held in users' wallets over a long period of time would disappear.^[12]

Double-spending

Double-spending (a double spend) — the repeated transfer of one and the same assets. This attack breaks down into several subtypes.

• The “race” attack (Race Attack). The attacker carries out transaction X, paying for a purchase, while simultaneously transferring the same money to another account of their own via transaction Y. If the seller does not wait for confirmation of the transaction and ships the goods, they are taking a large risk, since there is a 50% probability that transaction Y ends up in the true chain, and this probability rises if the attacker deliberately chooses which network nodes to use for one operation or the other.^[19]

• Finney attack works as follows: the attacker tries to find a block that contains their transaction Y. However, as soon as the block is found, the attacker sends transaction X, after which they buy the goods. The seller waits for confirmation of transaction X and ships the goods. If, at that moment, a block with transaction Y appears, a fork situation is created in which miners must choose one of the two blocks to continue the blockchain. By concentrating a large amount of computing resources in the attacker's hands, they can significantly increase the probability that the block with operation Y is chosen. Thus a confirmed transaction is not guaranteed to be valid.^[20]

Selfish mining

In selfish mining (English: selfish mining), the attacker's goal is to control the network while holding computing resources whose total power is less than 50%. This is achieved by the attacker claiming that their pool is more profitable to mine in than other pools, which attracts outside miners. The attacker publishes blocks in such a way that the computing resources of other miners and pools are wasted. The rough course of the algorithm is as follows:

1. The pool secretly, unknown to everyone, mines its own private chain.
2. If the pool finds a new block for its private chain, then:
   1. If the original chain has forked, the attacker publishes their block, so that their chain becomes longer and becomes the true one, and the honest miners' chain is discarded.
   2. If there is no fork yet, the pool continues to secretly mine its private chain, extending its lead.
3. If the public chain finds a block for the publicly shared chain, then:
   1. If the public chain is ahead of the secret one, the attacker's pool discards its unpublished blocks and starts mining from the new public block.
   2. If the chains are level, the attacker's pool publishes all of its blocks, thereby pulling ahead on its own chain.
   3. If the public chain trails the private one by some number (N) of blocks, the pool publishes one block more (N+1), which isolates the new honest block.

In almost every outcome, honest miners end up worse off, which forces them to join the criminal pool.^[21]

Criticism of POW-based information systems

Opponents of the POW approach, besides a number of potential security problems, point to the following drawbacks:

• The probability that a miner will successfully create the next block is directly proportional to the computing power they hold, which leads to a constant increase in the quantity and quality of each network participant's equipment. Thus mining with POW algorithms requires an extremely large amount of electricity. For this reason the POW approach is not the best solution from the standpoint of energy efficiency.^[22][23]
• The results of computing hash functions are not needed anywhere except within the network itself. Ever since the technology appeared, the community has tried to come up with a way to direct all of the network's computing resources toward solving some useful mathematical or industrial problem, but this has not been achieved in its pure form.^[24]

Attempts to get rid of POW's shortcomings led to the emergence of POS and numerous hybrid variants.

Examples of hybrid technologies

Examples of hybrid schemes combining the ideas of POS and POW can be found in many cryptocurrencies. In them the blockchain consists of blocks of both types, which makes rewriting transaction history a difficult task, since POW blocks serve as checkpoints, given the total difficulty of the work across the whole chain. Usually, in such algorithms, POW blocks serve as indicators of real work performed, which gives sellers an extra guarantee of reliability when dealing with transactions. POW blocks can be used for currency issuance, while POS blocks can be regarded as potential income from a deposit.^[25]

Proof of Activity

A prototype algorithm not yet implemented, in which coin holders join the overall process only after some work has been done by POW participants, which reduces the chances of a 51% attack, since a majority holder will not be able to unilaterally control the creation of new blocks.^[26]

How the algorithm works:

1. A POW miner searches for a hash of the appropriate difficulty.
2. The hash found is sent to the network, being not a block itself but merely a first step, a distinctive template needed to create it.
3. The hash, consisting of 256 pseudo-random bits, is interpreted as N numbers, each of which is matched to one satoshi.
4. A one-to-one correspondence is established between each satoshi and the public key of its current owner.
5. As soon as all N owners have placed their signatures on this block, the result is a complete block.
6. If one of the holders is unavailable or is not participating in mining, the remaining miners continue generating templates with various combinations of candidate holders.
7. At some point the required block will have been signed the necessary number of times. The block reward is then split between the POW miner and all N holders.

Proof of Burn

Money is sent to an address that is the hash of a random number; funds at that address are guaranteed to be unspendable, since the probability of finding the keys to it tends to zero. In return, the miner receives a permanent chance of finding a PoB block and receiving a reward for it. Mining in this case is arranged so that the chances of success depend on the number of coins burned. By analogy, burning is like a non-refundable POS deposit, or an investment in virtual hardware for POW mining. From an economic standpoint, this algorithm is better suited to the later stages of a cryptocurrency's development, once most of the money supply has already been generated.^[27]

Proof of Capacity

The Proof of Capacity algorithm (or Proofs of Space) works as follows: mining requires allocating a substantial amount of memory on the computer, after which a large number of large data blocks are created by repeatedly hashing a public key together with random numbers. From the last header of each data block an index is obtained, after which a small piece of the block at that index is selected, a chunk (Chunk). The more memory that is allocated, the more chunks are obtained. The condition that must hold is that the hash of the chunk and the last header must be less than the target. In this way, every megabyte of memory acts as the equivalent of a lottery ticket and increases the chance of success when mining.^[28]

Proof of Research

The Proof of Research algorithm was developed within the GridCoin project in order to direct the computing power of PoW networks toward solving scientific problems on the BOINC platform. Proof of Research simultaneously uses Proof of Work to reward participants for the computations they perform, and Proof of Stake to encourage long-term participation in the project^[29].

Energy inefficiency[

POW-based systems are extremely resource-intensive.

• In 2013, the total computing power spent on POW on the Bitcoin network exceeded, by a factor of 256, the combined power of that year's top 500 most powerful supercomputers in the world.^[30]
• In 2017, fully processing a single transaction in the Bitcoin system required an average of 163 kW⋅h of energy. That much energy could fully cover the needs of a family of three living in a small single-story house for five and a half days. Mining cryptocurrencies on the Bitcoin and Ethereum networks together consumed more energy than the entire population of Syria^[22][23].

See also

• CAPTCHA
• Bitmessage
• Public-key cryptosystem
• One-way function
• Legal status of cryptocurrencies
• Alternative currency
• Digital currency
• Electronic money
• Virtual currency
• Token (cryptocurrency)
• Stablecoin
• Crypto-anarchism
• Online digital currency exchange service
• Blockchain
• Double-spending
• Proof of Identity
• Proof of Space
• Proof of Stake
• Proof of Elapsed Time
• Proof of Stake
• Trust-limited Proof of Activity
• Mining
• Forging
• ICO
• Cryptocurrency bubble
• 2018 cryptocurrency crash
• Smart contract
• Hodl