Add threshold multi-signatures

[burdges]

We should write threshold schnorr signatures using session types analogous to the multi-signature ones in multi.rs. We should first go over the threshold schnorr signing literature just to check if anything needs tweaking.

We'll likely need Pederson's DKG as a subprotocol for both shared key generation and for creating R. See https://pdfs.semanticscholar.org/642b/d1bbc86c7750cef9fa770e9e4ba86bd49eb9.pdf

[burdges]

We should do accountable subgroup multi-signatures along side this, which basically exist here already, but maybe the delinearization style impacts this as mentioned in https://github.com/w3f/schnorrkel/issues/44#issuecomment-519798874 (full group vs current group). I suspect this requires importing some of the signer table like construction from the bls crate, although not so much since we know all signers before finalizing.

There is an insecure accountable subgroup multi-signature scheme described at https://github.com/KZen-networks/multi-party-schnorr/blob/master/papers/accountable_subgroups_multisignatures.pdf and https://pdfs.semanticscholar.org/6bf4/f9450e7a8e31c106a8670b961de4735589cf.pdf but adopting the fix is easy.

[real-or-random]

Usually I would not post links to random GitHub issues without being asked, but my talk here is highly relevant to this. Schnorr-based threshold sigs shows how the standard schemes in the literature based on Feldman's VSS and Pedersen's VSS make assumptions that are weird in practice and thus may not be secure: https://www.youtube.com/watch?v=Wy5jpgmmqAg&list=PLaXwSyee0z4zWO0JLgcwhnjKqNBNJhBXY&index=53 The talk touches upon the real issues only superficially because my time was limited. Feel free to get in touch.

[burdges]

I'll close #44 since it duplicates this issue. We discussed delinearization mechanisms and accountable threshold interfaces there, and noted that blocking issues are resolving #6 and doing PVSS for DGKs and using passwords for some of the shares.

[burdges]

I've included comments about the DKG literature at https://github.com/w3f/bls/issues/6#issuecomment-573412444

[burdges]

https://www.researchgate.net/publication/225722958_Secure_Distributed_Key_Generation_for_Discrete-Log_Based_Cryptosystems

[burdges]

Isis implemented a reasonable DKG in https://github.com/isislovecruft/frost-dalek/tree/master/src but I hear other nifty new DKGs should appear soonish.

[real-or-random]

I hear other nifty new DKGs should appear soonish.

That sounds very interesting. Can you say more? ;)

[burdges]

I knew only vaguely about one upcoming one, but it uses pairings and I've no yet asked the authors if they thought about pairing-free variants, or more likely about the properties in the DKG literature that preceded theirs.

We avoid uses DKGs in Polkadot so I never dug too much into them, but some support slightly nicer setups and/or safer redealing key shares. I figured redealing key shares might be useful here.. assuming someone else tells me what's optimal. ;)

[alxs]

@burdges we have a grantee that wants to wait until this has been implemented to work on a milestone (@kevingzhang). Is it in the roadmap, or should he rather try to find another way?

[burdges]

We could speed this up I think. I think @Lederstrumpf got interested. Send the grantee our matrix info so they can bug us.

[kevingzhang]

Awesome, finally someone started paying attention to this issue!

[kevingzhang]

Awesome, looking forward to updates. thanks

[alxs]

@kevingzhang this is unlucky - @Lederstrumpf is leaving us and once again it's unlikely this gets done in the next few months.

[kayabaNerve]

I did code support for Schnorrkel around my own FROST library in hopes it may be useful: https://github.com/serai-dex/serai/compare/develop...schnorrkel

While I assume schnorrkel will eventually have its own in-house own implementation of FROST, the above is usable today and the underlying library is currently undergoing auditing, so it shouldn't be insecure/problematic (at least, definitely not a month from now).