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

Cannot aggregate to a single message #42

Open
leahcornelius opened this issue Jun 28, 2021 · 17 comments
Open

Cannot aggregate to a single message #42

leahcornelius opened this issue Jun 28, 2021 · 17 comments

Comments

@leahcornelius
Copy link

leahcornelius commented Jun 28, 2021

Say you have a single message, eg a block hash, M as well as a vector of signers S and their BLS signatures SIGS (where each signature in SIGS is a BLS signature on M)
if you call aggregate on sigs it will produce an aggregate signature A however calling:

verify_messages(&A, &[M], &S)

will yield false.
The only way to use aggregation is to make each signer S sign an individual message (Eg. SIGS[S] = S.sign(M + S)) which rusts in linear validation time. Is there no way to aggregate a set of non-heteromorphic signatures (eg all signatures are on the same message)?
Thanks

@leahcornelius
Copy link
Author

If i am not mistaken this is the primary use case of BLS. It allows consnt time (O(1)) validation speeds irrelevant of signer count.

@leahcornelius
Copy link
Author

image

@leahcornelius
Copy link
Author

As you can see the validation time of the aggregated signature grows linearly with the number of signers (as the number of signers == messages or it fails) whereas I was hoping for a semi-constant validation time.

@leahcornelius
Copy link
Author

As you can see in this paper https://eprint.iacr.org/2018/483.pdf, an aggregate signature of n signers on the same message m can be validated with just 2 pairings rather than the current n + 1

@leahcornelius
Copy link
Author

This should also be of use in implementing it, if the current method does not allow it. https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html

@AtropineTears
Copy link

I am having the same problem. I cannot get it to aggregate the same message.

It works for different messages but not the same.

I am wondering if anyone is looking into fixing it as it is a very useful feature.

Any updates???

@trevyn
Copy link

trevyn commented Dec 13, 2021

I’d also like to see this. I wonder if this would be eligible for a Filecoin Dev Grant: https://grants.filecoin.io/

@Kubuxu
Copy link

Kubuxu commented Dec 13, 2021

I don't think this was in the scope of this library. cc @dignifiedquire

@trevyn
Copy link

trevyn commented Dec 14, 2021

@leocornelius Does the underlying blst library/crate support this?
https://github.com/supranational/blst/blob/master/bindings/rust/README.md

@leahcornelius
Copy link
Author

I do not believe so @trevyn

@leahcornelius
Copy link
Author

@Kubuxu Well i dont see what scope would use BLS signuure heteromorphically? With O(n) validation time it strips BLS's major usecase

@dignifiedquire
Copy link
Contributor

This could probably be added, but yes it wasn't in scope when this library was developed.

@Kubuxu
Copy link

Kubuxu commented Jan 10, 2022

@leocornelius in essence this library was developed to work on 1:1 messages to signatures ratio aggregated to one signature aggregate, not 1 message and N signatures. Yes, the latter is one of the use cases of BLS but it wasn't in the scope of this library when it was developed.

@leahcornelius
Copy link
Author

What would it take for this to be added?

@AtropineTears
Copy link

Well from what I can see, they do not allow this on purpose. What I found you can do is the following:

Sign the following:

<insert-pk>_message

This allows you to sign the same message by prepending the public key to the message. The space is still saved as you do not need to store anything else besides the message and the public keys.

@Kubuxu
Copy link

Kubuxu commented Jan 31, 2022

@leocornelius
See

// Enforce that messages are distinct as a countermeasure against BLS's rogue-key attack.
// See Section 3.1. of the IRTF's BLS signatures spec:
// https://tools.ietf.org/html/draft-irtf-cfrg-bls-signature-02#section-3.1

and https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-bls-signature-02#section-3

This implementation uses the basic scheme (section 3.1) for protection against rouge key attacks.

For O(1) number of parings, you would need Proof of Possession scheme described in Section 3.3 (also known as "Proof of knowledge of the secret key" in the other document), which this library currently doesn't implement.

@miguelammatos
Copy link

I'm also interested in the scenario with N signatures for the same message, as proof-of-possession is done elsewhere.
Looking at the code, this seems to be a matter of disabling the message uniqueness checks on both verify and verify_messages.

I played around with this and it seems to be working fine (tested under simple scenarios).

I think this could be incorporated with an explicit feature e.g. "disable-rogue-key-attack-prevention" that is disabled by default.
If you think this is acceptable I can try to put together a PR.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

6 participants