Proof-of-work system

From CryptoWiki
Jump to: navigation, search

Proof-of-work, POW — is the way to protect the system from DoS attacks and some other types of attacks which is founded on solving some tasks by client with defined difficulty (POW-task)where the solution could be checked easily by server. Such schemes are known as client puzzle (CPP), computational puzzle or CPU pricing function.

Back to contents

Contents

The idea of CPP

The idea of CPP is to require that all clients connecting to the server properly solved mathematical puzzle to establish the connection if the server is under attack. After solving a puzzle client returns solution to server which quickly checks and allows to connect or disconnect. The puzzle consists of a simple and easily solvable problem, but it requires a certain amount of computation on the client side. True users will experience only minor computational cost and not true users will experience long delays: those customers who are trying to simultaneously install a large number of connections will not be able to do this because of the computational cost. This method is promising in the fight against some types of spam, as well as other attacks, for example, such as a denial of service.

POW classes

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

  • Challenge-response – protocols assume a direct interactive link between the requester (client) and the provider (server). The provider chooses a challenge, say an item in a set with a property, the requester finds the relevant response in the set, which is sent back and checked by the provider. As the challenge is chosen on the spot by the provider, its difficulty can be adapted to its current load. The work on the requester side may be bounded if the challenge-response protocol has a known solution (chosen by the provider), or is known to exist within a bounded search space.

Challenge-response.png

  • Solution-verification - protocols do not assume such a link: as a result the problem must be self-imposed before a solution is sought by the requester, and the provider must check both the problem choice and the found solution. Most such schemes are unbounded probabilistic iterative procedures such as Hashcash.

Solution-verification.png

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

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

The underlying functions used by these schemes may be:

  • CPU-bound where the computation runs at the speed of the processor, which greatly varies in time, as well as from high-end server to low-end portable devices.
  • Memory-bound where the computation speed is bound by main memory accesses (either latency or bandwidth), the performance of which is expected to be less sensitive to hardware evolution.
  • Network-bound if the client must perform few computations, but must collect some tokens from remote servers before querying the final service provider. In this sense the work is not actually performed by the requester, but it incurs delays anyway because of the latency to get the required tokens.

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.

Implementation and usage of POW

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

  • Integer square root modulo a large prime
  • Weaken Fiat–Shamir signatures
  • Ong–Schnorr–Shamir signature broken by Pollard
  • Partial hash inversion This paper formalizes the idea of a proof of work (POW) and introduces "the dependent idea of a bread pudding protocol", a "re-usable proof of work" (RPOW) system as Hashcash
  • Hash sequences
  • Puzzles
  • Diffie–Hellman-based puzzle
  • Moderate
  • Mbound
  • Hokkaido
  • Cuckoo Cycle
  • Merkle tree based
  • Guided tour puzzle protocol

Hashcash

An example of POW-protection is the system Hashcash, which uses a hashing partial inversion when sending e-mail. To calculate the appropriate header requires about 252 hash computations that need to be recalculated for each shipment. The need for continuing conversion makes sending spam very resource-intensive, but does not create obstacles to send regular mail. In addition, for validation code calculated using a single calculation of the SHA-1 to a pre-prepared label.

Hashcash - friendly technology to be used, according to the authors, in conjunction with other anti-spam technologies to increase the overall efficiency of such a complex system. To improve the efficiency of such a system is necessary that after the letter hashcash other anti-spam technologies (for example, processing by keywords) passed this message because already guaranteed maximum reliability. In turn, for you as the sender use hashcash guarantees your passing messages through other filters. Of course, spammers can also use hashcash, but send out mass emails will not be able, as to generate each hashcash-mark takes some processor time. You as an ordinary user with a desktop computer or a laptop, there is no need to worry that your correspondence will be sent hours or days, as you do not send out "a lot" of letters, your mail before sending delayed for a maximum of a few seconds even on old hardware. However, it will stop spammers: they want to send more than 10,000 messages per minute over DSL channel paid by stolen credit card before an account closed down. One reason for the elusiveness and effectiveness of mass mailings - the shortest period of time required for implementation, and this is taken advantage of by spammers.

One marker may be used for a plurality of receivers because each mark is valid only once and only for a single recipient. Elevation similar signature that identifies the recipient. If the mark is generated for joe@foo.com, then all recipients other than joe@foo.com rejected the letter because it actually is not addressed to them. Spammers can not change the destination address for which the mark was generated because the label itself is generated based on the address of the recipient. If you just change the field 'To:' letters, the message is simply not pass verification stage label.

It is also not possible to use the same mark that would send numerous letters to a single address: to perform this rule, each recipient is saved in a database, if a new message is received with a label already it is rejected.

Spammers can not use the "old" mark, which have been generated from the previously and have never been used because hashcash-markers have a shelf life. On this there is no way spammers generate labels for all the spam list for earlier spending a week or two, and then send letters to a few tens of minutes over DSL channel. Such letters will be rejected, because hashcash-markers have expired.

RPOW as e-money

Computer scientist Hal Finney built on the proof-of-work idea, yielding a system that exploited reusable proof of work ("RPOW"). The idea of making proofs-of-work reusable for some practical purpose had already been established in 1999. 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 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 web site 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. 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; RPOW is protected by the private keys stored in the TPM hardware and manufacturers holding TPM private keys. Hackers who steal a TPM manufacturer key, or anyone capable of obtaining the key by examining the TPM chip itself, could subvert that assurance. Bitcoins are "mined" using the Hashcash proof-of-work function by individual nodes and verified by the decentralized P2P bitcoin network.

Other cryptocurrencies have used different hashing algorithms, as well as prime chains as proof of work.

Attacks

Comparison of safety and problems with Proof of Stake

In this section Bitcoin will be primarily mentioned because it is the best example to explain the concept of attacks on POW protocols. Most problems with PoS-protocols stem from the fact that the protocol does not know anything other than the appropriate blockchain. The system works prove the presence of external factors, namely the amount of computational work it takes to find a solution. In systems with acknowledgment share no factors blockchain reinforcement in the physical world; so intuitively evident that the agreement on the basis of PoS allow more kinds of attacks.

The problem of "nothing is at stake"

Naive algorithms confirm share, based only have a serious problem: if there has been branching blockchain (whether accidentally or intentionally) rational behavior for all users pollock blocks on both branches. On the evidence of the algorithm works, such behavior is irrational. Sharing resources in different branches, miner reduces the probability of finding a block on each of them; the optimal strategy in PoW system - always working on one branch. The algorithm confirmation share, in contrast to the PoW, the probability of finding a block does not decrease if the user tries to work on several branches blockchain. Therefore, rational behavior in PoS-IMC Network is working on all the branches of which the user knows. Worse, naive confirmation none satisfies 2: In some circumstances, the best strategy may be working on an intermediate blockchain. This problem makes it easier to double expenditure or other types of attacks, based on branching blockchain. If users believe that the attack may succeed, they will support it, working on blockchain's attacker. While users with large amounts of currencies will resist the attacks, carried out by the branch because they are afraid of losing their money, the attack has a good chance to be successful, if the currency is distributed evenly among many users.

There are several proposed solutions to the problem of "nothing is at stake"; Algorithms delegated PoS is not usually affected by this problem, because at stake is a means Minter blocks; These funds will be confiscated if Minter will take part in the attack on the system.

The problem of the initial distribution

In systems using PoS, there is always the danger that the initial holders of coins will not be interested in spending their coins, as their balance directly contributes to their well-being. The Bitcoin and other PoW-systems technology early adopters are in the same conditions as other users: To Maina coins, they need to constantly improve their equipment and optimize resource usage. The PoS-system user who has purchased 10% of the total number of coins, the system needs only to open (e.g., $ 1,000) has an advantage over users with the same means at a time when the system is gained popularity and 1,000 $ ekvivaletno 0 01% of all coins. To prevent this situation, the implementation of PoS use additional algorithms for the initial distribution of the currency; for example, Peercoin Ethereum and use evidence of work to create new coins.

Attack from afar

In a system with PoS-agreement, an attacker with sufficient computing power can try to build an alternative blockchain, starting with the first unit. The PoW-system, this attack prevents the enormous computing power needed to build blockchain from scratch; At the same time, solve this task in real-PoS system. Since the attacker can move freely in the blockchain coins, which he builds his much larger dimension of the search space; Thus, this type of attack may be preferable to build an alternative to the recent blockchain branch point. The possibility of attack is stored in delegated confirmation proportion where it can be carried by a majority of delegates.

To prevent an attack from a distance, the protocol can set the maximum allowable depth of the branching point. For example, in Nxt user can not take alternative blockchain if it differs from existing over the past 720 blocks (corresponding to 12 hours). However, this restriction does not solve the problem of new users. When a user joins the network, it sees several blockchains without prior knowledge of their authenticity. If the attacker is preferable blockchain valid under the protocol, new users will receive it. One way to find out what the correct blockchain - download it from a trusted source; At the same time, it makes the system more centralized and makes confidence factor. However, blockchains downloaded from trusted sources are used in virtually all existing PoS-systems.

Attack by bribes

In this attack, the attacker tries to double-spend their funds as follows:

  • buy any goods or services;
  • wait until the transaction containing the payment will be regarded as confirmed by the seller;
  • Declare a reward for the construction on the basis of truncated blockchain, do not include the payment in question. For example, if the seller is waiting for the six confirmations, the attacker starts with blockchain without past six blocks. An attacker can offer a greater reward users who work only on blockchain attacker without it, blockchain attacker never catch up with the right).
  • An attacker can continue to pay bribes even if it was blockchained and the right will be the same length to get the support of the majority holders cryptocurrency.

Members participating in the attack, nothing to lose, if the attack fails; to attack the attacker will be profitable, if the total number of bribes paid less the cost of goods. For comparison, in the PoW-system, such an attack requires the attacker by bribing the majority of miners. Besides, in this case losing miners resources spent on calculation if the attack fails, then the amount of tricks is likely to be high. The attack is not feasible in a system with delegated PoS.

Attack accumulation age coins

This attack refers to Peercoin and other systems used by the age of coins instead of wealth as a measure of the proportion of the user. In the first version Peercoin, age coin was limited. This meant that the attacker waited long enough, can accumulate enough coins to actually master the network. For example, an attacker with a five per cent of all coins can divide your money into multiple outputs, and wait until the age of his UTXO would be 10 times higher than average. After that, the attacker can open several units in a row with a high probability (if small UTXO separately) to implement dual expenditure or other malicious actions. If you have multiple users attempting to carry out this attack, it would have led to a serious deterioration of network quality. In later versions of the protocol Peercoin, age UTXO limited to 90 days. Similarly, the age of the coin limited Novacoin and BlackCoin. Though limiting and does funded attack is much less likely, it significantly reduces the advantages of age coins.

Attack by precomputing

Let A Minter block Bh a height h; If A has significant computing power, it may affect the hash block Bh, to be able to decide the next block Bh + 1, for example, adding a new transaction in Bh. To reserve Bh + 1 for yourself, A browse all user profiles and checks whether the condition (2) for each of the allowed values of the time t. If the hash Bh «bad», that is, calculations show that the next block will be settled by another user, the attacker changes the parameters of an inserted transaction and try again. This can be exploited to build a long chain of blocks to collect more fees and try to spend double the spending (building a chain of secret and then releasing all the blocks at once to overtake the right blockchain with the transaction, that an attacker wants to pay).

Efficacy predvychislitelnoy attack depends on the proportion of the attacker, and the total number of users or UTXO system. The PoW-system, this attack is virtually impossible, since to generate a block with a "good" hash is much more complicated than just the correct unit. Similarly, in a system with the deleted sequence PoS Signer blocks does not depend on the properties of the final block; thus, DPoS approval is resistant to predvychislitelnym attacks.

Sybil attack

An attacker could try to fill the network under his control nodes, and other users can only connect to the blocks created for fraud. How this can happen:

  • Offensive block transactions from other users, disconnecting you from the general network.
  • The attacker connects you only to the blocks that makes it a separate network. As a result of this transaction will occur, which will forward the money again (double-spending).
  • An attacker can see all your transactions with the help of special programs.

DoS attack

Sending a large number of "garbage" data node that handles the transaction may complicate its work. Bitcoin network has built-in protection against attacks like "denial of service", but today this type of attack, each time becoming more and more difficult to block.

Comparison with the proof of the stake

Based on the PoW cryptocurrency somewhat prone to double spending; Nevertheless, the possibility of a successful double spending gradually decreases as the number of transaction confirmations and strongly depends on the number mayningovyh capacity that has the attacking. To reduce the risk of double spending, sellers usually wait a certain amount of evidence. In addition, there are mechanisms to reduce risks in the fast payments.

Types of attacks common to PoW and PoS - it is a denial of service (born. Denial of service, DoS) attacks, and Sybil. DoS-attack aims to interrupt the normal operation of the network by overflow nodes. For example, an attacker can fill the net transactions of low cost, as it happened during a large-scale network fludatake Bitcoin in July 2015. In the event of an attack Sybil attacker undermine the operation of the network, creating a significant number of nodes behave incorrectly. The degree of exposure to network DoS-attacks, and Sybil attacks depends not only on the type of negotiation used in the network, but the details of the network protocol. There is no intrinsic properties, which would make PoS less sensitive to these attacks than PoW.

One of the few attack vectors, especially for evidence of coordination work is selfish Mining (Eng. Selfish mining). When selfish Mining attacker publishes selectively blocks to the computing resources of other miners have been wasted. As in the case of matching PoS expensive resources are not involved in the creation of the blocks, this attack is not effective for PoS cryptocurrency. On the other hand, there is no evidence, that the egoistic Mining ever been successfully used in the bitcoin; Some studies argue that the description of the attack is based on incorrect assumptions.

To match with PoW exposure to attacks can be predicted based on the total capacity of the system is hashed. In the case of PoS-systems, there are no equivalent measures "state of health" of the network:

  • if the currency of evenly distributed between users, the system is susceptible to attacks based on branching blockchain;
  • if there are users with large portions, they can undermine the work of the network (for example, applying to transactions censorship).

POW modifications

Hybrid approval PoW / PoS

Some cryptocurrency using confirmation share, solve the problem of the initial allocation of funds by applying a limited version of the proof of the work to increase the monetary mass; Examples of such currencies are Peercoin and Novacoin. Hybrid coordination of works by creating two types of valid blocks which satisfy specific conditions PoW and PoS implementations.

The main alternative to the hybrid agreement - fully pre-established stock exchange (as in Nxt). Solution PoW- and PoS-blocks divided in time, using a Ethereum. Currently Ethereum uses only proof of work; introduction of PoS-approval is scheduled for the future, when the system becomes more mature.

Hybrid PoW / PoS-approval resistant against attacks from a distance, provided that the safety of the system provides sufficient capacity is hashed. Turning PoW-blocks blokcheyn also helps protect the system against the other attacks described previously. However, since the confirmation of the proportion is generally administered as an alternative to the proof operation, the combined system with time refuse PoW completely or in any case reduce its role in the system.

Slasher

Slasher Hybrid PoS / PoW-matching algorithm described Vitaliy Buterin (Vitalik Buterin), one of the architects Ethereum. Unlike other hybrid algorithms for generating blocks Slasher used solely proof job; but each block is validated as a PoW, and PoS.

Blocks are created using the proof work. Rather than include coinbase-transaction for an award for solving block Miner includes a block number hash (n) for some large natural number n. This number serves as a proof of mining; miner can take posited him the award for the block by creating a transaction, opening n. Reward Mining closed at 100 units and is limited in time: the award for the block at the height h can be achieved by the transaction recorded in one of the blocks with a height h + 100, h + 101, ..., h + 900. The average time between the creation of the blocks is 30 seconds.

To create a valid block, it must be cryptographically signed. On average, each unit can be signed by 64, and the likelihood of becoming a subscriber is proportional to the amount of funds held by the user. To determine the correct blokcheyna Fork used when the total number of signatures. By signing the unit, the user receives an award, closed for the next 1000 units. The award for the signature is higher than the reward for Mining, in order to prevent an arms race among the miners.

To combat Fork blokcheyna Slasher uses a mechanism similar Tendermint. If the user sees several blocks of the same height, signed by the same validator, a user can post a transaction the two signatures. If this transaction is included in the unit before the award of the unit will be available for use by unscrupulous validator 33% reward is paid to the user detect deviation from protocol, and the rest destroyed.

Implementation confirmation proportion used in the Slasher, to a large extent prevents the short forks blokcheyna. In fact, the vulnerability to short-term PoS attacks stems from the following observation. The PoS model, the probability to create a block for each of the competing circuits are independent from each other, since they depend on the last block hash chain. For users of the system it makes sense to try to create blocks based on each circuit, as this increases the expected reward. On the other hand, the likelihood of becoming Slasher validator unit is determined with a large time interval and the same for all circuits, if they are relatively small. Thus, users have no reason to support the fork blokcheyna because they know in advance whether they will sign the blocks in the future. For users do not have to maintain multiple branches blokcheyna if they do not have confidence that the fork will last more than 2000 units.

Since Slasher uses proof of work to create blocks attacks from a distance it requires substantial computing power. Slasher This gives significant advantages over models delegated PoS, which do not use the proof of work (for example, BitShares).

Glossary

Bibliography

Перейти к списку литературы или базе данных публикаций по разделу "Наименование вашего раздела".

Вернуться к оглавлению

Practical exersice

PoW:
File:PoW example c- Kryachko.zip Kryachko I. V, 2015