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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
Return-Path: <pieter.wuille@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id E693694B
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 16 May 2017 18:17:22 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f50.google.com (mail-wm0-f50.google.com [74.125.82.50])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 881EE212
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 16 May 2017 18:17:21 +0000 (UTC)
Received: by mail-wm0-f50.google.com with SMTP id b84so142364094wmh.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 16 May 2017 11:17:21 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to
:cc; bh=axSiGFBKpMTC8PS597wVvmwqRJGMUMObePKurV/NBy4=;
b=iBKxXfs7fNd+iEVpGEKZ+hHJk6BmAP8d18fNLzSqNntxUxI7lyFU/vu7odLO9KPf56
B50t3iwYTlAUp6D8SR6rd+dWfHLmiyyMReA18UZRaqAJm/InXayiQEOzTFoKQWnrHF0D
GdGKzbFZtVuVR+hCdRL2beo+AyyEIEoExB4MbcF6U1q3ObVelf9kez1IdLkmfj2toaxG
HN7v1DFeKjEUDyQ/KBalUylVXVZcayFOqMtcxZa8QTE01xOejSejBqXsWWE0KMIJqc/o
bjKOlPjopyFyfNQWbwKY/Hb6XcV7aNpOOG8TDezK+x6XcsX9QtHO1HgwA6VUOShst7kR
LSTQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:in-reply-to:references:from:date
:message-id:subject:to:cc;
bh=axSiGFBKpMTC8PS597wVvmwqRJGMUMObePKurV/NBy4=;
b=CYlC37wEUgulU+DFa47TCTthd2Z2RJjtzUNCoc4h1pL67ZxLCjD+Af8PN1xfhXKLDo
1cMUJjvK4PBBbaRcDSjNyfC2k1hcF3o3C98Lo1Zucx3w64+Bz12bmgI3kjJwv3gaX5L4
Ad5rp8crd8unHOEI9JD7wm+tDz5V1wYyrZ+BC7+Nl8ai+UDKEJuwwMKgpdj6KpSTzmZp
RmCiEDLYCVf3jZMg9ewIyaFCArIZGyV8gLnJmW3FUFFPcp5r9xbmsnEu0INMKmESw2nr
yr3vR8EL8Gl+AbFZhW/hhzp5ZaB7ej5IPNGAWIIqY2zQNZPyfWz/uy9dASA09Hzv3D7H
hDyQ==
X-Gm-Message-State: AODbwcBcVFJuCfmkWTiQEXX7B/KmCUAjqm6c7KIh91OoOYuhA5eavUky
RhGieaDDplavaKusREUE6uj+Q4yeqFCP
X-Received: by 10.80.180.229 with SMTP id x34mr98299edd.91.1494958640098; Tue,
16 May 2017 11:17:20 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.80.135.79 with HTTP; Tue, 16 May 2017 11:17:19 -0700 (PDT)
In-Reply-To: <20170516110104.GA5564@fedora-23-dvm>
References: <CAPg+sBgruEiXya6oFy6VpmR1KPDebjeGDtZZU+facZx5=L_a5w@mail.gmail.com>
<CT3GNfkLsQJyM0EmWXc3HBmnW1h2iptP0SohZnXZfZPffoVmcofD8fs_E3kV5PuFL0pQSQwwk_FyR-8-wdANf15NE8UElNWqcEcc5Ql3n8M=@protonmail.com>
<CAAS2fgTif+Y6VzFG+w7W+CY1+D_roCqGyy392qB2KcDPGpVeiw@mail.gmail.com>
<20170516110104.GA5564@fedora-23-dvm>
From: Pieter Wuille <pieter.wuille@gmail.com>
Date: Tue, 16 May 2017 11:17:19 -0700
Message-ID: <CAPg+sBjJLbhj71Epv=Qfc8HgJhSreN6BOmLkDkvcEGvPwxDNbg@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>
Content-Type: text/plain; charset="UTF-8"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM,
RCVD_IN_DNSWL_NONE 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: Tue, 16 May 2017 18:18:34 +0000
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Rolling UTXO set hashes
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol 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: Tue, 16 May 2017 18:17:23 -0000
On Tue, May 16, 2017 at 4:01 AM, Peter Todd via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> To be clear, *none* of the previous (U)TXO commitment schemes require *miners*
> to participate in generating a commitment. While that was previously thought to
> be true by many, I've seen no counter-arguments to the argument I published I
> few months ago(1) that (U)TXO commitments did not require a soft-fork to
> deploy.
>
> 1) "[bitcoin-dev] TXO commitments do not need a soft-fork to be useful",
> Peter Todd, Feb 23 2017,
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-February/013591.html
I'm aware, I agree, and I even referenced that mail in my original post.
However, all of those approaches still require a network wide choice
to be useful. A validating node that does not maintain a UTXO X must
get a proof of its unspentness from somewhere for at least the block
which contains a spend of X. In a world where such a model is deployed
network-wide, that proof information is generated by the wallet and
relayed wherever needed. In a partial deployment however, you need
nodes that can produce the proof for other nodes, and the ability to
produce a proof is significantly more expensive than running either an
old or a new full node.
This ability to produce proofs becomes even harder when there are
different models deployed at once. Even just having a different
criterion for which UTXOs need a proof (eg. "only outputs created more
than 1000 blocks ago") may already cause compatibility issues. Combine
that with the multitude of ideas about this (insertion-ordered TXO
trees, txid-ordered UTXO Patricia tries, AVL+ trees, append-only
bitfield, ...) with different trade-offs (in CPU, RAM for validators,
complexity for wallets/index services, ...), I don't think we're quite
ready to make that choice.
To be clear: I'm very much in favor of moving to a model where the
responsibilities of full nodes are reduced in the long term. But
before that can happen there will need to be implementations,
experiments, analysis, ...
Because of that, I think it is worthwhile to investigate solutions to
the "how can we efficiently compare UTXO sets" problem separately from
the "how do we reduce full node costs by sending proofs instead of it
maintaining the data". And rolling UTXO set hashes are a solution for
just the first - and one that has very low costs and no normative
datastructures at all.
--
Pieter
|
