Alexander Chepurnoy, Mario Larangeira, Alexander Ojiganov
Bitcoin is the first successful decentralized global digital cash system. Its mining process requires intense computational resources, therefore its usefulness remains a disputable topic. We aim to solve three problems with Bitcoin and other blockchain systems of today by repurposing their work. First, space to store a blockchain is growing linearly with number of transactions. Second, a honest node is forced to be irrational regarding storing full blocks by a way implementations are done. Third, a trustless bootstrapping process for a new node involves downloading and processing all the transactions ever written into a blockchain. In this paper we present a new consensus protocol for Bitcoin-like peer-to-peer systems where a right to generate a block is given to a party providing non-interactive proofs of storing a subset of the past state snapshots. Unlike the blockchain systems in use today, a network using our protocol is safe if the nodes prune full blocks not needed for mining. We extend the GKL model to describe our Proof-of-Work scheme and a transactional model modifications needed for it. We provide a detailed analysis of our protocol and proofs of its security.