Aggregating BLS signatures

Most of the different discussions in the community on BLS included BLS aggregation with a same message for individual signatures. This scheme is subject to attack, and would likely not be secure for GRIN.

But in a paper from two years ago, Dan Boneh actually proved the security of naive signature aggregation if all messages of individual signatures are different.

Here is a quotation from the paper in order to make things more precise:

“(One of the standard defenses) against the rogue public-key attack:
– Require that the messages being aggregated are distinct [12, 7], namely the verifier rejects an aggregate signature on non-distinct messages. This is sufficient to prevent the rogue key attack. Moreover, message distinctness can be enforced by always prepending the public key to every message prior to signing. However, because now all messages are distinct, we cannot take advantage of public-key aggregation as in (3) when aggregating signatures on a common message m.”

The precise description of this interesting and very scalable scheme is in the beginning of section 3.2, and as far as I understand could be used for GRIN by shrinking kernel size by 2/3. The aggregate signature proves that each iindividual public key had a correct signature, making the scheme naturally compatible with Mimblewimble. The security of tbe scheme is proven academically.

Few drawbacks:

  • No more scriptless script (atomic swaps, lightening,…) if we don’t keep Schnorr signatures somewhere.
  • quite big change in the security assumption.
  • would require to change the current elliptic curve and integrate a pairing-friendly curve instead (practically we would likely effectively need to support two curves).

One interesting point would be: “How to handle the migration from Schnorr to BLS?”

  1. Current Pedersen commitments use CurrentCurve, and as a consequence cannot be spent through transactions using a kernel excess that is signed with BLS. Output transition from Current Curve to PairingFriendlyCurve (PFCurve) should be made with transactions that consist of two partial excesses in the kernel, with their respective signature. Schnorr signature for the partial exces of the tx inputs, and BLS signature for the partial excess of the tx outputs.

  2. But how to verify for such transition transactions that:
    sum(output.Pedersen_bls) - sum(input.Pedersen_schnorr) = partial_excess_schnorr + partial_excess_bls. ?

the equation above actually does not have sense since it has two elliptoc curves in it.

The only way I might see around that for transition txs would be to prune neither of the tx inputs and neither of the tx outputs, and put the values of the commitments into the clear along with some proof that they are indeed the correct values. Not pretty. Important loss in privacy, and maybe not even sufficient. if blinding factors must be revealed for that, this is not good. Especially for the tx outputs. I don’t have a solution.

Overall, by having algebraic (group) operations on the tx inputs and tx outputs to be verified for each tx in one unique equation in order to be convinced that no coin is created out of the thin air, Mimblewimble might be a “curve-change resistant protocol”. If it is the case, the BLS question is solved. You could still have two worlds in parallel (by making some coinbase outputs that are on the BLS curve typically and enabling BLS transactions from them): one BLS and one Schnorr, but that’s kind of a broken concept, complicating things for not too much gain otherwise and with maybe implying different prices for schnorr outputs VS the bls outputs