referrerpolicy=no-referrer-when-downgrade

finality_relay/
headers.rs

1// Copyright 2019-2021 Parity Technologies (UK) Ltd.
2// This file is part of Parity Bridges Common.
3
4// Parity Bridges Common 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// Parity Bridges Common 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 Parity Bridges Common.  If not, see <http://www.gnu.org/licenses/>.
16
17use crate::{
18	finality_loop::SyncInfo, finality_proofs::FinalityProofsBuf, Error, FinalitySyncPipeline,
19	HeadersToRelay, SourceClient, SourceHeader, TargetClient,
20};
21
22use bp_header_chain::FinalityProof;
23use num_traits::Saturating;
24use std::cmp::Ordering;
25
26/// Unjustified headers container. Ordered by header number.
27pub type UnjustifiedHeaders<H> = Vec<H>;
28
29#[derive(Debug)]
30#[cfg_attr(test, derive(Clone, PartialEq))]
31pub struct JustifiedHeader<P: FinalitySyncPipeline> {
32	pub header: P::Header,
33	pub proof: P::FinalityProof,
34}
35
36impl<P: FinalitySyncPipeline> JustifiedHeader<P> {
37	pub fn number(&self) -> P::Number {
38		self.header.number()
39	}
40}
41
42/// Finality proof that has been selected by the `read_missing_headers` function.
43pub enum JustifiedHeaderSelector<P: FinalitySyncPipeline> {
44	/// Mandatory header and its proof has been selected. We shall submit proof for this header.
45	Mandatory(JustifiedHeader<P>),
46	/// Regular header and its proof has been selected. We may submit this proof, or proof for
47	/// some better header.
48	Regular(UnjustifiedHeaders<P::Header>, JustifiedHeader<P>),
49	/// We haven't found any missing header with persistent proof at the target client.
50	None(UnjustifiedHeaders<P::Header>),
51}
52
53impl<P: FinalitySyncPipeline> JustifiedHeaderSelector<P> {
54	/// Selects last header with persistent justification, missing from the target and matching
55	/// the `headers_to_relay` criteria.
56	pub(crate) async fn new<SC: SourceClient<P>, TC: TargetClient<P>>(
57		source_client: &SC,
58		info: &SyncInfo<P>,
59		headers_to_relay: HeadersToRelay,
60		free_headers_interval: Option<P::Number>,
61	) -> Result<Self, Error<P, SC::Error, TC::Error>> {
62		let mut unjustified_headers = Vec::new();
63		let mut maybe_justified_header = None;
64
65		let mut header_number = info.best_number_at_target + 1.into();
66		while header_number <= info.best_number_at_source {
67			let (header, maybe_proof) = source_client
68				.header_and_finality_proof(header_number)
69				.await
70				.map_err(Error::Source)?;
71
72			match (header.is_mandatory(), maybe_proof) {
73				(true, Some(proof)) => {
74					log::trace!(target: "bridge", "Header {:?} is mandatory", header_number);
75					return Ok(Self::Mandatory(JustifiedHeader { header, proof }))
76				},
77				(true, None) => return Err(Error::MissingMandatoryFinalityProof(header.number())),
78				(false, Some(proof))
79					if need_to_relay::<P>(
80						info,
81						headers_to_relay,
82						free_headers_interval,
83						&header,
84					) =>
85				{
86					log::trace!(target: "bridge", "Header {:?} has persistent finality proof", header_number);
87					unjustified_headers.clear();
88					maybe_justified_header = Some(JustifiedHeader { header, proof });
89				},
90				_ => {
91					unjustified_headers.push(header);
92				},
93			}
94
95			header_number = header_number + 1.into();
96		}
97
98		log::trace!(
99			target: "bridge",
100			"Read {} {} headers. Selected finality proof for header: {:?}",
101			info.num_headers(),
102			P::SOURCE_NAME,
103			maybe_justified_header.as_ref().map(|justified_header| &justified_header.header),
104		);
105
106		Ok(match maybe_justified_header {
107			Some(justified_header) => Self::Regular(unjustified_headers, justified_header),
108			None => Self::None(unjustified_headers),
109		})
110	}
111
112	/// Returns selected mandatory header if we have seen one. Otherwise returns `None`.
113	pub fn select_mandatory(self) -> Option<JustifiedHeader<P>> {
114		match self {
115			JustifiedHeaderSelector::Mandatory(header) => Some(header),
116			_ => None,
117		}
118	}
119
120	/// Tries to improve previously selected header using ephemeral
121	/// justifications stream.
122	pub fn select(
123		self,
124		info: &SyncInfo<P>,
125		headers_to_relay: HeadersToRelay,
126		free_headers_interval: Option<P::Number>,
127		buf: &FinalityProofsBuf<P>,
128	) -> Option<JustifiedHeader<P>> {
129		let (unjustified_headers, maybe_justified_header) = match self {
130			JustifiedHeaderSelector::Mandatory(justified_header) => return Some(justified_header),
131			JustifiedHeaderSelector::Regular(unjustified_headers, justified_header) =>
132				(unjustified_headers, Some(justified_header)),
133			JustifiedHeaderSelector::None(unjustified_headers) => (unjustified_headers, None),
134		};
135
136		let mut finality_proofs_iter = buf.buf().iter().rev();
137		let mut maybe_finality_proof = finality_proofs_iter.next();
138
139		let mut unjustified_headers_iter = unjustified_headers.iter().rev();
140		let mut maybe_unjustified_header = unjustified_headers_iter.next();
141
142		while let (Some(finality_proof), Some(unjustified_header)) =
143			(maybe_finality_proof, maybe_unjustified_header)
144		{
145			match finality_proof.target_header_number().cmp(&unjustified_header.number()) {
146				Ordering::Equal
147					if need_to_relay::<P>(
148						info,
149						headers_to_relay,
150						free_headers_interval,
151						&unjustified_header,
152					) =>
153				{
154					log::trace!(
155						target: "bridge",
156						"Managed to improve selected {} finality proof {:?} to {:?}.",
157						P::SOURCE_NAME,
158						maybe_justified_header.as_ref().map(|justified_header| justified_header.number()),
159						finality_proof.target_header_number()
160					);
161					return Some(JustifiedHeader {
162						header: unjustified_header.clone(),
163						proof: finality_proof.clone(),
164					})
165				},
166				Ordering::Equal => {
167					maybe_finality_proof = finality_proofs_iter.next();
168					maybe_unjustified_header = unjustified_headers_iter.next();
169				},
170				Ordering::Less => maybe_unjustified_header = unjustified_headers_iter.next(),
171				Ordering::Greater => {
172					maybe_finality_proof = finality_proofs_iter.next();
173				},
174			}
175		}
176
177		log::trace!(
178			target: "bridge",
179			"Could not improve selected {} finality proof {:?}.",
180			P::SOURCE_NAME,
181			maybe_justified_header.as_ref().map(|justified_header| justified_header.number())
182		);
183		maybe_justified_header
184	}
185}
186
187/// Returns true if we want to relay header `header_number`.
188fn need_to_relay<P: FinalitySyncPipeline>(
189	info: &SyncInfo<P>,
190	headers_to_relay: HeadersToRelay,
191	free_headers_interval: Option<P::Number>,
192	header: &P::Header,
193) -> bool {
194	match headers_to_relay {
195		HeadersToRelay::All => true,
196		HeadersToRelay::Mandatory => header.is_mandatory(),
197		HeadersToRelay::Free =>
198			header.is_mandatory() ||
199				free_headers_interval
200					.map(|free_headers_interval| {
201						header.number().saturating_sub(info.best_number_at_target) >=
202							free_headers_interval
203					})
204					.unwrap_or(false),
205	}
206}
207
208#[cfg(test)]
209mod tests {
210	use super::*;
211	use crate::mock::*;
212
213	#[test]
214	fn select_better_recent_finality_proof_works() {
215		let info = SyncInfo {
216			best_number_at_source: 10,
217			best_number_at_target: 5,
218			is_using_same_fork: true,
219		};
220
221		// if there are no unjustified headers, nothing is changed
222		let finality_proofs_buf =
223			FinalityProofsBuf::<TestFinalitySyncPipeline>::new(vec![TestFinalityProof(5)]);
224		let justified_header =
225			JustifiedHeader { header: TestSourceHeader(false, 2, 2), proof: TestFinalityProof(2) };
226		let selector = JustifiedHeaderSelector::Regular(vec![], justified_header.clone());
227		assert_eq!(
228			selector.select(&info, HeadersToRelay::All, None, &finality_proofs_buf),
229			Some(justified_header)
230		);
231
232		// if there are no buffered finality proofs, nothing is changed
233		let finality_proofs_buf = FinalityProofsBuf::<TestFinalitySyncPipeline>::new(vec![]);
234		let justified_header =
235			JustifiedHeader { header: TestSourceHeader(false, 2, 2), proof: TestFinalityProof(2) };
236		let selector = JustifiedHeaderSelector::Regular(
237			vec![TestSourceHeader(false, 5, 5)],
238			justified_header.clone(),
239		);
240		assert_eq!(
241			selector.select(&info, HeadersToRelay::All, None, &finality_proofs_buf),
242			Some(justified_header)
243		);
244
245		// if there's no intersection between recent finality proofs and unjustified headers,
246		// nothing is changed
247		let finality_proofs_buf = FinalityProofsBuf::<TestFinalitySyncPipeline>::new(vec![
248			TestFinalityProof(1),
249			TestFinalityProof(4),
250		]);
251		let justified_header =
252			JustifiedHeader { header: TestSourceHeader(false, 2, 2), proof: TestFinalityProof(2) };
253		let selector = JustifiedHeaderSelector::Regular(
254			vec![TestSourceHeader(false, 9, 9), TestSourceHeader(false, 10, 10)],
255			justified_header.clone(),
256		);
257		assert_eq!(
258			selector.select(&info, HeadersToRelay::All, None, &finality_proofs_buf),
259			Some(justified_header)
260		);
261
262		// if there's intersection between recent finality proofs and unjustified headers, but there
263		// are no proofs in this intersection, nothing is changed
264		let finality_proofs_buf = FinalityProofsBuf::<TestFinalitySyncPipeline>::new(vec![
265			TestFinalityProof(7),
266			TestFinalityProof(11),
267		]);
268		let justified_header =
269			JustifiedHeader { header: TestSourceHeader(false, 2, 2), proof: TestFinalityProof(2) };
270		let selector = JustifiedHeaderSelector::Regular(
271			vec![
272				TestSourceHeader(false, 8, 8),
273				TestSourceHeader(false, 9, 9),
274				TestSourceHeader(false, 10, 10),
275			],
276			justified_header.clone(),
277		);
278		assert_eq!(
279			selector.select(&info, HeadersToRelay::All, None, &finality_proofs_buf),
280			Some(justified_header)
281		);
282
283		// if there's intersection between recent finality proofs and unjustified headers and
284		// there's a proof in this intersection:
285		// - this better (last from intersection) proof is selected;
286		// - 'obsolete' unjustified headers are pruned.
287		let finality_proofs_buf = FinalityProofsBuf::<TestFinalitySyncPipeline>::new(vec![
288			TestFinalityProof(7),
289			TestFinalityProof(9),
290		]);
291		let justified_header =
292			JustifiedHeader { header: TestSourceHeader(false, 2, 2), proof: TestFinalityProof(2) };
293		let selector = JustifiedHeaderSelector::Regular(
294			vec![
295				TestSourceHeader(false, 8, 8),
296				TestSourceHeader(false, 9, 9),
297				TestSourceHeader(false, 10, 10),
298			],
299			justified_header,
300		);
301		assert_eq!(
302			selector.select(&info, HeadersToRelay::All, None, &finality_proofs_buf),
303			Some(JustifiedHeader {
304				header: TestSourceHeader(false, 9, 9),
305				proof: TestFinalityProof(9)
306			})
307		);
308
309		// when only free headers needs to be relayed and there are no free headers
310		let finality_proofs_buf = FinalityProofsBuf::<TestFinalitySyncPipeline>::new(vec![
311			TestFinalityProof(7),
312			TestFinalityProof(9),
313		]);
314		let selector = JustifiedHeaderSelector::None(vec![
315			TestSourceHeader(false, 8, 8),
316			TestSourceHeader(false, 9, 9),
317			TestSourceHeader(false, 10, 10),
318		]);
319		assert_eq!(
320			selector.select(&info, HeadersToRelay::Free, Some(7), &finality_proofs_buf),
321			None,
322		);
323
324		// when only free headers needs to be relayed, mandatory header may be selected
325		let finality_proofs_buf = FinalityProofsBuf::<TestFinalitySyncPipeline>::new(vec![
326			TestFinalityProof(6),
327			TestFinalityProof(9),
328		]);
329		let selector = JustifiedHeaderSelector::None(vec![
330			TestSourceHeader(false, 8, 8),
331			TestSourceHeader(true, 9, 9),
332			TestSourceHeader(false, 10, 10),
333		]);
334		assert_eq!(
335			selector.select(&info, HeadersToRelay::Free, Some(7), &finality_proofs_buf),
336			Some(JustifiedHeader {
337				header: TestSourceHeader(true, 9, 9),
338				proof: TestFinalityProof(9)
339			})
340		);
341
342		// when only free headers needs to be relayed and there is free header
343		let finality_proofs_buf = FinalityProofsBuf::<TestFinalitySyncPipeline>::new(vec![
344			TestFinalityProof(7),
345			TestFinalityProof(9),
346			TestFinalityProof(14),
347		]);
348		let selector = JustifiedHeaderSelector::None(vec![
349			TestSourceHeader(false, 7, 7),
350			TestSourceHeader(false, 10, 10),
351			TestSourceHeader(false, 14, 14),
352		]);
353		assert_eq!(
354			selector.select(&info, HeadersToRelay::Free, Some(7), &finality_proofs_buf),
355			Some(JustifiedHeader {
356				header: TestSourceHeader(false, 14, 14),
357				proof: TestFinalityProof(14)
358			})
359		);
360	}
361}