Skip to content

Implement BIP 340-342 validation (Schnorr/taproot/tapscript) #17977

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
wants to merge 13 commits into from
Closed

Implement BIP 340-342 validation (Schnorr/taproot/tapscript) #17977

wants to merge 13 commits into from

Conversation

sipa
Copy link
Member

@sipa sipa commented Jan 21, 2020 •
edited
Loading

This is an implementation of the Schnorr/taproot consensus rules proposed by BIPs 340, 341, and 342.

It consists of:

This does not include any wallet support.

Related PRs and PRs that were extracted from this and submitted separately: #18002 #16902 #18388 #18401 #18422 #18675 #19228

Dependencies:

TODO:

  • Tests for pre-activation (verify that consensus behavior doesn't change until flag is enabled)
  • Extract small & fast BIP341/BIP342 test vectors with good coverage out of the programmatic & slow feature_taproot.py test

@sipa sipa force-pushed the taproot branch 4 times, most recently from c9b9958 to 7b11d12 Compare January 21, 2020 23:44
@DrahtBot
Copy link
Contributor

DrahtBot commented Jan 21, 2020 •
edited
Loading

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

@sipa sipa force-pushed the taproot branch 2 times, most recently from 4ba9fcf to 1f499c5 Compare January 22, 2020 04:45
junderw
junderw reviewed Jan 22, 2020
View reviewed changes
kallewoof
kallewoof reviewed Jan 22, 2020
View reviewed changes
@ghost ghost mentioned this pull request Jan 22, 2020
Closed
14 tasks
ghost
ghost reviewed Jan 22, 2020
View reviewed changes
Copy link

@ghost ghost left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

As the BIPs have now been assigned numbers, this changes...:

  • BIP-Schnorr to BIP-340
  • BIP-Taproot to BIP-341
  • BIP-Tapscript to BIP-342

ghost
ghost reviewed Jan 22, 2020
View reviewed changes
skwp
skwp reviewed Jan 22, 2020
View reviewed changes
skwp
skwp reviewed Jan 22, 2020
View reviewed changes
@sipa
Copy link
Member Author

sipa commented Jan 22, 2020

@MaxHillebrand A few overall comments:

  • I don't think all references to (bip-)taproot/tapscript/schnorr should be changed to the BIP numbers; in some cases maybe we should just drop the "bip-" prefix (e.g. I think talking about a "taproot spend" is more clear than "bip341 spend").
  • All changes in the src/secp256k1 directory should go to Add schnorrsig module which implements BIP-340 compliant signatures bitcoin-core/secp256k1#558 instead (the src/secp256k1 is a git subtree imported from there).
  • The "BIPSchnorr" and "BIPSchnorrDerive" tagged hash tags are part of the spec, which I don't think should be changed.

@ghost
Copy link

ghost commented Jan 22, 2020

Thanks @sipa, I agree with your comments.
I have deleted my suggestions to change the tagged hashes, the others are still open. Please ACK/NACK and commit what you think is correct.

constcast-glitch
constcast-glitch reviewed Jan 22, 2020
View reviewed changes
Empact
Empact reviewed Jan 22, 2020
View reviewed changes
nopara73
nopara73 reviewed Jan 22, 2020
View reviewed changes
nopara73
nopara73 reviewed Jan 22, 2020
View reviewed changes
nopara73
nopara73 reviewed Jan 22, 2020
View reviewed changes
nopara73
nopara73 reviewed Jan 22, 2020
View reviewed changes
nopara73
nopara73 reviewed Jan 22, 2020
View reviewed changes
nopara73
nopara73 reviewed Jan 22, 2020
View reviewed changes
Empact
Empact reviewed Jan 22, 2020
View reviewed changes
Empact
Empact reviewed Jan 22, 2020
View reviewed changes
ghost
ghost reviewed Jan 22, 2020
View reviewed changes
Copy link

@ghost ghost left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Similar to Taproot, this unifies the upper case Tapscript consistently in the comments.

Empact
Empact reviewed Jan 22, 2020
View reviewed changes
@sipa sipa mentioned this pull request Sep 11, 2020
Merged
@sipa
Copy link
Member Author

sipa commented Sep 11, 2020

Rebased on top of #19944.

fanquake added a commit that referenced this pull request Sep 14, 2020
@fanquake
Merge #19944: Update secp256k1 subtree (including BIP340 support)
ba4b3fb 
b9c1a76 Squashed 'src/secp256k1/' changes from 2ed54da..8ab24e8 (Pieter Wuille)

Pull request description:

  This updates our src/secp256k1 subtree to the latest libsecp256k1 upstream version.

  As it adds BIP340 support (see bitcoin-core/secp256k1#558), this is a prerequisite for #17977. In particular, it contains:
  * A few generic library improvements
  * Support for x-only public keys as used by BIP340.
  * Support for "key pair" objects, making signing more efficient by using a precomputed public key.
  * Signing support for BIP340 Schnorr (single-party) signatures.
  * Verification support for BIP340 Schnorr signatures.
  * Support for verifying tweaked x-only keys, as used by BIP341's Taproot construction.

  Things that are not included:
  * MuSig, nor any kind of multisignatures, threshold signatures, ... on top.
  * Batch verification.
  * Support for variable-length messages in BIP340 (which are still being discussed, but won't affect BIP341, or Bitcoin Core).
  * A few more generic improvements that are still in the pipeline, including faster modular inversions.

ACKs for top commit:
  instagibbs:
    ACK 894fb33
  fanquake:
    ACK 894fb33. Any Valgrind concerns will be addressed upstream, see discussion in bitcoin-core/secp256k1#813, and if necessary, can be pulled into our tree prior to the 0.21.0 branch off. They are not a blocker for merging this PR in it's current state.
  benthecarman:
    ACK `894fb33`

Tree-SHA512: 6dc992f4477069b7fbd223316f1be955750923be1479c38adad2312649fdca1f316edb375c42ef9d97cea2407caaef49fb8c93abd6c037fe1a522910cbbc2479
sipa and others added 8 commits September 13, 2020 21:05
@sipa
Add TaggedHash function (BIP 340)
3430eae
@sipa
Keep spent outputs in PrecomputedTransactionData during validation
ba285d8 
A BIP-341 signature message may commit to the scriptPubKeys and amounts
of all spent outputs (including other ones than the input being signed
for spends), so keep them available to signature hashing code.
@jl2012 @sipa
Implement Taproot signature hashing (BIP 341)
b63f19a 
Includes changes to PrecomputedTransactionData by Pieter Wuille.
@sipa
refactor: put ECDSA in name of signature function
466b022
@sipa
Support for Schnorr signatures and integration in SignatureCheckers (…
76f2e3e 
…BIP 340)
@sipa
refactor: rename scriptPubKey in VerifyWitnessProgram to exec_script
ddfc365 
The old name is confusing, as it doesn't store a scriptPubKey, but the
actually executed script.
@sipa
Implement Taproot validation (BIP 341)
804ff64 
This includes key path spending and script path spending, but not the
Tapscript execution implementation.

Includes constants for various aspects of the consensus rules suggested
by Jeremy Rubin.
@sipa
Use ScriptExecutionData to pass through annex hash
d384d67
@sipa sipa closed this Sep 14, 2020
@sipa
Copy link
Member Author

sipa commented Sep 14, 2020

Closing in favor of new PR(s), as discussed here.

@sipa sipa mentioned this pull request Sep 14, 2020
Merged
sidhujag pushed a commit to syscoin/syscoin that referenced this pull request Sep 15, 2020
@fanquake
Merge bitcoin#19944: Update secp256k1 subtree (including BIP340 support)
711b819 
b9c1a76 Squashed 'src/secp256k1/' changes from 2ed54da..8ab24e8 (Pieter Wuille)

Pull request description:

  This updates our src/secp256k1 subtree to the latest libsecp256k1 upstream version.

  As it adds BIP340 support (see bitcoin-core/secp256k1#558), this is a prerequisite for bitcoin#17977. In particular, it contains:
  * A few generic library improvements
  * Support for x-only public keys as used by BIP340.
  * Support for "key pair" objects, making signing more efficient by using a precomputed public key.
  * Signing support for BIP340 Schnorr (single-party) signatures.
  * Verification support for BIP340 Schnorr signatures.
  * Support for verifying tweaked x-only keys, as used by BIP341's Taproot construction.

  Things that are not included:
  * MuSig, nor any kind of multisignatures, threshold signatures, ... on top.
  * Batch verification.
  * Support for variable-length messages in BIP340 (which are still being discussed, but won't affect BIP341, or Bitcoin Core).
  * A few more generic improvements that are still in the pipeline, including faster modular inversions.

ACKs for top commit:
  instagibbs:
    ACK 894fb33
  fanquake:
    ACK 894fb33. Any Valgrind concerns will be addressed upstream, see discussion in bitcoin-core/secp256k1#813, and if necessary, can be pulled into our tree prior to the 0.21.0 branch off. They are not a blocker for merging this PR in it's current state.
  benthecarman:
    ACK `894fb33`

Tree-SHA512: 6dc992f4477069b7fbd223316f1be955750923be1479c38adad2312649fdca1f316edb375c42ef9d97cea2407caaef49fb8c93abd6c037fe1a522910cbbc2479
laanwj added a commit that referenced this pull request Oct 15, 2020
@laanwj
Merge #19953: Implement BIP 340-342 validation (Schnorr/taproot/tapsc…
3caee16 
…ript)

0e2a5e4 tests: dumping and minimizing of script assets data (Pieter Wuille)
4567ba0 tests: add generic qa-asset-based script verification unit test (Pieter Wuille)
f06e6d0 tests: functional tests for Schnorr/Taproot/Tapscript (Pieter Wuille)
3c22663 tests: add BIP340 Schnorr signature support to test framework (Pieter Wuille)
206fb18 --- [TAPROOT] Tests --- (Pieter Wuille)
d7ff237 Activate Taproot/Tapscript on regtest (BIP 341, BIP 342) (Pieter Wuille)
e9a021d Make Taproot spends standard + policy limits (Pieter Wuille)
865d2c3 --- [TAPROOT] Regtest activation and policy --- (Pieter Wuille)
72422ce Implement Tapscript script validation rules (BIP 342) (Johnson Lau)
330de89 Use ScriptExecutionData to pass through annex hash (Pieter Wuille)
8bbed4b Implement Taproot validation (BIP 341) (Pieter Wuille)
0664f5f Support for Schnorr signatures and integration in SignatureCheckers (BIP 340) (Pieter Wuille)
5de246c Implement Taproot signature hashing (BIP 341) (Johnson Lau)
9eb5908 Add TaggedHash function (BIP 340) (Pieter Wuille)
450d2b2 --- [TAPROOT] BIP340/341/342 consensus rules --- (Pieter Wuille)
5d62e3a refactor: keep spent outputs in PrecomputedTransactionData (Pieter Wuille)
8bd2b4e refactor: rename scriptPubKey in VerifyWitnessProgram to exec_script (Pieter Wuille)
107b57d scripted-diff: put ECDSA in name of signature functions (Pieter Wuille)
f8c099e --- [TAPROOT] Refactors --- (Pieter Wuille)

Pull request description:

  This is an implementation of the Schnorr/taproot consensus rules proposed by BIPs [340](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki), [341](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki), and [342](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki).

  See the list of commits [below](#19953 (comment)). No signing or wallet support of any kind is included, as testing is done entirely through the Python test framework.

  This is a successor to #17977 (see discussion following [this comment](#17977 (comment))), and will have further changes squashed/rebased. The history of this PR can be found in #19997.

ACKs for top commit:
  instagibbs:
    reACK 0e2a5e4
  benthecarman:
    reACK 0e2a5e4
  kallewoof:
    reACK 0e2a5e4
  jonasnick:
    ACK 0e2a5e4 almost only looked at bip340/libsecp related code
  jonatack:
    ACK 0e2a5e4 modulo the last four commits (tests) that I plan to finish reviewing tomorrow
  fjahr:
    reACK 0e2a5e4
  achow101:
    ACK 0e2a5e4

Tree-SHA512: 1b00314450a2938a22bccbb4e177230cf08bd365d72055f9d526891f334b364c997e260c10bc19ca78440b6767712c9feea7faad9a1045dd51a5b96f7ca8146e
sidhujag pushed a commit to syscoin/syscoin that referenced this pull request Oct 16, 2020
@laanwj
Merge bitcoin#19953: Implement BIP 340-342 validation (Schnorr/taproo…
ca9eeb3 
…t/tapscript)

0e2a5e4 tests: dumping and minimizing of script assets data (Pieter Wuille)
4567ba0 tests: add generic qa-asset-based script verification unit test (Pieter Wuille)
f06e6d0 tests: functional tests for Schnorr/Taproot/Tapscript (Pieter Wuille)
3c22663 tests: add BIP340 Schnorr signature support to test framework (Pieter Wuille)
206fb18 --- [TAPROOT] Tests --- (Pieter Wuille)
d7ff237 Activate Taproot/Tapscript on regtest (BIP 341, BIP 342) (Pieter Wuille)
e9a021d Make Taproot spends standard + policy limits (Pieter Wuille)
865d2c3 --- [TAPROOT] Regtest activation and policy --- (Pieter Wuille)
72422ce Implement Tapscript script validation rules (BIP 342) (Johnson Lau)
330de89 Use ScriptExecutionData to pass through annex hash (Pieter Wuille)
8bbed4b Implement Taproot validation (BIP 341) (Pieter Wuille)
0664f5f Support for Schnorr signatures and integration in SignatureCheckers (BIP 340) (Pieter Wuille)
5de246c Implement Taproot signature hashing (BIP 341) (Johnson Lau)
9eb5908 Add TaggedHash function (BIP 340) (Pieter Wuille)
450d2b2 --- [TAPROOT] BIP340/341/342 consensus rules --- (Pieter Wuille)
5d62e3a refactor: keep spent outputs in PrecomputedTransactionData (Pieter Wuille)
8bd2b4e refactor: rename scriptPubKey in VerifyWitnessProgram to exec_script (Pieter Wuille)
107b57d scripted-diff: put ECDSA in name of signature functions (Pieter Wuille)
f8c099e --- [TAPROOT] Refactors --- (Pieter Wuille)

Pull request description:

  This is an implementation of the Schnorr/taproot consensus rules proposed by BIPs [340](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki), [341](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki), and [342](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki).

  See the list of commits [below](bitcoin#19953 (comment)). No signing or wallet support of any kind is included, as testing is done entirely through the Python test framework.

  This is a successor to bitcoin#17977 (see discussion following [this comment](bitcoin#17977 (comment))), and will have further changes squashed/rebased. The history of this PR can be found in bitcoin#19997.

ACKs for top commit:
  instagibbs:
    reACK bitcoin@0e2a5e4
  benthecarman:
    reACK 0e2a5e4
  kallewoof:
    reACK 0e2a5e4
  jonasnick:
    ACK 0e2a5e4 almost only looked at bip340/libsecp related code
  jonatack:
    ACK 0e2a5e4 modulo the last four commits (tests) that I plan to finish reviewing tomorrow
  fjahr:
    reACK 0e2a5e4
  achow101:
    ACK 0e2a5e4

Tree-SHA512: 1b00314450a2938a22bccbb4e177230cf08bd365d72055f9d526891f334b364c997e260c10bc19ca78440b6767712c9feea7faad9a1045dd51a5b96f7ca8146e
sidhujag pushed a commit to syscoin-core/syscoin that referenced this pull request Nov 10, 2020
@laanwj
Merge bitcoin#18002: Abstract out script execution out of VerifyWitne…
111c686 
…ssProgram()

c8e24dd [REFACTOR] Abstract out script execution out of VerifyWitnessProgram() (Pieter Wuille)

Pull request description:

  This is a refactoring cherry-picked out of bitcoin#17977. As it touches consensus code, I don't think this would ordinarily meet the bar for review cost vs benefit. However, it simplifies the changes for Taproot significantly, and if it's going to be necessitated by inclusion of that code, I may as well give it some additional attention by PRing it independently.

ACKs for top commit:
  fjahr:
    Re-ACK c8e24dd
  theStack:
    re-ACK bitcoin@c8e24dd
  Empact:
    Code Review Re-ACK bitcoin@c8e24dd
  ajtowns:
    ACK c8e24dd
  jnewbery:
    ACK c8e24dd
  jonatack:
    ACK c8e24dd

Tree-SHA512: 96c2aa5d2f9c7c802bcc008f5cde55b1dfedfaf42e34101331e6c0d594acdf6437661102dc939718f0877c20451336855dfbaa8aa8f57d9e722a7fa7329e3a46
UdjinM6 pushed a commit to UdjinM6/dash that referenced this pull request Aug 10, 2021
@fanquake @UdjinM6
Merge bitcoin#19944: Update secp256k1 subtree (including BIP340 support)
c2ab828 
b9c1a76 Squashed 'src/secp256k1/' changes from 2ed54da..8ab24e8 (Pieter Wuille)

Pull request description:

  This updates our src/secp256k1 subtree to the latest libsecp256k1 upstream version.

  As it adds BIP340 support (see bitcoin-core/secp256k1#558), this is a prerequisite for bitcoin#17977. In particular, it contains:
  * A few generic library improvements
  * Support for x-only public keys as used by BIP340.
  * Support for "key pair" objects, making signing more efficient by using a precomputed public key.
  * Signing support for BIP340 Schnorr (single-party) signatures.
  * Verification support for BIP340 Schnorr signatures.
  * Support for verifying tweaked x-only keys, as used by BIP341's Taproot construction.

  Things that are not included:
  * MuSig, nor any kind of multisignatures, threshold signatures, ... on top.
  * Batch verification.
  * Support for variable-length messages in BIP340 (which are still being discussed, but won't affect BIP341, or Bitcoin Core).
  * A few more generic improvements that are still in the pipeline, including faster modular inversions.

ACKs for top commit:
  instagibbs:
    ACK 894fb33
  fanquake:
    ACK 894fb33. Any Valgrind concerns will be addressed upstream, see discussion in bitcoin-core/secp256k1#813, and if necessary, can be pulled into our tree prior to the 0.21.0 branch off. They are not a blocker for merging this PR in it's current state.
  benthecarman:
    ACK `894fb33`

Tree-SHA512: 6dc992f4477069b7fbd223316f1be955750923be1479c38adad2312649fdca1f316edb375c42ef9d97cea2407caaef49fb8c93abd6c037fe1a522910cbbc2479
5tefan pushed a commit to 5tefan/dash that referenced this pull request Aug 12, 2021
@fanquake @5tefan
Merge bitcoin#19944: Update secp256k1 subtree (including BIP340 support)
abf9ac8 
b9c1a76 Squashed 'src/secp256k1/' changes from 2ed54da..8ab24e8 (Pieter Wuille)

Pull request description:

  This updates our src/secp256k1 subtree to the latest libsecp256k1 upstream version.

  As it adds BIP340 support (see bitcoin-core/secp256k1#558), this is a prerequisite for bitcoin#17977. In particular, it contains:
  * A few generic library improvements
  * Support for x-only public keys as used by BIP340.
  * Support for "key pair" objects, making signing more efficient by using a precomputed public key.
  * Signing support for BIP340 Schnorr (single-party) signatures.
  * Verification support for BIP340 Schnorr signatures.
  * Support for verifying tweaked x-only keys, as used by BIP341's Taproot construction.

  Things that are not included:
  * MuSig, nor any kind of multisignatures, threshold signatures, ... on top.
  * Batch verification.
  * Support for variable-length messages in BIP340 (which are still being discussed, but won't affect BIP341, or Bitcoin Core).
  * A few more generic improvements that are still in the pipeline, including faster modular inversions.

ACKs for top commit:
  instagibbs:
    ACK 894fb33
  fanquake:
    ACK 894fb33. Any Valgrind concerns will be addressed upstream, see discussion in bitcoin-core/secp256k1#813, and if necessary, can be pulled into our tree prior to the 0.21.0 branch off. They are not a blocker for merging this PR in it's current state.
  benthecarman:
    ACK `894fb33`

Tree-SHA512: 6dc992f4477069b7fbd223316f1be955750923be1479c38adad2312649fdca1f316edb375c42ef9d97cea2407caaef49fb8c93abd6c037fe1a522910cbbc2479
PhotoshiNakamoto added a commit to PhotonicBitcoin/pBTC-core that referenced this pull request Dec 11, 2021
@PhotoshiNakamoto
[consensus] MOVEONLY: Move single-sig checking EvalScript code to Eva…
6a91740 
…lChecksig

Bitcoin Core PR:bitcoin/bitcoin#18422

Pull request description:

  This is another small refactor pulled out of the Schnorr/Taproot PR bitcoin/bitcoin#17977.

  This is in preparation for adding different signature verification rules,
  specifically tapscript (BIP 342), which interprets opcode 0xac and 0xad
  as Schnorr signature verifications.
@bitcoin bitcoin locked as resolved and limited conversation to collaborators Feb 15, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Reviewers
27 more reviewers

@elichai elichai elichai left review comments

@v1048576 v1048576 v1048576 left review comments

@Sjors Sjors Sjors left review comments

@kallewoof kallewoof kallewoof left review comments

@theuni theuni theuni left review comments

@gmaxwell gmaxwell gmaxwell left review comments

@JeremyRubin JeremyRubin JeremyRubin left review comments

@jnewbery jnewbery jnewbery left review comments

@real-or-random real-or-random real-or-random left review comments

@luke-jr luke-jr luke-jr left review comments

@Kixunil Kixunil Kixunil left review comments

@fjahr fjahr fjahr left review comments

@constcast-glitch constcast-glitch constcast-glitch left review comments

@Empact Empact Empact left review comments

@StEvUgnIn StEvUgnIn StEvUgnIn left review comments

@brmdbr brmdbr brmdbr left review comments

@instagibbs instagibbs instagibbs left review comments

@maflcko maflcko maflcko left review comments

@skwp skwp skwp left review comments

@nopara73 nopara73 nopara73 left review comments

@junderw junderw junderw left review comments

@michaelfolkson michaelfolkson michaelfolkson left review comments

@ariard ariard ariard left review comments

@pinheadmz pinheadmz pinheadmz left review comments

@ShawkiS ShawkiS ShawkiS approved these changes

@Viral Viral Viral approved these changes

Reviewers whose approvals may not affect merge requirements
Assignees
No one assigned
Labels
Consensus
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.