With headlines proclaiming that Bitcoin, as a result of its Proof of Work consensus algorithm, consumes more electricity than Switzerland, the incentive for researchers to find more environmentally-friendly alternatives has become even more apparent. In their 2016 research paper, “Simple Proof of Space-Time and Rational Proofs of Storage”, Tal Moran and Ilan Orlov propose just this.
In the paper, the authors present an extension to the Proof of Space (PoS) consensus algorithm called Proof of Timespace (PoST). The proposed PoST aims to improve on its predecessor Proof of Space and replace the high energy-consuming Proof of Work consensus algorithm with a scalable, energy-efficient method.
Proof of Work
The Byzantine Generals’ Problem is a well-known allegory in computer science used to exemplify the issue of attempting to reach consensus in a group of unknown and, possibly, malicious actors. Satoshi Nakamoto solved this with the Proof of Work (PoW) consensus algorithm — a structure where miners compete to solve a hash puzzle. Here, the winner receives bitcoins for their solution and their block is subsequently published on the blockchain.
Although highly effective at what it was designed to do — allowing a group of unknown agents to reach consensus sustainably, the competitive element of PoW means that all participants consume energy while only one is rewarded. Additionally, there is a built-in difficulty adjustment complexity, which means that the difficulty of the hash puzzles increases in correspondence with the computational power used. In anticipation of an increase in the cryptocurrency’s popularity, these two factors pose significant environmental concerns.
While the Proof of Work method was a stroke of genius that gave rise to a digital store of value and an entirely new asset class, its wastefulness in terms of energy usage hasn’t gone unnoticed. Although some claim that this use of energy is necessary for the system to work, numerous researchers and computer scientists have set out to find a more environmentally-friendly consensus algorithm.
A new type of “work”
In their paper, Moran and Orlov introduce the Proof of Spacetime, a new consensus algorithm that uses a proof of resource payment scheme. They believe it to be a scalable and energy-efficient alternative to the commonly-used Proof of Work scheme.
Proof of Work operates on the basis that participants must submit, or pay with, “work” before they can add a block and receive the reward. This “work” entails submitting computing resources to Proof of Work network, making CPU the payment. In the proposed PoST consensus algorithm, two different resources can be “spent” by network participants:
1) Work, which refers to processing power, or a unit of CPU expended, similar to what Proof of Work is based on.
2) Storage or “spacetime”, which can be described as filling a specified amount of storage for a specified period. During this period, the storage cannot be used for anything else. As “work” in PoW, spacetime (PoST) is directly convertible to cost.
The key to the PoST consensus algorithm is that participants prefer storage over computing, which requires much less energy. Important here is rationality, which refers to the rational preference of participants to use storage over computing as it minimizes costs and maximizes profits. For PoST to work, the consensus structure must convince rational “provers” to use storage rather than work, especially in the context of a cryptocurrency where profit is the main incentive.
Proof of Space
The foundation of PoST can be traced back to Proof of Space (PoS), a consensus algorithm that was conceptualized in 2014. PoS is very similar to PoW; the key difference is that instead of using computation as “work”, storage is used. In PoS, a participant reserves a specified amount of space and sends this information to the verifier. By reserving this space, the participant proves a legitimate interest in participating in the network.
While this may seem like a viable replacement of PoW, the authors found a fundamental problem — unlike computational power, space can be reused. This means that participants can generate multiple proofs for no additional costs. Moreover, based on the parameters of PoS, it is economically rational for a participant to choose computation over space when the cost of storage is greater than the cost of computation, thus leading to yet another PoW system.
Proof of Spacetime
To solve these problems, Moran and Orlov introduced the Proof of Spacetime consensus algorithm. The basic work is very much the same as PoW and PoS, namely that participants compete to get rewarded based on the proof they submit to the network. However, in the case of PoST, this work is both computation and spacetime, where the former can be stored in the latter.
Proving that a participant has used a lot of space for a computation doesn’t suffice as it would be rational to keep on reusing the space and continue computations, thus still using high amounts of electricity. Instead, spacetime is measured, which is a specified unit of data storage reserved for a specified amount of time.
A participant in the network, or prover, has to convince the verifier that spacetime has been spent to be able to add a block and receive the accompanying reward. Each prover has to generate data that must be stored individually. To ensure that this data is cheaper to store than to generate, the stored data is generated through a Proof of Work. Compared to complete Proof of Work, PoST requires less energy because storage is added to the equation. In essence, PoST is a consensus algorithm that incorporates a trade-off between computational resource and spacetime, instead of a sole focus on CPU. Through this, an economically-rational user, based on current cost conditions, will opt to use spacetime resources over CPU. To ensure this preference remains the rational one, an automated mechanism for adjusting parameters is also proposed.
In PoST, a prover can decide, arbitrarily, on the composition of computational work and spacetime, as long as the spent resources are enough to meet the requirements. This means that the prover can have spent a specific amount of CPU, spacetime, or a combination of the two as proof of their eligibility to add a block and receive the reward. According to the authors, if the parameters are set correctly and the incremental difficulty adjustment works accordingly, this leads to rational provers preferring spacetime over computational work.
Incremental difficulty adjustment
One of the key features of the Bitcoin protocol is its difficulty adjustment, where the difficulty of solving the hash puzzles adjusts in relation to the total computational power used by the network to solve the puzzle. The more computational power, the higher the difficulty and vice versa. This market dynamic is also applied to PoST, albeit with several tweaks. Alongside computational power, the consensus algorithm also takes storage into account. This is referred to as the incremental difficulty adjustment.
The incremental difficulty adjustment is an automatic market-based mechanism that ensures that provers will prefer storage over computing and adjusts difficulty based on the cost of storage. The difficulty, in this context, refers to the period over which data is stored, so increasing difficulty means extending this period. As a result, the potential increase in the price of storage can be offset, maintaining the targeted preference for storage over computation.
Additionally, users are incentivized to honestly report whether there are storing data or computing it, and this information can be used to set the difficulty dynamically. In PoST, users have two options to generate proofs, storage-based and computation-based. By adding a minor incentive for computation-based solutions, the protocol can track users that use computation and adjust the difficulty accordingly.
Concluding remarks
Moran and Orlov have presented this new consensus algorithm in the hope of creating an alternative to the popular, but energy-consuming, Proof of Work mechanism. While the proposed protocol does appear to reduce energy consumption, the authors indicate that generating proof in the PoST structure is highly complex, and they have no concrete solution for this. The authors suggest that the next step might be a version of Proof of Space, where the proposed incremental difficulty adjustment of PoST and the lower complexity of generating proof of PoS are combined into a new consensus algorithm. There are several projects working on implementing or have implemented the PoST consensus algorithm, including Filecoin, Chia and Spacemesh.
Read the full article on Apograf and browse over 40,000 other research papers by clicking here.
