* Check every minute whether authority-discovery key has changed

* Fix test

* Fix comment

* Use HashSet for latest_published_keys

* More fixing

* God I'm tired, sorry

* Make keystore return `None` when a key doesn't exist

* Fixes

* More fixes

* Update comment

* Update primitives/keystore/src/lib.rs

Co-authored-by: André Silva <123550+andresilva@users.noreply.github.com>

* Update client/keystore/src/local.rs

Co-authored-by: André Silva <123550+andresilva@users.noreply.github.com>

* Address comments

* Update client/keystore/src/local.rs

Co-authored-by: André Silva <123550+andresilva@users.noreply.github.com>

Co-authored-by: André Silva <123550+andresilva@users.noreply.github.com>

* Ahh

* Work work work

* Fix all the compilation errors

* Fix test

* More fixes...

* Rework priority groups

* Broken tests fix

* Fix warning causing CI to fail

* [Hack] Try restore backwards-compatibility

* Fix peerset bug

* Doc fixes and clean up

* Error on state mismatch

* Try debug CI

* CI debugging

* [CI debug] Can I please see this line

* Revert "[CI debug] Can I please see this line"

This reverts commit 4b7cf7c1511f579cd818b21d46bd11642dfac5cb.

* Revert "CI debugging"

This reverts commit 9011f1f564b860386dc7dd6ffa9fc34ea7107623.

* Fix error! which isn't actually an error

* Fix Ok() returned when actually Err()

* Tweaks and fixes

* Fix build

* Peerset bugfix

* [Debug] Try outbound GrandPa slots

* Another bugfix

* Revert "[Debug] Try outbound GrandPa slots"

This reverts commit d175b9208c088faad77d9f0ce36ff6f48bd92dd3.

* [Debug] Try outbound GrandPa slots

* Apply suggestions from code review

Co-authored-by: Max Inden <mail@max-inden.de>

* Use consts for hardcoded peersets

* Revert "Try debug CI"

This reverts commit 62c4ad5e79c03d561c714a008022ecac463a597e.

* Renames

* Line widths

* Add doc

Co-authored-by: Max Inden <mail@max-inden.de>

* Happy new year

Updates the copyright years and fixes wrong license headers.

* Fix the template

* Split HEADER into HEADER-APACHE & HEADER-GPL

* fix docs

* Update frame/merkle-mountain-range/src/lib.rs

Co-authored-by: Alexander Theißen <alex.theissen@me.com>

Co-authored-by: Alexander Theißen <alex.theissen@me.com>

* Upgrade to libp2p-0.31.

* Address line width.

* Add generous incoming connection limit.

* Remove old noise configuration.

* client/authority-discovery: Publish and query on exponential interval

When a node starts up publishing and querying might fail due to various
reasons, for example due to being not yet fully bootstrapped on the DHT.
Thus one should retry rather sooner than later. On the other hand, a
long running node is likely well connected and thus timely retries are
not needed. For this reasoning use an exponentially increasing interval
for `publish_interval`, `query_interval` and
`priority_group_set_interval` instead of a constant interval.

* client/authority-discovery/src/interval.rs: Add license header

* .maintain/gitlab: Ensure adder collator tests are run on CI

* Make authority discovery configurable

This pr makes the authority discovery configurable. So, instead of
having default values for the query interval, publish interval etc this
pr adds a configuration to make these values changeable. This will be
useful for tests where authority discovery is required.

* Update client/authority-discovery/src/worker.rs

Co-authored-by: Max Inden <mail@max-inden.de>

* Update client/authority-discovery/src/lib.rs

Co-authored-by: Max Inden <mail@max-inden.de>

* Update client/authority-discovery/src/lib.rs

Co-authored-by: Max Inden <mail@max-inden.de>

* Update client/authority-discovery/src/lib.rs

Co-authored-by: Max Inden <mail@max-inden.de>

* Fix compilation

* line width

Co-authored-by: Max Inden <mail@max-inden.de>

* client/authority-discovery: Remove sentry node logic

The notion of sentry nodes has been deprecated (see [1] for details).
This commit removes support for sentry nodes in the
`client/authority-discovery` module.

While removing `Role::Sentry` this commit also introduces
`Role::Discover`, allowing a node to discover addresses of authorities
without publishing ones own addresses. This will be needed in Polkadot
for collator nodes.

[1] https://github.com/paritytech/substrate/issues/6845

* client/authority-discovery/service: Improve PeerId comment

As done with `NetworkService::{add_to,remove_from}_priority_group`, make
`NetworkService::set_priority_group` async as well. This future-proofs
the API should we ever decide to use a bounded channel between
`NetworkService` and `NetworkWorker`.

* Asyncify sign_with

* Asyncify generate/get keys

* Complete BareCryptoStore asyncification

* Cleanup

* Rebase

* Add Proxy

* Inject keystore proxy into extensions

* Implement some methods

* Await on send

* Cleanup

* Send result over the oneshot channel sender

* Process one future at a time

* Fix cargo stuff

* Asyncify sr25519_vrf_sign

* Cherry-pick and fix changes

* Introduce SyncCryptoStore

* SQUASH ME WITH THE first commit

* Implement into SyncCryptoStore

* Implement BareCryptoStore for KeystoreProxyAdapter

* authority-discovery

* AURA

* BABE

* finality-grandpa

* offchain-workers

* benchmarking-cli

* sp_io

* test-utils

* application-crypto

* Extensions and RPC

* Client Service

* bin

* Update cargo.lock

* Implement BareCryptoStore on proxy directly

* Simplify proxy setup

* Fix authority-discover

* Pass async keystore to authority-discovery

* Fix tests

* Use async keystore in authority-discovery

* Rename BareCryptoStore to CryptoStore

* WIP

* Remote mutable borrow in CryptoStore trait

* Implement Keystore with backends

* Remove Proxy implementation

* Fix service builder and keystore user-crates

* Fix tests

* Rework authority-discovery after refactoring

* futures::select!

* Fix multiple mut borrows in authority-discovery

* Merge fixes

* Require sync

* Restore Cargo.lock

* PR feedback - round 1

* Remove Keystore and use LocalKeystore directly

Also renamed KeystoreParams to KeystoreContainer

* Join

* Remove sync requirement

* Fix keystore tests

* Fix tests

* client/authority-discovery: Remove event stream dynamic dispatching

With authority-discovery moving from a poll based future to an `async`
future Rust has difficulties propagating the `Sync` trade through the
generated state machine.

Instead of using dynamic dispatching, use a trait parameter to specify
the DHT event stream.

* Make it compile

* Fix submit_transaction

* Fix block_on issue

* Use await in async context

* Fix manual seal keystore

* Fix authoring_blocks test

* fix aura authoring_blocks

* Try to fix tests for auth-discovery

* client/authority-discovery: Fix lookup_throttling test

* client/authority-discovery: Fix triggers_dht_get_query test

* Fix epoch_authorship_works

* client/authority-discovery: Remove timing assumption in unit test

* client/authority-discovery: Revert changes to termination test

* PR feedback

* Remove deadcode and mark test code

* Fix test_sync

* Use the correct keyring type

* Return when from_service stream is closed

* Convert SyncCryptoStore to a trait

* Fix line width

* Fix line width - take 2

* Remove unused import

* Fix keystore instantiation

* PR feedback

* Remove KeystoreContainer

* Revert "Remove KeystoreContainer"

This reverts commit ea4a37c7d74f9772b93d974e05e4498af6192730.

* Take a ref of keystore

* Move keystore to dev-dependencies

* Address some PR feedback

* Missed one

* Pass keystore reference - take 2

* client/finality-grandpa: Use `Arc<dyn CryptoStore>` instead of SyncXXX

Instead of using `SyncCryptoStorePtr` within `client/finality-grandpa`,
which is a type alias for `Arc<dyn SyncCryptoStore>`, use `Arc<dyn
CryptoStore>`. Benefits are:

1. No additional mental overhead of a `SyncCryptoStorePtr`.

2. Ability for new code to use the asynchronous methods of `CryptoStore`
instead of the synchronous `SyncCryptoStore` methods within
`client/finality-granpa` without the need for larger refactorings.

Note: This commit uses `Arc<dyn CryptoStore>` instead of
`CryptoStorePtr`, as I find the type signature more descriptive. This is
subjective and in no way required.

* Remove SyncCryptoStorePtr

* Remove KeystoreContainer & SyncCryptoStorePtr

* PR feedback

* *: Use CryptoStorePtr whereever possible

* *: Define SyncCryptoStore as a pure extension trait of CryptoStore

* Follow up to SyncCryptoStore extension trait

* Adjust docs for SyncCryptoStore as Ben suggested

* Cleanup unnecessary requirements

* sp-keystore

* Use async_std::task::block_on in keystore

* Fix block_on std requirement

* Update primitives/keystore/src/lib.rs

Co-authored-by: Max Inden <mail@max-inden.de>

* Fix wasm build

* Remove unused var

* Fix wasm compilation - take 2

* Revert async-std in keystore

* Fix indent

* Fix version and copyright

* Cleanup feature = "std"

* Auth Discovery: Ignore if from_service is cloed

* Max's suggestion

* Revert async-std usage for block_on

* Address PR feedback

* Fix example offchain worker build

* Address PR feedback

* Update Cargo.lock

* Move unused methods to test helper functions

* Restore accidentally deleted cargo.lock files

* Fix unused imports

Co-authored-by: Max Inden <mail@max-inden.de>
Co-authored-by: Shawn Tabrizi <shawntabrizi@gmail.com>

* client/authority-discovery: Throttle DHT requests

Instead of passing one DHT query for each authority down to the network
every query interval, only pass MAX_IN_FLIGHT_LOOKUPS at a given point
in time, triggering new ones when previous ones return.

* client/authority-discovery/worker/test: Fix wrong constant

* frame/authority-discovery: Have authorities() return both current and next

Authority address lookups on the DHT happen periodically (every 10
mintues) and are rather slow (~10 seconds).

In order to smooth the transition period between two sessions, have the
runtime module return both the current as well as the next authority
set. Thereby the client authority module will:

1. Publish its addresses one session in advance.

2. Prefetch the addresses of authorities of the next session in advance.

* frame/authority-discovery: Deduplicate authority ids

* frame/authority-discovery: Don't dedup on_genesis authorities

* frame/authority-discovery: Remove mut and sort on comparison in tests

* frame/authority-discovery: Use BTreeSet for deduplication

* client/authority-discovery: Test addresses per authority limit

* client/authority-discovery: Limit number of addresses per authority

* client/authority-discovery/worker: Extract address getter

* client/authority-discovery: Test for no duplicate p2p components

* client/authority-discovery: Append PeerId to Multiaddr at most once

When collecting the addresses to be published for the local node,
`addresses_to_publish` adds the local nodes `PeerId` to each
`Multiaddr`. Before doing so, ensure the `Multiaddr` does not already
contain one.

* client/authority-discovery: Remove explicit return

Revert the accidental query interval change from every one minute back
to every 10 minutes.

* client/authority-discovery: Rename AuthorityDiscovery to XXXWorker

* client/authority-discovery: Introduce AuthorityDiscoveryService

Add a basic `AuthorityDiscoveryService` implementation which enables
callers to get the addresses for a given `AuthorityId` from the local
cache.

* client/authority-discovery: Split into worker and service mod

Move `Service` and `Worker` to their own Rust modules resulting in the
following file structure.

├── build.rs
├── Cargo.toml
└── src
    ├── error.rs
    ├── lib.rs
    ├── service.rs
    ├── tests.rs
    ├── worker
    │   ├── addr_cache.rs
    │   ├── schema
    │   │   └── dht.proto
    │   └── tests.rs
    └── worker.rs

* client/authority-discovery: Cache PeerId -> AuthorityId mapping

* client/authority-discovery: Update priority group on interval

Instead of updating the authority discovery peerset priority group each
time a new DHT value is found, update it regularly on an interval.

This removes the need for deterministic random selection. Instead of
trying to return a random stable set of `Multiaddr`s, the `AddrCache`
now returns a random set on each call.

* client/authority-discovery: Implement Service::get_authority_id

* client/authority-discovery: Use HashMap instead of BTreeMap

* client/authority-discovery: Rework priority group interval

* client/authority-discovery: Fix comment

* bin/node/cli: Update authority discovery constructor

* client/authority-discovery: Fuse from_service receiver

* client/authority-discovery: Remove Rng import

* client/authority-discovery: Ignore Multiaddr without PeerId

* client/authority-discovery/service: Add note on returned None

* client/authority-discovery/addr_cache: Replace double clone with deref

In order to tell whether an address is the local nodes address the
authority discovery module previously compared the Multihash within the
`p2p` Multiaddr protocol.

rust-libp2p recently switched to a new PeerId representation (see [1]).
Multihashes of the same PeerId in the new and the old format don't
equal.

Instead of comparing the Multihashes, this patch ensures the module
compares the PeerIds

[1] https://github.com/libp2p/rust-libp2p/issues/555

* client/authority-discovery: Don't add own address to priority group

In the scenario of a validator publishing the address of its sentry node
to the DHT, said sentry node should not add its own Multiaddr to the
peerset "authority" priority group.

Related to 273f31b7.

* client/authority-discovery: Remove unused import PeerId

* client/authority-discovery/tests: Add tcp protocol to multiaddresses

* Ensure authority discovery avoids self-lookups.

Thereby additionally guard the `NetworkService` against
adding the local peer to the PSM or registering a
"known address" for the local peer.

* Clarify comments.

* See if returning errors is ok.

Previously, when publishing ones address onto the DHT, the signature
signing those addresses would be SCALE encoded twice.

This commit removes the second encoding and adjusts the tests
to catch future regressions.

Instead of logging value-found-event-handling failures or value-put
failures on error level, log them on debug level only additionally
recording them via Prometheus.

Motivation is that both events can happen in "normal" operations and
thus clutter the logs.

Expose the amount of addresses that are passed from the authority
discovery module down to the network peer set manager as a priority
group in order to connect to the corresponding nodes.

```
authority_discovery_priority_group_size 10
```

* client/authority-discovery: Allow to be run by sentry node

When run as a sentry node, the authority discovery module does not
publish any addresses to the dht, but still discovers validators and
sentry nodes of validators.

* client/authority-discovery/src/lib: Wrap lines at 100 characters

* client/authority-discovery: Remove TODO and unused import

* client/authority-discovery: Pass role to new unit tests

* client/authority-discovery: Apply suggestions

Co-Authored-By: André Silva <123550+andresilva@users.noreply.github.com>

* bin/node/cli/src/service: Use expressions instead of statements

Co-authored-by: André Silva <123550+andresilva@users.noreply.github.com>

* client/authority-discovery: Rework error handling

Instead of `handle_dht_events` returning a `Result<(), Error>`, return
a `Poll<Error>` where `Poll::Pending` signals that there are no more
events to handle and `Poll::Ready(Error)` signals that a fatal error
occured. Non fatal errors are handled within `handle_dht_events`
directly, thus looping in `poll` is not necessary anymore.

* client/authority-discovery: Return () instead of error on termiantion

* Update client/authority-discovery/src/lib.rs

Co-Authored-By: André Silva <123550+andresilva@users.noreply.github.com>

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>
Co-authored-by: André Silva <123550+andresilva@users.noreply.github.com>

* Make sure we poll authority event stream until all events are processed

* Add test

* client/authority-discovery: Add test ensure termination on network termi

* client/authority-discovery: Terminate when network does

When the dht event stream returns Poll::Ready(None) it is likely due to
the network terminating. When the network terminates due to the node
itself shutting down or due to a fatal error, there is no purpose in
continuing to run the authority discovery module.

* client/authority-discovery/src/lib: Apply suggestions

Co-Authored-By: André Silva <123550+andresilva@users.noreply.github.com>

Co-authored-by: André Silva <123550+andresilva@users.noreply.github.com>

* Adapt to rust-libp2p#1440.

* Further adapt to libp2p/master.

* Update to libp2p-0.17

* Finishing touches.

* Remove stray TODO.

* Incorporate review feedback.

* Remove unused import.

* Split the Roles bitfield in three

* Forgot to include some changes

* Fix cli test

* More test fixes

* Oh God, merging master broke other tests

* Didn't run the doctests

* Address review

* I'm trying to fix the build blindly because it's taking a good hour to compile on my machine

* Address some review

* Also update the peerset's API to make sense

* Fix peerset tests

* Fix browser node

* client: distinguish between local and network authority

Co-authored-by: André Silva <andre.beat@gmail.com>

* Add KEY_KIND_ID to the public trait

This change is being introduced for the purpose of identifying a public
key with it's identifier and algorithm "kind".

* Use `sign_with` as implemented in BareCryptoStore

* Implement `sign_with` in sc_keystore

* Fix inconsistencies, use *_KIND_ID in sp_core testing

* Rename KeyKindId to CryptoTypeId

* Remove pair-returning functions from BareCryptoStore trait

* Define CryptoTypeId in app-crypto macros

* Add functions to get keys supported by keystore

* Fix sign_with signature to include CryptoTypePublicPair

* Add `sign_with_any` and `sign_with_all`

* Use keystore.sign_with in auth_discovery

* Rename get_supported_keys -> supported_keys

* Added headers to function docstrings

* Use chain instead of extending a temp vector

* Fixed some code formatting

* Restrict size of CryptoTypeId

This is to be able to use Encode/Decode derives and the overcome having
the size being unknown at compile-time.

* Implement sign_with in the trait itself

* Remove whitespace

* Use key_type also as a CryptoTypeId in app_crypto macros

* Rename `get_keys` to `keys` in BareCryptoStore

* Remove usage of key_pair funcs in tests

* Adjust docstring for *_CYPTO_ID constants

* Fix failures

* Simplify mapping on keys

* Remove one let

* Fixed typo

* PR feedback

* remove whitespace

* Zip keys and signatures

* Use into_iter & remove cloned

* Pass index to MissingSignature

* Use typed errors instead of strings for BareCryptoStore

* Implement Debug for trait error

* Use hashsets for better performance for supported_keys

* Make sure keys are inserted into the keystore

* Make sign_with_all return type consistent with `sign_with`

* Rename Error to BareCryptoStoreError

* Rename CRYPT_TYPE_ID -> CRYPTO_ID

* Remove unnecessary CRYPTO_ID declaration in Public trait

* Convert pub key to CryptoTypePublicPair

* Fix use

* Fix code style

* Implement From on CryptoTypePublicPair in app_crypto macros

* Change CryptoTypePublicPair to a struct

* Implement Display on CryptoTypePublicPair

* Pass CryptoTypePublicPair to MissingSignature error

* Adjust docs according to function signature

* Unify keys implementation

* Fix RPC author tests

* Fix stackoverflow

* Tabify spaces

* Pass KeyTypeId to error for easier debugging

* Fix asserts

* Use ToHex to format public key

* Use constants from sp_core

* Rename testing KeyTypeId constants

* Please compiler

* Restore KeyTypeId names

apparently, they're not only used in tests

* Use BareCryptoStoreError instead of String

* Document return value

* Fix borrow check

* Convert to hashset internally

* WIP - iter_keys

* Return raw_public_keys

* Address PR feedback

* Address PR Feedback

* Fix hexdisplay import error

* Update primitives/core/src/traits.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* client/authority-discovery: Instrument code with Prometheus

Introduce Prometheus metrics into the authority discovery module
enabling one to observe:

- authority_discovery_times_published_total

- authority_discovery_amount_external_addresses_last_published

- authority_discovery_times_requested_total

- authority_discovery_dht_event_received

* client/authority-discovery/src/lib.rs: Reword metric help texts

Co-Authored-By: Ashley <ashley.ruglys@gmail.com>

* client/authority-discovery/src/lib.rs: Reword metric help text

Co-Authored-By: Ashley <ashley.ruglys@gmail.com>

* client/authority-discovery/tests: Fix struct instantiation + basic test

Co-authored-by: Ashley <ashley.ruglys@gmail.com>

* remove networkspecialization

* Fix most of the fallout

* get all tests compiling

Co-authored-by: Pierre Krieger <pierre.krieger1708@gmail.com>

* client/authority-discovery/Cargo.toml: Update dependency

* client/authority-discovery: Pass packet payload and addresses as slice

Starting with Bytes 0.5 `Vec<T>` does not implement `Buf`, but `&[T]`
does.

* Extend `Proposer` to optionally generate a proof of the proposal

* Something

* Refactor sr-api to not depend on client anymore

* Fix benches

* Apply suggestions from code review

Co-Authored-By: Tomasz Drwięga <tomusdrw@users.noreply.github.com>

* Apply suggestions from code review

* Introduce new `into_storage_changes` function

* Switch to runtime api for `execute_block` and don't require `H256`
anywhere in the code

* Put the `StorageChanges` into the `Proposal`

* Move the runtime api error to its own trait

* Adds `StorageTransactionCache` to the runtime api

This requires that we add `type NodeBlock = ` to the
`impl_runtime_apis!` macro to work around some bugs in rustc :(

* Remove `type NodeBlock` and switch to a "better" hack

* Start using the transaction cache from the runtime api

* Make it compile

* Move `InMemory` to its own file

* Make all tests work again

* Return block, storage_changes and proof from Blockbuilder::bake()

* Make sure that we use/set `storage_changes` when possible

* Add test

* Fix deadlock

* Remove accidentally added folders

* Introduce `RecordProof` as argument type to be more explicit

* Update client/src/client.rs

Co-Authored-By: Tomasz Drwięga <tomusdrw@users.noreply.github.com>

* Update primitives/state-machine/src/ext.rs

Co-Authored-By: Tomasz Drwięga <tomusdrw@users.noreply.github.com>

* Integrates review feedback

* Remove `unsafe` usage

* Update client/block-builder/src/lib.rs

Co-Authored-By: Benjamin Kampmann <ben@gnunicorn.org>

* Update client/src/call_executor.rs

* Bump versions

Co-authored-by: Tomasz Drwięga <tomusdrw@users.noreply.github.com>
Co-authored-by: Benjamin Kampmann <ben.kampmann@googlemail.com>

* client/authority-discovery: Limit number of connections to authorities

Instead of connecting to all sentry nodes of all authorities, with this
patch the authority discovery module does the following:

- Choose one sentry node per authority at random.

- Choose MAX_NUM_AUTHORITY_CONN out of the above at random.

The module uses randomness to prevent hot spots, e.g. all nodes trying
to connect to a single node. If the authority discovery module would
choose the nodes to connect to at random on each new address that it
learns of, the node would go through a lot of connection churn.  Instead
it creates a random seed at start up and uses this seed for its RNG on
each update cycle.

* client/authority-discovery: Extract address cache into own module

* client/authority-discovery/src/addr_cache: Add basic unit tests

* client/authority-discovery: Replace unwrap with expect on [u8] cmp

* .maintain/sentry-node/docker-compose.yml: Prefix endpoint flags

* client/authority-discovery/src/addr_cache: Use sort_unstable and cmp

* client/authority-discovery: Use BTreeMap in addr_cache for sorted iter

To reduce connection churn it is preferrable to have `get_subset` of the
`addr_cache` to return the same result on repeated calls. `get_subset`
iterates a map. To make the process of iteration deterministic, use a
`BTreeMap` instead of a `HashMap`.