* more backports from Cumulus subtree

* spelling

* fmt

* trigger CI

* Revert "trigger CI"

This reverts commit b009d732.

* Revert "Revert "trigger CI""

This reverts commit 715606a7.

* Revert "Revert "Revert "trigger CI"""

This reverts commit dc0d2233.

* Updated version according to Cumulus

* Renaming

* Cargo.lock

* backport cumulus changes

* bump substrate & polkadot and make it build

* fix runtimes

* bump substrate, polkadot & cumulus

* fix build: remove ump leftovers

* fix tests: disable runtime version check in tests

* fix build: use sp_version::runtime_version macro

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

Bumps [scale-info](https://github.com/paritytech/scale-info) from 2.5.0 to 2.6.0.
- [Release notes](https://github.com/paritytech/scale-info/releases)
- [Changelog](https://github.com/paritytech/scale-info/blob/master/CHANGELOG.md)
- [Commits](https://github.com/paritytech/scale-info/commits)

---
updated-dependencies:
- dependency-name: scale-info
  dependency-type: direct:production
  update-type: version-update:semver-minor
...

Signed-off-by: dependabot[bot] <[email protected]>

Bumps [scale-info](https://github.com/paritytech/scale-info) from 2.4.0 to 2.5.0.
- [Release notes](https://github.com/paritytech/scale-info/releases)
- [Changelog](https://github.com/paritytech/scale-info/blob/master/CHANGELOG.md)
- [Commits](https://github.com/paritytech/scale-info/compare/v2.4.0...v2.5.0)

---
updated-dependencies:
- dependency-name: scale-info
  dependency-type: direct:production
  update-type: version-update:semver-minor
...

Signed-off-by: dependabot[bot] <[email protected]>

Bumps [finality-grandpa](https://github.com/paritytech/finality-grandpa) from 0.16.1 to 0.16.2.
- [Release notes](https://github.com/paritytech/finality-grandpa/releases)
- [Commits](https://github.com/paritytech/finality-grandpa/compare/v0.16.1...v0.16.2)

---
updated-dependencies:
- dependency-name: finality-grandpa
  dependency-type: direct:production
  update-type: version-update:semver-patch
...

Signed-off-by: dependabot[bot] <[email protected]>

* Bump substrate/polkadot/cumulus

* sp_finality_grandpa - >sp_consensus_grandpa

* sp_beefy -> sp_consensus_beefy

* pallet_randomness_collective_flip -> pallet_insecure_randomness_collective_flip

* fix

* Cumulus parachain stuff

* Cumulus parachain stuff one more

* Millau/Rialto runtimes

* Removed pallet_insecure_randomness_collective_flip

* Millau node

* Removed session historial

* TMP: just try disable all fetches

* Docs in gitlab.yml

* Cleaning deps + satisfy `cargo build --release --all-targets --all-features`

* PR fixes

* update Substrate/Polkadot/Cumulus refs

* finality-grandpa 0.16

* fix miillau-runtime compilation

* fix rialto runtime compilation

* fixed rialto-parachain runtime compilation

* backport GRANDPA test fixes

* helper instead of removed record_all_keys

* substrate-relay is compiling

* millau-bridge-node at least compiles

* rialto-bridge-node at least compiles

* rialto-parachain-collator compiles

* fixings tests (wip)

* fmt

* fixed BEEFY alert

* clippy

* removed unused dep

* -extra var

* move Leaf to mod mmr

* fix benchmarks

* Bump log version to 0.4.17

* Removed unnecesseray dependency + rename BridgeGrandpaMillauCall to BridgeGrandpaCall

* switch to gav-xcm-v3 branch (wip)

* add comment

* play with CI

* keep playing with CI

* play with CI

* trigger CI

* Revert "trigger CI"

This reverts commit fc35ac64.

* cumulus: 4e952282914719fafd2df450993ccc2ce9395415
polkadot: 975e780ae0d988dc033f400ba822d14b326ee5b9
substrate: 89fcb3e4f62d221d4e161a437768e77d6265889e

* fix refs

* sync changes from https://github.com/paritytech/polkadot/pull/3828

* sync changes from https://github.com/paritytech/polkadot/pull/4387

* sync changes from https://github.com/paritytech/polkadot/pull/3940

* sync with changes from https://github.com/paritytech/polkadot/pull/4493

* sync with changes from https://github.com/paritytech/polkadot/pull/4958

* sync with changes from https://github.com/paritytech/polkadot/pull/3889

* sync with changes from https://github.com/paritytech/polkadot/pull/5033

* sync with changes from https://github.com/paritytech/polkadot/pull/5065

* compilation fixes

* fixed prometheus endpoint startup (it now requires to be spawned within tokio context)

* substrate: d0f6c1c60da22e04dd25c2eca46ebfe6f1571af0
polkadot: dd4b2e6a34a08a01b876d14641e99e7011be3463
cumulus: 9379cd6c1863ea846ad6c6a8cbbc99848dd5d693

* fmt

* fixed lost refs

* spelling

* benckhmarks

* fmt

* Remove Trailing Space

* Correct Source Chain Name

* Remove `pallet-substrate-bridge`

* Fix transfer call encoding test

Co-authored-by: Tomasz Drwięga <[email protected]>

* Add benchmarking skeleton

* Allow runtime to indicate concrete header type for benches

* Set up skeleton for benchmark tests

* Play around with mutating bench header

* Create a working test for benchmarking

* Add benches related to enacting authority set changes

* Add bench for checking effect of prec-commits/vote ancestries

* Use new `no_std` test utils in benchmarks

* Support pallet instances in benchmarking

* Use correct benchmarking instance macro

* Add instance to runtime benchmark helper impl

* Start using new justification creation API

* Allow mock header's number to be specified

* Set up benches with correct fork/depth parameters

* Use new pallet name during runtime bench setup

* Use correct `set_id` in tests

* Limit number of forks as workaround to get tests passing

* Use number of authorities which matches number of forks

* Make sure test post-conditions are checked properly

* Only read `CurrentAuthoritySet` from storage once

* Add combined benchmark for `submit_finality_proof`

* Add bench test

* Introduce config bounds related to justification verification

* Use config consts from pallet in benchmarking

* Return data relevant to benchmarks from helper functions

* Annotate `submit_finality_proof` with autogenerated weights

* Return actual weight after call execution

* Ignore Clippy warnings in bench template

* Update benchmark template

* Use `test-utils` to create test headers

* Clarify that helper is only for messages benches

* Add more documentation to benches

* Update TODOs

* Clarify return types in comment

* Fix pallet name post-merge

* Update NOTE to a TODO item

* Indicate that Config params are max values, not actual values

* Change Config validator count type to be `u32`

* Return decoded justification instead of fields

* Add missing trait bounds for tests

* Correctly issue weight refund

Thanks for spotting this Tomek!

* Update comment

* Add note about SESSION_LENGTH

* Fix benchmarking code

* Rename `pallet-finality-verifier` to `pallet-bridge-grandpa`

* Missed some CamelCase ones

* Update logging target in GRANDPA pallet

* Rename `pallet-bridge-call-dispatch` to `pallet-bridge-dispatch`

* Rename the dispatch pallet folder

* Update logging target in Dispatch pallet

* Missed a couple

* Format the repo

* Stop listing individual pallets in Compose logs

* Use correct pallet name in module doc comments

* Add `pallet-bridge-dispatch` to README project layout

* Sort crate names in TOML files

* Rename `pallet-bridge-grandpa` runtime Call alias

* Make Substrate deps uniform

* Rest of the deps.

* Fix broken merge.

* Revert substrate.

* Fix tests

Co-authored-by: Pierre Krieger <[email protected]>

* Move storage proof checker to runtime primtives

* Add method for parsing storage proofs

* Use finality-verifier pallet in runtime-common

* Get bridge pallet compiling again

* Use storage prover from bp-runtime in a few more places

* Don't leak `std` items from proof helper into `no-std` builds

* Fix benchmarking compilation

* Remove unused import in fuzzer

* Bump Substrate to version used by Polkadot (`5f056830`)

* Use `log` crate for runtime logging

See https://github.com/paritytech/substrate/pull/8128/ for more info.

* Stop using return value from `execute_block`

* Update test weight

* Add relevant storage items from Substrate pallet

* Add function for importing finalized headers to storage

* Remove unused getter functions

* Add GenesisConfig to pallet

* Add initialization extrinsic

* Add operational extrinsic

* Get existing finality verifier tests compiling again

* Add tests for pallet initialization

* Add tests related to pallet's operational status

* Update tests which were using `pallet-substrate-bridge`

* Add tests related to header imports

* Use wrapper function when init-ing some tests

* Add prefix to tests related to rate limiter

* Fix failed compilation related to GenesisConfig

* Add some documentation

* Change some extrinsics to be Operational

* Add public interface to pallet

* Implement runtime APIs for finality-verifier pallet

* Justify use of `expect` when importing headers

* Reject headers with forced changes

* Add weight to initialize extrinsic

* Remove TODO which will be addressed later

* Move succesful import log to correct location

* Expand proof for when `best_finalized` is fetched

* Move check for newer finalized blocks earlier in pipeline

* Rename `ConflictingFork` error to be more generic

* Only compute finality_target's hash once

* Add missing documentation to Runtime APIs

* Add TODO about using `set_id` from `ScheduledChange` digest

* Bump substrate deps.

* Bump scale.

* Bump ethabi.

* Remove inherent from aura.

* Migrate to construct_runtime

* cargo fmt --all

* Make AncestryProof type more flexible

* Only import single finalized header instead of a chain

* Fix unchecked header import tests

* Add option for limiting ancestry proof size

* Update finality verifier Config in runtimes

* Update some documentation

* Fix Clippy warning

* Allow AncestryChecker to return proof size

Stops us from abusing the `Size` trait

* Remove Size impl for Vec<T>

* Remove size contraints for ancestry proofs

With different proof types its unclear how to "size" should be interpreted,
so we remove this requirement all together to avoid confusion.

* Add Finality Verifier pallet to runtimes

* Implement simple ancestry checker

* Use the new checker in runtimes

* Remove unused import warning

* Bump max allowed ancestry proof size

* Add a few optimization suggestions when verifying ancestry

* Use session length as upper bound for ancestry proof size

* Remove unused time units

* Add skeleton for `pallet-finality-verifier`

* Sketch out implementation for importing finality proofs

* Get pallet compiling

* Introduce skeleton for mock runtime

* Start using real Grandpa types in finality pallet

* Redefine types in header chain primitives crate

* Implement HeaderChain for Substrate bridge pallet

* Plug Substrate Bridge Pallet into verifier mock

* Fix compilation of `header-chain` primitives

* Start writing to base pallet storage

* Add first "cross-pallet" test

* Move keyring primitives used in tests to shared crate

* Stop pulling `std` deps into `no_std` builds

* Revert "Stop pulling `std` deps into `no_std` builds"

This reverts commit f74dd660.

* Revert "Move keyring primitives used in tests to shared crate"

This reverts commit b774fa73.

* Use new SS58Prefix type in mock

* Start using `bp-test-utils` in finality pallet

* Start using real justification code

* Get a test working with real justification verification

* Add basic tests for invalid proofs

* Get rid of AncestryProof config type

* Add error types to transaction outcome

* Bound number of headers allowed in a single ancestry proof

* Disallow invalid authority sets

* Remove unused items

* Add some documentation

* Get rid of Clippy warnings

* Rename BaseHeaderChain to TransactionVerifier

* Remove unused code

* Make dummy trait implementations more generic

* Fix more Clippy complaints

* Update tests to use fix for duplicate headers

* Fix benchmarking compilation

* Rename TransactionVerifier to InclusionProofVerifier

* Move justification module to header-chain primitives crate

* Get justification module compiling in new location

* Get justification module tests compiling

* Use justification code from `header-chain` crate

Mostly compiles, having issues with std/test feature flags across crates.

* Move some code around

* Move justification tests to integration testing crate

* Add `test-utils` crate

* Remove tests and test-helper module from justification code

* Use `test-utils` in Substrate bridge pallet tests

* Remove `sp-keyring` related code from `pallet-substrate-bridge`

* Remove `helpers` module from `pallet-substrate-bridge`

* Add some documentation

* Add more documentation

* Fix typo

Co-authored-by: Tomasz Drwięga <[email protected]>

Co-authored-by: Tomasz Drwięga <[email protected]>

* benchmarks for pallet_message_lane::receive_messages_proof

* use CallOrigin::TargetAccount (worst case of CallOrigin)

* fmt

* closures

* Update modules/message-lane/src/benchmarking.rs

Co-authored-by: Hernando Castano <[email protected]>

* Update modules/message-lane/src/benchmarking.rs

Co-authored-by: Hernando Castano <[email protected]>

* fix compilation

Co-authored-by: Hernando Castano <[email protected]>

* migrate back to Substrate master

* fmt

* clippy

* extract ChainBase to bp-runtime

* post-merge fixes

* cargo fmt --all

* compilation fixes

* reexport BlockNumberOf, HashOf, HeaderOf

* get Substrate dependencies from crates.io

* removing unused dependencies

* cargo fmt --all

* remove commented dependencies

* remove commented dependencies again

* try to fix compilation

* Remove the Substrate primitives crate

The types here were only used in one place, the pallet itself. If other
components start using these types we can considering moving them back
into a standalone crate.

* Start trying to integrate justification module

* Make Substrate blocks configurable in Pallet

* WIP: Try and generalize justification test helpers

* Fix tests which use "real" justifications

* Put common test helpers alongside mock code

* Use common helper for creating headers

* Remove usage of UintAuthorityId

This change favours the use of the Ed25519Keyring authorities
in order to keep things consistent with the tests.

* Add documentation around config trait types

* Make test header, hash, and number types consistent

* Update modules/substrate/src/verifier.rs

Co-authored-by: Svyatoslav Nikolsky <[email protected]>

* Update modules/substrate/src/lib.rs

Co-authored-by: Tomasz Drwięga <[email protected]>

* Update modules/substrate/Cargo.toml

Co-authored-by: Svyatoslav Nikolsky <[email protected]>

* Derive `RuntimeDebug` instead of `Debug`

* Add `Paramter` as a trait constraint on config types

Since we use these types as part of the dispatchable functions
we should explicitly require this.

* Enforce that hasher output matches expected hash type

* Accept headers over indexes when making test justifications

* Check that authority sets are valid

* Make Clippy happy

* Apply correct Clippy fix

* Move justification code into primitives module

* Use new module in verifier code

* Add primitives module for Substrate test helpers

* WIP

* Move justification generation into test_helpers

* Revert commits which move `justification` into primitives

This reverts commit 03a381f0

.

Co-authored-by: Svyatoslav Nikolsky <[email protected]>
Co-authored-by: Tomasz Drwięga <[email protected]>

* Change script to update versions.

* Bump versions.

* Address remainders.

* cargo fmt --all

* Fix tests.

* Whitelist BlueOak license

* Fix benchmarks?

* Add pallet template from Substrate Dev Hub

* Clean up un-needed stuff from template

* Sketch out dispatchable interface

* Introduce notion of finality chain

* Add dependencies which were removed during a rebase

* Sketch out idea for finality header-chain pallet

* Sketch out ChainVerifier trait

* Add storage parameter to verifier

* Write out some things I think I need for finality verification

* Add some pseudocode for marking finalized headers

* Remove parity_scale_codec duplicate

* Move verification logic into pallet

I've been struggling with getting the generic types between the storage and verifier
traits to play nice with each other. As a way to continue making progress I'm moving
everything to the pallet. This way I hope to make progress towards a functional
pallet.

* Start doing verification around authority set changes

* Remove commented BridgeStorage and ChainVerifier traits

* Create Substrate bridge primitives crate

* Add logic for updating scheduled authority sets

* Introduce notion of imported headers

* Implement basic header ancestry checker

* Add mock runtime for tests

* Add testing boilerplate

* Add some storage read/write sanity tests

* Add some basic header import tests

* Add tests for ancestry proofs

* Create helper for changing authority sets

* Fix authority set test

Fixes a problem with how the scheduled change was counted as well as
a SCALE encoding issue

* Correctly check for scheduled change digests

There's no guarantee that the consensus digest item will be the last
one in a header, which is how it was previously being checked.

Thanks to Andre for pointing me to the Grandpa code that does this.

* Mark imported headers as finalized when appropriate

When a header that finalizes a chain of headers is succesfully imported
we also want to mark its ancestors as finalized.

* Add helper for writing test headers

* Add test helper for scheduling authority set changes

* Bump Substrate pallet and primitives to rc6

* Remove Millau verifier implementation

* Add some doc comments

* Remove some needless returns

* Make Clippy happy

* Split block import from finalization

* Make tests compile again

* Add test for finalizing header after importing children

* Create a test stub for importing future justifications

* Start adding genesis config

* Reject justifications from future

We should only be accepting justifications for the header
which enacted the current authority set. Any ancestors of
that header which require a justification can be imported
but they must not be finalized.

* Add explanation to some `expect()` calls

* Start adding GenesisConfig

* Plug genesis config into runtime

* Remove tests module

* Check for overflow when updating authority sets

* Make verifier take ownership of headers during import

* Only store best finalized header hash

Removed the need to store the whole header, since we store
it was part of the ImportedHeaders structure anyways

* Add some helpers to ImportedHeader

* Update ancestry checker to work with ImportedHeaders

* Update ancestry tests to use ImportedHeaders

* Update import tests to use ImportedHeaders

* Clean up some of the test helpers

* Remove stray dbg!

* Add doc comments throughout

* Remove runtime related code

* Fix Clippy warnings

* Remove trait bound on ImportedHeader struct

* Simplify checks in GenesisConfig

* Rename `get_header_by_hash()`

* Alias `parity_scale_codec` to `codec`

* Reword Verifier documentation

* Missed codec rename in tests

* Split ImportError into FinalizationError

* Remove ChainVerifier trait

This trait was a remenant of the original design, and it is not required
at the moment. Something like it should be added back in the future to
ensure that other chains which conform to this interface can be used
by higher-level bridge applications.

* Fix the verifier tests so they compile

* Implement Deref for ImportedHeader

* Get rid of `new` methods for some Substrate primitives

* Ensure that a child header's number follows its parent's

* Prevent ancestry checker from aimlessly traversing to genesis

If an ancestor which was newer than the child header we were checking we
would walk all the way to genesis before realizing that we weren't related.
This commit fixes that.

* Remove redundant clones

* Ensure that old headers are not finalized

Prevents a panic where if the header being imported and `best_finalized`
were the same header the ancestry checker would return an empty list. We
had made an assumption that the list would always be populated, and if this
didn't hold we would end up panicking.

* Disallow imports at same height as `best_finalized`

* Fix Clippy warnings

* Make NextScheduledChange optional

* Rework how scheduled authority set changes are enacted

We now require a justification for headers which _enact_ changes
instead of those which _schedule_ changes. A few changes had to
be made to accomodate this, such as changing when we check for
scheduled change logs in incoming headers.

* Update documentation for Substrate Primitives

* Clarify why we skip header in requires_justification check

* Add description to assert! call

* Fix formatting within macros

* Remove unused dependencies from runtime

* Remove expect call in GenesisConfig

* Turn FinalityProof into a struct

* Add some inline TODOs for follow up PRs

* Remove test which enacted multiple changes

This should be added back at some later point in time, but right now
the code doesn't allow for this behaviour.

* Use `contains_key` when checking for header

This is better than using `get().is_some()` since we skip
decoding the storage value

* Use initial hash when updating best_finalized

* Add better checks around enacting scheduled changes

* Rename finality related functions

* Appease Clippy

* verify justifications from runtime

* unreachable