research-article

LVMT: An Efficient Authenticated Storage for Blockchain

Authors:

Sidi Mohamed Beillahi,

Fan LongAuthors Info & Claims

ACM Transactions on Storage, Volume 20, Issue 3

Article No.: 17, Pages 1 - 34

https://doi.org/10.1145/3664818

Published: 06 June 2024 Publication History

Abstract

Authenticated storage access is the performance bottleneck of a blockchain, because each access can be amplified to potentially O(log n) disk I/O operations in the standard Merkle Patricia Trie (MPT) storage structure. In this article, we propose a multi-Layer Versioned Multipoint Trie (LVMT), a novel high-performance blockchain storage with significantly reduced I/O amplifications. LVMT uses the authenticated multipoint evaluation tree vector commitment protocol to update commitment proofs in constant time. LVMT adopts a multi-layer design to support unlimited key–value pairs and stores version numbers instead of value hashes to avoid costly elliptic curve multiplication operations. In our experiment, LVMT outperforms the MPT in real Ethereum traces, delivering read and write operations 6× faster. It also boosts blockchain system execution throughput by up to 2.7×.

References

[1]

0xngmi. 2023. DefiLlama—DeFi Dashboard. Retrieved from https://defillama.com

[2]

Vivek Bagaria, Sreeram Kannan, David Tse, Giulia Fanti, and Pramod Viswanath. 2019. Prism: Deconstructing the blockchain to approach physical limits. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security. 585–602.

Digital Library

[3]

Paulo S. L. M. Barreto, Ben Lynn, and Michael Scott. 2002. Constructing elliptic curves with prescribed embedding degrees. In Proceedings of the International Conference on Security in Communication Networks. Springer, 257–267.

[4]

Paulo S. L. M. Barreto and Michael Naehrig. 2005. Pairing-friendly elliptic curves of prime order. In Proceedings of the International Workshop on Selected Areas in Cryptography. Springer, 319–331.

[5]

Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. 2014. Succinct non-interactive zero knowledge for a von neumann architecture. In Proceedings of the 23rd USENIX Security Symposium. 781–796.

Digital Library

[6]

Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. 2012. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. 326–349.

Digital Library

[7]

Dan Boneh, Benedikt Bünz, and Ben Fisch. 2019. Batching techniques for accumulators with applications to IOPs and stateless blockchains. In Proceedings of the Annual International Cryptology Conference. Springer, 561–586.

Digital Library

[8]

Sean Bowe. 2017. BLS12-381: New zk-SNARK Elliptic Curve Construction. Retrieved from https://z.cash/blog/new-snark-curve

[9]

Sean Bowe, Ariel Gabizon, and Matthew D. Green. 2018. A multi-party protocol for constructing the public parameters of the Pinocchio zk-SNARK. In Proceedings of the International Conference on Financial Cryptography and Data Security. Springer, 64–77.

[10]

Sean Bowe, Ariel Gabizon, and Ian Miers. 2017. Scalable multi-party computation for zk-SNARK parameters in the random beacon model. IACR Cryptol. ePrint Arch. (2017), 1050. http://eprint.iacr.org/2017/1050

[11]

Vitalik Buterin. 2023. Ethereum Whitepaper. Retrieved from https://ethereum.org/en/whitepaper/

[12]

Vitalik Buterin and Virgil Griffith. 2017. Casper the friendly finality gadget. CoRR abs/1710.09437 (2017). arXiv:1710.09437 http://arxiv.org/abs/1710.09437

[13]

Dario Catalano and Dario Fiore. 2013. Vector commitments and their applications. In Proceedings of the International Workshop on Public Key Cryptography. Springer, 55–72.

[14]

Chenxing Li and Sidi Mohamed Beillahi and Guang Yang and Ming Wu and Wei Xu and Fan Long. 2023. Authenticated Storage Benchmarks. Retrieved from https://github.com/ChenxingLi/authenticated-storage-benchmarks

[15]

Jemin Andrew Choi, Sidi Mohamed Beillahi, Peilun Li, Andreas Veneris, and Fan Long. 2022. LMPTs: Eliminating storage bottlenecks for processing blockchain transactions. In Proceedings of the International Conference on Blockchain and Cryptocurrency. IEEE.

[16]

Conflux Network. 2023. Conflux Rust for Authenticated Storage Benchmarks. Retrieved from https://github.com/Conflux-Chain/conflux-rust/tree/asb-e2e

[17]

Arkworks contributors. 2022. arkworks zkSNARK Ecosystem. Retrieved from https://arkworks.rs

[18]

Ethereum. 2023. Merkle Patricia Tree. Retrieved from https://ethereum.org/en/developers/docs/data-structures-and-encoding/patricia-merkle-trie/

[19]

Ethereum. 2023. Zero-Knowledge Rollups. Retrieved from https://ethereum.org/en/developers/docs/scaling/zk-rollups/

[20]

Etherscanners. 2023. ERC-20 Top Tokens. Retrieved from https://etherscan.io/tokens

[21]

Etherscanners. 2023. Ethereum Gas Tracker. Retrieved from https://etherscan.io/gastracker

[22]

Ittay Eyal, Adem Efe Gencer, Emin Gün Sirer, and Robbert Van Renesse. 2016. Bitcoin-NG: A scalable blockchain protocol. In Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation. 45–59.

[23]

Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. 2017. Algorand: Scaling byzantine agreements for cryptocurrencies. In Proceedings of the 26th Symposium on Operating Systems Principles. ACM, 51–68.

Digital Library

[24]

Sergey Gorbunov, Leonid Reyzin, Hoeteck Wee, and Zhenfei Zhang. 2020. Pointproofs: Aggregating proofs for multiple vector commitments. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security. 2007–2023.

Digital Library

[25]

Jens Groth, Markulf Kohlweiss, Mary Maller, Sarah Meiklejohn, and Ian Miers. 2018. Updatable and universal common reference strings with applications to zk-SNARKs. In Proceedings of the Annual International Cryptology Conference. Springer, 698–728.

Digital Library

[26]

Yilin Han, Chenxing Li, Peilun Li, Ming Wu, Dong Zhou, and Fan Long. 2020. Shrec: Bandwidth-efficient transaction relay in high-throughput blockchain systems. In Proceedings of the 11th ACM Symposium on Cloud Computing (SoCC ’20). Association for Computing Machinery, New York, NY, 238–252. DOI:

Digital Library

[27]

Koh Wei Jie. 2021. Perpetual Powers of Tau. Retrieved from https://github.com/weijiekoh/perpetualpowersoftau

[28]

Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. 2010. Constant-size commitments to polynomials and their applications. In Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security. Springer, 177–194.

[29]

Eleftherios Kokoris-Kogias, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, Ewa Syta, and Bryan Ford. 2018. Omniledger: A secure, scale-out, decentralized ledger via sharding. In Proceedings of the IEEE Symposium on Security and Privacy. IEEE, 583–598.

[30]

Russell W. F. Lai and Giulio Malavolta. 2019. Subvector commitments with application to succinct arguments. In Annual International Cryptology Conference. Springer, 530–560.

Digital Library

[31]

Yoad Lewenberg, Yonatan Sompolinsky, and Aviv Zohar. 2015. Inclusive block chain protocols. In Proceedings of the International Conference on Financial Cryptography and Data Security. Springer, 528–547.

[32]

Ao Li, Jemin Andrew Choi, and Fan Long. 2020. Securing smart contract with runtime validation. In Proceedings of the 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI ’20), Alastair F. Donaldson and Emina Torlak (Eds.). ACM, 438–453. DOI:

Digital Library

[33]

Chenxing Li, Peilun Li, Dong Zhou, Zhe Yang, Ming Wu, Wei Xu, Fan Long, and Andrew Yao. 2020. A decentralized blockchain with high throughput and fast confirmation. In Proceedings of the USENIX Annul Technical Conference. USENIX.

[34]

Loi Luu, Viswesh Narayanan, Chaodong Zheng, Kunal Baweja, Seth Gilbert, and Prateek Saxena. 2016. A secure sharding protocol for open blockchains. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS ’16). ACM, New York, NY, 17–30. DOI:

Digital Library

[35]

David Mazieres. 2015. The stellar consensus protocol: A federated model for internet-level consensus. Stellar Dev. Found. 32 (2015), 1–45.

[36]

Satoshi Nakamoto. 2009. Bitcoin: A Peer-to-Peer Electronic Cash System. Retrieved from http://bitcoin.org/bitcoin.pdf

[37]

Gleb Naumenko, Gregory Maxwell, Pieter Wuille, Alexandra Fedorova, and Ivan Beschastnikh. 2019. Erlay: Efficient transaction relay for bitcoin. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security. 817–831.

Digital Library

[38]

Alex Ozdemir, Riad Wahby, Barry Whitehat, and Dan Boneh. 2020. Scaling verifiable computation using efficient set accumulators. In Proceedings of the 29th USENIX Security Symposium (USENIX Security ’20). 2075–2092.

Digital Library

[39]

Parity Technologies. 2020. Crate kvdb. Retrieved from https://docs.rs/kvdb/0.4.0/kvdb/

[40]

Soujanya Ponnapalli, Aashaka Shah, Souvik Banerjee, Dahlia Malkhi, Amy Tai, Vijay Chidambaram, and Michael Wei. 2021. RainBlock: Faster transaction processing in public blockchains. In Proceedings of the USENIX Annual Technical Conference (USENIX ATC ’21). 333–347.

[41]

Ponnapalli, Soujanya and Shah, Aashaka and Banerjee, Souvik and Malkhi, Dahlia and Tai, Amy and Chidambaram, Vijay and Wei, Michael. 2023. RainBlock Protocol. Retrieved from https://github.com/RainBlock/rainblock-protocol

[42]

Ethereum Improvement Proposals. 2015. EIP-20: Token Standard. Retrieved from https://eips.ethereum.org/EIPS/eip-20

[43]

Pandian Raju, Soujanya Ponnapalli, Evan Kaminsky, Gilad Oved, Zachary Keener, Vijay Chidambaram, and Ittai Abraham. 2018. mLSM: Making authenticated storage faster in ethereum. In Proceedings of the 10th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage ’18), Ashvin Goel and Nisha Talagala (Eds.). USENIX Association.

[44]

Pandian Raju, Soujanya Ponnapalli, Evan Kaminsky, Gilad Oved, Zachary Keener, Vijay Chidambaram, and Ittai Abraham. 2018. mLSM: Making authenticated storage faster in ethereum. In Proceedings of the 10th USENIX Workshop on Hot Topics in Storage and File Systems. 10.

[45]

Yonatan Sompolinsky, Shai Wyborski, and Aviv Zohar. 2021. PHANTOM GHOSTDAG: A scalable generalization of nakamoto consensus. In 3rd ACM Conference on Advances in Financial Technologies (AFT’21), Foteini Baldimtsi and Tim Roughgarden (Eds.). Arlington, Virginia, ACM, 57–70.

Digital Library

[46]

Yonatan Sompolinsky and Aviv Zohar. 2015. Secure high-rate transaction processing in bitcoin. In Proceedings of the 2015 International Conference on Financial Cryptography and Data Security. Springer, 507–527.

[47]

Shravan Srinivasan, Alexander Chepurnoy, Charalampos Papamanthou, Alin Tomescu, and Yupeng Zhang. 2022. Hyperproofs: Aggregating and maintaining proofs in vector commitments. In Proceedings of the 31st USENIX Security Symposium (USENIX Security ’22). 3001–3018.

[48]

Facebook Database Engineering Team. 2022. RocksDB: A Persistent Key-Value Store for Flash and RAM Storage. Retrieved from https://rocksdb.org.

[49]

Parity Technologies. 2019. OpenEthereum. Retrieved from https://www.parity.io/ethereum/

[50]

Alin Tomescu, Ittai Abraham, Vitalik Buterin, Justin Drake, Dankrad Feist, and Dmitry Khovratovich. 2020. Aggregatable subvector commitments for stateless cryptocurrencies. In Proceedings of the International Conference on Security and Cryptography for Networks. Springer, 45–64.

Digital Library

[51]

Alin Tomescu, Robert Chen, Yiming Zheng, Ittai Abraham, Benny Pinkas, Guy Golan Gueta, and Srinivas Devadas. 2020. Towards scalable threshold cryptosystems. In Proceedings of the IEEE Symposium on Security and Privacy. IEEE, 877–893.

[52]

Uniswap Labs. 2023. Peripheral Smart Contracts for Interacting with Uniswap V2. Retrieved from https://github.com/Uniswap/v2-periphery

[53]

Uniswap Labs. 2023. Uniswap Protocol. Retrieved from https://uniswap.org/

[54]

Jiaping Wang and Hao Wang. 2019. Monoxide: Scale out blockchains with asynchronous consensus zones. In Proceedings of the 16th USENIX Symposium on Networked Systems Design and Implementation. 95–112.

[55]

Karl Wüst and Arthur Gervais. 2018. Do you need a blockchain? In Proceedings of the Crypto Valley Conference on Blockchain Technology (CVCBT ’18). IEEE, 45–54.

[56]

Haifeng Yu, Ivica Nikolić, Ruomu Hou, and Prateek Saxena. 2020. OHIE: Blockchain scaling made simple. In Proceedings of the IEEE Symposium on Security and Privacy. IEEE, 90–105.

[57]

Mahdi Zamani, Mahnush Movahedi, and Mariana Raykova. 2018. Rapidchain: Scaling blockchain via full sharding. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security. 931–948.

Digital Library

Cited By

Zhu YZheng YLiu JLi YZha Z(2024)Noise-Resistance Learning via Multi-Granularity Consistency for Unsupervised Domain Adaptive Person Re-IdentificationACM Transactions on Multimedia Computing, Communications, and Applications10.1145/370232821:1(1-23)Online publication date: 2-Nov-2024
https://dl.acm.org/doi/10.1145/3702328
Wen HSong XChen XWei YNie LChua THui Yang GWang HHan SHauff CZuccon GZhang Y(2024)Simple but Effective Raw-Data Level Multimodal Fusion for Composed Image RetrievalProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3626772.3657727(229-239)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3626772.3657727
He ZLi ZQiao ALuo XZhang XChen TSong SLiu DNiu W(2024)Nurgle: Exacerbating Resource Consumption in Blockchain State Storage via MPT Manipulation2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00125(2180-2197)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00125

Index Terms

LVMT: An Efficient Authenticated Storage for Blockchain

Recommendations

LETUS: A Log-Structured Efficient Trusted Universal BlockChain Storage
SIGMOD/PODS '24: Companion of the 2024 International Conference on Management of Data

With the evolution of Web3.0 and decentralized applications (Dapps), increasing business logic is running on the blockchain. Blockchain storage, as the core infrastructure supporting the increasing volume of data, plays a crucial role. However, the ...
BAHS: A Blockchain-Aided Hash-Based Signature Scheme
Information Security Practice and Experience
Abstract
Hash-based one-time signatures are becoming increasingly important as they are post-quantum safe and have been used in multi-cast communication and other applications. However, managing the state of such signatures can present a significant ...
Storage efficient blockchain models for constrained applications
Abstract
The growing chain’s storage requirement is always an issue with blockchain platforms, and devices may not allocate the required storage to replicate an entire blockchain instance. To overcome this issue, we propose storage-efficient blockchain ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Storage

ACM Transactions on Storage Volume 20, Issue 3

August 2024

205 pages

EISSN:1553-3093

DOI:10.1145/3613664

Editor:
Erez Zadok
Stony Brook University, USA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2024

Online AM: 16 May 2024

Accepted: 22 April 2024

Revised: 10 March 2024

Received: 11 November 2023

Published in TOS Volume 20, Issue 3

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Key Research and Development Project of China
Shanghai Committee of Science and Technology, China
National Natural Science Foundation of China
Nanjing Turing AI Institute

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
282
Total Downloads

Downloads (Last 12 months)282
Downloads (Last 6 weeks)50

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhu YZheng YLiu JLi YZha Z(2024)Noise-Resistance Learning via Multi-Granularity Consistency for Unsupervised Domain Adaptive Person Re-IdentificationACM Transactions on Multimedia Computing, Communications, and Applications10.1145/370232821:1(1-23)Online publication date: 2-Nov-2024
https://dl.acm.org/doi/10.1145/3702328
Wen HSong XChen XWei YNie LChua THui Yang GWang HHan SHauff CZuccon GZhang Y(2024)Simple but Effective Raw-Data Level Multimodal Fusion for Composed Image RetrievalProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3626772.3657727(229-239)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3626772.3657727
He ZLi ZQiao ALuo XZhang XChen TSong SLiu DNiu W(2024)Nurgle: Exacerbating Resource Consumption in Blockchain State Storage via MPT Manipulation2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00125(2180-2197)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00125

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents