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
|
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 B99F21026
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 24 Oct 2018 02:22:37 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ot1-f43.google.com (mail-ot1-f43.google.com
[209.85.210.43])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 2D796713
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 24 Oct 2018 02:22:37 +0000 (UTC)
Received: by mail-ot1-f43.google.com with SMTP id z15so3452691otm.12
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 23 Oct 2018 19:22:37 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to;
bh=WUN5ytU8gJJRgQYwshi4TOT3DljG2VyEuZvreIWJcZw=;
b=XAouC8urO3ghqRbrOLSrplPWwqYqC1OEI+gIGU1eeyH/Blx5DHSYdPBAgjQlMPGq87
CLohiGJDv4gR6fia0Lj838qMkUv2WgG7lfjbBbIBAle+ZK64h7f7deNdAXNOsJhR0E88
h9tze1G3yGtfxEk8273btpDgeE/KwNbKDHxL4YBH6nxatlMOBAVj9vGMLxRQEfNG48Fu
YhS0xaAq25ngJKlsW8eOAqk7Z9A9jvcK8PHo7RXoWBE0Za8H7UOhxbZyOupKwDMEISgV
hFkcchfzqz6JMEYe2t+/ZeigfUTgcTVZ+/9JAbQ2r45wrDS+4PMykCaEYuJVm5tP4wih
WhOw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:references:in-reply-to:from:date
:message-id:subject:to;
bh=WUN5ytU8gJJRgQYwshi4TOT3DljG2VyEuZvreIWJcZw=;
b=guLaTgMhwVe0wDBXjC6qyFmi9qPLCT8qCWOz6ZzqJivvIg+cMjB1hj8HKOWHL4MSCc
u7OofQsZbVz0yzZfNynZMY1TGCveRjoGTaGNbJPRre7zJ8Enz39JMHk/Ci4LUGTC8HQU
bZi+Kn2WA9QrUERkhy74FjCPuovuecRoslHyU7xTAEINVjRv+4nzPJ273HJFV74FFDUq
8vSRrfBYefjMSaRR8xuPvg6BT30cHR1nkrP6x6IwgxQbTz+sgOVnVpZa/lz8MES878ts
xzhiYEaEihLITJO3L1iy3/OOZrNn/g8QUJ4eReKFZJw5jAiazKRA5iX3Dfttyp/3Nr1B
YhMA==
X-Gm-Message-State: AGRZ1gK3el1cU+Q1JI709TFq/QZRthGlNxBfFUEDhKn4FpaAY3wmwF/A
R/5VUlU3lsqRdyS6BDrp1gnQ9H3XtBbrKLOCAzY=
X-Google-Smtp-Source: AJdET5fcMsdoUm7oU8Go/Bvd7m3w92a6KIaXFstErR0+FzIWNYWX4uwijmNW7tmNYz+rhH4G8mZwP4OHLnv5SiGIY7o=
X-Received: by 2002:a9d:2377:: with SMTP id k52mr483204otd.238.1540347756195;
Tue, 23 Oct 2018 19:22:36 -0700 (PDT)
MIME-Version: 1.0
References: <CAAS2fgTXg5kk6TyUM9dS=tf5N0_Z-GKVmzMLwTW1HxUgrqdo+Q@mail.gmail.com>
<CAAS2fgSApdSYUWZx+_G7tMPPQm5bC4xjYzZ_mQZv=w-FD-4jWw@mail.gmail.com>
<20180713015157.k637vndspx4hgpfu@erisian.com.au>
In-Reply-To: <20180713015157.k637vndspx4hgpfu@erisian.com.au>
From: Pieter Wuille <pieter.wuille@gmail.com>
Date: Tue, 23 Oct 2018 19:22:24 -0700
Message-ID: <CAPg+sBhAE_WtZvbe7dEmWPMCsxwK4GmDKx2721X45Ua9KvhfEg@mail.gmail.com>
To: Anthony Towns <aj@erisian.com.au>,
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
X-Mailman-Approved-At: Wed, 24 Oct 2018 15:52:32 +0000
Subject: Re: [bitcoin-dev] Generalised taproot
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: Wed, 24 Oct 2018 02:22:37 -0000
On Thu, Jul 12, 2018 at 6:52 PM Anthony Towns via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> On Fri, Jan 26, 2018 at 09:34:39PM +0000, Gregory Maxwell via bitcoin-dev wrote:
> > [pubkey]
> > \-[pubkey]&&CSV
> > \-[fancy script]
>
> I think it's possible to do recursive taproot in this manner in a
> neat way, using Pedersen Commitments.
>
> (Background: A Pedersen commitment uses a second generator in the curve,
> and rather than constructing a point from a single secret, like A=a*G,
> it constructs a point from two secrets, like C=a*G+b*G2, and finding a
> different c,d such that C=c*G+d*G2 gives you the discrete log of G2)
>
> So combining this with the taproot structure gives an equation like:
>
> P = a*G + s*G2 + H(a*G+s*G2, Q)*G
>
> If you take "a" to be a private key (so A=a*G is the corresponding
> pubkey), "s" to be (the hash of) a set of additional conditions for
> spending with the pubkey, and "Q" to be an alternative method of spending,
> you get a recursive taproot construction.
I think this is a very neat construction, and has advantages beyond
solving the recursive-taproot-without-revealing-intermediary-scripts problem
(which is useful, but I would consider a stretch goal at best).
To summarize, this is my understanding of g'root:
* A spending condition is a policy of the form "sign with public key A
and additionally satsify script S". Such a condition is associated with
the point P = A + s*G2 (where G2 is a second independent generator for the
curve, and s=H(S)). To satisfy such a condition, you reveal S, provide
inputs that satisfy S, together with a signature for public key (P - s*G2).
We'll call A the companion key of spending condition P (as opposed to other
public keys which may appear in the script S).
* A scriptPubKey (or redeemScript in case of P2SH) can either be a spending
condition P directly, or a P2C derivation (using P + H(P,Q)G) of a spending
condition and an alternative. That alternative can either be another P2C
derivation ("recursive Taproot"), or a Merkle tree of disjunct spending
conditions.
This is elegant in that it removes the distinction between pay-to-pubkey and
pay-to-script constructions; every point becomes the representation of both.
As long as every script(branch) requires at least one pubkey check, it
comes at no cost (neither witness size or computational).
However, I think it also offers an easy way to construct a softfork-safe
cross-input aggregation system (discussed here before:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015838.html).
Essentially what's done here is extracting one key out of every spending
condition, given it a special place (the companion key) in the execution
structure - rather than being part of freeform script opcodes - and made it
cheaper to satisfy (as no pubkey needs to be revealed for it). This makes sense,
as we can assume that every (secure) script contains at least one CHECKSIG or
semantically equivalent operation, and with Schnorr multisignatures, can often
expect that to be just one key representing the set of all those who have to
sign.
However, it also means we could simply restrict a future cross-input signature
aggregation system to only apply to the set of these companion keys (one per
input). They are not subject to potential changes to the scripting language, as
they're outside of that. Under the assumption that most spending policies can be
encoded s a tractably-sized set of disjunct conditions, each with just a single
fixed set of public keys, the companion keys actually embody all public keys
involved in a transaction.
> (As far as deployment goes, I think it makes sense to get an initial
> schnorr/taproot/mast deployment out first, and add graftroot/aggregation
> later. My feeling is there's no great urgency for generalised taproot, so
> it would make sense to keep doing schnorr/taproot/mast for now, take time
> analysing generalised taproot, and if it seems sane and useful, aim to
> enable it in a later phase, eg at the same time as graftroot/aggregation)
Agree.
> [0] My inital name for these was "MAST-ended sc'roots", since it
> combines "taproot" and "scripts" and something MAST-like but only
> at the very end, but I was warned that the Mimblewimble folks have
> vast teams monitoring for Harry Potter references and will DMCA me,
> which I assume stands for "Dementors, Ministry, Cruciatus and Avada
> kedavra"... So I'm abbreviating generalised taproot as "g'root"
> instead. After all, what's the worst the Marvel guys could do?
Sebastian Geisler, Glenn Willen, and I had an hour long discussion to come up
with a name for the privileged key in g'root, but unfortunately had to resort
to the Valve universe instead to find "companion key"...
Cheers,
--
Pieter
|
