Date: Tue, 23 Jan 2018 02:51:51 +0000
In-Reply-To: <CAAS2fgTXg5kk6TyUM9dS=tf5N0_Z-GKVmzMLwTW1HxUgrqdo+Q@mail.gmail.com>
References: <CAAS2fgTXg5kk6TyUM9dS=tf5N0_Z-GKVmzMLwTW1HxUgrqdo+Q@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/alternative;
	boundary="----9VD9UAGH7C6ZZ0UCO6PP00ABXCZRAZ"
Content-Transfer-Encoding: 7bit
To: Gregory Maxwell <greg@xiph.org>,
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
	Gregory Maxwell via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>,
	Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
From: Matt Corallo <lf-lists@mattcorallo.com>
Message-ID: <61C1114D-A4E3-4628-AB7E-17C09EDDC2DE@mattcorallo.com>
Subject: Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting
Precedence: list

------9VD9UAGH7C6ZZ0UCO6PP00ABXCZRAZ
Content-Type: text/plain;
 charset=utf-8
Content-Transfer-Encoding: quoted-printable

Thanks Greg!

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!

Matt

On January 23, 2018 12:30:06 AM UTC, Gregory Maxwell via bitcoin-dev <bitc=
oin-dev@lists=2Elinuxfoundation=2Eorg> wrote:
>Interest in merkelized scriptPubKeys (e=2Eg=2E MAST) is driven by two mai=
n
>areas: efficiency and privacy=2E 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=2E
>
>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=2E  Other branches would only be used
>where some participant is failing to cooperate=2E 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=2E
>
>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=2E Otherwise, if the
>anonymity set of fancy usage is only other fancy usage it may not be
>very large in practice=2E One suggestion has been that ordinary
>checksig-only scripts should include a dummy branch for the rest of
>the tree (e=2Eg=2E a random value hash), making it look like there are
>potentially alternative rules when there aren't really=2E  The negative
>side of this is an additional 32-byte overhead for the overwhelmingly
>common case which doesn't need it=2E  I think the privacy gains are
>worth doing such a thing, but different people reason differently
>about these trade-offs=2E
>
>It turns out, however, that there is no need to make a trade-off=2E  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=2E
>
>Let's say we want to create a coin that can be redeemed by either
>Alice && Bob   or by CSV-timelock && Bob=2E
>
>Alice has public A, Bob has pubkey B=2E
>
>We compute the 2-of-2 aggregate key C =3D A + B=2E  (Simplified; to
>protect against rogue key attacks you may want to use the MuSig key
>aggregation function [1])
>
>We form our timelock script S =3D  "<timeout> OP_CSV OP_DROP B
>OP_CHECKSIGVERIFY"
>
>Now we tweak C to produce P which is the key we'll publish: P =3D C +
>H(C||S)G=2E
>
>(This is the attack hardened pay-to-contract construction described in
>[2])
>
>Then we pay to a scriptPubKey of [Taproot supporting version] [EC point
>P]=2E
>
>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)=2E
>
>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=2Eg=2E passes the
>CSV check and provides Bob's signature=2E With this information the
>network can verify that C + H(C||S) =3D=3D P=2E
>
>So in the all-sign case there is zero overhead; and no one can tell
>that the contract alternative exists=2E 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=2E
>
>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=2E
>
>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)=2E
>
>The verification computational complexity of signature path is
>obviously the same as any other plain signature (since its
>indistinguishable)=2E 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=2E
>
>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=2E Before paying into that escrow Alice/Bob would
>construct this signature=2E This idea is equally efficient in the common
>case, but larger and slower to verify in the alternative spend case=2E
>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=2E
>
>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=2E 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=2E
>
>
>[1] https://eprint=2Eiacr=2Eorg/2018/068
>[2] https://blockstream=2Ecom/sidechains=2Epdf Appendix A
>_______________________________________________
>bitcoin-dev mailing list
>bitcoin-dev@lists=2Elinuxfoundation=2Eorg
>https://lists=2Elinuxfoundation=2Eorg/mailman/listinfo/bitcoin-dev

------9VD9UAGH7C6ZZ0UCO6PP00ABXCZRAZ
Content-Type: text/html;
 charset=utf-8
Content-Transfer-Encoding: quoted-printable

<html><head></head><body>Thanks Greg!<br>
<br>
I&#39;d be hesitant to deploy a MAST proposal without this clever applicat=
ion of pay-to-contract-hash now! Looks like the overhead over a more-naive =
MAST construction is rather trivial, too!<br>
<br>
Matt<br><br><div class=3D"gmail_quote">On January 23, 2018 12:30:06 AM UTC=
, Gregory Maxwell via bitcoin-dev &lt;bitcoin-dev@lists=2Elinuxfoundation=
=2Eorg&gt; wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt=
 0pt 0=2E8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;=
">
<pre class=3D"k9mail">Interest in merkelized scriptPubKeys (e=2Eg=2E MAST)=
 is driven by two main<br>areas: efficiency and privacy=2E Efficiency becau=
se unexecuted forks of<br>a script can avoid ever hitting the chain, and pr=
ivacy because hiding<br>unexecuted code leaves scripts indistinguishable to=
 the extent that<br>their only differences are in the unexecuted parts=2E<b=
r><br>As Mark Friedenbach and others have pointed out before it is almost<b=
r>always the case that interesting scripts have a logical top level<br>bran=
ch which allows satisfaction of the contract with nothing other<br>than a s=
ignature by all parties=2E  Other branches would only be used<br>where some=
 participant is failing to cooperate=2E More strongly stated,<br>I believe =
that _any_ contract with a fixed finite participant set<br>upfront can be a=
nd should be represented as an OR between an N-of-N<br>and whatever more co=
mplex contract you might want to represent=2E<br><br>One point that comes u=
p while talking about merkelized scripts is can<br>we go about making fanci=
er contract use cases as indistinguishable as<br>possible from the most com=
mon and boring payments=2E Otherwise, if the<br>anonymity set of fancy usag=
e is only other fancy usage it may not be<br>very large in practice=2E One =
suggestion has been that ordinary<br>checksig-only scripts should include a=
 dummy branch for the rest of<br>the tree (e=2Eg=2E a random value hash), m=
aking it look like there are<br>potentially alternative rules when there ar=
en't really=2E  The negative<br>side of this is an additional 32-byte overh=
ead for the overwhelmingly<br>common case which doesn't need it=2E  I think=
 the privacy gains are<br>worth doing such a thing, but different people re=
ason differently<br>about these trade-offs=2E<br><br>It turns out, however,=
 that there is no need to make a trade-off=2E  The<br>special case of a top=
 level "threshold-signature OR<br>arbitrary-conditions" can be made indisti=
nguishable from a normal<br>one-party signature, with no overhead at all, w=
ith a special<br>delegating CHECKSIG which I call Taproot=2E<br><br>Let's s=
ay we want to create a coin that can be redeemed by either<br>Alice &amp;&a=
mp; Bob   or by CSV-timelock &amp;&amp; Bob=2E<br><br>Alice has public A, B=
ob has pubkey B=2E<br><br>We compute the 2-of-2 aggregate key C =3D A + B=
=2E  (Simplified; to<br>protect against rogue key attacks you may want to u=
se the MuSig key<br>aggregation function [1])<br><br>We form our timelock s=
cript S =3D  "&lt;timeout&gt; OP_CSV OP_DROP B OP_CHECKSIGVERIFY"<br><br>No=
w we tweak C to produce P which is the key we'll publish: P =3D C + H(C||S)=
G=2E<br><br>(This is the attack hardened pay-to-contract construction descr=
ibed in [2])<br><br>Then we pay to a scriptPubKey of [Taproot supporting ve=
rsion] [EC point P]=2E<br><br>Now Alice and Bob-- assuming they are both on=
line and agree about the<br>resolution of their contract-- can jointly form=
 a 2 of 2 signature for<br>P, and spend as if it were a payment to a single=
 party (one of them<br>just needs to add H(C||S) to their private key)=2E<b=
r><br>Alternatively, the Taproot consensus rules would allow this script to=
<br>be satisfied by someone who provides the network with C (the original<b=
r>combined pubkey), S, and does whatever S requires-- e=2Eg=2E passes the<b=
r>CSV check and provides Bob's signature=2E With this information the<br>ne=
twork can verify that C + H(C||S) =3D=3D P=2E<br><br>So in the all-sign cas=
e there is zero overhead; and no one can tell<br>that the contract alternat=
ive exists=2E In the alternative redemption<br>branch the only overhead is =
revealing the original combined pubkey<br>and, of course, the existence of =
the contract is made public=2E<br><br>This composes just fine with whatever=
 other merkelized script system<br>we might care to use, as the S can be wh=
atever kind of data we want,<br>including the root of some tree=2E<br><br>M=
y example shows 2-of-2 but it works the same for any number of<br>participa=
nts (and with setup interaction any threshold of<br>participants, so long a=
s you don't mind an inability to tell which<br>members signed off)=2E<br><b=
r>The verification computational complexity of signature path is<br>obvious=
ly the same as any other plain signature (since its<br>indistinguishable)=
=2E Verification of the branch redemption requires a<br>hash and a multipli=
cation with a constant point which is strictly more<br>efficient than a sig=
nature verification and could be efficiently fused<br>into batch signature =
validation=2E<br><br>The nearest competitor to this idea that I can come up=
 with would<br>supporting a simple delegation where the output can be spent=
 by the<br>named key, or a spending transaction could provide a script alon=
g with<br>a signature of that script by the named key, delegating control t=
o the<br>signed script=2E Before paying into that escrow Alice/Bob would<br=
>construct this signature=2E This idea is equally efficient in the common<b=
r>case, but larger and slower to verify in the alternative spend case=2E<br=
>Setting up the signature requires additional interaction between<br>partic=
ipants and the resulting signature must be durably stored and<br>couldn't j=
ust be recomputed using single-party information=2E<br><br>I believe this c=
onstruction will allow the largest possible anonymity<br>set for fixed part=
y smart contracts by making them look like the<br>simplest possible payment=
s=2E It accomplishes this without any overhead<br>in the common case, invok=
ing any sketchy or impractical techniques,<br>requiring extra rounds of int=
eraction between contract participants,<br>and without requiring the durabl=
e storage of other data=2E<br><br><br>[1] <a href=3D"https://eprint=2Eiacr=
=2Eorg/2018/068">https://eprint=2Eiacr=2Eorg/2018/068</a><br>[2] <a href=3D=
"https://blockstream=2Ecom/sidechains=2Epdf">https://blockstream=2Ecom/side=
chains=2Epdf</a> Appendix A<br><hr><br>bitcoin-dev mailing list<br>bitcoin-=
dev@lists=2Elinuxfoundation=2Eorg<br><a href=3D"https://lists=2Elinuxfounda=
tion=2Eorg/mailman/listinfo/bitcoin-dev">https://lists=2Elinuxfoundation=2E=
org/mailman/listinfo/bitcoin-dev</a><br></pre></blockquote></div></body></h=
tml>
------9VD9UAGH7C6ZZ0UCO6PP00ABXCZRAZ--