Return-Path: <shymaa.arafat@gmail.com> Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 80745C000D; Sat, 11 Sep 2021 03:00:27 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id 6658C415C7; Sat, 11 Sep 2021 03:00:27 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -0.199 X-Spam-Level: X-Spam-Status: No, score=-0.199 tagged_above=-999 required=5 tests=[BAYES_40=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Authentication-Results: smtp4.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id wC1DMS8Jsc-R; Sat, 11 Sep 2021 03:00:26 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-pg1-x52d.google.com (mail-pg1-x52d.google.com [IPv6:2607:f8b0:4864:20::52d]) by smtp4.osuosl.org (Postfix) with ESMTPS id 3EC39414CC; Sat, 11 Sep 2021 03:00:26 +0000 (UTC) Received: by mail-pg1-x52d.google.com with SMTP id 17so3585168pgp.4; Fri, 10 Sep 2021 20:00:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:from:date:message-id:subject:to; bh=seTou/amvaiVRNxL2kyu3q6hoUP/KrRLJOWgMVWhaFM=; b=Tidfj9RY2fMEBw8036pP8MP1DiAho2Z/aGURAULKnuyhkXyWgreI8+TFXv0eVp/33F Tw5Ac4K1Z+7jnk7Z7A1FJL2dh09lHFpQp9go2C9d16F2jpcWHnONZ4AvduXTN/dseU8a Ov1El51lX8xgQ+YMXACppoG7Ac+71JN9SvncAO5w5mNeuG9D+XNGhZCKIuok7mle18ZL 9mW+oy4LtWbh69KiGkKNeo3jT89z0DMYmgpk2Wh9ortNURhRbH0FvYqz63mAwBOQeWMm VBkOkyCcsYn+ebOwtq2yMeo/s+E/8KnGrM5VFh0sygpvVTk6PJuFMSLb1crIv98l+pfL pDHA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=seTou/amvaiVRNxL2kyu3q6hoUP/KrRLJOWgMVWhaFM=; b=fhoDr2PUPuvK9cAVQtCLYAq8c/0StxcY/WX/yMpX58ivF5j2NAt9u2dbe6dqEvDtaK ebEN41cYfXnDUe4ivmu9xSnxUaFAZDQTPH952RbnnfzBj3PZwC00mDJP6b6Zv9qTIbNg R7OkwmRR9Hghs/fowv5opf/XC3z5rop7CYDzX3c55KBoN/GDc3zFFD7XfdelV0V/Zo3H DETS/lGaALiUJgxkJFSs5EKLo0v+WlXCSoz3PvXctb9dAH0hHjfi0bRqqOL3TPClwH4I Nzk2MOga0vKac+3ga80LNNiOytTHGsbiXe079Q6cKhhHwitgkK2rnToJDRN1w2OupsLh 01MA== X-Gm-Message-State: AOAM533aQ41fUb1BdguDm0qU9h1jpK9agW2CgD5w6Pwg9bidme69TPTV g1JxAIDvuWxgT9oRkx+LX2bPL05ZgUe81AQAIjKyzW1f X-Google-Smtp-Source: ABdhPJy3rd4zMdoghwVjl/NDwueaV5FHcJ/4jYVYrGt+ldPeZTUFSXnqbSb0EJIeHG63FUk8mHMmSaVIeDqbWNVRCkY= X-Received: by 2002:aa7:9a06:0:b0:3f4:1f0a:4fc6 with SMTP id w6-20020aa79a06000000b003f41f0a4fc6mr711003pfj.58.1631329225313; Fri, 10 Sep 2021 20:00:25 -0700 (PDT) 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" X-Mailman-Approved-At: Sat, 11 Sep 2021 11:58:18 +0000 Subject: [bitcoin-dev] Storing the Merkle Tree in a compact way X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org> List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe> X-List-Received-Date: Sat, 11 Sep 2021 03:00:27 -0000 --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&right), + maybe= 1 more pointer in the leaves special nodes to handle different traversing = options (insert, delete, & 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'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--