* 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

* skeleton

* skeleton aux-schema module

* start approval types

* start aux schema with aux store

* doc

* finish basic types

* start approval types

* doc

* finish basic types

* write out schema types

* add debug and codec impls to approval types

* add debug and codec impls to approval types

also add some key computation

* add debug and codec impls to approval types

* getters for block and candidate entries

* grumbles

* remove unused AssignmentId

* load_decode utility

* implement DB clearing

* function for adding new block entry to aux store

* start `canonicalize` implementation

* more skeleton

* finish implementing canonicalize

* tag TODO

* implement a test AuxStore

* add allow(unused)

* basic loading and deleting test

* block_entry test function

* add a test for `add_block_entry`

* ensure range is exclusive at end

* test clear()

* test that add_block sets children

* add a test for canonicalize

* Update node/core/approval-voting/src/aux_schema/mod.rs

Co-authored-by: Peter Goodspeed-Niklaus <[email protected]>

* Update node/core/approval-voting/src/aux_schema/tests.rs

Co-authored-by: Peter Goodspeed-Niklaus <[email protected]>

* Update node/core/approval-voting/src/aux_schema/mod.rs

Co-authored-by: Peter Goodspeed-Niklaus <[email protected]>

Co-authored-by: Peter Goodspeed-Niklaus <[email protected]>

Bumps [futures](https://github.com/rust-lang/futures-rs) from 0.3.11 to 0.3.12.
- [Release notes](https://github.com/rust-lang/futures-rs/releases)
- [Changelog](https://github.com/rust-lang/futures-rs/blob/master/CHANGELOG.md)
- [Commits](https://github.com/rust-lang/futures-rs/compare/0.3.11...0.3.12)

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

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

Bumps [futures](https://github.com/rust-lang/futures-rs) from 0.3.10 to 0.3.11.
- [Release notes](https://github.com/rust-lang/futures-rs/releases)
- [Changelog](https://github.com/rust-lang/futures-rs/blob/master/CHANGELOG.md)
- [Commits](https://github.com/rust-lang/futures-rs/compare/0.3.10...0.3.11)

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

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

* Adds message types

* Add code skeleton

* Adds subsystem code.

* Adds a first test

* Adds interaction result to availability_lru

* Use LruCache instead of a HashMap

* Whitespaces to tabs

* Do not ignore errors

* Change error type

* Add a timeout to chunk requests

* Add custom errors and log them

* Adds replace_availability_recovery method

* recovery_threshold computed by erasure crate

* change core to std

* adds docs to error type

* Adds a test for invalid reconstruction

* refactors interaction run into multiple methods

* Cleanup AwaitedChunks

* Even more fixes

* Test that recovery with wrong root is an error

* Break to launch another requests

* Styling fixes

* Add SessionIndex to API

* Proper relay parents for MakeRequest

* Remove validator_discovery and use message

* Remove a stream on exhaustion

* On cleanup free the request streams

* Fix merge and refactor

Bumps [tempfile](https://github.com/Stebalien/tempfile) from 3.1.0 to 3.2.0.
- [Release notes](https://github.com/Stebalien/tempfile/releases)
- [Changelog](https://github.com/Stebalien/tempfile/blob/master/NEWS)
- [Commits](https://github.com/Stebalien/tempfile/commits)

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

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

* Add one Jaeger span per relay parent

This adds one Jaeger span per relay parent, instead of always creating
new spans per relay parent. This should improve the UI view, because
subsystems are now grouped below one common span.

* Fix doc tests

* Replace `PerLeaveSpan` to `PerLeafSpan`

* More renaming

* Moare

* Update node/subsystem/src/lib.rs

Co-authored-by: Andronik Ordian <[email protected]>

* Skip the spans

* Increase `spec_version`

Co-authored-by: Andronik Ordian <[email protected]>

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

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

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

* Bump version from v0.8.26 to v0.8.27

* bump substrate

Bumps [color-eyre](https://github.com/yaahc/color-eyre) from 0.5.8 to 0.5.10.
- [Release notes](https://github.com/yaahc/color-eyre/releases)
- [Changelog](https://github.com/yaahc/color-eyre/blob/v0.5.10/CHANGELOG.md)
- [Commits](https://github.com/yaahc/color-eyre/compare/v0.5.8...v0.5.10)

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

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

Bumps [nix](https://github.com/nix-rust/nix) from 0.19.0 to 0.19.1.
- [Release notes](https://github.com/nix-rust/nix/releases)
- [Changelog](https://github.com/nix-rust/nix/blob/master/CHANGELOG.md)
- [Commits](https://github.com/nix-rust/nix/compare/v0.19.0...v0.19.1)

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

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

Bumps [assert_cmd](https://github.com/assert-rs/assert_cmd) from 1.0.1 to 1.0.2.
- [Release notes](https://github.com/assert-rs/assert_cmd/releases)
- [Changelog](https://github.com/assert-rs/assert_cmd/blob/master/CHANGELOG.md)
- [Commits](https://github.com/assert-rs/assert_cmd/compare/v1.0.1...v1.0.2)

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

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

Bumps [color-eyre](https://github.com/yaahc/color-eyre) from 0.5.7 to 0.5.8.
- [Release notes](https://github.com/yaahc/color-eyre/releases)
- [Changelog](https://github.com/yaahc/color-eyre/blob/master/CHANGELOG.md)
- [Commits](https://github.com/yaahc/color-eyre/compare/v0.5.7...v0.5.8)

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

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

* update tiny-keccak to 0.2

* update deps except bitvec and shared_memory

* fix some warning after futures upgrade

* remove useless package rename caused by bug in cargo-upgrade

* revert parity-util-mem *

* remove unused import

* cargo update

* remove all renames on parity-scale-codec

* remove the leftovers

* remove unused dep

* start working on building the real overseer

Unfortunately, this fails to compile right now due to an upstream
failure to compile which is probably brought on by a recent upgrade
to rustc v1.47.

* fill in AllSubsystems internal constructors

* replace fn make_metrics with Metrics::attempt_to_register

* update to account for #1740

* remove Metrics::register, rename Metrics::attempt_to_register

* add 'static bounds to real_overseer type params

* pass authority_discovery and network_service to real_overseer

It's not straightforwardly obvious that this is the best way to handle
the case when there is no authority discovery service, but it seems
to be the best option available at the moment.

* select a proper database configuration for the availability store db

* use subdirectory for av-store database path

* apply Basti's patch which avoids needing to parameterize everything on Block

* simplify path extraction

* get all tests to compile

* Fix Prometheus double-registry error

for debugging purposes, added this to node/subsystem-util/src/lib.rs:472-476:

```rust
Some(registry) => Self::try_register(registry).map_err(|err| {
	eprintln!("PrometheusError calling {}::register: {:?}", std::any::type_name::<Self>(), err);
	err
}),
```

That pointed out where the registration was failing, which led to
this fix. The test still doesn't pass, but it now fails in a new
and different way!

* authorities must have authority discovery, but not necessarily overseer handlers

* fix broken SpawnedSubsystem impls

detailed logging determined that using the `Box::new` style of
future generation, the `self.run` method was never being called,
leading to dropped receivers / closed senders for those subsystems,
causing the overseer to shut down immediately.

This is not the final fix needed to get things working properly,
but it's a good start.

* use prometheus properly

Prometheus lets us register simple counters, which aren't very
interesting. It also allows us to register CounterVecs, which are.
With a CounterVec, you can provide a set of labels, which can
later be used to filter the counts.

We were using them wrong, though. This pattern was repeated in a
variety of places in the code:

```rust
// panics with an cardinality mismatch
let my_counter = register(CounterVec::new(opts, &["succeeded", "failed"])?, registry)?;
my_counter.with_label_values(&["succeeded"]).inc()
```

The problem is that the labels provided in the constructor are not
the set of legal values which can be annotated, but a set of individual
label names which can have individual, arbitrary values.

This commit fixes that.

* get av-store subsystem to actually run properly and not die on first signal

* typo fix: incomming -> incoming

* don't disable authority discovery in test nodes

* Fix rococo-v1 missing session keys

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

* try dummying out av-store on non-full-nodes

* overseer and subsystems are required only for full nodes

* Reduce the amount of warnings on browser target

* Fix two more warnings

* InclusionInherent should actually have an Inherent module on rococo

* Ancestry: don't return genesis' parent hash

* Update Cargo.lock

* fix broken test

* update test script: specify chainspec as script argument

* Apply suggestions from code review

Co-authored-by: Bastian Köcher <[email protected]>

* Update node/service/src/lib.rs

Co-authored-by: Bastian Köcher <[email protected]>

* node/service/src/lib: Return error via ? operator

* post-merge blues

* add is_collator flag

* prevent occasional av-store test panic

* simplify fix; expand application

* run authority_discovery in Role::Discover when collating

* distinguish between proposer closed channel errors

* add IsCollator enum, remove is_collator CLI flag

* improve formatting

* remove nop loop

* Fix some stuff

* Adds test parachain adder collator

* Add sudo to Rococo, change session length to 30 seconds and some renaming

* Update to the latest changes on master

* Some fixes

* Fix compilation

* Update parachain/test-parachains/adder/collator/src/lib.rs

Co-authored-by: Sergei Shulepov <[email protected]>

* Review comments

* Downgrade transaction version

* Fixes

* MOARE

* Register notification protocols

* utils: remove unused error

* av-store: more resilient to some errors

* address review nits

* address more review nits

Co-authored-by: Peter Goodspeed-Niklaus <[email protected]>
Co-authored-by: Andronik Ordian <[email protected]>
Co-authored-by: Fedor Sakharov <[email protected]>
Co-authored-by: Robert Habermeier <[email protected]>
Co-authored-by: Peter Goodspeed-Niklaus <[email protected]>
Co-authored-by: Max Inden <[email protected]>
Co-authored-by: Sergey Shulepov <[email protected]>
Co-authored-by: Sergei Shulepov <[email protected]>

* A real overseer feature

* Fix build without feature

* Update node/service/src/lib.rs

Co-authored-by: Bastian Köcher <[email protected]>

Co-authored-by: Robert Habermeier <[email protected]>
Co-authored-by: Bastian Köcher <[email protected]>

* get rid of glue wrapper error type

* cargo update -p sp-io

* cargo update -p sp-io

* "Update Substrate"

Co-authored-by: Andronik Ordian <[email protected]>
Co-authored-by: parity-processbot <>

* use color_eyre for its backtrace feature and error reporting

* lost Cargo.lock update

* wrapper

* add error glue to be able to utilize eyre

* Update src/main.rs

Co-authored-by: Bastian Köcher <[email protected]>

* Update src/main.rs

Co-authored-by: Bastian Köcher <[email protected]>

* avoid duplicate error print

* Update src/main.rs

Co-authored-by: Andronik Ordian <[email protected]>

Co-authored-by: Bastian Köcher <[email protected]>
Co-authored-by: Andronik Ordian <[email protected]>

* bump version & substrate

* update release checklist md

* Improve and unify testing facilities

This improves the testing facilities by making the test client easier to
use. It also removes code that is not required for the test client.
Besides that it also moves the test service and test client under
`node/test`.

* Update Cargo.lock

* Update node/test/client/src/block_builder.rs

Co-authored-by: Andronik Ordian <[email protected]>

* Remove explicit lifetime annotation

* Fix warnings and add extra `BlockBuilderExt`

Co-authored-by: Andronik Ordian <[email protected]>

* Remove old service, 3rd try

i.e.
Revert "Revert "Remove Old Service, 2nd try (#1732)" (#1758)"

This reverts commit c80f7b6b

.

Closes #1757.

We now have some evidence that the polkadot validator was producing
blocks after all; the reason the blocks_constructed metric was 0 was
that as a new metric it hadn't yet been incorporated into that
branch's codebase. See
https://github.com/paritytech/polkadot/issues/1757#issuecomment-700977602

As this PR is based on a newer `master` branch than the previous one,
that should hopefully no longer be an issue.

* paras trait now has an Origin type

* initial work running a two node local net

* use the right incantations so the nodes produce blocks together

* improve internal documentation

Co-authored-by: Bastian Köcher <[email protected]>

* Land XCM Builder

* Clean up Cargo dependencies

Co-authored-by: Gavin Wood <[email protected]>

Co-authored-by: Gavin Wood <[email protected]>

* Bump version

* Update RELEASE.md

Co-authored-by: Shawn Tabrizi <[email protected]>

Co-authored-by: Gavin Wood <[email protected]>

Co-authored-by: Gavin Wood <[email protected]>

This reverts commit 42fbca6e.

* Restore "Remove service, migrate all to service-new (#1630)"

i.e.
Revert "Revert "Remove service, migrate all to service-new (#1630)" (#1731)"

This reverts commit c68aee35

.

This allows us to get the changeset from #1630 into a new branch
which can be merged sometime in the future after appropriate burnin
tests have completed.

* remove ',)' from codebase outside of macros

* restore bdfl-preferred formatting

* attempt to improve destructuring formatting

* rename polkadot-service-new -> polkadot-service

* Apply suggestions from code review

Co-authored-by: Bastian Köcher <[email protected]>

* remove unused import

* Update runtime/rococo-v1/README.md

Co-authored-by: Bastian Köcher <[email protected]>

Co-authored-by: Andronik Ordian <[email protected]>
Co-authored-by: Bastian Köcher <[email protected]>

This reverts commit af14ea54.

* import rococo into chain-spec

* make a few stabs at moving forward

* wip: rococo readme

* remove /service crate

- Move the chain-spec files to node-service
- update sufficient cargo files that polkadot-service-new builds
- not everything else builds yet

* wip: chase down some build errors in polkadot-cli

There's a lot more to go, but some progress has happened.

* make more progress getting polkadot-cli to build

* don't ignore polkadot.json within the res directory

* don't recreate pathbufs

* Prepare Polkadot to be used by Cumulus

This begins to make Polkadot usable from Cumulus.

* Remove old test

* migrate new_chain_ops fix from /service

* partially remove node/test-service

* Reset some changes

* Revert "partially remove node/test-service"

This reverts commit 7b8f9ba5.

* WIP: replace v0 ParachainHost impl with v1 for test runtime

This is necessary because one of the current errors when building
the test service boils down to:

the trait bound `polkadot_test_runtime::RuntimeApiImpl<...>`:
  `polkadot_primitives::v1::ParachainHost<...>` is not satisfied

This is WIP because it appears to be causing some std leakage into
the wasm environment, or something; the compiler is currently
complaining about duplicate definitions of `panic_handler` and `oom`.
Presumably I have to identify all std types (Vec etc) and replace
them with sp_std equivalents.

* fix test runtime build

it wasn't std leakage, after all

* bump westend spec version

* use service-new as service within cli

* to revert: demo that forwarding the test runtime to the real impl blows up

* Revert "to revert: demo that forwarding the test runtime to the real impl blows up"

This reverts commit 68d2f385.

* Revert "Revert "to revert: demo that forwarding the test runtime to the real impl blows up""

This reverts commit 04cb1cbf.

Might have just forgotten to disable default features

* More reverts

* MOARE

* plug in the runtime as the generic instantiation

This feels closer to a solution, but it still has problems: in particular,
it's assumed that Runtime implements all appropriate Trait traits,
which this one apparently does not.

* implement necessary traits to get the test runtime compiling

This is almost certainly not correct in some way; it really
looks like I need to mess with the construct_runtime! macro
somehow, to inject the inclusion trait's event type as a Event
variant. Still, better lock down this changeset while it all
compiles.

* add inclusion::Event as variant into Event enum

* implement unimplemented bits in kusama

* implement unimplemented bits in polkadot runtime

* implement unimplemented bits in westend runtime

* migrate client upgrades from master

* update test service with new node changes

* package metadata--that wasn't intended to be removed

* add parachains v1 modules to each runtime

It's not clear what precisely this does, but it's probably the right
thing to do.

* enable cli to opt out of full node features

* adjust rococo chainspec per example

https://github.com/paritytech/polkadot/blob/26f1fa47

/service/src/chain_spec.rs#L362

* try to fix Cargo.lock

Co-authored-by: Bastian Köcher <[email protected]>
Co-authored-by: Andronik Ordian <[email protected]>

Co-authored-by: Parity Releases <[email protected]>
Co-authored-by: Demi Marie Obenour <[email protected]>

* 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 <[email protected]>

* 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 <[email protected]>

* 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 <[email protected]>

* bump version to v0.8.23
* bump substrate

* Update Cargo.toml

Fix version number

* Update Cargo.lock

* clean out v0 consensus crates

* remove service dependencies on old consensus code

* fix cli

* kill adder-collator

* bump Cargo.lock

* 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 <[email protected]>

Co-authored-by: Peter Goodspeed-Niklaus <[email protected]>

* start sketching out a collation generation subsystem

* invent a basic strategy for double initialization

* clean up warnings

* impl util requests from runtime assuming a context instead of a FromJob sender

* implement collation generation algorithm from guide

* update AllMessages in tests

* fix trivial review comments

* remove another redundant declaration from merge

* filter availability cores by para_id

* handle new activations each in their own async task

* update guide according to the actual current implementation

* add initialization to guide

* add general-purpose subsystem_test_harness helper

* write first handle_new_activations test

* add test that handle_new_activations filters local_validation_data requests

* add (failing) test of collation distribution message sending

* rustfmt

* broken: work on fixing sender test

Unfortunately, for reasons that are not yet clear, despite the public key
and checked data being identical, the signer is not producing an identical
signature. This commit produces this output (among more):

signing with  Public(c4733ab0bbe3ba4c096685d1737a7f498cdbdd167a767d04a21dc7df12b8c858 (5GWHUNm5...))
checking with Public(c4733ab0bbe3ba4c096685d1737a7f498cdbdd167a767d04a21dc7df12b8c858 (5GWHUNm5...))
signed payload:  [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 10, 0, 0, 0, c7, e5, c0, 64, 7a, db, fe, 44, 81, e5, 51, 11, 79, 9f, a5, 63, 93, 94, 3c, c4, 36, c6, 30, 36, c2, c5, 44, a2, 1b, db, b7, 82, 3, 17, a, 2e, 75, 97, b7, b7, e3, d8, 4c, 5, 39, 1d, 13, 9a, 62, b1, 57, e7, 87, 86, d8, c0, 82, f2, 9d, cf, 4c, 11, 13, 14]
checked payload: [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 10, 0, 0, 0, c7, e5, c0, 64, 7a, db, fe, 44, 81, e5, 51, 11, 79, 9f, a5, 63, 93, 94, 3c, c4, 36, c6, 30, 36, c2, c5, 44, a2, 1b, db, b7, 82, 3, 17, a, 2e, 75, 97, b7, b7, e3, d8, 4c, 5, 39, 1d, 13, 9a, 62, b1, 57, e7, 87, 86, d8, c0, 82, f2, 9d, cf, 4c, 11, 13, 14]

* fix broken test

* collation function returns commitments hash

It doesn't look like we use the actual commitments data anywhere, and
it's not obvious if there are any fields of `CandidateCommitments`
not available to the collator, so this commit just assigns them the
entire responsibility of generating the hash.

* add missing overseer impls

* calculating erasure coding is polkadot's responsibility, not cumulus

* concurrentize per-relay_parent requests