MIME-Version: 1.0
From: shymaa arafat <shymaa.arafat@gmail.com>
Date: Sat, 11 Sep 2021 05:00:12 +0200
Message-ID: <CAM98U8=r+DGW46O5Srp5SzqB38suYnZY8DR06dqx-_gdB5Ruxw@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>, 
 lightning-dev <lightning-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000fc905205cbaf6e07"
Subject: [bitcoin-dev] Storing the Merkle Tree in a compact way
Precedence: list

--000000000000fc905205cbaf6e07
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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=3D8 nodes
R[0]=3D0,1,2,...,7
R[1]=3D8,9,10,11
R[2]=3D12,13
R[3]=3D14
.
-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)=3D=3D0) drct=3D1;
            else drct=3D-1;
// first, the sibling node
proof[i]=3DR[0,i+drct]

//add the rest thru loop
For(j=3D1; j=E2=89=A4logN; j++)
 { index=3D i/(2^j)+drct;
    proof[i]=3DAdd(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 Tre=
e
.
Thanks for your time,
Shymaa M Arafat

--000000000000fc905205cbaf6e07
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"auto"><div dir=3D"auto">Allow me to introduce this simple idea =
that could be useful ...</div><div dir=3D"auto"><br></div>-The Intuition wa=
s some discussion on Utreexo project about storage saving and some traversi=
ng issues in handling the UTXOS Merkle Tree/ forest; that is=C2=A0 N intern=
al nodes need to be stored along with 2N pointers (left&amp;right), + maybe=
 1 more pointer in the leaves special nodes to handle different traversing =
options (insert, delete, &amp; differently proof fetch that traverse aunt o=
r niece node according to your implementation<div dir=3D"auto"><a href=3D"h=
ttps://github.com/mit-dci/utreexo/discussions/316">https://github.com/mit-d=
ci/utreexo/discussions/316</a>)<div dir=3D"auto">.<br><div dir=3D"auto">The=
n, 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:</div><div dir=3D"auto"><br></div><div dir=3D"aut=
o">- 2D array with variable row size; R[j] is of length (N/2^j)</div><div d=
ir=3D"auto">-For example when N=3D8 nodes</div><div dir=3D"auto">R[0]=3D0,1=
,2,...,7</div><div dir=3D"auto">R[1]=3D8,9,10,11</div><div dir=3D"auto">R[2=
]=3D12,13</div><div dir=3D"auto">R[3]=3D14</div><div dir=3D"auto">.</div><d=
iv dir=3D"auto">-We can see that total storage is just 2N-1 nodes,</div><di=
v dir=3D"auto">no need for pointers, and traversing could be neat in any di=
rection with the right formula:</div><div dir=3D"auto"><br></div><div dir=
=3D"auto">-Pseudo code to fetch proof[i] ...</div><div dir=3D"auto"><br></d=
iv><div dir=3D"auto">//direction to know + or -</div><div dir=3D"auto">If (=
(i mod 2)=3D=3D0) drct=3D1;=C2=A0</div><div dir=3D"auto">=C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 else drct=3D-1;</div><div dir=3D"auto">// first, t=
he sibling node</div><div dir=3D"auto">proof[i]=3DR[0,i+drct]</div><div dir=
=3D"auto">=C2=A0 =C2=A0 =C2=A0</div><div dir=3D"auto">//add the rest thru l=
oop</div><div dir=3D"auto">For(j=3D1; j=E2=89=A4logN; j++)</div><div dir=3D=
"auto">=C2=A0{ index=3D i/(2^j)+drct;</div><div dir=3D"auto">=C2=A0 =C2=A0 =
proof[i]=3DAdd(R[j,index]);</div><div dir=3D"auto">=C2=A0}</div><div dir=3D=
"auto"><br></div><div dir=3D"auto">-In fact it&#39;s just the simple primit=
ive approach of transforming a recursion to an iteration, and even if Utree=
xo team solved their problem differently I thought it is worth telling as i=
t can work for any Merkle Tree</div><div dir=3D"auto">.</div><div dir=3D"au=
to">Thanks for your time,</div><div dir=3D"auto">Shymaa M Arafat</div><div =
dir=3D"auto"><br></div></div></div></div>

--000000000000fc905205cbaf6e07--