Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Change BLS signature/public key aggregation to enable better caching #592

Open
Stebalien opened this issue Aug 26, 2024 · 4 comments · May be fixed by #604
Open

Change BLS signature/public key aggregation to enable better caching #592

Stebalien opened this issue Aug 26, 2024 · 4 comments · May be fixed by #604
Assignees

Comments

@Stebalien
Copy link
Member

Right now we're not taking advantage of the bitfield mask when aggregating public keys. I.e., each time we aggregate public keys we use an all-ones bitfield and cannot re-use any of the results of the aggregation.

Instead, we should:

  1. Use the full power table when aggregating public keys, using the bitfield to select the active keys. This will cost a bit more up-front, but we'll only pay that cost once per instance.
  2. Cache the coeff*pubkey+pubkey for every public key for the rest of the instance (cache https://github.com/drand/kyber/blob/94dae51d79b4b0c2d2a9b9cc382b864cf3537783/sign/bdn/bdn.go#L183-L185).

This is the one N^2 cryptographic operation we do, so it should make F3 scale significantly better.

@Stebalien
Copy link
Member Author

drand/kyber#61

@Stebalien
Copy link
Member Author

In GPBFT, my plan is to change the Verifier interface as follows:

type Aggregate interface {
	// Aggregates signatures from a participants.
	Aggregate(ids []int, sigs [][]byte) ([]byte, error)
	// VerifyAggregate verifies an aggregate signature.
	// Implementations must be safe for concurrent use.
	VerifyAggregate(payload, aggSig []byte, signers []uint64) error
}

type Verifier interface {
	// Verifies a signature for the given public key.
	// Implementations must be safe for concurrent use.
	Verify(pubKey PubKey, msg, sig []byte) error
	// Return an Aggregate that can aggregate and verify aggregate signatures
	// made by the given public keys.
	Aggregate(pubKeys []PubKey) Aggregate
}

One downside to this approach is that we'll pay the cost of pre-computing the coefficients for all keys in the power table when validating finality certificate signatures where the current method only has to compute the coefficients for the keys actually used. But... I don't think that's going to be a huge deal and I want to keep this simple for now.

@Stebalien
Copy link
Member Author

Ew. So... validation makes this a bit annoying. We're going to have to cache this as part of the committee, possibly put it in gpbft.PowerTable (for validation). Probably the latter, TBH.

@Stebalien
Copy link
Member Author

Hm. PowerTable is the right place, but that's probably going to cause a bunch of issues. I'll probably have to add it as an additional param and cache it in the *committee object.

@Stebalien Stebalien changed the title Change BLS signature/public key aggregation enable better caching Change BLS signature/public key aggregation to enable better caching Sep 6, 2024
Stebalien added a commit to Stebalien/FIPs that referenced this issue Sep 9, 2024
This commit:

1. Specifies the BLS curve used by F3.
2. Specifies the aggregation scheme.
3. Tweaks the aggregation scheme to use all public keys from the
   committee when computing the aggregation coefficients for better
   performance.

This change does not change how F3 consensus works, it just makes the
protocol more efficient.

See filecoin-project/go-f3#592
jsoares added a commit to filecoin-project/FIPs that referenced this issue Sep 10, 2024
* FIP-0086: Specify and update signature and signature aggregation

This commit:

1. Specifies the BLS curve used by F3.
2. Specifies the aggregation scheme.
3. Tweaks the aggregation scheme to use all public keys from the
   committee when computing the aggregation coefficients for better
   performance.

This change does not change how F3 consensus works, it just makes the
protocol more efficient.

See filecoin-project/go-f3#592

* Apply suggestions from code review

Co-authored-by: Jorge M. Soares <[email protected]>
Co-authored-by: Masih H. Derkani <[email protected]>

---------

Co-authored-by: Jorge M. Soares <[email protected]>
Co-authored-by: Masih H. Derkani <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
Status: In review
Development

Successfully merging a pull request may close this issue.

1 participant