Reduce BFT Signature Disk Usage

[kayabaNerve]

Per-block finality, with 300 validators, will generate 300 signatures every 6 seconds. This is 100 GB per year solely for block signatures.

Using either BLS or FROST would let us condense this to just 0.33-0.5 GB (as it ends up with just one signature). While BLS would be much slower to verify than a Schnorr signature, and take more space (list of participants, 48 or 96 byte signature), it'd likely be faster overall. With 500 validators, the FROST library (which can still be sped up with table caching, a better multiexp crate, threading...) takes 0.7s to create a signature using the BFT threshold.

BLS signatures are also practically performant and don't require coordination. FROST coordination is a pain likely requiring additional rounds, not to mention multiple additional rounds per individual failure, despite being done as part of the finalization process, which should be kept regular.

My vote would be BLS for BFT accordingly.

Implications for any light client. Considering we're already using Schnorr over Ristretto, we already can't be done in an ETH SC. BLS12-381 has a higher chance of being exposed as a precompile (inactive EIP + usage in ETH2), BUT sr25519 will already be available to Substrate systems.

Related to #47.

Edit: See #96 (comment) for where this issue has developed.

[kayabaNerve]

There is a related half-step of https://eprint.iacr.org/2021/350.pdf, though I wouldn't care for it compared to BLS.

[kayabaNerve]

I believe BLS threshold signatures would be possible without the requirement to note participants, which would further reduce space, though that may not be preferred due to slash mechanics. Key generation would be identical as under FROST, yet I believe, at first glance, signature shares would be direct with the polynomial applied AFTER collection, making it uncaring to which m participate.

[dan-da]

in case it's helpful. https://crates.io/crates/blsttc/7.0.0

[kayabaNerve]

Thanks :) My main concern is it being uncaring towards being constant time, but still good to note.

I personally would want to eye blst, which was the defacto best lib when I last worked with BLS, or a pure-Rust implementation. My concern with a pure-Rust implementation is if it solely implements the curve, when blst implements the suite (from key generation to signing to PoPs according to standard).

The raw curve would be appreciated so we can implement our own threshold scheme on top however, which may be trivial (reusing the FROST key-gen with just a few scalarmuls on top), yet blst should still expose enough for that making it a non-issue.

[kayabaNerve]

Threshold signatures would require the coordinated creation of a BLS key per validator set. While this is a one-time action distinct from how FROST would require it for every round, it is notable as VSSS still executes in polynomial time. It does save ~300 bytes per block however (as if we have 300 participants, they each need 1 byte to denote their presence in an offset increment scheme where values 0, 0, 1 translate to participating indexes 0, 1, 3).

[dan-da]

I personally would want to eye blst

blsttc offers the threshold_crypto api but uses blst under the hood.

Threshold signatures would require the coordinated creation of a BLS key per validator set

https://crates.io/crates/bls_dkg

[kayabaNerve]

Thanks for the correction :)

We also already have our own DKG as part of FROST, so I believe we'd just want to use that as it should work with BLS without issue (assuming ff/Group exposure). This becomes more notable thanks to topics such as #56 which would immensely decrease runtime performance costs, if its feasible. If we do a BLS DKG now around Serai's lib, we get that for free without having to redo the usage.

Though as of right now, I'm personally more leaning towards keeping consensus non-interactive just as interactive protocols are n-of-n, not 2/3n+1-of-n. We should also be able to sufficiently compress validator indexes. Instead of 0, marking a natural increment of 1, its possible to use 0 to skip an index, and use n to say the next n validators in the list participated. Given we more often than not have a sequence, it effectively offers compression there.

A halfway step, with the same API, not requiring pulling in BLS, is the above Schnorr compression though.

[kayabaNerve]

Since we have Tendermint for BFT, this is for Tendermint, which does have an explicit sig aggregation API.

[kayabaNerve]

https://forum.polkadot.network/t/new-research-result-regarding-efficient-verification-of-bls-signatures/1219 is extremely interesting regarding BLS performance. If we do move to BLS, we'd likely want to support this.

[kayabaNerve]

Per the recent commit mentioning this issue, we no longer use Tendermint in for Substrate's BFT. When we discuss #163, we discuss a temporal chain which doesn't need aggregation. This solely becomes a issue on optimizing Substrate.

I don't care to mess with GRANDPA too much. While yes, we can have a BLS DKG and submit votes with a threshold BLS scheme, GRANDPA should enable aggressive pruning of signatures (just one justification per epoch). This should make this issue not worth the effort to further optimize it. We do need to verify that pruning is performed (or that warp sync will only sync one commit per epoch, effectively pruning).

[kayabaNerve]

Tributaries are disposable and now have half-aggregation. GRANDPA only needs one justification per epoch. I don't care to do anything more given the reward for the complexity being no where near worth it.

[kayabaNerve]

... changing to wont-fix since half-aggregation had its own issue and nothing further (as discussed in this issue) was done.