Bumps [subxt](https://github.com/paritytech/subxt) from 0.35.3 to 0.36.0.
- [Release notes](https://github.com/paritytech/subxt/releases)
- [Changelog](https://github.com/paritytech/subxt/blob/master/CHANGELOG.md)
- [Commits](https://github.com/paritytech/subxt/compare/v0.35.3...v0.36.0)

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

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

Bumps [anyhow](https://github.com/dtolnay/anyhow) from 1.0.83 to 1.0.86.
- [Release notes](https://github.com/dtolnay/anyhow/releases)
- [Commits](https://github.com/dtolnay/anyhow/compare/1.0.83...1.0.86)

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

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

Bumps [thiserror](https://github.com/dtolnay/thiserror) from 1.0.60 to 1.0.61.
- [Release notes](https://github.com/dtolnay/thiserror/releases)
- [Commits](https://github.com/dtolnay/thiserror/compare/1.0.60...1.0.61)

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

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

* bump BHP version

* bump relay version

* fixed relayer metric value

* use master refs + fmt

* up polkadot-sdk deps

* bump relayer version

* subcommand to relay messages range

* fmt

* use master refs

Bumps [thiserror](https://github.com/dtolnay/thiserror) from 1.0.59 to 1.0.60.
- [Release notes](https://github.com/dtolnay/thiserror/releases)
- [Commits](https://github.com/dtolnay/thiserror/compare/1.0.59...1.0.60)

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

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

Bumps [serde](https://github.com/serde-rs/serde) from 1.0.200 to 1.0.201.
- [Release notes](https://github.com/serde-rs/serde/releases)
- [Commits](https://github.com/serde-rs/serde/compare/v1.0.200...v1.0.201)

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

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

Bumps [scale-info](https://github.com/paritytech/scale-info) from 2.11.2 to 2.11.3.
- [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.11.2...v2.11.3)

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

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

Bumps [anyhow](https://github.com/dtolnay/anyhow) from 1.0.82 to 1.0.83.
- [Release notes](https://github.com/dtolnay/anyhow/releases)
- [Commits](https://github.com/dtolnay/anyhow/compare/1.0.82...1.0.83)

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

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

Bumps [serde_json](https://github.com/serde-rs/json) from 1.0.116 to 1.0.117.
- [Release notes](https://github.com/serde-rs/json/releases)
- [Commits](https://github.com/serde-rs/json/compare/v1.0.116...v1.0.117)

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

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

* added relay-parachain-head subcommand support to substrate-relay binary

* bump polkadot-sdk

* custom branch -> master

Bumps [serde](https://github.com/serde-rs/serde) from 1.0.199 to 1.0.200.
- [Release notes](https://github.com/serde-rs/serde/releases)
- [Commits](https://github.com/serde-rs/serde/compare/v1.0.199...v1.0.200)

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

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

Bumps [num-traits](https://github.com/rust-num/num-traits) from 0.2.18 to 0.2.19.
- [Changelog](https://github.com/rust-num/num-traits/blob/master/RELEASES.md)
- [Commits](https://github.com/rust-num/num-traits/compare/num-traits-0.2.18...num-traits-0.2.19)

---
updated-dependencies:
- dependency-name: num-traits
  dependency-type: direct:production
  update-type: version-update:semver-patch
...

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

Bumps [serde](https://github.com/serde-rs/serde) from 1.0.198 to 1.0.199.
- [Release notes](https://github.com/serde-rs/serde/releases)
- [Commits](https://github.com/serde-rs/serde/compare/v1.0.198...v1.0.199)

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

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

* added FreeHeadersInterval to pallet-bridge-grandpa configuration

* added is_free_execution_expected parameter to the submit_finality_proof_ex + check it from the transaction extension

* move transaction extensions to a separate folder

* move grandpa call result check from RefundTransactionExtensionAdapter to RefundBridgedGrandpaMessages

* added RefundBridgedMessages to refund and bump priority of standalone messages transactions

* check_obsolete_submit_finality_proof may now boost transaction priority (this is not used yet - see next commit)

* added CheckAndBoostBridgeGrandpaTransactions that checks whether bridge GRANDPA transactions are obsolete and, if not, it may apply priority boost to

* relayer may be slashed to explicit account

* slash registered relayer if it has submitted failed GRANDPA transaction

* allow accepting some parachain headers for free

* added FreeParachainUpdateForFreeRelayHeader

* fix benchmarks compilation

* added WeightInfoExt for pallet-bridge-grandpa to include extra wight coming from CheckAndBoostBridgeGrandpaTransactions

* added free_headers_interval to the (runtime) FinalityApi of the chain

* added --only-free-headers CLI parameter (not used yet) to finality and complex relay

* actually use HeadersToRelay::Free in finality-relay

* actually support only-free-headers mode in parachains relay

* removed inactual comment (free_source_headers_interval is cached at relay level)

* added comment re free-headers-only support in on-demand parachains relay

* added --only-free-headers support to standalone parachains relay

* fixed dependency in runtime-codegen

* update RBH and WBH runtimes + ask for free execution if we are running in HeadersToRelay::Free mode

* add missing standalone RBH<>WBH finality relay

* also refund for submitting initial parachain head

* make FreeHeadersRemaining an Option => we know that when we are outside of tx body, it is `None` and otherwise it is `Some`

* add some traces to relay

* add more traces to pallets

* check for reorgs in signed ext for parachains module

* fix benchmarks compilation

* free interval instead of fixed free headers

* updated relays for new free headers criteria

* fixed trace

* CannotAcceptMoreFreeHeaders -> FreeHeadersLimitExceded

* additional_call_result_check -> check_call_result_ex

* is_granda_call_succeeded -> is_grandpa_call_successful

* move tx priority boost from check_obsolete_submit_finality_proof to extension

* lost changes

* dec counter when importing new para header

* limit maximal "free" parachain head size

* added grandpa_and_parachain_pallets_share_free_headers_counter test

* with free intervals (instead of fixed free headers) we need to check `improved_by` from extension code

* fix test name

* added CheckAndBoostBridgeParachainsTransactions to boost parachain transactions priority

* check parachain id in CheckAndBoostBridgeParachainsTransactions

* use submit_parachain_head_call_ex in tests

* removed commented code

* changed condition for consistency

* include overweight from runtime signed extensions into submit_parachain_heads call weight

* fixed comment

* removed obsolete code comment

* added important comment + test

* some fixes

* fix no-std compile

* again fix lost change

* use submit_parachain_heads_ex for Rococo<>Westend bridge

* fix for mandatory + interval check in ext

* deleted moved files (merge conflict)

* update polkadot-sdk refs + fix compilation

* removed another moved file

* bump chain versions

* bump relayer version

* lock up

Bumps [thiserror](https://github.com/dtolnay/thiserror) from 1.0.58 to 1.0.59.
- [Release notes](https://github.com/dtolnay/thiserror/releases)
- [Commits](https://github.com/dtolnay/thiserror/compare/1.0.58...1.0.59)

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

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

Bumps [rustls](https://github.com/rustls/rustls) from 0.21.8 to 0.21.11.
- [Release notes](https://github.com/rustls/rustls/releases)
- [Changelog](https://github.com/rustls/rustls/blob/main/CHANGELOG.md)
- [Commits](https://github.com/rustls/rustls/compare/v/0.21.8...v/0.21.11)

---
updated-dependencies:
- dependency-name: rustls
  dependency-type: indirect
...

Signed-off-by: dependabot[bot] <[email protected]>
Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>

* updated RELEASE.md

* bump relay version

* bump BHK version to 1_002_000

Bumps [subxt](https://github.com/paritytech/subxt) from 0.35.2 to 0.35.3.
- [Release notes](https://github.com/paritytech/subxt/releases)
- [Changelog](https://github.com/paritytech/subxt/blob/v0.35.3/CHANGELOG.md)
- [Commits](https://github.com/paritytech/subxt/compare/v0.35.2...v0.35.3)

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

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

Bumps [async-trait](https://github.com/dtolnay/async-trait) from 0.1.79 to 0.1.80.
- [Release notes](https://github.com/dtolnay/async-trait/releases)
- [Commits](https://github.com/dtolnay/async-trait/compare/0.1.79...0.1.80)

---
updated-dependencies:
- dependency-name: async-trait
  dependency-type: direct:production
  update-type: version-update:semver-patch
...

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

* Update CI image

* cargo update -p [email protected]

Bumps [subxt](https://github.com/paritytech/subxt) from 0.32.1 to 0.35.2.
- [Release notes](https://github.com/paritytech/subxt/releases)
- [Changelog](https://github.com/paritytech/subxt/blob/master/CHANGELOG.md)
- [Commits](https://github.com/paritytech/subxt/compare/v0.32.1...v0.35.2)

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

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

Bumps [anyhow](https://github.com/dtolnay/anyhow) from 1.0.81 to 1.0.82.
- [Release notes](https://github.com/dtolnay/anyhow/releases)
- [Commits](https://github.com/dtolnay/anyhow/compare/1.0.81...1.0.82)

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

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

* [dependabot] ignore migrated crates

* ignore more migrated crates

Bumps [quote](https://github.com/dtolnay/quote) from 1.0.35 to 1.0.36.
- [Release notes](https://github.com/dtolnay/quote/releases)
- [Commits](https://github.com/dtolnay/quote/compare/1.0.35...1.0.36)

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

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

The testing folder has also been moved to polkadot-sdk

* Remove migrated crates

* Reference polkadot-sdk for the migrated crates

* Leftovers

* Fixes

* Migrate fee payment from `Currency` to `fungible` (#2292)

Part of https://github.com/paritytech/polkadot-sdk/issues/226
Related https://github.com/paritytech/polkadot-sdk/issues/1833

- Deprecate `CurrencyAdapter` and introduce `FungibleAdapter`
- Deprecate `ToStakingPot` and replace usage with `ResolveTo`
- Required creating a new `StakingPotAccountId` struct that implements
`TypedGet` for the staking pot account ID
- Update parachain common utils `DealWithFees`, `ToAuthor` and
`AssetsToBlockAuthor` implementations to use `fungible`
- Update runtime XCM Weight Traders to use `ResolveTo` instead of
`ToStakingPot`
- Update runtime Transaction Payment pallets to use `FungibleAdapter`
instead of `CurrencyAdapter`
- [x] Blocked by https://github.com/paritytech/polkadot-sdk/pull/1296,
needs the `Unbalanced::decrease_balance` fix

(cherry picked from commit bda4e75ac49786a7246531cf729b25c208cd38e6)

* Upgrade `trie-db` from `0.28.0` to `0.29.0` (#3982)

- What does this PR do?
1. Upgrades `trie-db`'s version to the latest release. This release
includes, among others, an implementation of `DoubleEndedIterator` for
the `TrieDB` struct, allowing to iterate both backwards and forwards
within the leaves of a trie.
2. Upgrades `trie-bench` to `0.39.0` for compatibility.
3. Upgrades `criterion` to `0.5.1` for compatibility.
- Why are these changes needed?
Besides keeping up with the upgrade of `trie-db`, this specifically adds
the functionality of iterating back on the leafs of a trie, with
`sp-trie`. In a project we're currently working on, this comes very
handy to verify a Merkle proof that is the response to a challenge. The
challenge is a random hash that (most likely) will not be an existing
leaf in the trie. So the challenged user, has to provide a Merkle proof
of the previous and next existing leafs in the trie, that surround the
random challenged hash.

Without having DoubleEnded iterators, we're forced to iterate until we
find the first existing leaf, like so:
```rust
        // ************* VERIFIER (RUNTIME) *************
        // Verify proof. This generates a partial trie based on the proof and
        // checks that the root hash matches the `expected_root`.
        let (memdb, root) = proof.to_memory_db(Some(&root)).unwrap();
        let trie = TrieDBBuilder::<LayoutV1<RefHasher>>::new(&memdb, &root).build();

        // Print all leaf node keys and values.
        println!("\nPrinting leaf nodes of partial tree...");
        for key in trie.key_iter().unwrap() {
            if key.is_ok() {
                println!("Leaf node key: {:?}", key.clone().unwrap());

                let val = trie.get(&key.unwrap());

                if val.is_ok() {
                    println!("Leaf node value: {:?}", val.unwrap());
                } else {
                    println!("Leaf node value: None");
                }
            }
        }

        println!("RECONSTRUCTED TRIE {:#?}", trie);

        // Create an iterator over the leaf nodes.
        let mut iter = trie.iter().unwrap();

        // First element with a value should be the previous existing leaf to the challenged hash.
        let mut prev_key = None;
        for element in &mut iter {
            if element.is_ok() {
                let (key, _) = element.unwrap();
                prev_key = Some(key);
                break;
            }
        }
        assert!(prev_key.is_some());

        // Since hashes are `Vec<u8>` ordered in big-endian, we can compare them directly.
        assert!(prev_key.unwrap() <= challenge_hash.to_vec());

        // The next element should exist (meaning there is no other existing leaf between the
        // previous and next leaf) and it should be greater than the challenged hash.
        let next_key = iter.next().unwrap().unwrap().0;
        assert!(next_key >= challenge_hash.to_vec());
```

With DoubleEnded iterators, we can avoid that, like this:
```rust
        // ************* VERIFIER (RUNTIME) *************
        // Verify proof. This generates a partial trie based on the proof and
        // checks that the root hash matches the `expected_root`.
        let (memdb, root) = proof.to_memory_db(Some(&root)).unwrap();
        let trie = TrieDBBuilder::<LayoutV1<RefHasher>>::new(&memdb, &root).build();

        // Print all leaf node keys and values.
        println!("\nPrinting leaf nodes of partial tree...");
        for key in trie.key_iter().unwrap() {
            if key.is_ok() {
                println!("Leaf node key: {:?}", key.clone().unwrap());

                let val = trie.get(&key.unwrap());

                if val.is_ok() {
                    println!("Leaf node value: {:?}", val.unwrap());
                } else {
                    println!("Leaf node value: None");
                }
            }
        }

        // println!("RECONSTRUCTED TRIE {:#?}", trie);
        println!("\nChallenged key: {:?}", challenge_hash);

        // Create an iterator over the leaf nodes.
        let mut double_ended_iter = trie.into_double_ended_iter().unwrap();

        // First element with a value should be the previous existing leaf to the challenged hash.
        double_ended_iter.seek(&challenge_hash.to_vec()).unwrap();
        let next_key = double_ended_iter.next_back().unwrap().unwrap().0;
        let prev_key = double_ended_iter.next_back().unwrap().unwrap().0;

        // Since hashes are `Vec<u8>` ordered in big-endian, we can compare them directly.
        println!("Prev key: {:?}", prev_key);
        assert!(prev_key <= challenge_hash.to_vec());

        println!("Next key: {:?}", next_key);
        assert!(next_key >= challenge_hash.to_vec());
```
- How were these changes implemented and what do they affect?
All that is needed for this functionality to be exposed is changing the
version number of `trie-db` in all the `Cargo.toml`s applicable, and
re-exporting some additional structs from `trie-db` in `sp-trie`.

---------

Co-authored-by: Bastian Köcher <[email protected]>
(cherry picked from commit 4e73c0fcd37e4e8c14aeb83b5c9e680981e16079)

* Update polkadot-sdk refs

* Fix Cargo.lock

---------

Co-authored-by: Liam Aharon <[email protected]>
Co-authored-by: Facundo Farall <[email protected]>

* Use workspace.[authors|edition]

* Add repository.workspace = true

* Upgrade dependencies to the polkadot-sdk versions

* Upgrade async-std version

* Update jsonrpsee version

* cargo update

* use ci-unified image

* added CLI arguments: full WS URI + separate for WS path URI component + additional log

* URI -> URL?

* added TODO

* fmt

Bumps [tokio](https://github.com/tokio-rs/tokio) from 1.36.0 to 1.37.0.
- [Release notes](https://github.com/tokio-rs/tokio/releases)
- [Commits](https://github.com/tokio-rs/tokio/compare/tokio-1.36.0...tokio-1.37.0)

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

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