Paper 2021/623

Mining in Logarithmic Space

Aggelos Kiayias, Nikos Leonardos, and Dionysis Zindros

Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
cryptographic protocolsblockchainlight clientsmining
Contact author(s)
dionyziz @ gmail com
History
2021-05-17: revised
2021-05-17: received
See all versions
Short URL
https://ia.cr/2021/623
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/623,
      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{https://eprint.iacr.org/2021/623}},
      url = {https://eprint.iacr.org/2021/623}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.