Verifying group threshold keys

[mhluongo]

We've kicked around a few ideas for how best to do this. After researching #31 we know BLS aggregated signatures aren't an option due to the expensive pairing check scaling with the group size.

[mhluongo]

There are a couple constructions that would make sense.

The simplest is probably requiring each share that's submitted to be signed by an ETH ECDSA private key. In that scenario, we have to keep track of each share and combine them on-chain into a public threshold key. I don't think it's as gas efficient to keep track of each of those pieces.

More complicated is requiring each group member to sign the resulting threshold public key, and submit all signatures at group creation. This saves a ton on gas, but requires more communication in the off-chain group broadcast channel.

There's also a challenge/verify version where we trust the sender, and give eg a delay period allowing group creation challenges. Much cheaper, but ripe for abuse.

[Shadowfiend]

requiring each group member to sign the resulting threshold public key

Can you explain this one a bit more? Are you saying each group member signs + submits? Or everyone signs and then we submit one? The latter seems like an aggregated signature, the former seems like it may be similar to the previous discussion, but I'm not certain.

[mhluongo]

I'm outlining both as options, though for the latter what I'm saying is we can't aggregate signatures- ECDSA doesn't have agg sigs and BLS agg sigs are too expensive to verify on-chain

[Shadowfiend]

Ok, reread a few times and I think I've got it. Restating to make sure: the two options we're looking at are:

• Each member submits their share to the chain and the public key is recovered on-chain.
• Each member submits the public key to the chain, and we have some solution if someone submits a key that doesn't match others that have been submitted for this group.

Does that sound right?

Worth noting: do we need to explicitly say “each group member signs”? That implies to me an extra signature, but by submitting a transaction to the chain, we've already signed (because the transaction itself is signed), right?

[mhluongo]

we've already signed (because the transaction itself is signed), right?

Right, but that's just one signature speaking for the whole group. It might not matter though- acouple updates here.

First, it appears that our complexity concerns around aggregate signatures have recently been addressed. That post shows a method of avoiding replay attacks without the O(n) pairing check explosion.

Second, it's also become clear that if we are doing BLS sig verification on-chain every relay entry submission, we don't need this mechanism- any falsified entries will be discovered by the contract and the punishment will be the gas cost. Unless we decide the gas cost is too steep for v1, we should be good to close this.

[Shadowfiend]

I'm not really sure I follow here… This issue is about the public key generated during DKG. There is no BLS sig verification that can be applied to that, as there is no BLS key to use. Once the group is formed, what you're saying applies, but during group formation we still have the dual concerns of “what if someone who isn't supposed to be in the group submits a key for the group“ and “what happens if a bad player in the group submits a key other than the group's DKG-generated public key”.

Let me try to clarify the alternatives we're discussing, to see if I've understood them correctly (and add one more):

• Group signature: each group member signs the BLS public key after it's generated with their BLS secret key share, these sigs are aggregated, and then presumably one member submits the key + the aggregate sig. We verify on-chain the aggregate sig, group activates (possibly after an activation delay, still unclear). Main issue I see: more BLS logic on-chain, an extra round in DKG, and additional data needed from the clients to the chain in order for on-chain aggregate sig verification to work.
• Everyone submits: each group member independently submits the group public key and the chain verifies (a) the member is in the group (based on msg.sender) and (b) the key is either the first submission or matches previous submissions. Once all members have submitted the group public key and they all match, the group activates (possibly after an activation delay, still unclear). Main issue I see: higher gas cost, as each member has to submit the group pk.
  • Accusation: one member can submit the group pk. Group starts activating, but has an activation delay. Within the activation delay, any other group member can declare the submitted pk invalid. This triggers the everyone-submits scenario from above, only submissions are tallied, the majority pk is considered “correct”, and all members who didn't submit or submitted a different key are punished (with a payment to the majority from the punishment). The group never activates.

[mhluongo]

Derp, we've got two open verification concerns and I swapped them. Carry on. New info here is that there's an efficient way to check agg sigs to confirm a threshold key has signoff from all participants

[Shadowfiend]

If I understand correctly, the efficient way still requires us to have a pre-DKG submission (to the chain) of the aggregate public key (requires a trusted member or some other mechanism), or on-chain aggregation of the public key (which loses us the advantage of keeping everyone's individual pks secret, as well as costing gas to aggregate), right?