Paper 2019/1444

Compact Storage of Superblocks for NIPoPoW Applications

Kostis Karantias, Aggelos Kiayias, Nikos Leonardos, and Dionysis Zindros


Blocks in proof-of-work (PoW) blockchains satisfy the PoW equation $H(B) \leq T$. If additionally a block satisfies $H(B) \leq T2^{-\mu}$, it is called a $\mu$-superblock. Superblocks play an important role in the construction of compact blockchain proofs which allows the compression of PoW blockchains into so-called Non-Interactive Proofs of Proof-of-Work (NIPoPoWs). These certificates are essential for the construction of superlight clients, which are blockchain wallets that can synchronize exponentially faster than traditional SPV clients. In this work, we measure the distribution of superblocks in the Bitcoin blockchain. We find that the superblock distribution within the blockchain follows expectation, hence we empirically verify that the distribution of superblocks within the Bitcoin blockchain has not been adversarially biased. NIPoPoWs require that each block in a blockchain points to a sample of previous blocks in the blockchain. These pointers form a data structure called the interlink. We give efficient ways to store the interlink data structure. Repeated superblock references within an interlink can be omitted with no harm to security. Hence, it is more efficient to store a set of superblocks rather than a list. We show that, in honest executions, this simple observation reduces the number of superblock references by approximately a half in expectation. We then verify our theoretical result by measuring the improvement over existing blockchains in terms of the interlink sizes (which we improve by $79\%$) and the sizes of succinct NIPoPoWs (which we improve by $25\%$). As such, we show that deduplication allows superlight clients to synchronize $25\%$ faster.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.Mathematical Research for Blockchain Economy 2019
Contact author(s)
dionyziz @ gmail com
2019-12-12: received
Short URL
Creative Commons Attribution


      author = {Kostis Karantias and Aggelos Kiayias and Nikos Leonardos and Dionysis Zindros},
      title = {Compact Storage of Superblocks for NIPoPoW Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1444},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.