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)
Subject: [bitcoin-dev] UTXO set commitment hash
Precedence: list


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