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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
|
Return-Path: <pete@petertodd.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 12E23BC7
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 24 Feb 2017 04:36:20 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from outmail149095.authsmtp.com (outmail149095.authsmtp.com
[62.13.149.95])
by smtp1.linuxfoundation.org (Postfix) with ESMTP id 076B413C
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 24 Feb 2017 04:36:18 +0000 (UTC)
Received: from mail-c232.authsmtp.com (mail-c232.authsmtp.com [62.13.128.232])
by punt24.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v1O4aGV0093206;
Fri, 24 Feb 2017 04:36:16 GMT
Received: from petertodd.org (ec2-52-5-185-120.compute-1.amazonaws.com
[52.5.185.120]) (authenticated bits=0)
by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v1O4aEPH042689
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO);
Fri, 24 Feb 2017 04:36:15 GMT
Received: from [127.0.0.1] (localhost [127.0.0.1])
by petertodd.org (Postfix) with ESMTPSA id 0E3E740014;
Fri, 24 Feb 2017 04:36:14 +0000 (UTC)
Received: by localhost (Postfix, from userid 1000)
id 3FE91204AB; Thu, 23 Feb 2017 23:36:13 -0500 (EST)
Date: Thu, 23 Feb 2017 23:36:13 -0500
From: Peter Todd <pete@petertodd.org>
To: Bram Cohen <bram@bittorrent.com>
Message-ID: <20170224043613.GA32502@savin.petertodd.org>
References: <CAAcC9ys5sUxVfOjogFiF3gzk51D_L=QQkOYevTH=qbh_RkA3Hw@mail.gmail.com>
<CA+KqGkrUneGe4yORi=JAAWzoO0UftMUuJm3S-__W5sBh-+T1vQ@mail.gmail.com>
<20170223235105.GA28497@savin.petertodd.org>
<CA+KqGkowxEZeAFYa2JJchBDtRkg1p3YZNocivzu3fAtgRLDRBQ@mail.gmail.com>
<20170224010943.GA29218@savin.petertodd.org>
<CA+KqGkrOK76S3ffPJmpqYcBwtSeKESqN16yZsrwzDR6JZZmwFA@mail.gmail.com>
<20170224025811.GA31911@savin.petertodd.org>
<CA+KqGkq7gavAnAk-tcA+gxL2sWpv3ENhEmHrQHaPdyAsKrLjGg@mail.gmail.com>
<20170224031531.GA32118@savin.petertodd.org>
<CA+KqGkrfhg3GnbWwvKXHQ2NWuCnfzYyTPUxRhzYMuDBiNQR4eA@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="5mCyUwZo2JvN/JJP"
Content-Disposition: inline
In-Reply-To: <CA+KqGkrfhg3GnbWwvKXHQ2NWuCnfzYyTPUxRhzYMuDBiNQR4eA@mail.gmail.com>
User-Agent: Mutt/1.5.23 (2014-03-12)
X-Server-Quench: c7576ddb-fa4a-11e6-829f-00151795d556
X-AuthReport-Spam: If SPAM / abuse - report it at:
http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR
aQdMdAYUHlAWAgsB AmEbW1BeU1t7WGU7 bghPaBtcak9QXgdq
T0pMXVMcUgQXBU10 ZmYeVht0fwwIen94 YkAsDXdeW0IuIRRg
FB9QRHAHZDJmdWgd WRZFdwNVdQJNdxoR b1V5GhFYa3VsNCMk
FAgyOXU9MCtqYA0d aAwRMV8ICWMuJHYQ Sh4DGzQzHEoDLwAA
X-Authentic-SMTP: 61633532353630.1037:706
X-AuthFastPath: 0 (Was 255)
X-AuthSMTP-Origin: 52.5.185.120/25
X-AuthVirus-Status: No virus detected - but ensure you scan with your own
anti-virus system.
X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_LOW
autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] A Better MMR Definition
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
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: Fri, 24 Feb 2017 04:36:20 -0000
--5mCyUwZo2JvN/JJP
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
On Thu, Feb 23, 2017 at 07:32:43PM -0800, Bram Cohen wrote:
> On Thu, Feb 23, 2017 at 7:15 PM, Peter Todd <pete@petertodd.org> wrote:
>=20
> >
> > Glad we're on the same page with regard to what's possible in TXO
> > commitments.
> >
> > Secondly, am I correct in saying your UTXO commitments scheme requires
> > random
> > access? While you describe it as a "merkle set", obviously to be merkel=
ized
> > it'll have to have an ordering of some kind. What do you propose that
> > ordering
> > to be?
> >
>=20
> The ordering is by the bits in the hash. Technically it's a Patricia Trie.
> I'm using 'merkle tree' to refer to basically anything with a hash root.
The hash of what? The values in the set?
> > Maybe more specifically, what exact values do you propose to be in the =
set?
> >
> >
> That is unspecified in the implementation, it just takes a 256 bit value
> which is presumably a hash of something. The intention is to nail down a
> simple format and demonstrate good performance and leave those semantics =
to
> a higher layer. The simplest thing would be to hash together the txid and
> output number.
Ok, so let's assume the values in the set are the unspent outpoints.
Since we're ordering by the hash of the values in the set, outpoints will be
distributed uniformly in the set, and thus the access pattern of data in the
set is uniform.
Now let's fast-forward 10 years. For the sake of argument, assume that for
every 1 UTXO in the set that corresponds to funds in someone's wallet that =
are
likely to be spent, there are 2^12 =3D 4096 UTXO's that have been permanent=
ly
lost (and/or created in spam attacks) and thus will never be spent.
Since lost UTXO's are *also* uniformly distributed, if I'm processing a new
block that spends 2^12 =3D 4096 UTXO's, on average for each UTXO spent, I'll
have to update log2(4096) =3D 12 more digests than I would have had those "=
dead"
UTXO's not existed.
Concretely, imagine our UTXO set had just 8 values in it, and we were updat=
ing
two of them:
#
/ \
/ \
/ \
/ \
/ \
# #
/ \ / \
/ \ / \
# . . #
/ \ / \ / \ / \
. X . . . . X .
To mark two coins as spent, we've had to update 5 inner nodes.
Now let's look at what happens in an insertion-ordered TXO commitment schem=
e.
For sake of argument, let's assume the best possible case, where every UTXO
spent in that same block was recently created. Since the UTXO's are recently
created, chances are almost every single one of those "dead" UTXO's will ha=
ve
been created in the past. Thus, since this is an insertion-ordered data
structure, those UTXO's exist in an older part of the data structure that o=
ur
new block doesn't need to modify at all.
Concretely, again let's imagine a TXO commitment with 8 values in it, and t=
wo
of them being spent:
#
/ \
/ \
/ \
/ \
/ \
. #
/ \ / \
/ \ / \
. . . #
/ \ / \ / \ / \
. . . . . . X X
To mark two coins as spent, we've only had to update 3 inner nodes; while o=
ur
tree is higher with those lost coins, those extra inner nodes are amortised
across all the coins we have to update.
The situation gets even better when we look at the *new* UTXO's that our bl=
ock
creates. Suppose our UTXO set has size n. To mark a single coin as spent, we
have to update log2(n) inner nodes. We do get to amortise this a bit at the=
top
levels in the tree, but even if we assume the amortisation is totally free,
we're updating at least log2(n) - log2(m) inner nodes "under" the amortised
nodes at the top of the tree for *each* new node.
Meanwhile with an insertion-ordered TXO commitment, each new UTXO added to =
the
data set goes in the same place - the end. So almost none of the existing d=
ata
needs to be touched to add the new UTXOs. Equally, the hashing required for=
the
new UTXO's can be done in an incremental fashion that's very L1/L2 cache
friendly.
tl;dr: Precisely because access patterns in TXO commitments are *not* unifo=
rm,
I think we'll find that from a L1/L2/etc cache perspective alone, TXO
commitments will result in better performance than UTXO commitments.
Now it is true that Bitcoin's current design means we'll need a map of
confirmed outpoints to TXO insertion order indexes. But it's not particular=
ly
hard to add that "metadata" to transactions on the P2P layer in the same way
that segwit added witnesses to transactions without modifying how txids were
calculated; if you only connect to peers who provide you with TXO index
information in blocks and transactions, you don't need to keep that map
yourself.
Finally, note how this makes transactions *smaller* in many circumstances: =
it's
just a 8-byte max index rather than a 40 byte outpoint.
--=20
https://petertodd.org 'peter'[:-1]@petertodd.org
--5mCyUwZo2JvN/JJP
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
-----BEGIN PGP SIGNATURE-----
iQEcBAEBCAAGBQJYr7g2AAoJECSBQD2l8JH7cP4H/2rxlMxRuSpOHm3yH3NhX6Q1
+7bKiis07RYfTO5c8IaGqUqHorqDLXAQI2hXx37FyeE90H/u12Ev7PiZfVst6qgD
aqGSSaBQIvPVzhh3EBhTAmokHXQMucWt5Ibx8zJecYbGz6AWWR89jsBIfh5nPSnC
pEpfOmT5WUQNEhL1M9HN0m/phXcmr2+NgqjopyQGl7nxuy+2V99zHRn1gHU7o4QS
UWOyRMQidlGoi/nqm2XBO3jZmySlVs6w/RPReSZEw0rYcJVaw3NCZcr5UCCxiznd
qfulbhOf0dx5BpdPnqngMfteUMlVeXinUlOmJ1q1NXkrhOvEX5qgnvI34PHKrDk=
=6ew2
-----END PGP SIGNATURE-----
--5mCyUwZo2JvN/JJP--
|
