summaryrefslogtreecommitdiff
path: root/4c
diff options
context:
space:
mode:
authorBob McElrath <bob_bitcoin@mcelrath.org>2015-10-30 16:36:04 +0000
committerbitcoindev <bitcoindev@gnusha.org>2015-10-30 16:36:07 +0000
commit0888212cf7b00aa2fffa19ac02e77f3a7364f328 (patch)
tree92475db902057c9d560662be67b259bfd420ff91 /4c
parent22660a9ee4480043c49a35408708337489b8e47e (diff)
downloadpi-bitcoindev-0888212cf7b00aa2fffa19ac02e77f3a7364f328.tar.gz
pi-bitcoindev-0888212cf7b00aa2fffa19ac02e77f3a7364f328.zip
[bitcoin-dev] UTXO set commitment hash
Diffstat (limited to '4c')
-rw-r--r--4c/68ed16850d65f0228e61ac78f5f5a10b6abfd3146
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--
+