On a class of descrete functions for Proof-of-Space blockchain consensus protocols

Abstract

The classic blockchain design implies the mining procedure, which is essentially reflected in the following: to add a new block to the chain, a user has to solve an instance of some moderately hard computational problem (Proof-of-Work
framework, PoW). One of the most criticized points of this approach is that users have to perform a significant amount of computational work. As a result, the PoW-blockchains involve very high energy consumption. This led to the arising of a blockchain-related research area aimed at developing other ways to prove the right of a user to add a new block. In 2015, Dziembowski et al. suggested the Proof-of-Space concept (PoS): instead of spending a certain amount of time on computations, users should reserve a certain amount of disk space on their computers. This requirement can be implemented, for example, by requesting the user to invert some discrete function, so that a user who has stored the table of the function values could easily do it. In 2017, Abusalah et al., trying to overcome some shortcomings of the original (simple) PoS, suggested to choose the function as a special composition of two discrete functions. In this paper, we analyze the idea of Abusalah et al. It is shown that this proposal does not meet the PoS requirement to reserve the specified amount of disk space. Also, we discuss the analysis of mathematical models of blockchains as cryptographic primitives.