From vincent.palazzo at protonmail.com Thu Sep 16 12:37:24 2021 From: vincent.palazzo at protonmail.com (Vincent) Date: Thu, 16 Sep 2021 12:37:24 +0000 Subject: [Lightning-dev] Storing the Merkle Tree in a compact way In-Reply-To: References: Message-ID: Hi. Thanks for the reference, but I missed where you want save space with this compression on the Merkle Tree. Regards. Vincent. vincenzo.palazzo at protonmail.com https://github.com/vincenzopalazzo ??????? Original Message ??????? On Thursday, September 16th, 2021 at 5:15 AM, shymaa arafat wrote: > Allow me to introduce this simple idea that could be useful ... > > -The Intuition was some discussion on Utreexo project about storage saving and some traversing issues in handling the UTXOS Merkle Tree/ forest; that is N internal nodes need to be stored along with 2N pointers (left&right), + 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 > https://github.com/mit-dci/utreexo/discussions/316) > . > > Then, I thought of a simple idea that gets rid of all the pointers; specially appealing when we have all trees are full (complete) in the forest, but can work for any Merkle Tree: > > - 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 > R[3]=14 > . > -We can see that total storage is just 2N-1 nodes, > no need for pointers, and traversing could be neat in any direction with the right formula: > > -Pseudo code to fetch proof[i] ... > > //direction to know + or - > If ((i mod 2)==0) drct=1; > else drct=-1; > // first, the sibling node > proof[i]=R[0,i+drct] > > //add the rest thru loop > For(j=1; j?logN; j++) > { index= i/(2^j)+drct; > proof[i]=Add(R[j,index]); > } > > -In fact it's just the simple primitive approach of transforming a recursion to an iteration, and even if Utreexo team solved their problem differently I thought it is worth telling as it can work for any Merkle Tree > . > Thanks for your time, > Shymaa M Arafat -------------- next part -------------- An HTML attachment was scrubbed... URL: