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
|
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 B767998C
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 01:11:52 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from outmail148106.authsmtp.co.uk (outmail148106.authsmtp.co.uk
[62.13.148.106])
by smtp1.linuxfoundation.org (Postfix) with ESMTP id 4A9EC19A
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 01:11:50 +0000 (UTC)
Received: from mail-c232.authsmtp.com (mail-c232.authsmtp.com [62.13.128.232])
by punt22.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v1N1BoKS030331
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 01:11:50 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 v1N1Bmif028742
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO)
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 01:11:49 GMT
Received: from [127.0.0.1] (localhost [127.0.0.1])
by petertodd.org (Postfix) with ESMTPSA id 3232440123
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 23 Feb 2017 01:11:48 +0000 (UTC)
Received: by localhost (Postfix, from userid 1000)
id 746DC20245; Wed, 22 Feb 2017 20:11:47 -0500 (EST)
Date: Wed, 22 Feb 2017 20:11:47 -0500
From: Peter Todd <pete@petertodd.org>
To: bitcoin-dev@lists.linuxfoundation.org
Message-ID: <20170223011147.GB905@savin.petertodd.org>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="zx4FCpZtqtKETZ7O"
Content-Disposition: inline
User-Agent: Mutt/1.5.23 (2014-03-12)
X-Server-Quench: 0daca1cf-f965-11e6-829f-00151795d556
X-AuthReport-Spam: If SPAM / abuse - report it at:
http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVJwpGK10IU0Fd
P1hyKltILEZaQVBf Ri5dBBEKBAw1ADwr dVUTOktfYVU4Cld1
UkhIRUJSFQ9pABYF D1AbUAd3aQROfWBx Z0Z9XHVEXQo8dDh8
MBMNQ20EbWBkai4a V0RaOQMAIVAbf0wT dwZ2UnYQYGRSYGdo
RV49emhpZGgGd3UI TlxQc0QucWFDFTk5 QhEeGDgpAVZNSyJ7
KRs6YlgREUpZOw0p NlU9HFwfKRxaFgoW FUwFHTRUKUQFLwAA
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
Subject: [bitcoin-dev] TXO commitments do not need a soft-fork to be useful
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: Thu, 23 Feb 2017 01:11:52 -0000
--zx4FCpZtqtKETZ7O
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
Something I've recently realised is that TXO commitments do not need to be
implemented as a consensus protocol change to be useful. All the benefits t=
hey
provide to full nodes with regard to allowing for old UTXO data to be prune=
d -
and thus solving the UTXO bloat problem - can be implemented even without
having miners commit to the TXO commitment itself. This has a significant
deployment advantage too: we can try out multiple TXO commitment schemes, in
production, without the need for consensus changes.
# Reasoning
1) Like any other merkelized data structure, a TXO commitment allows a data=
set
- the TXO set - to be securely provided by an untrusted third party, allowi=
ng
the data itself to be discarded. So if you have a valid TXO commitment, you=
can
discard the TXO data itself, and rely on untrusted entities to provide you =
that
data on demand.
2) The TXO set is a super-set of the UTXO set; all data in the UTXO set is =
also
present in the TXO set. Thus a TXO commitment with spent TXO's pruned is
equivalent to a UTXO set, doubly so if inner nodes in the commitment tree
commit to the sum-unspent of their children.
3) Where a outpoint-indexed UTXO set has a uniform access pattern, an
insertion-ordered TXO set has a delibrately *non-uniform* access pattern: n=
ot
only are new entries to the TXO set always appended to the end - an operati=
on
that requires a known, log2(n), sized set of merkle tips - but due to lost
coins alone we can guarantee that older entries in the TXO set will be less
frequently updated than newer entries.
4) Thus a full node that doesn't have enough local storage to maintain the =
full
UTXO set can instead keep track of a TXO commitment, and prune older UTXO's
=66rom it that are unlikely to be spent. In the event those UTXO's are spen=
t,
transactions and blocks spending them can trustlessly provide the necessary
data to temporarily fill-in the node's local TXO set database, allowing the
next commitment to be calculated.
5) By *not* committing the TXO commitment in the block itself, we obsolete =
my
concept of delayed TXO commitments: you don't need to have calculated the T=
XO
commitment digest to validate a block anyway!
# Deployment Plan
1) Implement a TXO commitment scheme with the ability to efficiently store =
the
last n versions of the commitment state for the purpose of reorgs (a
reference-counted scheme naturally does this).
2) Add P2P support for advertising to peers what parts of the TXO set you've
pruned.
3) Add P2P support to produce, consume, and update TXO unspentness proofs as
part of transaction and block relaying.
4) Profit.
# Bootstrapping New Nodes
With a TXO commitment scheme implemented, it's also possible to produce
serialized UTXO snapshots for bootstrapping new nodes. Equally, it's obviou=
sly
possible to distribute those snapshots, and have people you trust attest to=
the
validity of those snapshots.
I argue that a snapshot with an attestation from known individuals that you
trust is a *better* security model than having miners attest to validity: t=
he
latter is trusting an unknown set of unaccountable, anonymous, miners.
This security model is not unlike the recently implemented -assumevalid
scheme(1), in that auditing the validity of the assumed valid TXO commitmen=
ts
is something anyone can do provided they have a full node. Similarly, we co=
uld
ship Bitcoin nodes with an assumed-valid TXO commitment, and have those nod=
es
fill in the UTXO data from their peers.
However it is a weaker security model, in that a false TXO commitment can m=
ore
easily be used to trick a node into accepting invalid transactions/blocks;
assumed valid blocks requires proof-of-work to pull off this attack. A
compromise may be to use assumed valid TXO commitments, extending my partial
UTXO set(2) suggestion of having nodes validate the chain backwards, to
eventually validate 100% of the chain.
# References
1) https://github.com/bitcoin/bitcoin/pull/9484
2) [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framewo=
rk),
Peter Todd, Jul 17th 2013, Bitcoin development mailing list,
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-July/002917=
=2Ehtml
--=20
https://petertodd.org 'peter'[:-1]@petertodd.org
--zx4FCpZtqtKETZ7O
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
-----BEGIN PGP SIGNATURE-----
iQEcBAEBCAAGBQJYrjbQAAoJECSBQD2l8JH7SI8H/1a/5zXlHpgLBE2/ujxQfh04
pJ9W2wlxw4l4LZLHF8Jtk6WeURMWPSrocoi46uq/MrbPjxq+ySbZQBVRskVwZGd6
5uD5cZjlUlFLZB6Yz5qP2A5dmj/7BDcOT12cSU7evXDEPh1iWIjB2f3Bo5Z6wmG9
QYkZt5dBKmcnRqyx4MyVTCfrrK3jBBoMUgIht4bF9+hwc7X+4M91KqwRg2XfrDMO
5tOBrfzIOpDajjZlwNB16fN1VZNy86UkuCtC7dSn8kvaela2FW6Cv9KPB4fSrBhq
XXWttxuCoheD82C+LgojBwE1B6wEwi+6LOW9oJdm4sIgZe3e3+DOjnvs2pq4u/M=
=h5w+
-----END PGP SIGNATURE-----
--zx4FCpZtqtKETZ7O--
|
