History for Taproot PR #19953

[sipa]

I'm opening this PR to give a convenient way to see the history #19953 goes through, as review comments get addressed.

The intent is to only add commits here, and use merge commit when the real PR undergoes a rebase.

It is marked draft as this branch isn't expected to be merged.

_{PREV="$(git rev-parse HEAD)"; git log --oneline upstream/master..HEAD | while read C L; do if [ "d${L:0:14}" == "d--- [TAPROOT] " ]; then if [ "d$PREV" != "" ]; then git diff --shortstat $C..$PREV | (read _ _ _ ADD _ DEL _; echo "### ${L:14:-4} (https://github.com/sipa/bitcoin/compare/$C...$PREV) [+$ADD -$DEL]:"); echo; fi; PREV=$C; PREVL=$L; else echo -n " * $C **${L}**: "; git show "$C" --format="%b" -s | awk '/^$/{exit} 1' | tr $'\n' ' '; echo; fi; done | tac}

Initial version (2020-09-20) [+2730 -118]

• 0daa370 scripted-diff: put ECDSA in name of signature functions: In preparation for adding Schnorr versions of CheckSig, VerifySignature, and ComputeEntry, give them an ECDSA specific name.
• 135f12a refactor: rename scriptPubKey in VerifyWitnessProgram to exec_script: The old name is confusing, as it doesn't store a scriptPubKey, but the actually executed script.
• f4d16cf refactor: keep spent outputs in PrecomputedTransactionData: 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.
• 60ce123 Add TaggedHash function (BIP 340): This adds the TaggedHash function as defined by BIP340 to the hash module, which is used in BIP340 and BIP341 to produce domain-separated hashes.
• 34da219 Implement Taproot signature hashing (BIP 341): This implements the new sighashing scheme from BIP341, with all relevant whole-transaction values precomputed once and cached.
• 52ddb42 Support for Schnorr signatures and integration in SignatureCheckers (BIP 340): This enables the schnorrsig module in libsecp256k1, adds the relevant types and functions to src/pubkey, as well as in higher-level SignatureChecker classes. The (verification side of the) BIP340 test vectors is also added.
• 828aed0 Implement Taproot validation (BIP 341): This includes key path spending and script path spending, but not the Tapscript execution implementation (leaf 0xc0 remains unemcumbered in this commit).
• a39a7ec Use ScriptExecutionData to pass through annex hash: Instead of recomputing the annex hash every time a signature is verified, compute it once and cache it in a new ScriptExecutionData structure.
• ebce982 Implement Tapscript script validation rules (BIP 342): This adds a new SigVersion::TAPSCRIPT, makes the necessary interpreter changes to make it implement BIP342, and uses them for leaf version 0xc0 in Taproot script path spends.
• 812c856 Make Taproot spends standard + policy limits: This adds a TxoutType::WITNESS_V1_TAPROOT for P2TR outputs, and permits spending them in standardness rules. No corresponding CTxDestination is added for it, as that isn't needed until we want wallet integration. The taproot validation flags are also enabled for mempool transactions, and standardness rules are added (stack item size limit, no annexes).
• 5ee49fd Activate Taproot/Tapscript on regtest (BIP 341, BIP 342): Define a versionbits-based activation for the new consensus rules on regtest. No activation or activation mechanism is defined for testnet or mainnet.
• 697d461 [TESTS] Add BIP340 Schnorr signature support to test framework: Add a pure Python implementation of BIP340 signing and verification, tested against the BIP's test vectors.
• fd6e288 [TESTS] Functional tests for Schnorr/Taproot/Tapscript: A large functional test is added that automatically generates random transactions which exercise various aspects of the new rules, and verifies they are accepted into the mempool (when appropriate), and correctly accepted/rejected in (Python-constructed) blocks.
• 64030b1 [TESTS] Add minimized test vector as unit test: This adds a relatively small set of test cases for the BIP341/BIP342 script validation rules as a unit test. The tests were generated by modifying the feature_taproot.py randomized tester to dump the constructed transactions and witnesses used, and using the fuzzing framework to minimize it.

Updates 2020-09-22 (sipa/bitcoin@33b6a13...076dfd9) [+38 -38]:

• 4f5272c Document length assumption in XOnlyPubKey::VerifySchnorr correctly:
• 672b1af Make IsOpSuccess match BIP text more closely:
• c22d75b Use OP_SUCCESSx instead of SUCCESSx in error message:
• 550edc0 Simplify/clarify tweak_add_{priv,pub}_key in tests:
• 076dfd9 Python assert does not need parens:

Update: test vectors in qa-assets (sipa/bitcoin@3889288...9dfcd36) [+98 -43]:

• 00d8575 Always clone qa-assets repo in CI, but shallowly:
• 35fc47b Improve script unit test and use qa-assets JSON:

Updates 2020/09/23 (sipa/bitcoin@9dfcd36...7d694f8) [+6 -110]:

• cdc57ba Script interpreter nits:
• 2612d16 Document implicit CLEANSTACK/MINIMALIF in witv0/tapscript execution:
• 7d694f8 Remove script_taproot_tests (moved to qa-assets):

Updates 2020/09/24 (sipa/bitcoin@b5d2f3b...1ec9ce2) [+28 -13]:

• 4181a0c Exit bip143/341 checking loop early:
• 4e6c200 Make SignatureHashCache take cache reference instead of pointer:
• 29bf92a Use separate script error for tapscript MINIMALIF:
• 1ec9ce2 Add a test for consensus CLEANSTACK in tapscript:

Updates 2020/10/01 (sipa/bitcoin@8e8b458...99c50a6) [+294 -27]:

• ba4ac3e Improve some code comments:
• c634f7e Compute witnesses only once for each input in feature_taproot.py: Instead of re-evaluating the entire signing logic for every input, for every attempt, compute them once and reuse them.
• 9e963a0 Run legacy tests with both compressed and uncompressed keys:
• 687c91a Use a separate prefix for legacy tests that need taproot validation tests:
• 6d23fd6 Add support for dumping generated test cases:
• 7d5fd3c Add fuzz 'test' to minimize script_assets_test.json:

Merge with master 2020/10/02 (sipa/bitcoin@99c50a6...6cf077d) [+21666 -4524]:

• 3103136 Merge remote-tracking branch 'upstream/master' into taproot-history:
• 6cf077d Fix expected error message in feature_taproot.py:

Updates 2020/10/06 (sipa/bitcoin@490b974...10b9a48) [+11 -7]:

• 4ade578 Avoid a ScriptExecutionData copy in EvalScript:
• 10b9a48 Remove inadvertantly added newlines:

Updates 2020/10/07 (sipa/bitcoin@68ebf4a...8362324) [+21 -17]:

• 3265f14 Variable naming/typing/calling improvements:
• c171004 Use more constexpr:
• 2ea6a0a Consistent comment style:
• 8362324 Add comments referencing the BIPs:

Updates 2020/10/08 (sipa/bitcoin@5a78976...67750a3) [+85 -72]:

• fb6bc8a Decide key_version based on sigversion instead of passing through:
• 67750a3 Report more detailed signature validation errors:

Updates 2020/10/11 (sipa/bitcoin@ce24bbb...7029ff5) [+13 -15]:

• 2127387 Add extra assertion on spent_outputs size:
• 11c05b4 Rename fSuccess -> success in comments:
• 1a464c6 Small fixes to feature_taproot.py:
• 7029ff5 Some style fixes:

Updates 2020/10/12 (sipa/bitcoin@36f4fa5...4e2ac63) [+5 -5]:

• 34a93d7 Really rename fuccess -> success in comments:
• 4e2ac63 Pass tapleaf_hash by reference to VerifyTaprootCommitment: