Would this mean in the invalid case, the client still needs to check S1…Sn one by one to find the invalid one? How would this better than “big aggregate signature of all messages in the block” approach, in terms of the number of signatures to check?
Yep! Though note that:
- We can expect that most blocks received will be valid.
- If a block is invalid, there’s technically no need to figure out why it’s invalid; you can just reject it and move on. A client would only do full rechecking to figure out which of the signatures is faulty if a high level of error logging is turned on.
I think the smaller range should be on the order of 1…2^{128}, assuming 128 bit soundness is desired. In the case of 2 signatures, with r_1=1, its easy to show that 1…2^{64} only has 64 bits of soundness
Sure, but 64 bits of soundness is fine because the attacker doesn’t have the ability to try many times and check locally if they succeeded. It’s checked client-side, so it just means that there’s only a 2^{-64} chance of success
and this extends to larger aggregations if an attacker can restrict the signatures to be in a subgroup of order 2^{64}, which could likely exist if the pairing friendly curve used is also a SNARK friendly curve.
The elliptic curve group BLS-12-381 is operating in is a prime-order subgroup. So it’s not possible for there to be a lower-order sub-subgroup of that (except the trivial one with one element).