Proof of Work (Pow): It is an economic measure to deter service abuses by requiring some work from the service requester, usually processing time by a computer. If you are requesting a service, you have to show the service provider that you have spent significant interest in the service you are requesting.
The Proof of Work concept was there earlier in one or another form. We will read about how the Proof of Work mechanism was proposed to combat email spammers.
The Broad Idea of this Proof of Work is that every service requester must spend some time on the service that he or she is asking for before actually requesting the service. That way, it shows you from the economic perspective that the service requester has some interest in the service. It also ensures that the services provided to that service requester will genuinely accept that service and will not use it maliciously.
This idea is actually an old idea, proposed by Dwork and Naor in 1992 in an interesting paper published in a Cryptology conference to combat junk emails. They have shared that you have to do some work to send a valid email, and this way, the spammer will be discouraged from sending junk email.
Proof of Work (PoW) Features
The work must be moderately hard but feasible for the service requester side. Whereas at the service provider side, the work must be easy to check or validate. That way, the service requesters will get discouraged to forge the work because they have to spend a significant amount of time to complete that particular work.
How Cryptographic Hash as the PoW?
The use of puzzle friendliness property of a cryptographic hash function as the “Work.”
Given X and Y, find out k, such that Y = Hash(X||k). However, it is difficult but not infeasible to find such k. If such k has been found, then it can be easily verified by the challenger. The best algorithm to find k is to apply a certain kind of brute force mechanism or random search over the possible values. This particular “Work” is difficult to find but easier to validate.
This work was proposed by Adam Back in 2002 and used Hashcash as a Proof of Work (PoW). This Hashcash can be added with an email as a goodwill token. The Hashcash will be generated by legitimate email senders, whereas the spam email generators get discouraged as the generation of the Hashcash is a time-consuming process. But the spammers are very much interested to send repeated emails one after another by some auto-generated script. If they have to wait for a certain amount of time to send every email, the spammer will not benefit from that.
Hashcash Proof of Work
Hashcash will be embedded after textual encoding in the email header as a stamp, and this proves that the sender has spent a modest amount of CPU time calculating the stamp before sending the email. It is improbable that the sender is a spammer because the spammer is very much interested to send repeated emails one after another by some auto-generated script.
The receiver can verify the Hashcash stamp very easily. So, any change in the header requires a change in the Hashcash value, and brute force is the only way to find the valid Hashcash.
Format of Hashcash Stamp:
- Version: – Version of the protocol.
- Hashed code format length: – As a challenge, (N) zero bits must be there with the newly generated Hashcash.
- Date: Date on which email is created or sent.
- Resource: Email Address.
- Optional extension: Additional option.
- String of random characters: Unique for every new email to prevent replay attack.
- Counter: It keeps the Nonce value.
Example:
In this scheme, the challenge is given to the email sender to find the Hashcash value start with N zero bits. The email sender has to find out the hash value where the first N bits must be 0. There is a counter parameter that stores nonce value. During verification, the receiver uses the nonce value and generates Hashcash to verify the Hashcash stamp.
Y = Hash(X||k) where k is the nonce, supplied by the sender in the email header and X is the email header, and Y is the HashCash value or stamp.
Complexity Analysis of Hashcash PoW scheme
In this scheme, the challenge is finding the 160 bits hash value from an arbitrary input data length, i.e., Email Header, with a nonce of 20 bits. The nonce of 20 bits implies that the first 20 bits must be zero as an output or Hashcash or stamp for email header.
On average, the sender will have to try 
hash values to find a valid header stamp, as the hash value is 160 bits, so the hash function generates 1 hash value out of a total 
possible values. However, 20 zero bits at the beginning imply 
possible valid values that satisfy this criterion. The chance of randomly selecting a header with 20 zero bits at the prefix is 1 in .
Summary
We have seen the general “Proof of Work” concept and how it is used to combat email spammers: the Hashcash mechanism and complexity analysis of the Hashcash scheme.
References
- NPTEL lecture series on Blockchains Architecture, Design and Use Cases by Prof. Sandip Chakraborty, IIT Kharagpur.
221 total views, 1 views today
