📅 Original date posted:2021-09-16
📝 Original message:
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 <shymaa.arafat at gmail.com> 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: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20210916/42856a25/attachment.html>;
Vincent [ARCHIVE] /
npub1cc…74z4j
2023-06-09 13:03:42
in reply to nevent1q…fkad
Author Public Key
npub1ccmq3hqeecsnfxzyxkhkzz35rfp4wnx80x6hjl7d2vfegz8ae4qqu74z4jPublished at
2023-06-09 13:03:42Event JSON
{
"id": "ee898edf926f525d40d7ae4387703110e38309f797a7d50b60ef6aaffae990ad",
"pubkey": "c63608dc19ce2134984435af610a341a43574cc779b5797fcd53139408fdcd40",
"created_at": 1686315822,
"kind": 1,
"tags": [
[
"e",
"9c53653fd3f42c91db5ca714d11cad6e64bdc7586d436984ec5ed402536ac6dc",
"",
"root"
],
[
"e",
"a23a3f8a98967ceda585c92386083f1fe655a6edbd225dc596608effa69899b0",
"",
"reply"
],
[
"p",
"ffbede6cc00fc0cadcbf4d9c17063fe865134ffd55e693dcfbd95bd883ecd42e"
]
],
"content": "📅 Original date posted:2021-09-16\n📝 Original message:\nHi.\n\nThanks for the reference, but I missed where you want save space with this compression on the Merkle Tree.\n\nRegards.\n\nVincent.\nvincenzo.palazzo at protonmail.com\nhttps://github.com/vincenzopalazzo\n‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐\nOn Thursday, September 16th, 2021 at 5:15 AM, shymaa arafat \u003cshymaa.arafat at gmail.com\u003e wrote:\n\n\u003e Allow me to introduce this simple idea that could be useful ...\n\u003e\n\u003e -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\u0026right), + maybe 1 more pointer in the leaves special nodes to handle different traversing options (insert, delete, \u0026 differently proof fetch that traverse aunt or niece node according to your implementation\n\u003e https://github.com/mit-dci/utreexo/discussions/316)\n\u003e .\n\u003e\n\u003e 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:\n\u003e\n\u003e - 2D array with variable row size; R[j] is of length (N/2^j)\n\u003e -For example when N=8 nodes\n\u003e R[0]=0,1,2,...,7\n\u003e R[1]=8,9,10,11\n\u003e R[2]=12,13\n\u003e R[3]=14\n\u003e .\n\u003e -We can see that total storage is just 2N-1 nodes,\n\u003e no need for pointers, and traversing could be neat in any direction with the right formula:\n\u003e\n\u003e -Pseudo code to fetch proof[i] ...\n\u003e\n\u003e //direction to know + or -\n\u003e If ((i mod 2)==0) drct=1;\n\u003e else drct=-1;\n\u003e // first, the sibling node\n\u003e proof[i]=R[0,i+drct]\n\u003e\n\u003e //add the rest thru loop\n\u003e For(j=1; j≤logN; j++)\n\u003e { index= i/(2^j)+drct;\n\u003e proof[i]=Add(R[j,index]);\n\u003e }\n\u003e\n\u003e -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\n\u003e .\n\u003e Thanks for your time,\n\u003e Shymaa M Arafat\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20210916/42856a25/attachment.html\u003e",
"sig": "2a67feb6c62d16e419ba8bc4ad79a3039e92c358f87a3d73278a3742ddf45d6c13b2735186b395b668f6646207bdd31c6cc995aba05acc62db8e744886e47ecf"
}