Error Correction Code Verifiable Computation Consensus

Abstract

In blockchain, proof-of-work (PoW) is a popular consensus mechanism in which block publishers secure block contents through competitive computation. This competition has led to the emergence of specialized computing devices, such as application-specific integrated circuits (ASICs). Consequently, block publishing has become monopolized by a small group of top publishers equipped with ASICs and benefiting from economy of scale. This monopoly undermines immutability and security that are derived from the decentralized structure of blockchains. In this paper, we introduce a type of blockchain consensus algorithm named error-correction code verifiable computation consensus (ECCVCC), which includes conventional PoW. After that, we propose a novel ECCVCC utilizing a syndrome decoding problem as its crypto puzzle. The ECCVCC algorithm suppresses the development of efficient ASICs by utilizing time-varying cryptographic puzzles. As a result, the decentralization of a blockchain with ECCVCC can be improved compared to the blockchains with other consensus algorithms. Our analysis and simulation demonstrate that ECCVCC achieves robust control over block-generation time and difficulty under practical scenarios. Finally, we discuss that ASIC-resistant consensus algorithms, such as ECCVCC, sustain a blockchain network decentralized for a significantly longer period compared to conventional hash-PoW.