prospective-parachains: limit count of nodes in a fragment tree #3219
Assignees
Labels
T0-node
This PR/Issue is related to the topic “node”.
T8-polkadot
This PR/Issue is related to/affects the Polkadot network.
Comments
alindima
added
T0-node
This was referenced Feb 6, 2024
|
will most likely be tackled as part of: #3541 |
github-merge-queue bot
pushed a commit
that referenced
this issue
May 13, 2024
Reworks prospective-parachains so that we allow a number of unconnected candidates (for which we don't know the parent candidate yet). Needed for elastic scaling: #3541. Without this, candidate B will not be validated and backed until candidate A (its parent) is validated and a backing statement reaches the validator. Due to the high complexity of the subsystem, I rewrote parts of it so that we don't concern ourselves with candidates which form cycles or which form parachain forks. We now have "Fragment chains" instead of "Fragment trees". This greatly simplifies some of the code and is a compromise we can make. We just need to make sure that cycle-producing parachains don't brick the relay chain and that fork-producing parachains can still make some progress (on one core at least). The only forks that are allowed are those on the relay chain, obviously. Unconnected candidates are kept in the `CandidateStorage` and whenever a new candidate is introduced, we try to repopulate the chain with as many candidates as we can. Also fixes #3219 Guide changes will be done as part of: #3699 TODOs: - [x] see if we can replace the `Cow` over the candidate commitments with an `Arc` over the entire `ProspectiveCandidate`. It's only being overwritten in unit tests. We can work around that. - [x] finish fragment_chain unit tests - [x] add more prospective-parachains subsystem tests - [x] test with zombienet what happens if a parachain is creating cycles (it should not brick the relay chain). - [x] test with zombienet a parachain that is creating forks. it should keep producing blocks from time to time (one bad collator should not DOS the parachain, even if throughput decreases) - [x] add some more logs and metrics - [x] add prdoc and remove the "silent" label --------- Signed-off-by: Andrei Sandu <andrei-mihail@parity.io> Co-authored-by: Andrei Sandu <andrei-mihail@parity.io>
github-project-automation
bot
moved this from In Progress
to Completed
in parachains team board
hitchhooker
pushed a commit
to ibp-network/polkadot-sdk
that referenced
this issue
Jun 5, 2024
Reworks prospective-parachains so that we allow a number of unconnected candidates (for which we don't know the parent candidate yet). Needed for elastic scaling: paritytech#3541. Without this, candidate B will not be validated and backed until candidate A (its parent) is validated and a backing statement reaches the validator. Due to the high complexity of the subsystem, I rewrote parts of it so that we don't concern ourselves with candidates which form cycles or which form parachain forks. We now have "Fragment chains" instead of "Fragment trees". This greatly simplifies some of the code and is a compromise we can make. We just need to make sure that cycle-producing parachains don't brick the relay chain and that fork-producing parachains can still make some progress (on one core at least). The only forks that are allowed are those on the relay chain, obviously. Unconnected candidates are kept in the `CandidateStorage` and whenever a new candidate is introduced, we try to repopulate the chain with as many candidates as we can. Also fixes paritytech#3219 Guide changes will be done as part of: paritytech#3699 TODOs: - [x] see if we can replace the `Cow` over the candidate commitments with an `Arc` over the entire `ProspectiveCandidate`. It's only being overwritten in unit tests. We can work around that. - [x] finish fragment_chain unit tests - [x] add more prospective-parachains subsystem tests - [x] test with zombienet what happens if a parachain is creating cycles (it should not brick the relay chain). - [x] test with zombienet a parachain that is creating forks. it should keep producing blocks from time to time (one bad collator should not DOS the parachain, even if throughput decreases) - [x] add some more logs and metrics - [x] add prdoc and remove the "silent" label --------- Signed-off-by: Andrei Sandu <andrei-mihail@parity.io> Co-authored-by: Andrei Sandu <andrei-mihail@parity.io>
liuchengxu
pushed a commit
to liuchengxu/polkadot-sdk
that referenced
this issue
Jun 19, 2024
Reworks prospective-parachains so that we allow a number of unconnected candidates (for which we don't know the parent candidate yet). Needed for elastic scaling: paritytech#3541. Without this, candidate B will not be validated and backed until candidate A (its parent) is validated and a backing statement reaches the validator. Due to the high complexity of the subsystem, I rewrote parts of it so that we don't concern ourselves with candidates which form cycles or which form parachain forks. We now have "Fragment chains" instead of "Fragment trees". This greatly simplifies some of the code and is a compromise we can make. We just need to make sure that cycle-producing parachains don't brick the relay chain and that fork-producing parachains can still make some progress (on one core at least). The only forks that are allowed are those on the relay chain, obviously. Unconnected candidates are kept in the `CandidateStorage` and whenever a new candidate is introduced, we try to repopulate the chain with as many candidates as we can. Also fixes paritytech#3219 Guide changes will be done as part of: paritytech#3699 TODOs: - [x] see if we can replace the `Cow` over the candidate commitments with an `Arc` over the entire `ProspectiveCandidate`. It's only being overwritten in unit tests. We can work around that. - [x] finish fragment_chain unit tests - [x] add more prospective-parachains subsystem tests - [x] test with zombienet what happens if a parachain is creating cycles (it should not brick the relay chain). - [x] test with zombienet a parachain that is creating forks. it should keep producing blocks from time to time (one bad collator should not DOS the parachain, even if throughput decreases) - [x] add some more logs and metrics - [x] add prdoc and remove the "silent" label --------- Signed-off-by: Andrei Sandu <andrei-mihail@parity.io> Co-authored-by: Andrei Sandu <andrei-mihail@parity.io>
TarekkMA
pushed a commit
to moonbeam-foundation/polkadot-sdk
that referenced
this issue
Aug 2, 2024
Reworks prospective-parachains so that we allow a number of unconnected candidates (for which we don't know the parent candidate yet). Needed for elastic scaling: paritytech#3541. Without this, candidate B will not be validated and backed until candidate A (its parent) is validated and a backing statement reaches the validator. Due to the high complexity of the subsystem, I rewrote parts of it so that we don't concern ourselves with candidates which form cycles or which form parachain forks. We now have "Fragment chains" instead of "Fragment trees". This greatly simplifies some of the code and is a compromise we can make. We just need to make sure that cycle-producing parachains don't brick the relay chain and that fork-producing parachains can still make some progress (on one core at least). The only forks that are allowed are those on the relay chain, obviously. Unconnected candidates are kept in the `CandidateStorage` and whenever a new candidate is introduced, we try to repopulate the chain with as many candidates as we can. Also fixes paritytech#3219 Guide changes will be done as part of: paritytech#3699 TODOs: - [x] see if we can replace the `Cow` over the candidate commitments with an `Arc` over the entire `ProspectiveCandidate`. It's only being overwritten in unit tests. We can work around that. - [x] finish fragment_chain unit tests - [x] add more prospective-parachains subsystem tests - [x] test with zombienet what happens if a parachain is creating cycles (it should not brick the relay chain). - [x] test with zombienet a parachain that is creating forks. it should keep producing blocks from time to time (one bad collator should not DOS the parachain, even if throughput decreases) - [x] add some more logs and metrics - [x] add prdoc and remove the "silent" label --------- Signed-off-by: Andrei Sandu <andrei-mihail@parity.io> Co-authored-by: Andrei Sandu <andrei-mihail@parity.io>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
As discovered in #3160 (comment), the fragment tree size is an exponential function of
O(num_forks ^ core_count).This is not a problem for non-elastic-scaling, because core_count will always be 1 and num_forks is a constant equal to the backing group size multiplied by the configured async backing max candidate depth.
For secure elastic scaling, we should add a limit to the number of nodes in a fragment tree, to not allow for an unreasonable amount of forks, which could potentially DOS block authoring. This is needed because num_forks and core_count will be influenced by how many cores a parachain acquires. For example if they acquire 100 cores, the fragment tree size could grow to O(500^100) in size. It's reasonable to enforce that parachains that have forks over a sensible amount will not be able to make use of elastic scaling.
The text was updated successfully, but these errors were encountered: