1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
Return-Path: <runesvend@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id D55CF13EB
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 18 Sep 2015 19:05:43 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wi0-f173.google.com (mail-wi0-f173.google.com
[209.85.212.173])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 49A6E15B
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 18 Sep 2015 19:05:43 +0000 (UTC)
Received: by wicge5 with SMTP id ge5so44834630wic.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 18 Sep 2015 12:05:41 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=from:content-type:content-transfer-encoding:subject:message-id:date
:to:mime-version;
bh=W79hzA9f6JDzbJ37pSlGcl+66s3Os/78Nph1G7cpfUs=;
b=EatUY81dv8Pqa1so3uYBGJfHnSeyUHmz7ZMmtpGrh1x12IbUVm+i9aJ/sFmjkCOnfc
vSm7PACA+Fr6h00vpL6lW3hlKukGyp8oG3ACH6jnqpvMoRKaz8AOI0006Wzjl+EYsnPs
d9mvFtXn+FMHNQ6orpQjYk8ao17H2PqAWPa/eNO2I5l/2A1pKpymQyF4u/mJvDC5g5xN
kRqTdZ1CUzjTMYC6oykeMNkGrVnfVf2XSoCCQokrH/iyAsXuCvHCsiJR4X+3ot9+OZFs
stK/o11Drq6lItFL28Kkcq13JafI4IAek6ZdyUR/0pY1MCmYP+KmE3crNxkMZaIzDTTA
1LgQ==
X-Received: by 10.194.60.115 with SMTP id g19mr8711333wjr.29.1442603141665;
Fri, 18 Sep 2015 12:05:41 -0700 (PDT)
Received: from [192.168.1.33] ([212.60.121.11])
by smtp.gmail.com with ESMTPSA id le3sm209348wjb.25.2015.09.18.12.05.40
for <bitcoin-dev@lists.linuxfoundation.org>
(version=TLS1 cipher=ECDHE-RSA-RC4-SHA bits=128/128);
Fri, 18 Sep 2015 12:05:41 -0700 (PDT)
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\))
X-Mailer: Apple Mail (2.2104)
X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, MIME_QP_LONG_LINE,
RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: [bitcoin-dev] Hash of UTXO set as consensus-critical
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, 18 Sep 2015 19:05:44 -0000
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=
|
