pith. sign in

arxiv: 2606.11736 · v1 · pith:XCM6QSFHnew · submitted 2026-06-10 · 💻 cs.CR · cs.DC· cs.ET

MHOT: Height-Optimized Authenticated Data Structure for Blockchain State Commitment

Sipeng Xie , Qianhong Wu , Minghang Li , Qiyuan Gao , Bo Qin , Qin Wang This is my paper

Pith reviewed 2026-06-27 09:17 UTC · model grok-4.3

classification 💻 cs.CR cs.DCcs.ET
keywords authenticated data structureblockchain state commitmentMerkle treeheight optimizationadaptive fanouthierarchical proofsattack resiliencediscriminative bits
0
0 comments X

The pith

Indexing keys by their actual distinguishing bits produces height-optimal authenticated tries with linear fanout coupling and logarithmic proof overhead.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that fixed-prefix indexing in standard Merkle tries forces exponential growth between node span and proof size, leaving systems open to cheap height-inflation attacks. MHOT replaces that indexing with selection of only the bits that separate keys, yielding an adaptive fanout whose height is provably minimal while preserving ordinary hash verification. A two-layer Merkle construction then caps the extra proof cost per high-fanout node at logarithmic rather than linear in the fanout. Measurements on live Ethereum traces confirm the resulting gains in write speed, write amplification, and proof size, together with complete resistance to the cited attack even when the adversary expends a full block gas budget. The central contention is that these improvements follow from height optimality itself rather than from any new cryptographic primitive.

Core claim

MHOT indexes state keys by their discriminative bits to produce an adaptive fanout whose height is provably minimal. A two-layer Merkle construction then limits proof size growth to O(log k) per node rather than O(k). On Ethereum traces this produces up to ninefold higher write throughput, fourfold lower write amplification, and twofold smaller proofs than the Patricia Trie while maintaining zero success rate for height-inflation attacks even when the adversary spends an entire block’s gas budget.

What carries the argument

Discriminative-bit indexing that selects only bits separating keys, paired with hierarchical two-layer Merkle proofs that collapse per-node verification cost from linear to logarithmic in fanout.

If this is right

  • Write throughput rises by up to a factor of nine on mainnet workloads.
  • Write amplification falls by a factor of four.
  • Proof sizes shrink by a factor of two.
  • Attack success rate reaches zero under full-budget height-inflation attempts.
  • Tree height stays minimal without exponential growth in proof size when fanout increases.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same bit-discrimination rule could be applied to authenticated structures outside blockchains to reduce path length.
  • Dynamic adjustment of fanout based on observed key separation might further tune the height-proof trade-off at runtime.
  • Lower state-update costs would follow in any system that charges for Merkle-path length.

Load-bearing premise

Indexing by discriminative bits can be maintained efficiently at scale without introducing hidden distribution assumptions or maintenance costs that offset the height gains.

What would settle it

An experiment that inserts keys chosen to maximize collisions on discriminative bits and measures whether tree height exceeds the claimed minimum or whether proof construction time grows super-linearly.

Figures

Figures reproduced from arXiv: 2606.11736 by Bo Qin, Minghang Li, Qianhong Wu, Qin Wang, Qiyuan Gao, Sipeng Xie.

Figure 1
Figure 1. Figure 1: Cross-block node sharing in MPT under copy￾on-write semantics. When accounts are modified, only af￾fected paths change. Unchanged subtrees remain shared. Such append-only structure requires O(d) writes per modification, where d is the path length from leaf to root. hash values in the proof. Hierarchical hashing reduces this to O(d ·s) hashes, but each node still requires O(2 s ) hash computations during co… view at source ↗
Figure 2
Figure 2. Figure 2: HOT insertion mechanisms with fanout k = 3. (a) Normal Insert: the new key is added when the node has capacity. (b) Leaf pushdown: a collision creates a new child node containing both entries. (c) Parent pull-up: overflow propagates upward when hchild +1 = hparent; this is the only path that increases global tree height. (d) Intermediate node creation: when hchild +1 < hparent, an intermediate node ab￾sorb… view at source ↗
Figure 3
Figure 3. Figure 3: Node layout in MHOT. The top panel shows a com￾pound node with fixed-size metadata and variable-length child array. The bottom panel shows two child reference formats. FINAL references store version, height, and hash; TEMP ref￾erences store a temporary ID for deferred hashing. per-node overhead from O(k) to O(logk). For k = 32, this yields roughly a 6× reduction in hash overhead. In practice, single-point … view at source ↗
Figure 4
Figure 4. Figure 4: Write throughput. MHOT-AF denotes asynchronous flush; MHOT without suffix uses synchronous flush. MHOT outperforms MPT by 5–9× across all configurations. 100k 500k 1m Real Workload Scale 0 1 2 3 4 5 6 Average Write Amplification MPT RAIN MHOT-Blake3 MHOT-Keccak MHOT-Blake3-AF MHOT-Keccak-AF LVMT [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Average write amplification comparison. Lower is [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Tree height comparison. LVMT achieves optimal height under synthetic workloads but degrades to match MPT under real traces. MHOT maintains consistent height. Real-world trace. The Ethereum mainnet trace reveals a limitation of fixed-span architectures. LVMT maintains an average height of 2, but individual branches reach depth 9, approaching MPT and RainBlock’s worst-case heights of 10. Real Ethereum addres… view at source ↗
Figure 8
Figure 8. Figure 8: Multi-point and range proof scalability under [PITH_FULL_IMAGE:figures/full_fig_p014_8.png] view at source ↗
Figure 10
Figure 10. Figure 10: Security games for MHOT proof system soundness. In the membership game G mem, the adversary wins if verification accepts but (K,V) ∈/ Tπ, where ExtractTrie reconstructs the partial trie from the proof (see Definition 15). In the non-membership game G nmem, the adversary wins if the reached leaf equals the query key. In G lb , ComputeLB(π) derives the correct lower bound from the authenticated structure. B… view at source ↗
read the original abstract

State root computation dominates (78%) blockchain block processing time. Ethereum's canonical authenticated data structure, i.e., Merkle Patricia Trie (MPT), suffers from severe tree-height growth and is vulnerable to \textit{Nurgle attacks} (SP'24), where adversaries inflate path depth via hash collisions and degrade system performance at negligible cost. Existing defenses increase node fanout (span) to bound tree height, but higher span inflates proof size exponentially. Prior work mitigates this trade-off using vector commitments, at the cost of trusted setup or expensive verification. We present \textsc{Mhot}, a height-optimal authenticated data structure for blockchain state commitment that preserves standard hash-based verification without trusted setup. Unlike MPT's fixed-prefix indexing, which couples span and fanout exponentially, \textsc{Mhot} indexes by discriminative bits that actually distinguish keys, achieving adaptive span with linear fanout coupling and provably minimal height. To prevent high fanout from inflating proofs, we introduce hierarchical proofs, a two-layer Merkle construction that reduces per-node proof overhead from O(k) to O(log k). On Ethereum mainnet workloads, \textsc{Mhot} achieves up to 9X higher write throughput, 4X lower write amplification, and 2X smaller proofs than MPT. Under Nurgle attacks, even when the adversary consumes an entire block's gas budget, \textsc{Mhot} maintains a 0% attack success rate (v.s., 99.97% for MPT). Our results, somewhat surprisingly, show that height optimality (not new crypto primitives!) is the key abstraction for scalable and attack-resilient blockchain state commitment.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces MHOT, a height-optimized authenticated data structure for blockchain state commitment. It replaces MPT's fixed-prefix indexing with discriminative-bit indexing to achieve adaptive span, linear fanout coupling, and provably minimal height. Hierarchical proofs are used to keep proof sizes at O(log k) per node. Evaluations on Ethereum workloads show up to 9X write throughput, 4X lower amplification, 2X smaller proofs, and 0% success rate under Nurgle attacks vs. 99.97% for MPT. The key insight is that height optimality, not new primitives, enables scalability and resilience.

Significance. If the construction and analysis hold, this work would establish height optimality via discriminative indexing as a practical abstraction for improving blockchain ADS performance and security against height-inflation attacks, without relying on trusted setups or complex crypto. The empirical results on real workloads and attack scenarios provide concrete evidence of the benefits.

major comments (2)
  1. [Abstract and indexing section] Abstract and indexing section: The central claim of provably minimal height and linear fanout coupling under discriminative-bit indexing requires that the indexing can be maintained efficiently on dynamic inserts/deletes without super-linear costs or uniformity assumptions on keys. The manuscript does not provide an algorithm, complexity analysis, or security reduction for this maintenance step, which is load-bearing for both the performance claims and the Nurgle attack resistance (0% success rate).
  2. [Proof construction section] Proof construction section: The hierarchical two-layer Merkle construction is said to reduce per-node proof overhead from O(k) to O(log k) while preserving hash-based security. However, no formal security argument is given showing that the adaptive fanout does not introduce vulnerabilities, particularly under adversarial key distributions that could affect the discriminative bits.
minor comments (2)
  1. [Evaluation] The workloads are from Ethereum mainnet, but details on how the attack gas budget is modeled and the exact parameters for Nurgle attack simulation should be clarified for reproducibility.
  2. [Notation] The term 'discriminative bits' is introduced without a formal definition in the abstract; a precise definition early in the paper would aid clarity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review. We address the two major comments point-by-point below and will revise the manuscript to incorporate the requested details on maintenance algorithms and security arguments.

read point-by-point responses

  1. Referee: [Abstract and indexing section] Abstract and indexing section: The central claim of provably minimal height and linear fanout coupling under discriminative-bit indexing requires that the indexing can be maintained efficiently on dynamic inserts/deletes without super-linear costs or uniformity assumptions on keys. The manuscript does not provide an algorithm, complexity analysis, or security reduction for this maintenance step, which is load-bearing for both the performance claims and the Nurgle attack resistance (0% success rate).

    Authors: We agree that the current manuscript would benefit from an expanded treatment of dynamic maintenance. We will add a dedicated subsection (in the revised Section 4) that presents the insert/delete algorithms explicitly, proves O(log n) amortized complexity per operation based on height optimality, and shows that no uniformity assumptions on keys are required because discriminative bits are identified via direct key comparisons at each level. We will also include a brief security argument establishing that height minimality and Nurgle resistance follow directly from correct bit discrimination, independent of the attack model. revision: yes

  2. Referee: [Proof construction section] Proof construction section: The hierarchical two-layer Merkle construction is said to reduce per-node proof overhead from O(k) to O(log k) while preserving hash-based security. However, no formal security argument is given showing that the adaptive fanout does not introduce vulnerabilities, particularly under adversarial key distributions that could affect the discriminative bits.

    Authors: We acknowledge that a formal security reduction is missing from the current draft. The hierarchical construction composes two standard Merkle trees, so its security reduces to collision resistance of the underlying hash function. In the revision we will add a theorem and proof sketch (new subsection in Section 5) demonstrating that verification still requires recomputing the root hash and that adaptive fanout determined by discriminative bits does not create additional attack surfaces; any forgery would still imply a hash collision even under adversarial key distributions. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation chain is self-contained

full rationale

The provided abstract and context describe a new construction (discriminative-bit indexing plus hierarchical proofs) whose claimed properties (adaptive span, minimal height, linear fanout coupling, O(log k) proofs) are presented as following from the indexing choice and two-layer Merkle structure. No equations, fitted parameters, or self-citations are shown that reduce these claims to the inputs by construction. The reader's assessment notes the absence of such reductions, and the skeptic concerns address empirical bounds rather than definitional circularity. The derivation therefore stands as independent of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 2 invented entities

Abstract-only view limits visibility; no explicit free parameters or invented entities beyond the MHOT construction itself are stated. Standard cryptographic hash assumptions are implicit.

axioms (1)
  • standard math Standard collision-resistant hash function properties suffice for security of the Merkle construction
    Invoked implicitly for both MPT baseline and MHOT proofs
invented entities (2)
  • Discriminative-bit indexing no independent evidence
    purpose: Achieve adaptive span with linear fanout coupling for minimal height
    Core new mechanism described in abstract; no independent evidence supplied
  • Hierarchical proofs no independent evidence
    purpose: Reduce per-node proof overhead from O(k) to O(log k)
    Two-layer Merkle construction introduced to control proof size

pith-pipeline@v0.9.1-grok · 5848 in / 1366 out tokens · 21915 ms · 2026-06-27T09:17:52.190767+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

78 extracted references · 7 canonical work pages

  1. [1]

    URL: https://github.com/ethereum/devp2p/ blob/master/caps/snap.md

    devp2p/caps/snap.md at master · ethereum/devp2p. URL: https://github.com/ethereum/devp2p/ blob/master/caps/snap.md

  2. [2]

    Kvac: Key-value commitments for blockchains and beyond

    Shashank Agrawal and Srinivasan Raghuraman. Kvac: Key-value commitments for blockchains and beyond. In International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), volume 12493 ofLNCS, pages 839–869. Springer, 2020. doi:10.1007/978-3-030-64840-4_28

    work page doi:10.1007/978-3-030-64840-4_28 2020

  3. [3]

    Chainspace: A sharded smart contracts platform

    Mustafa Al-Bassam, Alberto Sonnino, Shehar Bano, Dave Hrycyszyn, and George Danezis. Chainspace: A sharded smart contracts platform. InNetwork and Distributed System Security Symposium (NDSS), 2018. doi:10.14722/ndss.2018.23241

    work page doi:10.14722/ndss.2018.23241 2018

  4. [4]

    EIP-3102: Bi- nary trie structure

    Guillaume Ballet and Vitalik Buterin. EIP-3102: Bi- nary trie structure. Ethereum Improvement Propos- als, September 2020. https://eips.ethereum.org/ EIPS/eip-3102

    2020

  5. [5]

    EIP-4762: Statelessness gas cost changes

    Guillaume Ballet, Vitalik Buterin, Dankrad Feist, Ig- nacio Hagopian, Tanishq Jasoria, and Gajinder Singh. EIP-4762: Statelessness gas cost changes. Ethereum Im- provement Proposals, February 2022. https://eips. ethereum.org/EIPS/eip-4762

    2022

  6. [6]

    Height optimized tries.ACM Transactions on Database Systems (TODS), 47:1 – 46, 2022

    Robert Binna, Eva Zangerle, Martin Pichl, Günther Specht, and Viktor Leis. Height optimized tries.ACM Transactions on Database Systems (TODS), 47:1 – 46, 2022

    2022

  7. [7]

    Merkle multi-proofs

    Remco Bloemen. Merkle multi-proofs. Technical Note, 2025. Available at: https://xn--2-umb.com/ 25/merkle-multi-proof/

    2025

  8. [8]

    EIP-150: Gas cost changes for io- heavy operations

    Vitalik Buterin. EIP-150: Gas cost changes for io- heavy operations. Ethereum Improvement Proposals, October 2016. https://eips.ethereum.org/EIPS/ eip-150

    2016

  9. [9]

    EIP-7864: Ethereum state using a unified binary tree

    Vitalik Buterin, Guillaume Ballet, Dankrad Feist, Igna- cio Hagopian, Kevaundray Wedderburn, Tanishq Jasoria, Gajinder Singh, Danno Ferrin, Piper Merriam, and Got- tfried Herold. EIP-7864: Ethereum state using a unified binary tree. Ethereum Improvement Proposals, January 2025.https://eips-wg.github.io/EIPs/7864/

    2025

  10. [10]

    EIP-7864: Ethereum state using a unified binary tree

    Vitalik Buterin, Guillaume Ballet, Dankrad Feist, Igna- cio Hagopian, Kevaundray Wedderburn, Tanishq Jaso- ria, Gajinder Singh, Danno Ferrin, Piper Merriam, and Gottfried Herold. EIP-7864: Ethereum state using a unified binary tree. Ethereum Improvement Proposals, January 2025. https://eips.ethereum.org/EIPS/ eip-7864

    2025

  11. [11]

    EIP-6800: Ethereum state using a uni- fied verkle tree

    Vitalik Buterin, Dankrad Feist, Kevaundray Wedderburn, Guillaume Ballet, Piper Merriam, Gottfried Herold, Ig- nacio Hagopian, Tanishq Jasoria, Gajinder Singh, and Danno Ferrin. EIP-6800: Ethereum state using a uni- fied verkle tree. Ethereum Improvement Proposals, March 2023. https://eips.ethereum.org/EIPS/ eip-6800

    2023

  12. [12]

    EIP-2929: Gas cost increases for state access opcodes

    Vitalik Buterin and Martin Swende. EIP-2929: Gas cost increases for state access opcodes. Ethereum Im- provement Proposals, September 2020. https://eips. ethereum.org/EIPS/eip-2929

    2020

  13. [13]

    Splitdb: Closing the performance gap for lsm-tree-based key-value stores.IEEE Transactions on Computers (TC), 73:206–220, 2024

    Miao Cai, Xuzhen Jiang, Junru Shen, and Baoliu Ye. Splitdb: Closing the performance gap for lsm-tree-based key-value stores.IEEE Transactions on Computers (TC), 73:206–220, 2024

    2024

  14. [14]

    Incrementally aggre- gatable vector commitments and applications to ver- ifiable decentralized storage

    Matteo Campanelli, Dario Fiore, Nicola Greco, Dimitris Kolonelos, and Luca Nizzardo. Incrementally aggre- gatable vector commitments and applications to ver- ifiable decentralized storage. InInternational Con- ference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), volume 12492 ofLNCS, pages 3–35. Springer, 2020. doi:10.1...

    2020

  15. [15]

    Vector commitments and their applications

    Dario Catalano and Dario Fiore. Vector commitments and their applications. InInternational Conference on Practice and Theory in Public-Key Cryptography (PKC), volume 7778 ofLNCS, pages 55–72. Springer, 2013. doi:10.1007/978-3-642-36362-7_5

    work page doi:10.1007/978-3-642-36362-7_5 2013

  16. [16]

    On the impossibility of algebraic vector commitments in pairing-free groups

    Dario Catalano, Dario Fiore, Rosario Gennaro, and Emanuele Giunta. On the impossibility of algebraic vector commitments in pairing-free groups. InTheory of Cryptography Conference (TCC), volume 13748 of LNCS, pages 274–299. Springer, 2022. doi:10.1007/ 978-3-031-22365-5_10

    2022

  17. [17]

    Forerunner: Constraint-based speculative transaction execution for ethereum

    Yang Chen, Zhongxin Guo, Runhuai Li, Shuo Chen, Lidong Zhou, Yajin Zhou, and Xian Zhang. Forerunner: Constraint-based speculative transaction execution for ethereum. InACM SIGOPS Symposium on Operating Systems Principles (SOSP), pages 570–587, 2021

    2021

  18. [18]

    Chainkv: A semantics- aware key-value store for ethereum system.Proceedings of the ACM on Management of Data (SIGMOD), 2023

    Zehao Chen, Bingzhe Li, Xiaojun Cai, Zhiping Jia, Lei Ju, Zili Shao, and Zhaoyan Shen. Chainkv: A semantics- aware key-value store for ethereum system.Proceedings of the ACM on Management of Data (SIGMOD), 2023

    2023

  19. [19]

    Edrax: A cryp- tocurrency with stateless transaction validation

    Alexander Chepurnoy, Charalampos Papamanthou, Shravan Srinivasan, and Yupeng Zhang. Edrax: A cryp- tocurrency with stateless transaction validation. Cryp- tology ePrint Archive, Report 2018/968, 2018. https: //eprint.iacr.org/2018/968

    2018

  20. [20]

    Veneris, and Fan Long

    Jemin Andrew Choi, Sidi Mohamed Beillahi, Peilun Li, Andreas G. Veneris, and Fan Long. Lmpts: Eliminating storage bottlenecks for processing blockchain transac- tions. InIEEE International Conference on Blockchain and Cryptocurrency (ICBC), pages 1–9, 2022

    2022

  21. [21]

    Functional commit- ments for all functions, with transparent setup

    Leo de Castro and Chris Peikert. Functional commit- ments for all functions, with transparent setup. InAn- nual International Conference on the Theory and Appli- cations of Cryptographic Techniques (EUROCRYPT), 2023

    2023

  22. [22]

    Accelerating merkle patricia trie with gpu.Proceedings of the VLDB Endowment (VLDB), 17:1856–1869, 2024

    Yangshen Deng, Muxi Yan, and Bo Tang. Accelerating merkle patricia trie with gpu.Proceedings of the VLDB Endowment (VLDB), 17:1856–1869, 2024

    2024

  23. [23]

    Siying Dong, Andrew Kryder, Yanqin Jin, Lin Peng, Kanchan Mehra, Jeremy Yakdus, Wei-Nee Chen, Ab- hishek Sharma, Youngjin Kwon, and Gary J. Katz. RocksDB: Evolution of development, optimization and uses of lsm-based storage. InProceedings of the 8th Bi- ennial Conference on Innovative Data Systems Research (CIDR), 2017

    2017

  24. [24]

    Erigon: Ethereum implementation on the efficiency frontier

    Erigon Team. Erigon: Ethereum implementation on the efficiency frontier. GitHub Repository, 2024. Available at:https://github.com/erigontech/erigon

    2024

  25. [25]

    An efficient hot/cold data separation scheme for storage optimization in consor- tium blockchain full nodes.Cluster Computing, 28, 2025

    Libo Feng and Xian Deng. An efficient hot/cold data separation scheme for storage optimization in consor- tium blockchain full nodes.Cluster Computing, 28, 2025

    2025

  26. [26]

    Robust and fast blockchain state synchronization

    Enrique Fynn, Ethan Buchman, Zarko Milosevic, Robert Soulé, and Fernando Pedone. Robust and fast blockchain state synchronization. In Eshcar Hillel, Roberto Palmieri, and Etienne Rivière, editors,26th Interna- tional Conference on Principles of Distributed Sys- tems, OPODIS 2022, Brussels, Belgium, December 13- 15, 2022, volume 253 ofLIPIcs, pages 8:1–8:2...

    work page doi:10.4230/lipics.opodis 2022

  27. [27]

    Utilizing parallelism in smart contracts on decentralized blockchains by taming application- inherent conflicts

    Péter Garamvölgyi, Yuxi Liu, Dong Zhou, Fan Long, and Ming Wu. Utilizing parallelism in smart contracts on decentralized blockchains by taming application- inherent conflicts. InInternational Conference on Soft- ware Engineering (ICSE), pages 2315–2326, 2022

    2022

  28. [28]

    Block-stm: Scaling blockchain execution by turning ordering curse to a performance blessing

    Rati Gelashvili, Alexander Spiegelman, Zhuolun Xiang, George Danezis, Zekun Li, Dahlia Malkhi, Yu Xia, and Runtian Zhou. Block-stm: Scaling blockchain execution by turning ordering curse to a performance blessing. In ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP), pages 232– 244, 2023

    2023

  29. [29]

    Parallel intermediate node fetching (for a single trie)

    Geth Team. Parallel intermediate node fetching (for a single trie). Go Ethereum Issue #28266, 2023. Available at: https://github.com/ethereum/go-ethereum/ issues/28266. Accessed: 2026-05-18

    2023

  30. [30]

    Pointproofs: Aggregating proofs for multiple vector commitments

    Sergey Gorbunov, Leonid Reyzin, Hoeteck Wee, and Zhenfei Zhang. Pointproofs: Aggregating proofs for multiple vector commitments. InACM SIGSAC Con- ference on Computer and Communications Security (CCS), pages 2007–2023. ACM, 2020. doi:10.1145/ 3372297.3417244

    arXiv 2007

  31. [31]

    Nurgle: Exacerbating resource consumption in blockchain state storage via mpt manipulation

    Zheyuan He, Zihao Li, Ao Qiao, Xiapu Luo, Xiaosong Zhang, Ting Chen, Shuwei Song, Dijun Liu, and Weina Niu. Nurgle: Exacerbating resource consumption in blockchain state storage via mpt manipulation. InIEEE Symposium on Security and Privacy (S&P), pages 2180– 2197, 2024

    2024

  32. [32]

    Syn- thesizing efficient super-instruction sets for ethereum virtual machine

    Xiaowen Hu, David Zhao, and Bernhard Scholz. Syn- thesizing efficient super-instruction sets for ethereum virtual machine. InACM SIGPLAN International Work- shop on Virtual Machines and Intermediate Languages (VMIL), 2024

    2024

  33. [33]

    EIP-1186: Rpc- method to get merkle proofs - eth_getproof

    Simon Jentzsch and Christoph Jentzsch. EIP-1186: Rpc- method to get merkle proofs - eth_getproof. Ethereum Improvement Proposals, June 2018. https://eips. ethereum.org/EIPS/eip-1186

    2018

  34. [34]

    EIP- 4444: Bound historical data in execution clients

    George Kadianakis, lightclient, and Alex Stokes. EIP- 4444: Bound historical data in execution clients. Ethereum Improvement Proposals, November 2021. https://eips.ethereum.org/EIPS/eip-4444

    2021

  35. [35]

    Zaverucha, and Ian Goldberg

    Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-size commitments to polynomials and their applications. InInternational Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), 2010

    2010

  36. [36]

    Partitioning of trees for minimizing height and cardinality.Information Process- ing Letters, 89:181–185, 2004

    András Kovács and Tamás Kis. Partitioning of trees for minimizing height and cardinality.Information Process- ing Letters, 89:181–185, 2004

    2004

  37. [37]

    Verkle trees

    John Kuszmaul. Verkle trees. 2019. Available at: https://math.mit.edu/research/highschool/ primes/materials/2018/Kuszmaul.pdf

    2019

  38. [38]

    Adaptive re- structuring of merkle and verkle trees for enhanced blockchain scalability.Internet of Things, 27:101315, 2024

    Oleksandr Kuznetsov, Dzianis Kanonik, Alex Rusnak, Anton Yezhov, and Oleksandr Domin. Adaptive re- structuring of merkle and verkle trees for enhanced blockchain scalability.Internet of Things, 27:101315, 2024

    2024

  39. [39]

    Aardvark: An asyn- chronous authenticated dictionary with applications to account-based cryptocurrencies

    Derek Leung, Yossi Gilad, Sergey Gorbunov, Leonid Reyzin, and Nickolai Zeldovich. Aardvark: An asyn- chronous authenticated dictionary with applications to account-based cryptocurrencies. In31st USENIX Se- curity Symposium (USENIX Security 22), pages 4237–

  40. [40]

    USENIX Association, 2022

    2022

  41. [41]

    Lvmt: An efficient authenticated storage for blockchain.ACM Transactions on Storage, 20(3), June 2024

    Chenxing Li, Sidi Mohamed Beillahi, Guang Yang, Ming Wu, Wei Xu, and Fan Long. Lvmt: An efficient authenticated storage for blockchain.ACM Transactions on Storage, 20(3), June 2024. doi:10.1145/3664818

    work page doi:10.1145/3664818 2024

  42. [42]

    Par- allelevm: Operation-level concurrent transaction execu- tion for evm-compatible blockchains

    Haoran Lin, Hang Feng, Yajin Zhou, and Lei Wu. Par- allelevm: Operation-level concurrent transaction execu- tion for evm-compatible blockchains. InProceedings of the European Conference on Computer Systems (Eu- roSys), 2025

    2025

  43. [43]

    Trafficformer: An efficient pre-trained model for traffic data

    Zhongtang Luo, Yanxue Jia, Alejandra Victoria Os- pina Gracia, and Aniket Kate. Cauchyproofs: Batch- updatable vector commitment with easy aggregation and application to stateless blockchains. InIEEE Sym- posium on Security and Privacy (S&P). IEEE, 2025. doi:10.1109/SP61157.2025.00247

    work page doi:10.1109/sp61157.2025.00247 2025

  44. [44]

    Martel, Glen Nuckolls, Premkumar T

    Charles U. Martel, Glen Nuckolls, Premkumar T. De- vanbu, Michael Gertz, April Kwong, and Stuart G. Stub- blebine. A general model for authenticated data struc- tures.Algorithmica, 39:21–41, 2004

    2004

  45. [45]

    Ralph C. Merkle. A digital signature based on a con- ventional encryption function. InAnnual International Cryptology Conference, 1987. URL: https://api. semanticscholar.org/CorpusID:28484604

    1987

  46. [46]

    The log-structured merge-tree (lsm-tree)

    Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Eliz- abeth O’Neil. The log-structured merge-tree (lsm-tree). Acta Informatica, 33(4):351–385, 1996

    1996

  47. [47]

    An algorithm and architecture co-design for accelerating smart contracts in blockchain

    Rui Pan, Chubo Liu, Guoqing Xiao, Mingxing Duan, Keqin Li, and Kenli Li. An algorithm and architecture co-design for accelerating smart contracts in blockchain. InAnnual International Symposium on Computer Archi- tecture (ISCA), 2023

    2023

  48. [48]

    Reth: Modular, contributor-friendly and blazing-fast implementation of the ethereum protocol in rust

    Paradigm. Reth: Modular, contributor-friendly and blazing-fast implementation of the ethereum protocol in rust. GitHub Repository, 2024. Available at: https: //github.com/paradigmxyz/reth

    2024

  49. [49]

    Rainblock: Faster transaction processing in public blockchains

    Soujanya Ponnapalli, Aashaka Shah, Amy Tai, Sou- vik Banerjee, Vijay Chidambaram, Dahlia Malkhi, and Michael Yung Chung Wei. Rainblock: Faster transaction processing in public blockchains. InUSENIX Annual Technical Conference (USENIX ATC), 2020

    2020

  50. [50]

    Schain: Scalable con- currency over flexible permissioned blockchain.IEEE International Conference on Data Engineering (ICDE), pages 1901–1913, 2023

    Xiaodong Qi, Zhihao Chen, Haizhen Zhuo, Quanqing Xu, Chengyu Zhu, Zhao Zhang, Cheqing Jin, Aoying Zhou, Ying Yan, and Hui Zhang. Schain: Scalable con- currency over flexible permissioned blockchain.IEEE International Conference on Data Engineering (ICDE), pages 1901–1913, 2023

    1901

  51. [51]

    Sequences of games: a tool for taming complexity in security proofs.IACR Cryptol

    Victor Shoup. Sequences of games: a tool for taming complexity in security proofs.IACR Cryptol. ePrint Arch., 2004:332, 2004

    2004

  52. [52]

    Hyperproofs: Aggregating and maintaining proofs in vector commitments

    Shravan Srinivasan, Alexander Chepurnoy, Charalam- pos Papamanthou, Alin Tomescu, and Yupeng Zhang. Hyperproofs: Aggregating and maintaining proofs in vector commitments. InUSENIX Security Symposium, pages 3001–3018. USENIX, 2022

    2022

  53. [53]

    Letus: A log-structured efficient trusted universal blockchain storage

    Shikun Tian, Zhonghao Lu, Haizhen Zhuo, Xiaojing Tang, Peiyi Hong, Shenglong Chen, Dayi Yang, Ying Yan, Zhiyong Jiang, Hui Zhang, and Guofei Jiang. Letus: A log-structured efficient trusted universal blockchain storage. InCompanion of the 2024 International Con- ference on Management of Data (SIGMOD), 2024

    2024

  54. [54]

    Aggre- gatable subvector commitments for stateless cryptocur- rencies

    Alin Tomescu, Ittai Abraham, Vitalik Buterin, Justin Drake, Dankrad Feist, and Dmitry Khovratovich. Aggre- gatable subvector commitments for stateless cryptocur- rencies. InSecurity and Cryptography for Networks (SCN), volume 12238 ofLNCS, pages 45–64. Springer, 2020.doi:10.1007/978-3-030-57990-6_3

    work page doi:10.1007/978-3-030-57990-6_3 2020

  55. [55]

    Towards scalable threshold cryptosystems

    Alin Tomescu, Robert Chen, Yiming Zheng, Ittai Abra- ham, Benny Pinkas, Guy Golan-Gueta, and Srinivas De- vadas. Towards scalable threshold cryptosystems. In IEEE Symposium on Security and Privacy (S&P), pages 877–893, 2020

    2020

  56. [56]

    A semantic-integrated lsm-tree- based key-value storage engine for blockchain systems

    Qian Wei, Zehao Chen, Xiaowei Chen, Yuhao Zhang, Xiaojun Cai, Zhiping Jia, Zhaoyan Shen, Yi Wang, Zili Shao, and Bingzhe Li. A semantic-integrated lsm-tree- based key-value storage engine for blockchain systems. IEEE Transactions on Computer-Aided Design of Inte- grated Circuits and Systems (TCAD), 2024

    2024

  57. [57]

    Ethereum: A secure decentralised gen- eralised transaction ledger

    Gavin Wood. Ethereum: A secure decentralised gen- eralised transaction ledger. Ethereum Yellow Paper,

  58. [58]

    Available at: https://ethereum.github.io/ yellowpaper/paper.pdf

  59. [59]

    EIP-161: State trie clearing (invariant- preserving alternative)

    Gavin Wood. EIP-161: State trie clearing (invariant- preserving alternative). Ethereum Improvement Pro- posals, October 2016. https://eips.ethereum.org/ EIPS/eip-161

    2016

  60. [60]

    Solsdb: Solve the ethereum’s bottleneck caused by storage engine.Future Generation Computer Systems (FGCS), 160:295–304, 2024

    Cuihua Yang, Fan Yang, Quanqing Xu, Yongquan Zhang, and Junqing Liang. Solsdb: Solve the ethereum’s bottleneck caused by storage engine.Future Generation Computer Systems (FGCS), 160:295–304, 2024

    2024

  61. [61]

    Cole: A column-based learned storage for blockchain systems

    Ce Zhang, Cheng Xu, Haibo Hu, and Jianliang Xu. Cole: A column-based learned storage for blockchain systems. InUSENIX Conference on File and Storage Technolo- gies (FAST), 2023

    2023

  62. [62]

    Seer: Accelerating blockchain transac- tion execution by fine-grained branch prediction.Pro- ceedings of the VLDB Endowment (VLDB), 18(3):822– 835, 2024

    Shijie Zhang, Ru Cheng, Xinpeng Liu, Jiang Xiao, Hai Jin, and Bo Li. Seer: Accelerating blockchain transac- tion execution by fine-grained branch prediction.Pro- ceedings of the VLDB Endowment (VLDB), 18(3):822– 835, 2024

    2024

  63. [63]

    DTVM: Revolutionizing smart contract execu- tion with determinism and compatibility.arXiv preprint arXiv:2504.16552, 2025

    Wei Zhou, Changzheng Wei, Ying Yan, Wei Tang, et al. DTVM: Revolutionizing smart contract execu- tion with determinism and compatibility.arXiv preprint arXiv:2504.16552, 2025. Available at:https://arxiv. org/abs/2504.16552. A Notations (Table 4) B Formal Security Proofs This section presents rigorous security proofs for MHOT’s proof mechanisms using the s...

    arXiv 2025

  64. [64]

    Non-membership: stmt= (K,nmem) asserts K/∈ keys(T)

  65. [65]

    Multi-membership: stmt= ({(K i,Vi)}m i=1,multi) as- serts∀i:(K i,Vi)∈T

  66. [66]

    Lower bound: stmt= (Q,K r,Vr,lb) asserts lb(Q) = (Kr,Vr)

  67. [67]

    Range: stmt= ([first,last),entries,range) asserts entries={(K,V)∈T:first≤K<last}. Binding property of commitments.A fundamental security requirement is that the commitment scheme iscomputation- ally binding: no efficient adversary can produce two distinct tries with the same commitment. This property is essential for all subsequent soundness proofs. Lemma...

  68. [68]

    Parseπ= (K ′,V ′,Path) 6.returnK=K ′ GameG multi Π,A (λ): 1.pp←Setup(1 λ) 2.(R,{(K i,Vi)}m i=1,π)←A(pp) 3.b←Verify(R,({(K i,Vi)},multi),π) 4.ifb=0then return0 5.fori=1tomdo 6.π i ←ExtractSingleProof(π,i) 7.T πi ←ExtractTrie(π i) 8.if(K i,Vi)/∈Tπi then return1 9.return0 GameG lb Π,A (λ): 1.pp←Setup(1 λ) 2.(R,Q,K r,Vr,π)←A(pp) 3.b←Verify(R,(Q,K r,Vr,lb),π) ...

  69. [69]

    authentic

    Parseπ= (Q,Path,K ′,V ′,v ′,Adj,K r,Vr) 6.K ∗ ←ComputeLB(π) 7.returnK r ̸=K ∗ GameG range Π,A (λ): 1.pp←Setup(1 λ) 2.(R,first,last,entries,π)←A(pp) 3.b←Verify(R,([first,last),entries,range),π) 4.ifb=0then return0 5.r L ←ComputeRank(π.π L lb) 6.r R ←ComputeRank(π.π R lb) 7.return|entries| ̸=r R −r L Figure 10: Security games for MHOTproof system soundness....

  70. [70]

    The proof π commits to a unique leaf hash hℓ at the terminal position

  71. [71]

    If K exists in TR, its leaf must also have hash hℓ (same position, same root)

  72. [72]

    ThusH leaf(K′∥V ′∥v′) =h ℓ =H leaf(K∥ · ∥·)

  73. [73]

    extraction

    SinceK̸=K ′, the inputs differ, witnessing a collision. The collision witness is (K′∥V ′∥v′) paired with the existence guarantee that some (K∥V ∗∥v∗) hashes to the same value. In the random oracle model, this is a standard “extraction” argument; in the standard model, it suffices for the reduction. Therefore: Advnmem Π (A)≤Adv CR H (B2)(24) B.6 Proof of T...

  74. [74]

    Share the same prefix as Q up to the discriminative bits extracted before depthf

  75. [75]

    The minimum key inc j′’s subtree is found by leftmost descent, yielding lb(Q)

    Have a larger sparse partial key than c j, implying lexico- graphically larger keys. The minimum key inc j′’s subtree is found by leftmost descent, yielding lb(Q). If no right sibling exists at depthf , the algorithm backtracks to depth f−1 and repeats. This process continues until finding a right sibling or determining that no key≥Q exists (returning ⊥)....

  76. [76]

    Sub-case 4b: Undershot case with incorrect sibling.The verifier checks that the first adjustment entry is the immediate right sibling at the fork point

    If the adversary claims index j>0 at some level but the authentic leftmost child differs, the CMR reconstruction will fail unless a collision exists. Sub-case 4b: Undershot case with incorrect sibling.The verifier checks that the first adjustment entry is the immediate right sibling at the fork point. The authentic right sibling is determined by the spars...

  77. [77]

    ,cj0−1 of the root

    All keys in childrenc 0,c 1, . . . ,cj0−1 of the root

  78. [78]

    honest verification

    Keys smaller thanKwithin childc j0’s subtree. The count from (1) is: j0−1 ∑ j=0 lc(c j)(31) where lc(c j) is the leaf count of subtreec j, stored in the node’s Lfield and committed in the content hash. The count from (2) is rankc j0 (K), the rank of K within the subtrie rooted atc j0. By the inductive hypothesis: rankc j0 (K) = h−1 ∑ i=1 ji−1 ∑ j=0 lc(pat...