From: =?utf-8?Q?Rune_Kj=C3=A6r_Svendsen?= <runesvend@gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Message-Id: <5D55F6EC-801B-4607-882F-B76CF57298B1@gmail.com>
Date: Fri, 18 Sep 2015 21:05:37 +0200
To: bitcoin-dev@lists.linuxfoundation.org
Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2104\))
Subject: [bitcoin-dev] Hash of UTXO set as consensus-critical
Precedence: list

Currently, when a new node wants to join the network, it needs to =
retrieve the entire blockchain history, starting from January 2009 and =
up until now, in order to derive a UTXO set that it can verify new =
blocks/transactions against. With a blockchain size of 40GB and a UTXO =
size of around 1GB, the extra bandwidth required is significant, and =
will keep increasing indefinitely. If a newly mined block were to =
include the UTXO set hash of the chain up until the previous block =E2=80=94=
 the hash of the UTXO set on top of which this block builds =E2=80=94 =
then new nodes, who want to know whether a transaction is valid, would =
be able to acquire the UTXO set in a trustless manner, by only verifying =
proof-of-work headers, and knowing that a block with an invalid UTXO set =
hash would be rejected.

I=E2=80=99m not talking about calculating a complicated tree structure =
from the UTXO set, which would put further burden on already burdened =
Bitcoin Core nodes. We simply include the hash of the current UTXO set =
in a newly created block, such that the transactions in the new block =
build *on top* of the UTXO set whose hash is specified. This actually =
alleviates Bitcoin Core nodes, as it will now become possible for nodes =
without the entire blockchain to answer SPV queries (by retrieving the =
UTXO set trustlessly and using this to answer queries). It also saves =
bandwidth for Bitcore Core nodes, who only need to send roughly 1GB of =
data, in order to synchronise a node, rather than 40GB+. I will continue =
to run a full Bitcoin Core node, saving the entire blockchain history, =
but it shouldn=E2=80=99t be a requirement to hold the entire transaction =
history in order to start verifying new transactions.

As far as I can see, this also forces miners to actually maintain an =
UTXO set, rather than just build on top of the chain with the most =
proof-of-work. Producing a UTXO set and verifying a block against a =
chain is the same thing, so by including the hash of the UTXO set we =
force miners to verify the block that they want to build on top of.

Am I missing something obvious, because as far as I can see, this solves =
the problem of quadratic time complexity for initial sync: =
http://www.youtube.com/watch?v=3DTgjrS-BPWDQ&t=3D2h02m12s

The only added step to verifying a block is to hash the UTXO set. So it =
does require additional computation, but most modern CPUs have a SHA256 =
throughput of around 500 MB/s, which means it takes only two seconds to =
hash the UTXO set. And this can be improved further (GPUs can do 2-3 =
GB/s). A small sacrifice for the added ease of initial syncing, in my =
opinion.

/Rune=