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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
|
Return-Path: <gmaxwell@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 5DC6A825
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 23 Jan 2018 00:30:09 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-vk0-f41.google.com (mail-vk0-f41.google.com
[209.85.213.41])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 8465C134
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 23 Jan 2018 00:30:08 +0000 (UTC)
Received: by mail-vk0-f41.google.com with SMTP id j204so2817886vke.12
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 22 Jan 2018 16:30:08 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:sender:from:date:message-id:subject:to;
bh=AAJaxFw9tvvN14AtDNOyTO0kTsrbG+pXxWpCBeCrj0M=;
b=Ae7IBqI5FxTMHhGJwsArbMkHPMlcAb2mJjDXEknHBGcMz88gU4Nk5qnSpQFFBOODS+
bgB2pSW97Q2+4Fkw81I8v36fGm3ev1XN982Q6rH84VV1mzGvO56mTxzCyqLBcHmK2M5L
9ss7cfK9XA/LlUpjnhaCpMfkitJUq1nL8fhKd5FHXe+CEz7mDKH6Upvnng4pulavd0MM
9IdLgsqFtoxlBun4TcHcCiI2SfuvBeUqGJsVWLT57bae9HXski+yYork2myB3s+J6/K3
ZOn2JD2QHg+UY9hnAs3aVOFr/r4up9oHMyC8uZMv4mNg5Hs1l4ebr0tKf3ce+KQ6AlUH
ktfQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:sender:from:date:message-id:subject
:to; bh=AAJaxFw9tvvN14AtDNOyTO0kTsrbG+pXxWpCBeCrj0M=;
b=IoBSfaNR4/r3HjhD3JCtFR1jua0qWxvgux6pB52O1V1Xam6VTRK/aRgQeZ4bVT9I4j
5LWLQuZqTtFvZ7Y0DNuptheoRPmMW7eWOTuxHb+pLoFo08m84f6itbbIey9PZyzoyaZ/
PcGSIqhQJQ+wwW3QhTeTrBUTPt+gSAj94WTljbdrCuxN+u3J6IpPd6AZC92rGFLwMLPf
CQN1I+5ckDic6MChUySYa9t+89VOu2vQxsYMeOVkukIWFqwMA9IgG1M1m2v48r8NUJKE
Ym+oYl5UbzRwTGtWyAUJj0TQEwp7Q+Y2XgmTUiagKDTIILLSOZCM8EFRruVpj50oJ7kx
Rfrg==
X-Gm-Message-State: AKwxytdo1T1vM73g29Ok/ARaxwiXoUKpUuDJfDdpr60oQ6bX7u7sZGVf
HRVpWlj+HLcbd3i1uQYmv1tKRTU7w/NeNwvKI6Phmg==
X-Google-Smtp-Source: AH8x225BO2MbhH1Q3Wx8e59ZSvOZmPFx1Estfho6enPywx/ETc7N45UnFaFMIvHd+iA3Hr15ESbqk8HV2upcXrahlDQ=
X-Received: by 10.31.149.195 with SMTP id x186mr491013vkd.14.1516667407472;
Mon, 22 Jan 2018 16:30:07 -0800 (PST)
MIME-Version: 1.0
Sender: gmaxwell@gmail.com
Received: by 10.103.78.155 with HTTP; Mon, 22 Jan 2018 16:30:06 -0800 (PST)
From: Gregory Maxwell <greg@xiph.org>
Date: Tue, 23 Jan 2018 00:30:06 +0000
X-Google-Sender-Auth: 5A0mQp2OPVRzsPUjl4DPiwUWC2w
Message-ID: <CAAS2fgTXg5kk6TyUM9dS=tf5N0_Z-GKVmzMLwTW1HxUgrqdo+Q@mail.gmail.com>
To: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset="UTF-8"
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, 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, 23 Jan 2018 01:37:09 +0000
Subject: [bitcoin-dev] Taproot: Privacy preserving switchable scripting
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, 23 Jan 2018 00:30:09 -0000
Interest in merkelized scriptPubKeys (e.g. MAST) is driven by two main
areas: efficiency and privacy. Efficiency because unexecuted forks of
a script can avoid ever hitting the chain, and privacy because hiding
unexecuted code leaves scripts indistinguishable to the extent that
their only differences are in the unexecuted parts.
As Mark Friedenbach and others have pointed out before it is almost
always the case that interesting scripts have a logical top level
branch which allows satisfaction of the contract with nothing other
than a signature by all parties. Other branches would only be used
where some participant is failing to cooperate. More strongly stated,
I believe that _any_ contract with a fixed finite participant set
upfront can be and should be represented as an OR between an N-of-N
and whatever more complex contract you might want to represent.
One point that comes up while talking about merkelized scripts is can
we go about making fancier contract use cases as indistinguishable as
possible from the most common and boring payments. Otherwise, if the
anonymity set of fancy usage is only other fancy usage it may not be
very large in practice. One suggestion has been that ordinary
checksig-only scripts should include a dummy branch for the rest of
the tree (e.g. a random value hash), making it look like there are
potentially alternative rules when there aren't really. The negative
side of this is an additional 32-byte overhead for the overwhelmingly
common case which doesn't need it. I think the privacy gains are
worth doing such a thing, but different people reason differently
about these trade-offs.
It turns out, however, that there is no need to make a trade-off. The
special case of a top level "threshold-signature OR
arbitrary-conditions" can be made indistinguishable from a normal
one-party signature, with no overhead at all, with a special
delegating CHECKSIG which I call Taproot.
Let's say we want to create a coin that can be redeemed by either
Alice && Bob or by CSV-timelock && Bob.
Alice has public A, Bob has pubkey B.
We compute the 2-of-2 aggregate key C = A + B. (Simplified; to
protect against rogue key attacks you may want to use the MuSig key
aggregation function [1])
We form our timelock script S = "<timeout> OP_CSV OP_DROP B OP_CHECKSIGVERIFY"
Now we tweak C to produce P which is the key we'll publish: P = C + H(C||S)G.
(This is the attack hardened pay-to-contract construction described in [2])
Then we pay to a scriptPubKey of [Taproot supporting version] [EC point P].
Now Alice and Bob-- assuming they are both online and agree about the
resolution of their contract-- can jointly form a 2 of 2 signature for
P, and spend as if it were a payment to a single party (one of them
just needs to add H(C||S) to their private key).
Alternatively, the Taproot consensus rules would allow this script to
be satisfied by someone who provides the network with C (the original
combined pubkey), S, and does whatever S requires-- e.g. passes the
CSV check and provides Bob's signature. With this information the
network can verify that C + H(C||S) == P.
So in the all-sign case there is zero overhead; and no one can tell
that the contract alternative exists. In the alternative redemption
branch the only overhead is revealing the original combined pubkey
and, of course, the existence of the contract is made public.
This composes just fine with whatever other merkelized script system
we might care to use, as the S can be whatever kind of data we want,
including the root of some tree.
My example shows 2-of-2 but it works the same for any number of
participants (and with setup interaction any threshold of
participants, so long as you don't mind an inability to tell which
members signed off).
The verification computational complexity of signature path is
obviously the same as any other plain signature (since its
indistinguishable). Verification of the branch redemption requires a
hash and a multiplication with a constant point which is strictly more
efficient than a signature verification and could be efficiently fused
into batch signature validation.
The nearest competitor to this idea that I can come up with would
supporting a simple delegation where the output can be spent by the
named key, or a spending transaction could provide a script along with
a signature of that script by the named key, delegating control to the
signed script. Before paying into that escrow Alice/Bob would
construct this signature. This idea is equally efficient in the common
case, but larger and slower to verify in the alternative spend case.
Setting up the signature requires additional interaction between
participants and the resulting signature must be durably stored and
couldn't just be recomputed using single-party information.
I believe this construction will allow the largest possible anonymity
set for fixed party smart contracts by making them look like the
simplest possible payments. It accomplishes this without any overhead
in the common case, invoking any sketchy or impractical techniques,
requiring extra rounds of interaction between contract participants,
and without requiring the durable storage of other data.
[1] https://eprint.iacr.org/2018/068
[2] https://blockstream.com/sidechains.pdf Appendix A
|
