diff options
author | Bob McElrath <bob_bitcoin@mcelrath.org> | 2015-10-30 16:36:04 +0000 |
---|---|---|
committer | bitcoindev <bitcoindev@gnusha.org> | 2015-10-30 16:36:07 +0000 |
commit | 0888212cf7b00aa2fffa19ac02e77f3a7364f328 (patch) | |
tree | 92475db902057c9d560662be67b259bfd420ff91 /4c | |
parent | 22660a9ee4480043c49a35408708337489b8e47e (diff) | |
download | pi-bitcoindev-0888212cf7b00aa2fffa19ac02e77f3a7364f328.tar.gz pi-bitcoindev-0888212cf7b00aa2fffa19ac02e77f3a7364f328.zip |
[bitcoin-dev] UTXO set commitment hash
Diffstat (limited to '4c')
-rw-r--r-- | 4c/68ed16850d65f0228e61ac78f5f5a10b6abfd3 | 146 |
1 files changed, 146 insertions, 0 deletions
diff --git a/4c/68ed16850d65f0228e61ac78f5f5a10b6abfd3 b/4c/68ed16850d65f0228e61ac78f5f5a10b6abfd3 new file mode 100644 index 000000000..6858188d6 --- /dev/null +++ b/4c/68ed16850d65f0228e61ac78f5f5a10b6abfd3 @@ -0,0 +1,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-- + |