Promethon: New way to look at the next generation of Internet!
Ethereum uses a world state to hold states of each account. But the size of this world state is growing rapidly and there hasn't been any efficient solution for shrinking it down. World state is implemented by using Merkle Patricia Trie but today, we introduce PromethoniXTrie. PromethoniXTrie acts as a bridge between Merkle Patricia Trie and Red-Black Tree. The main idea is to keep an extra value to validate that the account should still exist on the network or not. But due to the large volume of data, the challenge that has always existed is how to perform this validation in a short time and remove invalid accounts.
A Red-Black Tree is a specialised binary search tree data structure noted for fast storage and retrieval of ordered information, and a guarantee that operations will complete within a known time. Also, guarantees searching in Big O time of O(logn), where n is the number of entries (or keys) in the tree. The insert and delete operations, along with the tree rearrangement and recoloring, are also performed in O(logn) time.
Therefore, according to the description of the Red-Black Tree, if we keep a Red-Black Tree next to our Merkle Patricia Trie and can establish a relationship between them so that the Red-Black Tree is always sorted based on the additional value we keep, we can always find the leftmost node of Red-Black Tree in Big O time of O(1).
Now the question that arises is, what is this extra value and how does it perform the validation?
To be honest, this question can have many different answers, each with pros and cons. But what we all know is that eventually we want to reduce the volume of data, so we can't store all the data all the time.
- An initial idea: we can consider this "extra value" as the block time of the last change or use in the contract. For example, if a year has passed since the last change, we can delete that account. Read More & Implementation
- Another idea is to charge a fee per certain amount of volume. Whenever this amount is used up and never charged again, delete that account.
The PromethoniXTrie project implements the basis of the second idea. It creates a Merkle Patricia Trie and a Red-Black Tree and establishes the desired connection between them and then tests the performance of the Promethon idea. You can read more about the algorithm here.
Our initial tests have been positive and promising. We are currently implementing this idea on the go-ethereum source code and we hope to announce its completion soon!
In the provided implementation, you'll find a straightforward integration of both the Merkle Patricia Trie and Red-Black Tree. If you intend to create your own implementation for benchmarking purposes, ensure that it maintains equal overhead on these data structure implementations. This parity in overhead ensures fair comparison and accurate assessment of performance metrics across different implementations.
The implementation includes an interface called TestStruct, which provides basic functions like Get, Add, Delete, and UpdateBlockHeight. These functions simulate typical operations in a blockchain, ensuring compatibility and facilitating easy testing of the PromethoniXTrie data structure.
Additionally, a straightforward implementation of our concept is available in the benchmark/red_black_tree_impl.go. This implementation embodies our idea, allowing for benchmarking and evaluation of the proposed approach.
Moreover, you'll find a simple random dataset generator designed to create datasets for testing purposes. Initially, it generates a set of unique addresses ($AddressCount), followed by the creation of transactions. Each transaction adds 1000 bytes ($DataSize) of random data to the corresponding account, with a total of 10000 ($SampleSize) transactions generated by default. This dataset generator aids in simulating real-world scenarios and enables comprehensive testing of the PromethoniXTrie implementation.
The program follows a two-step process: first, it generates a random dataset, and then it proceeds to benchmark the processing, creation, and insertion timings of our approach. By evaluating these benchmarks, our proposal demonstrates its capability to handle data efficiently and effectively. This comprehensive testing validates the feasibility and robustness of the PromethoniXTrie approach, showcasing its potential to address scalability challenges within blockchain networks.
Run the program from main.go!