MIME-Version: 1.0
In-Reply-To: <CAAS2fgTXg5kk6TyUM9dS=tf5N0_Z-GKVmzMLwTW1HxUgrqdo+Q@mail.gmail.com>
References: <CAAS2fgTXg5kk6TyUM9dS=tf5N0_Z-GKVmzMLwTW1HxUgrqdo+Q@mail.gmail.com>
From: Greg Sanders <gsanders87@gmail.com>
Date: Tue, 23 Jan 2018 10:43:59 -0500
Message-ID: <CAB3F3DuzJv3COKHP2q3o9zSViRU08wRd+9MQ6vB0qLMzSQNPTw@mail.gmail.com>
To: Gregory Maxwell <greg@xiph.org>, 
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="089e0825821886de050563736b15"
Subject: Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting
Precedence: list

--089e0825821886de050563736b15
Content-Type: text/plain; charset="UTF-8"

Interesting parallels to current Elements sidechain peg-in functionality.
User tweaks the watchmen(BTC holder) pubkey using P2CH, committing to a
script that is used on the *sidechain side* as spending authorization for
that bitcoin output rather than mainnet.

I think composing the two can be done as:

P = C' + H(C'||S')G + H(C||S)G

where C is redefined as `C' + H(C'||S')G`, which for Bitcoin consensus
purposes is just a single pubkey.



On Mon, Jan 22, 2018 at 7:30 PM, 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.
>
> 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.
>
> 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.
>
> 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.
>
> Let's say we want to create a coin that can be redeemed by either
> Alice && Bob   or by CSV-timelock && Bob.
>
> Alice has public A, Bob has pubkey B.
>
> We compute the 2-of-2 aggregate key C = A + B.  (Simplified; to
> protect against rogue key attacks you may want to use the MuSig key
> aggregation function [1])
>
> We form our timelock script S =  "<timeout> OP_CSV OP_DROP B
> OP_CHECKSIGVERIFY"
>
> Now we tweak C to produce P which is the key we'll publish: P = C +
> H(C||S)G.
>
> (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].
>
> 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).
>
> 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) == P.
>
> 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.
>
> 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.
>
> 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).
>
> 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.
>
> 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.
>
> 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.
>
>
> [1] https://eprint.iacr.org/2018/068
> [2] https://blockstream.com/sidechains.pdf Appendix A
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

<div dir=3D"ltr">Interesting parallels to current Elements sidechain peg-in=
 functionality. User tweaks the watchmen(BTC holder) pubkey using P2CH, com=
mitting to a script that is used on the *sidechain side* as spending author=
ization for that bitcoin output rather than mainnet.<div><br></div><div>I t=
hink composing the two can be done as:</div><div><br></div><div>P =3D C&#39=
; + H(C&#39;||S&#39;)G + H(C||S)G</div><div><br></div><div>where C is redef=
ined as `C&#39; + H(C&#39;||S&#39;)G`, which for Bitcoin consensus purposes=
 is just a single pubkey.<br><div><br></div><div><br></div></div></div><div=
 class=3D"gmail_extra"><br><div class=3D"gmail_quote">On Mon, Jan 22, 2018 =
at 7:30 PM, Gregory Maxwell via bitcoin-dev <span dir=3D"ltr">&lt;<a href=
=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin=
-dev@lists.linuxfoundation.org</a>&gt;</span> wrote:<br><blockquote class=
=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padd=
ing-left:1ex">Interest in merkelized scriptPubKeys (e.g. MAST) is driven by=
 two main<br>
areas: efficiency and privacy. Efficiency because unexecuted forks of<br>
a script can avoid ever hitting the chain, and privacy because hiding<br>
unexecuted code leaves scripts indistinguishable to the extent that<br>
their only differences are in the unexecuted parts.<br>
<br>
As Mark Friedenbach and others have pointed out before it is almost<br>
always the case that interesting scripts have a logical top level<br>
branch which allows satisfaction of the contract with nothing other<br>
than a signature by all parties.=C2=A0 Other branches would only be used<br=
>
where some participant is failing to cooperate. More strongly stated,<br>
I believe that _any_ contract with a fixed finite participant set<br>
upfront can be and should be represented as an OR between an N-of-N<br>
and whatever more complex contract you might want to represent.<br>
<br>
One point that comes up while talking about merkelized scripts is can<br>
we go about making fancier contract use cases as indistinguishable as<br>
possible from the most common and boring payments. Otherwise, if the<br>
anonymity set of fancy usage is only other fancy usage it may not be<br>
very large in practice. One suggestion has been that ordinary<br>
checksig-only scripts should include a dummy branch for the rest of<br>
the tree (e.g. a random value hash), making it look like there are<br>
potentially alternative rules when there aren&#39;t really.=C2=A0 The negat=
ive<br>
side of this is an additional 32-byte overhead for the overwhelmingly<br>
common case which doesn&#39;t need it.=C2=A0 I think the privacy gains are<=
br>
worth doing such a thing, but different people reason differently<br>
about these trade-offs.<br>
<br>
It turns out, however, that there is no need to make a trade-off.=C2=A0 The=
<br>
special case of a top level &quot;threshold-signature OR<br>
arbitrary-conditions&quot; can be made indistinguishable from a normal<br>
one-party signature, with no overhead at all, with a special<br>
delegating CHECKSIG which I call Taproot.<br>
<br>
Let&#39;s say we want to create a coin that can be redeemed by either<br>
Alice &amp;&amp; Bob=C2=A0 =C2=A0or by CSV-timelock &amp;&amp; Bob.<br>
<br>
Alice has public A, Bob has pubkey B.<br>
<br>
We compute the 2-of-2 aggregate key C =3D A + B.=C2=A0 (Simplified; to<br>
protect against rogue key attacks you may want to use the MuSig key<br>
aggregation function [1])<br>
<br>
We form our timelock script S =3D=C2=A0 &quot;&lt;timeout&gt; OP_CSV OP_DRO=
P B OP_CHECKSIGVERIFY&quot;<br>
<br>
Now we tweak C to produce P which is the key we&#39;ll publish: P =3D C + H=
(C||S)G.<br>
<br>
(This is the attack hardened pay-to-contract construction described in [2])=
<br>
<br>
Then we pay to a scriptPubKey of [Taproot supporting version] [EC point P].=
<br>
<br>
Now Alice and Bob-- assuming they are both online 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).<br>
<br>
Alternatively, the Taproot consensus rules would allow this script to<br>
be satisfied by someone who provides the network with C (the original<br>
combined pubkey), S, and does whatever S requires-- e.g. passes the<br>
CSV check and provides Bob&#39;s signature. With this information the<br>
network can verify that C + H(C||S) =3D=3D P.<br>
<br>
So in the all-sign case there is zero overhead; and no one can tell<br>
that the contract alternative exists. 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.<br>
<br>
This composes just fine with whatever other merkelized script system<br>
we might care to use, as the S can be whatever kind of data we want,<br>
including the root of some tree.<br>
<br>
My example shows 2-of-2 but it works the same for any number of<br>
participants (and with setup interaction any threshold of<br>
participants, so long as you don&#39;t mind an inability to tell which<br>
members signed off).<br>
<br>
The verification computational complexity of signature path is<br>
obviously the same as any other plain signature (since its<br>
indistinguishable). Verification of the branch redemption requires a<br>
hash and a multiplication with a constant point which is strictly more<br>
efficient than a signature verification and could be efficiently fused<br>
into batch signature validation.<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 along with<br>
a signature of that script by the named key, delegating control to the<br>
signed script. Before paying into that escrow Alice/Bob would<br>
construct this signature. This idea is equally efficient in the common<br>
case, but larger and slower to verify in the alternative spend case.<br>
Setting up the signature requires additional interaction between<br>
participants and the resulting signature must be durably stored and<br>
couldn&#39;t just be recomputed using single-party information.<br>
<br>
I believe this construction will allow the largest possible anonymity<br>
set for fixed party smart contracts by making them look like the<br>
simplest possible payments. It accomplishes this without any overhead<br>
in the common case, invoking any sketchy or impractical techniques,<br>
requiring extra rounds of interaction between contract participants,<br>
and without requiring the durable storage of other data.<br>
<br>
<br>
[1] <a href=3D"https://eprint.iacr.org/2018/068" rel=3D"noreferrer" target=
=3D"_blank">https://eprint.iacr.org/2018/<wbr>068</a><br>
[2] <a href=3D"https://blockstream.com/sidechains.pdf" rel=3D"noreferrer" t=
arget=3D"_blank">https://blockstream.com/<wbr>sidechains.pdf</a> Appendix A=
<br>
______________________________<wbr>_________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
<wbr>linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.<wbr>org=
/mailman/listinfo/bitcoin-<wbr>dev</a><br>
</blockquote></div><br></div>

--089e0825821886de050563736b15--