From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 Date: Sat, 11 Sep 2021 05:00:12 +0200 Message-ID: To: Bitcoin Protocol Discussion , lightning-dev 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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
Allow me to introduce this simple idea = that could be useful ...

-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
https://github.com/mit-d= ci/utreexo/discussions/316)
.
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:

- 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 di= rection with the right formula:

-Pseudo code to fetch proof[i] ...

//direction to know + or -
If (= (i mod 2)=3D=3D0) drct=3D1;=C2=A0
=C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 else drct=3D-1;
// first, t= he sibling node
proof[i]=3DR[0,i+drct]
=C2=A0 =C2=A0 =C2=A0
//add the rest thru l= oop
For(j=3D1; j=E2=89=A4logN; j++)
=C2=A0{ index=3D i/(2^j)+drct;
=C2=A0 =C2=A0 = proof[i]=3DAdd(R[j,index]);
=C2=A0}

-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
.
Thanks for your time,
Shymaa M Arafat

--000000000000fc905205cbaf6e07--