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

Oleg A. Logachev, Sergey N. Fedorov


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.

Full Text:

PDF (Russian)


Varnovsky N. P. Blockchain as a cryptographic primitive // International

Journal of Open Information Technologies (INJOIT). 2020.

Vol. 8, no. 12. P. 28–32 [in Russian].

Tapscott D., Tapscott A. The blockchain revolution: How the technology

behind bitcoin is changing money, business, and the world.

London : Penguin Books, 2016.

Drescher D. Blockchain basics: A non-technical introduction in

steps. New York : Apress, 2017.

Pass R., Seeman L., Shelat A. Analysis of the blockchain protocol

in asynchronous networks // Advances in Cryptology—

EUROCRYPT ’17. Vol. 10210 of Lecture Notes in Computer Science.

Berlin, Heidelberg : Springer, 2017. P. 643–673.

Proofs of space / S. Dziembowski, S. Faust, V. Kolmogorov,

K. Pietrzak // Advances in Cryptology—CRYPTO ’92. Vol. 9216 of

Lecture Notes in Computer Science. Berlin, Heidelberg : Springer,

P. 585–605.

Beyond Hellman’s time–memory trade-offs with applications to proofs

of space / H. Abusalah, J. Alwen, B. Cohen et al. // Asiacrypt 2017,

Part II. Vol. 10625 of Lecture Notes in Computer Science. Berlin,

Heidelberg : Springer, 2017. P. 357–379.

Dwork C., Naor M. Pricing via processing or combatting junk mail //

Advances in Cryptology—CRYPTO ’92. Vol. 740 of Lecture Notes in

Computer Science. Berlin, Heidelberg : Springer, 1993. P. 139–147.

Hellman M. E. A cryptanalytic time–memory trade-off // IEEE Trans.

on Information Theory. 1980. Vol. IT-26, no. 4. P. 401–406.

Katz J., Lindell Y. Introduction to Modern Cryptography. London :

CRC Press, 2007.

Nechayev V. I. Elementy kriptografii : Osnovy teorii zashchity

informatsii. Moscow : Vysshaya shkola, 1999 [in Russian].

Vasilenko O. N. Number-theoretic algorithms in cryptography. Providence

(Rhode Island) : American Mathematical Society, 2006.


  • There are currently no refbacks.

Abava  Absolutech Convergent 2020

ISSN: 2307-8162