Useful Proof of Work (PoW) – Energy Preserving Cryptocurrency PoW Protocols

Proof of Work (PoW) protocols was first presented by Cynthia Dwork and Moni Naor via an article that was published in 1993. The term “Proof of Work” (PoW)was first used by Markus Jackobsson in a paper that was published in 1999 that described the use of PoW protocols to ensure that a specific amount of energy was spent to do a task in a simple verifiable way. In most cases, PoW protocols force malicious users to perform a large computing workload, thus shielding against email spamming, denial of service attacks (DDoS) and most importantly, double spending attacks on cryptocurrency blockchains such as bitcoin. Unluckily, current PoW schemes are often irrelevant to the task they are associated with so that the work done is not technically useful in completing the task. Even more, the computing work was done and energy consumed is literally not useful for anything other than verifying that work had been done.

A recently published paper proposed PoW protocols that are based on a variety of computational problems such as 3SUM, Orthogonal Vectors, All-Pairs Shortest Path and any other problem that reduces to the previously mentioned problem types (including deciding which graph property is statable as first order logic). In other words, these PoW protocols won’t waste energy, instead, they are useful in solving a myriad of computational problems that are of real practical interest. The proposed PoW protocols are based on delegation of the evaluation of low degree polynomials that originate from studying the average case fine grained complexity. The authors of the paper proved that, apart from being hard on the average (based on worst case hardness assumptions), evaluation of the polynomials is a task that cannot be amortized across various instances. These useful PoW protocols can help in benefiting from the large amount of energy wasted with PoWs that are utilized on a massive scale, as is the case with bitcoin.

Why Do We Need Useful PoWs?

Like we mentioned earlier, the energy consumed throughout fulfillment of bitcoin’s PoWs protocol is literally wasted because it is useful for nothing other than proving that the work, solving the mathematical puzzle, had been successfully accomplished. Accordingly, PoWs are a waste of a large amount of resources and electrical energy, which has been described in many instances as an “environmental disaster”. The earliest attempts to solve this problem were in the form of two altcoins; Primecoin and Permacoin. Primecoin proposed a PoW protocol whose outcome aids in building of chains of prime numbers. Permacoin proposed a PoW protocol that repurposed bitcoin mining resources to store archival data in a decentralized manner on basis of Proofs of Retrievability (thus users invest not only their processing power, but also their storage capacity).

The Usefulness of the Proposed PoW Protocols:

The proposed PoW protocols included Orthogonal Vectors, 3SUM, All Pairs Shortest Path (APSP) along with a myriad of other problems that can be presented as low degree polynomials whose evaluations could be efficiently verified and so fit into the protocol assuming their hardness.

Furthermore, any other problem that can be reduced to any of the hard problems can also be part of the proposed PoW protocol for delegating instances of this problem. Accordingly, the PoW protocols achieve hardness and non-amortizability that match the worst-case hardness of any of these problems. As such, many types of graph problems have been proven to reduce to one of these problems, and particularly, the task that include determining whether a given graph has a specific property for any property that could be written in first order logic can be reduced to Orthogonal Vectors. Consequently, the achieved useful PoW protocols are based on the hardness of Orthogonal Vectors and their generalizations so that any given problem that could be phrased, in the form of a first order graph property, can be delegated.

The proposed useful PoW protocols can be considered a delegation of computation scheme for an unlimited type of practical problems while preserving their PoW characteristics that shield against activities including spam and double spending. Furthermore, the required work can be distributed among the community, similarly to bitcoin mining pools, and can be done is a way robust to Byzantine failures as well as noise.