Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
// Copyright 2022 Parity Technologies (UK) Ltd.
// This file is part of Polkadot.
// Polkadot is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
// Polkadot is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// You should have received a copy of the GNU General Public License
// along with Polkadot. If not, see <http://www.gnu.org/licenses/>.
//! A tree utility for managing parachain fragments not referenced by the relay-chain.
//!
//! # Overview
//!
//! This module exposes two main types: [`FragmentTree`] and [`CandidateStorage`] which are meant to
//! be used in close conjunction. Each fragment tree is associated with a particular relay-parent
//! and each node in the tree represents a candidate. Each parachain has a single candidate storage,
//! but can have multiple trees for each relay chain block in the view.
//!
//! A tree has an associated [`Scope`] which defines limits on candidates within the tree.
//! Candidates themselves have their own [`Constraints`] which are either the constraints from the
//! scope, or, if there are previous nodes in the tree, a modified version of the previous
//! candidate's constraints.
//!
//! This module also makes use of types provided by the Inclusion Emulator module, such as
//! [`Fragment`] and [`Constraints`]. These perform the actual job of checking for validity of
//! prospective fragments.
//!
//! # Usage
//!
//! It's expected that higher-level code will have a tree for each relay-chain block which might
//! reasonably have blocks built upon it.
//!
//! Because a para only has a single candidate storage, trees only store indices into the storage.
//! The storage is meant to be pruned when trees are dropped by higher-level code.
//!
//! # Cycles
//!
//! Nodes do not uniquely refer to a parachain block for two reasons.
//! 1. There's no requirement that head-data is unique for a parachain. Furthermore, a parachain
//! is under no obligation to be acyclic, and this is mostly just because it's totally
//! inefficient to enforce it. Practical use-cases are acyclic, but there is still more than
//! one way to reach the same head-data.
//! 2. and candidates only refer to their parent by its head-data. This whole issue could be
//! resolved by having candidates reference their parent by candidate hash.
//!
//! The implication is that when we receive a candidate receipt, there are actually multiple
//! possibilities for any candidates between the para-head recorded in the relay parent's state
//! and the candidate in question.
//!
//! This means that our candidates need to handle multiple parents and that depth is an
//! attribute of a node in a tree, not a candidate. Put another way, the same candidate might
//! have different depths in different parts of the tree.
//!
//! As an extreme example, a candidate which produces head-data which is the same as its parent
//! can correspond to multiple nodes within the same [`FragmentTree`]. Such cycles are bounded
//! by the maximum depth allowed by the tree. An example with `max_depth: 4`:
//!
//! ```text
//! committed head
//! |
//! depth 0: head_a
//! |
//! depth 1: head_b
//! |
//! depth 2: head_a
//! |
//! depth 3: head_b
//! |
//! depth 4: head_a
//! ```
//!
//! As long as the [`CandidateStorage`] has bounded input on the number of candidates supplied,
//! [`FragmentTree`] complexity is bounded. This means that higher-level code needs to be selective
//! about limiting the amount of candidates that are considered.
//!
//! The code in this module is not designed for speed or efficiency, but conceptual simplicity.
//! Our assumption is that the amount of candidates and parachains we consider will be reasonably
//! bounded and in practice will not exceed a few thousand at any time. This naive implementation
//! will still perform fairly well under these conditions, despite being somewhat wasteful of
//! memory.
use std::{
borrow::Cow,
collections::{
hash_map::{Entry, HashMap},
BTreeMap, HashSet,
},
};
use super::LOG_TARGET;
use bitvec::prelude::*;
use polkadot_node_subsystem_util::inclusion_emulator::staging::{
ConstraintModifications, Constraints, Fragment, ProspectiveCandidate, RelayChainBlockInfo,
};
use polkadot_primitives::vstaging::{
BlockNumber, CandidateHash, CommittedCandidateReceipt, Hash, HeadData, Id as ParaId,
PersistedValidationData,
};
/// Kinds of failures to import a candidate into storage.
#[derive(Debug, Clone, PartialEq)]
pub enum CandidateStorageInsertionError {
/// An error indicating that a supplied candidate didn't match the persisted
/// validation data provided alongside it.
PersistedValidationDataMismatch,
/// The candidate was already known.
CandidateAlreadyKnown(CandidateHash),
}
/// Stores candidates and information about them such as their relay-parents and their backing
/// states.
pub(crate) struct CandidateStorage {
// Index from head data hash to candidate hashes with that head data as a parent.
by_parent_head: HashMap<Hash, HashSet<CandidateHash>>,
// Index from head data hash to candidate hashes outputting that head data.
by_output_head: HashMap<Hash, HashSet<CandidateHash>>,
// Index from candidate hash to fragment node.
by_candidate_hash: HashMap<CandidateHash, CandidateEntry>,
}
impl CandidateStorage {
/// Create a new `CandidateStorage`.
pub fn new() -> Self {
CandidateStorage {
by_parent_head: HashMap::new(),
by_output_head: HashMap::new(),
by_candidate_hash: HashMap::new(),
}
}
/// Introduce a new candidate.
pub fn add_candidate(
&mut self,
candidate: CommittedCandidateReceipt,
persisted_validation_data: PersistedValidationData,
) -> Result<CandidateHash, CandidateStorageInsertionError> {
let candidate_hash = candidate.hash();
if self.by_candidate_hash.contains_key(&candidate_hash) {
return Err(CandidateStorageInsertionError::CandidateAlreadyKnown(candidate_hash))
}
if persisted_validation_data.hash() != candidate.descriptor.persisted_validation_data_hash {
return Err(CandidateStorageInsertionError::PersistedValidationDataMismatch)
}
let parent_head_hash = persisted_validation_data.parent_head.hash();
let output_head_hash = candidate.commitments.head_data.hash();
let entry = CandidateEntry {
candidate_hash,
relay_parent: candidate.descriptor.relay_parent,
state: CandidateState::Introduced,
candidate: ProspectiveCandidate {
commitments: Cow::Owned(candidate.commitments),
collator: candidate.descriptor.collator,
collator_signature: candidate.descriptor.signature,
persisted_validation_data,
pov_hash: candidate.descriptor.pov_hash,
validation_code_hash: candidate.descriptor.validation_code_hash,
},
};
self.by_parent_head.entry(parent_head_hash).or_default().insert(candidate_hash);
self.by_output_head.entry(output_head_hash).or_default().insert(candidate_hash);
// sanity-checked already.
self.by_candidate_hash.insert(candidate_hash, entry);
Ok(candidate_hash)
}
/// Remove a candidate from the store.
pub fn remove_candidate(&mut self, candidate_hash: &CandidateHash) {
if let Some(entry) = self.by_candidate_hash.remove(candidate_hash) {
let parent_head_hash = entry.candidate.persisted_validation_data.parent_head.hash();
if let Entry::Occupied(mut e) = self.by_parent_head.entry(parent_head_hash) {
e.get_mut().remove(&candidate_hash);
if e.get().is_empty() {
e.remove();
}
}
}
}
/// Note that an existing candidate has been seconded.
pub fn mark_seconded(&mut self, candidate_hash: &CandidateHash) {
if let Some(entry) = self.by_candidate_hash.get_mut(candidate_hash) {
if entry.state != CandidateState::Backed {
entry.state = CandidateState::Seconded;
}
}
}
Loading full blame...