Digital systems are subject to several types of attacks and abuses against them.
An example, denial of service (DoS), occurs when a server is flooded with false requests to access its services. If the number of dummy requests exceeds the number of requests the server can handle, legitimate users will not be served or will experience delays.
A denial of service attack thus disrupts the regular flow of a server and should be avoided.
Another such attack is e-mail spam, in which an e-mail account is filled with unsolicited e-mails, usually containing advertising or malware.
One possible defence against these attacks is to require the client to provide proof of work. Proof of work could be the solution to a calculation problem, a difficult memory problem, a problem requiring user intervention (such as CAPTCHA). The user can therefore no longer spammer because he is obliged to provide proof of work and if this proof takes time to be made then the attacker can no longer overwhelm the query service.
The problem must be moderately difficult to solve but easy to verify (quick calculation).
A service provider can then pose the problem to anyone requesting the service, and grant access only to users who pass the challenge. This allows the service provider to identify users who are willing to pay the price to enter the service. If the proof of work is well designed, this price will be a minor inconvenience (like a short delay) for legitimate users but an economic deterrent for service attackers as they will spend time there.
Proof of work systems can be implemented according to two protocols:
Challenge-Response: This protocol implies permanent communication between the client and the server. First the client requests the service, then the server chooses a proof of work and challenges the client. The client must then resolve the proof of work and send the response to the server. Finally, the server checks that the proof of work has been correctly performed and then grants the client access to the service. This is the model used, for example, in CAPTCHA. The advantage of this protocol is that the server can adapt the difficulty of the proof of work to conditions, such as the server load.
Solution-Verification: This protocol is asynchronous: solution and verification can be performed at different times. Continuous communication between server and client is not required. First, the client creates a proof of work problem and solves it, this problem should be different each time and chosen by an algorithm for example, the client could use the result of a hash function to generate it. Then the client sends the solution to the server, which checks it and proceeds accordingly.
To secure the blockchain (the transaction database), Bitcoin requires proof of working on blocks of transactions according to the Solution-Verification protocol.
Bitcoin uses partial hash inversion as a proof of work function. Partial hash reversal requires that the hash of a block of transactions matches a certain pattern. The reason to match is that the hash starts with at least a certain number of 0 bits. This is called hash reversal because the proof of work must reverse (i.e. match) a certain pattern in part of the hash. It is important that the hash function is resistant to preimage attack. Otherwise, it would not be difficult, from a computer point of view, to find a partial hash reversal, which would defeat the purpose of the proof of work.
The diagram below shows a partial hash inversion applied to the message “Predya”. The hash function used in the schematic is SHA256^2, Bitcoin hash function. The partial hash inversion in this example requires that the first 12 bits (3 hexadecimal characters in the schema) to be zero.
The free variable to resolve the partial hash is a nunce added to the message. To resolve partial hash reversal, a nonce must be found so that the message hash and nonce correspond to the partial hash, that is, the hash begins with at least three zero characters.
The diagram above increments the nonce until a solution is found. The solution is found in the value of nonce 4207. Although this example starts with a nonce value of 1 and increments it with each combination, there is nothing to prevent trying random nunces.
It is expensive in calculation to solve the partial hash inversion, because many nonce (303 in this exemple) had to be tried before finding a solution. However, it is inexpensive to verify that the work has been done, it requires only one hash test. One of the advantages of partial hash inversion is that the difficulty of the work proof can be easily adjusted by changing the number of 0 bits that makes up the beginning of the hash to be found.