Extending The Boundaries and Exploring The Limits Of Blockchain Compression
Anurag Jain, Emmanuelle Anceaume, Sujit Gujar · 2023
The long-term feasibility of blockchain technology is hindered by the inability of existing blockchain protocols to prune the consensus data leading to constantly growing storage and communication requirements. Kiayias et al. have proposed Non-Interactive-Proofs-of-Proof-of-Works (NIPoPoWs) as a mecha-nism to reduce the storage and communication complexity of blockchains to O(poly log(n)). However, their protocol is only resilient to an adversary that may control strictly less than a third of the total computational power, which is a reduction from the security guaranteed by Bitcoin and other existing Proof-of-based blockchains. We present an improvement to the Kiayias et al. proposal, which is resilient against an adversary that may control less than half of the total computational power while operating in$o$(polylog$(n)$) storage and communication complexity. Additionally, we present a novel proof that establishes a lower bound of$O(\log(n))$on the storage and communication complexity of any PoW-based blockchain protocol.