n-signature to (n+1)/2-signature compression

[kayabaNerve]

Inspired by #96. The interesting part is that unlike #96, detailing the BFT process, which described either:

• Specifying signer indexes
• DKGs
• Interactive signing

This would require none of them and be applicable to all transactions without an overhead, setup, or interactivity.

For a list of schnorr signatures R, s, you can simply store {R_i}, sum(s) and perform full verification. While this does introduce malleability (which may be reducible to some degree by not using a straight sum), the validators did handle the original R, s properly (assuming they were honest, which is an assumption already made) and are solely archiving the compressed form.

I don't care to do this at launch, yet it is critical we ensure Substrate isn't hashing signatures into blocks as that is a requirement to consider pre-launch. It'd enable pruning half of all signatures from the database while reducing bandwidth accordingly for syncing parties.

[kayabaNerve]

https://eprint.iacr.org/2021/350.pdf for the exact paper detailing this.

While Substrate by default uses Multisignature, which is ECDSA, Ed25519, and Ristretto, we only use Ristretto enabling this without hassle across all TX signatures.

[kayabaNerve]

The Tendermint branch has an explicit signature aggregration API which would enable utilization of this without issue. With regards to post-application, justifications should never be placed on-chain, making this feasible.

[kayabaNerve]

As a correction to my above commentary, the paper did not introduce malleability. That was a misunderstanding on my end.

[kayabaNerve]

Adding Tendermint label since remaining part of this issue is integrating with Tendermint.

[kayabaNerve]

Resolved with #346.