Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 63E42A59 for ; Wed, 22 May 2019 14:14:59 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ot1-f65.google.com (mail-ot1-f65.google.com [209.85.210.65]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 599E9879 for ; Wed, 22 May 2019 14:14:58 +0000 (UTC) Received: by mail-ot1-f65.google.com with SMTP id j49so2153158otc.13 for ; Wed, 22 May 2019 07:14:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=johnnewbery-com.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=tsV/DUGyqMPwwR5Fafm6bSTcV0xA9CAWgPT3vJFIrt0=; b=xwxdyeDjOA8oi2w/5HzORoY8433GMN633KxBYG/yEaP/XhTnZ4lDRbMCmJMx+0DvV6 rN8qhn+1syOvSlKaR1LjJvmbQp1rjKSW7+hqx08Gh5TGeq9KK6WjDpnLpXdl9GWO1j08 22I4/sF8X692gYh0YbryVfu18pYWnU4iiOG7iKEIZCcaIIxryEUekYx+ckThQLNyaNUN wAd0dGj7+O/eR0GA1KDMlkB1pv95hzZJs85TTxT+REdbooc5thKxTK2wQMO2DVBBgGF0 u3yll2w50HY20n/JdptBS2wcOdegvWahQ9XSZ7AA2/epKaYWf1HUAP8gyM3pbHQHENoU HMcw== 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=tsV/DUGyqMPwwR5Fafm6bSTcV0xA9CAWgPT3vJFIrt0=; b=UccQ/o9ibTnel8l+wZUmRufXOOg1eMY3xE9+h2qYwNZb54p5EJ+pr9IBxCWVILaPK7 OAXGeCmjwFKCQnTWcEtu6eL2uNe6+T1tXxRUiai84vaXWgCOKqSgmXJdlowqZqTJ8/0j SAbI535GA5PEhNos1zM4YdXaCqfl7pNiLQcOtamJ8j4aLbVyplPeR3wztvKouUhE90EP U2pm95Kto2/GayxELobjPCtokdYI901KEvRJU89fZ5ZJ+ucWP6IIcLZ6aLzDwDYRZZQZ xmAebESnVLiAtrDqKX48uYtIpYIl+9BjjfRIkVaOUTOd63ViqBo+glPpQVFZtKIGrOew nFWw== X-Gm-Message-State: APjAAAX2VRn8TN1KZ6gC7GENWta9wU2AT/9RsInPHL9ShWzGK1uMlXBw 2MeJLiXoZs150VKAZeCPNBOdh/a+Vsc= X-Google-Smtp-Source: APXvYqyaa96IFCb50qw2hyizhMoOzpWJl/+yY461/01c0HLhpREJPw/EBgsM/HWuzPyjDY89GiGxXA== X-Received: by 2002:a9d:6153:: with SMTP id c19mr17311997otk.292.1558534497199; Wed, 22 May 2019 07:14:57 -0700 (PDT) Received: from mail-ot1-f41.google.com (mail-ot1-f41.google.com. [209.85.210.41]) by smtp.gmail.com with ESMTPSA id j18sm1868986oih.45.2019.05.22.07.14.56 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 22 May 2019 07:14:56 -0700 (PDT) Received: by mail-ot1-f41.google.com with SMTP id s19so2197852otq.5 for ; Wed, 22 May 2019 07:14:56 -0700 (PDT) X-Received: by 2002:a9d:629a:: with SMTP id x26mr31291333otk.7.1558534495678; Wed, 22 May 2019 07:14:55 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: John Newbery Date: Wed, 22 May 2019 10:14:44 -0400 X-Gmail-Original-Message-ID: Message-ID: To: Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="000000000000fc387405897a967b" X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, HTML_MESSAGE, 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, 22 May 2019 14:30:15 +0000 Subject: Re: [bitcoin-dev] Taproot proposal X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 22 May 2019 14:14:59 -0000 --000000000000fc387405897a967b Content-Type: text/plain; charset="UTF-8" Hi, > A Taproot output is a SegWit output [...] with > version number 1, and a 33-byte witness program whose first byte is 0 or 1. Given a secret key k and public key P=(x,y), a signer with the knowledge of k can sign for -P=(x,p-y) since -k is the secret key for that point. Encoding the y value of the public key therefore adds no security. As an alternative to providing the y value of the taproot output key Q when constructing the taproot output, the signer can provide it when signing. We can also restrict the y value of the internal key P to be even (or high, or a quadratic residue). That gives us 4 options for how to set the y signs for P and Q. 1. Q sign is explictly set in the witness program, P sign is explicitly set in the control block => witness program is 33 bytes, 32 possible leaf versions (one for each pair of 0xc0..0xff) 2. Q sign is explictly set in the witness program, P sign is implicitly even => witness program is 33 bytes, 64 possible leaf versions (one for each 0xc0..0xff) 3. Q sign is explictly set in the control block, P sign is explicitly set in the control block => witness program is 32 bytes, 16 possible leaf versions (one for each 4-tuple of 0xc0..0xff) 4. Q sign is explictly set in the control block, P sign is implicitly even => witness program is 32 bytes, 32 possible leaf versions (one for pair of 0xc0..0xff) The current proposal uses (1). Using (3) or (4) would reduce the size of a taproot output by one byte to be the same size as a P2WSH output. That means that it's not more expensive for senders compared to sending to P2WSH. (Credit to James Chiang for suggesting omitting the y sign from the public key and to sipa for pointing out the 4 options above) > (native or P2SH-nested, see BIP141) I'd prefer to not support P2SH-nested TR. P2SH wrapping was useful for segwit v0 for compatibility reasons. Most wallets/exchanges/services now support sending to native segwit addresses (https://en.bitcoin.it/wiki/Bech32_adoption) and that will be even more true if Schnorr/Taproot activate in 12+ months time. On Mon, May 6, 2019 at 2:36 PM Pieter Wuille via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > Hello everyone, > > Here are two BIP drafts that specify a proposal for a Taproot > softfork. A number of ideas are included: > > * Taproot to make all outputs and cooperative spends indistinguishable > from eachother. > * Merkle branches to hide the unexecuted branches in scripts. > * Schnorr signatures enable wallet software to use key > aggregation/thresholds within one input. > * Improvements to the signature hashing algorithm (including signing > all input amounts). > * Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support > batch validation. > * Tagged hashing for domain separation (avoiding issues like > CVE-2012-2459 in Merkle trees). > * Extensibility through leaf versions, OP_SUCCESS opcodes, and > upgradable pubkey types. > > The BIP drafts can be found here: > * https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki > specifies the transaction input spending rules. > * https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki > specifies the changes to Script inside such spends. > * https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki > is the Schnorr signature proposal that was discussed earlier on this > list (See > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html > ) > > An initial reference implementation of the consensus changes, plus > preliminary construction/signing tests in the Python framework can be > found on https://github.com/sipa/bitcoin/commits/taproot. All > together, excluding the Schnorr signature module in libsecp256k1, the > consensus changes are around 520 LoC. > > While many other ideas exist, not everything is incorporated. This > includes several ideas that can be implemented separately without loss > of effectiveness. One such idea is a way to integrate SIGHASH_NOINPUT, > which we're working on as an independent proposal. > > The document explains basic wallet operations, such as constructing > outputs and signing. However, a wide variety of more complex > constructions exist. Standardizing these is useful, but out of scope > for now. It is likely also desirable to define extensions to PSBT > (BIP174) for interacting with Taproot. That too is not included here. > > Cheers, > > -- > Pieter > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > --000000000000fc387405897a967b Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi,

> A Taproot output is a Seg= Wit output [...] =C2=A0with
> version number 1, and a 33-byte witness= program whose first byte is 0 or 1.

Given a secret key k and public= key P=3D(x,y), a signer with the knowledge of k
can sign for -P=3D(x,p-= y) since -k is the secret key for that point. Encoding the
y value of th= e public key therefore adds no security. As an alternative to
providing = the y value of the taproot output key Q when constructing the taproot
ou= tput, the signer can provide it when signing. We can also restrict the y va= lue
of the internal key P to be even (or high, or a quadratic residue). = That gives
us 4 options for how to set the y signs for P and Q.

1= . Q sign is explictly set in the witness program, P sign is explicitly set = in the control block
=C2=A0 =C2=A0 =3D> witness program is 33 bytes, = 32 possible leaf versions (one for each pair of 0xc0..0xff)
2. Q sign is= explictly set in the witness program, P sign is implicitly even
=C2=A0 = =C2=A0 =3D> witness program is 33 bytes, 64 possible leaf versions (one = for each 0xc0..0xff)
3. Q sign is explictly set in the control block, P = sign is explicitly set in the control block
=C2=A0 =C2=A0 =3D> witnes= s program is 32 bytes, 16 possible leaf versions (one for each 4-tuple of 0= xc0..0xff)
4. Q sign is explictly set in the control block, P sign is im= plicitly even
=C2=A0 =C2=A0 =3D> witness program is 32 bytes, 32 poss= ible leaf versions (one for pair of 0xc0..0xff)

The current proposal= uses (1). Using (3) or (4) would reduce the size of a
taproot output by= one byte to be the same size as a P2WSH output. That means
that it'= s not more expensive for senders compared to sending to P2WSH.
=C2=A0(Credit to James Chiang for suggesting omitting the y sign from the public= key and
to sipa for pointing out the 4 options above)

> (nati= ve or P2SH-nested, see BIP141)

I'd prefer to not support P2SH-ne= sted TR. P2SH wrapping was useful for segwit
v0 for compatibility reason= s. Most wallets/exchanges/services now support sending
to native segwit = addresses (https://en.bitcoin.it/wiki/Bech32_adoption) and that
will b= e even more true if Schnorr/Taproot activate in 12+ months time.
<= br>
On Mon,= May 6, 2019 at 2:36 PM Pieter Wuille via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.o= rg> wrote:
https://github.com/sipa/bips/bl= ob/bip-schnorr/bip-taproot.mediawiki
specifies the transaction input spending rules.
* https://github.com/sipa/bips/= blob/bip-schnorr/bip-tapscript.mediawiki
specifies the changes to Script inside such spends.
* https://github.com/sipa/bips/bl= ob/bip-schnorr/bip-schnorr.mediawiki
is the Schnorr signature proposal that was discussed earlier on this
list (See https://lists= .linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html)

An initial reference implementation of the consensus changes, plus
preliminary construction/signing tests in the Python framework can be
found on https://github.com/sipa/bitcoin/commits/tapr= oot. All
together, excluding the Schnorr signature module in libsecp256k1, the
consensus changes are around 520 LoC.

While many other ideas exist, not everything is incorporated. This
includes several ideas that can be implemented separately without loss
of effectiveness. One such idea is a way to integrate SIGHASH_NOINPUT,
which we're working on as an independent proposal.

The document explains basic wallet operations, such as constructing
outputs and signing. However, a wide variety of more complex
constructions exist. Standardizing these is useful, but out of scope
for now. It is likely also desirable to define extensions to PSBT
(BIP174) for interacting with Taproot. That too is not included here.

Cheers,

--
Pieter
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--000000000000fc387405897a967b--