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
|
Return-Path: <apoelstra@wpsoftware.net>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 7C813BBC
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 23 May 2018 17:52:42 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from mail.wpsoftware.net (wpsoftware.net [96.53.77.134])
by smtp1.linuxfoundation.org (Postfix) with ESMTP id 4DE096DA
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 23 May 2018 17:52:41 +0000 (UTC)
Received: from boulet.lan (boulot.lan [192.168.0.193])
by mail.wpsoftware.net (Postfix) with ESMTPSA id 15EAD401E1;
Wed, 23 May 2018 17:52:39 +0000 (UTC)
Date: Wed, 23 May 2018 17:52:39 +0000
From: Andrew Poelstra <apoelstra@wpsoftware.net>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20180523175239.GR14992@boulet.lan>
References: <CAPg+sBgKY-nmL=x+LVubtB0fFBAwd-1CDHT7zhidX8p9DLSGyg@mail.gmail.com>
<20180523135013.GN14992@boulet.lan>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="dO6Thh8T/cwyDjv9"
Content-Disposition: inline
In-Reply-To: <20180523135013.GN14992@boulet.lan>
User-Agent: Mutt/1.7.1 (2016-10-04)
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: Re: [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: Wed, 23 May 2018 17:52:42 -0000
--dO6Thh8T/cwyDjv9
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
On Wed, May 23, 2018 at 01:50:13PM +0000, Andrew Poelstra via bitcoin-dev w=
rote:
>=20
> Graftroot also break blind signature schemes. Consider a protocol such as=
[1]
> where some party has a bunch of UTXOs all controlled (in part) by the same
> key X. This party produces blind signatures on receipt of new funds, and =
can
> only verify the number of signatures he produces, not anything about what=
he
> is signing.
>=20
> BTW, the same concern holds for SIGHASH_NOINPUT, which I'd also like to be
> disable-able. Maybe we should extend one of ZmnSCPxj's suggestions to inc=
lude
> a free "flags" byte or two in the witness?
>=20
> (I also had the same concern about signature aggregation. It seems like i=
t's
> pretty hard to preserve the "one signature =3D at most one input" invaria=
nt of
> Bitcoin, but I think it's important that it is preserved, at least for
> outputs that need it.)
>=20
> Or maybe, since it appears it will require a space hit to support optional
> graftroot anyway, we should simply not include it in a proposal for Tapro=
ot,
> since there would be no opportunity cost (in blockchain efficiency) to do=
ing
> it later.
>=20
> [1] https://github.com/apoelstra/scriptless-scripts/pull/1=20
>
On further thought, I rescind this concern (ditto for SIGHASH_NOINPUT) (but
not for aggregate sigs, they still interact badly with blind signatures).
As long as graftroot (and NOINPUT) sigs commit to the public key, it is
possible for a server to have unique keys for every output, even while
retaining the same private key, and thereby ensure that "one sig can spend
only one output" holds. To do this, suppose the server has a BIP32 xpubkey
(xG, cc). A blind signer using the private key x can be made to sign not
only for xG, but also for any publicly-derived child keys of (xG, cc).
Here is a simple scheme that does this:
1. Signer provides a nonce R =3D kG
2. Challenger computes bip32 tweak h, chooses blinders alpha and beta,
and computes:
R' =3D R + alpha*G + beta*P
e =3D H(P + hG || R' || tx)
e' =3D e + beta
and sends e' to the signer.
3. Signer replies with s =3D k + xe' (=3D k + beta*x + (x + h)e - he)
4. Challenger unblinds this as s' =3D s + alpha + he
(This blind signature scheme is vulnerable to Wagner's attack, though see
Schnorr 2004 [1] for mitigations that are perfectly compatible with this
modified BIP32ish scheme.)
I'm unsure whether key-prefixing is _actually_ necessary for this, but it
makes the security argument much clearer since the messagehash contains
some data which can be made unique per-utxo and is committed in the chain.
Andrew
[1] http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=3D8ECEF9295598=
65FD68D1D873555D18FE?doi=3D10.1.1.68.9836&rep=3Drep1&type=3Dpdf
--=20
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web: https://www.wpsoftware.net/andrew
"A goose alone, I suppose, can know the loneliness of geese
who can never find their peace,
whether north or south or west or east"
--Joanna Newsom
--dO6Thh8T/cwyDjv9
Content-Type: application/pgp-signature; name="signature.asc"
-----BEGIN PGP SIGNATURE-----
iQEcBAEBCAAGBQJbBaplAAoJEMWI1jzkG5fBxiAH/Rk1QWYz+62bIZVpcbX4VmRs
K9w83i5XsOYUnaPnVeBdC+rZNZOGIAFtS61KHfbKCaKa20CMdVjtLcdbbZWMXLNo
VAdIT8F76R9jSUYqg6OMcUaJK9RszqVmDDo2T1jMl+aUiu52dEs1nGg/YL8DuQ+S
QPNZsdSrweXJxX/wq/QhQumWfRIIOo8tLieMOVdBaxRg62md7LFLF5WLlTbvjtYy
uVcFMFogTnlNpbHizMColvZ+nXm6yFq238P9VJCjD/YNVe3zqGeeI6wrS+7REJl0
4jHgd6H9ByJby8bDkAh8Pe0k9Lc3LSkmhR29Sd7pbwpi31gHtkSY7iJrTMzGQHM=
=5u1y
-----END PGP SIGNATURE-----
--dO6Thh8T/cwyDjv9--
|
