Authors:
(1) Oleksandr Kuznetsov, Proxima Labs, 1501 Larkin Street, suite 300, San Francisco, USA and Department of Political Sciences, Communication and International Relations, University of Macerata, Via Crescimbeni, 30/32, 62100 Macerata, Italy (kuznetsov@karazin.ua);
(2) Dzianis Kanonik, Proxima Labs, 1501 Larkin Street, suite 300, San Francisco, USA;
(3) Alex Rusnak, Proxima Labs, 1501 Larkin Street, suite 300, San Francisco, USA (alex@proxima.one);
(4) Anton Yezhov, Proxima Labs, 1501 Larkin Street, suite 300, San Francisco, USA;
(5) Oleksandr Domin, Proxima Labs, 1501 Larkin Street, suite 300, San Francisco, USA.
Table of Links
1.1. The Blockchain Paradigm and the Challenge of Scalability
1.3. Our contribution and 1.4. Article structure
2. Conceptualizing the Problem
3. Our Idea for Optimizing Trees in Blockchain
4. Efficiency of adaptive Merkle trees
5. Algorithm for Merkle Tree Restructuring
6.2. Example 1.1: Binary Tree Restructuring Through Leaf Node Swapping
6.3. Example 2.1: Restructuring a Non-Binary Tree by Adding a Single Leaf
6.4. Example 2.2: Restructuring a Non-Binary Tree Through Leaf Pair Swapping
6.5. Example 2.3: Restructuring a Patricia-Merkle Tree Fragment Through Leaf Pair Swapping
7. Path Encoding in the Adaptive Merkle Tree
8.2. Technology and Advantages
9.2. Comparison with Existing Solutions
1.1. The Blockchain Paradigm and the Challenge of Scalability
In the burgeoning landscape of blockchain technology, Ethereum stands out as a beacon of innovation and application diversity. The network's capacity to support a wide array of decentralized applications (dApps) and smart contracts has positioned it at the forefront of blockchain development. This prominence is underscored by the data depicted in Figure 1, which reveals a significant uptick in the total number of unique Ethereum addresses over the past year, surging from 219.26 million to 254.66 million [7].
However, the rapid expansion of the Ethereum network brings to light the pressing challenges associated with managing an ever-growing blockchain ecosystem. The core issue revolves around the efficient verification and management of data within the blockchain's infrastructure, a task that becomes increasingly complex as the network scales. The juxtaposition of the network's growth against the slight decrease in daily active Ethereum addresses, as shown in Figure 2, further complicates this challenge [8]. Despite a year-over-year decrease of 1.70% in daily active addresses, the fact remains that a mere 0.17% of all unique addresses engage with the network on a daily basis. This discrepancy between the total number of addresses and the proportion of active participants underscores a critical aspect of blockchain management: the network's activity is highly concentrated within a relatively small segment of the overall user base.
This concentration of activity presents a unique set of challenges in optimizing the blockchain's state tree. The state tree must be updated frequently to reflect the transactions and interactions occurring within the network, a process that is predominantly influenced by the small fraction of actively participating addresses. The need to efficiently manage and verify these updates, without compromising the integrity or performance of the network, is paramount.
Given this backdrop, our research aims to address the pressing need for an optimized approach to managing the blockchain's state tree, particularly within the context of Ethereum's rapidly expanding network. The goal of our study is to explore innovative methods for restructuring Merkle and Verkle Trees adaptively, thereby enhancing the efficiency of data verification processes. By focusing on dynamic adjustments to tree configurations in response to usage patterns, we seek to minimize verification path lengths and reduce the computational overhead associated with maintaining data integrity. This research endeavor not only aims to bolster the scalability of blockchain systems but also to contribute to the ongoing discourse on optimizing blockchain infrastructure for the next generation of decentralized applications.
This paper is available on arxiv under CC by 4.0 Deed (Attribution 4.0 International) license.