* replace HistoricalValidationCode usages with ValidationCodeByHash

* runtime-api: tabify tests file

* update implementers guide

* guide: reversion safety

* guide: manage reversion safety in subsystems

* add leaf status to ActivatedLeaf

* add an LRU-cache to overseer for staleness detection

* update ActivatedLeaf usages in tests to contain status field

* add variant where missed accidentally

* add some helpers to LeafStatus

* address grumbles

* validator_discovery: less flexible, but simpler design

* fix test

* remove unused struct

* smol optimization

* validator_discovery: basic retrying logic

* add a test

* add more tests

* update the guide

* more test logic

* Require at least 2/3 connectivity.

* Fix test.

* Update node/network/gossip-support/src/lib.rs

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

* Update node/network/gossip-support/src/lib.rs

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

Co-authored-by: Robert Klotzner <robert.klotzner@gmx.at>
Co-authored-by: Robert Klotzner <eskimor@users.noreply.github.com>
Co-authored-by: André Silva <123550+andresilva@users.noreply.github.com>

* Remove signature verification in backing.

`SignedFullStatement` now signals that the signature has already been
checked.

* Remove unused check_payload function.

* Introduced unchecked signed variants.

* Fix inclusion to use unchecked variant.

* More unchecked variants.

* Use unchecked variants in protocols.

* Start fixing statement-distribution.

* Fixup statement distribution.

* Fix inclusion.

* Fix warning.

* Fix backing properly.

* Fix bitfield distribution.

* Make crypto store optional for `RuntimeInfo`.

* Factor out utility functions.

* get_group_rotation_info

* WIP: Collator cleanup + check signatures.

* Convenience signature checking functions.

* Check signature on collator-side.

* Fix warnings.

* Fix collator side tests.

* Get rid of warnings.

* Better Signed/UncheckedSigned implementation.

Also get rid of Encode/Decode for Signed! *party*

* Get rid of dead code.

* Move Signed in its own module.

* into_checked -> try_into_checked

* Fix merge.

* Update branch

* Make it compile

* Compile

* gate approval-checking logic (#2470)

* Fix build

* Updates

* Fix merge

* Adds missing crate

* Companion for Substrate#8386

https://github.com/paritytech/substrate/pull/8386



* Fix fix fix

* Fix

* Fix compilation

* Rewrite to `ParachainsInherentDataProvider`

* Make it compile

* Renamings

* Revert stuff

* Remove stale file

* Guide updates

* Update node/core/parachains-inherent/src/lib.rs

Co-authored-by: Andronik Ordian <write@reusable.software>

* Update node/core/parachains-inherent/src/lib.rs

Co-authored-by: Andronik Ordian <write@reusable.software>

* Apply suggestions from code review

* Reset accidental changes

* More

* Remove stale file

* update Substrate

Co-authored-by: Robert Habermeier <rphmeier@gmail.com>
Co-authored-by: Andronik Ordian <write@reusable.software>
Co-authored-by: parity-processbot <>

* guide: don't request availability data from ourselves

* add QueryAllChunks message

* implement QueryAllChunks

* remove unused relay_parent from StoreChunk

* test QueryAllChunks

* fast paths make short roads

* test early exit behavior

* dispute subsystem files

* rename

* fix linkcheck

* flesh out section README

* coordinator schema

* DisputeCoordinatorMessage

* stub & coordinator protocol

* dispute coordinator

* add some more message fields

* move links to bottom

* dispute participation

* Cleen It Up !

* runtime: store candidate receipts in dispute state

yeah, this is a little heavier. why are you reading this?

* Revert "runtime: store candidate receipts in dispute state"

This reverts commit 51c10bfd.

* add dispute availability statement type and prepare for availability

* add 'spam slots' to disputes runtmie

* return Spam Slots info from runtime

* rework `ImportStatement` to `ImportStatements`

* some more methods for dispute coordinator

* candidates-included runtime API

* algo for providing disputes to runtime.

* handle signing with coordinator

* dispute coordinator chain ops

* remove dead file

* remove keystore from dispute participation

* adjust ApprovedAncestor to return the necssary data

* discuss how approved ancestor and determine undisputed chain are used together

* add TODO

* initiate disputes from approval voting

* route statements from candidate backing and approval voting

* fix guide build

* Indentation fix.

* Prepare request-response for PoV fetching.

* Drop old PoV distribution.

* WIP: Fetch PoV directly from backing.

* Backing compiles.

* Runtime access and connection management for PoV distribution.

* Get rid of seemingly dead code.

* Implement PoV fetching.

Backing does not yet use it.

* Don't send `ConnectToValidators` for empty list.

* Even better - no need to check over and over again.

* PoV fetching implemented.

+ Typechecks
+ Should work

Missing:

- Guide
- Tests
- Do fallback fetching in case fetching from seconding validator fails.

* Check PoV hash upon reception.

* Implement retry of PoV fetching in backing.

* Avoid pointless validation spawning.

* Add jaeger span to pov requesting.

* Add back tracing.

* Review remarks.

* Whitespace.

* Whitespace again.

* Cleanup + fix tests.

* Log to log target in overseer.

* Fix more tests.

* Don't fail if group cannot be found.

* Simple test for PoV fetcher.

* Handle missing group membership better.

* Add test for retry functionality.

* Fix flaky test.

* Spaces again.

* Guide updates.

* Spaces.

* add number to `ActivatedLeavesUpdate`

* update subsystem util and overseer

* use new ActivatedLeaf everywhere

* sort view

* sorted and limited view in network bridge

* use live block hash only if it's newer

* grumples

* malicious reputation cost is fatal

* make ReportBad a malicious cost

* futures control-flow for cleaning up inactive collator peers

* guide: network bridge updates

* add `PeerDisconnected` message

* guide: update

* reverse order

* remember to match

* implement disconnect peer in network bridge

* implement disconnect_inactive_peers

* test

* remove println

* don't hardcore policy

* add fuse outside of loop

* use default eviction policy

* guide changes for a fast-path requesting from backing validators

* add backing group to availability recovery message

* add new phase to interaction

* typos

* add full data messages

* handle new network messages

* dispatch full data requests

* cleanup

* check chunk index

* test for invalid recovery

* tests

* Typos.

* fix some grumbles

* be more explicit about error handling and control flow

* fast-path param

* use with_chunks_only in Service

Co-authored-by: Robert Klotzner <robert.klotzner@gmx.at>

* REVERT: comment out graphviz

* rewrite most of protocol-disputes

* write about conclusion and  chain selection

* tie back in overview

* basic disputes module

* guide: InclusionInherent -> ParaInherent

* language

* add ParaInherentData type

* plug parainherentdata into provisioner

* provide_multi_dispute

* tweak

* inclusion pipeline logic for disputes

* be clearer about signature checking

* reject backing of disputed blocks

* some type rejigging

* known-disputes runtime API

* wire up inclusion

* Revert "REVERT: comment out graphviz"

This reverts commit 66203e36.

* timeouts

* include in initialization order

* address grumbles

* integrate approval voting into overseer

* expose public API and make keystore arc

* integrate overseer in service

* guide: `ApprovedAncestor` returns block number

* return block number along with hash from ApprovedAncestor

* introduce a voting rule for reporting on approval checking

* integrate the delay voting rule

* Rococo configuration

* fix compilation and add slack

* fix web-wasm build

* tweak parameterization

* migrate voting rules to asycn

* remove hack comment

* Notify collators about seconded collation

This pr adds functionality to inform a collator that its collation was
seconded by a parachain validator. Before this signed statement was only
gossiped over the validation substream. Now, we explicitly send the
seconded statement to the collator after it was validated successfully.

Besides that it changes the `CollatorFn` to return an optional result
sender that is informed when the build collation was seconded by a
parachain validator.

* Add test

* Make sure we only send `Seconded` statements

* Make sure we only receive valid statements

* Review feedback

* validator_discovery: pass PeerSet to the request

* validator_discovery: track PeerSet of connected peers

* validator_discovery: fix tests

* validator_discovery: fix long line

* some fixes

* some validator_discovery logs

* log validator discovery request

* Also connect to validators on `DistributePoV`.

* validator_discovery: store the whole state per peer_set

* bump spec versions in kusama, polkadot and westend

* Correcting doc.

* validator_discovery: bump channel capacity

* pov-distribution: some cleanup

* this should fix the test, but it does not

* I just got some brain damage while fixing this

Why are you even reading this???

* wrap long line

* address some review nits

Co-authored-by: Robert Klotzner <robert.klotzner@gmx.at>

* grab guide updates from approval-voting branch

* focus on control flow and behavior, not functions

* add approval voting preamble info

* tabs -> spaces

* Companion for #7997

https://github.com/paritytech/substrate/pull/7997



* rename slot_number to slot

* rename SlotNumber type in overseer docs

* "Update Substrate"

Co-authored-by: André Silva <andrerfosilva@gmail.com>
Co-authored-by: parity-processbot <>

* use proper descriptive generic type names

* cleanup

* Table stores a list of detected misbehavior per authority

* add Table::drain_misbehaviors_for

* WIP: unify misbehavior types; report multiple misbehaviors per validator

Code checks, but tests don't yet pass.

* update drain_misbehaviors: return authority id as well as specific misbehavior

* enable unchecked construction of Signed structs in tests

* remove test-features feature & unnecessary generic

* fix backing tests

This took a while to figure out, because where we'd previously been
passing around `SignedFullStatement`s, we now needed to construct
those on the fly within the test, to take advantage of the signature-
checking in the constructor. That, in turn, necessitated changing the
iterable type of `drain_misbehaviors` to return the validator index,
and passing that validator index along within the misbehavior report.

Once that was sorted, however, it became relatively straightforward:
just needed to add appropriate methods to deconstruct the misbehavior
reports, and then we could construct the signed statements directly.

* fix bad merge

* initial impl approval distribution

* initial tests and fixes

* batching seems difficult: different peers have different needs

* bridge: fix test after merge

* some guide updates

* only send assignments to peers who know about the block

* fix a test, add approvals test

* simplify

* do not send assignment to peers for finalized blocks

* guide: protocol input and output

* one more test

* more comments, logs, initial metrics

* fix a typo

* one more thing: early return when reimporting a thing locally

* collation-generation: use persisted validation data

* node: remote FullValidationData API

* runtime: remove FullValidationData API

* backing tests: use persisted validation data

* FullCandidateReceipt: use persisted validation data

This is not a big change since this type is not used anywhere

* Remove ValidationData and TransientValidationData

Also update the guide

* alternate availability store schema

* improvements

* tweaks

* new DB schema and skeleton

* expand skeleton and tweaks

* handle backing and inclusion

* let finality be handled later

* handle finalized blocks

* implement query methods

* implement chunk storing

* StoreAvailableData

* fix an off-by-one

* implement pruning

* reinstate subsystem trait impl

* reinstate metrics

* fix warnings

* remove chunks_cache

* oops

* actually store the available data

* mockable pruning interval

* fix tests

* spacing

* fix code grumbles

* guide improvements

* make time mockable

* implement a mocked clock for testing

* return DB errors

* Update node/core/av-store/Cargo.toml

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

* Update roadmap/implementers-guide/src/node/utility/availability-store.md

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

* Update roadmap/implementers-guide/src/node/utility/availability-store.md

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

* review grumbles & clarity

* fix review grumbles

* Add docs

Co-authored-by: Andronik Ordian <write@reusable.software>

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>
Co-authored-by: Andronik Ordian <write@reusable.software>

Batch messages to network bridge and introduce a timeout to `SubsystemContext::send_message` (#2197)

* guide: batch network messages

* bridge: batch

* av-dist: batch outgoing messages

* time-out message sends in subsystem context

* Update node/subsystem/src/messages.rs

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

* Revert "time-out message sends in subsystem context"

This reverts commit d49be625

.

* Update node/network/availability-distribution/src/lib.rs

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

* Store all chunks and in a single transaction

* Adds chunks LRU to store

* Add pruning records metrics

* Use honest cache instead of LRU

* Remove unnecessary optional cache

* Fix review nits that are fixable

* guide: add missing ApprovalDistributionMessage variant

* guide: deduplicate sensence

* guide: non-semantic changes

* guide: update per the issue description

* GetBackedCandidates operates on multiple hashes now

* GetBackedCandidates still needs a relay parent

* implement changes specified in guide

* distinguish between various occasions for canceled oneshots

* add tracing info to getbackedcandidates

* REVERT ME: add tracing messages for GetBackedCandidates

Note that these messages are only sometimes actually passed on to the
candidate backing subsystem, with the consequence that it is
unexpectedly frequent that the provisioner fails to create its
provisionable data.

* REVERT ME: more tracing logging

* REVERT ME: log when CandidateBackingJob receives any message at all

* REVERT ME: log when send_msg sends a message to a job

* fix candidate-backing tests

* streamline GetBackedCandidates

This uses table.attested_candidate instead of table.get_candidate, because
it's not obvious how to get a BackedCandidate from just a
CommittedCandidateReceipt.

* REVERT ME: more logging tracing job lifespans

* promote warning about job premature demise

* don't terminate CandiateBackingJob::run_loop in event of failure to process message

* Revert "REVERT ME: more logging tracing job lifespans"

This reverts commit 7365f2fb.

* Revert "REVERT ME: log when send_msg sends a message to a job"

This reverts commit 58e46aad.

* Revert "REVERT ME: log when CandidateBackingJob receives any message at all"

This reverts commit 0d6f3841.

* Revert "REVERT ME: more tracing logging"

This reverts commit 675fd262.

* Revert "REVERT ME: add tracing messages for GetBackedCandidates"

This reverts commit e09e1564.

* formatting

* add logging message to CandidateBackingJob::run_loop start

* REVERT ME: add tracing to candidate-backing job creation

* run candidatebacking loop even if no assignment

* use unique error variants for each canceled oneshot

* Revert "REVERT ME: add tracing to candidate-backing job creation"

This reverts commit 8ce5f4f0.

* try_runtime_api more to reduce silent exits

* add sanity check that returned backed candidates preserve ordering

* remove redundant err attribute

* expand description

* basics of availability recovery

* finish availability recovery

* fill out missing text

* Update roadmap/implementers-guide/src/node/availability/availability-recovery.md

Co-authored-by: Fedor Sakharov <fedor.sakharov@gmail.com>

* fix signal handling

Co-authored-by: Fedor Sakharov <fedor.sakharov@gmail.com>

* guide: move erasure-root to candidate descriptor

* primitives: move erasure root to descriptor

* guide: unify candidate commitments and validation outputs

* primitives: unify validation outputs and candidate commitments

* parachains-runtime: fix fallout

* runtimes: fix fallout

* collation generation: fix fallout

* fix stray reference in primitives

* fix fallout in node-primitives

* fix remaining fallout in collation generation

* fix fallout in candidate validation

* fix fallout in runtime API subsystem

* fix fallout in subsystem messages

* fix fallout in candidate backing

* fix fallout in availability distribution

* don't clone

* clone

Co-authored-by: Sergei Shulepov <sergei@parity.io>

* guide: fix formatting for SessionInfo module

* primitives: SessionInfo type

* punt on approval keys

* ah, revert the type alias

* session info runtime module skeleton

* update the guide

* runtime/configuration: sync with the guide

* runtime/configuration: setters for newly added fields

* runtime/configuration: set codec indexes

* runtime/configuration: update test

* primitives: fix SessionInfo definition

* runtime/session_info: initial impl

* runtime/session_info: use initializer for session handling (wip)

* runtime/session_info: mock authority discovery trait

* guide: update the initializer's order

* runtime/session_info: tests skeleton

* runtime/session_info: store n_delay_tranches in Configuration

* runtime/session_info: punt on approval keys

* runtime/session_info: add some basic tests

* Update primitives/src/v1.rs

* small fixes

* remove codec index annotation on structs

* fix off-by-one error

* validator_discovery: accept a session index

* runtime: replace validator_discovery api with session_info

* Update runtime/parachains/src/session_info.rs

Co-authored-by: Sergei Shulepov <sergei@parity.io>

* runtime/session_info: add a comment about missing entries

* runtime/session_info: define the keys

* util: expose connect_to_past_session_validators

* util: allow session_info requests for jobs

* runtime-api: add mock test for session_info

* collator-protocol: add session_index to test state

* util: fix error message for runtime error

* fix compilation

* fix tests after merge with master

Co-authored-by: Sergei Shulepov <sergei@parity.io>

* skeleton flow control

* tweaks & rename to approvals distribution

* Update roadmap/implementers-guide/src/node/approval/approval-distribution.md

Co-authored-by: Peter Goodspeed-Niklaus <coriolinus@users.noreply.github.com>

* Update roadmap/implementers-guide/src/node/approval/approval-distribution.md

Co-authored-by: Peter Goodspeed-Niklaus <coriolinus@users.noreply.github.com>

* add a `NewBlocks` message and dispatch

* new data format for approval distribution

* guide: update view to include finalized block number

* approvals: document view updating

* pruning when peers disconnect

* add remaining message types

* fix link

* network message type

* handle incoming assignments

* import_and_circulate_approval

* handle new blocks

* address review comments

* address review comments and use nifty VRFProof

Co-authored-by: Peter Goodspeed-Niklaus <coriolinus@users.noreply.github.com>

* use snake_case for log targets

* remove unused continue

* validator_discovery: when disconnecting, use all addresses

* validator_discovery: simplify request revokation

* fix a typo

* Make `CandidateHash` a real type

This pr adds a new type `CandidateHash` that is used instead of the
opaque `Hash` type. This helps to ensure on the type system level that
we are passing the correct types.

This pr also fixes wrong usage of `relay_parent` as `candidate_hash`
when communicating with the av storage.

* Update core-primitives/src/lib.rs

Co-authored-by: Peter Goodspeed-Niklaus <coriolinus@users.noreply.github.com>

* Wrap the lines

Co-authored-by: Peter Goodspeed-Niklaus <coriolinus@users.noreply.github.com>

* fix: ensure candidate validation gets code based on occupied core assumption

* guide: runtime API for historical validation code

* add historical runtime API

* integrate into runtime API subsystem

* remove blocked TODO

* fix service build: enable notifications protocol only under real overseer

* Update node/subsystem/src/messages.rs

Co-authored-by: Sergei Shulepov <sergei@parity.io>

* fix compilation

Co-authored-by: Robert Habermeier <robert@Roberts-MacBook-Pro.local>
Co-authored-by: Sergei Shulepov <sergei@parity.io>

* add storage for approvals module

* basics of approval logic

* fix links

* Session info module

* create an approvals_inherent module

* integrate approvals module with inclusion

* Remove approvals runtime

* tweak mentions of on-chain logic

* add note on finality-grandpa voting rule

* elaborate on node-side components

* stub for availability recovery

* add another note on voting rule

* Beginnings of approval subsystems

* flesh out approval voting now

* logic for checking assignment certs

* initial scheduler logic

* scheduler logic

* adjst tranche taking logic

* approval voting import

* approval work (voting side)

* amend some TODOs

* mark some TODOs

* describe `ApprovedAncestor`

* reference protocol-approval.md

* clarity on bitfield

* remove approvals_inherent

* tweak session_info module according to review

* formatting & nits

Co-authored-by: Robert Habermeier <robert@Roberts-MacBook-Pro.local>

* annoying whitespaces

* update guide

Add `CheckValidationOutputs` runtime api and also change the
candidate-validation stuff

* promote ValidationOutputs to global primitives

i.e. move it from node specific primitives to global v1 primitives. This
will be needed when we share it later in the runtime inclusion module

* refactor acceptance checks in the inclusion module

factor out the common code to share it during the block inclusion and
for the forthcoming CheckValidationOutputs runtime api.

Also note that the acceptance criteria was updated to incorporate checks
that exist now in candidate-validation

* plumb the runtime api outside

* extract validation_data from ValidationOutputs

* use runtime-api to check validation outputs

apart from that refactor, update docs and tidy a bit

* Update the maxium code size

This is to fix a test that performs an upgrade.

* chain-api subsystem: implement BlockHeader messsage

* update the guide

* stupid, but it compiles

* redo

* cleanup

* add ValidatorDiscovery to msgs

* sketch network bridge code

* ConnectToAuthorities instead of validators

* more stuff

* cleanup

* more stuff

* complete ConnectToAuthoritiesState

* Update node/network/bridge/src/lib.rs

Co-authored-by: Peter Goodspeed-Niklaus <coriolinus@users.noreply.github.com>

* Collator protocol subsystem (#1659)

* WIP

* The initial implementation of the collator side.

* Improve comments

* Multiple collation requests

* Add more tests and comments to validator side

* Add comments, remove dead code

* Apply suggestions from code review

Co-authored-by: Peter Goodspeed-Niklaus <coriolinus@users.noreply.github.com>

* Fix build after suggested changes

* Also connect to the next validator group

* Remove a Future impl and move TimeoutExt to util

* Minor nits

* Fix build

* Change FetchCollations back to FetchCollation

* Try this

* Final fixes

* Fix build

Co-authored-by: Peter Goodspeed-Niklaus <coriolinus@users.noreply.github.com>

* handle multiple in-flight connection requests

* handle cancelled requests

* Update node/core/runtime-api/src/lib.rs

Co-authored-by: Bernhard Schuster <bernhard@ahoi.io>

* redo it again

* more stuff

* redo it again

* update comments

* workaround Future is not Send

* fix trailing spaces

* clarify comments

* bridge: fix compilation in tests

* update more comments

* small fixes

* port collator protocol to new validator discovery api

* collator tests compile

* collator tests pass

* do not revoke a request when the stream receiver is closed

* make revoking opt-in

* fix is_fulfilled

* handle request revokation in collator

* tests

* wait for validator connections asyncronously

* fix compilation

* relabel my todos

* apply Fedor's patch

* resolve reconnection TODO

* resolve revoking TODO

* resolve channel capacity TODO

* resolve peer cloning TODO

* resolve peer disconnected TODO

* resolve PeerSet TODO

* wip tests

* more tests

* resolve Arc TODO

* rename pending to non_revoked

* one more test

* extract utility function into util crate

* fix compilation in tests

* Apply suggestions from code review

Co-authored-by: Fedor Sakharov <fedor.sakharov@gmail.com>

* revert pin_project removal

* fix while let loop

* Revert "revert pin_project removal"

This reverts commit ae7f529d

.

* fix compilation

* Update node/subsystem/src/messages.rs

* docs on pub items

* guide updates

* remove a TODO

* small guide update

* fix a typo

* link to the issue

* validator discovery: on_request docs

Co-authored-by: Peter Goodspeed-Niklaus <coriolinus@users.noreply.github.com>
Co-authored-by: Fedor Sakharov <fedor.sakharov@gmail.com>
Co-authored-by: Bernhard Schuster <bernhard@ahoi.io>

* Register listeners in statement distribution

* Review fixes

* choose the straightforward candidate selection algorithm for now

* add draft implementation of candidate selection

* fix typo in summary

* more properly report misbehaving collators

* describe how CandidateSelection subsystem becomes aware of candidates

* revise candidate selection / collator protocol interaction pattern

* implement rest of candidate selection per the guide

* review: resolve nits

* start writing test suite, harness

* implement first test

* add second test

* implement third test

Co-authored-by: Bernhard Schuster <bernhard@ahoi.io>

* update primitives

* correct parent_head field

* make hrmp field pub

* refactor validation data: runtime

* refactor validation data: messages

* add arguments to full_validation_data runtime API

* port runtime API

* mostly port over candidate validation

* remove some parameters from ValidationParams

* guide: update candidate validation

* update candidate outputs

* update ValidationOutputs in primitives

* port over candidate validation

* add a new test for no-transient behavior

* update util runtime API wrappers

* candidate backing

* fix missing imports

* change some fields of validation data around

* runtime API impl

* update candidate validation

* fix backing tests

* grumbles from review

* fix av-store tests

* fix some more crates

* fix provisioner tests

* fix availability distribution tests

* port collation-generation to new validation data

* fix overseer tests

* Update roadmap/implementers-guide/src/node/utility/candidate-validation.md

Co-authored-by: Peter Goodspeed-Niklaus <coriolinus@users.noreply.github.com>

Co-authored-by: Peter Goodspeed-Niklaus <coriolinus@users.noreply.github.com>