Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Coding Schemes for Blockchain Networks
event speaker icon
Avi Mizrahi (Ph.D. Thesis Seminar)
event date icon
Wednesday, 11.10.2023, 11:30
event location icon
Zoom Lecture: 94964184897
event speaker icon
Advisor: Dr. O. Rottenstreich
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.