1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
|
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--
|
