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&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--