Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id C50DB1014 for ; Tue, 23 Jan 2018 21:23:31 +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 B8D76CA for ; Tue, 23 Jan 2018 21:23:29 +0000 (UTC) Received: from [IPv6:2607:fb90:1ed8:9046:d5e4:d7c3:b43e:c8c0] (unknown [172.56.44.209]) by mail.bluematt.me (Postfix) with ESMTPSA id 8E8031A1882; Tue, 23 Jan 2018 21:23:27 +0000 (UTC) Date: Tue, 23 Jan 2018 21:23:21 +0000 In-Reply-To: <285E52DF-04E8-4E03-85A0-764F54B3EED9@friedenbach.org> References: <61C1114D-A4E3-4628-AB7E-17C09EDDC2DE@mattcorallo.com> <285E52DF-04E8-4E03-85A0-764F54B3EED9@friedenbach.org> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----VXY0DXTQHOMBCI0TUUNZ6T3F5JR63O" Content-Transfer-Encoding: 7bit To: Mark Friedenbach , Bitcoin Protocol Discussion From: Matt Corallo Message-ID: 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 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 21:23:31 -0000 ------VXY0DXTQHOMBCI0TUUNZ6T3F5JR63O Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable The issue with that approach without support for the privacy-encouraging wr= apper proposed by Greg here is that it encourages adoption halfway and dest= roys a lot of the value of the apparent-script monoculture for privacy pres= ervation=2E Greg's proposal here doesn't change the format of any specific = MAST implementation, but instead adds the privacy wrapper that I always fel= t was missing in existing proposals, without any real additional overhead i= n many use-cases! Indeed, permissionless innovation is important, but the huge advantage of = providing the privacy wrapper by default here is absolutely massive to the = ecosystem and should not be handwaved away for vague possibly-advantages=2E Matt On January 23, 2018 2:39:37 PM UTC, Mark Friedenbach wrote: >I had the opposite response in private, which I will share here=2E 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=2E 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=2E It's not used in production anywhere=2E Even i= f >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=2E 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=2E Not the >other way around=2E [1] > >I take this advance as further evidence in favor of this view=2E 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=2E Taproo= t is a >clearly superior approach=2E But is it optimal? I don=E2=80=99t think we = can >claim that now=2E Optimality of these constructs isn=E2=80=99t something = easily >proven, with the nearest substitute being unchanging consensus over >extended periods of time=2E > >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=2E Take P2SH: from this point forward there is no reason to use >it in new applications, ever=2E But it must be forever supported=2E In an >alternate universe we could have deployed a native MAST proposal, like >BIP 114, only to have Taproot-like schemes discovered after activation=2E >That would have been a sucky outcome=2E It is still the case that we >could go for Taproot right now, and then in six months or a year=E2=80=99= s time >we find an important tweak or a different approach entirely that is >even better, but the activation process had already started=2E That would >be a sucky outcome we haven=E2=80=99t avoided yet=2E > >This is not an argument against template specialization for common code >paths, especially those which increase fungibility of coins=2E I do think >we should have a native MAST template eventually, using Taproot or >something better=2E 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 th= at >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=2E Cryptographers tend to only think up solutions to >problems that are on their minds=2E And the problems on most people=E2=80= =99s >minds are primarily those that are deployable today, or otherwise >near-term applicable=2E > >BIPS 116 and 117 each provide a reusable component that together >happens to enable a generic form of MAST=2E Even without the workarounds >required to avoid CLEANSTACK violations, the resulting MAST template is >larger than what is possible with specialization=2E 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=2E I don=E2=80=99t think I=E2=80=99d personally be willing to b= et 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=2E We may find ways Taproot can be tweaked to >enable other applications (like encoding a hash preimage as well) or >simplify obscure corner cases=2E > >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=2E 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=2E A proposal right now to standardize a more >compact lightning script type would be rightly rejected=2E It is less >obvious but just as true that the same should hold for MAST=2E > >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]=2E 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=2E > >[1] >https://lists=2Elinuxfoundation=2Eorg/pipermail/bitcoin-dev/2018-January/= 015537=2Ehtml > >[2] >https://lists=2Elinuxfoundation=2Eorg/pipermail/bitcoin-dev/2017-Septembe= r/015029=2Ehtml > > >> On Jan 22, 2018, at 6:51 PM, Matt Corallo via bitcoin-dev > 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 > wrote: >> Interest in merkelized scriptPubKeys (e=2Eg=2E MAST) is driven by two >main >> 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 >>=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=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 >>=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=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 >>=20 >> It turns out, however, that there is no need to make a trade-off=2E=20 >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 >>=20 >> Let's say we want to create a coin that can be redeemed by either >> Alice && Bob or by CSV-timelock && Bob=2E >>=20 >> Alice has public A, Bob has pubkey B=2E >>=20 >> 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]) >>=20 >> We form our timelock script S =3D " 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=2E >>=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]=2E >>=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)=2E >>=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=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 >>=20 >> 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 >>=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=2E >>=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)=2E >>=20 >> 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 >>=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=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 >>=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=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 >>=20 >>=20 >> [1] https://eprint=2Eiacr=2Eorg/2018/068 > >> [2] https://blockstream=2Ecom/sidechains=2Epdf > Appendix A >>=20 >> bitcoin-dev mailing list >> bitcoin-dev@lists=2Elinuxfoundation=2Eorg >> https://lists=2Elinuxfoundation=2Eorg/mailman/listinfo/bitcoin-dev > >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists=2Elinuxfoundation=2Eorg >> https://lists=2Elinuxfoundation=2Eorg/mailman/listinfo/bitcoin-dev ------VXY0DXTQHOMBCI0TUUNZ6T3F5JR63O Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: quoted-printable The issue with that approa= ch without support for the privacy-encouraging wrapper proposed by Greg her= e is that it encourages adoption halfway and destroys a lot of the value of= the apparent-script monoculture for privacy preservation=2E Greg's pro= posal here doesn't change the format of any specific MAST implementatio= n, but instead adds the privacy wrapper that I always felt was missing in e= xisting proposals, without any real additional overhead in many use-cases!<= br>
Indeed, permissionless innovation is important, but the huge advantage of = providing the privacy wrapper by default here is absolutely massive to the = ecosystem and should not be handwaved away for vague possibly-advantages=2E=

Matt

On January 23, 2018 2:39:37 PM UTC,= Mark Friedenbach <mark@friedenbach=2Eorg> wrote:
I had the opposite response in private, which I will share here=2E As rece= ntly as Jan 9th feedback on BIP 117 was shared on this list by Pieter Wuill= e and others suggesting we adopt native MAST template instead of the user p= rogrammable combination of BIPs 116 and 117=2E Part of my response then was= , I quote:

I have= nt the hubris to suggest that we know exactly what a templated MAST *should= * look like=2E It's not used in production anywhere=2E Even if we did have = the foresight, the tail-call semantics allow for other constructions beside= s MAST and for the sake of the future we should allow such permission-less = innovation=2E 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=2E Not the other way around=2E [1]
<= div class=3D"">

I take this advance as furthe= r evidence in favor of this view=2E 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=2E Taproot is a clearly superior approach=2E But is it optima= l? I don=E2=80=99t think we can claim that now=2E Optimality of these const= ructs isn=E2=80=99t something easily proven, with the nearest substitute be= ing unchanging consensus over extended periods of time=2E

Every time we add an output type specialization, we intr= oduce a new codepath in the core of the script consensus that must be maint= ained forever=2E Take P2SH: from this point forward there is no reason to u= se it in new applications, ever=2E But it must be forever supported=2E In a= n alternate universe we could have deployed a native MAST proposal, like BI= P 114, only to have Taproot-like schemes discovered after activation=2E Tha= t would have been a sucky outcome=2E 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 f= ind an important tweak or a different approach entirely that is even better= , but the activation process had already started=2E That would be a sucky o= utcome we haven=E2=80=99t avoided yet=2E

This is not an argument against template specialization for common code p= aths, especially those which increase fungibility of coins=2E I do think we= should have a native MAST template eventually, using Taproot or something = better=2E However if I may be allowed I will make an educated guess about t= he origin of Taproot: I think it=E2=80=99s no coincidence that Greg had thi= s 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=2E= Cryptographers tend to only think up solutions to problems that are on the= ir minds=2E And the problems on most people=E2=80=99s minds are primarily t= hose that are deployable today, or otherwise near-term applicable=2E
<= div>
BIPS 116 and 117 each provide a reusable comp= onent that together happens to enable a generic form of MAST=2E Even withou= t the workarounds required to avoid CLEANSTACK violations, the resulting MA= ST template is larger than what is possible with specialization=2E 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 conversat= ion (2) they get the MAST feature available for use in production by the wi= der community=2E 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 unt= il 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=2E We may find ways Taproot can b= e tweaked to enable other applications (like encoding a hash preimage as we= ll) or simplify obscure corner cases=2E

I feel quite strongly that the correct approach is to add support for gene= ric 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=2E To take a= more obvious example, lightning protocol is still an active area or resear= ch and I think it is abundantly clear that we don=E2=80=99t know yet what t= he globally optimal layer-2 caching protocol will be, even if we have educa= ted guesses as to its broad structure=2E A proposal right now to standardiz= e a more compact lightning script type would be rightly rejected=2E It is l= ess obvious but just as true that the same should hold for MAST=2E
I have argued these points before in favor of p= ermission less innovation first, then application specialization later, in = [1] and at the end of the rather long email [2]=2E 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=2E

On Jan 22, 2018, at 6:51 PM, Matt Corallo via bitcoin= -dev <bitcoin-dev@lists=2Elinuxfoundation=2Eorg> wrote:

Thanks Gre= g!

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 <bitcoin-dev@lists= =2Elinuxfoundation=2Eorg> wrote:
Interest in merkelized scriptPubKeys (e=2Eg=2E MAST)=
 is driven by two main
areas: efficiency and privacy=2E Effic=
iency because unexecuted forks of
a script can avoid ever hit=
ting the chain, and privacy because hiding
unexecuted code le=
aves 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 ot=
her
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 r=
epresented as an OR between an N-of-N
and whatever more compl=
ex 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 Otherwi=
se, if the
anonymity set of fancy usage is only other fancy u=
sage it may not be
very large in practice=2E One suggestion h=
as been that ordinary
checksig-only scripts should include a =
dummy branch for the rest of
the tree (e=2Eg=2E a random valu=
e hash), making it look like there are
potentially alternativ=
e rules when there aren't really=2E  The negative
side of thi=
s is an additional 32-byte overhead for the overwhelmingly
co=
mmon 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
arbitr=
ary-conditions" can be made indistinguishable from a normal
o=
ne-party signature, with no overhead at all, with a special
d=
elegating 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 describe=
d in [2])

Then we pay to a scriptPubKey of [Ta=
proot 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 fo=
r
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 woul=
d allow this script to
be satisfied by someone who provides t=
he network with C (the original
combined pubkey), S, and does=
 whatever S requires-- e=2Eg=2E passes the
CSV check and prov=
ides 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
th=
at the contract alternative exists=2E In the alternative redemption
branch the only overhead is revealing the original combined pubkeyand, of course, the existence of the contract is made public=
=2E

This composes just fine with whatever othe=
r 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 inter=
action any threshold of
participants, so long as you don't mi=
nd 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 (sin=
ce its
indistinguishable)=2E Verification of the branch redem=
ption requires a
hash and a multiplication with a constant po=
int which is strictly more
efficient than a signature verific=
ation and could be efficiently fused
into batch signature val=
idation=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 spendin=
g transaction could provide a script along with
a signature o=
f that script by the named key, delegating control to the
sig=
ned script=2E Before paying into that escrow Alice/Bob would
=
construct this signature=2E This idea is equally efficient in the commoncase, but larger and slower to verify in the alternative spend =
case=2E
Setting up the signature requires additional interact=
ion between
participants and the resulting signature must be =
durably stored and
couldn't just be recomputed using single-p=
arty information=2E

I believe this constructio=
n will allow the largest possible anonymity
set for fixed par=
ty smart contracts by making them look like the
simplest poss=
ible 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,<=
br class=3D"">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
bitcoi=
n-dev@lists=2Elinuxfoundation=2Eorg
https:=
//lists=2Elinuxfoundation=2Eorg/mailman/listinfo/bitcoin-dev
______________________________________= _________
bitcoin-dev mailing list
bitcoin-dev@lis= ts=2Elinuxfoundation=2Eorg
https://lists=2Elinuxfoundatio= n=2Eorg/mailman/listinfo/bitcoin-dev

------VXY0DXTQHOMBCI0TUUNZ6T3F5JR63O--