[bitcoin-dev] Taproot: Privacy preserving switchable scripting

[bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Gregory Maxwell]

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

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Chris Belcher]

This sounds like a useful idea for improving the privacy of coinswap.
Traditionally coinswap mixing had an anonymity set related to the number
of multisig transactions being used on the blockchain. With the new tech
of Schnorr, MAST and now this Taproot, with sufficient adoption
coinswap's anonymity set could be much higher, potentially including
almost every other on-chain transaction.

[1] https://bitcointalk.org/index.php?topic=321228.0
[2] https://github.com/AdamISZ/CoinSwapCS

On 23/01/18 00:30, Gregory Maxwell via bitcoin-dev 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
> 

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Matt Corallo]

[-- Attachment #1: Type: text/plain, Size: 6042 bytes --]

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 <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

[-- Attachment #2: Type: text/html, Size: 6566 bytes --]

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Anthony Towns]

On Tue, Jan 23, 2018 at 12:30:06AM +0000, Gregory Maxwell via bitcoin-dev wrote:
> 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.

> 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].

Is this really intended as paying directly to a pubkey, instead of a
pubkey hash?

If so, isn't that a step backwards with regard to resistance to quantum
attacks against ECC?

Paying direct to pubkey doesn't seem quite enough to make pay-to-taproot
cheaper than p2wpkh: the extra 12 bytes in the scriptPubKey would need
you to reduce the witness by 48 bytes to maintain the weight, but I think
you'd only be saving 33 bytes by not having to reveal the pubkey, and
another 6-7 bytes by having a tighter signature encoding than DER. Still,
that's pretty close with a difference of only a couple of vbytes per
input by my count.

If it were "pay-to-taproot-hash", then presuming taproot hashes were 256
bit, then p2wpkh would be a full 12 vbytes cheaper due to the shorter
hash. That might make it hard to maximise the anonymity set. I suppose
a small penalty/discount could be added to align the economic incentives
though.

I wonder how this interacts with segwit versioning. I think you'd want
to have taproot be versioned overall so that you could cope with moving
to a new signing method (different curve, or something non-ECC based)
eventually, and segwit versioning will handle that already; but maybe
it would also be a good idea to also have "S" include a version, that
could be bumped to add new features to script, but left hidden within
the hash so that the fact you're using new (or old) features is only
revealed when it has to be.

Those nits aside, this seems great.

Cheers,
aj

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Gregory Maxwell]

On Tue, Jan 23, 2018 at 6:44 AM, Anthony Towns <aj@erisian.com.au> wrote:
> Is this really intended as paying directly to a pubkey, instead of a
> pubkey hash?
>
> If so, isn't that a step backwards with regard to resistance to quantum
> attacks against ECC?

You're reading too much into a description of the idea. It's not a BIP
or a spec; I tried to provide enough details to make the general idea
concrete. I didn't dive into details or optimizations (for example,
you can use this with a "no EC redemption path" by special casing
empty C as the point at infinity, and you'd have an output that was
indistinguishable until spend... yadda yadda).

Considering the considerable level of address reuse -- I recall prior
stats that a majority of circulating funds are on addresses that had
previously been used, on top of the general race limitations-- I am
now dubious to the idea that hashing provides any kind of meaningful
quantum resistance and somewhat regret introducing that meme to the
space in the first place. If we considered quantum resistance a
meaningful concern we should address that specifically.  --- so I
don't think that should be a factor that drives a decision here.

When collision resistance is needed (as I think it clearly is for
taproot) you don't get a space savings in the txout from hashing, so
there is an argument to use the public key directly at least... but
it's worth considering.  Direct SPK use is also adventitious for being
able to efficiently ZKP over the UTXO set, e.g. for private solvency
proofs, but it isn't absolutely mandatory for that (one can hash
inside the proof, but it's slower).

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Mark Friedenbach]

[-- Attachment #1: Type: text/plain, Size: 11710 bytes --]

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’s BIP 114, with some quibbling over details. Taproot is a clearly superior approach. But is it optimal? I don’t think we can claim that now. Optimality of these constructs isn’t 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’s 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’t 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’s 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’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’s 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’t think I’d personally be willing to bet that we found the optimal MAST structure in Greg’s 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’t 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/015537.html <https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015537.html>
[2] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/015029.html <https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/015029.html>

> On Jan 22, 2018, at 6:51 PM, Matt Corallo via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> 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 <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 <https://eprint.iacr.org/2018/068>
> [2] https://blockstream.com/sidechains.pdf <https://blockstream.com/sidechains.pdf> Appendix A
> 
> 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


[-- Attachment #2: Type: text/html, Size: 14177 bytes --]

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Greg Sanders]

[-- Attachment #1: Type: text/plain, Size: 6248 bytes --]

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
>

[-- Attachment #2: Type: text/html, Size: 7468 bytes --]

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Matt Corallo]

[-- Attachment #1: Type: text/plain, Size: 12811 bytes --]

The issue with that approach without support for the privacy-encouraging wrapper proposed by Greg here is that it encourages adoption halfway and destroys a lot of the value of the apparent-script monoculture for privacy preservation. Greg's proposal here doesn't change the format of any specific MAST implementation, but instead adds the privacy wrapper that I always felt was missing in existing proposals, without any real additional overhead in 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.

Matt

On January 23, 2018 2:39:37 PM UTC, Mark Friedenbach <mark@friedenbach.org> wrote:
>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’s BIP 114, with some quibbling over details. Taproot is a
>clearly superior approach. But is it optimal? I don’t think we can
>claim that now. Optimality of these constructs isn’t 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’s 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’t 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’s 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’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’s 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’t think I’d personally be willing to bet that we found
>the optimal MAST structure in Greg’s 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’t 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/015537.html
><https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015537.html>
>[2]
>https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/015029.html
><https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/015029.html>
>
>> On Jan 22, 2018, at 6:51 PM, Matt Corallo via bitcoin-dev
><bitcoin-dev@lists.linuxfoundation.org> wrote:
>> 
>> 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
><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
><https://eprint.iacr.org/2018/068>
>> [2] https://blockstream.com/sidechains.pdf
><https://blockstream.com/sidechains.pdf> Appendix A
>> 
>> 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

[-- Attachment #2: Type: text/html, Size: 15171 bytes --]

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Gregory Maxwell]

On Tue, Jan 23, 2018 at 9:23 PM, Matt Corallo via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> The issue with that approach without support for the privacy-encouraging
> wrapper proposed by Greg here is that it encourages adoption halfway and
> destroys a lot of the value of the apparent-script monoculture for privacy
> preservation. Greg's proposal here doesn't change the format of any specific
> MAST implementation, but instead adds the privacy wrapper that I always felt
> was missing in existing proposals, without any real additional overhead in
> 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.

Even if to someone who didn't care about anyone's privacy at all,
non-taproot is simply inefficient.  In the (I argue) overwhelmingly
common case of everyone-agrees simple hash based branching requires a
30% overhead to communicate the commitment to the untaken branch (and
worse in the case of extensive aggregation).  I don't think an
argument can be sustained in favor of that kind of communications
overhead.

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Anthony Towns]

On Tue, Jan 23, 2018 at 01:15:38PM +0000, Gregory Maxwell wrote:
> On Tue, Jan 23, 2018 at 6:44 AM, Anthony Towns <aj@erisian.com.au> wrote:
> > Is this really intended as paying directly to a pubkey, instead of a
> > pubkey hash?
> > If so, isn't that a step backwards with regard to resistance to quantum
> > attacks against ECC?
> Considering the considerable level of address reuse -- I recall prior
> stats that a majority of circulating funds are on addresses that had
> previously been used, on top of the general race limitations-- I am
> now dubious to the idea that hashing provides any kind of meaningful
> quantum resistance and somewhat regret introducing that meme to the
> space in the first place. If we considered quantum resistance a
> meaningful concern we should address that specifically.  --- so I
> don't think that should be a factor that drives a decision here.

Hmm, at least people can choose not to reuse addresses currently --
if everyone were using taproot and that didn't involve hashing the key,
there would be no way for individuals to hedge against quantum attacks
in case they're ever feasible, at least that I can see (well, without
moving their funds out of bitcoin anyway)?

Even "X + H(X|script)g" with X being a random point would end up
attackable, since that would almost always end up corresponding with a
valid public key that a successful attack could then find a private key
for.

(It seems like using the point at infinity wouldn't work because 
P = 0+H(0||S)g = H(0||S)g, so as soon as you tried to spend it via S,
someone watching the mempool would know H(0||S), which is the secret key
for P, and be able to spend it via the pubkey path -- no quantum crypto
needed. Or am I missing something?)

Also, if the people currently reusing addresses tend to cycle the funds
through fairly quickly anyway, they might be able to simply stop doing
that when quantum attacks start approaching feasibility. If funds are
being held in reused addresses over the long term, that would be more
of a problem though...

> When collision resistance is needed (as I think it clearly is for
> taproot) you don't get a space savings in the txout from hashing, so
> there is an argument to use the public key directly at least... but
> it's worth considering.  Direct SPK use is also adventitious for being
> able to efficiently ZKP over the UTXO set, e.g. for private solvency
> proofs, but it isn't absolutely mandatory for that (one can hash
> inside the proof, but it's slower).

Yeah, that was one of the assumptions for
http://www.jbonneau.com/doc/DBBCB15-CCS-provisions.pdf iirc. 

(Also, pretty sure you mean "advantageous", but at least I learnt a new
word today)

Cheers,
aj

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Gregory Maxwell]

On Tue, Jan 23, 2018 at 10:22 PM, Anthony Towns <aj@erisian.com.au> wrote:
> Hmm, at least people can choose not to reuse addresses currently --
> if everyone were using taproot and that didn't involve hashing the key,

Can you show me a model of quantum computation that is conjectured to
be able to solve the discrete log problem but which would take longer
than fractions of a second to do so? Quantum computation has to occur
within the coherence lifetime of the system.

> way for individuals to hedge against quantum attacks in case they're ever feasible, at least that I can see (well, without moving their funds out of bitcoin anyway)?

By using scriptpubkeys with actual security against quantum computers
instead of snake-oil.

> (It seems like using the point at infinity wouldn't work because

Indeed, that doesn't work.

> that when quantum attacks start approaching feasibility. If funds are
> being held in reused addresses over the long term, that would be more

They are. But I don't believe that is relevant; the attacker would
simply steal the coins on spend.

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Andrew Poelstra]

[-- Attachment #1: Type: text/plain, Size: 1843 bytes --]

On Tue, Jan 23, 2018 at 10:45:06PM +0000, Gregory Maxwell via bitcoin-dev wrote:
> On Tue, Jan 23, 2018 at 10:22 PM, Anthony Towns <aj@erisian.com.au> wrote:
> > Hmm, at least people can choose not to reuse addresses currently --
> > if everyone were using taproot and that didn't involve hashing the key,
> 
> Can you show me a model of quantum computation that is conjectured to
> be able to solve the discrete log problem but which would take longer
> than fractions of a second to do so? Quantum computation has to occur
> within the coherence lifetime of the system.
> 
> > way for individuals to hedge against quantum attacks in case they're ever feasible, at least that I can see (well, without moving their funds out of bitcoin anyway)?
> 
> By using scriptpubkeys with actual security against quantum computers
> instead of snake-oil.
> 
> > (It seems like using the point at infinity wouldn't work because
> 
> Indeed, that doesn't work.
> 
> > that when quantum attacks start approaching feasibility. If funds are
> > being held in reused addresses over the long term, that would be more
> 
> They are. But I don't believe that is relevant; the attacker would
> simply steal the coins on spend.


Then the system would need to be hardforked to allow spending through a
quantum-resistant ZKP of knowledge of the hashed public key. I expect
that in a post-quantum world there will be demand for such a fork,
especially if we came into such a world through surprise evidence of
a discrete log break.

-- 
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
       --Joanna Newsom


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 455 bytes --]

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Tim Ruffing]

On Wed, 2018-01-24 at 01:52 +0000, Andrew Poelstra via bitcoin-dev
wrote:
> 
> > They are. But I don't believe that is relevant; the attacker would
> > simply steal the coins on spend.
> 
> 
> Then the system would need to be hardforked to allow spending through
> a
> quantum-resistant ZKP of knowledge of the hashed public key. I expect
> that in a post-quantum world there will be demand for such a fork,
> especially if we came into such a world through surprise evidence of
> a discrete log break.
> 

There are simpler ways using consensus / waiting instead of zero-
knowledge, e.g., 

1. Include H(classic_pk, tx) to blockchain, wait until confirmed.
2. Reveal classic_pk, tx

This is taken from my tweet [1] but now I realize that these are
basically Guy Fawkes "signatures" [2]. Joseph Bonneau and Andrew Miller
 [3] had the idea to use this for cryptocurrency without asymmetric
cryptography.

Best,
Tim

[1] https://twitter.com/real_or_random/status/948226830166786048
[2] https://www.cl.cam.ac.uk/~rja14/Papers/fawkes.pdf
[3] http://www.jbonneau.com/doc/BM14-SPW-fawkescoin.pdf

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Natanael]

[-- Attachment #1: Type: text/plain, Size: 5418 bytes --]

Den 23 jan. 2018 23:45 skrev "Gregory Maxwell via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org>:

On Tue, Jan 23, 2018 at 10:22 PM, Anthony Towns <aj@erisian.com.au> wrote:
> Hmm, at least people can choose not to reuse addresses currently --
> if everyone were using taproot and that didn't involve hashing the key,

Can you show me a model of quantum computation that is conjectured to
be able to solve the discrete log problem but which would take longer
than fractions of a second to do so? Quantum computation has to occur
within the coherence lifetime of the system.


Quantum computers works like randomized black boxes, you run them in many
cycles with a certain probability of getting the right answer.

The trick to them is that they bias the probabilities of their qubits to
read out the correct answer *more often than at random*, for many classes
of problems. You (likely) won't get the correct answer immediately.

https://en.wikipedia.org/wiki/Quantum_computing

Quoting Wikipedia:

> An algorithm is composed of a fixed sequence of quantum logic gates and a
problem is encoded by setting the initial values of the qubits, similar to
how a classical computer works. The calculation usually ends with a
measurement, collapsing the system of qubits into one of the 2 n
{\displaystyle 2^{n}} 2^{n} pure states, where each qubit is zero or one,
decomposing into a classical state. The outcome can therefore be at most n
{\displaystyle n} n classical bits of information (or, if the algorithm did
not end with a measurement, the result is an unobserved quantum state).
Quantum algorithms are often probabilistic, in that they provide the
correct solution only with a certain known probability.

A non programmed QC is essentially an RNG driven by quantum effects. You
just get random bits.

A programmed one will need to run the and program over and over until you
can derive the correct answer from one of its outputs. How fast this goes
depends on the problem and the algorithm.

Most people here have heard of Grover's algorithm, it would crack a
symmetric 256 bit key in approximately 2^128 QC cycles - completely
impractical. Shor's algorithm is the dangerous one for ECC since it cracks
current keys at "practical" speeds.

https://eprint.iacr.org/2017/598 - resource estimates, in terms of size of
the QC. Does not address implementation speed.

I can't seem to find specific details, but I remember having seen estimates
of around 2^40 cycles in practical implementations for 256 bit ECC (this
assumes use error correction schemes, QC machines with small some
imperfections, and more). Unfortunately I can't find a source for this
estimate. I've seen lower estimates too, but they seem entirely
theoretical.

Read-out time for QC:s is indeed insignificant, in terms of measuring the
state of the qubits after a complete cycle.

Programming time, time to prepared for readout, reset, reprogramming, etc,
that will all take a little longer. In particular with more qubits
involved, since they all need to be in superposition and be coherent at
some point. Also, you still have to parse all the different outputs (on a
classical computer) to find your answer among them.
Very very optimistic cycle speeds are in the GHz range, and then that's
still on the order of ~15 minutes for 2^40 cycles. Since we don't even have
a proper general purpose QC yet, nor one with usable amounts of qubits, we
don't even know if we can make them run at a cycle per second, or per
minute...

However if somebody *does* build a fast QC that's nearly ideal, then
Bitcoin's typical use of ECC would be in immediate danger. The most
optimistic QC plausible would indeed be able to crack keys in under a
minute. But my own wild guess is that for the next few decades none will be
faster than a runtime measured in weeks for cracking keys.

---

Sidenote, I'm strongly in favor of implementing early support for the
Fawkes scheme mentioned previously.

We could even patch it on top of classical transactions - you can only
break ECC with a known public key, so just commit to the signed transaction
into the blockchain before publishing it. Then afterwards you publish the
transaction itself, with a reference to the commitment. That transaction
can then be assumed legit simply because there was no room to crack the key
before the commitment, and the transaction matches the commitment.

Never reuse keys, and you're safe against QC:s.

Sidenote: There's a risk here with interception, insertion of a new
commitment and getting the new transaction into the blockchain first.
However, I would suggest a mining policy here were two known conflicting
transactions with commitments are resolved such that the one with the
oldest commitment wins. How to address detection of conflicting
transactions with commitments older than confirmed transactions isn't
obvious. Some of these may be fully intentional by the original owner, such
as a regretted transaction.

Another sidenote: HD wallets with hash based hardened derivation should
also be safe in various circumstances, near completely safe in the case
where they're defined such that knowing an individual private key, which is
not the root key,  is not enough to derive any other in your wallet.
HD schemes that only prevent derivation of parent keypairs in the tree
would require that you never use a key derived from another already used or
published public key.

[-- Attachment #2: Type: text/html, Size: 7301 bytes --]

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Tim Ruffing]

On Wed, 2018-01-24 at 13:51 +0100, Natanael via bitcoin-dev wrote:
> Sidenote: There's a risk here with interception, insertion of a new
> commitment and getting the new transaction into the blockchain first.
> However, I would suggest a mining policy here were two known
> conflicting transactions with commitments are resolved such that the
> one with the oldest commitment wins. How to address detection of
> conflicting transactions with commitments older than confirmed
> transactions isn't obvious. Some of these may be fully intentional by
> the original owner, such as a regretted transaction.

Okay, I think my proposal was wrong...

This looks better (feel free to break again):
1. Commit (H(classic_pk, tx), tx) to the blockchain, wait until confirmed
2. Reveal classic_pk in the blockchain

Then the tx in the first valid commitment wins. If the attacker
intercepts classic_pk, it won't help him. He cannot create the first
valid commitment, because it is created already. (The reason is that
the decommitment is canonical now; for all commitments, the
decommitment is just classic_pk.)

By the way, maybe I'm stating the obvious but Taproot (or similar) is
indeed very nice for outputs generated in the future: You can have a
path for a classical signature scheme and a path for a quantum-secure
scheme.

Best,
Tim

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Natanael]

[-- Attachment #1: Type: text/plain, Size: 3908 bytes --]

Den 24 jan. 2018 16:38 skrev "Tim Ruffing via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org>:

Okay, I think my proposal was wrong...

This looks better (feel free to break again):
1. Commit (H(classic_pk, tx), tx) to the blockchain, wait until confirmed
2. Reveal classic_pk in the blockchain

Then the tx in the first valid commitment wins. If the attacker
intercepts classic_pk, it won't help him. He cannot create the first
valid commitment, because it is created already. (The reason is that
the decommitment is canonical now; for all commitments, the
decommitment is just classic_pk.)


That's not the type of attack I'm imagining. Both versions of your scheme
are essentially equivalent in terms of this attack.

Intended steps:
1: You publish a hash commitment.
2: The hash ends up in the blockchain.
3: You publish the transaction itself, and it matches the hash commitment.
4: Because it matches, miners includes it. It's now in the blockchain.

Attack:
1: You publish a hash commitment.
2: The hash ends up the blockchain.
3: You publish the transaction itself, it matches the hash commitment.
4: The attacker mess with the network somehow to prevent your transaction
from reaching the miners.
5: The attacker cracks your keypair, and makes his own commitment hash for
his own theft transaction.
6: Once that commitment is in the blockchain, he publishes his own theft
transaction.
7: The attacker's theft transaction gets into the blockchain.
8 (optionally): The miners finally see your original transaction with the
older commitment, but now the theft transaction can't be undone. There's
nothing to do about it, nor a way to know if it's intentional or not.
Anybody not verifying commitments only sees a doublespend attempt.

---

More speculation, not really a serious proposal:

I can imagine one way to reduce the probability of success for the attack
by publishing encrypted transactions as the commitment, to then publish the
key - the effect of this is that the key is easier to propagate quickly
across the network than a full transaction, making it harder to succeed
with a network based attack. This naive version by itself is however a
major DoS vector against the network.

You could, in some kind of fork, redefine how blocks are processed such
that you can prune all encrypted transactions that have not had the key
published within X blocks. The validation rules would work such that to
publish the key for an encrypted transaction in a new block, that
transaction must both be recent enough, be valid by itself, and also not
conflict with any other existing plaintext / decrypted transactions in the
blockchain.

Blocks wouldn't necessarily even need to include the encrypted transactions
during propagation. This works because encrypted transactions have zero
effect until the key is published. In this case you'd effectively be
required to publish your encrypted transaction twice to ensure the raw data
isn't lost, once to get into a block and again together with the key to get
it settled.

Since miners will likely keep at least the most recent encrypted
transactions cached to speed up validation, this is faster to settle than
to publish the committed transaction as mentioned in the beginning. This
increases your chances to get your key into the blockchain to settle your
transaction before the attacker completes his attack, versus pushing a full
transaction that miners haven't seen before.

This version would still allow DoS against miners caching all encrypted
transactions. However, if efficient Zero-knowledge proofs became practical
then you can use one to prove your encrypted transaction valid, even
against the UTXO set and in terms of not colliding with existing
commitments - in this case the DoS attack properties are nearly identical
to standard transactions.
If you want to change a committed transaction, you'd need to let the
commitment expire.

[-- Attachment #2: Type: text/html, Size: 5596 bytes --]

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Tim Ruffing]

On Wed, 2018-01-24 at 19:51 +0100, Natanael wrote:
> 
> That's not the type of attack I'm imagining. Both versions of your
> scheme are essentially equivalent in terms of this attack. 
> 
> Intended steps: 
> 1: You publish a hash commitment. 
> 2: The hash ends up in the blockchain. 
> 3: You publish the transaction itself, and it matches the hash
> commitment. 
> 4: Because it matches, miners includes it. It's now in the
> blockchain. 

I think you misread my second proposal. The first step is not only to
publish the hash but to publish a *pair* consisting of the hash and the
transaction.

If the attacker changes the transaction on the wire, the user does not
care and will try again.

By the way: As described here, everybody could do this first step and
flood the blockchain with it. We cannot immediately subtract a fee,
because it's not clear that some transaction will take place at all. So
we need to take the fee from somewhere else or do something else to
prevent spam. But that's entirely different issue...

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Natanael]

[-- Attachment #1: Type: text/plain, Size: 1954 bytes --]

Den 25 jan. 2018 00:22 skrev "Tim Ruffing via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org>:


I think you misread my second proposal. The first step is not only to
publish the hash but to publish a *pair* consisting of the hash and the
transaction.

If the attacker changes the transaction on the wire, the user does not
care and will try again.


I guess I assumed you meant it otherwise because I didn't assume you
intended a commitment to the full transaction just without the asymmetric
key material.

You could treat it the same way as in my suggestion, let it expire and
prune it if the key material isn't published in time.

However... A sufficiently powerful attacker can deploy as soon as he sees
your published signature and key, delay its propagation to the miners,
force expiration and then *still* repeat the attack with his own forgery.

Honestly, as long as we need to allow any form of expiry + relying on
publication of the vulnerable algorithms result for verification, I think
the weakness will remain.

No expiration hurts in multiple ways like via DoS, or by locking in
potentially wrong (or straight up malicious) transactions.

---

There's one way out, I believe, which is quantum safe Zero-knowledge
proofs. Currently STARK:s are one variant presumed quantum safe. It would
be used to completely substitute the publication of the public key and
signatures, and this way we don't even need two-step commitments.

It does however likely require a hardfork to apply to old transactions. (I
can imagine an extension block type softfork method, in which case old
UTXO:s get locked on the mainchain to create equivalent valued extension
block funds.)

Without practical ZKP,  and presuming no powerful QC attackers with the
ability to control the network (basically NSA level attackers), I do think
the Fawkes signature scheme is sufficient. Quantum attacks are likely to be
very expensive anyway, for the foreseeable future.

[-- Attachment #2: Type: text/html, Size: 2812 bytes --]

[bitcoin-dev] Recovery of old UTXOs in a post-quantum world

[Tim Ruffing]

(changing the subject... ;))

My proposal does not include any form of expiration, so I don't see how
it should be vulnerable to the described attack.

To make this a little bit more detailed:

The user has one or more single standard UTXOs all with ECDSA public
key classic_pk and thus address SHA256(RIPEMD160((classic_pk)). The
corresponding secret key is classic_sk. Let MAC be a quantum-secure
message-authentication code, e.g., MAC(k,x)=H(k||x) for a suitable hash
function, e.g, BLAKE2 or SHA3.

The idea is to (ab)use the public key classic_pk as a key for the MAC. 

To spend an UTXO with a transaction tx, the user does the following:
   1. Create and publish a "transaction" c that references the address
      SHA256(RIPEMD160((classic_pk)) and contains the following data: 
      MAC(classic_pk,tx))||tx
   2. Wait until c is confirmed. (If it does not confirm, send it again as
      usual).
   3. Create and publish a "transaction" d with the following data:
      classic_pk||Sign(classic_sk, tx)

Consensus rules:
A transaction d=classic_pk||sig spends all UTXOs with
address SHA256(RIPEMD160(classic_pk)), applying the effects of tx, if
there exists a transaction c=mac||tx in the blockchain such that 
   1. c is the first transaction (among all referencing the address) in
      the blockchain where mac is a valid MAC for message tx under correct
      key classic_pk
   2. sig is valid ECDSA signature over tx under public key classic_pk

c-transactions never expire. 

If the user has not published classic_pk before, this should be secure
against quantum attackers:
Before step 2, the MAC key k=classic_pk is only known to the user. So
the only valid c that the attacker can produce has the real transaction
tx, because a different transaction tx' requires the attacker to forge
the MAC. Since the user waits for confirmation, the first c in the
blockchain fulfilling conditions 1 and 2 has been created by the user.

Even if classic_pk is known, this is no less secure than "classic
spending", because we require an ECDSA signature on tx.

I'm pretty confident that I'm not overlooking an obvious attack. If I'm
wrong then please describe exactly the steps of the user and the
attacker. 

Best,
Tim 


On Thu, 2018-01-25 at 01:09 +0100, Natanael wrote:
> 
> Den 25 jan. 2018 00:22 skrev "Tim Ruffing via bitcoin-dev" <bitcoin-d
> ev@lists.linuxfoundation.org>:
> > I think you misread my second proposal. The first step is not only
> > to
> > publish the hash but to publish a *pair* consisting of the hash and
> > the
> > transaction.
> > 
> > If the attacker changes the transaction on the wire, the user does
> > not
> > care and will try again.
> 
> I guess I assumed you meant it otherwise because I didn't assume you
> intended a commitment to the full transaction just without the
> asymmetric key material. 
> 
> You could treat it the same way as in my suggestion, let it expire
> and prune it if the key material isn't published in time. 
> 
> However... A sufficiently powerful attacker can deploy as soon as he
> sees your published signature and key, delay its propagation to the
> miners, force expiration and then *still* repeat the attack with his
> own forgery. 
> 
> Honestly, as long as we need to allow any form of expiry + relying on
> publication of the vulnerable algorithms result for verification, I
> think the weakness will remain. 
> 
> No expiration hurts in multiple ways like via DoS, or by locking in
> potentially wrong (or straight up malicious) transactions.
> 
> ---
> 
> There's one way out, I believe, which is quantum safe Zero-knowledge
> proofs. Currently STARK:s are one variant presumed quantum safe. It
> would be used to completely substitute the publication of the public
> key and signatures, and this way we don't even need two-step
> commitments. 
> 
> It does however likely require a hardfork to apply to old
> transactions. (I can imagine an extension block type softfork method,
> in which case old UTXO:s get locked on the mainchain to create
> equivalent valued extension block funds.)
> 
> Without practical ZKP,  and presuming no powerful QC attackers with
> the ability to control the network (basically NSA level attackers), I
> do think the Fawkes signature scheme is sufficient. Quantum attacks
> are likely to be very expensive anyway, for the foreseeable future. 

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Gregory Maxwell]

On Tue, Jan 23, 2018 at 12:30 AM, Gregory Maxwell <greg@xiph.org> wrote:
> 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.

Keeping in mind that a single public point can stand in for any
monotone function of public keys, a taproot branch is only needed for
accountability (being able to tell from public data which branches
were used) or when conditions other than public keys are required e.g.
CSV + a monotone function of keys.

I believe that with scriptless-scripts most of hash preimages can be
accomplished without an actual hash pre-image condition.

Are there other simple and very useful/general preconditions that
would be useful ANDed with a monotone function of public keys like is
the case for CSV?

I ask because recursive taproot by itself isn't very interesting,
since (other than accountability) there is no gain to not just merging
the alternative, but if there are additional conditions then it can be
useful. E.g.

[pubkey]
      \-[pubkey]&&CSV
             \-[fancy script]

So it might make sense to support a taproot construction that can
nest, where interior nested keys have a CSV/CLTV predicate. But are
there other simple predicates that cover a lot of cases?


[Aside: _please_ change the subject lines for further discussion about
quantum computers;]

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 2519 bytes --]

On Tue, Jan 23, 2018 at 1:44 AM, Anthony Towns via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Tue, Jan 23, 2018 at 12:30:06AM +0000, Gregory Maxwell via bitcoin-dev
> wrote:
> > 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.
>
> > 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].
>
> Is this really intended as paying directly to a pubkey, instead of a
> pubkey hash?
>
> If so, isn't that a step backwards with regard to resistance to quantum
> attacks against ECC?
>
> Paying direct to pubkey doesn't seem quite enough to make pay-to-taproot
> cheaper than p2wpkh: the extra 12 bytes in the scriptPubKey would need
> you to reduce the witness by 48 bytes to maintain the weight, but I think
> you'd only be saving 33 bytes by not having to reveal the pubkey, and
> another 6-7 bytes by having a tighter signature encoding than DER. Still,
> that's pretty close with a difference of only a couple of vbytes per
> input by my count.
>

I've been thinking about your comment, and I think your concern can be
addressed.  Taproot would almost certainly be deployed in conjunction with
cross-input signature aggregation.  Because aggregation doesn't work with
ECDSA, only those signatures using Taproot and other Schnorr signatures
would be available for aggregation.  Just having the ability to support
cross-input signature aggregation may be motivation enough for ordinary
pub-key users to switch to Taproot.  However, there is more.

Cross-input signature aggregation probably requires a new field to be added
to the P2P transaction structure to hold the aggregated signature, since
there isn't really a good place to put it in the existing structure (there
are games you can play to make it fit, but I think it is worthwhile).  The
obvious way add block commitments to a new tx field is via the witness
reserved value mechanism present in BIP 141.  At this point I think there
will be some leeway to adjust the discount on the weight of this new
aggregated signature tx field so that even a single input taproot using the
aggregated signature system (here an aggregation of 1 signature) ends up no
more expensive than a single input segwit P2WPKH.

[-- Attachment #2: Type: text/html, Size: 3073 bytes --]

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Matt Corallo]

Gah, please no. I see no material reason why cross-input signature aggregation shouldn't have the signatures in the first n-1 inputs replaced with something like a single-byte push where a signature is required to indicate aggregation, and the combined signature in the last input at whatever position the signature is required.

On January 27, 2018 5:07:25 PM UTC, Russell O'Connor via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
-snip-
>Cross-input signature aggregation probably requires a new field to be
>added
>to the P2P transaction structure to hold the aggregated signature,
>since
>there isn't really a good place to put it in the existing structure
>(there
>are games you can play to make it fit, but I think it is worthwhile). 
>The
>obvious way add block commitments to a new tx field is via the witness
>reserved value mechanism present in BIP 141.  At this point I think
>there
>will be some leeway to adjust the discount on the weight of this new
>aggregated signature tx field so that even a single input taproot using
>the
>aggregated signature system (here an aggregation of 1 signature) ends
>up no
>more expensive than a single input segwit P2WPKH.

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[ZmnSCPxj]

Good morning Greg,

I am probably being exceedingly naive, but I would like to compare Taproot to a generalization of funding transactions.

For instance, CoinSwapCS:

1.  It uses an HTLC in an off-chain transaction, and a funding transaction TX0 whose output is a "simple" 2-of-2.
2.  The HTLC tx spends this 2-of-2.
3.  If a branch of the HTLC succeeds, the parties contact each other and create a replacement of the (unconfirmed and unbroadcasted but signed) HTLC tx that assigns the funds to the correct owners.
4.  If the above step fails, individual parties can in isolation publish the HTLC tx and provide its requirements.

Both of #3 and #4 above, appear to me naively as similar to the two "top" cases of Taproot, i.e. either C is signed by all parties, or S is revealed and fulfilled.

The important bits of this "generalized funding transaction" pattern is:

1. The contract that enforces correct behavior spends an unsigned and unbroadcasted funding transaction output (which requires N-of-N).
2. The enforcement contract is signed first by all parties before the funding transaction is signed by anybody.  This is possible due to SegWit.
3.  Then, when all parties are sure they have the fully-signed smart contract, the initial funding transaction is signed and broadcast and confirmed.
4.  When the condition that the contract requires is achieved, then the parties contact each other and try to jointly create a simpler transaction that spends the funding transaction directly to whoever gets the money in the correct proportion.  This avoids publishing the smart contract onchain, and looks like an ordinary N-of-N spend.
5.  If they fail to get all required signatures for any reason, any party can publish the enforcement contract transaction and subsequently fulfill its conditions in another transaction.

Admittedly, Taproot if added to the consensus would reduce the number of transactions by 1 in the "S is revealed" case.
But the "generalized funding transaction" pattern is already possible today, and MuSig (to my limited understanding) can be used to make it indistinguishable from 1-of-1 (so, possibly, make it P2WPKH?).


(I am probably neglecting something very simple and direct, however...)

Regards,
ZmnSCPxj

-------- Original Message --------
 On January 23, 2018 8:30 AM, 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
>

[bitcoin-dev] Generalised taproot

[Anthony Towns]

On Fri, Jan 26, 2018 at 09:34:39PM +0000, Gregory Maxwell via bitcoin-dev wrote:
> I ask because recursive taproot by itself isn't very interesting,
> since (other than accountability) there is no gain to not just merging
> the alternative, but if there are additional conditions then it can be
> useful. E.g.
> 
> [pubkey]
>       \-[pubkey]&&CSV
>              \-[fancy script]

I think it's possible to do recursive taproot in this manner in a
neat way, using Pedersen Commitments. 

(Background: A Pedersen commitment uses a second generator in the curve,
and rather than constructing a point from a single secret, like A=a*G,
it constructs a point from two secrets, like C=a*G+b*G2, and finding a
different c,d such that C=c*G+d*G2 gives you the discrete log of G2)

So combining this with the taproot structure gives an equation like:

  P = a*G + s*G2 + H(a*G+s*G2, Q)*G

If you take "a" to be a private key (so A=a*G is the corresponding
pubkey), "s" to be (the hash of) a set of additional conditions for
spending with the pubkey, and "Q" to be an alternative method of spending,
you get a recursive taproot construction.

To spend "P", you would either:

  - sign with P directly (only possible if s=0, indicating there are no
    additional conditions to satisfy when spending with this key)

  - reveal the extra conditions you have to satisfy (s), satisfy
    them, and provide a signature the key "P-s*G2"

  - reveal the points "a*G+s*G2" and "Q", and satisfy "Q"

If you structure the conditions as:

  (pubkey A) |
    (pubkey B & script x) |
      (pubkey C & script y) |
        (merkle tree of scripts, root=z)

Then you can construct a pubkey point as:

   D' = z
   C' = C + y*G2 + H(C+y*G2, D')*G
   B' = B + x*G2 + H(B+x*G2, C')*G
   A' = A + H(A, B')*G

and if you want to spend something with a scriptPubKey of A', you could
use:

   (1) plain signature with privkey = a+H(A,B')

   (2) reveal [A, B'], reveal [x], provide [witness(x)],
       signature with privkey = b+H(B+x*G2,C')

   (3) reveal [A, B'], reveal [B+x*G2, C'], reveal [y], provide
       [witness(y)], signature with privkey = c+H(C+y*G2, D')

   (4) reveal [A, B'], reveal [B+x*G2, C'], reveal [C+y*G2],
       reveal [script], reveal merkle path from script to z,
       provide [witness(script)].

That way, you can keep two sets of things secret:

 - until you hit the merkle-tree of scripts, you don't reveal
   whether there are or aren't any lower layers

 - you don't reveal the conditions corresponding with any of the
   keys, other than the key you're spending with

This is as (space) efficient as basic taproot:

  taproot: P + H(P, [Q CHECKSIGVERIFY cond]) 
  witness:
    (1) sig(P)
    (2) P [Q CHECKSIGVERIFY cond] sig(Q) witness(cond)

becomes:

  g'root: P + H(P, Q + cond*G2)*G
  witness:
    (1) sig(P+H(..)*G)
    (2) P Q sig(Q) cond witness(cond)

[0]

It's potentially more efficient for cases where the taproot assumption
doesn't hold, and the common case is to spend with conditions:

  g'root: P + cond*G2 + H(P+cond*G2, Q)*G
  witness:
    (1) cond witness(cond) sig(P+H(..)*G)
    (2) [P+cond*G2] Q sig(Q)

  taproot: Q + H(Q, [P checksig cond])*G
    (1) Q [P CHECKSIG cond] [sig(P) witness(cond)]   (64 bytes overhead)
    (2) sig(Q+H(..)*G)                               (64 bytes saved)

It's also potentially more efficient than using a merkle tree with taproot
when there are three spending paths, and one merkle branch is more likely
than the other, eg, if the conditions are "sign with A", or "sign with
B and satisfy x", or (least likely) "sign with C and satisfy y":

Let s = [B CHECKSIGVERIFY x], t = [C CHECKSIGVERIFY y], r = H(H(s),H(t))

 taproot+MAST: A + H(A,r)*G
  (1t) sig(A+H(..)*G)
  (2t) A,s,H(t),sig(B),witness(x)
  (3t) A,t,H(s),sig(C),witness(y)

 g'root: A', where:
           C' = C + y*G2
           B' = B + x*G2 + H(B+x*G2,C')*G
           A' = A + H(A,B')*G
  (1g) sig(A+H(..)*G)
  (2g) A B' x sig(B'-x*G2) witness(x)
  (3g) A B' [B+x*G2] C' y sig(C) witness(y)

(1t) and (1g) are the same; (2t) is about 32B larger than (2g) because
s=[B x], and  (3t) is about 32B smaller than (3g) because the g'root
descent reveals two additional points.

(As far as deployment goes, I think it makes sense to get an initial
schnorr/taproot/mast deployment out first, and add graftroot/aggregation
later. My feeling is there's no great urgency for generalised taproot, so
it would make sense to keep doing schnorr/taproot/mast for now, take time
analysing generalised taproot, and if it seems sane and useful, aim to
enable it in a later phase, eg at the same time as graftroot/aggregation)

Cheers,
aj

[0] My inital name for these was "MAST-ended sc'roots", since it
    combines "taproot" and "scripts" and something MAST-like but only
    at the very end, but I was warned that the Mimblewimble folks have
    vast teams monitoring for Harry Potter references and will DMCA me,
    which I assume stands for "Dementors, Ministry, Cruciatus and Avada
    kedavra"... So I'm abbreviating generalised taproot as "g'root"
    instead. After all, what's the worst the Marvel guys could do?

Re: [bitcoin-dev] Generalised taproot

[Pieter Wuille]

On Thu, Jul 12, 2018 at 6:52 PM Anthony Towns via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> On Fri, Jan 26, 2018 at 09:34:39PM +0000, Gregory Maxwell via bitcoin-dev wrote:
> > [pubkey]
> >       \-[pubkey]&&CSV
> >              \-[fancy script]
>
> I think it's possible to do recursive taproot in this manner in a
> neat way, using Pedersen Commitments.
>
> (Background: A Pedersen commitment uses a second generator in the curve,
> and rather than constructing a point from a single secret, like A=a*G,
> it constructs a point from two secrets, like C=a*G+b*G2, and finding a
> different c,d such that C=c*G+d*G2 gives you the discrete log of G2)
>
> So combining this with the taproot structure gives an equation like:
>
>   P = a*G + s*G2 + H(a*G+s*G2, Q)*G
>
> If you take "a" to be a private key (so A=a*G is the corresponding
> pubkey), "s" to be (the hash of) a set of additional conditions for
> spending with the pubkey, and "Q" to be an alternative method of spending,
> you get a recursive taproot construction.

I think this is a very neat construction, and has advantages beyond
solving the recursive-taproot-without-revealing-intermediary-scripts problem
(which is useful, but I would consider a stretch goal at best).

To summarize, this is my understanding of g'root:
* A spending condition is a policy of the form "sign with public key A
  and additionally satsify script S". Such a condition is associated with
  the point P = A + s*G2 (where G2 is a second independent generator for the
  curve, and s=H(S)). To satisfy such a condition, you reveal S, provide
  inputs that satisfy S, together with a signature for public key (P - s*G2).
  We'll call A the companion key of spending condition P (as opposed to other
  public keys which may appear in the script S).
* A scriptPubKey (or redeemScript in case of P2SH) can either be a spending
  condition P directly, or a P2C derivation (using P + H(P,Q)G) of a spending
  condition and an alternative. That alternative can either be another P2C
  derivation ("recursive Taproot"), or a Merkle tree of disjunct spending
  conditions.

This is elegant in that it removes the distinction between pay-to-pubkey and
pay-to-script constructions; every point becomes the representation of both.
As long as every script(branch) requires at least one pubkey check, it
comes at no cost (neither witness size or computational).

However, I think it also offers an easy way to construct a softfork-safe
cross-input aggregation system (discussed here before:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015838.html).

Essentially what's done here is extracting one key out of every spending
condition, given it a special place (the companion key) in the execution
structure - rather than being part of freeform script opcodes - and made it
cheaper to satisfy (as no pubkey needs to be revealed for it). This makes sense,
as we can assume that every (secure) script contains at least one CHECKSIG or
semantically equivalent operation, and with Schnorr multisignatures, can often
expect that to be just one key representing the set of all those who have to
sign.

However, it also means we could simply restrict a future cross-input signature
aggregation system to only apply to the set of these companion keys (one per
input). They are not subject to potential changes to the scripting language, as
they're outside of that. Under the assumption that most spending policies can be
encoded s a tractably-sized set of disjunct conditions, each with just a single
fixed set of public keys, the companion keys actually embody all public keys
involved in a transaction.

> (As far as deployment goes, I think it makes sense to get an initial
> schnorr/taproot/mast deployment out first, and add graftroot/aggregation
> later. My feeling is there's no great urgency for generalised taproot, so
> it would make sense to keep doing schnorr/taproot/mast for now, take time
> analysing generalised taproot, and if it seems sane and useful, aim to
> enable it in a later phase, eg at the same time as graftroot/aggregation)

Agree.

> [0] My inital name for these was "MAST-ended sc'roots", since it
>     combines "taproot" and "scripts" and something MAST-like but only
>     at the very end, but I was warned that the Mimblewimble folks have
>     vast teams monitoring for Harry Potter references and will DMCA me,
>     which I assume stands for "Dementors, Ministry, Cruciatus and Avada
>     kedavra"... So I'm abbreviating generalised taproot as "g'root"
>     instead. After all, what's the worst the Marvel guys could do?

Sebastian Geisler, Glenn Willen, and I had an hour long discussion to come up
with a name for the privileged key in g'root, but unfortunately had to resort
to the Valve universe instead to find "companion key"...

Cheers,

-- 
Pieter