path: root/c5/6feb615b29202a70d154875106648128850a6a

Return-Path: <mark@friedenbach.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 8D95CF80
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 23 Jan 2018 14:39:44 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-pf0-f182.google.com (mail-pf0-f182.google.com
	[209.85.192.182])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 9B5812F6
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 23 Jan 2018 14:39:40 +0000 (UTC)
Received: by mail-pf0-f182.google.com with SMTP id e11so468247pff.6
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 23 Jan 2018 06:39:40 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=friedenbach-org.20150623.gappssmtp.com; s=20150623;
	h=from:mime-version:subject:date:references:to:in-reply-to:message-id; 
	bh=S1IP9jfb447cVzCiRLcdLOHpy3sPOSejvn6cfHauBKg=;
	b=DE2vGw33GXVEXqtlC9wHyRZQ1l6ywPu+FLWsD+mDYq3B55ZhAG2xSiWjnXfo41Nxyn
	nC+MnVxps8kUT1iaMyju1wIeuyyzXop3atbDbc0zgUi8OBYzq6kr22YkrmlkeWRB3w8y
	GBkJcM4mwxolbvydBGh73qyD3im72VYYnWnRr0t9QZe39PghIgZ/F/lNtDVXitJtkZGh
	q7tmFDTlt+rD67MVpz5Gygo62Rs9Ap3iXRacRy9WjJxv1RsEEf+QERBUg53DF+kHwT+E
	Jo3rfkmV56SpC+9HJA1FpgFb0+0ylyuW1DOwZqPuSwU9y2vkHmYbneOJqW46+bzT5fRo
	EpEw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20161025;
	h=x-gm-message-state:from:mime-version:subject:date:references:to
	:in-reply-to:message-id;
	bh=S1IP9jfb447cVzCiRLcdLOHpy3sPOSejvn6cfHauBKg=;
	b=m5bG81IwPkKfXkt1YvGTYrpA/QLYb2RGfrFbkGpj/iILBEr0KloHoq93IiYff4PN1g
	Ez7p3FnXJaxzbYFrYaJc1iH1vs81Eizbo6ATjWqdA3W6G7HBPwDyfpXeYWiAtHKdbZ9R
	eFvkl+8leoUF2k66D7W+t34gYJKDSgC0EAhossr3LpXz7Jn+fheBxnk1YYfJfOKjqbhI
	CN+MGf+YJ4PFbyVCgHOu3vtY30LnphlzQfIODK7jNx+Mrl2isnMlFrGke29ZE/ZJNJLn
	yFS5rPAo1HnM2CvFqoV4aPzO7C3ytIqGCU+Ngl6JxKGNmtENJ6aj3zf4ZiS4iljqkV6l
	ZwKw==
X-Gm-Message-State: AKwxytc5ZuHdFDf38XRGDIWJHh2YcjqYkzA6mFbHL0t2s3+ZRXvOP6Zt
	TJoZGrvLmPCoUNS5TBB6C0JibwzbGyE=
X-Google-Smtp-Source: AH8x227sOy3vVlh2xH0mWEstEd2Ysl04Rzx03Rg9hGEtAhTMsTWzg7JxD/U5mngLPLxyzoPRC0h1ag==
X-Received: by 10.98.233.10 with SMTP id j10mr9935630pfh.123.1516718380000;
	Tue, 23 Jan 2018 06:39:40 -0800 (PST)
Received: from ?IPv6:2601:646:8080:4dbb:5123:57fd:2a38:53f1?
	([2601:646:8080:4dbb:5123:57fd:2a38:53f1])
	by smtp.gmail.com with ESMTPSA id y1sm7607255pge.78.2018.01.23.06.39.38
	(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
	Tue, 23 Jan 2018 06:39:39 -0800 (PST)
From: Mark Friedenbach <mark@friedenbach.org>
Content-Type: multipart/alternative;
	boundary="Apple-Mail=_AE03DB4F-2910-4A79-B166-B0F5F2D01688"
Mime-Version: 1.0 (Mac OS X Mail 11.2 \(3445.5.20\))
Date: Tue, 23 Jan 2018 06:39:37 -0800
References: <CAAS2fgTXg5kk6TyUM9dS=tf5N0_Z-GKVmzMLwTW1HxUgrqdo+Q@mail.gmail.com>
	<61C1114D-A4E3-4628-AB7E-17C09EDDC2DE@mattcorallo.com>
To: Matt Corallo <lf-lists@mattcorallo.com>,
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
In-Reply-To: <61C1114D-A4E3-4628-AB7E-17C09EDDC2DE@mattcorallo.com>
Message-Id: <285E52DF-04E8-4E03-85A0-764F54B3EED9@friedenbach.org>
X-Mailer: Apple Mail (2.3445.5.20)
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
Subject: Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting
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, 23 Jan 2018 14:39:44 -0000


--Apple-Mail=_AE03DB4F-2910-4A79-B166-B0F5F2D01688
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=utf-8

I had the opposite response in private, which I will share here. As =
recently as Jan 9th feedback on BIP 117 was shared on this list by =
Pieter Wuille and others suggesting we adopt native MAST template =
instead of the user programmable combination of BIPs 116 and 117. Part =
of my response then was, I quote:

I havent the hubris to suggest that we know exactly what a templated =
MAST *should* look like. It's not used in production anywhere. Even if =
we did have the foresight, the tail-call semantics allow for other =
constructions besides MAST and for the sake of the future we should =
allow such permission-less innovation. The proper sequence of events =
should be to enable features in a generic way, and then to create =
specialized templates to save space for common constructions. Not the =
other way around. [1]

I take this advance as further evidence in favor of this view. As =
recently as 24 hours ago if you had asked what a native-MAST template =
would have looked like, the answer would have been something like =
Johnson Lau=E2=80=99s BIP 114, with some quibbling over details. Taproot =
is a clearly superior approach. But is it optimal? I don=E2=80=99t think =
we can claim that now. Optimality of these constructs isn=E2=80=99t =
something easily proven, with the nearest substitute being unchanging =
consensus over extended periods of time.

Every time we add an output type specialization, we introduce a new =
codepath in the core of the script consensus that must be maintained =
forever. Take P2SH: from this point forward there is no reason to use it =
in new applications, ever. But it must be forever supported. In an =
alternate universe we could have deployed a native MAST proposal, like =
BIP 114, only to have Taproot-like schemes discovered after activation. =
That would have been a sucky outcome. It is still the case that we could =
go for Taproot right now, and then in six months or a year=E2=80=99s =
time we find an important tweak or a different approach entirely that is =
even better, but the activation process had already started. That would =
be a sucky outcome we haven=E2=80=99t avoided yet.

This is not an argument against template specialization for common code =
paths, especially those which increase fungibility of coins. I do think =
we should have a native MAST template eventually, using Taproot or =
something better. However if I may be allowed I will make an educated =
guess about the origin of Taproot: I think it=E2=80=99s no coincidence =
that Greg had this insight and/or wrote it up simultaneous with a push =
by myself and others for getting MAST features into bitcoin via BIPs 98, =
116, and 117, or 114. Cryptographers tend to only think up solutions to =
problems that are on their minds. And the problems on most people=E2=80=99=
s minds are primarily those that are deployable today, or otherwise =
near-term applicable.

BIPS 116 and 117 each provide a reusable component that together happens =
to enable a generic form of MAST. Even without the workarounds required =
to avoid CLEANSTACK violations, the resulting MAST template is larger =
than what is possible with specialization. However let=E2=80=99s not =
forget that (1) they also enable other applications like honeypots, key =
trees, and script delegation; and relevant to this conversation (2) they =
get the MAST feature available for use in production by the wider =
community. I don=E2=80=99t think I=E2=80=99d personally be willing to =
bet that we found the optimal MAST structure in Greg=E2=80=99s Taproot =
until we have people doing interesting production work like multisig =
wallets, lightning protocol, and the next set of consensus features =
start putting it into production and exploring edge cases. We may find =
ways Taproot can be tweaked to enable other applications (like encoding =
a hash preimage as well) or simplify obscure corner cases.

I feel quite strongly that the correct approach is to add support for =
generic features to accomplish the underlying goal in a user =
programmable way, and THEN after activation and some usage consider ways =
in which common use cases can be made more efficient through output =
specialization. To take a more obvious example, lightning protocol is =
still an active area or research and I think it is abundantly clear that =
we don=E2=80=99t know yet what the globally optimal layer-2 caching =
protocol will be, even if we have educated guesses as to its broad =
structure. A proposal right now to standardize a more compact lightning =
script type would be rightly rejected. It is less obvious but just as =
true that the same should hold for MAST.

I have argued these points before in favor of permission less innovation =
first, then application specialization later, in [1] and at the end of =
the rather long email [2]. I hope you can take the time to read those if =
you still feel we should take a specialized template approach instead of =
the user programmable BIPSs 116 and 117.

[1] =
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/01553=
7.html =
<https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/0155=
37.html>
[2] =
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/015=
029.html =
<https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/01=
5029.html>

> On Jan 22, 2018, at 6:51 PM, Matt Corallo via bitcoin-dev =
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>=20
> Thanks Greg!
>=20
> I'd be hesitant to deploy a MAST proposal without this clever =
application of pay-to-contract-hash now! Looks like the overhead over a =
more-naive MAST construction is rather trivial, too!
>=20
> Matt
>=20
> On January 23, 2018 12:30:06 AM UTC, Gregory Maxwell via bitcoin-dev =
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> Interest in merkelized scriptPubKeys (e.g. MAST) is driven by two main
> areas: efficiency and privacy. Efficiency because unexecuted forks of
> a script can avoid ever hitting the chain, and privacy because hiding
> unexecuted code leaves scripts indistinguishable to the extent that
> their only differences are in the unexecuted parts.
>=20
> As Mark Friedenbach and others have pointed out before it is almost
> always the case that interesting scripts have a logical top level
> branch which allows satisfaction of the contract with nothing other
> than a signature by all parties.  Other branches would only be used
> where some participant is failing to cooperate. More strongly stated,
> I believe that _any_ contract with a fixed finite participant set
> upfront can be and should be represented as an OR between an N-of-N
> and whatever more complex contract you might want to represent.
>=20
> One point that comes up while talking about merkelized scripts is can
> we go about making fancier contract use cases as indistinguishable as
> possible from the most common and boring payments. Otherwise, if the
> anonymity set of fancy usage is only other fancy usage it may not be
> very large in practice. One suggestion has been that ordinary
> checksig-only scripts should include a dummy branch for the rest of
> the tree (e.g. a random value hash), making it look like there are
> potentially alternative rules when there aren't really.  The negative
> side of this is an additional 32-byte overhead for the overwhelmingly
> common case which doesn't need it.  I think the privacy gains are
> worth doing such a thing, but different people reason differently
> about these trade-offs.
>=20
> It turns out, however, that there is no need to make a trade-off.  The
> special case of a top level "threshold-signature OR
> arbitrary-conditions" can be made indistinguishable from a normal
> one-party signature, with no overhead at all, with a special
> delegating CHECKSIG which I call Taproot.
>=20
> Let's say we want to create a coin that can be redeemed by either
> Alice && Bob   or by CSV-timelock && Bob.
>=20
> Alice has public A, Bob has pubkey B.
>=20
> We compute the 2-of-2 aggregate key C =3D A + B.  (Simplified; to
> protect against rogue key attacks you may want to use the MuSig key
> aggregation function [1])
>=20
> We form our timelock script S =3D  "<timeout> OP_CSV OP_DROP B =
OP_CHECKSIGVERIFY"
>=20
> Now we tweak C to produce P which is the key we'll publish: P =3D C + =
H(C||S)G.
>=20
> (This is the attack hardened pay-to-contract construction described in =
[2])
>=20
> Then we pay to a scriptPubKey of [Taproot supporting version] [EC =
point P].
>=20
> Now Alice and Bob-- assuming they are both online and agree about the
> resolution of their contract-- can jointly form a 2 of 2 signature for
> P, and spend as if it were a payment to a single party (one of them
> just needs to add H(C||S) to their private key).
>=20
> Alternatively, the Taproot consensus rules would allow this script to
> be satisfied by someone who provides the network with C (the original
> combined pubkey), S, and does whatever S requires-- e.g. passes the
> CSV check and provides Bob's signature. With this information the
> network can verify that C + H(C||S) =3D=3D P.
>=20
> So in the all-sign case there is zero overhead; and no one can tell
> that the contract alternative exists. In the alternative redemption
> branch the only overhead is revealing the original combined pubkey
> and, of course, the existence of the contract is made public.
>=20
> This composes just fine with whatever other merkelized script system
> we might care to use, as the S can be whatever kind of data we want,
> including the root of some tree.
>=20
> My example shows 2-of-2 but it works the same for any number of
> participants (and with setup interaction any threshold of
> participants, so long as you don't mind an inability to tell which
> members signed off).
>=20
> The verification computational complexity of signature path is
> obviously the same as any other plain signature (since its
> indistinguishable). Verification of the branch redemption requires a
> hash and a multiplication with a constant point which is strictly more
> efficient than a signature verification and could be efficiently fused
> into batch signature validation.
>=20
> The nearest competitor to this idea that I can come up with would
> supporting a simple delegation where the output can be spent by the
> named key, or a spending transaction could provide a script along with
> a signature of that script by the named key, delegating control to the
> signed script. Before paying into that escrow Alice/Bob would
> construct this signature. This idea is equally efficient in the common
> case, but larger and slower to verify in the alternative spend case.
> Setting up the signature requires additional interaction between
> participants and the resulting signature must be durably stored and
> couldn't just be recomputed using single-party information.
>=20
> I believe this construction will allow the largest possible anonymity
> set for fixed party smart contracts by making them look like the
> simplest possible payments. It accomplishes this without any overhead
> in the common case, invoking any sketchy or impractical techniques,
> requiring extra rounds of interaction between contract participants,
> and without requiring the durable storage of other data.
>=20
>=20
> [1] https://eprint.iacr.org/2018/068 =
<https://eprint.iacr.org/2018/068>
> [2] https://blockstream.com/sidechains.pdf =
<https://blockstream.com/sidechains.pdf> Appendix A
>=20
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev =
<https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


--Apple-Mail=_AE03DB4F-2910-4A79-B166-B0F5F2D01688
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
	charset=utf-8

<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html; =
charset=3Dutf-8"></head><body style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; line-break: after-white-space;" class=3D"">I =
had the opposite response in private, which I will share here. As =
recently as Jan 9th feedback on BIP 117 was shared on this list by =
Pieter Wuille and others suggesting we adopt native MAST template =
instead of the user programmable combination of BIPs 116 and 117. Part =
of my response then was, I quote:<div class=3D""><br =
class=3D""></div><blockquote style=3D"margin: 0 0 0 40px; border: none; =
padding: 0px;" class=3D""><div class=3D"">I havent the hubris to suggest =
that we know exactly what a templated MAST *should* look like. It's not =
used in production anywhere. Even if we did have the foresight, the =
tail-call semantics allow for other constructions besides MAST and for =
the sake of the future we should allow such permission-less innovation. =
The proper sequence of events should be to enable features in a generic =
way, and then to create specialized templates to save space for common =
constructions. Not the other way around. [1]</div></blockquote><div =
class=3D""><div><br class=3D""></div><div>I take this advance as further =
evidence in favor of this view. As recently as 24 hours ago if you had =
asked what a native-MAST template would have looked like, the answer =
would have been something like Johnson Lau=E2=80=99s BIP 114, with some =
quibbling over details. Taproot is a clearly superior approach. But is =
it optimal? I don=E2=80=99t think we can claim that now. Optimality of =
these constructs isn=E2=80=99t something easily proven, with the nearest =
substitute being unchanging consensus over extended periods of =
time.</div><div><br class=3D""></div><div>Every time we add an output =
type specialization, we introduce a new codepath in the core of the =
script consensus that must be maintained forever. Take P2SH: from this =
point forward there is no reason to use it in new applications, ever. =
But it must be forever supported. In an alternate universe we could have =
deployed a native MAST proposal, like BIP 114, only to have Taproot-like =
schemes discovered after activation. That would have been a sucky =
outcome. It is still the case that we could go for Taproot right now, =
and then in six months or a year=E2=80=99s time we find an important =
tweak or a different approach entirely that is even better, but the =
activation process had already started. That would be a sucky outcome we =
haven=E2=80=99t avoided yet.</div><div><br class=3D""></div><div>This is =
not an argument against template specialization for common code paths, =
especially those which increase fungibility of coins. I do think we =
should have a native MAST template eventually, using Taproot or =
something better. However if I may be allowed I will make an educated =
guess about the origin of Taproot: I think it=E2=80=99s no coincidence =
that Greg had this insight and/or wrote it up simultaneous with a push =
by myself and others for getting MAST features into bitcoin via BIPs 98, =
116, and 117, or 114. Cryptographers tend to only think up solutions to =
problems that are on their minds. And the problems on most people=E2=80=99=
s minds are primarily those that are deployable today, or otherwise =
near-term applicable.</div><div><br class=3D""></div><div>BIPS 116 and =
117 each provide a reusable component that together happens to enable a =
generic form of MAST. Even without the workarounds required to avoid =
CLEANSTACK violations, the resulting MAST template is larger than what =
is possible with specialization. However let=E2=80=99s not forget that =
(1) they also enable other applications like honeypots, key trees, and =
script delegation; and relevant to this conversation (2) they get the =
MAST feature available for use in production by the wider community. I =
don=E2=80=99t think I=E2=80=99d personally be willing to bet that we =
found the optimal MAST structure in Greg=E2=80=99s Taproot until we have =
people doing interesting production work like multisig wallets, =
lightning protocol, and the next set of consensus features start putting =
it into production and exploring edge cases. We may find ways Taproot =
can be tweaked to enable other applications (like encoding a hash =
preimage as well) or simplify obscure corner cases.</div><div><br =
class=3D""></div><div>I feel quite strongly that the correct approach is =
to add support for generic features to accomplish the underlying goal in =
a user programmable way, and THEN after activation and some usage =
consider ways in which common use cases can be made more efficient =
through output specialization. To take a more obvious example, lightning =
protocol is still an active area or research and I think it is =
abundantly clear that we don=E2=80=99t know yet what the globally =
optimal layer-2 caching protocol will be, even if we have educated =
guesses as to its broad structure. A proposal right now to standardize a =
more compact lightning script type would be rightly rejected. It is less =
obvious but just as true that the same should hold for =
MAST.</div><div><br class=3D""></div><div>I have argued these points =
before in favor of permission less innovation first, then application =
specialization later, in [1] and at the end of the rather long email =
[2]. I hope you can take the time to read those if you still feel we =
should take a specialized template approach instead of the user =
programmable BIPSs 116 and 117.</div><div><br =
class=3D""></div><div>[1]&nbsp;<a =
href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-Janua=
ry/015537.html" =
class=3D"">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-Ja=
nuary/015537.html</a></div><div>[2]&nbsp;<a =
href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-Septe=
mber/015029.html" =
class=3D"">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-Se=
ptember/015029.html</a></div><div><br class=3D""></div><div><blockquote =
type=3D"cite" class=3D""><div class=3D"">On Jan 22, 2018, at 6:51 PM, =
Matt Corallo via bitcoin-dev &lt;<a =
href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" =
class=3D"">bitcoin-dev@lists.linuxfoundation.org</a>&gt; wrote:</div><br =
class=3D"Apple-interchange-newline"><div class=3D""><div class=3D"">Thanks=
 Greg!<br class=3D"">
<br class=3D"">
I'd be hesitant to deploy a MAST proposal without this clever =
application of pay-to-contract-hash now! Looks like the overhead over a =
more-naive MAST construction is rather trivial, too!<br class=3D"">
<br class=3D"">
Matt<br class=3D""><br class=3D""><div class=3D"gmail_quote">On January =
23, 2018 12:30:06 AM UTC, Gregory Maxwell via bitcoin-dev &lt;<a =
href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" =
class=3D"">bitcoin-dev@lists.linuxfoundation.org</a>&gt; =
wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt =
0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<pre class=3D"k9mail">Interest in merkelized scriptPubKeys (e.g. MAST) =
is driven by two main<br class=3D"">areas: efficiency and privacy. =
Efficiency because unexecuted forks of<br class=3D"">a script can avoid =
ever hitting the chain, and privacy because hiding<br =
class=3D"">unexecuted code leaves scripts indistinguishable to the =
extent that<br class=3D"">their only differences are in the unexecuted =
parts.<br class=3D""><br class=3D"">As Mark Friedenbach and others have =
pointed out before it is almost<br class=3D"">always the case that =
interesting scripts have a logical top level<br class=3D"">branch which =
allows satisfaction of the contract with nothing other<br class=3D"">than =
a signature by all parties.  Other branches would only be used<br =
class=3D"">where some participant is failing to cooperate. More strongly =
stated,<br class=3D"">I believe that _any_ contract with a fixed finite =
participant set<br class=3D"">upfront can be and should be represented =
as an OR between an N-of-N<br class=3D"">and whatever more complex =
contract you might want to represent.<br class=3D""><br class=3D"">One =
point that comes up while talking about merkelized scripts is can<br =
class=3D"">we go about making fancier contract use cases as =
indistinguishable as<br class=3D"">possible from the most common and =
boring payments. Otherwise, if the<br class=3D"">anonymity set of fancy =
usage is only other fancy usage it may not be<br class=3D"">very large =
in practice. One suggestion has been that ordinary<br =
class=3D"">checksig-only scripts should include a dummy branch for the =
rest of<br class=3D"">the tree (e.g. a random value hash), making it =
look like there are<br class=3D"">potentially alternative rules when =
there aren't really.  The negative<br class=3D"">side of this is an =
additional 32-byte overhead for the overwhelmingly<br class=3D"">common =
case which doesn't need it.  I think the privacy gains are<br =
class=3D"">worth doing such a thing, but different people reason =
differently<br class=3D"">about these trade-offs.<br class=3D""><br =
class=3D"">It turns out, however, that there is no need to make a =
trade-off.  The<br class=3D"">special case of a top level =
"threshold-signature OR<br class=3D"">arbitrary-conditions" can be made =
indistinguishable from a normal<br class=3D"">one-party signature, with =
no overhead at all, with a special<br class=3D"">delegating CHECKSIG =
which I call Taproot.<br class=3D""><br class=3D"">Let's say we want to =
create a coin that can be redeemed by either<br class=3D"">Alice =
&amp;&amp; Bob   or by CSV-timelock &amp;&amp; Bob.<br class=3D""><br =
class=3D"">Alice has public A, Bob has pubkey B.<br class=3D""><br =
class=3D"">We compute the 2-of-2 aggregate key C =3D A + B.  =
(Simplified; to<br class=3D"">protect against rogue key attacks you may =
want to use the MuSig key<br class=3D"">aggregation function [1])<br =
class=3D""><br class=3D"">We form our timelock script S =3D  =
"&lt;timeout&gt; OP_CSV OP_DROP B OP_CHECKSIGVERIFY"<br class=3D""><br =
class=3D"">Now we tweak C to produce P which is the key we'll publish: P =
=3D C + H(C||S)G.<br class=3D""><br class=3D"">(This is the attack =
hardened pay-to-contract construction described in [2])<br class=3D""><br =
class=3D"">Then we pay to a scriptPubKey of [Taproot supporting version] =
[EC point P].<br class=3D""><br class=3D"">Now Alice and Bob-- assuming =
they are both online and agree about the<br class=3D"">resolution of =
their contract-- can jointly form a 2 of 2 signature for<br class=3D"">P, =
and spend as if it were a payment to a single party (one of them<br =
class=3D"">just needs to add H(C||S) to their private key).<br =
class=3D""><br class=3D"">Alternatively, the Taproot consensus rules =
would allow this script to<br class=3D"">be satisfied by someone who =
provides the network with C (the original<br class=3D"">combined =
pubkey), S, and does whatever S requires-- e.g. passes the<br =
class=3D"">CSV check and provides Bob's signature. With this information =
the<br class=3D"">network can verify that C + H(C||S) =3D=3D P.<br =
class=3D""><br class=3D"">So in the all-sign case there is zero =
overhead; and no one can tell<br class=3D"">that the contract =
alternative exists. In the alternative redemption<br class=3D"">branch =
the only overhead is revealing the original combined pubkey<br =
class=3D"">and, of course, the existence of the contract is made =
public.<br class=3D""><br class=3D"">This composes just fine with =
whatever other merkelized script system<br class=3D"">we might care to =
use, as the S can be whatever kind of data we want,<br =
class=3D"">including the root of some tree.<br class=3D""><br =
class=3D"">My example shows 2-of-2 but it works the same for any number =
of<br class=3D"">participants (and with setup interaction any threshold =
of<br class=3D"">participants, so long as you don't mind an inability to =
tell which<br class=3D"">members signed off).<br class=3D""><br =
class=3D"">The verification computational complexity of signature path =
is<br class=3D"">obviously the same as any other plain signature (since =
its<br class=3D"">indistinguishable). Verification of the branch =
redemption requires a<br class=3D"">hash and a multiplication with a =
constant point which is strictly more<br class=3D"">efficient than a =
signature verification and could be efficiently fused<br class=3D"">into =
batch signature validation.<br class=3D""><br class=3D"">The nearest =
competitor to this idea that I can come up with would<br =
class=3D"">supporting a simple delegation where the output can be spent =
by the<br class=3D"">named key, or a spending transaction could provide =
a script along with<br class=3D"">a signature of that script by the =
named key, delegating control to the<br class=3D"">signed script. Before =
paying into that escrow Alice/Bob would<br class=3D"">construct this =
signature. This idea is equally efficient in the common<br =
class=3D"">case, but larger and slower to verify in the alternative =
spend case.<br class=3D"">Setting up the signature requires additional =
interaction between<br class=3D"">participants and the resulting =
signature must be durably stored and<br class=3D"">couldn't just be =
recomputed using single-party information.<br class=3D""><br class=3D"">I =
believe this construction will allow the largest possible anonymity<br =
class=3D"">set for fixed party smart contracts by making them look like =
the<br class=3D"">simplest possible payments. It accomplishes this =
without any overhead<br class=3D"">in the common case, invoking any =
sketchy or impractical techniques,<br class=3D"">requiring extra rounds =
of interaction between contract participants,<br class=3D"">and without =
requiring the durable storage of other data.<br class=3D""><br =
class=3D""><br class=3D"">[1] <a href=3D"https://eprint.iacr.org/2018/068"=
 class=3D"">https://eprint.iacr.org/2018/068</a><br class=3D"">[2] <a =
href=3D"https://blockstream.com/sidechains.pdf" =
class=3D"">https://blockstream.com/sidechains.pdf</a> Appendix A<br =
class=3D""><hr class=3D""><br class=3D"">bitcoin-dev mailing list<br =
class=3D""><a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" =
class=3D"">bitcoin-dev@lists.linuxfoundation.org</a><br class=3D""><a =
href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
class=3D"">https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev<=
/a><br =
class=3D""></pre></blockquote></div></div>________________________________=
_______________<br class=3D"">bitcoin-dev mailing list<br class=3D""><a =
href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" =
class=3D"">bitcoin-dev@lists.linuxfoundation.org</a><br =
class=3D"">https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev<=
br class=3D""></div></blockquote></div><br class=3D""></div></body></html>=

--Apple-Mail=_AE03DB4F-2910-4A79-B166-B0F5F2D01688--