Maru State Storage | Anton Yezhov, Alex Rusna - Proxima Labs

hi everyone um uh today we're presenting uh a new uh work in from our cryptographic team that um is proposing a new type of a trick construction that is uh going to significantly reduce the overhead of uh hashing and solve the state storage problem uh in uh blockchains so uh to start blockchains are introducing a fundamental shift in uh storage of data where um they bring security and transparency and decentralization you using cryptographic methods uh to maintain distributed Ledger however in such scalability is the biggest problem because um it requires to maintain uh The Ledger uh on many instances and process large volumes of transactions leading to bottlenecks and increased costs overcoming such scalability is essential for blockchain continued growth and uh it's necessary to come up with the new model and architectures to sustain growth here we can see that uh the growth of total unique ethereum addresses over one-ear period is quite significant and if we're looking at the frequency of use we we can notice that the number of uh uh frequently daily used uh addresses is quite narrow representing only 177% of uh unique addresses that are actively engaged with the network daily pointing to a high concentration of pattern uh in pattern activity this concentration uh challenges uh for optimizing the blockchain State Management emphasizing the need for efficient data verification and management strategies to accommodate the network scaling complexities our contribution is uh proposing we're proposing a new Dynamic restructuring algorithm for Merkel trees that enhances scalability and efficiency of blockchain systems by optimizing their verification and storing process Pro processing and uh we also extend the applicability of these optimized uh tree structures Beyond traditional blockchains uh demonstrating their versatility uh that goes beyond blockchain to conceptualize the problem uh what we have is in regular blockchain designs uh Merkle trees act as a balanced tree and uh here you can see that uh for any frequency of use of the address uh for any Leaf node the search complexity is averaged out um the problem with this is that for even for high frequently used uh Leaf node the search complexity is on average the same as for the low frequency see use node which leads to an average out higher significantly higher computational cost for accessing the data so the inefficiency really comes uh from uh their verification strategy while maintaining the data integrity and what we are proposing is uh the Adaptive tree that uses the frequency distribution of use uh and uh Narrows the search comp complexity uh for it thus enhancing the efficiency and scalability of the blockchains our adaptive Merle tree inspired by uh Huffman encoding prioritizes data based on the usage frequency placing frequently accessed nodes closer to the route to streamline verification process by aligning nodes placed uh placement by with usage probability the Adaptive structure significantly reduces the path in computational uh complexity for verifying five high frequency data enhancing efficiency and reducing verification time their verification path for high usage nodes such as node a like here we can uh see it um designed um is considerably shorter in the Adaptive treat compared to the balanc structure demonstrating a direct correlation between data access frequency and computational resource allocation so here we can see that uh for a node a which is high uh high frequency use we can restructure it to the uh to be positioned to the higher to the top of the tree thus reducing the hashing amount of hashing that is required to access the uh the node the efficiency of adaptive Merkel trees in comparison to the Balan trees uh what we see is the average path length is determined in balanced trees is determined by log M of n where M represents the maximum allowable number of child child nodes per node or the aity of the tree and N is count of unique symbols uh within the alphabet for the Adaptive tree uh what we uh indicate that the average path length mirrors the average length of the Huffman encoding uh calculated at as the weighted sum of all Cod length uh with the probabilities of the corresponding symbol serving as weight and here we see a a sigma uh over Pi Pi * ly Li I where Pi Pi I is the probability of the I symbol and Li is the length of the code uh for the I symbol now the efficiency of the Adaptive tree is theoretically uh average length of the Huffman code given a specific probability distribution can be derived from the entropy formula uh transforming this assessments into a comparison in comparison of the complexity of data Integrity verification in both the classical balance in the proposed adaptive tree yields for balance tree B for balance binary tree the average moral path uh complexity is k equals to 4 whereas for adaptive tree the average path length is uh roughly equals to 3.5 which indicates an efficiency gain of approximately 133% which is an average theoretical uh theoretical um efficiency uh the gain reflects U the reduced average number of hashes uh required to verify the Integrity of the leaf data and here we're going to uh show the experimentation the experimental uh evidence that actually this reconstruction yields even far bigger efficiencies yeah thank you uh I'll continue so our efficiency of adaptive Miracle tree with the ethereum experiment on meracle Patricia try so we have evaluated the efficiency of our approach on 100K blocks consecutive of ethereum blockchain so for the evaluation we use simplified model of blockchain where transactions only changes to and from addresses and only mentioned in transaction slot exists so we have like the block range of 100K uh we have around 31.5 million of transactions we have 3.9 active addresses and the addresses that capture 50% of total activity were around 4K from 3.9 million addresses that captured 90% of total activity was 1.

6 million so the percentage of total activity captured by the 50% of the addresses is 92% of all activity that was happened on CH PX transaction will introduce new addresses is 9% so you can see the efficiency so we expected the average depth of accessed element was calculated using the formulas from the previous slide and Sample probability distribution so you can see the number of block blocks and logarithmic of number of blocks the results as we use depths of assessed element in three as estimation of number of hashes needed to calculate the treap in our experiment we calculated theoretical Improvement of 90 27% on 100K blocks as probability of truction of new address with the new transactions is much higher than in real ethereum blockchain we conclude that the result will continue to improve with additional blocks and we project that theoretical Improvement for the full ethereum blockchain could be around 42% so in our small scale implementation experiments real improvements was within the 5 person of thetical limit and we expected to will be even closer for full scale implementation so the next part is uh the algorithm of for Merle 3 reconstruction as adaptive 3 requires the Reconstruction in Merle 3 in order to put the more frequently used nodes higher in the three and put more uh rarely used nodes lower the Reconstruction of Miracle tree aimed for to optimize this efficiency of blockchain applications so the two criteria we have is minimization of average pass length the deviation between key and H is assessed through the average disparen so with each element disparen defined as the next Formula so and the second point is that minimization of altered pass the algorithm should limit modifications to a minimal subset of nodes reflecting the reality that only a few accounts are activated in any given transaction including complex smart transactions like contract addresses and execution of uh subcontracts this approach ensures that unactive accounts retain their positions and pass within the three preserving the Integrity of user data and access path ways so the input is a tree or a tree fragment with the root intermediate nodes and leaves the probability distribution frequencies of these three leaves is a set of leaves available for reconstruction a new Leaf or a new probability distribution for all three leaves so the output will be a restructured tree or a fragment of restructure three optimized according to the criteria of minimizing the average disp parency so do have the next steps of the algorithm utilize the set L of leaves available for reconstruction for formulate all possible reconstruction alternatives for the tree evaluate the average disparen for each alternative select the alternative with the lowest average disp parency and adop selected alternative to the as the algorithm output so the most challenging aspect of this algorithm is step one which involves generating all possible reconstruction passes so you can see here on these examples that like with adding a new Leaf we need to reconstruct all uh other probabilities like disp parency for all other leaves and put a new Leaf in one of the position so like this iteration is shown on this uh table with first alternative and the second alternative for the same tree with different diser so the same is examples is going further when we have a second iteration we have like in next iterations and then we have like this more third iteration force and this is like five to 10 iterations all of them are showing the examples on binary tree but we also have the examples on the uh force uh Miracle tree and the Miracle Patricia try so this is um yeah and this is the examples of reconstructing mirle Patricia try with the new leafes heading and the leaf pair swapping um I think I'll transfer the word to Alex back for the path encoding in adaptive Miracle tree so um to talk about path encoding in adaptive uh trees is integrating adaptive trees into the ethereum's uh framework it necessitates the departure from understanding that uh we can use balance Merk patrier tree as the data structure proposing that in our proposal uh is the nbalance tree that aligns leaves based on the frequency of usage challenging the traditional path encoding uh method the new new method uh would alter the deterministic path encoding of uh addresses necessitating a novel mechanism that ENC counts for the dynamic positioning of leaves without disrupting the existing address system this means that in order to adop for uh balanced pucha tree uh structure to be to adopt this adaptive structure uh what we have to do is we have to attach a new um dual structure uh that would effectively not disrupt the uh existing addresses which are stored in the balance tree but would have a subsequent new structure uh added to it that would have a dynamic address system the Dual structure system mapping uh account addresses to their adaptive path encodings emerges as a practical solution to maintain uh compatibility ensuring seamless integration and operational continuity within the blockchain chain Network this Innovative uh integration promises to significantly reduce verification complexity and costs by adapting the to usage pattern potentially revolutionizing the way blockchain system manage data integrity and address verification uh here we can see effectively uh in a more uh detailed way how uh what is the leaf probability distribution and uh what is the path en coding uh for for balance Tre which is average Cod length is four and for the Adaptive three is 3.49 which is uh effectively 133% more efficient um as ethereum is moving into the uh into a more compressed tree with a veral tree construction the we believe that uh this will the Adaptive tree structure will yield even more savings as the cost of moving from uh you know layer to layer from in the veral tree is even more expensive the Advent of the veral tree uh trees marks a transformative uh transformative advancement in blockchain storage and verification melting the succinctness of vector commitments with the hierarchical Integrity of Merle trees and address scalability uh and efficiency uh challenges by implementing an Adaptive restructuring approach we can significantly augment the efficiency and scalability of veral trees tailoring their configur ation uh dynamically in response to usage pattern with uh within blockchain systems our strategy involves the dynamic adjustment of veral tree uh of veral trees utilizing statistical analysis to optimize data into organization based on access and update frequencies thus streamlining verification process by incorporating uh Huffman coding principles allows for strategic placement of frequently accessed elements close to the route effectively minimizing path length for verification and enhancing overall system performance reduce proof size by optimizing the structure of uh vertical trees to reflect excess pattern we can significantly reduce the size of proofs required to verifying transactions this is because frequently accessed data can be positioned closer to the route making it quicker and less resource intensive to generate uh and verify proofs meaning uh in the veral trees as you build the tree and it gets deeper the size of the proof uh increases so by uh in the cost of this proof increases with it um enhanced adaptive restructuring can also lead to a more efficient verification process shorter pass for frequently accessed data mean that less computational effort is required to verify enhance uh to verify transactions enhancing the overall throughput of the blockchains dynamic scalability uh of blockchain system can evolve so the storage and access pattern of adaptive with adaptive restructuring allows veral trees to dynamically adjust to these changes ensuring that the data structure remains optimized to current usage Trends and by optimizing the path length uh for data access and verification this approach can reduce the cost associated with these operations in blockchain systems where transaction costs are significant concerns such as ethereum this can lead to substantial savings uh for users and applications um through rigorous analysis and examples we we demonstrated the efficiency uh that uh can be achieved uh using adaptive Merkel trees our algorithm uh for merel tree restructuring detailed in section number five uh provides a systemic uh systematic approach for dynamically adjusting tree structur significantly improving upon the static nature of traditional Merkle trees by extending our concept to veral trees we show that uh how adaptive struct restructuring can be also applied to the most novel uh tree structures and in conclusion uh we can say that um we provide a conceptual framework for adapting exis Merle tree constructions to current blockchain infrastructures and demonstrate through examples the uh the practicality and benefits of this approach notably in the optimizing verification process and cost reduction comparative um comparing to uh analysis underscores that adaptive restructuring offers foundational Improvement in scalability and efficiency without adding complexity or securing vulnerabilities distinguishing it from other scalability Solutions and uh in conclusion the Adaptive restructuring of Merkel uh of Merkel and veral trees marks a significant advancement toward resolving the blockchain scalability challenges both on the state storage and uh uh search complexity and computational complexity uh for storing and accessing the data offering a blend of efficiency security and practicality which is crucial for evolving blockchain ecosystems thank you thank you so much