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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
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 09E291667
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 22 May 2018 18:17:46 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-oi0-f54.google.com (mail-oi0-f54.google.com
[209.85.218.54])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id F25B96C6
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 22 May 2018 18:17:44 +0000 (UTC)
Received: by mail-oi0-f54.google.com with SMTP id v2-v6so17084503oif.3
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 22 May 2018 11:17:44 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:from:date:message-id:subject:to;
bh=wlwy3NwBwZF0y5/wRss//wVQrLd68Z9PYbzclBy1p8w=;
b=BBivYU9i2ve8j+lv2Dih4Bh2GRZpEak4rw7r6ZfTg5f6AsuU/wPiod07RjnvP3oXYG
VQFOz8kSo9a2JCBLgEEwjd/0mvoFp90/NtPdu1DCNSDBcCLVhULFXFcrAi/rVI9CF41k
8VZrGWUZvw42pGaEQI93OCWw5Dgcqdd0vFappGj0cVQiqrm8GZymp3d53VRrxTASRP2j
5siCMGBP7QzFj/TNtvNTmYX++YODC8iJb5zsjrMQag3rOfRKQS1kwjhtXFlZgcyv6TIx
6CUK/NP/61Eyfdkg1PLUKsPzsuD4U/OrtLFsh+6aUdcFMGMNCkkfugW3r0B47lLBYe/M
mYEQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:from:date:message-id:subject:to;
bh=wlwy3NwBwZF0y5/wRss//wVQrLd68Z9PYbzclBy1p8w=;
b=GN09D7eUfT37cxAMMWWLkR5jD6K62EwZY4zhBNuw02/fW0BelZ1qqdfZcQrblHu4Yd
4aVDJ+OCMVp6lcdb64LSMIX2grnXq+HWytDg7feFeF/1YYtMc+h5ZHpW40RF2KjFbX1w
JsrBrn3Me6FkGF3R4vNytrfPtCbRe8KYiaZQkmOUTH7prsDz7ho0zUAo9Q/27CJ/9EnB
SDxEO0jhTGB3ctIOPChbTTXBzm7T3S3DJ6J/XCiTV/IzTjXJVo7T2f2Ie+rX7au7vNBa
tSVO2fe1DCqQiU16SCgdV+wqDtd5+1PgbWKZ88smy5Tq+0K2Fh+d9ZHMFAZT4HVLRHhJ
CDsQ==
X-Gm-Message-State: ALKqPwfFlihtirNJ/neCwJRsuiYW/fclqtbMpfl+Kkyzd5n+9rUSe5Vt
RTiL5Wwz2OFjt2JMJS0pFcI6h0sLU7QgJLnTlUvsOua4
X-Google-Smtp-Source: AB8JxZp7UtWFOMc2jGbtJ4E6qF/z/EuNWv2kHB7Fo2pncOX30Gbi/rk3aCWQoTYFBhdcHp0Quz6sPN7Q+DRRrEUABd0=
X-Received: by 2002:aca:f12:: with SMTP id 18-v6mr15328197oip.46.1527013063836;
Tue, 22 May 2018 11:17:43 -0700 (PDT)
MIME-Version: 1.0
Received: by 2002:a4a:6ac8:0:0:0:0:0 with HTTP; Tue, 22 May 2018 11:17:42
-0700 (PDT)
From: Pieter Wuille <pieter.wuille@gmail.com>
Date: Tue, 22 May 2018 11:17:42 -0700
Message-ID: <CAPg+sBgKY-nmL=x+LVubtB0fFBAwd-1CDHT7zhidX8p9DLSGyg@mail.gmail.com>
To: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.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
Subject: [bitcoin-dev] Should Graftroot be optional?
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, 22 May 2018 18:17:46 -0000
Hello all,
Given the recent discussions about Taproot [1] and Graftroot [2], I
was wondering if a practical deployment needs a way to explicitly
enable or disable the Graftroot spending path. I have no strong
reasons why this would be necessary, but I'd like to hear other
people's thoughts.
As a refresher, the idea is that a script type could exists which
looks like a pubkey Q, but can be spent either:
* By signing the spending transaction directly using Q (key spending)
* By proving Q was derived as Q = P + H(P,S)*G, with a script S and
its inputs (Taproot script spending).
* By signing a script S using Q, and providing S's inputs (Graftroot
script spending).
Overall, these constructions let us create combined
pay-to-pubkey-or-script outputs that are indistinguishable, and don't
even reveal a script spending path existed in the first place when the
key spending path is used. The two approaches ((T)aproot and
(G)raftroot) for the script spending path have different trade-offs:
* T outputs can be derived noninteractively from key and scripts; G
outputs need an interaction phase where the key owner(s) sign off on
the potential script spending paths.
* T lets you prove what all the different spending paths are.
* T without any other technology only needs to reveal an additional
point when spending a single script; G needs half-aggregated
signatures [3] to achieve the same, which complicates design (see
[4]).
* G is more compact when dealing with many spending paths (O(1) in the
number of spending paths), while T spends need to be combined with
Merkle branches to deal with large number of spends (and even then is
still O(log n)).
* G spending paths can be added after the output is created; T
requires them be fixed at output creation time.
My question is whether it is safe to always permit both types of
script spending paths, or an explicit commitment to whether Graftroot
is permitted is necessary. In theory, it seems that this shouldn't be
needed: the key owners are always capable of spending the funds
anyway, so them choosing to delegate to others shouldn't enable
anything that isn't
possible by the key owners already.
There are a few concerns, however:
* Accidentally (participating in) signing a script may have more broad
consequences. Without Graftroot, that effect is limited to a single
transaction with specific inputs and outputs, and only as long as all
those inputs are unspent. A similar but weaker concern exists for
SIGHASH_NOINPUT.
* In a multisignature setting (where the top level key is an aggregate
of multiple participants), the above translates to the ability for a
(threshold satsisfying) subset of participants being able to (possibly
permanently) remove others from the set of signers (rather than for a
single output).
* In a situation where private keys are stored in an HSM, without
Graftroot an attacker needs access to the device and convince it to
sign for every output he wants to steal (assuming the HSM prevents
leaking private keys). With Graftroot, the HSM may be tricked into
signing a script that does not include itself. Arguably, in a
Graftroot setting such an HSM would need a degree of protection
similar to not leaking private keys applied to not signing scripts,
but this may be less obvious.
Overall, none of these are convincing points, but they do make me
uncomfortable about the effect the Graftroot spending path may have on
some use cases. Given that Taproot/Graftroot's primary advantage is
increasing fungibility by making all outputs look identical, it seems
good to discuss potential reasons such outputs couldn't or wouldn't be
adopted in certain applications.
[1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015614.html
[2] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015700.html
[3] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014308.html
[4] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015838.html
Cheers,
--
Pieter
|
