Paper 2021/035

Sketches for Blockchains

Ori Rottenstreich

Abstract

Blockchains suffer from a critical scalability problem where traditionally each network node maintains all network state, including records since the establishment of the blockchain. Sketches are popular hash-based data structures used to represent a large amount of data while supporting particular queries such as on set membership, cardinality estimation and identification of large elements. Often, to achieve time and memory savings, sketches allow potential inaccuracies in answers to the queries. The design of popular blockchain networks such as Bitcoin and Ethereum makes use of sketches for various tasks such as summarization of transaction blocks or declaring the interests of light nodes. Similarly, they seem natural to deal with the size of the state in blockchains. In this paper, we study existing and potential future applications of sketches in blockchains. We first summarize current blockchain use cases of sketches. Likewise, we explore how this coupling can be generalized to a wider range of sketches and additional functionalities. In particular, we explain how sketches can detect anomalies based on efficient an summary of the state or traffic.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. International Conference on Communication Systems and Networks (COMSNETS) 2021
Keywords
BlockchainSketches
Contact author(s)
ori rot @ gmail com
History
2021-01-12: received
Short URL
https://ia.cr/2021/035
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/035,
      author = {Ori Rottenstreich},
      title = {Sketches for Blockchains},
      howpublished = {Cryptology ePrint Archive, Paper 2021/035},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/035}},
      url = {https://eprint.iacr.org/2021/035}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.