From: Johnson Lau <jl2012@xbt.hk>
Content-Type: text/plain;
	charset=utf-8
Content-Transfer-Encoding: quoted-printable
Mime-Version: 1.0 (Mac OS X Mail 11.2 \(3445.5.20\))
Date: Fri, 25 May 2018 17:46:29 +0800
References: <CAPg+sBgKY-nmL=x+LVubtB0fFBAwd-1CDHT7zhidX8p9DLSGyg@mail.gmail.com>
	<20180523135013.GN14992@boulet.lan> <20180523175239.GR14992@boulet.lan>
To: Andrew Poelstra <apoelstra@wpsoftware.net>,
	bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
In-Reply-To: <20180523175239.GR14992@boulet.lan>
Message-Id: <AE21F8B7-2763-40CA-8A61-F862A80E18BB@xbt.hk>
Subject: Re: [bitcoin-dev] Should Graftroot be optional?
Precedence: list

While you have rescind your concern, I=E2=80=99d like to point out that =
it=E2=80=99s strictly a problem of SIGHASH_NOINPUT, not graftroot (or =
script delegation in general).

For example, we could modify graftroot. Instead of signing the (script), =
we require it to sign (outpoint | script). That means a graftroot =
signature would never be valid for more than one UTXO.

> On 24 May 2018, at 1:52 AM, Andrew Poelstra via bitcoin-dev =
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>=20
> On Wed, May 23, 2018 at 01:50:13PM +0000, Andrew Poelstra via =
bitcoin-dev wrote:
>>=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 =
include
>> a free "flags" byte or two in the witness?
>>=20
>> (I also had the same concern about signature aggregation. It seems =
like it's
>> pretty hard to preserve the "one signature =3D at most one input" =
invariant 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 =
Taproot,
>> since there would be no opportunity cost (in blockchain efficiency) =
to doing
>> it later.
>>=20
>> [1] https://github.com/apoelstra/scriptless-scripts/pull/1=20
>>=20
>=20
> On further thought, I rescind this concern (ditto for SIGHASH_NOINPUT) =
(but
> not for aggregate sigs, they still interact badly with blind =
signatures).
>=20
> 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).
>=20
> Here is a simple scheme that does this:
>=20
>  1. Signer provides a nonce R =3D kG
>=20
>  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.
>=20
>  3. Signer replies with s =3D k + xe' (=3D k + beta*x + (x + h)e - he)
>=20
>  4. Challenger unblinds this as s' =3D s + alpha + he
>=20
> (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.)
>=20
> 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.
>=20
>=20
> Andrew
>=20
>=20
> [1] =
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=3D8ECEF929559865F=
D68D1D873555D18FE?doi=3D10.1.1.68.9836&rep=3Drep1&type=3Dpdf
>=20
>=20
> --=20
> Andrew Poelstra
> Mathematics Department, Blockstream
> Email: apoelstra at wpsoftware.net
> Web:   https://www.wpsoftware.net/andrew
>=20
> "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
>=20
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev