The Taub Faculty of Computer Science Events and Talks

We study the design of coding schemes for blockchain networks, focusing on state organization and memory-efficient data structures for communication protocols. We first propose traffic-aware sharding, a technique that arranges data into distinct groups, to decrease overhead from cross-shard transactions while providing memory-efficient mappings of data into shards. Then, we study the use of Merkle trees in transaction proof verification, discussing a traffic-aware approach to organize data in such trees for cost-effective communication. We also study the Invertible Bloom Lookup Table (IBLT), a probabilistic data structure used in set reconciliation protocols such as the synchronization of blockchain transaction mempools. Beyond the basic Bloom filter that can answer membership queries, the IBLT has a listing operation that traditionally succeeds in a probabilistic manner. We suggest an IBLT with listing guarantees, in which listing always succeeds when the size of the represented set is smaller than a given threshold. The constructions are based on various coding techniques such as stopping sets of error-correcting codes, Steiner systems, as well as new methodologies we develop. We provide an in-depth analysis of the parameter space of each of the constructions.