Published on: 2021-09-16T15:05:24+00:00
The Utreexo project has been exploring ways to address storage space and traversing issues in the UTXOS Merkle Tree/forest. Currently, storing N internal nodes requires 2N pointers, along with an additional pointer in the leaves special nodes for different traversing options. To overcome this problem, a simple idea has been proposed to eliminate all pointers by using a 2D array with variable row sizes.In this approach, each row of the 2D array, denoted as R[j], has a length of N/2^j. For example, when N=8 nodes, R[0] contains elements from 0 to 7, R[1] contains elements from 8 to 11, R[2] contains elements 12 and 13, and R[3] contains element 14. This way, the total storage required is just 2N-1 nodes, eliminating the need for pointers.Traversing the Merkle Tree becomes more efficient with the right formula. The formula involves fetching proof[i] through pseudo-code, which determines whether to add or subtract 1 from i based on the direction. After determining the direction, the sibling node is added, followed by the rest of the nodes through a loop. This iterative approach transforms a recursion into an iteration, making it applicable to any Merkle Tree.This idea of compressing the Merkle Tree has potential applications in saving storage space and improving traversing efficiency. For a more detailed explanation, lecture notes and a video link are provided, along with a discussion by Shymaa M Arafat on the BitcoinTalk forum.
Updated on: 2023-08-02T04:46:27.874422+00:00