Skip to content

Conversation

@pinheadmz
Copy link
Member

@pinheadmz pinheadmz commented Feb 26, 2020

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_CHECKSIGADD with 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.js can 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 of 18010 passing.

@bcoin-org bcoin-org deleted a comment from SiZapPaaiGwat Feb 26, 2020
@pinheadmz
Copy link
Member Author

pinheadmz commented Mar 10, 2020

rebase to 4e1a953:

Squash fixup commit for isTaprootHashType()

Add missing 'TAPSCRIPT' in digestsByVal

@pinheadmz
Copy link
Member Author

rebase to 96eb409:

remove JSONify witness stack (helpful for testing, see #895)

squash updated test vectors

Matthew Zipkin added 4 commits May 22, 2022 16:27
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-commenter
Copy link

codecov-commenter commented May 22, 2022

Codecov Report

Merging #948 (f3dce1f) into master (f8118d0) will increase coverage by 0.55%.
The diff coverage is 93.25%.

@@            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     
Impacted Files Coverage Δ
lib/protocol/networks.js 100.00% <ø> (ø)
lib/workers/workerpool.js 66.31% <0.00%> (ø)
lib/workers/packets.js 37.83% <8.33%> (-0.11%) ⬇️
lib/workers/jobs.js 51.92% <33.33%> (ø)
lib/utils/util.js 66.66% <83.33%> (+5.55%) ⬆️
lib/primitives/tx.js 87.35% <94.91%> (+3.96%) ⬆️
lib/script/witness.js 70.07% <96.42%> (+6.77%) ⬆️
lib/script/script.js 82.09% <97.74%> (+2.12%) ⬆️
lib/blockchain/chain.js 69.08% <100.00%> (+0.19%) ⬆️
lib/primitives/outpoint.js 98.55% <100.00%> (+2.34%) ⬆️
... and 10 more

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update f8118d0...f3dce1f. Read the comment docs.

@pinheadmz
Copy link
Member Author

It's alive!! Big rebase to ee27f2e

The new test vectors uncovered some bugs from the original PR:

  • Since BIP341 sighashing uses all single SHA256 (and legacy, witnessV0 sighashing uses double-SHA256) the caches for these different operations must be kept separate. You can see the Bitcoin Core version of this here.

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.

Matthew Zipkin added 9 commits May 25, 2022 09:46
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.
@pinheadmz
Copy link
Member Author

rebase to f3b2927:

Various bug fixes and new comments:

  • fixed taproot-test getTests() which was combining vectors together and making a mess
  • updated certain error codes with names that match Bitcoin Core (like SCHNORR_SIG_HASHTYPE)
  • fixed which tapscript witness items get checked against policy size limits
  • fixed evalChecksigTapscript() handling of empty scripts and return values: explanation

The testing suite is now completely passing, so this PR is ready for review! 🎉

TODO:

  • activation logic
  • 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.

@pinheadmz pinheadmz marked this pull request as ready for review May 25, 2022 15:07
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants