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
|
Return-Path: <bob_bitcoin@mcelrath.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 366B6258
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 30 Oct 2015 16:36:07 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mcelrath.org (moya.mcelrath.org [50.31.3.130])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 9A0EA16E
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 30 Oct 2015 16:36:06 +0000 (UTC)
Received: from mcelrath.org (localhost [127.0.0.1])
by mcelrath.org (8.14.3/8.14.3/Debian-9.4) with ESMTP id t9UGa5EY021985
(version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT)
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 30 Oct 2015 16:36:05 GMT
Received: (from mcelrath@localhost)
by mcelrath.org (8.14.3/8.14.3/Submit) id t9UGa425021984
for bitcoin-dev@lists.linuxfoundation.org; Fri, 30 Oct 2015 16:36:04 GMT
X-Authentication-Warning: mcelrath.org: mcelrath set sender to
bob_bitcoin@mcelrath.org using -f
Date: Fri, 30 Oct 2015 16:36:04 +0000
From: Bob McElrath <bob_bitcoin@mcelrath.org>
To: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20151030163604.GA29303@mcelrath.org>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha1;
protocol="application/pgp-signature"; boundary="FCuugMFkClbJLl1L"
Content-Disposition: inline
User-Agent: Mutt/1.5.20 (2009-06-14)
X-Spam-Status: No, score=-2.9 required=5.0 tests=BAYES_00,RP_MATCHES_RCVD
autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Fri, 30 Oct 2015 17:46:35 +0000
Subject: [bitcoin-dev] UTXO set commitment hash
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development 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, 30 Oct 2015 16:36:07 -0000
--FCuugMFkClbJLl1L
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
The state of bitcoin transactions can be committed to in blocks by keeping =
two
running hashes, one of unspent transaction outputs and one of spent transac=
tion
outputs. A "running hash" $R$ I define as being computed by taking the pre=
vious
value of the hash $r$, concatenating it with the new data $x$, and hashing =
it:
\[
R =3D hash(r|x).
\]
In the case of the UTXO set, the data $x$ can be taken to be the concatenat=
ion
(txid|vout|amount) for all outputs, let's call this running hash hTXO. Bec=
ause
data cannot be "removed" from this set commitment, a second hash can be com=
puted
consisting of the spent outputs, let's call this hSTXO. Thus the pair of h=
ashes
(hTXO, hSTXO) is equivalent to a hash of all unspent outputs. These hashes=
can
be placed into a block's Merkle tree by miners with a soft fork. It can be
reduced to a single hash hUXTO =3D hash(hTXO|hSXTO) if desired.
By defining *how* to compute (hTXO, hSXTO) we can define an implementation
independent definition of consensus that is extremely cheap to compute. The
order in which outputs are hashed is clearly important, but bitcoin has a w=
ell
defined ordering already in terms of the order in which transactions appear=
in
blocks, and the sequential order of outputs.
In the recent discussion surrounding leveldb and jgarzik's new sqlite branc=
h, it
has been brought up repeatedly by gmaxwell that this db is "consensus criti=
cal".
As a data structure storing the state of transactions, of course it's conse=
nsus
critical. However there's only one right answer to what the set of UTXOs i=
s.
Any other result reported by the db is simply wrong. By creating and publi=
shing
(hTXO, hSXTO), miners can publish their view of the transaction state, and =
any
implementation can be validated against it.
As I understand it, leveldb is in the bitcoin core source tree because it c=
ould
have bugs and give the wrong answer for a given UTXO (see BIP50). This is =
worse
than a consensus failure, it's just wrong, and the argument that we have to=
keep
leveldb around and maintain it because it could be wrong is pretty ugly, an=
d I
don't think anyone actually wants to do this. Let's not be wrong in the fi=
rst
place, and let's choose databases based on performance and other considerat=
ions.
"Not being wrong" should go without saying, regardless of implementation
details.
It should be noted that (hTXO, hSXTO) can be computed twice, once without t=
he
database (while processing a new block) and once by requesting the same data
=66rom the database. So bad database behavior can be detected and prevente=
d from
causing consensus failures. And then we can remove leveldb from the core.
--
Cheers, Bob McElrath
"For every complex problem, there is a solution that is simple, neat, and w=
rong."
-- H. L. Mencken=20
--FCuugMFkClbJLl1L
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
Content-Disposition: inline
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
iEYEARECAAYFAlYznHQACgkQjwioWRGe9K3OSwCfbqyF4J/3GHa0hFo2613Y2C39
LK4An3gnZ+Pr/WHeU8i0CWHU4jd1K43h
=Yznw
-----END PGP SIGNATURE-----
--FCuugMFkClbJLl1L--
|
