[bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Gregory Maxwell via bitcoin-dev]

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

[Chris Belcher via bitcoin-dev]

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

Post by Gregory Maxwell via bitcoin-dev
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[Matt Corallo via bitcoin-dev]

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

Post by Gregory Maxwell via bitcoin-dev
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[Mark Friedenbach via bitcoin-dev]

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>

Post by Matt Corallo via bitcoin-dev
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
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[Matt Corallo via bitcoin-dev]

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

Post by Mark Friedenbach via bitcoin-dev
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
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
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
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

<https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>

_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[Gregory Maxwell via bitcoin-dev]

On Tue, Jan 23, 2018 at 9:23 PM, Matt Corallo via bitcoin-dev

Post by Matt Corallo via bitcoin-dev
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.

[Anthony Towns via bitcoin-dev]

Post by Gregory Maxwell via bitcoin-dev
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

[Gregory Maxwell via bitcoin-dev]

Post by Anthony Towns via bitcoin-dev
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).

[Anthony Towns via bitcoin-dev]

Post by Gregory Maxwell via bitcoin-dev

Post by Anthony Towns via bitcoin-dev
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...

Post by Gregory Maxwell via bitcoin-dev
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

[Gregory Maxwell via bitcoin-dev]

Post by Anthony Towns via bitcoin-dev
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.

Post by Anthony Towns via bitcoin-dev
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.

Post by Anthony Towns via bitcoin-dev
(It seems like using the point at infinity wouldn't work because

Indeed, that doesn't work.

Post by Anthony Towns via bitcoin-dev
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.

[Andrew Poelstra via bitcoin-dev]

Post by Gregory Maxwell via bitcoin-dev

Post by Anthony Towns via bitcoin-dev
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.

Post by Anthony Towns via bitcoin-dev
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.

Post by Anthony Towns via bitcoin-dev
(It seems like using the point at infinity wouldn't work because

Indeed, that doesn't work.

Post by Anthony Towns via bitcoin-dev
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

[Tim Ruffing via bitcoin-dev]

On Wed, 2018-01-24 at 01:52 +0000, Andrew Poelstra via bitcoin-dev

Post by Andrew Poelstra via bitcoin-dev

Post by Gregory Maxwell via bitcoin-dev
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

[Natanael via bitcoin-dev]

Den 23 jan. 2018 23:45 skrev "Gregory Maxwell via bitcoin-dev" <

Post by Anthony Towns via bitcoin-dev
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

Post by Anthony Towns via bitcoin-dev
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.

[Tim Ruffing via bitcoin-dev]

Post by Natanael via bitcoin-dev
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

[Natanael via bitcoin-dev]

Den 24 jan. 2018 16:38 skrev "Tim Ruffing via bitcoin-dev" <
bitcoin-***@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.

[Tim Ruffing via bitcoin-dev]

Post by Natanael via bitcoin-dev
That's not the type of attack I'm imagining. Both versions of your
scheme are essentially equivalent in terms of this attack.
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...

[Natanael via bitcoin-dev]

Den 25 jan. 2018 00:22 skrev "Tim Ruffing via bitcoin-dev" <
bitcoin-***@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.

[Tim Ruffing via bitcoin-dev]

(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

Den 25 jan. 2018 00:22 skrev "Tim Ruffing via bitcoin-dev" <bitcoin-d

Post by Tim Ruffing via bitcoin-dev
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.

[Russell O'Connor via bitcoin-dev]

On Tue, Jan 23, 2018 at 1:44 AM, Anthony Towns via bitcoin-dev <

Post by Gregory Maxwell via bitcoin-dev

Post by Gregory Maxwell via bitcoin-dev
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.

Post by Gregory Maxwell via bitcoin-dev
(This is the attack hardened pay-to-contract construction described in

[2])

Post by Gregory Maxwell via bitcoin-dev
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.

[Matt Corallo via bitcoin-dev]

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-***@lists.linuxfoundation.org> wrote:
-snip-

Post by Russell O'Connor via bitcoin-dev
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.

[Greg Sanders via bitcoin-dev]

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 <

Post by Gregory Maxwell via bitcoin-dev
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[Gregory Maxwell via bitcoin-dev]

Post by Gregory Maxwell via bitcoin-dev
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;]

[ZmnSCPxj via bitcoin-dev]

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

Post by Gregory Maxwell via bitcoin-dev
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
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev