Proof-of-work system

Last updated

A Proof-of-Work (PoW) system (or protocol, or function) is an economic measure to deter denial of service attacks and other service abuses such as spam on a network by requiring some work from the service requester, usually meaning processing time by a computer. The concept was invented by Cynthia Dwork and Moni Naor as presented in a 1993 journal article. [1] The term "Proof of Work" or PoW was first coined and formalized in a 1999 paper by Markus Jakobsson and Ari Juels. [2]

Cynthia Dwork American computer scientist

Cynthia Dwork is an American computer scientist at Harvard University, where she is Gordon McKay Professor of Computer Science, Radcliffe Alumnae Professor at the Radcliffe Institute for Advanced Study, and Affiliated Professor, Harvard Law School. She is a distinguished scientist at Microsoft Research.

Moni Naor Israeli cryptographer

Moni Naor is an Israeli computer scientist, currently a professor at the Weizmann Institute of Science. Naor received his Ph.D. in 1989 at the University of California, Berkeley. His advisor was Manuel Blum.

Markus Jakobsson is a computer security researcher, entrepreneur and writer, whose work is focused on the issue of digital security.

Contents

A key feature of these schemes is their asymmetry: the work must be moderately hard (but feasible) on the requester side but easy to check for the service provider. This idea is also known as a CPU cost function, client puzzle, computational puzzle or CPU pricing function. It is distinct from a CAPTCHA, which is intended for a human to solve quickly, rather than a computer.

Client Puzzle Protocol

Client Puzzle Protocol (CPP) is a computer algorithm for use in Internet communication, whose goal is to make abuse of server resources infeasible. It is an implementation of a proof-of-work system (POW).

A CAPTCHA is a type of challenge–response test used in computing to determine whether or not the user is human.

Background

One popular system, used in Hashcash, uses partial hash inversions to prove that work was done, as a good-will token to send an e-mail. For instance the following header represents about 252 hash computations to send a message to calvin@comics.net on January 19, 2038:

Hashcash is a proof-of-work system used to limit email spam and denial-of-service attacks, and more recently has become known for its use in bitcoin as part of the mining algorithm. Hashcash was proposed in 1997 by Adam Back and described more formally in Back's paper "Hashcash - A Denial of Service Counter-Measure".

X-Hashcash: 1:52:380119:calvin@comics.net:::9B760005E92F0DAE

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

0000000000000756af69e2ffbdb930261873cd71

Whether PoW systems can actually solve a particular denial-of-service issue such as the spam problem is subject to debate; [3] [4] the system must make sending spam emails obtrusively unproductive for the spammer, but should also not prevent legitimate users from sending their messages. In other words, a genuine user should not encounter any difficulties when sending an email, but an email spammer would have to expend a considerable amount of computing power to send out many emails at once. Proof-of-work systems are being used as a primitive by other more complex cryptographic systems such as bitcoin which uses a system similar to Hashcash.

Bitcoin () is a cryptocurrency, a form of electronic cash. It is a decentralized digital currency without a central bank or single administrator that can be sent from user to user on the peer-to-peer bitcoin network without the need for intermediaries.

Variants

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

Proof of Work challenge response.svg
Proof of Work solution verification.svg

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).[ further explanation needed ] A generic technique for reducing variance is to use multiple independent sub-challenges, as the average of multiple samples will have a lower variance.

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

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

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.

List of Proof-of-Work functions

Here is a list of known proof-of-work functions:

Reusable proof-of-work as e-money

Computer scientist Hal Finney built on the proof-of-work idea, yielding a system that exploited reusable proof of work ("RPOW"). [18] The idea of making proofs-of-work reusable for some practical purpose had already been established in 1999. [2] Finney's purpose for RPoW was as token money. Just as a gold coin's value is thought to be underpinned by the value of the raw gold needed to make it, the value of an RPoW token is guaranteed by the value of the real-world resources required to 'mint' a PoW token. In Finney's version of RPoW, the PoW token is a piece of Hashcash.

A website can demand a PoW token in exchange for service. Requiring a PoW token from users would inhibit frivolous or excessive use of the service, sparing the service's underlying resources, such as bandwidth to the Internet, computation, disk space, electricity, and administrative overhead.

Finney's RPoW system differed from a PoW system in permitting the random exchange of tokens without repeating the work required to generate them. After someone had "spent" a PoW token at a website, the website's operator could exchange that "spent" PoW token for a new, unspent RPoW token, which could then be spent at some third-party website similarly equipped to accept RPoW tokens. This would save the resources otherwise needed to 'mint' a PoW token. The anti-counterfeit property of the RPoW token was guaranteed by remote attestation. The RPoW server that exchanges a used PoW or RPoW token for a new one of equal value uses remote attestation to allow any interested party to verify what software is running on the RPoW server. Since the source code for Finney's RPoW software was published (under a BSD-like license), any sufficiently knowledgeable programmer could, by inspecting the code, verify that the software (and, by extension, the RPoW server) never issued a new token except in exchange for a spent token of equal value.

Until 2009, Finney's system was the only RPoW system to have been implemented; it never saw economically significant use.

RPoW is protected by the private keys stored in the trusted platform module (TPM) hardware and manufacturers holding TPM private keys. Stealing a TPM manufacturer's key or obtaining the key by examining the TPM chip itself would subvert that assurance.

Bitcoin-type proof-of-work

In 2009, the Bitcoin network went online. Bitcoin is a proof-of-work cryptocurrency that, like Finney's RPoW, is also based on the Hashcash PoW. But in Bitcoin double-spend protection is provided by a decentralized P2P protocol for tracking transfers of coins, rather than the hardware trusted computing function used by RPoW. Bitcoin has better trustworthiness because it is protected by computation. Bitcoins are "mined" using the Hashcash proof-of-work function by individual miners and verified by the decentralized nodes in the P2P bitcoin network.

The difficulty is periodically adjusted to keep the block time around a target time.

ASICs and mining pools

Within the Bitcoin community there are groups working together in mining pools. [19] Some miners use ASICs (Application-Specific Integrated Circuit) for PoW. [20] Some PoWs claim to be ASIC resistant, i.e. to limit the efficiency gain that an ASIC can have over commodity hardware, like a GPU, to be well under an order of magnitude. In practice, such claims have not withstood the test of time.[ citation needed ]

See also

Notes

1. ^ On most Unix systems this can be verified with a command: echo -n 1:52:380119:calvin@comics.net:::9B760005E92F0DAE | openssl sha1

Related Research Articles

Financial cryptography is the use of cryptography in applications in which financial loss could result from subversion of the message system. Financial cryptography is distinguished from traditional cryptography in that for most of recorded history, cryptography has been used almost entirely for military and diplomatic purposes.

Articles related to cryptography include:

Cryptographic hash function Special class of hash function that has certain properties which make it suitable for use in cryptography

A cryptographic hash function is a special class of hash function that has certain properties which make it suitable for use in cryptography. It is a mathematical algorithm that maps data of arbitrary size to a bit string of a fixed size and is designed to be a one-way function, that is, a function which is infeasible to invert. The only way to recreate the input data from an ideal cryptographic hash function's output is to attempt a brute-force search of possible inputs to see if they produce a match, or use a rainbow table of matched hashes. Bruce Schneier has called one-way hash functions "the workhorses of modern cryptography". The input data is often called the message, and the output is often called the message digest or simply the digest.

In cryptography, a preimage attack on cryptographic hash functions tries to find a message that has a specific hash value. A cryptographic hash function should resist attacks on its preimage.

Provable security refers to any type or level of security that can be proved. It is used in different ways by different fields.

Merkle tree tree in which every non-leaf node is labelled with the hash of the labels or values (in case of leaves) of its child nodes

In cryptography and computer science, a hash tree or Merkle tree is a tree in which every leaf node is labelled with the hash of a data block, and every non-leaf node is labelled with the cryptographic hash of the labels of its child nodes. Hash trees allow efficient and secure verification of the contents of large data structures. Hash trees are a generalization of hash lists and hash chains.

Cryptographic nonce arbitrary number used only once in a cryptographic communication

In cryptography, a nonce is an arbitrary number that can be used just once in a cryptographic communication. It is similar in spirit to a nonce word, hence the name. It is often a random or pseudo-random number issued in an authentication protocol to ensure that old communications cannot be reused in replay attacks. They can also be useful as initialization vectors and in cryptographic hash functions.

Adam Back is a British businessman and cryptographer.

Non-interactive zero-knowledge proofs are a variant of zero-knowledge proofs in which no interaction is necessary between prover and verifier. Blum, Feldman, and Micali showed that a common reference string shared between the prover and the verifier is enough to achieve computational zero-knowledge without requiring interaction. Goldreich and Oren gave impossibility results for one shot zero-knowledge protocols in the standard model. In 2003, Shafi Goldwasser and Yael Tauman Kalai published an instance of an identification scheme for which any hash function will yield an insecure digital signature scheme. These results are not contradictory, as the impossibility result of Goldreich and Oren does not hold in the common reference string model or the random oracle model. Non-interactive zero-knowledge proofs however show a separation between the cryptographic tasks that can be achieved in the standard model and those that can be achieved in 'more powerful' extended models.

Trusted timestamping is the process of securely keeping track of the creation and modification time of a document. Security here means that no one—not even the owner of the document—should be able to change it once it has been recorded provided that the timestamper's integrity is never compromised.

Linked timestamping is a type of trusted timestamping where issued time-stamps are related to each other.

Double-spending is a potential flaw in a digital cash scheme in which the same single digital token can be spent more than once. Unlike physical cash, a digital token consists of a digital file that can be duplicated or falsified. As with counterfeit money, such double-spending leads to inflation by creating a new amount of copied currency that did not previously exist. This devalues the currency relative to other monetary units or goods and diminishes user trust as well as the circulation and retention of the currency. Fundamental cryptographic techniques to prevent double-spending, while preserving anonymity in a transaction, are blind signatures and, particularly in offline systems, secret splitting.

Guided tour puzzle (GTP) protocol is a cryptographic protocol for mitigating application layer denial of service attacks. It aims to overcome the shortcoming of computation-based puzzle protocols, in which clients are required to compute hard CPU or memory-bound puzzles that favor clients with abundant computational resources. Guided tour puzzle protocol can be seen as a form of proof-of-work (POW) protocol.

Cryptocurrency digital medium of exchange

A cryptocurrency is a digital asset designed to work as a medium of exchange that uses strong cryptography to secure financial transactions, control the creation of additional units, and verify the transfer of assets. Cryptocurrencies use decentralized control as opposed to centralized digital currency and central banking systems.

Proof of stake (PoS) is a type of algorithm by which a cryptocurrency blockchain network aims to achieve distributed consensus. In PoS-based cryptocurrencies the creator of the next block is chosen via various combinations of random selection and wealth or age. In contrast, the algorithm of proof-of-work-based cryptocurrencies such as bitcoin uses mining; that is, the solving of computationally intensive puzzles to validate transactions and create new blocks.

Proof-of-space (PoSpace), also called Proof-of-capacity (PoC), is a means of showing that one has a legitimate interest in a service by allocating a non-trivial amount of memory or disk space to solve a challenge presented by the service provider. The concept was formulated by Dziembowski et al. in 2015 and with a different formal definition by Ateniese et al. in 2014.

In computer security, proof of secure erasure (PoSE) or proof of erasure is a remote attestation protocol, by which an embedded device proves to a verifying party, that it has just erased (overwritten) all its writable memory. The purpose is to make sure that no malware remains in the device. After that typically a new software is installed into the device.

Ethash is the proof-of-work function in Ethereum-based blockchain currencies. It uses Keccak, a hash function eventually standardized to SHA-3. These two are different, and should not be confused. Since version 1.0, Ethash has been designed to be ASIC-resistant via memory-hardness and easily verifiable. It also uses a slightly modified version of earlier Dagger and Hashimoto hashes to remove computational overhead. Previously referred to as Dagger-Hashimoto, the Ethash function has evolved over time. Ethash uses an initial 1 GB dataset known as the Ethash DAG and a 16 MB cache for light clients to hold. These are regenerated every 30,000 blocks, known as an epoch. Miners grab slices of the DAG to generate mix-hashes using transaction and receipt data, along with a cryptographic nonce to generate a hash below a dynamic target difficulty.

References

  1. 1 2 3 4 Dwork, Cynthia; Naor, Moni (1993). "Pricing via Processing, Or, Combatting Junk Mail, Advances in Cryptology". CRYPTO’92: Lecture Notes in Computer Science No. 740. Springer: 139–147.
  2. 1 2 3 Jakobsson, Markus; Juels, Ari (1999). "Proofs of Work and Bread Pudding Protocols". Secure Information Networks: Communications and Multimedia Security. Kluwer Academic Publishers: 258–272.
  3. Laurie, Ben; Clayton, Richard (May 2004). "Proof-of-work proves not to work". WEIS 04.
  4. Liu, Debin; Camp, L. Jean (June 2006). "Proof of Work can work - Fifth Workshop on the Economics of Information Security".
  5. How powerful was the Apollo 11 computer?, a specific comparison that shows how different classes of devices have different processing power.
  6. 1 2 Abadi, Martín; Burrows, Mike; Manasse, Mark; Wobber, Ted (2005). "Moderately hard, memory-bound functions". ACM Trans. Inter. Tech. 5 (2): 299–327.
  7. 1 2 Dwork, Cynthia; Goldberg, Andrew; Naor, Moni (2003). "On memory-bound functions for fighting spam". Advances in Cryptology: CRYPTO 2003. Springer. 2729: 426–444.
  8. 1 2 Coelho, Fabien. "Exponential memory-bound functions for proof of work protocols". Cryptology ePrint Archive, Report.
  9. 1 2 Tromp, John (2015). "Cuckoo Cycle; a memory bound graph-theoretic proof-of-work" (PDF). Financial Cryptography and Data Security: BITCOIN 2015. Springer. pp. 49–62.
  10. 1 2 Abliz, Mehmud; Znati, Taieb (December 2009). "A Guided Tour Puzzle for Denial of Service Prevention". Proceedings of the Annual Computer Security Applications Conference (ACSAC) 2009. Honolulu, HI: 279–288.
  11. Back, Adam. "HashCash". Popular Proof-of-Work system. First announce in March 1997.
  12. Gabber, Eran; Jakobsson, Markus; Matias, Yossi; Mayer, Alain J. (1998). "Curbing junk e-mail via secure classification". Financial Cryptography: 198–213.
  13. Wang, Xiao-Feng; Reiter, Michael (May 2003). "Defending against denial-of-service attacks with puzzle auctions" (PDF). IEEE Symposium on Security and Privacy '03.
  14. Franklin, Matthew K.; Malkhi, Dahlia (1997). "Auditable metering with lightweight security". Financial Cryptography '97. Updated version May 4, 1998.
  15. Juels, Ari; Brainard, John (1999). "Client puzzles: A cryptographic defense against connection depletion attacks". NDSS 99.
  16. Waters, Brent; Juels, Ari; Halderman, John A.; Felten, Edward W. (2004). "New client puzzle outsourcing techniques for DoS resistance". 11th ACM Conference on Computer and Communications Security.
  17. Coelho, Fabien. "An (almost) constant-effort solution-verification proof-of-work protocol based on Merkle trees". Cryptology ePrint Archive, Report.
  18. "Reusable Proofs of Work". Archived from the original on December 22, 2007.
  19. Overview of the Bitcoin mining pools on blockchain.info
  20. What is an ASIC miner on digitaltrends.com