bnb-chain / tss-lib

Threshold Signature Scheme, for ECDSA and EDDSA
MIT License
790 stars 271 forks source link

Improve DLN proof verification performance for large signing groups #203

Closed pdyraga closed 2 years ago

pdyraga commented 2 years ago

Verification of discrete logarithm proofs is the most expensive part of threshold ECDSA key generation for large groups. In round 2 of key generation, the local party needs to verify proofs received from all other parties. The cost of a call to dlnProof.Verify measured on Darwin/arm64 Apple M1 max is 341758528 ns/op - see BenchmarkDlnProof_Verify. There are two proofs that need to be verified during the key generation so assuming there are two cores available exclusively for this work, the verification of 100 messages takes about 35 seconds. For a group size of 1000, the verification takes about 350 seconds. The verification is performed in separate goroutines with no control over the number of goroutines created. When executing the protocol locally, during the development, for a group size of 100, 100*99*2 = 19 800 goroutines for DLN proof verification are created more or less at the same time. Even such a powerful CPU as Apple M1 Max struggles with computing the proofs - it takes more than 16 minutes on all available cores and all other processes are starved.

To optimize the code to allow it to be executed for larger groups, the number of goroutines created at the same time for DLN proof verification is throttled so that all other processes are not perpetually denied necessary CPU time to perform their work. This is achieved by introducing the DlnProofVerifier that limits the concurrency level, by default to the number of CPUs (cores) available.

The throttling logic has no real impact on the DLN proof verification performance for small groups:

BenchmarkDlnProof_Verify-10                3     343508611 ns/op     1777336 B/op     3803 allocs/op
BenchmarkDlnVerifier_VerifyProof1-10       3     343131722 ns/op     1857218 B/op     4319 allocs/op
BenchmarkDlnVerifier_VerifyProof2-10       3     342200917 ns/op     1858941 B/op     4319 allocs/op

Here is a two-minute profiling sample when executing locally key generation for a group size of 100 on the master branch:

image

yycen commented 2 years ago

Looks good and thanks for sharing the profiling results! I will have a test and read code soon.

pdyraga commented 2 years ago

Hey @yycen, I wanted to bump up this PR. TBTC v2 chaosnet starts next week and it would be great to ship this code. Currently we are attached to a fork, and we would love to switch back to the upstream.