Taproot proposal
24 messages, 6 May to 18 Sep 2019. Started by Pieter Wuille.
ZmnSCPxj (6), Pieter Wuille (5), Russell O'Connor (4), Luke Dashjr (2), Anthony Towns (2), Sjors Provoost, Johnson Lau, John Newbery, +2 more
Hello everyone,
Here are two BIP drafts that specify a proposal for a Taproot softfork. A number of ideas are included:
* Taproot to make all outputs and cooperative spends indistinguishable from eachother. * Merkle branches to hide the unexecuted branches in scripts. * Schnorr signatures enable wallet software to use key aggregation/thresholds within one input. * Improvements to the signature hashing algorithm (including signing all input amounts). * Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support batch validation. * Tagged hashing for domain separation (avoiding issues like CVE-2012-2459 in Merkle trees). * Extensibility through leaf versions, OP_SUCCESS opcodes, and upgradable pubkey types.
The BIP drafts can be found here: * https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki specifies the transaction input spending rules. * https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki specifies the changes to Script inside such spends. * https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki is the Schnorr signature proposal that was discussed earlier on this list (See https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html)
An initial reference implementation of the consensus changes, plus preliminary construction/signing tests in the Python framework can be found on https://github.com/sipa/bitcoin/commits/taproot. All together, excluding the Schnorr signature module in libsecp256k1, the consensus changes are around 520 LoC.
While many other ideas exist, not everything is incorporated. This includes several ideas that can be implemented separately without loss of effectiveness. One such idea is a way to integrate SIGHASH_NOINPUT, which we're working on as an independent proposal.
The document explains basic wallet operations, such as constructing outputs and signing. However, a wide variety of more complex constructions exist. Standardizing these is useful, but out of scope for now. It is likely also desirable to define extensions to PSBT (BIP174) for interacting with Taproot. That too is not included here.
Cheers,
There are multiple references to "space savings", but no rationale for treating "space" as something to save or even define. The costs are in CPU time and I/O (which "space saving" doesn't necessarily reduce) and bandwidth (which can often be reduced without "space saving" in commitments). The proposal can apparently be made simpler by ignoring this irrelevant "space saving" goal.
Tagged hashes put the tagging at the start of the hash input. This means implementations can pre-cache SHA2 states, but it also means they can't reuse states to produce data for different contexts. (I'm not sure if there is a use for doing so... but maybe as part of further hiding MAST branches?)
Is there any way to use the Taproot construct here while retaining external script limitations that the involved party(ies) *cannot* agree to override? For example, it is conceivable that one might wish to have an unconditional CLTV enforced in all circumstances.
It may be useful to have a way to add a salt to tap branches.
Some way to sign an additional script (not committed to by the witness program) seems like it could be a trivial addition.
On Monday 06 May 2019 17:57:57 Pieter Wuille via bitcoin-dev wrote:
Quoted text (48 lines)
> Hello everyone, > > Here are two BIP drafts that specify a proposal for a Taproot > softfork. A number of ideas are included: > > * Taproot to make all outputs and cooperative spends indistinguishable > from eachother. > * Merkle branches to hide the unexecuted branches in scripts. > * Schnorr signatures enable wallet software to use key > aggregation/thresholds within one input. > * Improvements to the signature hashing algorithm (including signing > all input amounts). > * Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support > batch validation. > * Tagged hashing for domain separation (avoiding issues like > CVE-2012-2459 in Merkle trees). > * Extensibility through leaf versions, OP_SUCCESS opcodes, and > upgradable pubkey types. > > The BIP drafts can be found here: > * https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki > specifies the transaction input spending rules. > * https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki > specifies the changes to Script inside such spends. > * https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki > is the Schnorr signature proposal that was discussed earlier on this > list (See > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.ht >ml) > > An initial reference implementation of the consensus changes, plus > preliminary construction/signing tests in the Python framework can be > found on https://github.com/sipa/bitcoin/commits/taproot. All > together, excluding the Schnorr signature module in libsecp256k1, the > consensus changes are around 520 LoC. > > While many other ideas exist, not everything is incorporated. This > includes several ideas that can be implemented separately without loss > of effectiveness. One such idea is a way to integrate SIGHASH_NOINPUT, > which we're working on as an independent proposal. > > The document explains basic wallet operations, such as constructing > outputs and signing. However, a wide variety of more complex > constructions exist. Standardizing these is useful, but out of scope > for now. It is likely also desirable to define extensions to PSBT > (BIP174) for interacting with Taproot. That too is not included here. > > Cheers,
Hey Pieter,
I think this is a reasonable collection of changes that make sense in combination. Some initial feedback and questions.
From the BIP:
Quoted text (5 lines)
> If one or more of the spending conditions consist of just a single key (after aggregation), > he most likely one should be made the internal key. If no such condition exists, it may > be worthwhile adding one that consists of an aggregation of all keys participating in all > scripts combined; effectively adding an "everyone agrees" branch. If that is inacceptable, > pick as internal key a point with unknown discrete logarithm (TODO).
I assume Luke Dashjr referred to the above when saying:
Quoted text (4 lines)
> Is there any way to use the Taproot construct here while retaining external > script limitations that the involved party(ies) *cannot* agree to override? > For example, it is conceivable that one might wish to have an unconditional > CLTV enforced in all circumstances.
One reason why someone would want to avoid a "everone agrees" branch, is duress (or self-discipline, or limiting powers of a trustee). In particular with respect to time-locks.
Can this "unknown discrete logarithm" be made provably unknown, so all signers are assured of this property? Bonus points if the outside world can't tell. The exact mechanism could be outside the scope of the BIP, but knowing that it's possible is useful.
Perhaps Lightning devs have an opinion on "everyone agrees" with respect to hash pre-images. I suspect there is no benefit in guaranteeing that a pre-image must be revealed or a timeout must be waited for and there's no way around that condition.
Regarding usage of Schnorr: do I understand correctly that the "everyone agrees" internal key MUST use Schnorr, and that individual branches MAY use Schnorr, but only if they're marked as tapscript spend?
Why is tapscript not mandatory?
Misc details:
In the Design section under "Merkle branches" I suggest adding bullet points with short descriptions of "various known mechanisms for implementing this". In addition to "space savings" maybe also briefly mention a few other pros and cons, like implementation complexity and privacy. And then point out which one you picked.
In the Design section, explicitly point out you're no longer using the hash of a public key (can move some explanation up from rationale section). This is a significant change, even if you have good reason to believe it's perfectly safe.
Regarding the 64 byte SHA256(tag) || SHA256(tag) 64-byte long context-specific constant: maybe add that sha-2 block size is 512 bits
"Conceptually every Taproot output corresponds to" -> some of this conceptual stuff belongs in or before the Specification section. Try briefly explaining how tagged hashes and script validation (stack) interact, before specifying them in detail. The figure (without the pseudo-code) can be helpful for that.
In the figure with the merkle tree, the description says there's "3 script leaves.". So what's going on in leaf D? If it's a way to indicate an unused leaf, why is E different (or is also TapLeaf)? Maybe emphasize that "TapLeaf" tag is there so prove to all signers there's no secret conditions (the CVE-2012-2459 protection you refer to).
Sjors
Quoted text (79 lines)
> Op 6 mei 2019, om 22:17 heeft Luke Dashjr via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> het volgende geschreven: > > There are multiple references to "space savings", but no rationale for > treating "space" as something to save or even define. The costs are in CPU > time and I/O (which "space saving" doesn't necessarily reduce) and bandwidth > (which can often be reduced without "space saving" in commitments). The > proposal can apparently be made simpler by ignoring this irrelevant "space > saving" goal. > > Tagged hashes put the tagging at the start of the hash input. This means > implementations can pre-cache SHA2 states, but it also means they can't reuse > states to produce data for different contexts. (I'm not sure if there is a > use for doing so... but maybe as part of further hiding MAST branches?) > > Is there any way to use the Taproot construct here while retaining external > script limitations that the involved party(ies) *cannot* agree to override? > For example, it is conceivable that one might wish to have an unconditional > CLTV enforced in all circumstances. > > It may be useful to have a way to add a salt to tap branches. > > Some way to sign an additional script (not committed to by the witness > program) seems like it could be a trivial addition. > > > On Monday 06 May 2019 17:57:57 Pieter Wuille via bitcoin-dev wrote: >> Hello everyone, >> >> Here are two BIP drafts that specify a proposal for a Taproot >> softfork. A number of ideas are included: >> >> * Taproot to make all outputs and cooperative spends indistinguishable >> from eachother. >> * Merkle branches to hide the unexecuted branches in scripts. >> * Schnorr signatures enable wallet software to use key >> aggregation/thresholds within one input. >> * Improvements to the signature hashing algorithm (including signing >> all input amounts). >> * Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support >> batch validation. >> * Tagged hashing for domain separation (avoiding issues like >> CVE-2012-2459 in Merkle trees). >> * Extensibility through leaf versions, OP_SUCCESS opcodes, and >> upgradable pubkey types. >> >> The BIP drafts can be found here: >> * https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki >> specifies the transaction input spending rules. >> * https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki >> specifies the changes to Script inside such spends. >> * https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki >> is the Schnorr signature proposal that was discussed earlier on this >> list (See >> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.ht >> ml) >> >> An initial reference implementation of the consensus changes, plus >> preliminary construction/signing tests in the Python framework can be >> found on https://github.com/sipa/bitcoin/commits/taproot. All >> together, excluding the Schnorr signature module in libsecp256k1, the >> consensus changes are around 520 LoC. >> >> While many other ideas exist, not everything is incorporated. This >> includes several ideas that can be implemented separately without loss >> of effectiveness. One such idea is a way to integrate SIGHASH_NOINPUT, >> which we're working on as an independent proposal. >> >> The document explains basic wallet operations, such as constructing >> outputs and signing. However, a wide variety of more complex >> constructions exist. Standardizing these is useful, but out of scope >> for now. It is likely also desirable to define extensions to PSBT >> (BIP174) for interacting with Taproot. That too is not included here. >> >> Cheers, > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Good morning Luke,
Quoted text (4 lines)
> Is there any way to use the Taproot construct here while retaining external > script limitations that the involved party(ies) cannot agree to override? > For example, it is conceivable that one might wish to have an unconditional > CLTV enforced in all circumstances.
Perhaps this can be enforced offchain, by participants refusing to sign a transaction unless it has an `nLockTime` of the agreed-upon "unconditional CLTV". Then the CLTV need only be on branches which have a strict subset of the participants as signers.
Quoted text (2 lines)
> > It may be useful to have a way to add a salt to tap branches.
Would not adding `OP_PUSH(<salt>) OP_DROP` to the leaves work? If you enforce always salting with a 32-byte salt, that "only" saves 3 bytes of witness data (for the `OP_PUSHDATA1+size` and `OP_DROP` opcodes). Or do you refer to always salting every node? (I am uncertain, but would not adding a salt to every leaf be sufficient?)
(in any case, if you use different pubkeys for each contract, rather than reusing keys, is that not enough randomization to prevent creating rainbow tables of scripts?)
Quoted text (3 lines)
> > Some way to sign an additional script (not committed to by the witness > program) seems like it could be a trivial addition.
It seems to me the annex can be used for this, by having it contain both the script and the signature somehow concatenated.
Regards, ZmnSCPxj
Good morning Sjors,
Sent with ProtonMail Secure Email.
‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ On Wednesday, May 8, 2019 4:42 AM, Sjors Provoost via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (22 lines)
> Hey Pieter, > > I think this is a reasonable collection of changes that make sense in combination. Some initial feedback and questions. > > From the BIP: > > > If one or more of the spending conditions consist of just a single key (after aggregation), > > he most likely one should be made the internal key. If no such condition exists, it may > > be worthwhile adding one that consists of an aggregation of all keys participating in all > > scripts combined; effectively adding an "everyone agrees" branch. If that is inacceptable, > > pick as internal key a point with unknown discrete logarithm (TODO). > > I assume Luke Dashjr referred to the above when saying: > > > Is there any way to use the Taproot construct here while retaining external > > script limitations that the involved party(ies) cannot agree to override? > > For example, it is conceivable that one might wish to have an unconditional > > CLTV enforced in all circumstances. > > One reason why someone would want to avoid a "everone agrees" branch, is duress (or self-discipline, or limiting powers of a trustee). In particular with respect to time-locks. > > Can this "unknown discrete logarithm" be made provably unknown, so all signers are assured of this property? Bonus points if the outside world can't tell. The exact mechanism could be outside the scope of the BIP, but knowing that it's possible is useful.
As I understand it, it is possible to take some random data, hash it with SHA256 and acquire a 256-bit number. Then treat that number as an X coordinate (or is it Y...), and see if there exists a point on the secp256k1 curve at that coordinate. If not, try another random data, or just hash the same number again. As I understand it, about half the possible X coordinates will have a point on the curve.
I believe this is the "hash to a point" technique.
The scalar behind the above point cannot be known, unless either the hash function is broken, or ECDLP is broken. (perhaps a better cryptographer can give the proper qualifications, any corrections, and etc etc)
As the point is just an arbitrary point on the curve, it is unknown to the rest of the world whether somebody knows the scalar, or nobody knows.
Quoted text (2 lines)
> > Perhaps Lightning devs have an opinion on "everyone agrees" with respect to hash pre-images. I suspect there is no benefit in guaranteeing that a pre-image must be revealed or a timeout must be waited for and there's no way around that condition.
The "everyone agrees" branch in Lightning is basically the "cooperative close" of the channel. So it is not likely we will need an "everyone agrees" branch in the actual HTLCs we transfer *within* the channel. So if we need to use hashes still, we will likely use the "hash to a point" technique above.
Or just use pubkeys given by both participants, that should be enough to ensure the "everyone agrees" branch is never taken if we write our software such that we never agree to sign with it (i.e. just get points from both sides and MuSig them; then each side can just erase the scalar generating it from memory and whatever caches exist on the system; a node might even just generate a single random point from a scalar it subsequently erases, and just use some non-hardened derivation path from that for every HTLC it has to make). This technique is "sufficiently provably unknown" since each participant knows that it deliberately erased the only means of knowing the complete discrete log by erasing its share. In short, "everyone agrees" is trivially easy to make "nobody can agree" by a single participant never agreeing to let itself be ripped off.
Do note that it is likely Lightning will eventually switch to using payment points/scalars instead of hashes/preimages. This will allow us to have path decorrelation, both within a route, and in multiple routes of the same payment. This is enabled by Schnorr, as this requires Scriptless Script. (granted 2p-ECDSA also enables Scriptless Script, but we decided to wait for Schnorr to hit base layer instead) This means we would be using the "everyone agrees" path only, with everyone agreeing to first create a `nLockTime` backout tx, then everyone agreeing to create a transaction where one side has knowledge of a secret scalar that is learned by the other side upon completion of the signature.
Regards, ZmnSCPxj
On Mon, May 06, 2019 at 08:17:09PM +0000, Luke Dashjr via bitcoin-dev wrote:
Quoted text (2 lines)
> Some way to sign an additional script (not committed to by the witness > program) seems like it could be a trivial addition.
Aside: if you want to commit to something extra *with* the witness program, you could use either an unsolvable tapleaf branch (eg, one that uses OP_RETURN and also pushes the data you want to commit to), or a p2c construction like:
Taproot: Q = P + H_TapTweak(P || S)*G
P2C: P = R + H_"myp2c"(R || Contract)*G
If you don't have any scripts for S, you could set S=["OP_RETURN"] to ensure there are no scripts. Having either the TapTweak formula or the H_myp2c hash should be enough to ensure that your contract can't get maliciously reinterpreted as a valid tapscript, having both is just belts and suspenders.
But to address your question: if you want to commit to something extra at spending/signing time rather than when creating the address, then that's what the annex should be useful for. eg as a simple example, your annex might be:
0x50 [flag]
0x25 [entry size]
0x77 [annex entry id]
0x0008c618 [block height == 575000]
0x00000000000000000007df59824a0c86d1cc21b90eb25259dd2dba5170cea5f5
[block hash for block at 575000]
which would allow you to commit to a particular block hash, and there could be a soft fork that added the restriction that such a commitment invalidates the transaction if the block at the given height doesn't match the provided hash.
You still need to the soft-fork to do the enforcing, but once you have that, *every* existing taproot address automatically gets "upgraded" to allow you to make the commitment, including via key path spends, which seems pretty nice.
(That construction (ie size,id,data) lets you have multiple entries in the annex reasonably efficiently)
Cheers, aj
Good morning Sjors, sorry everyone for the double-posting...
Quoted text (6 lines)
> I believe this is the "hash to a point" technique. > > The scalar behind the above point cannot be known, unless either the hash function is broken, or ECDLP is broken. > (perhaps a better cryptographer can give the proper qualifications, any corrections, and etc etc) > > As the point is just an arbitrary point on the curve, it is unknown to the rest of the world whether somebody knows the scalar, or nobody knows.
Now that I think further, everyone can use *the same* point generated from an arbitrary "hash to a point". For example, we can define the "script-only point" as the point whose X coordinate (or is it Y...) is equal to SHA256("Pieter Wuille is really great!"). Add more "really " until we get a point on the curve.
Provided everyone knows what the exact data to hash is, and the exact hash function, the above procedure is sufficient for everybody to verify that Pieter Wuille (and anyone else for that matter) cannot, in fact, spend the coin unilaterally, and that nobody can actually spend the coin, except via a script.
Since the point on the output is tweaked by the script merkle tree root, varying your pubkey for each use will be enough to blind the use of the "script-only point" until you have to reveal it during spending anyway. If you *absolutely* insist on reusing your pubkeys, then adding a `OP_PUSH(<salt>) OP_DROP` to at least one script, with a random salt, should be enough to blind the use of the script-only point until you have to reveal the script you want to use. Or even just further tweak the point before using it as the taproot internal pubkey, so that not even a coin spend reveals that the "everyone agrees" branch was never actually an option.
Quoted text (4 lines)
> Or just use pubkeys given by both participants, that should be enough to ensure the "everyone agrees" branch is never taken if we write our software such that we never agree to sign with it (i.e. just get points from both sides and MuSig them; then each side can just erase the scalar generating it from memory and whatever caches exist on the system; a node might even just generate a single random point from a scalar it subsequently erases, and just use some non-hardened derivation path from that for every HTLC it has to make). > This technique is "sufficiently provably unknown" since each participant knows that it deliberately erased the only means of knowing the complete discrete log by erasing its share. > In short, "everyone agrees" is trivially easy to make "nobody can agree" by a single participant never agreeing to let itself be ripped off. >
The "taproot assumption" is that there exists some finite set of participants that is interested in how the coin will be spent. Under the taproot assumption then, any "truster" that assigns time-limited control of a coin to a "trustee" is part of that finite set interested in the coin spend conditions. So the truster should in fact be asked for a pubkey to be added in the taproot internal pubkey that enables the "everyone agrees" branch. Then the truster can simply generate a point without knowing its private key, or by forgetting this private key.
If one is sufficiently schizophrenic, one can split oneself into a "truster" and "trustee" as above and deliberately forget the truster private key. Then one is sufficiently unable to spend under duress by deleting the "truster" sub-agent and providing real-world access to the "trustee" sub-agent that can only spend under specific SCRIPT-defined conditions.
(the above paragraph should not be taken to mean that I am an agent-based AI)
That is, it should be enough for everyone to agree to lock the "everyone agrees" branch and throw away their own key, to keep that branch locked.
Regards, ZmnSCPxj
On Monday 06 May 2019 20:17:09 Luke Dashjr via bitcoin-dev wrote:
Quoted text (2 lines)
> Some way to sign an additional script (not committed to by the witness > program) seems like it could be a trivial addition.
This would be especially useful for things like OP_CHECKBLOCKATHEIGHT:
https://github.com/bitcoin/bips/blob/master/bip-0115.mediawiki
Thanks for the comments so far!
I'm going to respond to some of the comments here. Things which I plan to address with changes in the BIP I'll leave for later.
On Mon, 6 May 2019 at 13:17, Luke Dashjr <luke@dashjr•org> wrote:
Quoted text (4 lines)
> Tagged hashes put the tagging at the start of the hash input. This means > implementations can pre-cache SHA2 states, but it also means they can't reuse > states to produce data for different contexts. (I'm not sure if there is a > use for doing so... but maybe as part of further hiding MAST branches?)
It's true you can't cache/precompute things across tags, but I also think there is no need. The type of data hashed in a sighash vs a merkle branch/leaf vs a tweak is fundamentally different. I think this is perhaps a good guidance to include about when separate tags are warranted vs. simply making sure the input does not collide: there shouldn't be much or any shared data with things that are expected to be inputs under other tags.
Quoted text (4 lines)
> Is there any way to use the Taproot construct here while retaining external > script limitations that the involved party(ies) *cannot* agree to override? > For example, it is conceivable that one might wish to have an unconditional > CLTV enforced in all circumstances.
Yes, absolutely - you can use a point with unknown discrete logarithm as internal key. This will result in only script path spends being available. For the specific goal you're stating an alternative may be using a valid known private key, using it to pre-sign a timelocked transaction, and destroying the key.
Quoted text (1 line)
> It may be useful to have a way to add a salt to tap branches.
If you don't reuse public keys, effectively every branch is automatically salted (and the position in the tree gets randomized automatically when doing so, providing a small additional privacy benefit).
Quoted text (4 lines)
>> Some way to sign an additional script (not committed to by the witness >> program) seems like it could be a trivial addition. > This would be especially useful for things like OP_CHECKBLOCKATHEIGHT: > https://github.com/bitcoin/bips/blob/master/bip-0115.mediawiki
If you're talking about the ability to sign over the ability to spend to another script ("delegation"), there are lots of interesting applications and ways to implement it. But it overlaps with Graftroot, and doing it efficiently in general has some interesting and non-obvious engineering challenges (for example, signing over to a script that enforces "f(tx)=y" for some f can be done by only storing f and then including y in the sighash).
For the specific example of BIP115's functionality, that seems like a reasonable thing that could be dealt with using the annex construction in the proposed BIP. A consensus rule could define a region inside the annex that functions as a height-blockhash assertion. The annex is included in all sighashes, so it can't be removed from the input; later opcodes could include the ability to inspect that assertion even.
On Tue, 7 May 2019 at 13:43, Sjors Provoost <sjors@sprovoost•nl> wrote:
Quoted text (1 line)
> One reason why someone would want to avoid a "everone agrees" branch, is duress (or self-discipline, or limiting powers of a trustee). In particular with respect to time-locks.>
Indeed, though as I suggested above, you can also use timelocked transactions (but using only CLTV branches is more flexible certainly).
Quoted text (1 line)
> Can this "unknown discrete logarithm" be made provably unknown, so all signers are assured of this property? Bonus points if the outside world can't tell. The exact mechanism could be outside the scope of the BIP, but knowing that it's possible is useful.
Yes, that's a TODO that's left in the draft, but this is absolutely possible (using a hash-to-curve operation). As ZmnSCPxj already suggested, there can even be a fixed known constant you can use for this. However, you get better privacy by taking this fixed known constant (call it C) and using as internal key a blinded version of it (C+rG, for some random value r, and G the normal secp256k1 generator); as long as the DL between G and C is unknown, this is safe (and does not reveal to the world that in fact no key-path was permitted when spending).
Quoted text (3 lines)
> Regarding usage of Schnorr: do I understand correctly that the "everyone agrees" internal key MUST use Schnorr, and that individual branches MAY use Schnorr, but only if they're marked as tapscript spend? > > Why is tapscript not mandatory?
Spending using the internal key always uses a single Schnorr signature and nothing else. When you spend using a script path, you must reveal both the script and its leaf version. If that leaf version is 0xc0, the script is interpreted as a tapscript (in which only Schnorr opcodes exist). If that leaf version is not 0xc0, the script is undefined, and is unconditionally valid. This is one of the included extension mechanisms, allowing replacing the whole script language with something else, but without revealing it unless a branch using it is actually used (different Merkle tree leaves can have a distinct leaf versions).
So the reason that tapscript is not mandatory is because other leaf versions are undefined, and left for future extensions (similar to how future segwit versions at the output level are undefined).
Cheers,
Quoted text (6 lines)
> >> >> Some way to sign an additional script (not committed to by the witness >> program) seems like it could be a trivial addition. > > It seems to me the annex can be used for this, by having it contain both the script and the signature somehow concatenated.
This is not possible since the whole annex is signed. It is possible if the signed “script” does not require further input, like per-input lock-time, relative lock-time, check block hash
Quoted text (7 lines)
> > Regards, > ZmnSCPxj > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Good morning Johnson,
Quoted text (6 lines)
> > > Some way to sign an additional script (not committed to by the witness > > > program) seems like it could be a trivial addition. > > > > It seems to me the annex can be used for this, by having it contain both the script and the signature somehow concatenated. > > This is not possible since the whole annex is signed. It is possible if the signed “script” does not require further input, like per-input lock-time, relative lock-time, check block hash
I understand, you are correct.
Possibly the correct way would be to use another leaf version. The "script" of such a new leaf version would not actually be a script, but a delegation key. Then for this leaf version the actual script and signature from the delegation key attesting that script would be on top of the witness stack that will be used by the actual script. This has the nice property that the existence of a delegation key is hidden from the output, and that if an alternate script is in the MAST (as an alternative to the delegation), use of that alternate script does not reveal that delegation could have been possible.
Regards, ZmnSCPxj
Good morning list,
Quoted text (11 lines)
> > Can this "unknown discrete logarithm" be made provably unknown, so all signers are assured of this property? Bonus points if the outside world can't tell. The exact mechanism could be outside the scope of the BIP, but knowing that it's possible is useful. > > Yes, that's a TODO that's left in the draft, but this is absolutely > possible (using a hash-to-curve operation). As ZmnSCPxj already > suggested, there can even be a fixed known constant you can use for > this. However, you get better privacy by taking this fixed known > constant (call it C) and using as internal key a blinded version of it > (C+rG, for some random value r, and G the normal secp256k1 generator); > as long as the DL between G and C is unknown, this is safe (and does > not reveal to the world that in fact no key-path was permitted when > spending).
Gregory Maxwell commented some days ago:
Quoted text (1 line)
> 2019-05-11T23:35:02 <gmaxwell> sipa: also someone might want to point out to ZmnSCPxj that his scheme for getting a NUMS point is insecure (it must also commit to G because we don't know how G was generated)
I am assuming that gmax is referring to my description of the "hash-to-point" or "hash-to-curve" operation.
A little more research shows this: https://crypto.stackexchange.com/a/25603
From the above, it seems the method that real cryptographers use is:
1. Generate some random data d. 2. Get x = h(G | d) where G is the existing generator for secp256k1. 3. Find a point on secp256k1 with X coordinate x. 4. If not found, go to 1.
In any case, I am almost sure that for every case where the "everyone agrees" path is unwanted in a taproot address, the simple "put your own pubkey lock on the door and throw away the privkey" technique would work without requiring a NUMS point: the same taproot assumption should also work here. But generation of a NUMS point might be of independent interest in any case (e.g. setting up Pedersen commitments).
Regards, ZmnSCPxj
Regarding Tapscript, the specification calls for the final value of the stack being a single non-false value:
The tapscript is executed according to the rules in the following section,
Quoted text (4 lines)
> with the initial stack as input > II. If the execution results in anything but exactly one element on > the stack which evaluates to true with CastToBool(), fail. >
Perhaps it is worth taking this opportunity here to remove a minor wart of the Script language and instead require the stack to be exactly empty upon completion.
In addition to removing a potential malleability vector, I expect it would simplify development of Bitcoin Script. A rule requiring an empty stack means that the conjunction (logical and) of two policies can be implemented by the simple concatenation of Bitcoin Scripts. This combined with the taproot ability to form the disjunction (logical or) of policies by having multiple Merkle branches, means that the translation of a policy written in disjunctive normal form (the logical ors of logical ands of primitive policies) can be straightforwardly translated to a taproot of tapscript.
That said, I think the developers of miniscript < http://bitcoin.sipa.be/miniscript/miniscript.html> are in a much better position to comment on whether my above intuition is correct given that they've had to implement a host of various calling conventions. I understand that at least some of this complexity is due to Bitcoin Script's one element stack rule.
Scripts under the old one element rule can be translated to the new rule by adding an OP_VERIFY operation to the end of the script; however it is likely that this OP_VERIFY can be folded into the previous operation yielding an OP_EQUALVERIFY or OP_CHECKSIGVERIFY in many cases.
Even if we choose not to implement the empty stack rule, we should at least require that the last element be 0x01 to remove a potential malleability vector and bring it in line with MINIMAL_IF semantics.
Thanks.
On Mon, May 6, 2019 at 2:36 PM Pieter Wuille via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (56 lines)
> Hello everyone, > > Here are two BIP drafts that specify a proposal for a Taproot > softfork. A number of ideas are included: > > * Taproot to make all outputs and cooperative spends indistinguishable > from eachother. > * Merkle branches to hide the unexecuted branches in scripts. > * Schnorr signatures enable wallet software to use key > aggregation/thresholds within one input. > * Improvements to the signature hashing algorithm (including signing > all input amounts). > * Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support > batch validation. > * Tagged hashing for domain separation (avoiding issues like > CVE-2012-2459 in Merkle trees). > * Extensibility through leaf versions, OP_SUCCESS opcodes, and > upgradable pubkey types. > > The BIP drafts can be found here: > * https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki > specifies the transaction input spending rules. > * https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki > specifies the changes to Script inside such spends. > * https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki > is the Schnorr signature proposal that was discussed earlier on this > list (See > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html > ) > > An initial reference implementation of the consensus changes, plus > preliminary construction/signing tests in the Python framework can be > found on https://github.com/sipa/bitcoin/commits/taproot. All > together, excluding the Schnorr signature module in libsecp256k1, the > consensus changes are around 520 LoC. > > While many other ideas exist, not everything is incorporated. This > includes several ideas that can be implemented separately without loss > of effectiveness. One such idea is a way to integrate SIGHASH_NOINPUT, > which we're working on as an independent proposal. > > The document explains basic wallet operations, such as constructing > outputs and signing. However, a wide variety of more complex > constructions exist. Standardizing these is useful, but out of scope > for now. It is likely also desirable to define extensions to PSBT > (BIP174) for interacting with Taproot. That too is not included here. > > Cheers, > > -- > Pieter > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >
Hi,
Quoted text (2 lines)
> A Taproot output is a SegWit output [...] with > version number 1, and a 33-byte witness program whose first byte is 0 or
1.
Given a secret key k and public key P=(x,y), a signer with the knowledge of k can sign for -P=(x,p-y) since -k is the secret key for that point. Encoding the y value of the public key therefore adds no security. As an alternative to providing the y value of the taproot output key Q when constructing the taproot output, the signer can provide it when signing. We can also restrict the y value of the internal key P to be even (or high, or a quadratic residue). That gives us 4 options for how to set the y signs for P and Q.
1. Q sign is explictly set in the witness program, P sign is explicitly set
in the control block
=> witness program is 33 bytes, 32 possible leaf versions (one for each
pair of 0xc0..0xff)
2. Q sign is explictly set in the witness program, P sign is implicitly even
=> witness program is 33 bytes, 64 possible leaf versions (one for each
0xc0..0xff)
3. Q sign is explictly set in the control block, P sign is explicitly set
in the control block
=> witness program is 32 bytes, 16 possible leaf versions (one for each
4-tuple of 0xc0..0xff)
4. Q sign is explictly set in the control block, P sign is implicitly even
=> witness program is 32 bytes, 32 possible leaf versions (one for pair
of 0xc0..0xff)
The current proposal uses (1). Using (3) or (4) would reduce the size of a taproot output by one byte to be the same size as a P2WSH output. That means that it's not more expensive for senders compared to sending to P2WSH.
(Credit to James Chiang for suggesting omitting the y sign from the public key and to sipa for pointing out the 4 options above)
Quoted text (1 line)
> (native or P2SH-nested, see BIP141)
I'd prefer to not support P2SH-nested TR. P2SH wrapping was useful for segwit v0 for compatibility reasons. Most wallets/exchanges/services now support sending to native segwit addresses (https://en.bitcoin.it/wiki/Bech32_adoption) and that will be even more true if Schnorr/Taproot activate in 12+ months time.
On Mon, May 6, 2019 at 2:36 PM Pieter Wuille via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (56 lines)
> Hello everyone, > > Here are two BIP drafts that specify a proposal for a Taproot > softfork. A number of ideas are included: > > * Taproot to make all outputs and cooperative spends indistinguishable > from eachother. > * Merkle branches to hide the unexecuted branches in scripts. > * Schnorr signatures enable wallet software to use key > aggregation/thresholds within one input. > * Improvements to the signature hashing algorithm (including signing > all input amounts). > * Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support > batch validation. > * Tagged hashing for domain separation (avoiding issues like > CVE-2012-2459 in Merkle trees). > * Extensibility through leaf versions, OP_SUCCESS opcodes, and > upgradable pubkey types. > > The BIP drafts can be found here: > * https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki > specifies the transaction input spending rules. > * https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki > specifies the changes to Script inside such spends. > * https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki > is the Schnorr signature proposal that was discussed earlier on this > list (See > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html > ) > > An initial reference implementation of the consensus changes, plus > preliminary construction/signing tests in the Python framework can be > found on https://github.com/sipa/bitcoin/commits/taproot. All > together, excluding the Schnorr signature module in libsecp256k1, the > consensus changes are around 520 LoC. > > While many other ideas exist, not everything is incorporated. This > includes several ideas that can be implemented separately without loss > of effectiveness. One such idea is a way to integrate SIGHASH_NOINPUT, > which we're working on as an independent proposal. > > The document explains basic wallet operations, such as constructing > outputs and signing. However, a wide variety of more complex > constructions exist. Standardizing these is useful, but out of scope > for now. It is likely also desirable to define extensions to PSBT > (BIP174) for interacting with Taproot. That too is not included here. > > Cheers, > > -- > Pieter > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >
On Tue, 21 May 2019 at 10:20, Russell O'Connor <roconnor@blockstream•io> wrote:
Quoted text (11 lines)
> > Regarding Tapscript, the specification calls for the final value of the stack being a single non-false value: > >> The tapscript is executed according to the rules in the following section, with the initial stack as input >> II. If the execution results in anything but exactly one element on the stack which evaluates to true with CastToBool(), fail. > > Perhaps it is worth taking this opportunity here to remove a minor wart of the Script language and instead require the stack to be exactly empty upon completion. > > In addition to removing a potential malleability vector, I expect it would simplify development of Bitcoin Script. A rule requiring an empty stack means that the conjunction (logical and) of two policies can be implemented by the simple concatenation of Bitcoin Scripts. This combined with the taproot ability to form the disjunction (logical or) of policies by having multiple Merkle branches, means that the translation of a policy written in disjunctive normal form (the logical ors of logical ands of primitive policies) can be straightforwardly translated to a taproot of tapscript. > > That said, I think the developers of miniscript <http://bitcoin.sipa.be/miniscript/miniscript.html> are in a much better position to comment on whether my above intuition is correct given that they've had to implement a host of various calling conventions. I understand that at least some of this complexity is due to Bitcoin Script's one element stack rule.
IIRC I looked into this a few months ago, and found that the spending cost (script size + expected witness size) of the optimal script for every Miniscript policy at most changes by 1 WU (in either direction) by requiring an empty stack rather than a true value, though in a (admittedly very arbitrarily biased) distribution, more policies were improved by it than degraded. This is not taking Taproot into account (as many of those policies in a Taproot-supporting world should optimally make use of the internal key and Merkle tree, rather than turning everything into a monolithic script). I expect that this may make the impact somewhat larger, but still never more than a 1 WU gain.
I don't think the spending cost changes justify this change, so the remaining criteria are complexity ones. In my view, the main benefit would be to authors of hand-written scripts where the consistency benefits matter, but this needs to be weighed against the mental cost of learning the new semantics. For Miniscript itself, this doesn't make much difference - the top level calling convention would become 'V' instead of 'T', but 'T' would still exist as a calling convention that may be used internally; it's a few lines change.
So overall this feels like something with marginal costs, but also at most marginal benefits. Perhaps other people have stronger opinions.
Quoted text (1 line)
> Even if we choose not to implement the empty stack rule, we should at least require that the last element be 0x01 to remove a potential malleability vector and bring it in line with MINIMAL_IF semantics.
This feels like the right thing to do; as we're making MINIMALIF part of consensus for Tapscript it would make sense to apply the same rule to the "return" value of the script. There is a downside though, namely that in some places where you'd use "<n> OP_CHECKSEQUENCEVERIFY" or "<n> OP_CHECKLOCKTIMEVERIFY" you now need to add an additional OP_0NOTEQUAL to convert the left-over element n into an exact 0x01. I also can't come up with any practical benefits that this would have; if the top stack element in a particular code path comes directly from the input, it's insecure regardless; if there isn't, it'll generally be a a boolean (or an intentional non-boolean true value) computed by the script.
On Tue, 21 May 2019 at 13:05, John Newbery <john@johnnewbery•com> wrote:
Quoted text (9 lines)
> > Hi, > > > A Taproot output is a SegWit output [...] with > > version number 1, and a 33-byte witness program whose first byte is 0 or 1. > > Given a secret key k and public key P=(x,y), a signer with the knowledge of k > can sign for -P=(x,p-y) since -k is the secret key for that point. Encoding the > y value of the public key therefore adds no security.
That's a good point; without security benefit there's no reason to make pay-to-taproots more expensive. Making them the same cost as P2WSH is nice in any case.
Quoted text (18 lines)
> As an alternative to > providing the y value of the taproot output key Q when constructing the taproot > output, the signer can provide it when signing. We can also restrict the y value > of the internal key P to be even (or high, or a quadratic residue). That gives > us 4 options for how to set the y signs for P and Q. > > 1. Q sign is explictly set in the witness program, P sign is explicitly set in the control block > => witness program is 33 bytes, 32 possible leaf versions (one for each pair of 0xc0..0xff) > 2. Q sign is explictly set in the witness program, P sign is implicitly even > => witness program is 33 bytes, 64 possible leaf versions (one for each 0xc0..0xff) > 3. Q sign is explictly set in the control block, P sign is explicitly set in the control block > => witness program is 32 bytes, 16 possible leaf versions (one for each 4-tuple of 0xc0..0xff) > 4. Q sign is explictly set in the control block, P sign is implicitly even > => witness program is 32 bytes, 32 possible leaf versions (one for pair of 0xc0..0xff) > > The current proposal uses (1). Using (3) or (4) would reduce the size of a > taproot output by one byte to be the same size as a P2WSH output. That means > that it's not more expensive for senders compared to sending to P2WSH.
I prefer (4). There is a slight complexity in needing a conditional sign swap when signing (to make sure the corresponding key is even), but I think it's minimal compared to the other changes needed here already. I'll try to amend the reference code soon to see what impact this idea has.
Quoted text (6 lines)
> > (native or P2SH-nested, see BIP141) > > I'd prefer to not support P2SH-nested TR. P2SH wrapping was useful for segwit > v0 for compatibility reasons. Most wallets/exchanges/services now support sending > to native segwit addresses (https://en.bitcoin.it/wiki/Bech32_adoption) and that > will be even more true if Schnorr/Taproot activate in 12+ months time.
I'm not sure there is much to gain here. There is perhaps a minimal fungibility improvement by not having another bit (P2SH or not) that can leak some information about the software you're using. On the other hand, until native taproot outputs are common, choosing P2SH wrapped ones leak less information at output creation time. Apart from that, I think it would only minimally impact implementation complexity. Are there other advantages I'm missing?
Cheers,
On Wed, May 22, 2019 at 10:06 PM Pieter Wuille <pieter.wuille@gmail•com> wrote:
Quoted text (56 lines)
> On Tue, 21 May 2019 at 10:20, Russell O'Connor <roconnor@blockstream•io> > wrote: > > > > Regarding Tapscript, the specification calls for the final value of the > stack being a single non-false value: > > > >> The tapscript is executed according to the rules in the following > section, with the initial stack as input > >> II. If the execution results in anything but exactly one element on > the stack which evaluates to true with CastToBool(), fail. > > > > Perhaps it is worth taking this opportunity here to remove a minor wart > of the Script language and instead require the stack to be exactly empty > upon completion. > > > > In addition to removing a potential malleability vector, I expect it > would simplify development of Bitcoin Script. A rule requiring an empty > stack means that the conjunction (logical and) of two policies can be > implemented by the simple concatenation of Bitcoin Scripts. This combined > with the taproot ability to form the disjunction (logical or) of policies > by having multiple Merkle branches, means that the translation of a policy > written in disjunctive normal form (the logical ors of logical ands of > primitive policies) can be straightforwardly translated to a taproot of > tapscript. > > > > That said, I think the developers of miniscript < > http://bitcoin.sipa.be/miniscript/miniscript.html> are in a much better > position to comment on whether my above intuition is correct given that > they've had to implement a host of various calling conventions. I > understand that at least some of this complexity is due to Bitcoin Script's > one element stack rule. > > IIRC I looked into this a few months ago, and found that the spending > cost (script size + expected witness size) of the optimal script for > every Miniscript policy at most changes by 1 WU (in either direction) > by requiring an empty stack rather than a true value, though in a > (admittedly very arbitrarily biased) distribution, more policies were > improved by it than degraded. This is not taking Taproot into account > (as many of those policies in a Taproot-supporting world should > optimally make use of the internal key and Merkle tree, rather than > turning everything into a monolithic script). I expect that this may > make the impact somewhat larger, but still never more than a 1 WU > gain. > > I don't think the spending cost changes justify this change, so the > remaining criteria are complexity ones. In my view, the main benefit > would be to authors of hand-written scripts where the consistency > benefits matter, but this needs to be weighed against the mental cost > of learning the new semantics. For Miniscript itself, this doesn't > make much difference - the top level calling convention would become > 'V' instead of 'T', but 'T' would still exist as a calling convention > that may be used internally; it's a few lines change. > > So overall this feels like something with marginal costs, but also at > most marginal benefits. Perhaps other people have stronger opinions. >
Thanks for the info. I'm surprised to learn that 'T' would still exist internally. That does make my proposed ammendment a somewhat more marginal than I expected. I still think it would be an improvement, but I guess it is acceptable the way it is if that is what other people prefer.
Quoted text (16 lines)
> > Even if we choose not to implement the empty stack rule, we should at > least require that the last element be 0x01 to remove a potential > malleability vector and bring it in line with MINIMAL_IF semantics. > > This feels like the right thing to do; as we're making MINIMALIF part > of consensus for Tapscript it would make sense to apply the same rule > to the "return" value of the script. There is a downside though, > namely that in some places where you'd use "<n> > OP_CHECKSEQUENCEVERIFY" or "<n> OP_CHECKLOCKTIMEVERIFY" you now need > to add an additional OP_0NOTEQUAL to convert the left-over element n > into an exact 0x01. I also can't come up with any practical benefits > that this would have; if the top stack element in a particular code > path comes directly from the input, it's insecure regardless; if there > isn't, it'll generally be a a boolean (or an intentional non-boolean > true value) computed by the script. >
That is a very good argument. If we were to go with an empty stack we'd probably also want modify to have CSV and CLTV pop their inputs off the stack. But at that point perhaps we'd want to change their opcode values to avoid confusion with old style script. I guess I'm getting more convinced to not touch this stuff just and just bear with the somewhat unfortunate legacy behaviour.
I have a comment about the 'input_index' of the transaction digest for taproot signatures. It is currently listed as 2 bytes. I think it would be better to expand that to 4 bytes. The two byte limit is derived from the block size / weight limit, which limits the maximum size of a transaction, which in turn, due to a minimum size of an inputs, places a limit on the maximum number of inputs.
However, I think it is a mistake to mix limits from the block layer into the transaction layer of the consensus rules. For example, I believe that, as it stands currently, if we wanted to hardfork an increase in the block weight limit, doing so wouldn't have any impact on the transaction layer and we could transparently manage larger transactions with the current transaction format [2]. However if we start incorporating the block limits into the transaction layer, then we run the risk of such a hard fork needing to also make consensus changes in the transaction format/interpretation if we wanted to handle larger transaction sizes, which, while doable, wouldn't be so great.
The current transaction format limits the number of inputs (and the number of outputs) to 2^32-1 or less [1]. So using 4 bytes for the 'input_index' will suffice.
Given that adding 2 bytes to the signed transaction digest isn't a big deal, it's probably better just to keep block limits and transaction limits separate.
[1]The var-integer field for the number of inputs (and the number of outputs) in a transaction looks like it should allow upto 2^64-1 inputs; however this is an illusion. The P2P rules dictate that these values are immediately taken modulo 2^32 after decoding. For example, if the number of inputs is a var-integer encoding of 0x0100000001, it is actually just a non-canonical way of encoding that there is 1 input. Try this at home!
[2]If we were to hardfork an increase in the block weight limit, we would probably want to still keep the limit on the size of transactions that consume legacy UTXOs in order to avoid the quadratic computation problems that plagues the legacy transaction digest.
On Mon, May 6, 2019 at 2:36 PM Pieter Wuille via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (56 lines)
> Hello everyone, > > Here are two BIP drafts that specify a proposal for a Taproot > softfork. A number of ideas are included: > > * Taproot to make all outputs and cooperative spends indistinguishable > from eachother. > * Merkle branches to hide the unexecuted branches in scripts. > * Schnorr signatures enable wallet software to use key > aggregation/thresholds within one input. > * Improvements to the signature hashing algorithm (including signing > all input amounts). > * Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support > batch validation. > * Tagged hashing for domain separation (avoiding issues like > CVE-2012-2459 in Merkle trees). > * Extensibility through leaf versions, OP_SUCCESS opcodes, and > upgradable pubkey types. > > The BIP drafts can be found here: > * https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki > specifies the transaction input spending rules. > * https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki > specifies the changes to Script inside such spends. > * https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki > is the Schnorr signature proposal that was discussed earlier on this > list (See > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html > ) > > An initial reference implementation of the consensus changes, plus > preliminary construction/signing tests in the Python framework can be > found on https://github.com/sipa/bitcoin/commits/taproot. All > together, excluding the Schnorr signature module in libsecp256k1, the > consensus changes are around 520 LoC. > > While many other ideas exist, not everything is incorporated. This > includes several ideas that can be implemented separately without loss > of effectiveness. One such idea is a way to integrate SIGHASH_NOINPUT, > which we're working on as an independent proposal. > > The document explains basic wallet operations, such as constructing > outputs and signing. However, a wide variety of more complex > constructions exist. Standardizing these is useful, but out of scope > for now. It is likely also desirable to define extensions to PSBT > (BIP174) for interacting with Taproot. That too is not included here. > > Cheers, > > -- > Pieter > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation•org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >
On Wed, Jun 26, 2019 at 08:08:01PM -0400, Russell O'Connor via bitcoin-dev wrote:
Quoted text (3 lines)
> I have a comment about the 'input_index' of the transaction digest for taproot > signatures. It is currently listed as 2 bytes. I think it would be better to > expand that to 4 bytes.
FWIW, I think this would be essentially free, at least for the current sighash modes, as (I think) all the non-ANYONECANPAY modes have at least 4 bytes of sha256 padding at present.
In addition to (or, perhaps, as a special case of) the reasons Russell gives, I think this change would also better support proof-of-reserves via taproot signatures (cf [0] or BIP 127), as it would allow the proof tx to include more than 65k utxos with each utxo being signed with a signature that commits to all inputs including the invalid placeholder.
[0] https://blockstream.com/2019/02/04/en-standardizing-bitcoin-proof-of-reserves/
If you didn't have this, but wanted to do proof-of-reserves over >65k taproot UTXOs, you could use ANYONECANPAY signatures, and use the output amounts to ensure the signatures can't be abused, something like:
inputs:
0: spend from txid 0000..0000 vout 0, no witness data
1: utxo1, signed with ANYONECANPAY|ALL
2: utxo2, signed with ANYONECANPAY|ALL
3: utxo3, signed with ANYONECANPAY|ALL
[etc]
outputs:
0: sum(utxo1..utxoN), pay to self
1: 2099999997690001-sum(utxo1..utxo3), payable to whatever
The total output value is therefore one satoshi more bitcoin than there could ever have been, so none of the utxoK signatures can be reused on the blockchain (unless there's severe inflation due to bugs or hardforks), but the values (and sums) all remain less than 21M BTC so it also won't fail the current "amount too big" sanity checks.
That seems a bit more fragile/complicated than using SIGHASH_ALL for everything, though it means your cold wallet doesn't have to serialize your >65k transactions to verify it's signing what it thinks it is.
Quoted text (6 lines)
> [1]The var-integer field for the number of inputs (and the number of outputs) > in a transaction looks like it should allow upto 2^64-1 inputs; however this is > an illusion. The P2P rules dictate that these values are immediately taken > modulo 2^32 after decoding. For example, if the number of inputs is a > var-integer encoding of 0x0100000001, it is actually just a non-canonical way > of encoding that there is 1 input. Try this at home!
Hmm? If I'm following what you mean, that's not the P2P rules, it's the Unserialize code, in particular:
compat/assumptions.h:52:static_assert(sizeof(int) == 4, "32-bit int assumed");
serialize.h:289:uint64_t ReadCompactSize(Stream& is)
serialize.h-679-template<typename Stream, unsigned int N, typename T, typename V>
serialize.h-680-void Unserialize_impl(Stream& is, prevector<N, T>& v, const V&)
serialize.h-681-{
serialize.h-682- v.clear();
serialize.h:683: unsigned int nSize = ReadCompactSize(is);
(and other Unserialize_impl implementations)
However, ReadCompactSize throws "size too large" if the return value is greater than MAX_SIZE == 0x02000000 =~ 33.5M, which prior to the implicit cast to 32 bits in Unserialize_impl. And it looks like that check's been there since Satoshi...
So as far as I can see, that encoding's just unsupported/invalid, rather than equivalent/non-canonical?
Cheers, aj
Hmm? If I'm following what you mean, that's not the P2P rules, it's the
Quoted text (25 lines)
> Unserialize code, in particular:
>
> compat/assumptions.h:52:static_assert(sizeof(int) == 4, "32-bit int
> assumed");
>
> serialize.h:289:uint64_t ReadCompactSize(Stream& is)
>
> serialize.h-679-template<typename Stream, unsigned int N, typename T,
> typename V>
> serialize.h-680-void Unserialize_impl(Stream& is, prevector<N, T>& v,
> const V&)
> serialize.h-681-{
> serialize.h-682- v.clear();
> serialize.h:683: unsigned int nSize = ReadCompactSize(is);
>
> (and other Unserialize_impl implementations)
>
> However, ReadCompactSize throws "size too large" if the return value is
> greater than MAX_SIZE == 0x02000000 =~ 33.5M, which prior to the implicit
> cast to 32 bits in Unserialize_impl. And it looks like that check's been
> there since Satoshi...
>
> So as far as I can see, that encoding's just unsupported/invalid, rather
> than equivalent/non-canonical?
>Thanks for this correction! I totally missed that MAX_SIZE == 0x02000000. I think I mistook it for SIZE_MAX when reviewing this, or just didn't notice it at all.
Cheers,
Quoted text (3 lines)
> aj > >
Hi, I want to add to John Newbery's suggestion of using implicit even/odd only public keys and tweaked public keys in taproot and suggest the following:
If everything is implicit then the only reason for the first byte of the control block(`c[0]`) is the tapscript leaf version. I suggest that this is moved to be the first OP_CODE of the tapscript itself (i.e. OP_0/OP_1 etc.) That way having the script *tells* you what does it mean without needing to check the control block. That way there's a separation between the tapscript+leaf version and the control block being the merkle path to the script.
On Fri, 9 Aug 2019 at 08:02, Elichai Turkel via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (2 lines)
> > Hi,
Since the idea of implicitly even pubkeys has potentially more general implications, I've started a separate thread [1] about that idea.
Quoted text (2 lines)
> I want to add to John Newbery's suggestion of using implicit even/odd only public keys and tweaked public keys in taproot and suggest the following: > If everything is implicit then the only reason for the first byte of the control block(`c[0]`) is the tapscript leaf version.
That's unfortunately not correct. If we want to maintain batch-verifiability of the taproot tweaking (the Q = P + H(P,m)G relation), we still need a bit in the control block to convey whether a negation was necessary to make P+H(P,m)G even, even if P and Q both have implied-even Y coordinates. Not doing that would require exploring 2^n combinations to batch verify n relations, obviously destroying any performance savings the batch verification had in the first place.
Quoted text (3 lines)
> I suggest that this is moved to be the first OP_CODE of the tapscript itself (i.e. OP_0/OP_1 etc.) > That way having the script *tells* you what does it mean without needing to check the control block. > That way there's a separation between the tapscript+leaf version and the control block being the merkle path to the script.
If we keep the leaf version idea (it's possible to instead just rely entirely on OP_SUCCESSx, and drop leaf versions), my preference is to still keep it separate from script, though just for a fairly banal reason: that way the script consists entirely of opcodes and can be treated uniformly by debug tools, rather than needing to treat the first byte special. I do understand your preference too, but I don't know how it weighs up.
[1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-August/017247.html
Cheers,
Quoted text (1 line)
> I'd prefer to not support P2SH-nested TR. P2SH wrapping was useful for
segwit v0 for compatibility reasons. Most wallets/exchanges/services now support sending to native segwit addresses (https://en.bitcoin.it/wiki/Bech32_adoption) and that will be even more true if Schnorr/Taproot activate in 12+ months time.
Apologies for necroing an ancient thread, but I'm echoing my agreement with John here. We still have plenty of time to have ecosystem upgrade by the time taproot is likely to activate.
On Wed, May 22, 2019 at 10:30 AM John Newbery via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (118 lines)
> Hi, > > > A Taproot output is a SegWit output [...] with > > version number 1, and a 33-byte witness program whose first byte is 0 or > 1. > > Given a secret key k and public key P=(x,y), a signer with the knowledge > of k > can sign for -P=(x,p-y) since -k is the secret key for that point. > Encoding the > y value of the public key therefore adds no security. As an alternative to > providing the y value of the taproot output key Q when constructing the > taproot > output, the signer can provide it when signing. We can also restrict the y > value > of the internal key P to be even (or high, or a quadratic residue). That > gives > us 4 options for how to set the y signs for P and Q. > > 1. Q sign is explictly set in the witness program, P sign is explicitly > set in the control block > => witness program is 33 bytes, 32 possible leaf versions (one for > each pair of 0xc0..0xff) > 2. Q sign is explictly set in the witness program, P sign is implicitly > even > => witness program is 33 bytes, 64 possible leaf versions (one for > each 0xc0..0xff) > 3. Q sign is explictly set in the control block, P sign is explicitly set > in the control block > => witness program is 32 bytes, 16 possible leaf versions (one for > each 4-tuple of 0xc0..0xff) > 4. Q sign is explictly set in the control block, P sign is implicitly even > => witness program is 32 bytes, 32 possible leaf versions (one for > pair of 0xc0..0xff) > > The current proposal uses (1). Using (3) or (4) would reduce the size of a > taproot output by one byte to be the same size as a P2WSH output. That > means > that it's not more expensive for senders compared to sending to P2WSH. > > (Credit to James Chiang for suggesting omitting the y sign from the public > key and > to sipa for pointing out the 4 options above) > > > (native or P2SH-nested, see BIP141) > > I'd prefer to not support P2SH-nested TR. P2SH wrapping was useful for > segwit > v0 for compatibility reasons. Most wallets/exchanges/services now support > sending > to native segwit addresses (https://en.bitcoin.it/wiki/Bech32_adoption) > and that > will be even more true if Schnorr/Taproot activate in 12+ months time. > > On Mon, May 6, 2019 at 2:36 PM Pieter Wuille via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation•org> wrote: > >> Hello everyone, >> >> Here are two BIP drafts that specify a proposal for a Taproot >> softfork. A number of ideas are included: >> >> * Taproot to make all outputs and cooperative spends indistinguishable >> from eachother. >> * Merkle branches to hide the unexecuted branches in scripts. >> * Schnorr signatures enable wallet software to use key >> aggregation/thresholds within one input. >> * Improvements to the signature hashing algorithm (including signing >> all input amounts). >> * Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support >> batch validation. >> * Tagged hashing for domain separation (avoiding issues like >> CVE-2012-2459 in Merkle trees). >> * Extensibility through leaf versions, OP_SUCCESS opcodes, and >> upgradable pubkey types. >> >> The BIP drafts can be found here: >> * https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki >> specifies the transaction input spending rules. >> * https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki >> specifies the changes to Script inside such spends. >> * https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki >> is the Schnorr signature proposal that was discussed earlier on this >> list (See >> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html >> ) >> >> An initial reference implementation of the consensus changes, plus >> preliminary construction/signing tests in the Python framework can be >> found on https://github.com/sipa/bitcoin/commits/taproot. All >> together, excluding the Schnorr signature module in libsecp256k1, the >> consensus changes are around 520 LoC. >> >> While many other ideas exist, not everything is incorporated. This >> includes several ideas that can be implemented separately without loss >> of effectiveness. One such idea is a way to integrate SIGHASH_NOINPUT, >> which we're working on as an independent proposal. >> >> The document explains basic wallet operations, such as constructing >> outputs and signing. However, a wide variety of more complex >> constructions exist. Standardizing these is useful, but out of scope >> for now. It is likely also desirable to define extensions to PSBT >> (BIP174) for interacting with Taproot. That too is not included here. >> >> Cheers, >> >> -- >> Pieter >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists•linuxfoundation•org >> 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 >
Good morning Greg and John,
I am not as sanguine here; SegWit activation was already delayed relative to commonly-broadcast expectations, yet many services *still* do not support sending to SegWit v0 addresses even now.
On the other hand, the major benefit of taproot is the better privacy and homogeneity afforded by Taproot, and supporting both P2SH-wrapped and non-wrapped SegWit v1 addresses simply increases the number of places that a user may be characterized and potentially identified.
Thus while I disagree with your reasoning, I do agree with your conclusion: no P2SH-wrapped SegWit v1.
Regards, ZmnSCPxj
Sent with ProtonMail Secure Email.
‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ On Tuesday, September 17, 2019 12:18 AM, Greg Sanders via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (106 lines)
> > I'd prefer to not support P2SH-nested TR. P2SH wrapping was useful for segwit > v0 for compatibility reasons. Most wallets/exchanges/services now support sending > to native segwit addresses (https://en.bitcoin.it/wiki/Bech32_adoption) and that > will be even more true if Schnorr/Taproot activate in 12+ months time. > > Apologies for necroing an ancient thread, but I'm echoing my agreement with John here. > We still have plenty of time to have ecosystem upgrade by the time taproot is likely to activate. > > On Wed, May 22, 2019 at 10:30 AM John Newbery via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote: > > > Hi, > > > > > A Taproot output is a SegWit output [...] with > > > version number 1, and a 33-byte witness program whose first byte is 0 or 1. > > > > Given a secret key k and public key P=(x,y), a signer with the knowledge of k > > can sign for -P=(x,p-y) since -k is the secret key for that point. Encoding the > > y value of the public key therefore adds no security. As an alternative to > > providing the y value of the taproot output key Q when constructing the taproot > > output, the signer can provide it when signing. We can also restrict the y value > > of the internal key P to be even (or high, or a quadratic residue). That gives > > us 4 options for how to set the y signs for P and Q. > > > > 1. Q sign is explictly set in the witness program, P sign is explicitly set in the control block > > => witness program is 33 bytes, 32 possible leaf versions (one for each pair of 0xc0..0xff) > > 2. Q sign is explictly set in the witness program, P sign is implicitly even > > => witness program is 33 bytes, 64 possible leaf versions (one for each 0xc0..0xff) > > 3. Q sign is explictly set in the control block, P sign is explicitly set in the control block > > => witness program is 32 bytes, 16 possible leaf versions (one for each 4-tuple of 0xc0..0xff) > > 4. Q sign is explictly set in the control block, P sign is implicitly even > > => witness program is 32 bytes, 32 possible leaf versions (one for pair of 0xc0..0xff) > > > > The current proposal uses (1). Using (3) or (4) would reduce the size of a > > taproot output by one byte to be the same size as a P2WSH output. That means > > that it's not more expensive for senders compared to sending to P2WSH. > > > > (Credit to James Chiang for suggesting omitting the y sign from the public key and > > to sipa for pointing out the 4 options above) > > > > > (native or P2SH-nested, see BIP141) > > > > I'd prefer to not support P2SH-nested TR. P2SH wrapping was useful for segwit > > v0 for compatibility reasons. Most wallets/exchanges/services now support sending > > to native segwit addresses (https://en.bitcoin.it/wiki/Bech32_adoption) and that > > will be even more true if Schnorr/Taproot activate in 12+ months time. > > > > On Mon, May 6, 2019 at 2:36 PM Pieter Wuille via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote: > > > > > Hello everyone, > > > > > > Here are two BIP drafts that specify a proposal for a Taproot > > > softfork. A number of ideas are included: > > > > > > * Taproot to make all outputs and cooperative spends indistinguishable > > > from eachother. > > > * Merkle branches to hide the unexecuted branches in scripts. > > > * Schnorr signatures enable wallet software to use key > > > aggregation/thresholds within one input. > > > * Improvements to the signature hashing algorithm (including signing > > > all input amounts). > > > * Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support > > > batch validation. > > > * Tagged hashing for domain separation (avoiding issues like > > > CVE-2012-2459 in Merkle trees). > > > * Extensibility through leaf versions, OP_SUCCESS opcodes, and > > > upgradable pubkey types. > > > > > > The BIP drafts can be found here: > > > * https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki > > > specifies the transaction input spending rules. > > > * https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki > > > specifies the changes to Script inside such spends. > > > * https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki > > > is the Schnorr signature proposal that was discussed earlier on this > > > list (See https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016203.html) > > > > > > An initial reference implementation of the consensus changes, plus > > > preliminary construction/signing tests in the Python framework can be > > > found on https://github.com/sipa/bitcoin/commits/taproot. All > > > together, excluding the Schnorr signature module in libsecp256k1, the > > > consensus changes are around 520 LoC. > > > > > > While many other ideas exist, not everything is incorporated. This > > > includes several ideas that can be implemented separately without loss > > > of effectiveness. One such idea is a way to integrate SIGHASH_NOINPUT, > > > which we're working on as an independent proposal. > > > > > > The document explains basic wallet operations, such as constructing > > > outputs and signing. However, a wide variety of more complex > > > constructions exist. Standardizing these is useful, but out of scope > > > for now. It is likely also desirable to define extensions to PSBT > > > (BIP174) for interacting with Taproot. That too is not included here. > > > > > > Cheers, > > > > > > -- > > > Pieter > > > _______________________________________________ > > > bitcoin-dev mailing list > > > bitcoin-dev@lists•linuxfoundation•org > > > 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 Mon, 16 Sep 2019 at 21:10, ZmnSCPxj via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (9 lines)
> ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ > > I'd prefer to not support P2SH-nested TR. P2SH wrapping was useful for segwit > > v0 for compatibility reasons. Most wallets/exchanges/services now support sending > > to native segwit addresses (https://en.bitcoin.it/wiki/Bech32_adoption) and that > > will be even more true if Schnorr/Taproot activate in 12+ months time. > > > > Apologies for necroing an ancient thread, but I'm echoing my agreement with John here. > > We still have plenty of time to have ecosystem upgrade by the time taproot is likely to activate. > On the other hand, the major benefit of taproot is the better privacy and homogeneity afforded by Taproot, and supporting both P2SH-wrapped and non-wrapped SegWit v1 addresses simply increases the number of places that a user may be characterized and potentially identified.
I'm starting to lean towards not allowing P2SH wrapped Taproot as well.
Given the progress bech32 adoption has made in the past year or so, I don't think adding P2SH support would result in many more software authors deciding to implement receive-to-taproot functionality. And without that advantage, having the option of supporting P2SH wrapping actually risks degrading the privacy goals it aims for (see ZmnSCPxj's argument above).
My main intuition for keeping P2SH is that Segwit was really designed to support both, and I expect that disallowing P2SH would actually require (very slightly) more complex validation code. I don't think this is a sufficiently strong reason, especially as keeping P2SH support does increase the number of combinations software needs to test (both in consensus code and wallets).
Cheers,