[consensus] aggregate BLS signatures in LedgerInfo and timeout certificate

[zekun000]

We use a naive signature aggregation with Ed25519 by using a BTreeMap<Author, Signature> https://github.com/aptos-labs/aptos-core/blob/d216b5af246352327d44ded4c03af8205c19e31a/types/src/ledger_info.rs#L198

BLS enables us to aggregate those signatures into a single one with a bit mask on the validator set indicating the corresponding author.

If we have a set of validators [a, b, c, d] and signatures from [a, c, d], the original form is {a: S_a, c: S_c, d: S_d} and the new form is {[1, 0, 1, 1], S_agg}

On verification we need to turn the bitmask into original public keys and aggregate them into a single public and verify the aggregated signature. more details in https://github.com/aptos-labs/aptos-core/blob/f70a00eeea3b5f02508f7423538fec097634a213/crates/aptos-crypto/src/bls12381/mod.rs#L188

Translating between author to bitmask and back to public key happens in ValidatorVerifier https://github.com/aptos-labs/aptos-core/blob/d216b5af246352327d44ded4c03af8205c19e31a/types/src/validator_verifier.rs#L167

Today the struct serves as both aggregator and proof, we'll need to have a separate aggregator to keep individual signatures until enough staking power and do the aggregation. like here it uses the LedgerInfoWithSignatures to track all the pending signature but we'll need to have a different struct to do that https://github.com/aptos-labs/aptos-core/blob/274c3356f834bff5ee117f50c5cdbd41d3f2d8f7/consensus/src/pending_votes.rs#L51

Once we're done with aggregating LedgerInfoWithSignatures, we can aggregate the TimeoutCertificate too. Unlike the multi-sig in LedgerInfo, this is an aggregate signature over different messages. https://github.com/aptos-labs/aptos-core/blob/d216b5af246352327d44ded4c03af8205c19e31a/consensus/consensus-types/src/timeout_2chain.rs#L103

[alinush]

@zekun000, you linked to the multisig example. The aggregate example is in https://github.com/aptos-labs/aptos-core/blob/f70a00eeea3b5f02508f7423538fec097634a213/crates/aptos-crypto/src/bls12381/mod.rs#L277

[zekun000]

we need multisig for ledger info and aggregate for timeout certificate

[alinush]

Then it would be good to clearly differentiate between multisig and aggregate sigs in your issue... I can edit it.

[sitalkedia]

@zekun000 - Can you clarify why we need aggregate for timeout? In other words, why the timeout message would be different for different validators?

[zekun000]

you can take a look at the timeout struct, it contains the local highest qc from each node which is used for the 2-chain safety rules

[sitalkedia]

@zekun000 , @alinush - Can you clarify when and how are we going to verify PoP - https://github.com/aptos-labs/aptos-core/blob/f70a00eeea3b5f02508f7423538fec097634a213/crates/aptos-crypto/src/bls12381/mod.rs#L148. Should this be done once per round before aggregating the signatures?

[alinush]

This need only be done once per public key, before relying on that public key to verify signatures. The best time to check its PoP is when you deserialize that PK (and its PoP) from disk and load it up in memory. Past that point, you can trust that PK.

[zekun000]

PoP is checked when the validator joins or rotates the key. it’s already implemented