Author: shymaa arafat 2021-09-11 03:00:12
Published on: 2021-09-11T03:00:12+00:00
Introducing a simple idea that could be useful for storage saving in handling the UTXOS Merkle Tree/forest, Shymaa M Arafat discusses the issues with storing N internal nodes along with 2N pointers. To handle different traversing options, additional pointers may also be required in the special leaves nodes. A new approach proposed by Arafat gets rid of all the pointers and uses a 2D array with variable row size instead. This method is specially appealing when all trees are full (complete) in the forest but can work for any Merkle Tree. In this approach, R[j] is of length (N/2^j), where j represents the level of the tree. For example, when N=8 nodes, R[0]={0,1,2,...,7}, R[1]={8,9,10,11}, R[2]={12,13}, and R[3]={14}. The total storage needed is just 2N-1 nodes, and there is no need for pointers. Traversing could be done neatly in any direction with the right formula. A pseudo code to fetch proof[i] is provided, which involves determining the direction to move, fetching the sibling node, and adding the rest through a loop. This method transforms recursion to an iteration and can work for any Merkle Tree. Although the Utreexo team may have solved their problem differently, Arafat believes this approach is worth sharing.
Updated on: 2023-06-03T05:49:03.106474+00:00