Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id D0BFE1005 for ; Tue, 23 Jan 2018 02:52:17 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from mail.bluematt.me (mail.bluematt.me [192.241.179.72]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 86826134 for ; Tue, 23 Jan 2018 02:52:16 +0000 (UTC) Received: from [IPv6:2607:fb90:1ede:7cc7:59d4:96d4:3f1c:85d0] (unknown [172.56.44.95]) by mail.bluematt.me (Postfix) with ESMTPSA id 227AD1A0D34; Tue, 23 Jan 2018 02:52:07 +0000 (UTC) Date: Tue, 23 Jan 2018 02:51:51 +0000 In-Reply-To: References: MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----9VD9UAGH7C6ZZ0UCO6PP00ABXCZRAZ" Content-Transfer-Encoding: 7bit To: Gregory Maxwell , Bitcoin Protocol Discussion , Gregory Maxwell via bitcoin-dev , Bitcoin Dev From: Matt Corallo Message-ID: <61C1114D-A4E3-4628-AB7E-17C09EDDC2DE@mattcorallo.com> X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,HTML_MESSAGE 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, 23 Jan 2018 05:22:21 +0000 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 23 Jan 2018 02:52:17 -0000 ------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 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 " 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 Thanks Greg!

I'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!

Matt

On January 23, 2018 12:30:06 AM UTC= , Gregory Maxwell via bitcoin-dev <bitcoin-dev@lists=2Elinuxfoundation= =2Eorg> wrote:
Interest in merkelized scriptPubKeys (e=2Eg=2E MAST)= is driven by two main
areas: efficiency and privacy=2E Efficiency becau= se unexecuted forks of
a script can avoid ever hitting the chain, and pr= ivacy 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 almostalways the case that interesting scripts have a logical top level
bran= ch which allows satisfaction of the contract with nothing other
than a s= ignature 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 a= nd should be represented as an OR between an N-of-N
and whatever more co= mplex contract you might want to represent=2E

One point that comes u= p while talking about merkelized scripts is can
we go about making fanci= er contract use cases as indistinguishable as
possible from the most com= mon and boring payments=2E Otherwise, if the
anonymity set of fancy usag= e 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), m= aking it look like there are
potentially alternative rules when there ar= en't really=2E The negative
side of this is an additional 32-byte overh= ead 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 re= ason 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 indisti= nguishable from a normal
one-party signature, with no overhead at all, w= ith a special
delegating CHECKSIG which I call Taproot=2E

Let's s= ay we want to create a coin that can be redeemed by either
Alice &&a= mp; Bob or by CSV-timelock && Bob=2E

Alice has public A, B= ob 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 u= se the MuSig key
aggregation function [1])

We form our timelock s= cript S =3D "<timeout> OP_CSV OP_DROP B OP_CHECKSIGVERIFY"

No= w 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 descr= ibed in [2])

Then we pay to a scriptPubKey of [Taproot supporting ve= rsion] [EC point P]=2E

Now Alice and Bob-- assuming they are both on= line 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 originalcombined pubkey), S, and does whatever S requires-- e=2Eg=2E passes theCSV check and provides Bob's signature=2E With this information the
ne= twork can verify that C + H(C||S) =3D=3D P=2E

So in the all-sign cas= e there is zero overhead; and no one can tell
that the contract alternat= ive 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 wh= atever kind of data we want,
including the root of some tree=2E

M= y example shows 2-of-2 but it works the same for any number of
participa= nts (and with setup interaction any threshold of
participants, so long a= s you don't mind an inability to tell which
members signed off)=2E
The verification computational complexity of signature path is
obvious= ly the same as any other plain signature (since its
indistinguishable)= =2E Verification of the branch redemption requires a
hash and a multipli= cation with a constant point which is strictly more
efficient than a sig= nature 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 alon= g with
a signature of that script by the named key, delegating control t= o the
signed script=2E Before paying into that escrow Alice/Bob wouldconstruct this signature=2E This idea is equally efficient in the commoncase, but larger and slower to verify in the alternative spend case=2ESetting up the signature requires additional interaction between
partic= ipants and the resulting signature must be durably stored and
couldn't j= ust be recomputed using single-party information=2E

I believe this c= onstruction will allow the largest possible anonymity
set for fixed part= y smart contracts by making them look like the
simplest possible payment= s=2E It accomplishes this without any overhead
in the common case, invok= ing any sketchy or impractical techniques,
requiring extra rounds of int= eraction between contract participants,
and without requiring the durabl= e storage of other data=2E


[1] https://eprint=2Eiacr=2Eorg/2018/068
[2] https://blockstream=2Ecom/side= chains=2Epdf Appendix A

bitcoin-dev mailing list
bitcoin-= dev@lists=2Elinuxfoundation=2Eorg
https://lists=2Elinuxfoundation=2E= org/mailman/listinfo/bitcoin-dev
------9VD9UAGH7C6ZZ0UCO6PP00ABXCZRAZ--