referrerpolicy=no-referrer-when-downgrade

polkadot_primitives/v9/
speculative.rs

1// Copyright (C) Parity Technologies (UK) Ltd.
2// This file is part of Polkadot.
3
4// Polkadot is free software: you can redistribute it and/or modify
5// it under the terms of the GNU General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8
9// Polkadot is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12// GNU General Public License for more details.
13
14// You should have received a copy of the GNU General Public License
15// along with Polkadot.  If not, see <http://www.gnu.org/licenses/>.
16
17//! Relay-visible speculative-messaging commitments.
18//!
19//! The relay chain sees only the commitments in the `UMPSignal::Provides` / `Requires` signals:
20//! - `Provides(StreamsRoot)`: the root of the sender's keyed stream commitment tree, one per sender
21//! block, recorded into the relay's provides window.
22//! - `Requires(RequiresSet)`: a receiver's expected `(source, StreamsRoot)` entries, matched
23//! against each source's window.
24//!
25//! These live here because `UMPSignal` is defined in `polkadot-primitives::v9` and the relay chain
26//! decodes them. The parachain-side types that build them are in
27//! `cumulus-primitives-spec-messaging`.
28
29use alloc::vec::Vec;
30use polkadot_core_primitives::Hash;
31use polkadot_parachain_primitives::primitives::Id as ParaId;
32use sp_core::ConstU32;
33use sp_runtime::BoundedVec;
34
35/// Maximum number of source parachains a receiver can consume from in one block; bounds the
36/// `requires` commitment. The design's `MaxCommitmentEntries`: today's parachain count rounded up.
37/// Consensus-relevant, since decode rejects larger sets.
38pub const MAX_COMMITMENT_ENTRIES: u32 = 256;
39
40/// Root of a sender's stream commitment tree: a compact binary trie keyed by the 8-byte `StreamId`
41/// encoding, with the streams' MMR roots as leaves.
42///
43/// A newtype over `Hash`, distinct from an MMR root so the two cannot be confused. The relay chain
44/// treats it as opaque; the tree and its proofs are in
45/// `cumulus-primitives-spec-messaging::streams_root`.
46#[derive(
47	Clone,
48	Copy,
49	codec::Encode,
50	codec::Decode,
51	codec::DecodeWithMemTracking,
52	codec::MaxEncodedLen,
53	Debug,
54	Default,
55	Eq,
56	PartialEq,
57	scale_info::TypeInfo,
58)]
59#[cfg_attr(feature = "std", derive(Hash))]
60pub struct StreamsRoot(pub Hash);
61
62/// A receiver's `requires` commitment: a bounded set of `(ParaId, StreamsRoot)` entries, one per
63/// source parachain, sorted by strictly increasing `ParaId`. The order is enforced at decode so the
64/// encoding is canonical. The relay matches each entry against that source's provides window.
65#[derive(
66	Clone, codec::Encode, codec::MaxEncodedLen, Debug, Eq, PartialEq, scale_info::TypeInfo,
67)]
68#[cfg_attr(feature = "std", derive(Hash))]
69pub struct RequiresSet(BoundedVec<(ParaId, StreamsRoot), ConstU32<MAX_COMMITMENT_ENTRIES>>);
70
71/// Manual `Decode` to enforce the canonical form: non-empty, strictly increasing `ParaId`s. An
72/// empty set has nothing the relay could match; a candidate that requires nothing emits no
73/// `Requires` signal.
74impl codec::Decode for RequiresSet {
75	fn decode<I: codec::Input>(input: &mut I) -> Result<Self, codec::Error> {
76		let inner =
77			BoundedVec::<(ParaId, StreamsRoot), ConstU32<MAX_COMMITMENT_ENTRIES>>::decode(input)?;
78
79		if inner.is_empty() {
80			return Err(codec::Error::from("RequiresSet must not be empty"));
81		}
82		for pair in inner.windows(2) {
83			if pair[0].0 >= pair[1].0 {
84				return Err(codec::Error::from(
85					"RequiresSet entries must be sorted by increasing ParaId",
86				));
87			}
88		}
89
90		Ok(Self(inner))
91	}
92}
93
94// Mem-tracking safe; the derive does not compose with a manual `Decode`.
95impl codec::DecodeWithMemTracking for RequiresSet {}
96
97impl RequiresSet {
98	/// The committed `StreamsRoot` for `source`, if present (O(log n) lookup).
99	pub fn get(&self, source: ParaId) -> Option<&StreamsRoot> {
100		self.0
101			.binary_search_by_key(&source, |(id, _)| *id)
102			.ok()
103			.map(|idx| &self.0[idx].1)
104	}
105
106	/// The number of entries in the set.
107	pub fn len(&self) -> usize {
108		self.0.len()
109	}
110
111	/// Whether the set has no entries.
112	pub fn is_empty(&self) -> bool {
113		self.0.is_empty()
114	}
115
116	/// Iterate the `(source, StreamsRoot)` entries in ascending `ParaId` order.
117	pub fn iter(&self) -> impl Iterator<Item = &(ParaId, StreamsRoot)> {
118		self.0.iter()
119	}
120
121	/// Build a [`RequiresSet`] from any iterator, sorting by `ParaId`.
122	pub fn try_from_iter(
123		it: impl IntoIterator<Item = (ParaId, StreamsRoot)>,
124	) -> Result<Self, CommitmentError> {
125		let mut entries: Vec<(ParaId, StreamsRoot)> = it.into_iter().collect();
126		entries.sort_by_key(|(source, _)| *source);
127
128		if entries.is_empty() {
129			return Err(CommitmentError::Empty);
130		}
131		if entries.windows(2).any(|w| w[0].0 == w[1].0) {
132			return Err(CommitmentError::DuplicateParaId);
133		}
134
135		let inner = BoundedVec::try_from(entries).map_err(|_| CommitmentError::TooManyEntries)?;
136
137		Ok(Self(inner))
138	}
139}
140
141impl<'a> IntoIterator for &'a RequiresSet {
142	type Item = &'a (ParaId, StreamsRoot);
143	type IntoIter = core::slice::Iter<'a, (ParaId, StreamsRoot)>;
144
145	fn into_iter(self) -> Self::IntoIter {
146		self.0.iter()
147	}
148}
149
150/// Errors that can occur when constructing a [`RequiresSet`].
151#[derive(Debug, PartialEq, Eq)]
152pub enum CommitmentError {
153	/// No entries. A candidate that requires nothing emits no `Requires` signal instead.
154	Empty,
155	/// The same source `ParaId` appears more than once.
156	DuplicateParaId,
157	/// More entries were provided than `MAX_COMMITMENT_ENTRIES` allows.
158	TooManyEntries,
159}
160
161#[cfg(test)]
162mod tests {
163	use super::*;
164	use codec::{Decode, Encode};
165
166	fn sr(byte: u8) -> StreamsRoot {
167		StreamsRoot(Hash::repeat_byte(byte))
168	}
169
170	/// `n` entries with distinct, strictly-increasing `ParaId`s.
171	fn many(n: u32) -> Vec<(ParaId, StreamsRoot)> {
172		(0..n).map(|i| (ParaId::from(i), sr(i as u8))).collect()
173	}
174
175	#[test]
176	fn try_from_iter_sorts_entries() {
177		let set = RequiresSet::try_from_iter([
178			(ParaId::from(3), sr(3)),
179			(ParaId::from(1), sr(1)),
180			(ParaId::from(2), sr(2)),
181		])
182		.unwrap();
183
184		let ids: Vec<ParaId> = set.iter().map(|(id, _)| *id).collect();
185		assert_eq!(ids, vec![ParaId::from(1), ParaId::from(2), ParaId::from(3)]);
186	}
187
188	#[test]
189	fn try_from_iter_rejects_duplicate_para_id() {
190		let result =
191			RequiresSet::try_from_iter([(ParaId::from(1), sr(1)), (ParaId::from(1), sr(2))]);
192		assert_eq!(result, Err(CommitmentError::DuplicateParaId));
193	}
194
195	#[test]
196	fn try_from_iter_rejects_too_many_entries() {
197		let result = RequiresSet::try_from_iter(many(MAX_COMMITMENT_ENTRIES + 1));
198		assert_eq!(result, Err(CommitmentError::TooManyEntries));
199	}
200
201	#[test]
202	fn encode_decode_round_trip_works() {
203		let set = RequiresSet::try_from_iter([(ParaId::from(1), sr(1)), (ParaId::from(2), sr(2))])
204			.unwrap();
205
206		let encoded = set.encode();
207		let decoded = RequiresSet::decode(&mut &encoded[..]).unwrap();
208
209		assert_eq!(set, decoded);
210	}
211
212	#[test]
213	fn decode_rejects_out_of_order_para_ids() {
214		let bad: Vec<(ParaId, StreamsRoot)> =
215			vec![(ParaId::from(2), sr(2)), (ParaId::from(1), sr(1))];
216		let encoded = bad.encode();
217
218		assert!(RequiresSet::decode(&mut &encoded[..]).is_err());
219	}
220
221	#[test]
222	fn decode_rejects_duplicate_para_ids() {
223		let bad: Vec<(ParaId, StreamsRoot)> =
224			vec![(ParaId::from(1), sr(1)), (ParaId::from(1), sr(2))];
225		let encoded = bad.encode();
226
227		assert!(RequiresSet::decode(&mut &encoded[..]).is_err());
228	}
229
230	#[test]
231	fn decode_rejects_too_many_entries() {
232		let encoded = many(MAX_COMMITMENT_ENTRIES + 1).encode();
233		assert!(RequiresSet::decode(&mut &encoded[..]).is_err());
234	}
235
236	#[test]
237	fn get_finds_existing_and_missing_entries() {
238		let set = RequiresSet::try_from_iter([(ParaId::from(1), sr(1)), (ParaId::from(3), sr(3))])
239			.unwrap();
240
241		assert_eq!(set.get(ParaId::from(1)), Some(&sr(1)));
242		assert_eq!(set.get(ParaId::from(3)), Some(&sr(3)));
243		assert_eq!(set.get(ParaId::from(2)), None);
244	}
245
246	#[test]
247	fn len_and_is_empty() {
248		let set = RequiresSet::try_from_iter([(ParaId::from(1), sr(1))]).unwrap();
249		assert!(!set.is_empty());
250		assert_eq!(set.len(), 1);
251	}
252
253	#[test]
254	fn empty_set_is_not_constructible_or_decodable() {
255		// Neither the constructor nor the wire admits an empty set.
256		assert_eq!(RequiresSet::try_from_iter([]), Err(CommitmentError::Empty));
257		let encoded = Vec::<(ParaId, StreamsRoot)>::new().encode();
258		assert!(RequiresSet::decode(&mut &encoded[..]).is_err());
259	}
260
261	#[test]
262	fn into_iter_yields_sorted_entries() {
263		let set = RequiresSet::try_from_iter([(ParaId::from(2), sr(2)), (ParaId::from(1), sr(1))])
264			.unwrap();
265
266		let collected: Vec<_> = (&set).into_iter().collect();
267		assert_eq!(collected, vec![&(ParaId::from(1), sr(1)), &(ParaId::from(2), sr(2))]);
268	}
269}