Proofs of Useless Work — Can we solve Bitcoin’s energy waste?
In our latest paper, Maya Dotan and I show that Proof of Work (PoW) systems can never be used to solve meaningful problems in trustless systems. As the full paper that can be hard to read for the everyday crypto-enthusiast, this blog is here to make this knowledge accessible to readers with just a basic understanding of cryptocurrencies.
In this post, we will examine one of the most common ways to overcome the huge waste of resources that are required in Bitcoin’s protocol. We define a wasteless process as a process that is Secure, Efficient, and solves User Uploaded problems. We show that the “types” of problems that could be used under these constraints are extremely strict. This implies that unless more assumptions will be made — we’re screwed. 😧
Recap — Bitcoin’s Mining Mechanism
Cryptocurrencies (such as Bitcoin) are distributed currencies which use a special data structure called a blockchain. A Blockchain is an appendable list of blocks (i.e. data with a specific structure), and a transaction is valid only upon being included in a block. Security in Bitcoin translates to a consensus across all users regarding the blockchain.
Satoshi Nakamoto’s consensus rule determines that the longest chain is the rightful one, and thus to achieve the above security, we should enforce that blocks will be mined rarely.
In Bitcoin, mining works as follows: miners (people who run the mining procedure) guess binary strings, and try to find a string s that holds SHA256(s) < D (for some D that gets updated in order to keep the mining rate constant). Since SHA256 is believed to be hard to invert, and D is very small, this ensures blocks are created rarely, as needed for Satoshi’s consensus. As you can guess, huge amounts of resources go to waste during that process (According to this site it is equivalent to the energy consumption of Switzerland).
What is Waste?
Bitcoin Uses electricity to keep the system secure. In this regard, the electricity is not wasted, rather it is used to secure the system against adversaries. However, the fact remains that the computations currently being performed by Bitcoin miners have no other merit except being “hard”.
Our definition of wasteless problem solving is consists of three parameters: (1) Efficient, (2) Secure, and (3) User Uploaded:
The first two properties are clear: the algorithm used by the mining process must be the most efficient algorithm, and the process should uphold the standard notions of cryptocurrencies security (otherwise no one will use it).
In addition, we want the mining process to execute calculations instead of an external system, so we demand that the problems that we will solve should originate from the users.
We utilize a fee mechanism in which the uploading users pay to solve the problems, and the system will solve only the most profitable problems. If users are willing to pay to solve problems and are willing to compete on the price with other users, then the market forces will ensure that we will solve problems that would be solved anyway. Neet!
Only specific Functions!
Jumping to our final results, we show that the above three properties imply restrictions on the set of problems that the system could solve.
For example, one of the required properties is that the miners should be able to “prove to the system” that they indeed tried to solve problems.
The proof idea is simple: otherwise, a malicious miner will not try to solve them, which can lead to either: [1] if the honest miners do solve the problems, then this is a security risk (due to imbalance of power) or [2] if the honest miners do not solve the problems, then the system is in waste.
At this point, it is interesting to remember this paper, which states that if there is some special trusted hardware that can prove the above, then this is a “happy case”- all problems can meet our analysis. Unfortunately, this requires special hardware, which keeps being hacked [1], [2], etc.
Our next step was to discuss problems in which the proof that the miner supplies is the output of the problem. This is an unhappy case, and Theorem 2 (section 3.3) proves that the types of allowed problems are only one-way functions. This means that we can’t for instance hope to solve general NP-problems, only problems in which “every case is the hardest case”.
So What Now?
At the end of the paper, we suggested a small change to the Bitcoin protocol that allows users to upload problems and solve them. Unfortunately, we must hard-code the specific allowed functions (for example, they can only ask for “trimmed output” of SHA256), and we assume that there are “enough” problems — otherwise, we will waste energy in exchange for security.
This is a first step toward the ultimate goal of reducing the waste of PoW cryptocurrencies.
We believe that further research can sharpen the result. In particular, if more strict measures can enforce honest behavior (such as trusted hardware etc.), the family of allowed functions can be greatly increased.
The full paper can be found here: https://arxiv.org/pdf/2007.01046.pdf
