{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,14]],"date-time":"2026-10-14T16:44:57Z","timestamp":1791996297396,"version":"4.4.0"},"reference-count":29,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2025,2,7]],"date-time":"2025-02-07T00:00:00Z","timestamp":1738886400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100010661","name":"European Union\u2019s Horizon 2020 research and innovation program under the Marie Sk\u0142odowska-Curie grant agreement","doi-asserted-by":"publisher","award":["101007820\u2014TRUST"],"award-info":[{"award-number":["101007820\u2014TRUST"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"European Union\u2019s Horizon 2020 research and innovation program under the Marie Sk\u0142odowska-Curie grant agreement","doi-asserted-by":"publisher","award":["ECS00000041-VITALITY-CUP D83C22000710005"],"award-info":[{"award-number":["ECS00000041-VITALITY-CUP D83C22000710005"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"name":"European Union\u2014NextGenerationEU under the Italian Ministry of University and Research (MIUR), National Innovation Ecosystem","award":["101007820\u2014TRUST"],"award-info":[{"award-number":["101007820\u2014TRUST"]}]},{"name":"European Union\u2014NextGenerationEU under the Italian Ministry of University and Research (MIUR), National Innovation Ecosystem","award":["ECS00000041-VITALITY-CUP D83C22000710005"],"award-info":[{"award-number":["ECS00000041-VITALITY-CUP D83C22000710005"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Future Internet"],"abstract":"<jats:p>This study addresses a critical challenge in modern blockchain systems: the excessive size of Merkle proofs in state verification, which significantly impacts scalability and efficiency. As highlighted by Ethereum\u2019s founder, Vitalik Buterin, current Merkle Patricia Tries (MPTs) are highly inefficient for stateless clients, with worst-case proofs reaching approximately 300 MB. We present a comprehensive probabilistic analysis of path length distributions in MPTs to optimize proof size while maintaining security guarantees. Our novel mathematical model characterizes the distribution of path lengths in tries containing random blockchain addresses and validates it through extensive computational experiments. The findings reveal logarithmic scaling of average path lengths with respect to the number of addresses, with unprecedented precision in predicting structural properties across scales from 100 to 300 million addresses. The research demonstrates remarkable accuracy, with discrepancies between theoretical and experimental results not exceeding 0.01 across all tested scales. By identifying and verifying the right-skewed nature of path length distributions, we provide critical insights for optimizing Merkle proof generation and size reduction. Our practical implementation guidelines demonstrate potential proof size reductions of up to 70% through optimized path structuring and node layout. This work bridges the gap between theoretical computer science and practical blockchain engineering, offering immediate applications for blockchain client optimization and efficient state-proof generation.<\/jats:p>","DOI":"10.3390\/fi17020072","type":"journal-article","created":{"date-parts":[[2025,2,7]],"date-time":"2025-02-07T11:03:51Z","timestamp":1738926231000},"page":"72","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Optimizing Merkle Proof Size Through Path Length Analysis: A Probabilistic Framework for Efficient Blockchain State Verification"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2331-6326","authenticated-orcid":false,"given":"Oleksandr","family":"Kuznetsov","sequence":"first","affiliation":[{"name":"Department of Theoretical and Applied Sciences, eCampus University, Via Isimbardi 10, 22060 Novedrate, Italy"},{"name":"Department of Intelligent Software Systems and Technologies, School of Computer Science and Artificial Intelligence, V.N. Karazin Kharkiv National University, 4 Svobody Sq., 61022 Kharkiv, Ukraine"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8893-9244","authenticated-orcid":false,"given":"Emanuele","family":"Frontoni","sequence":"additional","affiliation":[{"name":"Department of Political Sciences, Communication and International Relations, University of Macerata, Via Crescimbeni, 30\/32, 62100 Macerata, Italy"},{"name":"VRAI\u2014Vision, Robotics and Artificial Intelligence Lab, Via Brecce Bianche 12, 60131 Ancona, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kateryna","family":"Kuznetsova","sequence":"additional","affiliation":[{"name":"Department of Political Sciences, Communication and International Relations, University of Macerata, Via Crescimbeni, 30\/32, 62100 Macerata, Italy"},{"name":"VRAI\u2014Vision, Robotics and Artificial Intelligence Lab, Via Brecce Bianche 12, 60131 Ancona, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1700-3075","authenticated-orcid":false,"given":"Marco","family":"Arnesano","sequence":"additional","affiliation":[{"name":"Department of Theoretical and Applied Sciences, eCampus University, Via Isimbardi 10, 22060 Novedrate, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2025,2,7]]},"reference":[{"key":"ref_1","unstructured":"Pandey, R., Goundar, S., and Fatima, S. (2023). Chapter 3\u2014Distributed Computing to Blockchain: Architecture, Technology, and Applications. Distributed Computing to Blockchain, Academic Press."},{"key":"ref_2","unstructured":"Pandey, R., Goundar, S., and Fatima, S. (2023). Chapter 15\u2014Ethereum Blockchain Platform. Distributed Computing to Blockchain, Academic Press."},{"key":"ref_3","unstructured":"Ethereum (2023). Ethereum Yellow Paper 2023, Ethereum."},{"key":"ref_4","unstructured":"(2024, November 28). vitalik.eth [@VitalikButerin] @danfinlay The Goal Is to Replace the Current Merkle Patricia State Tree (MPT), Because the Current MPT Is *very* Unfriendly to Stateless Clients: A Worst-Case Stateless Proof for an Ethereum Block Is ~300 MB (Think: Spam Reads on 24kB Contracts), and Even the Average Case Sucks Because The. Twitter. Available online: https:\/\/x.com\/VitalikButerin\/status\/1817408883897593911."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"101193","DOI":"10.1016\/0304-3975(89)90115-1","article-title":"On the Balance Property of Patricia Tries: External Path Length Viewpoint","volume":"68","author":"Kirschenhofer","year":"1989","journal-title":"Theor. Comput. Sci."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1016\/0304-3975(92)90261-D","article-title":"Comments of \u201con the Balance Property of Patricia Tries: External Path Length Viewpoint\u201d","volume":"106","author":"Andersson","year":"1992","journal-title":"Theor. Comput. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"101193","DOI":"10.1016\/j.iot.2024.101193","article-title":"Merkle Trees in Blockchain: A Study of Collision Probability and Security Implications","volume":"26","author":"Kuznetsov","year":"2024","journal-title":"Internet Things"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"101315","DOI":"10.1016\/j.iot.2024.101315","article-title":"Adaptive Merkle Trees for Enhanced Blockchain Scalability","volume":"27","author":"Kuznetsov","year":"2024","journal-title":"Internet Things"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1016\/j.tcs.2015.02.009","article-title":"Smoothed Heights of Tries and Patricia Tries","volume":"609","author":"Tong","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/S0377-0427(01)00458-7","article-title":"Laws of Large Numbers and Tail Inequalities for Random Tries and PATRICIA Trees","volume":"142","author":"Devroye","year":"2002","journal-title":"J. Comput. Appl. Math."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/S0306-4573(01)00031-0","article-title":"A Dynamic Construction Algorithm for the Compact Patricia Trie Using the Hierarchical Structure","volume":"38","author":"Jung","year":"2002","journal-title":"Inf. Process. Manag."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"104697","DOI":"10.1016\/j.ic.2021.104697","article-title":"A Self-Stabilizing Hashed Patricia Trie","volume":"285","author":"Knollmann","year":"2022","journal-title":"Inf. Comput."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"100575","DOI":"10.1016\/j.cosrev.2023.100575","article-title":"Understanding Blockchain: Definitions, Architecture, Design, and System Comparison","volume":"50","author":"Tabatabaei","year":"2023","journal-title":"Comput. Sci. Rev."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"117282","DOI":"10.1109\/ACCESS.2023.3325748","article-title":"Multi-State Merkle Patricia Trie (MSMPT): High-Performance Data Structures for Multi-Query Processing Based on Lightweight Blockchain","volume":"11","author":"Mardiansyah","year":"2023","journal-title":"IEEE Access"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/j.future.2024.05.050","article-title":"SolsDB: Solve the Ethereum\u2019s Bottleneck Caused by Storage Engine","volume":"160","author":"Yang","year":"2024","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"5326","DOI":"10.1109\/TNET.2024.3466245","article-title":"Traffic-Aware Merkle Trees for Shortening Blockchain Transaction Proofs","volume":"32","author":"Mizrahi","year":"2024","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Kuznetsov, O., Rusnak, A., Yezhov, A., Kanonik, D., Kuznetsova, K., and Domin, O. (2024). Efficient and Universal Merkle Tree Inclusion Proofs via OR Aggregation. Cryptography, 8.","DOI":"10.3390\/cryptography8030028"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"12627","DOI":"10.1007\/s10586-024-04484-6","article-title":"Android Malware Detection Using Time-Aware Machine Learning Approach","volume":"27","author":"AlSobeh","year":"2024","journal-title":"Clust. Comput."},{"key":"ref_19","first-page":"102117","article-title":"Study on Data Storage and Verification Methods Based on Improved Merkle Mountain Range in IoT Scenarios","volume":"36","author":"Liang","year":"2024","journal-title":"J. King Saud Univ. Comput. Inf. Sci."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Alshattnawi, S., Shatnawi, A., AlSobeh, A.M.R., and Magableh, A.A. (2024). Beyond Word-Based Model Embeddings: Contextualized Representations for Enhanced Social Media Spam Detection. Appl. Sci., 14.","DOI":"10.3390\/app14062254"},{"key":"ref_21","unstructured":"Merkle, R.C. (1982). Method of Providing Digital Signatures. (4309569), U.S. Patent."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1145\/321479.321481","article-title":"PATRICIA\u2014Practical Algorithm To Retrieve Information Coded in Alphanumeric","volume":"15","author":"Morrison","year":"1968","journal-title":"J. ACM"},{"key":"ref_23","unstructured":"Knuth, D. (1998). Art of Computer Programming, The: Volume 3: Sorting and Searching, Addison-Wesley Professional. [2nd ed.]."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/j.future.2023.11.026","article-title":"Data Management in Ethereum DApps: A Cost and Performance Analysis","volume":"153","author":"Kostamis","year":"2024","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Arslanian, H. (2022). Ethereum. The Book of Crypto: The Complete Guide to Understanding Bitcoin, Cryptocurrencies and Digital Assets, Springer International Publishing.","DOI":"10.1007\/978-3-030-97951-5"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"George, J.T. (2022). Ethereum. Introducing Blockchain Applications: Understand and Develop Blockchain Applications Through Distributed Systems, Apress.","DOI":"10.1007\/978-1-4842-7480-4"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"100120","DOI":"10.1016\/j.bcra.2022.100120","article-title":"An Empirical Study on the Complexity, Security and Maintainability of Ethereum-Based Decentralized Applications (DApps)","volume":"4","author":"Samreen","year":"2023","journal-title":"Blockchain Res. Appl."},{"key":"ref_28","unstructured":"Kuznetsov, O. (2024, August 26). Patricia Trie Simulation for Ethereum Addresses. Available online: https:\/\/colab.research.google.com\/drive\/1rxevEArsxD5CN_aHYB_gDDJs_sra4ZbV?usp=sharing."},{"key":"ref_29","unstructured":"(2024, December 05). Merkle Patricia Trie. Available online: https:\/\/ethereum.org\/en\/developers\/docs\/data-structures-and-encoding\/patricia-merkle-trie\/."}],"container-title":["Future Internet"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-5903\/17\/2\/72\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T16:28:58Z","timestamp":1760027338000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-5903\/17\/2\/72"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,7]]},"references-count":29,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,2]]}},"alternative-id":["fi17020072"],"URL":"https:\/\/doi.org\/10.3390\/fi17020072","relation":{},"ISSN":["1999-5903"],"issn-type":[{"value":"1999-5903","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,7]]}}}