[DO NOT MERGE] Schnorr batch verification for blocks

fjahr commented at 5:06 pm on February 27, 2024: contributor

This is a simple draft implementation of Schnorr signature batch verification in blocks, put here for conceptual discussion, and collaborative benchmarking. Most of code added here is from the secp256k1 implementation.

The secp256k1 code is still under review itself, please spend some time giving feedback on the API etc. if you can:

TODOs

Fix functional/feature_taproot.py
Extensive benchmarking using ConnectBlock() tracing
Add unit tests
Batch taproot tweak verification as well
Conceptual discussion in what form this realistically could be introduced into the code base, and later, a release

Squashed 'src/secp256k1/' changes from efe85c70a2..282757398c

282757398c WIP: Silent merge conflicts
42dc5a9494 batch: Generate graphs for batch verification speed up
fd9f58842f batch, extrakeys: Add benchmark for batch verify and `tweak_add_check`
94df19cd26 batch: Add tests for `batch_add_*` APIs
32d3f93683 batch,ecmult: Add tests for core batch APIs and `strauss_batch` refactor
30d5b37526 batch: Add API usage example
014c1501e2 batch: Add `batch_add_*` APIs
57f1c10a48 batch, ecmult: Add `batch_verify` API and refactor `strauss_batch`
871ade3aac batch: Add `create` and `destroy` APIs
960b6dafa4 batch: Initialize an experimental batch module
0653a25d50 Merge bitcoin-core/secp256k1#1486: ci: Update cache action
94a14d5290 ci: Update cache action
2483627299 Merge bitcoin-core/secp256k1#1483: cmake: Recommend native CMake commands in README
5ad3aa3dcd Merge bitcoin-core/secp256k1#1484: tests: Drop redundant _scalar_check_overflow calls
51df2d9ab3 tests: Drop redundant _scalar_check_overflow calls
3777e3f36a cmake: Recommend native CMake commands in README
e4af41c61b Merge bitcoin-core/secp256k1#1249: cmake: Add `SECP256K1_LATE_CFLAGS` configure option
3bf4d68fc0 Merge bitcoin-core/secp256k1#1482: build: Clean up handling of module dependencies
e6822678ea build: Error if required module explicitly off
89ec583ccf build: Clean up handling of module dependencies
44378867a0 Merge bitcoin-core/secp256k1#1468: v0.4.1 release aftermath
a9db9f2d75 Merge bitcoin-core/secp256k1#1480: Get rid of untested sizeof(secp256k1_ge_storage) == 64 code path
74b7c3b53e Merge bitcoin-core/secp256k1#1476: include: make docs more consistent
b37fdb28ce check-abi: Minor UI improvements
ad5f589a94 check-abi: Default to HEAD for new version
9fb7e2f156 release process: Style and formatting nits
ba5d72d626 assumptions: Use new STATIC_ASSERT macro
e53c2d9ffc Require that sizeof(secp256k1_ge_storage) == 64
d0ba2abbff util: Add STATIC_ASSERT macro
da7bc1b803 include: in doc, remove article in front of "pointer"
aa3dd5280b include: make doc about ctx more consistent
e3f690015a include: remove obvious "cannot be NULL" doc
d373bf6d08 Merge bitcoin-core/secp256k1#1474: tests: restore scalar_mul test
79e094517c Merge bitcoin-core/secp256k1#1473: Fix typos
3dbfb48946 tests: restore scalar_mul test
d77170a88d Fix typos
e7053d065b release process: Add email step
429d21dc79 release process: Run sanity checks on release PR
42f8c51402 cmake: Add `SECP256K1_LATE_CFLAGS` configure option

git-subtree-dir: src/secp256k1
git-subtree-split: 282757398c85c747addee74c5e410ab0b050f4ac

d5f970e647

Merge commit 'd5f970e6479c9cef435aee9b266badd8fb088aaa' into 2024-02-batch-validation-updated 2fd7c8f07a

BatchVerify: Enable experimental batch module in secp256k1 7af51d25b1

DrahtBot commented at 5:06 pm on February 27, 2024: contributor

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

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process. A summary of reviews will appear here.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#29803 (Update libsecp256k1 subtree to latest master by fanquake)
#29745 (bench: Adds a benchmark for CheckInputScripts by kevkevinpal)
#29675 (wallet: Be able to receive and spend inputs involving MuSig2 aggregate keys by achow101)
#28122 (Silent Payments: Implement BIP352 by josibake)

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.

fjahr force-pushed on Feb 27, 2024

DrahtBot added the label CI failed on Feb 27, 2024

DrahtBot commented at 5:11 pm on February 27, 2024: contributor

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

Debug: https://github.com/bitcoin/bitcoin/runs/22041704016

Sjors commented at 9:40 am on February 28, 2024: member

I guess this is most interesting to test against the last 50K blocks on mainnet, i.e. since early 2023? Given the high percentage of taproot transactions. Such testing could benefit from a assume utxo snapshot, saving everyone the pain of rewinding. I can bake one, though ideally I’d like #26045 to land first.

Is the current PR already using batches? It’s unclear to me by glancing over validation.cpp if and how it’s collecting up to max_batch_size{106} signatures before calling batch.Verify().

Maybe add a -schnorrbatchverify startup argument so more people can try it once it gets through review.

fjahr commented at 12:53 pm on February 28, 2024: contributor

I guess this is most interesting to test against the last 50K blocks on mainnet, i.e. since early 2023? Given the high percentage of taproot transactions. Such testing could benefit from a assume utxo snapshot, saving everyone the pain of rewinding. I can bake one, though ideally I’d like #26045 to land first.

Yeah, that would be great. I have to get the tracing part to work in my setup again before I can start.

Is the current PR already using batches? It’s unclear to me by glancing over validation.cpp if and how it’s collecting up to max_batch_size{106} signatures before calling batch.Verify().

Yes, the rough architecture is as as follows (sorry for not writing a better explanation above but it’s still very rough and I expect it to change). So, the batch object is constructed and then handed down from ConnectBlock() to CheckInputScripts() which hands it to the CScriptCheck constructor. When the CScriptCheck instance is executed and the batch object is present BatchingCachingTransactionSignatureChecker is used which only differs from the default CachingTransactionSignatureChecker in that its implementation of VerifySchnorrSignature() and adds the Schnorr sig to the batch object instead of verifying it right there. (Here we have an issue because the function is not doing what the name says anymore but it is a much simpler change this way and I find it hard to predict where we will land with this in the end.) Then back in ConnectBlock() the batch object is verified after all transactions have been iterated over.

The 106 is an implementation detail from secp256k1 that I am not sure needs to be really exposed here. But what matters for the question is: if there are more than 106 sigs added to the batch the verification for the already added sigs will happen when the next sig is added and if the verification fails the adding itself will fail. So, a callback to the last paragraph, every 106 sigs the naming of VerifySchnorrSignature() is actually still correct ;) and the one verify call in the end just verifies the last n % 106 sigs left for that block. I did not put any effort in documenting this properly here yet because the secp256k1 API is not finalized yet and the details on this particular topic might still change, see for example https://github.com/bitcoin-core/secp256k1/pull/1134#pullrequestreview-1083948472

Everything should be conditional on the presence of a batch object which defaults to nullptr and if that is the case all the other functions should work as usual, for example when used outside of the context of a new block.

Maybe add a -schnorrbatchverify startup argument so more people can try it once it gets through review.

Yeah, I have been thinking that or maybe even a compiler argument

BatchVerify: Add basic schnorr sig batch verification in ConnectBlock() 1825555b6b

fjahr force-pushed on Feb 28, 2024

fjahr commented at 1:14 pm on February 28, 2024: contributor

@Sjors maybe what confused you is that BatchingCachingTransactionSignatureChecker::VerifySchnorrSignatureBatch() was unused. That was actually a leftover from an earlier design spike and I just forgot to remove it. It’s gone now.

Sjors commented at 1:36 pm on February 28, 2024: member

if there are more than 106 sigs added to the batch the verification for the already added sigs will happen when the next sig is added and if the verification fails the adding itself will fail.

That clarifies a lot, and should be documented :-)

DrahtBot added the label Needs rebase on Apr 6, 2024

DrahtBot commented at 10:26 am on April 6, 2024: contributor

🐙 This pull request conflicts with the target branch and needs rebase.

0xB10C commented at 8:33 am on May 13, 2024: contributor

@willcl-ark and I ran a IBD benchmark vs master for this PR: IBD from a local node to height 840000 and currently only looking at the connect_block duration.

In the current draft implementation:

master is currently faster
batch validation is attempted and decreases performance even before taproot activated
after taproot activation, batch validation is significantly slower than non-batch validation

Used this bpftrace script to collect CSV data:

 0#!/usr/bin/env bpftrace
 1
 2usdt:./src/bitcoind:validation:block_connected
 3{
 4  $height = (int32) arg1;
 5  $tx = (uint64) arg2;
 6  $ins = (int32) arg3;
 7  $sigops = (int64) arg4;
 8  $duration = (int64) arg5; // in nanoseconds
 9
10  printf("%d,%ld,%d,%ld,%ld\n", $height, $tx, $ins, $sigops, $duration);
11}

willcl-ark commented at 8:38 am on May 13, 2024: member

batch validation is attempted and decreases performance even before taproot activated

From a quick skim of the changes ISTM that we always use the BatchingCachingTransactionSignatureChecker, and there was no switch to the CachingTransactionSignatureChecker, but this could well be because this is only in WIP state. It doesnt account for why it’s currently slower in all cases though.

[DO NOT MERGE] Schnorr batch verification for blocks #29491

Code Coverage

Reviews

Conflicts