Trying to split parts of the
https://github.com/paritytech/polkadot-sdk/pull/1903 into smaller PRs

For https://github.com/paritytech/polkadot-sdk/pull/1903 it would help
if `verify_with_validator_set()` returned the list of valid
authority-signatures pairs, since after the verification we need to send
them in the equivocation proof.

This is the significant step to make BEEFY client able to handle both
ECDSA and (ECDSA, BLS) type signature. The idea is having BEEFY Client
generic on crypto types makes migration to new types smoother.

This makes the BEEFY Keystore generic over AuthorityId and extends its
tests to cover the case when the AuthorityId is of type (ECDSA,
BLS12-377)

---------

Co-authored-by: Davide Galassi <[email protected]>
Co-authored-by: Robert Hambrock <[email protected]>

* Merged BEEFY primitives with generic signature and keyset commitment support from old pull to current code

* - Add bls-experimental feature to application-crypto and beefy primitives
- Fix remaining crypto -> ecdsa_crypto
- code build but not tests

* Make beefy primitive tests compile

* move bls related beefy primitives code and test behind bls-experimental flag

* Make BEEFY clients complies with BEEFY API depending on AuthorityId

* - Rename `BeefyAuthoritySet.root` → `BeefyAuthoritySet.keyset_commitment`.
- Remove apk proof keyset_commitment from `BeefyAuthoritySet`.
- Fix failing signed commitment and signature to witness test.
- Make client compatible with BeefyAPI generic on AuthorityId.
- `crypto` → `ecdsa_crypto` in BEEFY client and frame.

* Commit Cargo lock remove ark-serialize from BEEFY primitives

* Use Codec instead of Encode + Decode in primitives/consensus/beefy/src/lib.rs

Co-authored-by: Davide Galassi <[email protected]>

* - Make `BeefyApi` generic over Signature type.
- Make new `BeeyApi` functinos also generic over AuthorityId and Signature

* Unmake BeefyAPI generic over Signature. Recover Signature type from AuthId.

* - dont use hex or hex-literal use array-bytes instead in beefy primitives and bls crypto.
- CamelCase ECDSA and BLS everywhere.

* Move the definition of BEEFY key type from `primitives/beefy` to `crypto.rs` according to new convention.

* - Add bls377_generate_new to `sp-io` and `application_crypto::bls`.
- Add `bls-experimental` to `sp-io`

Does not compile because PassByCodec can not derive PassBy using customly implemented PassByIner.

* Implement PassBy for `bls::Public` manually

* fix Beefy `KEY_TYPE` in `frame/beefy` tests to come from `sp-core::key_types` enum

* specify both generic for `hex2array_unchecked` in `sp-core/bls.rs`

* Rename `crypto`→`ecdsa_crypto` in `primitives/consensus/beefy/src/test_utils.rs` docs

* remove commented-out code in `primitives/consensus/beefy/src/commitment.rs`

Co-authored-by: Davide Galassi <[email protected]>

* Fix inconsistency in panic message in  `primitives/io/src/lib.rs`

Co-authored-by: Davide Galassi <[email protected]>

* Remove redundant feature activation in `primitives/io/Cargo.toml`

Co-authored-by: Davide Galassi <[email protected]>

* - make `w3f-bls` a dev-dependancy only for beefy primitives.

- clean up comments.

Co-authored-by: Davide Galassi <[email protected]>

* export BEEFY KEY_TYPE from primitives/consensus/beefy
make `frame/consensus/beefy` in dependent of sp_crypto_app
use consistent naming in the beefy primitive tests.

* - implement `BeefyAuthorityId` for `bls_crypto::AuthorityId`.
- implement `bls_verify_works` test for BEEFY `bls_crypto`.

* Remove BEEFY `ecdsa_n_bls_crypto` for now for later re-introduction

* Make commitment and witness BEEFY tests not use Keystore.

* put `bls_beefy_verify_works` test under `bls-experimental` flag.

* bump up Runtime `BeefyAPI` to version 3 due to introducing generic AuthorityId.

* reuse code and encapsulate w3f-bls backend in sp-core as most as possible

Co-authored-by: Davide Galassi <[email protected]>

* Make comments in primities BEEFY `commitment.rs` and `witness.rs``tests convention conforming

* Use master dep versions

* Trivial change. Mostly to trigger CI

* Apply suggestions from code review

Co-authored-by: André Silva <[email protected]>

* Fix Cargo.toml

* Trigger CI with cumulus companion

* Trigger CI after polkadot companion change

---------

Co-authored-by: Davide Galassi <[email protected]>
Co-authored-by: André Silva <[email protected]>

* Do some cleanups

Found them while looking over the code.

* More

* Fix

* add cost/benefit to gossip messages
* report BEEFY gossip peer reputation changes
* drop WorkerParams helper struct
* add reputation costs to tests
* add peer reputation cost/benefit to on-demand-requests protocol
* include amount of signatures checked in invalid proof reputation cost

Signed-off-by: Adrian Catangiu <[email protected]>

* sc-consensus-beefy: add justifications to gossip protocol

* sc-consensus-beefy: voter gossips finality proofs

* sc-consensus-beefy: add finality proof gossip test

* sc-consensus-beefy: always gossip finality proof

Gossip finality proof in _both_ cases of reaching finality threshold
through votes:
1. threshold reached through self vote,
2. threshold reached through incoming vote.

* address comments

* Move beefy primitives to consensus dir
* Move beefy gadget to client consensus folder
* Rename beefy crates

* Change copyright year to 2023 from 2022

* Fix incorrect update of copyright year

* Remove years from copy right header

* Fix remaining files

* Fix typo in a header and remove update-copyright.sh

* client/beefy: simplify self_vote logic

* client/beefy: migrate to new state version

* client/beefy: detect equivocated votes

* fix typos

* sp-beefy: add equivocation primitives

* client/beefy: refactor vote processing

* fix version migration for new rounds struct

* client/beefy: track equivocations and create proofs

* client/beefy: adjust tests for new voting logic

* sp-beefy: fix commitment ordering and equality

* client/beefy: simplify handle_vote() a bit

* client/beefy: add simple equivocation test

* client/beefy: submit equivocation proof - WIP

* frame/beefy: add equivocation report runtime api - part 1

* frame/beefy: report equivocation logic - part 2

* frame/beefy: add pluggable Equivocation handler - part 3

* frame/beefy: impl ValidateUnsigned for equivocations reporting

* client/beefy: submit report equivocation unsigned extrinsic

* primitives/beefy: fix tests

* frame/beefy: add default weights

* frame/beefy: fix tests

* client/beefy: fix tests

* frame/beefy-mmr: fix tests

* frame/beefy: cross-check session index with equivocation report

* sp-beefy: make test Keyring useable in pallet

* frame/beefy: add basic equivocation test

* frame/beefy: test verify equivocation results in slashing

* frame/beefy: test report_equivocation_old_set

* frame/beefy: add more equivocation tests

* sp-beefy: fix docs

* beefy: simplify equivocations and fix tests

* client/beefy: address review comments

* frame/beefy: add ValidateUnsigned to test/mock runtime

* client/beefy: fixes after merge master

* fix missed merge damage

* client/beefy: add test for reporting equivocations

Also validated there's no unexpected equivocations reported in the
other tests.

Signed-off-by: acatangiu <[email protected]>

* sp-beefy: move test utils to their own file

* client/beefy: add negative test for equivocation reports

* sp-beefy: move back MmrRootProvider - used in polkadot-service

* impl review suggestions

* client/beefy: add equivocation metrics

---------

Signed-off-by: acatangiu <[email protected]>
Co-authored-by: parity-processbot <>

* client/beefy: detect equivocated votes

* client/beefy: make sure to persist state after voting

* client/beefy: drop never-used aux-schema v2 migration

* impl review suggestion

---------

Signed-off-by: Adrian Catangiu <[email protected]>

* primitives/beefy: move Payload to its own file

* primitives/beefy: add Payload tests

* primitives/beefy: add MmrRootProvider as custom BEEFY payload provider

* client/beefy: use generic BEEFY 'PayloadProvider'

* primitives/beefy: rename Payload::new to Payload::from_single_entry for clarity

* fix visibility

* fix cargo doc

* beefy: use VersionedFinalityProof instead of SignedCommitment.

* Change the exposed RPC API to support versioned proofs.

Co-authored-by: Adrian Catangiu <[email protected]>

* client/beefy: don't accept vote for older rounds

* client/beefy: clean up and reorg the worker struct

* client/beefy: first step towards Full BEEFY

The first step from Lean->Full BEEFY is to have the worker
enforce uninterrupted line of BEEFY finalized mandatory blocks.

There is one mandatory block per session (the first block in the
session). As such, votes processing and votes generation now
enforces that all mandatory blocks are finalized in strict
monotonically increasing sequence and no block 'N' will be worked
on if there is any GRANDPA finalized but BEEFY non-final mandatory
block 'M', where 'M < N'.

Implementation details:

- Introduced 'VoterOracle' to separate the voting decisions logic,
  and track new/pending sessions.

- New sessions get queued up with the worker operating either:
  1. up-to-date - all mandatory blocks leading up to current GRANDPA
     finalized: queue has ONE element, the 'current session' where
     `mandatory_done == true`,
  2. lagging behind GRANDPA: queue has [1, N] elements, where all
     `mandatory_done == false`.
     In this state, everytime a session gets its mandatory block
     BEEFY finalized, the session is popped off the queue,
     eventually getting to operating mode `1. up-to-date`.

- Votes get triaged and those that fall withing the `VoterOracle`
  allowed window get processed, the others get dropped if stale,
  or buffered for later processing (when they reach the window).

- Worker general code was also updated to fall in one of two roles:
  1. react to external events and change internal 'state',
  2. generate events/votes based on internal 'state'.

Signed-off-by: acatangiu <[email protected]>

* client/beefy: sketch idea for block import and sync

Signed-off-by: acatangiu <[email protected]>

* client/beefy: add BEEFY block import

* client/beefy: process justifications from block import

* client/beefy: add TODOs for sync protocol

* client/beefy: add more docs and comments

* client/beefy-rpc: fix RPC error

* client/beefy: verify justification validity on block import

* client/beefy: more tests

* client/beefy: small fixes

- first handle and note the self vote before gossiping it,
- don't shortcircuit on err when processing pending votes.

* client/beefy: remove invalid justifications at block import

* todo: beefy block import tests

* RFC: ideas for multiple justifications per block

* Revert "RFC: ideas for multiple justifications per block"

This reverts commit 8256fb07d3124db69daf252720b3c0208202624d.

* client/beefy: append justif to backend on block import

* client/beefy: groundwork for block import test

* client/beefy: groundwork2 for block import test

* client/beefy: groundwork3 for block import test

* client/beefy: add block import test

* client/beefy: add required trait bounds to block import builder

* remove client from beefy block import, backend gets the job done

Signed-off-by: acatangiu <[email protected]>