Paper 2024/1451

Traffic-aware Merkle Trees for Shortening Blockchain Transaction Proofs

Avi Mizrahi, Technion - Israel Institute of Technology
Noam Koren, Technion - Israel Institute of Technology
Ori Rottenstreich, Technion - Israel Institute of Technology
Yuval Cassuto, Technion - Israel Institute of Technology
Abstract

Merkle trees play a crucial role in blockchain networks in organizing network state. They allow proving a particular value of an entry in the state to a node that maintains only the root of the Merkle trees, a hash-based signature computed over the data in a hierarchical manner. Verification of particular state entries is crucial in reaching a consensus on the execution of a block where state information is required in the processing of its transactions. For instance, a payment transaction should be based on the balance of the two involved accounts. The proof length affects the network communication and is typically logarithmic in the state size. In this paper, we take advantage of typical transaction characteristics for better organizing Merkle trees to improve blockchain network performance. We focus on the common transaction processing where Merkle proofs are jointly provided for multiple accounts. We first provide lower bounds for the communication cost that are based on the distribution of accounts involved in the transactions. We then describe algorithms that consider traffic patterns for significantly reducing it. The algorithms are inspired by various coding methods such as Huffman coding, partition and weight balancing. We also generalize our approach towards the encoding of smart contract transactions that involve an arbitrary number of accounts. Likewise, we rely on real blockchain data to show the savings allowed by our approach. The experimental evaluation is based on transactions from the Ethereum network and demonstrates cost reduction for both payment transactions and smart contract transactions.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Minor revision. IEEE/ACM Transactions on Networking
Keywords
BlockchainMerkle TreesCoding Theory
Contact author(s)
avraham m @ cs technion ac il
noam koren @ campus technion ac il
or @ technion ac il
ycassuto @ ee technion ac il
History
2024-09-18: approved
2024-09-17: received
See all versions
Short URL
https://ia.cr/2024/1451
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1451,
      author = {Avi Mizrahi and Noam Koren and Ori Rottenstreich and Yuval Cassuto},
      title = {Traffic-aware Merkle Trees for Shortening Blockchain Transaction Proofs},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1451},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1451}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.