crypto: ed25519 & sr25519 batch verification by tac0turtle · Pull Request #6120 · tendermint/tendermint

tac0turtle · 2021-02-16T16:14:21Z

Description

Add batch verification

all done on a macbook pro m1 8gb

verifyCommitLight benchmarks

benchmark                                          old ns/op      new ns/op      delta
BenchmarkValidatorSet_VerifyCommitLight/1-8        1091694        578156         -47.04%
BenchmarkValidatorSet_VerifyCommitLight/8-8        909134         11070          -98.78%
BenchmarkValidatorSet_VerifyCommitLight/64-8       836350         11571          -98.62%
BenchmarkValidatorSet_VerifyCommitLight/1024-8     2620631542     2067067209     -21.12%

verifiyCommitLighttrusting

BenchmarkValidatorSet_VerifyCommitLightTrusting/1-8        1131301        579758         -48.75%
BenchmarkValidatorSet_VerifyCommitLightTrusting/8-8        428150         5995           -98.60%
BenchmarkValidatorSet_VerifyCommitLightTrusting/64-8       534509         6658           -98.75%
BenchmarkValidatorSet_VerifyCommitLightTrusting/1024-8     2639015083     2083845167     -21.04%

verifyCommit

benchmark                                     old ns/op      new ns/op      delta
BenchmarkValidatorSet_VerifyCommit/1-8        1094466        574299         -47.53%
BenchmarkValidatorSet_VerifyCommit/8-8        1116186        572915         -48.67%
BenchmarkValidatorSet_VerifyCommit/64-8       1383445        629387         -54.51%
BenchmarkValidatorSet_VerifyCommit/1024-8     2764757791     2076397292     -24.90%

codecov · 2021-02-18T13:47:27Z

Codecov Report

Merging #6120 (5e1ceb1) into master (bf8cce8) will decrease coverage by 0.16%.
The diff coverage is 63.05%.

@@            Coverage Diff             @@
##           master    #6120      +/-   ##
==========================================
- Coverage   60.82%   60.66%   -0.17%     
==========================================
  Files         276      277       +1     
  Lines       25788    25913     +125     
==========================================
+ Hits        15686    15719      +33     
- Misses       8488     8555      +67     
- Partials     1614     1639      +25

Impacted Files	Coverage Δ
crypto/crypto.go	`0.00% <ø> (ø)`
crypto/sr25519/privkey.go	`51.16% <0.00%> (ø)`
crypto/sr25519/pubkey.go	`56.52% <0.00%> (+4.34%)`	⬆️
crypto/ed25519/ed25519.go	`45.65% <50.00%> (+3.54%)`	⬆️
types/validator_set.go	`83.17% <62.96%> (-6.40%)`	⬇️
crypto/sr25519/batch.go	`83.33% <83.33%> (ø)`
privval/signer_listener_endpoint.go	`77.64% <0.00%> (-11.77%)`	⬇️
mempool/reactor.go	`65.71% <0.00%> (-6.43%)`	⬇️
privval/signer_endpoint.go	`75.75% <0.00%> (-6.07%)`	⬇️
libs/events/events.go	`92.94% <0.00%> (-5.89%)`	⬇️
... and 18 more

tac0turtle · 2021-02-25T14:59:15Z

This pr focuses on previous commit verification. I think current vote verification in a batch form should be done in a separate PR because it puts a greater focus on consensus.

alexanderbez

Great work @marbar3778. I left some questions and comments 👍

CHANGELOG_PENDING.md

crypto/batch/batch.go

crypto/ed25519/bench_test.go

crypto/ed25519/ed25519.go

crypto/sr25519/sr25519_test.go

types/validator_set.go

types/validator_set_test.go

crypto/batch/batch.go

crypto/ed25519/bench_test.go

crypto/ed25519/ed25519.go

crypto/sr25519/batch.go

crypto/ed25519/ed25519.go

crypto/sr25519/batch.go

types/validator_set.go

crypto/ed25519/bench_test.go

crypto/sr25519/bench_test.go

author Marko Baricevic <marbar3778@yahoo.com> 1614262850 +0100 committer Marko Baricevic <marbar3778@yahoo.com> 1614692925 +0100 gpgsig -----BEGIN PGP SIGNATURE----- iQIzBAABCAAdFiEEFE0lS6lW436ohG3eHBpbRKDkZ00FAmA+Qj0ACgkQHBpbRKDk Z01x5Q/7B9W9kvHie8GNI9nLU7/BBiJo1tvfIA9bUbS0mpEvm25Bp9CndLg7jmWt tKEZmu+diANZVKSdtrPWUhiD6hg980BBZqrMjXnedxpQGAoDwQxFwrRbMhkU7TJC InoMsGkMKAiJ2oKDWQNH+5iGiJqsgO9oXXgzWXZdE9usfcuikoJyYOOx8T/Pnyed aCdEpCRKklAzSawT2gBOoCpTzOohZ/Jr2NGgBj93PUem1cAQBqhcvHm4lxVCT+E8 vHobXxErTFf+22o4Pj2HjDjqihfuhOT4+mAb9Bz53FtWyq5uHrtnhITABCF2fHFd Mk68y3pAzM9hBjiyb2FIYQ4HHMaC841qamlTRUb8RdgxGYpV0TZ39A3F92gkYgad fOr8jBrGtZDXnqEeGdEcZYqeYVOP/YvAy4jvgE3RPbaaGc1nXgR6J54/dxpEqEek KOMtWVaR2xLVg1D9/EZlzH2qX4Vy2ybIWlLZApHXIPN6KLwkkB1OV3LfUGdTAcT5 ag9eOSU41KLp4c1QUwTBbwBAqZ7b1f/790jvIIrUwXDl66Llj7VP9WxhzrlnX2k0 03YcJbFkGw57jAm7UwfH0Y+F0wHLWuPtUt0TDwTxMlaYYTyjT2kpBwsevBCxUWTv YiBNeOzajD5UiKc7JE7yKZUPthstyvOrPHgi1AxgLXxsI0cq6GQ= =Vik0 -----END PGP SIGNATURE----- add verifycommit batch and bench specify keytype for benchmark remove new.txt goimport add changelog entry address comments Update crypto/sr25519/sr25519_test.go Co-authored-by: Aleksandr Bezobchuk <alexanderbez@users.noreply.github.com> Update crypto/sr25519/batch.go Co-authored-by: Anton Kaliaev <anton.kalyaev@gmail.com> Update crypto/ed25519/ed25519.go Co-authored-by: Aleksandr Bezobchuk <alexanderbez@users.noreply.github.com> Update crypto/ed25519/ed25519_test.go Co-authored-by: Aleksandr Bezobchuk <alexanderbez@users.noreply.github.com> Update crypto/ed25519/ed25519_test.go Co-authored-by: Aleksandr Bezobchuk <alexanderbez@users.noreply.github.com> add more context add comment for signature check Update crypto/ed25519/bench_test.go Co-authored-by: Aleksandr Bezobchuk <alexanderbez@users.noreply.github.com>

Co-authored-by: Aleksandr Bezobchuk <alexanderbez@users.noreply.github.com>

alexanderbez · 2021-03-03T14:09:35Z

types/validator_set.go

+		for idx, commitSig := range commit.Signatures {
+			if commitSig.Absent() {
+				continue // OK, some signatures can be absent.
+			}
+
+			// The vals and commit have a 1-to-1 correspondance.
+			// This means we don't need the validator address or to do any lookup.
+			val := vals.Validators[idx]
+
+			// Validate signature.
+			voteSignBytes := commit.VoteSignBytes(chainID, int32(idx))
+			if !val.PubKey.VerifySignature(voteSignBytes, commitSig.Signature) {
+				return fmt.Errorf("wrong signature (#%d): %X", idx, commitSig.Signature)
+			}
+
+			// Good!
+			if commitSig.ForBlock() {
+				talliedVotingPower += val.VotingPower
+			}


So this block and the block under the case of when !bv.Verify() evaluates true are identical. We should keep this code DRY. Perhaps move this logic to an inline function in this function.

e.g.

verifySigsDefault := func(...) { // ... } // ... if !bv.Verify() { verifySigsDefault(...) }

Also, if !bv.Verify() evaluates to true, we recompute the voteSignBytes all over again. Maybe this isn't much overhead, but perhaps we can compute and store these once. Thoughts @melekes?

I can look at inlining, I tested it and ran into some issues but cant recall why I reverted.

We can try caching it. If verification fails we will need to single verify whats in the cache and potentially more. Its possible to do this, I can do some benchmarking to test this.

It should 100% be possible. The code is identical unless I'm missing something obscure.

agree re code duplication

types/validator_set.go

alexanderbez · 2021-03-04T18:42:38Z

CHANGELOG_PENDING.md

 - [rpc/client/http] \#6163 Do not drop events even if the `out` channel is full (@melekes)
 - [node] \#6059 Validate and complete genesis doc before saving to state store (@silasdavis)
 - [state] \#6067 Batch save state data (@githubsands & @cmwaters)
+- [libs/log] \#6174 Include timestamp (`ts` field; `time.RFC3339Nano` format) in JSON logger output (@melekes)


Where did this entry come from?

no idea, merged in master and it appeared. Will remove

types/validator_set.go

alexanderbez

Looks good @marbar3778. Could use use linting/style cleanup, but the logic seems good.

types/validator_set.go

Co-authored-by: Aleksandr Bezobchuk <alexanderbez@users.noreply.github.com>

…ermint into marko/batch-impl

ValarDragon · 2021-03-15T15:51:56Z

yay! Very excited that this got in =)))

Co-authored-by: Aleksandr Bezobchuk <alexanderbez@users.noreply.github.com> Co-authored-by: Anton Kaliaev <anton.kalyaev@gmail.com>

init batch verification

2505de1

tac0turtle added the C:crypto Component: Crypto label Feb 16, 2021

tac0turtle self-assigned this Feb 16, 2021

tac0turtle added 3 commits February 17, 2021 14:45

batch

6033c8d

migrate commitlight and commitlight trusting to batch

bd24ee2

remove local home dir

9864e11

tac0turtle added 5 commits February 18, 2021 15:51

pull out duplication

e8ec972

fix tests

4a06da5

Merge branch 'master' into marko/batch-impl

fe9371e

add benchmarks

51253ce

add batch verification for sr25519

bb5ddd1

tac0turtle changed the title ~~crypto: ed25519 batch verification~~ crypto: ed25519 & sr25519 batch verification Feb 25, 2021

tac0turtle marked this pull request as ready for review February 25, 2021 15:39

tac0turtle requested review from alexanderbez, ebuchman, melekes and tessr as code owners February 25, 2021 15:39

alexanderbez suggested changes Mar 1, 2021

View reviewed changes

melekes reviewed Mar 1, 2021

View reviewed changes

alexanderbez reviewed Mar 2, 2021

View reviewed changes

crypto/ed25519/bench_test.go Outdated Show resolved Hide resolved

alexanderbez reviewed Mar 2, 2021

View reviewed changes

crypto/sr25519/bench_test.go Outdated Show resolved Hide resolved

tac0turtle force-pushed the marko/batch-impl branch from 844d9e0 to 79b54ba Compare March 2, 2021 13:49

Update crypto/sr25519/bench_test.go

7a7a4db

Co-authored-by: Aleksandr Bezobchuk <alexanderbez@users.noreply.github.com>

tac0turtle force-pushed the marko/batch-impl branch from 79b54ba to 7a7a4db Compare March 2, 2021 13:50

remove comment

a0c6493

tac0turtle requested a review from alexanderbez March 2, 2021 16:32

alexanderbez reviewed Mar 3, 2021

View reviewed changes

tac0turtle added 7 commits March 4, 2021 11:47

Merge branch 'master' into marko/batch-impl

d102290

DRY..er

31a5966

dont pass in seenVals

9f9cf4c

Merge branch 'master' into marko/batch-impl

af8c857

fix ed25519 batch

af5781f

cache sign bytes

c444204

linting

ec98975

alexanderbez approved these changes Mar 4, 2021

View reviewed changes

alexanderbez reviewed Mar 4, 2021

View reviewed changes

types/validator_set.go Show resolved Hide resolved

types/validator_set.go Show resolved Hide resolved

tac0turtle and others added 7 commits March 4, 2021 20:14

Update types/validator_set.go

d1c92ab

Co-authored-by: Aleksandr Bezobchuk <alexanderbez@users.noreply.github.com>

Update types/validator_set.go

623113c

Co-authored-by: Aleksandr Bezobchuk <alexanderbez@users.noreply.github.com>

add a bit more detail to godoc

47fd433

minor touchup

55cca71

minor touchup

da4223e

Merge branch 'marko/batch-impl' of https://github.com/tendermint/tend…

a90e6f3

…ermint into marko/batch-impl

Merge branch 'master' into marko/batch-impl

5e1ceb1

tac0turtle merged commit 6ffdf18 into master Mar 15, 2021

tac0turtle deleted the marko/batch-impl branch March 15, 2021 10:58

tac0turtle mentioned this pull request Jul 27, 2022

v0.37 release plan #9091

Closed

39 tasks

tac0turtle mentioned this pull request Aug 7, 2022

upstream 0.35 crypto improvements #9186

Closed

JayT106 mentioned this pull request Sep 19, 2022

crypto: ed25519 & sr25519 batch verification #9456

Closed

3 tasks

adizere mentioned this pull request Dec 7, 2023

crypto: port crypto improvements stuck from v0.35 cometbft/cometbft#1769

Closed

3 tasks

Conversation

tac0turtle commented Feb 16, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Description

Uh oh!

codecov bot commented Feb 18, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

tac0turtle commented Feb 25, 2021

Uh oh!

alexanderbez left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

alexanderbez Mar 3, 2021

Choose a reason for hiding this comment

Uh oh!

tac0turtle Mar 3, 2021

Choose a reason for hiding this comment

Uh oh!

alexanderbez Mar 3, 2021

Choose a reason for hiding this comment

Uh oh!

melekes Mar 4, 2021

Choose a reason for hiding this comment

Uh oh!

Uh oh!

alexanderbez Mar 4, 2021

Choose a reason for hiding this comment

Uh oh!

tac0turtle Mar 4, 2021

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

alexanderbez left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

ValarDragon commented Mar 15, 2021

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

tac0turtle commented Feb 16, 2021 •

edited

Loading

codecov bot commented Feb 18, 2021 •

edited

Loading