Paper 2021/623

Mining in Logarithmic Space

Aggelos Kiayias, Nikos Leonardos, and Dionysis Zindros


Blockchains maintain two types of data: Application data and consensus data. Towards long-term blockchain scalability, both of these must be pruned. While a large body of literature has explored the pruning of application data (UTXOs, account balances, and contract state), little has been said about the permanent pruning of consensus data (block headers). We present a protocol which allows pruning the blockchain by garbage collecting old blocks as they become unnecessary. These blocks can simply be discarded and are no longer stored by any miner. We show that all miners can be light miners with no harm to security. Our protocol is based on the notion of superblocks, blocks that have achieved an unusually high difficulty. We leverage them to represent underlying proof-of-work without ever illustrating it, storing it, or transmitting it. After our pruning is applied, the storage and communication requirements for consensus data is reduced exponentially. We develop new probabilistic mathematical methods to analyze our protocol in the random oracle model. We prove our protocol is both secure and succinct under an uninterrupted honest majority assumption for $1/3$ adversaries. Our protocol is the first to achieve always secure, always succinct, and online Non-Interactive Proofs of Proof-of-Work, all necessary components for a logarithmic space mining scheme. Our work has applications beyond mining and also constitutes an improvement in state-of-the-art superlight clients and cross-chain bridges.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
cryptographic protocolsblockchainlight clientsmining
Contact author(s)
dionyziz @ gmail com
2021-05-17: revised
2021-05-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Aggelos Kiayias and Nikos Leonardos and Dionysis Zindros},
      title = {Mining in Logarithmic Space},
      howpublished = {Cryptology ePrint Archive, Paper 2021/623},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.