perf(light): Use cache when verifying signatures by wllmshao · Pull Request #4322 · cometbft/cometbft

wllmshao · 2024-10-23T18:00:26Z

This PR adds two new methods to light package: VerifyCommitLightTrustingWithCache and VerifyCommitLightWithCache so that we don't have to verify the same signatures twice.

Pending some perf tests/benchmarks to measure performance improvement.

ValarDragon · 2024-10-23T19:58:51Z

types/validation.go

+		cacheKey := string(val.Address) + string(voteSignBytes)
+		_, ok := verifiedSignatureCache[cacheKey]


Nice! This has a malleabiltiy vector though if addresses weren't fixed size. Its also not zero-allocation, which is good to have at the sig verification level.

Perhaps structure the map using vote sign bytes as the key, and then the val address as the value? Not sure we can avoid the string casts for immutability reasons, so maybe we just live with the allocs. Should see how much it slows it down in the normal case.

Also can we allow passing in a nil map (skipping the check if nil)

Updated to make these changes.

Using string(voteSignBytes) as the key and val address as the value

Check verifiedSignatureCache != nil before any usage. Pass nil where ever the cache does not need to be used

types/validation.go

ValarDragon

LGTM, nice work!

But we should add a tests around non-nil caches being provided, and tally logic for counting to 2/3rds still working!

wllmshao · 2024-10-24T18:21:29Z

@ValarDragon thinking about this more, aren't the VoteSignBytes actually likely to be the same across signatures? I see a comment that says they differ only in the timestamp, the rest of the fields are identical. Would it not be better to use the validator address or the commit signature as the cache key?

ValarDragon · 2024-10-25T16:52:42Z

So we need to be sure that all 3 arguments for Verify(sign_bytes, signature, public_key) are the same, ideally with 0 allocations.

The key being the signature makes sense to me, since your right sign_bytes can get re-used. And then the value of the map being struct{sign_bytes, public_key} perhaps, where we check those two fields

types/validation.go

wllmshao · 2024-10-28T19:08:59Z

I added unit tests and changed the cache schema. Opening this for review.

Will still do some perf tests / benchmarks to try to measure performance improvement.

melekes

Thanks @wllmshao ❤️ Would love to see this merged

.changelog/unreleased/improvements/2365-deduplicate-light-signature-checks.md

types/validation.go

types/validator_set.go

types/validation.go

melekes · 2024-10-31T06:26:19Z

Please don't force-push. It makes reviewing impossible

cason

I wonder whether the signatures cache should I type by itself, instead of using a map[string]SignatureCacheValue. This will probably render it simple to implement and test.

Moreover, I wonder whether the tests can indeed confirm that the cache is being used. I think that a mock signature verifier/key should be used in this case, so we are really sure that the verification methods are not invoked.

.changelog/unreleased/improvements/2365-deduplicate-light-signature-checks.md

cason · 2024-10-31T08:07:06Z

This PR assumes that pubkeys are uniquely identified by the Address. Is that safe?

Yes. The consensus logic uses it, for instance proposerAddr := cs.privValidatorPubKey.Address(). And the Vote type include the same Address() that should match the address in the validator set.

Co-authored-by: Daniel <daniel.cason@informal.systems>

wllmshao · 2024-11-04T04:38:48Z

I wonder whether the signatures cache should I type by itself, instead of using a map[string]SignatureCacheValue. This will probably render it simple to implement and test.

Moreover, I wonder whether the tests can indeed confirm that the cache is being used. I think that a mock signature verifier/key should be used in this case, so we are really sure that the verification methods are not invoked.

Created a new type for SignatureCache to replace the map usage.
Added unit tests that use mocks to ensure that the cache is being used and signature verifications are not happening.

melekes

Thanks 🙏

melekes · 2024-11-04T05:41:33Z

types/signature_cache.go

+	cache map[string]SignatureCacheValue
+}
+
+func NewSignatureCache() SignatureCache {


I don't see how this is better than the original map[string]SignatureCacheValue. @cason is this what you had in mind?

Yes, so we can implement this abstraction in the way we prefer.

types/signature_cache.go

cason

Thank you a lot for this effort.

There are some details that we should take care of, but I'd say that we can take it over from here.

cason · 2024-11-05T08:36:11Z

types/signature_cache.go

+	cache map[string]SignatureCacheValue
+}
+
+func NewSignatureCache() SignatureCache {


Yes, so we can implement this abstraction in the way we prefer.

cason · 2024-11-05T08:40:27Z

types/validation.go

+				sig := commit.Signatures[idx]
+				verifiedSignatureCache.Add(string(sig.Signature), SignatureCacheValue{
+					ValidatorAddress: sig.ValidatorAddress,
+					VoteSignBytes:    commit.VoteSignBytes(chainID, int32(idx)),


This call requires proto encoding, namely is kind of expensive. Don't we have these bytes already computed?

cason · 2024-11-05T08:41:42Z

types/signature_cache.go

+}
+
+type signatureCache struct {
+	cache map[string]SignatureCacheValue


This cache grows over time, should we somehow restrict its size?

cason · 2024-11-05T08:42:17Z

.changelog/unreleased/improvements/2365-deduplicate-light-signature-checks.md

Should we add a new changelog entry for the creation of the SignatureCache type?

Closes #2365 This PR adds two new methods to `light` package: `VerifyCommitLightTrustingWithCache` and `VerifyCommitLightWithCache` so that we don't have to verify the same signatures twice. Pending some perf tests/benchmarks to measure performance improvement. --------- Co-authored-by: mergify[bot] <37929162+mergify[bot]@users.noreply.github.com> Co-authored-by: Anton Kaliaev <anton.kalyaev@gmail.com> Co-authored-by: Daniel <daniel.cason@informal.systems>

wllmshao force-pushed the ws/dedupe_light_sig branch 4 times, most recently from 791470a to 76c5e4f Compare October 23, 2024 18:24

ValarDragon reviewed Oct 23, 2024

View reviewed changes

types/validation.go Outdated Show resolved Hide resolved

ValarDragon reviewed Oct 23, 2024

View reviewed changes

wllmshao force-pushed the ws/dedupe_light_sig branch from ea25d8e to d01fd92 Compare October 23, 2024 21:17

wllmshao force-pushed the ws/dedupe_light_sig branch from 54590a6 to 6c3d2c6 Compare October 28, 2024 18:42

wllmshao commented Oct 28, 2024

View reviewed changes

types/validation.go Show resolved Hide resolved

wllmshao force-pushed the ws/dedupe_light_sig branch from 1dd5304 to 1955212 Compare October 28, 2024 19:08

wllmshao marked this pull request as ready for review October 28, 2024 19:13

wllmshao requested a review from a team as a code owner October 28, 2024 19:13

wllmshao requested review from a team and ValarDragon October 28, 2024 19:13

melekes reviewed Oct 29, 2024

View reviewed changes

.changelog/unreleased/improvements/2365-deduplicate-light-signature-checks.md Outdated Show resolved Hide resolved

types/validation.go Outdated Show resolved Hide resolved

types/validation.go Show resolved Hide resolved

types/validator_set.go Show resolved Hide resolved

wllmshao requested a review from melekes October 29, 2024 23:02

wllmshao force-pushed the ws/dedupe_light_sig branch from 4f588b3 to 94ce647 Compare October 29, 2024 23:02

melekes reviewed Oct 30, 2024

View reviewed changes

types/validation.go Outdated Show resolved Hide resolved

This comment was marked as resolved.

Sign in to view

wllmshao added 6 commits October 30, 2024 11:15

perf: Remove duplicated signature checks in light.VerifyNonAdjacent

20fdc73

Use voteSignBytes as key, val addr as value

25c7fbc

Combine cache conditions into cacheHit

1ad0324

Change cache scheme and add unit tests

c336be1

Use val pubkey address directly

07bbe81

Add new method to remove breaking changes, use bytes instead of address

31835c8

wllmshao force-pushed the ws/dedupe_light_sig branch from 94ce647 to 31835c8 Compare October 30, 2024 15:15

melekes approved these changes Oct 31, 2024

View reviewed changes

mergify bot added 3 commits October 31, 2024 06:26

Merge branch 'main' into ws/dedupe_light_sig

f2132e6

Merge branch 'main' into ws/dedupe_light_sig

3df790a

Merge branch 'main' into ws/dedupe_light_sig

268f6bd

cason reviewed Oct 31, 2024

View reviewed changes

.changelog/unreleased/improvements/2365-deduplicate-light-signature-checks.md Outdated Show resolved Hide resolved

This comment was marked as resolved.

Sign in to view

Merge branch 'main' into ws/dedupe_light_sig

a4041e5

mergify bot and others added 3 commits October 31, 2024 13:09

Merge branch 'main' into ws/dedupe_light_sig

308f652

Merge branch 'main' into ws/dedupe_light_sig

f765a77

update changelog

67b96c8

Co-authored-by: Daniel <daniel.cason@informal.systems>

melekes added enhancement New feature or request light-client Light client-related labels Nov 1, 2024

melekes changed the title ~~perf: Remove duplicated signature checks in light.VerifyNonAdjacent~~ perf(light): Use cache when verifying signatures Nov 1, 2024

wllmshao added 2 commits November 3, 2024 23:37

Make signatureCache its own type, add mock unit tests

f51ed6f

Merge branch 'main' into ws/dedupe_light_sig

55e90f5

melekes reviewed Nov 4, 2024

View reviewed changes

wllmshao and others added 2 commits November 4, 2024 17:06

use val address in cache value

11aee1b

Merge branch 'main' into ws/dedupe_light_sig

fd7c290

cason approved these changes Nov 5, 2024

View reviewed changes

melekes added this pull request to the merge queue Nov 5, 2024

melekes mentioned this pull request Nov 5, 2024

light: minor improvements following PR #4322 #4431

Open

Merged via the queue into cometbft:main with commit 3e3ee5d Nov 5, 2024

		cacheKey := string(val.Address) + string(voteSignBytes)
		_, ok := verifiedSignatureCache[cacheKey]

Conversation

wllmshao commented Oct 23, 2024 • edited by melekes Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ValarDragon Oct 23, 2024

Choose a reason for hiding this comment

Uh oh!

wllmshao Oct 23, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

ValarDragon left a comment

Choose a reason for hiding this comment

Uh oh!

wllmshao commented Oct 24, 2024

Uh oh!

ValarDragon commented Oct 25, 2024

Uh oh!

Uh oh!

wllmshao commented Oct 28, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

melekes left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

This comment was marked as resolved.

melekes commented Oct 31, 2024

Uh oh!

cason left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

This comment was marked as resolved.

cason commented Oct 31, 2024

Uh oh!

wllmshao commented Nov 4, 2024

Uh oh!

melekes left a comment

Choose a reason for hiding this comment

Uh oh!

melekes Nov 4, 2024

Choose a reason for hiding this comment

Uh oh!

cason Nov 5, 2024

Choose a reason for hiding this comment

Uh oh!

Uh oh!

cason left a comment

Choose a reason for hiding this comment

Uh oh!

cason Nov 5, 2024

Choose a reason for hiding this comment

Uh oh!

cason Nov 5, 2024

Choose a reason for hiding this comment

Uh oh!

cason Nov 5, 2024

Choose a reason for hiding this comment

Uh oh!

cason Nov 5, 2024

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

wllmshao commented Oct 23, 2024 •

edited by melekes

Loading

wllmshao Oct 23, 2024 •

edited

Loading

wllmshao commented Oct 28, 2024 •

edited

Loading