path: root/35/60a504d6327450aecde7c4509a39f4590c6cb0

Return-Path: <roconnor@blockstream.io>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 3AA30C7F
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 21 May 2019 17:20:47 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-io1-f42.google.com (mail-io1-f42.google.com
	[209.85.166.42])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id B1DAA87B
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 21 May 2019 17:20:45 +0000 (UTC)
Received: by mail-io1-f42.google.com with SMTP id u2so14585267ioc.4
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 21 May 2019 10:20:45 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=blockstream.io; s=google;
	h=mime-version:references:in-reply-to:from:date:message-id:subject:to; 
	bh=FHS1OGDsQ4fCHuTyaj8sziIlyVXS4OR6mlzHnj9g2jo=;
	b=s1f5eq1wB8RRF21pXYTT6Ny8DpFmEDTq8sX3AX5p4P5GDbtRpG54fq3693zHFSiAfK
	JXpR9L6Zwyu0X+QOjkugcyKrzs+lTZcvV5BqZP4+rD3kY2GUr1j8if2PgZ0GGd1Bk/Lf
	19o3Cu+DzZp8JWptmZw4ffVhuvO8PIQ3Ubu1E=
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=FHS1OGDsQ4fCHuTyaj8sziIlyVXS4OR6mlzHnj9g2jo=;
	b=sGCl52nUp+3U04z66tOhu1ET9ZjPD09dmbB5/dHPiRb36XPWTGDMzXw6y/MBx//kui
	1+RSDEdx9FNNoVC/VsT1IqvKTLTgSD6Q3AtcrUazr443mjN7magoUyYKVrGnJpObr8R1
	1hlBr8QaeAAsdm3UWDG01cP/DBUr+FgZRP+I9cemdgaEwLWa/WkADBSwXRUcpRRA1PaI
	NLHxEs9G7iyu4lkeBhyhsADZGfofOSmTi31h+Nuq+i/UKtRTR4pmqP3stpoDfty4AYqy
	v1bj2TGvQmse8VZKY0YMszF+khRho/rE9zk11caSdj5EUWMia8Qy78InLInCLSUPTzkF
	pkCg==
X-Gm-Message-State: APjAAAVAbCtcV+QoSZguJydmOod5tt2VkiOGSPVdIykT1De1sZNFHoo4
	43Hlj8HmcJ095WYHVb+6cIhejQn253ucLyxE9JPQDO/TvUI=
X-Google-Smtp-Source: APXvYqwdjiH/0F+E1YS0GzC8rAONBprD6YKxPbawXCQI1r6Wafiudb2eNjOiNQjJZfAmMNMahab8KIllgyK5gfSIzQI=
X-Received: by 2002:a5e:c817:: with SMTP id y23mr666762iol.290.1558459244576; 
	Tue, 21 May 2019 10:20:44 -0700 (PDT)
MIME-Version: 1.0
References: <CAPg+sBg6Gg8b7hPogC==fehY3ZTHHpQReqym2fb4XXWFpMM-pQ@mail.gmail.com>
In-Reply-To: <CAPg+sBg6Gg8b7hPogC==fehY3ZTHHpQReqym2fb4XXWFpMM-pQ@mail.gmail.com>
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Tue, 21 May 2019 13:20:32 -0400
Message-ID: <CAMZUoKkm33U+Rb+x03qUsFDG5CeX2C=nW8vD_8zbiAdsWazofQ@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>, 
	Pieter Wuille <pieter.wuille@gmail.com>,
	Andrew Poelstra <andrew.poelstra@blockstream.com>
Content-Type: multipart/alternative; boundary="000000000000abad1305896911e1"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, DKIM_VALID_AU, 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: Tue, 21 May 2019 18:36:00 +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 <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, 21 May 2019 17:20:47 -0000

--000000000000abad1305896911e1
Content-Type: text/plain; charset="UTF-8"

Regarding Tapscript, the specification calls for the final value of the
stack being a single non-false value:

The tapscript is executed according to the rules in the following section,
> with the initial stack as input
>     II. If the execution results in anything but exactly one element on
> the stack which evaluates to true with CastToBool(), fail.
>

Perhaps it is worth taking this opportunity here to remove a minor wart of
the Script language and instead require the stack to be exactly empty upon
completion.

In addition to removing a potential malleability vector, I expect it would
simplify development of Bitcoin Script.  A rule requiring an empty stack
means that the conjunction (logical and) of two policies can be implemented
by the simple concatenation of Bitcoin Scripts.  This combined with the
taproot ability to form the disjunction (logical or) of policies by having
multiple Merkle branches, means that the translation of a policy written in
disjunctive normal form (the logical ors of logical ands of primitive
policies) can be straightforwardly translated to a taproot of tapscript.

That said, I think the developers of miniscript <
http://bitcoin.sipa.be/miniscript/miniscript.html> are in a much better
position to comment on whether my above intuition is correct given that
they've had to implement a host of various calling conventions.  I
understand that at least some of this complexity is due to Bitcoin Script's
one element stack rule.

Scripts under the old one element rule can be translated to the new rule by
adding an OP_VERIFY operation to the end of the script; however it is
likely that this OP_VERIFY can be folded into the previous operation
yielding an OP_EQUALVERIFY or OP_CHECKSIGVERIFY in many cases.

Even if we choose not to implement the empty stack rule, we should at least
require that the last element be 0x01 to remove a potential malleability
vector and bring it in line with MINIMAL_IF semantics.

Thanks.

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
>

--000000000000abad1305896911e1
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div dir=3D"ltr"><div dir=3D"ltr"><div>Regarding Tapscript=
, the specification calls for the final value of the stack being a single n=
on-false value:</div><div><br></div><blockquote class=3D"gmail_quote" style=
=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding=
-left:1ex"><div>The tapscript is executed according to the rules in the fol=
lowing section, with the initial stack as input<br></div><div>=C2=A0=C2=A0=
=C2=A0 II. If the execution results in anything but exactly one element on =
the stack which evaluates to true with <code>CastToBool()</code>, fail.</di=
v></blockquote><div>=C2=A0</div><div>Perhaps it is worth taking this opport=
unity here to remove a minor wart of the Script language and instead requir=
e the stack to be exactly empty upon completion.</div><div><br></div><div>I=
n addition to removing a potential malleability vector, I expect it would s=
implify development of Bitcoin Script.=C2=A0 A rule requiring an empty stac=
k means that the conjunction (logical and) of two policies can be implement=
ed by the simple concatenation of Bitcoin Scripts.=C2=A0 This combined with=
 the taproot ability to form the disjunction (logical or) of policies by ha=
ving multiple Merkle branches, means that the translation of a policy writt=
en in disjunctive normal form (the logical ors of logical ands of primitive=
 policies) can be straightforwardly translated to a taproot of tapscript.</=
div><div><br></div><div>That said, I think the developers of miniscript &lt=
;<a href=3D"http://bitcoin.sipa.be/miniscript/miniscript.html">http://bitco=
in.sipa.be/miniscript/miniscript.html</a>&gt; are in a much better position=
 to comment on whether my above intuition is correct given that they&#39;ve=
 had to implement a host of various calling conventions.=C2=A0 I understand=
 that at least some of this complexity is due to Bitcoin Script&#39;s one e=
lement stack rule.<br></div><div><br></div><div>Scripts under the old one e=
lement rule can be translated to the new rule by adding an OP_VERIFY operat=
ion to the end of the script; however it is likely that this OP_VERIFY can =
be folded into the previous operation yielding an OP_EQUALVERIFY or OP_CHEC=
KSIGVERIFY in many cases.<br></div><div><br></div><div>Even if we choose no=
t to implement the empty stack rule, we should at least require that the la=
st element be 0x01 to remove a potential malleability vector and bring it i=
n line with MINIMAL_IF semantics.</div><div><br></div><div>Thanks.<br></div=
><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Mo=
n, May 6, 2019 at 2:36 PM Pieter Wuille via bitcoin-dev &lt;<a href=3D"mail=
to:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation=
.org</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"mar=
gin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1=
ex">Hello everyone,<br>
<br>
Here are two BIP drafts that specify a proposal for a Taproot<br>
softfork. A number of ideas are included:<br>
<br>
* Taproot to make all outputs and cooperative spends indistinguishable<br>
from eachother.<br>
* Merkle branches to hide the unexecuted branches in scripts.<br>
* Schnorr signatures enable wallet software to use key<br>
aggregation/thresholds within one input.<br>
* Improvements to the signature hashing algorithm (including signing<br>
all input amounts).<br>
* Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support<br>
batch validation.<br>
* Tagged hashing for domain separation (avoiding issues like<br>
CVE-2012-2459 in Merkle trees).<br>
* Extensibility through leaf versions, OP_SUCCESS opcodes, and<br>
upgradable pubkey types.<br>
<br>
The BIP drafts can be found here:<br>
* <a href=3D"https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.medi=
awiki" rel=3D"noreferrer" target=3D"_blank">https://github.com/sipa/bips/bl=
ob/bip-schnorr/bip-taproot.mediawiki</a><br>
specifies the transaction input spending rules.<br>
* <a href=3D"https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.me=
diawiki" rel=3D"noreferrer" target=3D"_blank">https://github.com/sipa/bips/=
blob/bip-schnorr/bip-tapscript.mediawiki</a><br>
specifies the changes to Script inside such spends.<br>
* <a href=3D"https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.medi=
awiki" rel=3D"noreferrer" target=3D"_blank">https://github.com/sipa/bips/bl=
ob/bip-schnorr/bip-schnorr.mediawiki</a><br>
is the Schnorr signature proposal that was discussed earlier on this<br>
list (See <a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-de=
v/2018-July/016203.html" rel=3D"noreferrer" target=3D"_blank">https://lists=
.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html</a>)<br>
<br>
An initial reference implementation of the consensus changes, plus<br>
preliminary construction/signing tests in the Python framework can be<br>
found on <a href=3D"https://github.com/sipa/bitcoin/commits/taproot" rel=3D=
"noreferrer" target=3D"_blank">https://github.com/sipa/bitcoin/commits/tapr=
oot</a>. All<br>
together, excluding the Schnorr signature module in libsecp256k1, the<br>
consensus changes are around 520 LoC.<br>
<br>
While many other ideas exist, not everything is incorporated. This<br>
includes several ideas that can be implemented separately without loss<br>
of effectiveness. One such idea is a way to integrate SIGHASH_NOINPUT,<br>
which we&#39;re working on as an independent proposal.<br>
<br>
The document explains basic wallet operations, such as constructing<br>
outputs and signing. However, a wide variety of more complex<br>
constructions exist. Standardizing these is useful, but out of scope<br>
for now. It is likely also desirable to define extensions to PSBT<br>
(BIP174) for interacting with Taproot. That too is not included here.<br>
<br>
Cheers,<br>
<br>
-- <br>
Pieter<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div></div></div></div>

--000000000000abad1305896911e1--