Cannot aggregate to a single message

[leahcornelius]

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]

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]

[leahcornelius]

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]

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]

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]

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]

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

[Kubuxu]

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

[trevyn]

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

[leahcornelius]

I do not believe so @trevyn

[leahcornelius]

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

[dignifiedquire]

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

[Kubuxu]

@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]

What would it take for this to be added?

[AtropineTears]

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]

@leocornelius
See

bls-signatures/src/signature.rs

Lines 142 to 144 in 884410d

	// 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]

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.