Author: shymaa arafat 2021-09-16 15:05:24
Published on: 2021-09-16T15:05:24+00:00
A simple idea to save storage and simplify traversing of the UTXOS Merkle Tree/ forest is introduced by Shymaa M Arafat. The tree can be viewed as a simple complete tree to 1D array with no pointers, as described in lecture 8 at MIT OpenCourseWare. This method saves approximately 76 million * 2 (size of pointer, probably 4 bytes) * ~600MB with almost no effort. Since all trees in Utreexo forest are full binary trees, this method is perfect to use. However, Shymaa suggests putting it in a 2D array to make it easier to handle the indexing math since they traverse in many ways, normally to delete or insert, and the parent siblings for the proofs. The Intuition behind this idea is some discussion on the Utreexo project about storage saving and some traversing issues in handling the UTXOS Merkle Tree/ forest. N internal nodes need to be stored along with 2N pointers (left&right), plus maybe 1 more pointer in the leaves special nodes to handle different traversing options (insert, delete, & differently proof fetch that traverse aunt or niece node according to your implementation). Shymaa's approach gets rid of all the pointers, which is especially appealing when all trees are full (complete) in the forest but can work for any Merkle Tree.The idea is to use a 2D array with variable row size. R[j] is of length (N/2^j). 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 is just 2N-1 nodes, and there is no need for pointers. Traversing could be neat in any direction with the right formula. Pseudo code to fetch proof[i] is provided, which is just the simple primitive approach of transforming a recursion to an iteration. Even if Utreexo team solved their problem differently, Shymaa thinks it is worth telling as it can work for any Merkle Tree.
Updated on: 2023-06-03T05:48:35.223826+00:00