go-algorand icon indicating copy to clipboard operation
go-algorand copied to clipboard

Batch-verify: Stream transactions to the verifier [WIP]

Open algonautshant opened this issue 2 years ago • 1 comments

This PR delivers two main features:

  1. A method to batch the verifications of incoming transactions
  2. Streaming capabilities of transactions to the verifier

Why (1): Batching transactions are more efficient to verify because of the cryptographic efficiency in doing so. It is used for verification of txns in the block and the Msig. With this work, it will also be possible for incoming txns.

Why (2): Batch verifier should use the execution pool to keep the number of goroutines performing heavy lifting in check. This approach is also followed in PaysetGroups for verifying the txns in a block.
The transaction handler cannot block until the transaction is verified, for that reason it also uses the exec pool in txHandler. The handler and the verifier cannot both use the exec pool, this may lead to a deadlock. For this reason, the streaming approach is adopted here.

Other considerations and future work:

  1. The signatures inside LogicSig (Msig or Sig) are not added to the main batch. Instead, they are batched in their own batch. This is a limitation and the performance can be improved by adding them to the top level batch. This requires the decoupling of the txn validity checks from the signature verification, and will be address in a different PR.

  2. In the crypto_sign_ed25519_open_batch implementation, the validity of every transaction is checked in case the batch verification fails. This can be improved for all workflows: a. in case we don't care with sig fails, and we reject the whole batch (Msig, block validation), we are doing the extra work of verifying each sig one by one when the batch fails. b. in case we are which txn sig failed, in case of batch verification of the incoming txns, the verification can be done by checking logarithmic number of the sigs, instead we check linearly all of them.

algonautshant avatar Oct 02 '22 16:10 algonautshant

Codecov Report

Merging #4621 (bab964b) into master (f15c9ad) will increase coverage by 0.10%. The diff coverage is 90.16%.

@@            Coverage Diff             @@
##           master    #4621      +/-   ##
==========================================
+ Coverage   53.59%   53.70%   +0.10%     
==========================================
  Files         433      433              
  Lines       53864    54050     +186     
==========================================
+ Hits        28868    29027     +159     
- Misses      22758    22776      +18     
- Partials     2238     2247       +9     
Impacted Files Coverage Δ
cmd/goal/clerk.go 8.77% <0.00%> (ø)
data/ledger.go 31.38% <ø> (ø)
data/transactions/verify/verifiedTxnCache.go 78.12% <ø> (+0.57%) :arrow_up:
ledger/ledger.go 69.87% <ø> (ø)
ledger/notifier.go 88.57% <ø> (ø)
node/node.go 4.26% <0.00%> (-0.02%) :arrow_down:
data/transactions/verify/txn.go 70.24% <93.29%> (-4.34%) :arrow_down:
data/txHandler.go 72.07% <93.75%> (+13.78%) :arrow_up:
crypto/batchverifier.go 100.00% <100.00%> (ø)
data/txDupCache.go 97.00% <100.00%> (+0.09%) :arrow_up:
... and 8 more

:mega: We’re building smart automated test selection to slash your CI/CD build times. Learn more

codecov[bot] avatar Oct 02 '22 17:10 codecov[bot]

Looks good to me. I'd be satisfied with any other changes being a follow-on cleanup PR later.

brianolson avatar Dec 27 '22 17:12 brianolson

Please fix some start usage in tests

algorandskiy avatar Dec 29 '22 00:12 algorandskiy