Taproot: Privacy preserving switchable scripting
25 messages, 23 Jan to 24 Oct 2018. Started by Gregory Maxwell.
Gregory Maxwell (5), Tim Ruffing (4), Matt Corallo (3), Anthony Towns (3), Natanael (3), Chris Belcher, Mark F, Greg Sanders, +4 more
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
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:
Quoted text (109 lines)
> 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 >
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:
Quoted text (112 lines)
>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
On Tue, Jan 23, 2018 at 12:30:06AM +0000, Gregory Maxwell via bitcoin-dev wrote:
Quoted text (6 lines)
> 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
On Tue, Jan 23, 2018 at 6:44 AM, Anthony Towns <aj@erisian•com•au> wrote:
Quoted text (5 lines)
> 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).
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>
Quoted text (121 lines)
> 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
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:
Quoted text (111 lines)
> 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 >
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:
Quoted text (228 lines)
>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
On Tue, Jan 23, 2018 at 9:23 PM, Matt Corallo via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (11 lines)
> 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.
On Tue, Jan 23, 2018 at 01:15:38PM +0000, Gregory Maxwell wrote:
Quoted text (13 lines)
> 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...
Quoted text (7 lines)
> 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
On Tue, Jan 23, 2018 at 10:22 PM, Anthony Towns <aj@erisian•com•au> wrote:
Quoted text (2 lines)
> 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.
Quoted text (1 line)
> 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.
Quoted text (1 line)
> (It seems like using the point at infinity wouldn't work because
Indeed, that doesn't work.
Quoted text (2 lines)
> 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.
On Tue, Jan 23, 2018 at 10:45:06PM +0000, Gregory Maxwell via bitcoin-dev wrote:
Quoted text (23 lines)
> 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.
On Wed, 2018-01-24 at 01:52 +0000, Andrew Poelstra via bitcoin-dev wrote:
Quoted text (12 lines)
> > > 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
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:
Quoted text (2 lines)
> 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:
Quoted text (1 line)
> 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.
On Wed, 2018-01-24 at 13:51 +0100, Natanael via bitcoin-dev wrote:
Quoted text (8 lines)
> 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
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.
On Wed, 2018-01-24 at 19:51 +0100, Natanael wrote:
Quoted text (11 lines)
> > 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...
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.
(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:
Quoted text (49 lines)
> > 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.
On Tue, Jan 23, 2018 at 12:30 AM, Gregory Maxwell <greg@xiph•org> wrote:
Quoted text (5 lines)
> 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;]
On Tue, Jan 23, 2018 at 1:44 AM, Anthony Towns via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (27 lines)
> 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.
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-
Quoted text (17 lines)
>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.
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:
Quoted text (109 lines)
>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 >
On Fri, Jan 26, 2018 at 09:34:39PM +0000, Gregory Maxwell via bitcoin-dev wrote:
Quoted text (8 lines)
> 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?On Thu, Jul 12, 2018 at 6:52 PM Anthony Towns via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (21 lines)
> 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.
Quoted text (6 lines)
> (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.
Quoted text (7 lines)
> [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,