-
Notifications
You must be signed in to change notification settings - Fork 822
Implement BIP 340-342 validation (Schnorr/taproot/tapscript) #948
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.
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
Conversation
|
rebase to 4e1a953: Squash fixup commit for Add missing |
Transactions have versions. Witness programs have versions. This replaces the transaction digest "version" with an enum. This will prepare Script and TX for Taproot, which introduces a third TX serialization format. Also renames sigHash functions in tx.js that had their own little confusing version numbers: signatureHashV0 -> signatureHashLegacy signatureHashV1 -> signatureHashWitnessV0
Taproot introduces a sighash algorithm that requires a serialization of the values of ALL the input coins into a transaction. Currently, all the TX check/verify and Script verify methods expect a single coin to be passed in, to check one specific input at a time. This commit updates the signature for several functions throughout the codebase to pass an array of ALL input coins when verifying a TX input. Legacy behavior is preserved by using the index argument to pick out the one coin being verified. Many of the arguments expected by Script.verify() can be found redundantly in either the tx object or the coins array it is passed. Therefore the arguments to this function can be greatly simplified: OLD: verify(input, witness, output, tx, index, value, flags) NEW: verify(tx, index, coins, flags) This refactor also modifies the worker packets that handle input checking (async signing will need to be updated as well in a future commit). All regression tests, bench tests, and script fuzz tests were checked and pass.
Codecov Report
@@ Coverage Diff @@
## master #948 +/- ##
==========================================
+ Coverage 65.66% 66.22% +0.55%
==========================================
Files 156 157 +1
Lines 26082 26452 +370
==========================================
+ Hits 17128 17519 +391
+ Misses 8954 8933 -21
Continue to review full report at Codecov.
|
|
It's alive!! Big rebase to ee27f2e
The new test vectors uncovered some bugs from the original PR:
Since the tests are still not 100% passing, I'm leaving this PR as a draft and will rebase again once I iron out the last few bugs. |
Will be needed to lexicographically compare adjacent merkele branches in Taproot control block.
Reference from Bitcoin Core src/script/interpreter.h
// Taproot/Tapscript validation (BIPs 341 & 342)
//
SCRIPT_VERIFY_TAPROOT = (1U << 17),
// Making unknown Taproot leaf versions non-standard
//
SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION = (1U << 18),
// Making unknown OP_SUCCESS non-standard
SCRIPT_VERIFY_DISCOURAGE_OP_SUCCESS = (1U << 19),
// Making unknown public key versions (in BIP 342 scripts) non-standard
SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_PUBKEYTYPE = (1U << 20)
Like its caller verify(), this function will need the values of all the input coins to compute the signature hash for Taproot spends. Unlike verify(), we don't pull the "output" script from the coin of the input being checked, because that script may have actually come from a P2SH redeem script (in the input itself).
This is especially important for Script.isUnknown() which calls Script.getType(), and will cause TX.hasStandardInputs() to fail if that type is undefined. TODO: Address, Witness and Input methods that "guess" their corresponding output should be checked for interference by new Taproot witness patterns, and expanded if possible. New functions in Script/common.js like "isSignatureEncoding()" will need to be added.
This extends Script.verifyProgram() to cover version 1 (Taproot) rules. Tests cover standard and mandatory flags (mempool and block, respectively). Note at this point only key path spending is fully verified.
|
rebase to f3b2927: Various bug fixes and new comments:
The testing suite is now completely passing, so this PR is ready for review! 🎉 TODO:
|
This branch is modeled after bitcoin/bitcoin#17977 which is the current work-in-progress branch to deploy Taproot and related rules to Bitcoin Core.
The reference implementation has only begun review and the BIPs themselves are subject to changes which will have to be applied in the code. Some updates may require changes in bcrypto.
(In fact, bcrypto currently only offers BIP340 Schnorr support in JavaScript, not native code).At this time, bcrypto has already made the changes for even-Y instead of square-Y. When the reference branch gets updated I can regenerate the test vectors and rebase.As such, this PR will require long-term maintenance and paying close attention to the reference implementation, including hard-to-spot force-push updates.
There are rules in the code that are not documented in the BIPs (specifically, standardness rules).
There are rules in the code that are not covered by tests. I plan on writing tests, if I can, for the Bitcoin Core branch, then adding them back to this PR if they are considered appropriate. From what I can tell so far the untested rules include some standardenss changes, taproot-embedded-in-P2SH (which is not Taproot and therefore just an anyone-can-spend), and the use of
OP_CHECKSIGADDwith more than one key.The test cases for this PR were generated by a modified branch of the reference implementation. The Bitcoin Test Framework generates (in memory) a huge amount of transactions using random values and conditions to cover the new rules. The modified branch dumps all the UTXOs and spending transactions into a JSON file along with metadata so that bcoin can be tested the same way. The Bitcoin Test Framework has two sets of tests: a round of single-output spends, and a round of multiple-output spends. The former set creates a somewhat small (635 kB) JSON file, and that is included in this branch as a test vector. The latter creates a huge JSON file - almost 16 MB. I have generated this file and tested bcoin against it locally (
taproot-test.jscan run on either file) but decided not to commit a 16MB test vector. The result of running the multiple-output test is a fabulous report of18010 passing.