From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 366B6258 for ; 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 ; 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 ; 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 To: Bitcoin Dev 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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--