Restructuring a Non-Binary Tree by Adding a Single Leaf

cover
10 Sept 2024

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.

Abstract and 1. Introduction

1.1. The Blockchain Paradigm and the Challenge of Scalability

1.2. State of the art

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. Examples of Merkle Tree Restructuring Algorithm Execution and 6.1 Example 1: Restructuring a Binary Tree by Adding One Leaf

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. Enhancing Verkle Trees Through Adaptive Restructuring and 8.1. Application of Adaptive Trees in Verkle Tree Technology

8.2. Technology and Advantages

9. Discussion

9.1. Our Contribution

9.2. Comparison with Existing Solutions

10. Conclusion and References

6.3. Example 2.1: Restructuring a Non-Binary Tree by Adding a Single Leaf

In this example, we explore a non-binary tree where each node can have up to four children (m = 4), closely mirroring a simplified real-world scenario of Patricia-Merkle trees in the Ethereum blockchain.

Let's assume the initial state of the tree is as shown in Figure 11.a, similar to the previous example. Also, let the newly added leaves and their probability distributions follow the pattern established in Example 1. These changes in probabilities are summarized in Table 5, which also lists the number of alternatives and the unique discrepancy value (1). Figures 21-30 depict the corresponding tree graphs.

Table 5. List of Leaves and Their Probabilities per Iteration, Number of Restructuring Alternatives, and Minimum Discrepancy Value

Figure 21: Tree Restructuring (Iterations 1)

Figure 22: Tree Restructuring (Iterations 2)

. Figure 23: Tree Restructuring (Iterations 3)

Figure 24: Tree Restructuring (Iterations 4)

Figure 25: Tree Restructuring (Iterations 5)

Figure 26: Tree Restructuring (Iterations 6)

Figure 27: Tree Restructuring (Iterations 7)

Figure 28: Tree Restructuring (Iterations 8)

Figure 29: Tree Restructuring (Iterations 9)

Figure 30: Tree Restructuring (Iterations 10)

The calculations of discrepancies in Table 5 show that the configuration of the restructured trees tends towards optimality by minimizing the average path length.

Now, let's demonstrate the algorithm's operation in the mode of swapping positions between pairs of nodes, as in Example 1.1.

This paper is available on arxiv under CC by 4.0 Deed (Attribution 4.0 International) license.