Promethon: efficient reduction of Ethereum’s world state size using red-black trees

1 Introduction

Ethereum maintains a global world state that stores account balances, contract storage, and other account-related data. This world state is implemented using a Merkle-Patricia trie (Smith, 2023), which enables efficient account lookup and deterministic verification of the entire structure. In particular, operations such as locating an account and computing the global hash can be performed in O ( k ) time, where k is the address length. In contrast, a simple array representation would require O ( n ) operations, where n denotes the total number of accounts. ¹

A key design characteristic of Ethereum is that users can permanently store data by paying only a one-time transaction fee. As a result, nodes must retain account and contract data indefinitely, even when it is never accessed again. This behavior has contributed to rapid and continuous world-state growth. A single transaction to a new address typically consumes roughly 100 bytes of persistent storage, which must be replicated across all full nodes (io, 2023). Over time, this accumulation imposes increasing storage, synchronization, and processing costs on the network (Ycharts.com, 2023).

In our work, we conducted an independent analysis of Ethereum blocks from 2024 using the BigQuery API (Google, 2024). We extracted and processed the transaction and contract-creation data to quantify dormant state growth. Our results show that in the first 6 months of 2024, 1,882,687 contracts were created, of which 1,701,693 (90.38%) were never called in the following 6 months. Over the full year, 3,036,254 contracts were created and never used again, representing 75.33% of all deployed contracts. These findings reveal a substantial volume of persistent, unused state data and highlight the need for mechanisms to reclaim storage from inactive accounts and contracts.

Several proposals have attempted to address world-state growth, including stateless clients (Buterin, 2017), state rent (GitHub, 2015), and time-based state expiry (Ethereum, 2021; Saingre et al., 2021). These efforts primarily outline conceptual directions rather than deployable solutions, and–as discussed in (Buterin, 2021)–they remain largely untested at the implementation level due to unresolved scalability, usability, and operational challenges.

In brief, the stateless client approach (Buterin, 2017) suggests storing only the Merkle-trie root in the world state while relying on block proposers or external providers to supply Merkle proofs. Although this design reduces local storage, it significantly increases dependency on external infrastructure and alters long-standing assumptions about account ownership and accessibility. Time-based expiry (Ethereum, 2021) periodically removes inactive portions of the state, but the required copying and rebuilding of account data introduces substantial overhead and becomes increasingly expensive as the state grows. State rent (GitHub, 2015) proposes the general idea of charging users for long-term storage to discourage indefinite retention, yet it does not describe an efficient algorithm for identifying, charging, and deleting expired accounts.

In this paper, we propose an efficient, concrete state-expiry mechanism that addresses these limitations. Our goal is to mitigate world-state growth while preserving Ethereum’s existing computational characteristics. Currently, transaction execution and storage operations run in O ( k ) and O ( n ) per block, respectively. Any practical solution must avoid increasing these costs–for example, replacing O ( k ) with O ( n )–and should ideally add only modest overhead, on the order of O ( log ⁡ n ).

Building on the conceptual state-rent model (GitHub, 2015), our approach periodically charges each account, every c blocks, for occupying storage in the world state. A naïve implementation that iterates over all accounts would immediately incur O ( n ) overhead and would therefore be infeasible. To overcome this limitation, we introduce a hybrid structure that combines a Red-Black Tree (Wikipedia, 2024) with the Merkle-Patricia Trie (Smith, 2023). The Red-Black Tree maintains accounts ordered by effective balance, enabling the rent mechanism to evaluate only the lowest-balance accounts during each period. Accounts capable of paying remain, while insufficient accounts are deleted efficiently.

This design supports periodic rent collection in O ( log ⁡ n ) time while preserving Ethereum’s existing execution semantics and storage properties. Further technical details are provided in Section 4.

1.1 Our contributions

1.1.1 An efficient state-expiry method

We present a practical and efficient state-expiry mechanism that limits world-state growth while preserving Ethereum’s existing computation and storage complexities. Building on the idea of state rent, our method provides a concrete algorithmic framework that avoids the O ( n ) overhead of naïve scanning approaches.

By integrating the Merkle-Patricia Trie with a Red-Black Tree into a unified structure, our method enables periodic charging and efficient identification of accounts unable to maintain their state. Because accounts are kept in balanced order by effective balance, expired accounts can be removed in O ( log ⁡ n ) without introducing significant overhead to the network.

1.1.2 Pilot implementation in the go language

We provide a pilot implementation (GitHub, 2024) in the Go programming language, the same platform used by Geth (Go Ethereum) (Ethereum, 2024), the most widely deployed Ethereum client. This implementation demonstrates the practicality of our approach and illustrates seamless integration between Merkle-Patricia tries and Red-Black Trees for efficient world-state management.

1.2 Paper organization

The remainder of this paper is organized as follows. Section 2 reviews prior efforts to address world-state growth. Section 3 introduces the required data-structure primitives. Section 4 presents our proposed mechanism. Section 6 analyzes complexity and compares related approaches. Section 7 discusses implementation details and experimental evaluation. Section 9 concludes the paper.

2 Related work

The challenge of Ethereum’s growing global state has motivated numerous research directions since the network’s inception. In this section, we review key proposals and discuss their limitations relative to our goals.

2.1 The stateless client improvement proposal

The stateless client proposal (Buterin, 2017) seeks to minimize local storage requirements by shifting responsibility for state data to external providers. Rather than storing complete account information, nodes retain only the Merkle-trie root and verify updates using Merkle proofs supplied by block proposers or third-party state providers. A related idea stores contract bytecode externally via IPFS (Norvill et al., 2018).

While effective at reducing node storage, these approaches introduce deep reliance on external databases and services. They also alter long-standing usability expectations by weakening the ability of users to manage accounts solely through private-key ownership. In practice, this represents a substantial shift in Ethereum’s operational model and introduces availability and trust concerns.

2.2 State expiry by time

State expiry by time (Ethereum, 2021) periodically removes accounts that have not been accessed within a predefined window. Although conceptually straightforward, the approach requires copying inactive accounts into new tries during transaction processing, creating bottlenecks as the state grows. Dormant accounts can also accumulate between expiry cycles, forcing nodes to retain large irrelevant portions of state. Moreover, selecting an appropriate expiry interval is difficult: short intervals incur heavy processing costs, while long intervals fail to meaningfully constrain growth.

2.3 State rent

State rent (GitHub, 2015) proposes shifting from one-time storage fees to recurring charges based on the amount and duration of stored data. This model encourages users to free unused storage rather than occupying the world state indefinitely. However, the proposal leaves unresolved the central algorithmic challenge: efficiently determining which accounts must pay, assessing solvency, and deleting expired entries at scale.

Our work provides a concrete mechanism that operationalizes the state-rent concept. By integrating a Red-Black Tree into the Merkle-Patricia trie, we maintain accounts in sorted order by effective balance, allowing the system to evaluate only the minimum-balance account at each step. If this account is solvent, the remaining accounts are guaranteed to be solvent as well; otherwise, deletion proceeds efficiently. This design transforms state rent from a conceptual proposal into an implementable algorithm.

3 Preliminaries

In this section, we will provide a concise overview of the foundational data structures employed in our scheme.

3.1 Red-black tree

When it comes to the crucial tasks of searching and sorting data, the binary search tree stands out. However, the performance of a binary search tree is heavily contingent on its structure, and in the worst-case scenario, it can degrade into a linear structure with a time complexity of O ( n ).

The red-black tree, first introduced in (Guibas and Sedgewick, 1978) and later refined through a series of subsequent works (Andersson, 1993; Okasaki, 1999; Cormen et al., 2001), provides an efficient data structure for balancing binary search trees. It shares similarities with a binary search tree, but distinguishes itself by ensuring an upper-bound complexity of O ( log ⁡ n ) for insertion and deletion operations. Within a red-black tree, each node is categorized as either red or black. While the search complexity remains at O ( log ⁡ n ) for both red-black trees and binary search trees, the red-black tree guarantees a time complexity of O ( log ⁡ n ) following any insertion or deletion. It’s crucial to note that in a binary search tree, insertions or deletions can, in their worst-case scenarios, lead to a complexity of O ( n ). Red-black trees secure a time complexity of O ( log ⁡ n ) by meticulously maintaining the balance of the binary tree. This is achieved through a corrective algorithm known as the fix-up procedure, which is executed immediately after a node is inserted or deleted. The fix-up procedure restores the tree’s balance and ensures all properties are met by performing a series of targeted adjustments, primarily through recoloring nodes and performing rotations to restructure the tree. This entire restoration process has a time complexity of O ( log ⁡ n ), which is what preserves the tree’s overall efficiency.

In fact, a red-black tree is a type of self-balancing binary search tree with additional properties to ensure efficient performance for insertion and deletion operations. The key properties of a red-black tree are as follows.

• Property 1: Each node is either red or black.
• Property 2: The root is always black.
• Property 3: All leaves (NIL nodes) are black.
• Property 4: If a node is red, both its children must be black (i.e., no two red nodes can be adjacent).
• Property 5: Every path from a node to its descendant NIL nodes must have the same number of black nodes, known as the black-height.

As an example, the trees depicted in Figure 1 do not satisfy the essential properties required for a valid red-black tree. Specifically, these configurations exhibit several violations.

• The left and middle trees violate property 5. They exhibit inconsistencies in the black-height across different paths from the root to the leaves, where the number of black nodes is not the same.
• The right tree violates property four by containing adjacent red nodes, which is not allowed. According to Property 4, if a node is red, both its children must be black to ensure no two red nodes are adjacent.

In contrast, the trees shown in Figure 2 conform to all the necessary properties of red-black trees. By satisfying these properties, the trees in Figure 2 ensure that the red-black tree operations are efficiently managed, providing a worst-case time complexity of O ( log ⁡ n ). This structural integrity is crucial for maintaining balanced operations and ensuring performance even as the dataset grows.

3.2 Merkle-Patricia trie

The Merkle-Patricia trie is a pivotal data structure in blockchain technologies like Ethereum, merging the concepts of Merkle trees and Patricia tries to efficiently store and verify key-value pairs. Building upon Ralph Merkle’s 1988 innovation for digital signatures (Merkle, 1987), it has become an ubiquitous tool for data verification. In traditional data structures, recalculating the hash of a complete database due to a single element change requires the hashing of all the elements of the database, resulting in a time complexity of O ( n ). In contrast, a Merkle-Patricia trie achieves this with a significantly improved time complexity of O ( k ) where k is the length of the key (Account address in Ethereum). This tree-based data structure ensures that each non-leaf node represents the hash of its child nodes. All leaf nodes reside at the same depth and are positioned as far left as possible.

Figure 3 illustrates the hierarchical structure of a Merkle-Patricia trie. At the top of the structure, the root hash represents the cryptographic summary of the entire data stored within the trie. This root hash acts as the entry point, allowing users to verify the integrity of the entire database efficiently. Moving down from the root, intermediate nodes, such as ”hash 1″ and ”hash 16″ store hashes computed from their respective child nodes. For example, ”hash one″ is the cryptographic sum of the hashes from hash 17 to hash 32, each representing a portion of the data stored further down the trie.

In this figure, each intermediate node is labeled with a key, which represents a specific part of the key-value pair path within the trie. For instance, ”key: 0″ at the level of ”hash 1″ corresponds to all data that shares the common prefix ”0″ in their keys. Further down, the node with the key ”00″ under ”hash 17″ indicates that all child data of this node shares the prefix ”00″ in their keys. This process of using keys continues recursively down the structure.

The base layer of the structure, called leaf nodes, holds the actual key-value pairs. The key feature of the Merkle-Patricia trie is that even a single modification to any of these leaf nodes will trigger changes in the hashes of all intermediate nodes up to the root, ensuring the validity and integrity of the structure. Despite this cascading effect, the structure allows for efficient updating and verification, with changes propagating only along the affected branches. This is why the time complexity remains constant at O ( k ), where k is constant.

This property of the trie enables efficient comparison between different versions of the database, allowing for quick identification of inconsistencies or changes.

In our system, we merge these two structures into a single hybrid state representation.

4 Proposed solution

We begin this section with an overview of our scheme, followed by a more detailed description of the internal mechanisms of our solution.

4.1 Overview

Our innovative solution involves a fundamental modification to the logic of the system. We have introduced a mandatory rental fee for each account to persistently store its data in the world state. In contrast to the current Ethereum approach, where the cost is incurred only once during the transaction that saves the data, our model ensures an ongoing expense for maintaining account data. This strategic shift aims to mitigate the accumulation of dormant accounts and contract data, which occurs when there is no ongoing cost associated with retaining data on the blockchain.

To implement this, we designed a mechanism that deducts a nominal amount from all accounts per block, proportional to their storage trie usage. If an account’s balance decreases to zero due to these deductions, the account is automatically deleted. This approach not only optimizes resource allocation by discouraging accumulation of unnecessary accounts but also fosters a more efficient and streamlined blockchain ecosystem.

However, reducing the amount from each account presents a significant challenge, as it requires iterating over the entire dataset. In the context of the Ethereum blockchain, which, as of 20 July 2025, has over 328 million accounts, performing such an operation with every block creation–occurring approximately every 12 seconds–is impractical.

One initial idea involves organizing all accounts in ascending order and placing them in an array. By exclusively managing the account with the minimum balance, we can ascertain whether other accounts have a zero balance. However, this approach presents a drawback: if any account conducts a transaction, altering its position in the array necessitates a rearrangement with a time complexity of O ( n ).

To overcome this limitation, we introduce a unified hybrid data structure that merges the ordering properties of a Red-Black tree directly into the leaf layer of the Merkle-Patricia trie. Instead of maintaining two separate data structures and synchronizing pointers between them, the account’s trie leaf is extended with Red-Black tree metadata, enabling efficient balance-based ordering and updates within the same structure. This merged design (Figure 4) preserves the native O ( k ) lookup behavior of the trie while achieving O ( log ⁡ n ) reordering performance, allowing accounts to be efficiently updated, reorganized, or deleted without the overhead of traversing or modifying two independent structures.

The dilemma lies in the fact that the current Ethereum implementation executes transactions with a time complexity of O ( k ), and shifting to O ( n ) would not constitute an enhancement. On top of that, considering the number of accounts on the Ethereum platform, executing numerous transactions with an O ( n ) complexity on existing hardware is deemed unfeasible.

To overcome this obstacle, our solution involves several modifications, the most significant of which is the implementation of a red-black tree instead of an array to organize accounts in ascending order. By leveraging a red-black tree, we can rearrange accounts with a more manageable time complexity of O ( log ⁡ n ), providing an optimized solution to the challenges posed by the dynamic nature of account positions in a rapidly evolving blockchain environment. Additionally, instead of maintaining the balances in the world-state trie, we store a pointer for each account to its associated node in the red-black tree. The account balances, as well as other parameters such as the last block in which an account was modified, are also kept in the red-black tree nodes.

As illustrated in Figure 5, our proposed solution integrates the Merkle-Patricia trie with a red-black tree to optimize the management of Ethereum’s world state. The left side of the figure depicts the Merkle-Patricia trie, which organizes account addresses in a hierarchical structure for efficient lookups. Each leaf node in the trie corresponds to an account and contains a two-way pointer to a node in the red-black tree, shown on the right side of the figure.

To elaborate, each leaf node within the Merkle-Patricia trie acts as a reference to a specific red-black tree node responsible for storing the values associated with the mapped account. This symbiotic relationship allows for a dynamic and efficient organization of account data.

In terms of key assignments, the Merkle-Patricia trie utilizes account addresses as keys. Conversely, the red-black tree employs dual keys for each node.

• Balance of the account: Reflecting the balance in Ether of the associated account.
• Last block modification: Capturing the last block number in which the account’s balance was modified.

This dual-key system ensures nuanced and granular tracking of account modifications within the red-black tree, enhancing the robustness and precision of our overall data management strategy. By utilizing dual keys, we can sort accounts based on both their balance and the amount of storage tree they have used over time. This sorted data structure allows us to efficiently detect and potentially delete accounts (and their associated storage space) that are inactive or lack sufficient balance to cover their storage costs on the Ethereum network.

4.2 Scheme details

To provide a comprehensive understanding of our proposed method and to enhance its modularity, we have structured the entire process into a number of distinct algorithms. The list of algorithms and the parameters are listed in Table 1. During the creation of the each block, the miner which is creating a block invokes two algorithms in sequence, namely, E x e c T r a n s and C h e c k Z e r o.

TABLE 1. Parameters and algorithms used in our solution.

In the subsequent sections, we describe the functionality of these algorithms within our scheme.

4.2.1 E x e c T r a n s algorithm

This algorithm is dedicated to executing transactions. Each transaction involves a sender s, receiver r, and a transaction value v. The algorithm comprises the following steps:

• Traverse the red-black tree node mapped by the Merkle-Patricia trie address of the sender.
• Calculate the storage fee of the sender s using the following formula (Equation 1):

S t o r a g e F e e s = C u r B l o c k − L a s t M o d s × A c c B y t e s s × P r i c e B y t e (1)

Intuitively, the above formula calculates the storage fee accumulated since the account was last charged for its storage usage. We determine this by counting the number of blocks since the last rent payment and multiplying it by the storage fee per block. The storage fee amount is proportional to the account’s storage usage.

• 3. Update the sender’s temporary account balance using the following formula (Equation 2):

B a l a n c e s = B a l a n c e s − S t o r a g e F e e s (2)

• 4. In the next step, we first ensure that the sender’s temporary balance does not fall below zero after the storage fee payment. If the balance remains sufficient, we proceed with the transaction; otherwise, we revert it.

More formally, we check if ( B a l a n c e s ≥ v ). If f a l s e, we revert the transaction and undo the sender balance update. If t r u e, we proceed with the transaction and calculate the new balance of the receiver account using (Equation 3) and update both account balances in the red-black tree based on Equation 4:

S t o r a g e F e e r = C u r B l o c k − L a s t M o d r × A c c B y t e s r × P r i c e B y t e (3)

B a l a n c e r = max 0 , B a l a n c e r + v − S t o r a g e F e e r (4)

Note that negative balances are not allowed, which is why we use the M a x function in the above formula.

• 5. Update the last modified value of the sender’s and receiver’s accounts to the current block number in their respective red-black tree nodes by setting L a s t M o d s = C u r B l o c k and L a s t M o d r = C u r B l o c k.
• 6. Perform a fix-up operation on the RB-ordered layer of the unified trie to ensure the data structure maintains an ordered storage of account balances. A number of illustrative examples in which the fix-up process is performed will be presented later.

This E x e c T r a n s algorithm is performed during the validity check, alongside verifying the transaction’s signature. If the signature is invalid, the block creator can select another transaction from the pool, ensuring that invalid transactions do not impact their block reward. It is important to note that temporary balances are stored in memory, not in storage, and will be deleted after execution.

Figures 6–9 illustrate some examples for our proposed Ethereum world state storage structure, which integrates both a Merkle-Patricia trie and a red-black tree. In these figures, the red-black tree is depicted upside down, with the leftmost node appearing as the rightmost node in the diagrams. The Ethereum world state contains three accounts, each represented by a node that stores the account’s balance and the last-modified block number. The bidirectional arrows indicate that the leaf node points to its corresponding account node, and the account node points back to the account’s address.

Figure 6 demonstrates a sample scenario in which part of the Ethereum world state and the proposed data structures for three Ethereum accounts are shown at block number 991,000. The state depicted in this figure represents the initial situation where no transactions have yet been processed. The leaf nodes in the Merkle-Patricia trie are linked to their corresponding nodes in the red-black tree. As described in the scheme details, each red-black tree node stores an account’s balance and the last block number in which the account was modified. The nodes in the red-black tree are sorted based on their balance values, with the highest balance on the left and the lowest balance on the right. Assume each of these accounts occupies only 1 byte in the storage tree, and the P r i c e B y t e value is 1 Wei.

Now, let’s consider the first scenario where account B attempts to send 110,000 Wei to account A. Although account B initially has sufficient balance, after paying the rent, it is left with only 9,000 Wei, which is insufficient to complete the transaction. Therefore, the transaction is not performed. The calculations are as follows:

s = B , v = 110000 , r = A C u r B l o c k = 991,000 L a s t M o d B = 887,980 B a l a n c e B = 112,020 S t o r a g e F e e B = 991,000 − 887,980 × 1 × 1 = 103,020 B a l a n c e B = 112,020 − 103,020 = 9,000

Now, consider Figure 6 again, and this time we focus on the second scenario where account C wishes to transfer seven million Wei to account A. After applying the E x e c T r a n s algorithm, the final balance for both accounts will reflect the amount remaining after the transfer, minus the fees they owe the network. The following calculations illustrate the rationale behind this example:

s = C , v = 7,000,000 , r = A C u r B l o c k = 991,000 L a s t M o d C = 544,333 B a l a n c e C = 12,004,338 S t o r a g e F e e C = 991000 − 544333 × 1 × 1 = 446,667 B a l a n c e C = 12004338 − 446667 − 7000000 = 4,557,671

And for the receiver account A, we calculate the storage fee and update its balance based on the storage fee and the received amount as follows:

S t o r a g e F e e A = 991000 − 990517 × 1 × 1 = 483 B a l a n c e A = max 0,2000110 + 7000000 − 483 = 8,999,627

As a result of these adjustments, their positions in the red-black tree will change, with account A now holding the highest balance relative to the space it occupies. The updated data structures are illustrated in Figure 7.

4.2.2 C h e c k Z e r o algorithm

The C h e c k Z e r o algorithm is used for finding and deleting accounts whose balance is zero or less. This algorithm proceeds as follows. - If the condition holds, just update the account balance. No further modifications are required, as all accounts possess a value greater than zero based on Equation 7:- If the condition does not hold, the account is marked for deletion. Consequently, remove the account from both the Merkle-Patricia trie and the red-black tree. After deleting from red-black tree, do a fix-up.

• Traverse the red-black tree by navigating to the leftmost branch to identify the node with the minimum value. We denote this node as r b left.
• Calculate the storage fee of r b left based on Equation 5:

S t o r a g e F e e r b left = C u r B l o c k − L a s t M o d r b left × A c c B y t e s r b left × P r i c e B y t e (5)

• 3. Verify the condition based on Equation 6:

B a l a n c e r b left − S t o r a g e F e e r b left > 0 (6)

B a l a n c e r b left = B a l a n c e r b left − S t o r a g e F e e r b left (7)

• 4. Repeat the algorithm, starting from the first step, until an account with a total value greater than zero is encountered.

It is important to note that the account’s aggregate balance is maintained only in memory during the execution of the algorithm and is not written to persistent storage. This design avoids unnecessary state growth, ensures that temporary computation artifacts are discarded automatically after execution, and keeps storage overhead minimal.

Figures 8, 9 illustrate the operation of the C h e c k Z e r o algorithm. Figure 8 shows a sample scenario at block 1,000,000 with three accounts before running the C h e c k Z e r o algorithm. For simplicity, we assume, as in previous scenarios, that the storage fee is one Wei per byte per block, and each account occupies only 1 byte. Accounts are ordered based on their current balance, which is calculated by subtracting the storage fee from the stored balance. Therefore, account B, which holds the smallest amount in this world state tree, is the only one that needs to be checked for potential deletion. Block 1,000,000 is the last block in which account B will be present if no additional Ether is sent to it. This is because its current balance is 112,020 Wei, and the fee it must pay is the difference between the current block and the last block it was modified:Consequently, at this block, the total balance becomes:In the subsequent block, the balance drops below zero, leading to the account’s deletion.

1,000,000 − 887,980 = 112,020 Wei

112,020 − 1,000,000 − 887,980 = 0 Wei

Figure 9, depicts the situation in the next block where account B has been deleted and the red-black tree has been updated accordingly.

4.3 Consistency of the cryptographic layer

The Merkle-Patricia trie that anchors Ethereum’s world state (Smith, 2023) provides two cryptographic guarantees that any state-management mechanism must preserve. First, it produces a single root hash that commits to all account key-value bindings stored in the trie; this root hash serves as the global state commitment included in every block header. Second, for any individual account address, a Merkle proof of length O ( k ) – where k is the address length in nibbles–suffices to demonstrate that a particular value is bound to that address under the committed root, enabling light-client verification and stateless validation. Both guarantees rely on the property that, given the same set of key-value bindings, all validators compute byte-identical leaf nodes and therefore byte-identical hashes up to the root.

The Promethon design preserves both guarantees by construction. The unified red-black tree metadata stored in each leaf node–the colour bit and the parent, left, and right pointers–refers to other nodes by their account addresses rather than by memory addresses or any node-local identifier. Account addresses are deterministic and globally consistent across validators, since they are derived from user public keys and contract-creation parameters in a manner that is already part of Ethereum’s consensus rules. The red-black tree operations (insertion, deletion, and the associated fix-up procedure) are themselves part of the prescribed state-transition function and are executed identically by every validator; this is the property that forces all validators to converge on the same red-black tree structure, since the red-black invariants alone do not uniquely determine the tree (multiple valid colourings and structures exist for the same set of keys, and determinism comes from the algorithm rather than from the data-structure properties). Consequently, the leaf nodes contain byte-identical fields across validators, the leaf hashes are identical, the Merkle proofs for any address are identical, and the final Merkle root hash is the same in all validators. The integrity guarantees of the original Merkle-Patricia trie–global commitment via the root hash and per-key proofs of length O ( k ) – are therefore preserved without modification.

5 Economic analysis and threat model

The rent mechanism introduced in Section 4.2 raises three economic questions that we address in this subsection: how the rent formula is justified, how the rent should be distributed once collected, and how the mechanism behaves under adversarial conditions. The objective is to demonstrate that the choices underlying the rent mechanism follow standard storage-pricing economics, that the distribution of collected rent admits well-defined design alternatives with explicit trade-offs, and that the mechanism is robust against the most natural adversarial strategies.

5.1 Rent formula and lazy collection

The storage fee defined in Equation 1 of Section 4.2 follows the standard time × space × unit-price model used by commercial storage markets (Amazon Web Services, 2026; Google Cloud, 2026) and by decentralised storage protocols such as Filecoin (Filecoin Foundation, 2026), all of which price storage according to the formula Total Cost = Price × Size × Duration, directly analogous to Promethon’s per-block rent. Under this model, an account’s fee accrues at a rate proportional to the bytes it occupies, integrated over the number of blocks since its last interaction with the chain. This pricing structure is the natural economic model for occupying shared persistent state, and the parameter P r i c e B y t e is the per-byte-per-block unit price.

A naive instantiation of this model would require charging every account at every block, incurring O ( n ) overhead per block and making the mechanism infeasible at Ethereum’s scale. Promethon instead collects rent lazily through two complementary paths defined in Section 4.2. First, at transaction time, the ExecTrans algorithm charges the sender for the rent accrued since L a s t M o d s, capturing the full notional rent for the entire dormant period in a single O ( k ) lookup and an O ( log ⁡ n ) re-ordering. Second, at the end of each block, the CheckZero algorithm evaluates only the leftmost account in the red-black tree; because the tree is sorted by effective balance, termination on the first solvent account is sufficient to certify that no other account is in deficit. The combination of these two paths ensures that every byte-block of state usage is charged exactly once over time, while the per-block work performed by the protocol remains O ( log ⁡ n ) plus O ( m ⁡ log ⁡ n ) for the (typically very small) number m of accounts deleted in a given block. The rent mechanism is therefore not ad hoc but a deliberate restatement of standard storage pricing under the implementation constraint that no per-block sweep over all accounts is permitted.

5.2 Distribution of collected rent

Once rent is charged, the protocol must specify where the collected Wei goes. Within the algorithmic design of Promethon, two viable distribution models are available; both are compatible with the rest of the mechanism and differ only in where the collected value flows. We describe each in turn and discuss the trade-off.

5.2.1 Method a–aggregate validator reward

Under this model, the protocol maintains a single additional field in the world state, denoted T o t a l B y t e s, equal to the sum of A c c B y t e s across all accounts. The field resides under the global Merkle-Patricia root and is therefore consistent across validators, and it is updated in O ( 1 ) on every operation that alters storage: account creation increases T o t a l B y t e s by the new account’s byte count, account deletion in CheckZero decreases it accordingly, and contract storage writes adjust it by the net change. At the end of every block, the block proposer receives an additional reward equal to T o t a l B y t e s × P r i c e B y t e Wei, credited to the coinbase balance through the standard block-reward mechanism.

Intuitively, this quantity corresponds to the per-block notional rent on the entirety of the world state being maintained by the network, paid to the validator in aggregate rather than per account. Individual accounts continue to be charged lazily, through ExecTrans and CheckZero, so the two flows match in expectation over time: the aggregate per-block payout to validators equals, on average, the aggregate rent collected from accounts. The principal advantage of this model is that validator compensation is smooth and predictable, scaling directly with the size of the state under maintenance. The principal limitation is that validators benefit from a larger T o t a l B y t e s, which is misaligned with the network-level goal of reducing state size; however, validators have no unilateral ability to inflate T o t a l B y t e s, since account creation requires user-signed transactions and CheckZero deletions are part of the state-transition function and cannot be omitted without producing an invalid block.

5.2.2 Method b–rent burning

As an alternative, rent collected via ExecTrans and CheckZero is permanently destroyed (burnt) rather than redistributed, mirroring the base-fee burning mechanism introduced by EIP-1559 (Buterin et al., 2019). Validators receive no direct compensation for rent collection; instead, all Ether holders benefit symmetrically through the mild deflationary pressure produced by burning.

The principal advantage of this model is that it presents the cleanest possible incentive structure for the goals of this work: validators have no economic interest in either expanding or shrinking the state, eliminating any incentive to manipulate transaction ordering, account creation, or block contents with respect to storage. The marginal computational cost of running CheckZero each block is O ( log ⁡ n ), negligible relative to the existing per-block validator workload, so the absence of dedicated compensation does not materially affect validator economics. The principal limitation is the symmetric one: validators are not directly rewarded for the storage they maintain, and the broader benefit accrues to all Ether holders rather than to the parties performing the work.

5.2.3 Comparison

Both methods are fully consistent with the algorithmic design of Promethon and require only a localized change to where the collected rent is sent; neither affects the time or storage complexity of any operation. Method A is preferable when the design priority is to compensate validators directly and predictably for the storage they maintain, while Method B is preferable when the design priority is to minimize validators’ economic interest in state-size growth and to allow the rent mechanism to act as a network-wide deflationary force. The choice between the two is a tokenomics and governance question rather than an algorithmic one and, in our view, is best decided through the same governance process by which Ethereum has decided analogous issues, such as the disposition of EIP-1559 base fees.

5.3 Threat model

We consider four representative adversarial scenarios against the rent mechanism and analyse each in turn.

• State-bloat/spam. An adversary creates a large number of low-balance accounts with the intent of inflating the world state. Every such account accrues rent under the same rules as legitimate accounts; the adversary either continues to fund them, in which case rent is paid into the network in line with the storage they consume, or the accounts fall to the minimum-balance position and are removed by CheckZero. The attack is self-funded from the network’s perspective and self-mitigating in the absence of continued funding.
• Targeted deletion of a victim account. An adversary seeks to force the deletion of an account they do not control. Deletion is determined exclusively by the tuple ( B a l a n c e , L a s t M o d ) and A c c B y t e s, all three of which can only be reduced by the account owner through outgoing transactions or storage growth. External parties can transfer Wei to the target–which strictly extends its life–but have no protocol-level mechanism to drain or expire it. The attack is structurally impossible.
• Dishonest validator. A validator omits rent application, skips a required CheckZero deletion, or otherwise produces a block inconsistent with the prescribed state-transition function. Because the rent updates and deletions are part of the state-transition function, any such deviation produces a state root that diverges from that computed by honest validators on the same block. The block fails attestation and is not finalized; the dishonest validator forfeits the proposer reward and any reward distributed under Method A above.
• Loss of dormant legitimate accounts. A legitimate user remains offline long enough for their account balance to be drained by rent and the account to be removed by CheckZero. We acknowledge this as a genuine usability limitation rather than a mitigated attack. Two design parameters bound the risk: first, P r i c e B y t e is a governance-level parameter that can be set conservatively to provide multi-year survival windows for typical account balances; second, users may pre-fund their accounts with an arbitrarily large rent buffer prior to going offline. Mechanisms for state revival from external proofs, analogous to those proposed in the time-based state-expiry literature (Buterin, 2021), are compatible with the present design and may be incorporated as future work.

6 Complexity analysis and comparison

Performing transactions, executing blocks, and managing data storage are crucial operations for every full node within the Ethereum network. The current version of Ethereum accomplishes these tasks with specific computational complexities.

• Executing blocks: The execution of each block, containing m transactions, is performed with a time complexity of O ( m ).
• Executing transactions: Transaction execution has a time complexity of O ( k ), where k is the length of account address.
• Storage complexity: Storing data in the Merkle-Patricia trie requires O ( n ) space

When contemplating new solutions, particularly for managing unused accounts, it is imperative that the proposed approach does not exacerbate the computational complexities of these algorithms. The Ethereum network heavily relies on the efficiency of these functionalities. Any increase in complexity, for example, from O ( k ) to O ( n ) for transaction execution, has the potential to disrupt network operations. This is a critical concern as n can be a substantial number, and a significant rise in complexity could render nodes inoperable, jeopardizing the overall functionality of the Ethereum network. Therefore, any enhancements or improvement proposals should be carefully considered and implemented to ensure the seamless operation of the Ethereum network.

In Ethereum, each account address is a unique 20-byte (160-bit) value, giving a maximum possible number of distinct accounts n of 2 160. In a red-black tree data structure, the number of steps required for an operation is O ( log ⁡ n ). Since n ≤ 2 160, it follows that log ⁡ n ≤ 160. For comparison, Ethereum’s Merkle Patricia Trie operates with a complexity of O ( k ), where k is the length in bits of a key, and k = 160 bits = 40 nibbles for Ethereum addresses. In the trie, each hexadecimal character (nibble, 4 bits) corresponds to one step in the lookup process. Therefore, for any practical and theoretical value of n in Ethereum, our new time complexity of O ( log ⁡ n ) is always bounded above by O ( 4 k ). Furthermore, the current number of accounts in Ethereum is much less than 2 40, meaning that in practice O ( log ⁡ n ) is also substantially better than O ( k ) today.

Building upon the preceding discussion, the complexity analysis of our proposed solution can be summarized as follows.

• Transaction execution: Finding and modifying data in the Merkle-Patricia trie is crucial for executing transactions on the current Ethereum network. The proposed method involves replacing the leaf nodes of the Merkle-Patricia trie with nodes of a red-black tree. The process of finding data remains unchanged and continues to have a time complexity of O ( k ). Modifying data involves updating the key value of the red-black tree node that the Merkle-Patricia trie points to. This operation has a time complexity of O ( 1 ) with a low constant. After modification, a fix-up on the red-black tree is required to maintain its properties which is done with the complexity of O ( log ⁡ n ).

In summary, the overall complexities for different tasks in the transaction execution step are as follows.

• Find the sender’s account and perform the operation: O ( k )
• Find the receiver’s account or create if non-existent: O ( k )
• Check if the sender has sufficient balance: O ( 1 )
• Update the sender’s or the receiver’s account balances: O ( 1 )
• Perform fix-up on the red-black tree: O ( log ⁡ n )

Hence, the overall complexity for transaction execution is O ( k + log ⁡ n ), which is approximately O ( log ⁡ n ).

• 2. Executing blocks: In the execution of blocks, Ethereum processes all transactions within and then nodes execute the consensus algorithm to ensure network security. Our proposed approach retains the majority of Ethereum’s processes but introduces the deletion of accounts with zero or negative balances. Utilizing the red-black tree, the algorithm efficiently identifies the account with the least Ether amount and iterates through the leftmost part of the tree to delete accounts with zero or negative balances.

The loop iterates m times (where m is the number of accounts to be deleted), with each deletion having a time complexity of O ( log ⁡ n ). Therefore, the total time complexity for account deletion is O ( m k + m ⁡ log ⁡ n ), which is approximately O ( m ⁡ log ⁡ n ), where m is the fraction of accounts to be deleted and is assumed to be only a small fraction of the total n accounts.

• 3. Storing data in storage: Storing n accounts in the Merkle-Patricia trie and n account details in the red-black tree each have a storage complexity of O ( n ). Therefore, the overall storage complexity for this step is O ( n ) + O ( n ) = O ( n ), aligning with the storage complexity of the current version of Ethereum.

Table 2 summarizes the comparison between our proposed solution and previously suggested approaches. It is important to note that these other approaches–such as time-based state expiry and the State Rent concept–were originally presented only as high-level ideas, without detailed implementation guidance. For the purpose of comparison, we assume a straightforward linear mechanism for identifying accounts eligible for deletion in the State Rent model. Despite these assumptions, the table highlights the efficiency and practicality advantages of our method relative to these conceptual proposals.

TABLE 2. Complexity comparison. n: number of accounts. p: bytes that all of the accounts take up. k: length of address. m: number of accounts that should be deleted after each block (Typically very small).

The linear approach operates by iterating over all accounts in the system at the conclusion of each new block. Its canonical implementation performs a scan over every account to determine which accounts, if any, need to be removed or updated based on block-level changes. For each account that must be deleted, the algorithm executes a removal from the Merkle-Patricia trie, as discussed earlier, has a time complexity of O ( k ) per operation, where k denotes the length of the address of the account. Consequently, for a given block, the algorithm incurs an O ( n ) overhead to iterate and inspect all n accounts, plus an additional O ( m k ) cost to remove m matching accounts from the matrix. This results in a total time complexity of O ( n + m k ) per block.

In summary, the proposed solution demonstrates favorable computational complexities, maintaining efficiency in transaction execution and block processing, while introducing a streamlined approach to account deletion with negligible impact on overall performance. Storage complexities also remain consistent with the existing Ethereum architecture.

7 Implementation and experimental results

To evaluate the efficiency of the proposed approach, we implemented our proposed data structure and performed practical experiments using historical data from the real Ethereum blockchain. We refer to the new structure as PromethoniXTrie. It creates a Merkle-Patricia trie in which every value is a node of a Red-Black tree, establishing the desired connection between them to test the performance of the Promethon idea. The implementation code and all codes used for the benchmarking are publicly available on GitHub (GitHub, 2024) for interested researchers.

Before detailing the implementation, it is important to clarify the focus of our evaluation. Regardless of the underlying data structure, when the same rent algorithm and logic are applied, the number of deleted accounts and the total amount of freed storage must remain identical across all approaches. What differs, however, is the efficiency with which these deletions can be detected and executed. Our contribution is the introduction of a data structure that performs this process with significantly improved time complexity. Therefore, in this implementation we focus primarily on examining the feasibility and performance characteristics of the proposed unified data structure, rather than on fine-tuning or optimizing the rent-collection algorithm itself.

7.1 Test environment

The benchmark tests were conducted on a MacBook Pro 2023 with the following specifications.

• Processor Chip: Apple M3 Pro
• Memory: 36 GB

7.2 Generating the sample dataset

To obtain a realistic workload, we sourced our dataset directly from the public Ethereum blockchain using BigQuery (Google, 2024). Specifically, we retrieved the first 1,000,000 transactions to accurately reflect actual transaction patterns without synthetic scaling or artificial modification. The following SQL query was used on the BigQuery platform (Google, 2024) to access the data.

Screenshot of an SQL query selecting all columns from the bigquery-public-data.crypto_ethereum.transactions table, ordering results by block_timestamp in ascending order, and limiting output to 1,000,000 rows. Syntax highlighting uses green for SQL keywords.

An example of a single transaction record obtained from the query is as follows.

Screenshot showing JSON-formatted Ethereum blockchain transaction data, including fields for hash, nonce, transaction index, sender and recipient addresses, value, gas, gas price, timestamp, and block number, with some values abbreviated.

For our benchmarks, we focused on key fields including b l o c k _ n u m b e r, b l o c k _ t i m e s t a m p, f r o m _ a d d r e s s, t o _ a d d r e s s, and v a l u e to simulate typical account-based transactions and state transitions within our data structures.

Our objective was to compare how efficiently our proposed PromethoniXTrie structure could process these transactions versus a baseline approach. The Linear approach iterates through all accounts at each new block (with O ( n ) time complexity), whereas PromethoniXTrie is specifically designed to scale more efficiently with dataset size.

7.3 Implementation of key operations in Promethon

In this section, we provide detailed implementations for the core operations of adding, modifying, and deleting accounts in the Promethon system. These operations maintain the integrity of the merged Merkle-Patricia trie structure (Figure 4), where the Merkle-Patricia trie (for efficient account lookups by address) incorporates the red-black tree directly into its leaf nodes. Each leaf node in the Merkle-Patricia trie includes red-black tree information: a bit indicating if it is red or black, pointers (as account addresses) for left child, right child, and parent, along with the account’s balance, last modification block, and other data. The red-black tree is overlaid on these leaf nodes, with nodes identified by their account addresses. The composite key for sorting in the red-black tree is primarily by balance (in ascending order), with ties broken by the last modification block number (also ascending). This ensures that the leftmost node always represents the account with the lowest effective balance after storage fees. Since the red-black tree pointers and colors are stored in the leaf node data, which contributes to the Merkle-Patricia trie’s root hash, the integrity of the red-black tree structure is verifiable alongside the Merkle-Patricia trie.

Key necessities for these operations include.

• Address-based pointers: Left, right, and parent pointers in each leaf node are account addresses, allowing navigation of the red-black tree by looking up addresses in the Merkle-Patricia trie.
• Key changes require reinsertion: Since the red-black tree is sorted by balance and last modification, any modification to these values changes the node’s sort position. Thus, modifications require removing the node from its current position in the red-black tree and reinserting it with the new key, triggering standard red-black tree fixup operations (rotations and recoloring to maintain balance and properties).
• Fixup in merged structure: The fixup is the standard red-black tree fixup, performed using address-based navigation. No additional reference updates are needed beyond updating the pointers (addresses) in the affected leaf nodes, as the structure is unified. Standard red-black tree fixup handles balance (O ( log ⁡ n ) traversals, each O ( k ) for address lookups).
• Storage fee calculation: Integrated into operations where balance changes, using Formula 1 in Section 4.2. Note that balances cannot go negative.
• Assumptions: All operations assume access to the root of the Merkle-Patricia trie (MPT_root) and the address of the red-black tree root (RB_root_addr, which is an account address or null). Errors (e.g., insufficient balance) revert changes atomically. Operations are atomic to maintain blockchain consistency. Null pointers are represented by a sentinel address (e.g., 0x0).

Below, we provide pseudo-code for each function. These are designed to be modular and integrable into Ethereum clients like Geth.

7.3.1 Add account (AddAccount)

This operation adds a new account to the world state. It inserts a new leaf into the Merkle-Patricia trie with integrated red-black tree fields and inserts the node into the red-black tree structure. Necessary for creating new accounts during transactions (e.g., first-time receivers). If the account already exists, it fails or redirects to modify().

Screenshot of a Golang function named AddAccount with color-coded syntax. The function checks if an account address exists in a Merkle Patricia Trie (MPT), returns an error if it does, creates a new MPT leaf containing provided parameters and red-black (RB) tree fields, inserts this leaf into the MPT, and updates the RB tree with logarithmic time complexity. Comments explaining each code step are shown in green, keywords and data types are highlighted in different colors, and the code concludes by returning nil.

7.3.2 Modify account (ModifyAccount)

This operation updates an account’s balance and last modification (e.g., during ExecTrans for senders/receivers). Since the sort key (balance, last_mod) changes, we remove the node from its current red-black tree position and reinsert it with the updated values. Necessary to handle transactions while maintaining sorted order for efficient zero-balance checks.

Screenshot of a code snippet written in Go language for a function named ModifyAccount. The function adjusts an account's balance, calculates storage fees, checks for sufficient balance, manages leaf nodes in a red-black tree, and updates state via a Merkle-Patricia Trie. Code comments are in blue-green, explanations and error messages use plain English and pathways are highlighted by green and red colored keywords and values.

7.3.3 Delete account (DeleteAccount)

This operation removes an account (e.g., during CheckZero when balance ≤ 0 after fees). It removes the node from the red-black tree structure and deletes the leaf from the Merkle-Patricia trie. Necessary for pruning expired accounts efficiently.

Go programming language code for the function DeleteAccount, which deletes an account by address using both a red-black tree and a Merkle Patricia trie. The code includes logic for finding and validating the address, deleting from both data structures, and returning errors or nil.

7.3.4 Fixup operation (fixup)

The fi x u p ( ) operation is the crucial, low-level procedure that maintains the five essential R e d − B l a c k tree properties (as outlined in Section 3.1) following an r b I n s e r t ( ) or r b D e l e t e ( ) operation. In the unified Promethon structure, this standard Red-Black tree algorithm is executed using account addresses for navigation.

The process operates as follows.

• Address-Based Navigation: To traverse the tree, the fi x u p ( ) procedure uses the account addresses stored in the L e f t A d d r, R i g h t A d d r, and P a r e n t A d d r fields of a leaf node.
• Node Retrieval (Lookup): Before performing a comparison (key sorting) or a structural modification (rotation/recoloring), the procedure must fetch the actual leaf node data from the Merkle-Patricia Trie using the address, typically via a fi n d I n M P T ( ) function. Each such lookup has a time complexity of O ( k ), where k is the length of the account address.
• Structural Modifications: When rotations (Left-Rotate or Right-Rotate) or recoloring are required, the fi x u p ( ) procedure directly updates the C o l o r and the pointer fields (L e f t A d d r, R i g h t A d d r, P a r e n t A d d r) within the affected leaf nodes. Since the data resides in the Merkle-Patricia Trie leaf, this modification triggers a hash update, propagating changes up the Merkle-Patricia trie branch.
• Complexity: Since the Red-Black fixup involves a logarithmic number of operations, O ( log ⁡ n ), and each traversal/lookup step incurs an O ( k ) overhead, the total complexity of the fixup remains within O ( k ⋅ log ⁡ n ). This O ( k ) overhead is constant and is necessary to maintain the verifiable integrity of the Red-Black structure through the Merkle-Patricia root.

No separate data structures or references need to be managed, as all necessary Red-Black tree information is integrated into the Merkle-Patricia leaf nodes, ensuring structural consistency and verifiability through the M P T _ root.

Screenshot of a code snippet in the Go programming language showing the implementation of a helper function called fixup, used to correct violations in a tree structure. The code contains detailed comments in green explaining each step such as fetching parent nodes, handling recoloring and rotations, moving up the tree, and ensuring the root node is black. Indentation and color-coding distinguish comments, keywords, and code logic.

7.3.5 Implementation details

To allow a uniform interface for state management across different data structure designs, we defined the following general interface.

Code snippet showing a Go interface named StateRentStructure with four methods: Get, Add, Delete, and UpdateBlockHeight. Method signatures specify parameter and return types, including string, error, Data, big.Int, byte slice, and uint64.

The Data type encapsulates an account’s balance, a data byte slice, and the last modified time for rent expiry calculations.

We implemented two distinct approaches conforming to the StateRentStructure interface. While both implementations provide the same core operations, they differ fundamentally in how account expiry is managed. PromethoniXTrie utilizes a sorted Red-Black tree to enable efficient identification and deletion of expired accounts, whereas LinearApproachTrie performs a full linear scan of all accounts at each block to identify accounts for removal. This distinction highlights the superior scalability and efficiency of PromethoniXTrie compared to the baseline approach.

7.3.6 PromethoniXTrie (our approach)

Screenshot of Golang source code defining PromethoniXTrie and related node structures for a Merkle-Patricia Trie, with embedded metadata for account management and red-black tree properties, using syntax highlighting.

This structure represents a unified hybrid design in which the Merkle-Patricia trie provides the hierarchical account lookup layer, while Red-Black tree ordering is embedded directly inside the LeafNode type. In this merged architecture, BranchNode and ExtensionNode preserve the traditional trie behavior, whereas LeafNode instances store account metadata–such as balance and last-modified block–along with Red-Black tree fields (Color, Parent, Left, Right) that enable efficient ordering.

The embedded Red-Black tree logic allows leaf nodes (accounts) to be maintained in a balanced structure according to their expiry priority under the rent algorithm. As a result, upon each call to UpdateBlockHeight (executed at the end of each block), the implementation can identify the leftmost LeafNode directly through the Red-Black metadata stored inside the unified trie. If the account at this position satisfies the expiry condition, it is deleted from the merged structure, after which the local Red-Black relationships are repaired through standard fix-up operations.

7.3.7 Linear approach trie (baseline)

Code snippet in Go defining a struct named LinearApproachTrie containing two fields: Trie of type MerklePatriciaTrie and BlockHeight of type uint64, with syntax highlighting applied.

This baseline approach does not utilize any additional sorted structure like a Red-Black tree. Instead, when UpdateBlockHeight is invoked, it performs a linear scan through all accounts stored in the Merkle-Patricia trie. For each account, it checks if the rent expiry condition is met and, if so, deletes that account from the trie.

7.4 Running the benchmark

The benchmark started by loading the dataset into memory. To evaluate scalability and performance as the transaction history grows, we incrementally processed the data in batches of 1,000 transactions. Specifically, we first executed the benchmarks with the initial 1,000 transactions, then extended to 2,000, 3,000, and continued in this manner up to the full dataset. For each batch size, we measured the average execution time of essential operations such as Get, Add, and Delete, as well as a custom UpdateBlockHeight() function to simulate the advancement of blockchain time.

The results were visualized in the performance graph shown in Figure 10. This graph clearly illustrates that as the dataset increases in size, our proposed PromethoniXTrie significantly outperforms the Linear approach.

8 Deployment and compatibility with the ethereum roadmap

Deploying Promethon on the Ethereum mainnet requires a hard fork. The proposed design modifies two aspects of the protocol that directly affect consensus. First, the encoding of trie leaf nodes is extended to carry red-black tree metadata (the node color and the parent, left, and right pointers), which alters the leaf hash and therefore the global state root for any given set of accounts. Second, the state-transition function is augmented so that, at every block, storage rent is deducted from accounts in proportion to their storage usage, and accounts whose effective balance becomes non-positive are removed automatically, without an explicit transaction. Either change alone would cause an un-upgraded client to compute a different state root than an upgraded client for the same block, which by definition precludes a soft-fork deployment. A one-time migration is required at the fork block to sort the existing accounts by effective balance and build the initial balanced red-black layout; this is an O ( n ⁡ log ⁡ n ) operation that clients perform off-chain during the upgrade window, analogous to the migration planned for the Verkle transition.

Promethon is also compatible with Ethereum’s longer-term roadmap. The red-black ordering operates at the leaf-value layer of the state structure, whereas planned upgrades such as Verkle trees (Ethereum, 2021) replace the commitment layer of the trie ² . Because Verkle leaves remain key-value bindings, the red-black metadata can be embedded inside Verkle leaf values exactly as it is embedded inside Merkle-Patricia leaves in the current design; the Verkle commitment then covers the additional fields automatically as part of the leaf value. Promethon therefore composes naturally with Verkle and can be deployed before, after, or alongside it. We further note that Promethon serves as an alternative to the time-based state-expiry direction outlined in (Buterin, 2021) the two should be viewed as substitutes rather than complementary mechanisms, as both target the same growth problem with different trade-offs. Finally, because Promethon introduces no new cryptographic primitives beyond those already present in Ethereum, the planned post-quantum transition is orthogonal to the changes proposed here and is not affected by them.

9 Conclusion

The rapid growth of Ethereum’s world state necessitates innovative solutions to address storage challenges and enhance network efficiency. Existing proposals, while insightful, suffer from drawbacks that hinder their practicality. Our proposed state expiry method introduces a novel approach, charging accounts at regular intervals to ensure that only relevant data is retained in the world state. Leveraging the synergy of red-black trees and Merkle-Patricia tries allows us to achieve optimal computational and storage complexities, maintaining a time complexity of O ( k ) for critical operations. This proposal represents a promising step forward in tackling the world state size problem, providing a balanced and efficient solution for the evolving landscape of decentralized systems.

Generative AI statement

The author(s) declared that generative AI was not used in the creation of this manuscript.

Any alternative text (alt text) provided alongside figures in this article has been generated by Frontiers with the support of artificial intelligence and reasonable efforts have been made to ensure accuracy, including review by the authors wherever possible. If you identify any issues, please contact us.

Publisher’s note

All claims expressed in this article are solely those of the authors and do not necessarily represent those of their affiliated organizations, or those of the publisher, the editors and the reviewers. Any product that may be evaluated in this article, or claim that may be made by its manufacturer, is not guaranteed or endorsed by the publisher.

Footnotes

Edited by: Andrea Michienzi, University of Pisa, Italy

Reviewed by: Chen Feng, The University of British Columbia, Canada

Pujianto Yugopuspito, University of Pelita Harapan, Indonesia

Footnotes

Unless otherwise stated, we use n to refer to the number of accounts in Ethereum’s world state

At the time of writing, Verkle trees are not yet deployed on Ethereum mainnet and are scheduled for a future network upgrade (Ethereum Foundation, 2026).