/__w/smoldot/smoldot/repo/lib/src/finality/verify.rs
Line | Count | Source (jump to first uncovered line) |
1 | | // Smoldot |
2 | | // Copyright (C) 2023 Pierre Krieger |
3 | | // SPDX-License-Identifier: GPL-3.0-or-later WITH Classpath-exception-2.0 |
4 | | |
5 | | // This program is free software: you can redistribute it and/or modify |
6 | | // it under the terms of the GNU General Public License as published by |
7 | | // the Free Software Foundation, either version 3 of the License, or |
8 | | // (at your option) any later version. |
9 | | |
10 | | // This program is distributed in the hope that it will be useful, |
11 | | // but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
13 | | // GNU General Public License for more details. |
14 | | |
15 | | // You should have received a copy of the GNU General Public License |
16 | | // along with this program. If not, see <http://www.gnu.org/licenses/>. |
17 | | |
18 | | use crate::finality::decode; |
19 | | |
20 | | use alloc::vec::Vec; |
21 | | use core::{cmp, iter, mem}; |
22 | | use rand_chacha::{ |
23 | | rand_core::{RngCore as _, SeedableRng as _}, |
24 | | ChaCha20Rng, |
25 | | }; |
26 | | |
27 | | /// Configuration for a commit verification process. |
28 | | #[derive(Debug)] |
29 | | pub struct CommitVerifyConfig<C> { |
30 | | /// SCALE-encoded commit to verify. |
31 | | pub commit: C, |
32 | | |
33 | | /// Number of bytes used for encoding the block number in the SCALE-encoded commit. |
34 | | pub block_number_bytes: usize, |
35 | | |
36 | | // TODO: document |
37 | | pub expected_authorities_set_id: u64, |
38 | | |
39 | | /// Number of authorities that are allowed to emit pre-commits. Used to calculate the |
40 | | /// threshold of the number of required signatures. |
41 | | pub num_authorities: u32, |
42 | | |
43 | | /// Seed for a PRNG used for various purposes during the verification. |
44 | | /// |
45 | | /// > **Note**: The verification is nonetheless deterministic. |
46 | | pub randomness_seed: [u8; 32], |
47 | | } |
48 | | |
49 | | /// Commit verification in progress. |
50 | | #[must_use] |
51 | | pub enum CommitVerify<C> { |
52 | | /// See [`CommitVerifyIsAuthority`]. |
53 | | IsAuthority(CommitVerifyIsAuthority<C>), |
54 | | /// See [`CommitVerifyIsParent`]. |
55 | | IsParent(CommitVerifyIsParent<C>), |
56 | | /// Verification is finished. Contains an error if the commit message is invalid. |
57 | | Finished(Result<(), CommitVerifyError>), |
58 | | /// Verification is finished, but [`CommitVerifyIsParent::resume`] has been called with `None`, |
59 | | /// meaning that some signatures couldn't be verified, and the commit message doesn't contain |
60 | | /// enough signatures that are known to be valid. |
61 | | /// |
62 | | /// The commit must be verified again after more blocks are available. |
63 | | FinishedUnknown, |
64 | | } |
65 | | |
66 | | /// Verifies that a commit is valid. |
67 | 0 | pub fn verify_commit<C: AsRef<[u8]>>(config: CommitVerifyConfig<C>) -> CommitVerify<C> { |
68 | 0 | let decoded_commit = |
69 | 0 | match decode::decode_grandpa_commit(config.commit.as_ref(), config.block_number_bytes) { |
70 | 0 | Ok(c) => c, |
71 | 0 | Err(_) => return CommitVerify::Finished(Err(CommitVerifyError::InvalidFormat)), |
72 | | }; |
73 | | |
74 | 0 | if decoded_commit.set_id != config.expected_authorities_set_id { |
75 | 0 | return CommitVerify::Finished(Err(CommitVerifyError::BadSetId)); |
76 | 0 | } |
77 | 0 |
|
78 | 0 | if decoded_commit.auth_data.len() != decoded_commit.precommits.len() { |
79 | 0 | return CommitVerify::Finished(Err(CommitVerifyError::InvalidFormat)); |
80 | 0 | } |
81 | 0 |
|
82 | 0 | let mut randomness = ChaCha20Rng::from_seed(config.randomness_seed); |
83 | 0 |
|
84 | 0 | // Make sure that there is no duplicate authority public key. |
85 | 0 | { |
86 | 0 | let mut unique = hashbrown::HashSet::with_capacity_and_hasher( |
87 | 0 | decoded_commit.auth_data.len(), |
88 | 0 | crate::util::SipHasherBuild::new({ |
89 | 0 | let mut seed = [0; 16]; |
90 | 0 | randomness.fill_bytes(&mut seed); |
91 | 0 | seed |
92 | 0 | }), |
93 | 0 | ); |
94 | 0 | if let Some((_, faulty_pub_key)) = decoded_commit |
95 | 0 | .auth_data |
96 | 0 | .iter() |
97 | 0 | .find(|(_, pubkey)| !unique.insert(pubkey)) Unexecuted instantiation: _RNCINvNtNtCsN16ciHI6Qf_7smoldot8finality6verify13verify_commitpE0B8_ Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot8finality6verify13verify_commitRShE0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot8finality6verify13verify_commitpE0B8_ Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot8finality6verify13verify_commitRShE0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot8finality6verify13verify_commitRShE0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot8finality6verify13verify_commitRShE0CsibGXYHQB8Ea_25json_rpc_general_requests |
98 | | { |
99 | 0 | return CommitVerify::Finished(Err(CommitVerifyError::DuplicateSignature( |
100 | 0 | **faulty_pub_key, |
101 | 0 | ))); |
102 | 0 | } |
103 | 0 | } |
104 | 0 |
|
105 | 0 | CommitVerification { |
106 | 0 | commit: config.commit, |
107 | 0 | block_number_bytes: config.block_number_bytes, |
108 | 0 | next_precommit_index: 0, |
109 | 0 | next_precommit_author_verified: false, |
110 | 0 | next_precommit_block_verified: false, |
111 | 0 | num_verified_signatures: 0, |
112 | 0 | num_authorities: config.num_authorities, |
113 | 0 | signatures_batch: ed25519_zebra::batch::Verifier::new(), |
114 | 0 | randomness, |
115 | 0 | } |
116 | 0 | .resume() |
117 | 0 | } Unexecuted instantiation: _RINvNtNtCsN16ciHI6Qf_7smoldot8finality6verify13verify_commitpEB6_ Unexecuted instantiation: _RINvNtNtCseuYC0Zibziv_7smoldot8finality6verify13verify_commitRShECsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RINvNtNtCseuYC0Zibziv_7smoldot8finality6verify13verify_commitpEB6_ Unexecuted instantiation: _RINvNtNtCseuYC0Zibziv_7smoldot8finality6verify13verify_commitRShECsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RINvNtNtCseuYC0Zibziv_7smoldot8finality6verify13verify_commitRShECscDgN54JpMGG_6author Unexecuted instantiation: _RINvNtNtCseuYC0Zibziv_7smoldot8finality6verify13verify_commitRShECsibGXYHQB8Ea_25json_rpc_general_requests |
118 | | |
119 | | /// Must return whether a certain public key is in the list of authorities that are allowed to |
120 | | /// generate pre-commits. |
121 | | #[must_use] |
122 | | pub struct CommitVerifyIsAuthority<C> { |
123 | | inner: CommitVerification<C>, |
124 | | } |
125 | | |
126 | | impl<C: AsRef<[u8]>> CommitVerifyIsAuthority<C> { |
127 | | /// Public key to verify. |
128 | 0 | pub fn authority_public_key(&self) -> &[u8; 32] { |
129 | 0 | debug_assert!(!self.inner.next_precommit_author_verified); |
130 | 0 | let decoded_commit = decode::decode_grandpa_commit( |
131 | 0 | self.inner.commit.as_ref(), |
132 | 0 | self.inner.block_number_bytes, |
133 | 0 | ) |
134 | 0 | .unwrap(); |
135 | 0 | decoded_commit.auth_data[self.inner.next_precommit_index].1 |
136 | 0 | } Unexecuted instantiation: _RNvMNtNtCsN16ciHI6Qf_7smoldot8finality6verifyINtB2_23CommitVerifyIsAuthoritypE20authority_public_keyB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB2_23CommitVerifyIsAuthorityRShE20authority_public_keyCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB2_23CommitVerifyIsAuthoritypE20authority_public_keyB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB2_23CommitVerifyIsAuthorityRShE20authority_public_keyCsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB2_23CommitVerifyIsAuthorityRShE20authority_public_keyCscDgN54JpMGG_6author Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB2_23CommitVerifyIsAuthorityRShE20authority_public_keyCsibGXYHQB8Ea_25json_rpc_general_requests |
137 | | |
138 | | /// Resumes the verification process. |
139 | | /// |
140 | | /// Must be passed `true` if the public key is indeed in the list of authorities. |
141 | | /// Passing `false` always returns [`CommitVerify::Finished`] containing an error. |
142 | 0 | pub fn resume(mut self, is_authority: bool) -> CommitVerify<C> { |
143 | 0 | if !is_authority { |
144 | 0 | let key = *self.authority_public_key(); |
145 | 0 | return CommitVerify::Finished(Err(CommitVerifyError::NotAuthority(key))); |
146 | 0 | } |
147 | 0 |
|
148 | 0 | self.inner.next_precommit_author_verified = true; |
149 | 0 | self.inner.resume() |
150 | 0 | } Unexecuted instantiation: _RNvMNtNtCsN16ciHI6Qf_7smoldot8finality6verifyINtB2_23CommitVerifyIsAuthoritypE6resumeB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB2_23CommitVerifyIsAuthorityRShE6resumeCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB2_23CommitVerifyIsAuthoritypE6resumeB6_ Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB2_23CommitVerifyIsAuthorityRShE6resumeCsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB2_23CommitVerifyIsAuthorityRShE6resumeCscDgN54JpMGG_6author Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB2_23CommitVerifyIsAuthorityRShE6resumeCsibGXYHQB8Ea_25json_rpc_general_requests |
151 | | } |
152 | | |
153 | | /// Must return whether a certain block is a descendant of the target block. |
154 | | #[must_use] |
155 | | pub struct CommitVerifyIsParent<C> { |
156 | | inner: CommitVerification<C>, |
157 | | /// For performance reasons, the block number is copied here, but not the block hash. This |
158 | | /// hasn't actually been benchmarked, so feel free to do so. |
159 | | block_number: u64, |
160 | | } |
161 | | |
162 | | impl<C: AsRef<[u8]>> CommitVerifyIsParent<C> { |
163 | | /// Height of the block to check. |
164 | 0 | pub fn block_number(&self) -> u64 { |
165 | 0 | self.block_number |
166 | 0 | } Unexecuted instantiation: _RNvMs_NtNtCsN16ciHI6Qf_7smoldot8finality6verifyINtB4_20CommitVerifyIsParentpE12block_numberB8_ Unexecuted instantiation: _RNvMs_NtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB4_20CommitVerifyIsParentpE12block_numberB8_ |
167 | | |
168 | | /// Hash of the block to check. |
169 | 0 | pub fn block_hash(&self) -> &[u8; 32] { |
170 | 0 | debug_assert!(!self.inner.next_precommit_block_verified); |
171 | 0 | let decoded_commit = decode::decode_grandpa_commit( |
172 | 0 | self.inner.commit.as_ref(), |
173 | 0 | self.inner.block_number_bytes, |
174 | 0 | ) |
175 | 0 | .unwrap(); |
176 | 0 | decoded_commit.precommits[self.inner.next_precommit_index].target_hash |
177 | 0 | } Unexecuted instantiation: _RNvMs_NtNtCsN16ciHI6Qf_7smoldot8finality6verifyINtB4_20CommitVerifyIsParentpE10block_hashB8_ Unexecuted instantiation: _RNvMs_NtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB4_20CommitVerifyIsParentRShE10block_hashCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMs_NtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB4_20CommitVerifyIsParentpE10block_hashB8_ Unexecuted instantiation: _RNvMs_NtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB4_20CommitVerifyIsParentRShE10block_hashCsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNvMs_NtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB4_20CommitVerifyIsParentRShE10block_hashCscDgN54JpMGG_6author Unexecuted instantiation: _RNvMs_NtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB4_20CommitVerifyIsParentRShE10block_hashCsibGXYHQB8Ea_25json_rpc_general_requests |
178 | | |
179 | | /// Height of the block that must be the ancestor of the block to check. |
180 | 0 | pub fn target_block_number(&self) -> u64 { |
181 | 0 | let decoded_commit = decode::decode_grandpa_commit( |
182 | 0 | self.inner.commit.as_ref(), |
183 | 0 | self.inner.block_number_bytes, |
184 | 0 | ) |
185 | 0 | .unwrap(); |
186 | 0 | decoded_commit.target_number |
187 | 0 | } Unexecuted instantiation: _RNvMs_NtNtCsN16ciHI6Qf_7smoldot8finality6verifyINtB4_20CommitVerifyIsParentpE19target_block_numberB8_ Unexecuted instantiation: _RNvMs_NtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB4_20CommitVerifyIsParentpE19target_block_numberB8_ |
188 | | |
189 | | /// Hash of the block that must be the ancestor of the block to check. |
190 | 0 | pub fn target_block_hash(&self) -> &[u8; 32] { |
191 | 0 | let decoded_commit = decode::decode_grandpa_commit( |
192 | 0 | self.inner.commit.as_ref(), |
193 | 0 | self.inner.block_number_bytes, |
194 | 0 | ) |
195 | 0 | .unwrap(); |
196 | 0 | decoded_commit.target_hash |
197 | 0 | } Unexecuted instantiation: _RNvMs_NtNtCsN16ciHI6Qf_7smoldot8finality6verifyINtB4_20CommitVerifyIsParentpE17target_block_hashB8_ Unexecuted instantiation: _RNvMs_NtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB4_20CommitVerifyIsParentpE17target_block_hashB8_ |
198 | | |
199 | | /// Resumes the verification process. |
200 | | /// |
201 | | /// Must be passed `Some(true)` if the block is known to be a descendant of the target block, |
202 | | /// or `None` if it is unknown. |
203 | | /// Passing `Some(false)` always returns [`CommitVerify::Finished`] containing an |
204 | | /// error. |
205 | 0 | pub fn resume(mut self, is_parent: Option<bool>) -> CommitVerify<C> { |
206 | 0 | match is_parent { |
207 | 0 | None => {} |
208 | 0 | Some(true) => self.inner.num_verified_signatures += 1, |
209 | | Some(false) => { |
210 | 0 | return CommitVerify::Finished(Err(CommitVerifyError::BadAncestry)); |
211 | | } |
212 | | } |
213 | | |
214 | 0 | self.inner.next_precommit_block_verified = true; |
215 | 0 | self.inner.resume() |
216 | 0 | } Unexecuted instantiation: _RNvMs_NtNtCsN16ciHI6Qf_7smoldot8finality6verifyINtB4_20CommitVerifyIsParentpE6resumeB8_ Unexecuted instantiation: _RNvMs_NtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB4_20CommitVerifyIsParentRShE6resumeCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMs_NtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB4_20CommitVerifyIsParentpE6resumeB8_ Unexecuted instantiation: _RNvMs_NtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB4_20CommitVerifyIsParentRShE6resumeCsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNvMs_NtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB4_20CommitVerifyIsParentRShE6resumeCscDgN54JpMGG_6author Unexecuted instantiation: _RNvMs_NtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB4_20CommitVerifyIsParentRShE6resumeCsibGXYHQB8Ea_25json_rpc_general_requests |
217 | | } |
218 | | |
219 | | struct CommitVerification<C> { |
220 | | /// Encoded commit message. Guaranteed to decode successfully. |
221 | | commit: C, |
222 | | |
223 | | /// See [`CommitVerifyConfig::block_number_bytes`]. |
224 | | block_number_bytes: usize, |
225 | | |
226 | | /// Index of the next pre-commit to process within the commit. |
227 | | next_precommit_index: usize, |
228 | | |
229 | | /// Whether the precommit whose index is [`CommitVerification::next_precommit_index`] has been |
230 | | /// verified as coming from the list of authorities. |
231 | | next_precommit_author_verified: bool, |
232 | | |
233 | | /// Whether the precommit whose index is [`CommitVerification::next_precommit_index`] has been |
234 | | /// verified to be about a block that is a descendant of the target block. |
235 | | next_precommit_block_verified: bool, |
236 | | |
237 | | /// Number of signatures that have been pushed for verification. Needs to be above a certain |
238 | | /// threshold for the commit to be valid. |
239 | | num_verified_signatures: usize, |
240 | | |
241 | | /// Number of authorities in the list. Used to calculate the threshold of the number of |
242 | | /// required signatures. |
243 | | num_authorities: u32, |
244 | | |
245 | | /// Verifying all the signatures together brings better performances than verifying them one |
246 | | /// by one. |
247 | | /// Note that batched Ed25519 verification has some issues. The code below uses a special |
248 | | /// flavor of Ed25519 where ambiguities are removed. |
249 | | /// See <https://docs.rs/ed25519-zebra/2.2.0/ed25519_zebra/batch/index.html> and |
250 | | /// <https://github.com/zcash/zips/blob/master/zip-0215.rst> |
251 | | signatures_batch: ed25519_zebra::batch::Verifier, |
252 | | |
253 | | /// Randomness generator used during the batch verification. |
254 | | randomness: ChaCha20Rng, |
255 | | } |
256 | | |
257 | | impl<C: AsRef<[u8]>> CommitVerification<C> { |
258 | 0 | fn resume(mut self) -> CommitVerify<C> { |
259 | 0 | // The `verify` function that starts the verification performs the preliminary check that |
260 | 0 | // the commit has the correct format. |
261 | 0 | let decoded_commit = |
262 | 0 | decode::decode_grandpa_commit(self.commit.as_ref(), self.block_number_bytes).unwrap(); |
263 | | |
264 | | loop { |
265 | 0 | if let Some(precommit) = decoded_commit.precommits.get(self.next_precommit_index) { |
266 | 0 | if !self.next_precommit_author_verified { |
267 | 0 | return CommitVerify::IsAuthority(CommitVerifyIsAuthority { inner: self }); |
268 | 0 | } |
269 | 0 |
|
270 | 0 | if !self.next_precommit_block_verified { |
271 | 0 | if precommit.target_hash == decoded_commit.target_hash |
272 | 0 | && precommit.target_number == decoded_commit.target_number |
273 | 0 | { |
274 | 0 | self.next_precommit_block_verified = true; |
275 | 0 | } else { |
276 | 0 | return CommitVerify::IsParent(CommitVerifyIsParent { |
277 | 0 | block_number: precommit.target_number, |
278 | 0 | inner: self, |
279 | 0 | }); |
280 | | } |
281 | 0 | } |
282 | | |
283 | 0 | let authority_public_key = decoded_commit.auth_data[self.next_precommit_index].1; |
284 | 0 | let signature = decoded_commit.auth_data[self.next_precommit_index].0; |
285 | 0 |
|
286 | 0 | let mut msg = Vec::with_capacity(1 + 32 + self.block_number_bytes + 8 + 8); |
287 | 0 | msg.push(1u8); // This `1` indicates which kind of message is being signed. |
288 | 0 | msg.extend_from_slice(&precommit.target_hash[..]); |
289 | 0 | // The message contains the little endian block number. While simple in concept, |
290 | 0 | // in reality it is more complicated because we don't know the number of bytes of |
291 | 0 | // this block number at compile time. We thus copy as many bytes as appropriate and |
292 | 0 | // pad with 0s if necessary. |
293 | 0 | msg.extend_from_slice( |
294 | 0 | &precommit.target_number.to_le_bytes()[..cmp::min( |
295 | 0 | mem::size_of_val(&precommit.target_number), |
296 | 0 | self.block_number_bytes, |
297 | 0 | )], |
298 | 0 | ); |
299 | 0 | msg.extend( |
300 | 0 | iter::repeat(0).take( |
301 | 0 | self.block_number_bytes |
302 | 0 | .saturating_sub(mem::size_of_val(&precommit.target_number)), |
303 | 0 | ), |
304 | 0 | ); |
305 | 0 | msg.extend_from_slice(&u64::to_le_bytes(decoded_commit.round_number)[..]); |
306 | 0 | msg.extend_from_slice(&u64::to_le_bytes(decoded_commit.set_id)[..]); |
307 | 0 | debug_assert_eq!(msg.len(), msg.capacity()); |
308 | | |
309 | 0 | self.signatures_batch |
310 | 0 | .queue(ed25519_zebra::batch::Item::from(( |
311 | 0 | ed25519_zebra::VerificationKeyBytes::from(*authority_public_key), |
312 | 0 | ed25519_zebra::Signature::from(*signature), |
313 | 0 | &msg, |
314 | 0 | ))); |
315 | 0 |
|
316 | 0 | self.next_precommit_index += 1; |
317 | 0 | self.next_precommit_author_verified = false; |
318 | 0 | self.next_precommit_block_verified = false; |
319 | | } else { |
320 | 0 | debug_assert!(!self.next_precommit_author_verified); |
321 | 0 | debug_assert!(!self.next_precommit_block_verified); |
322 | | |
323 | | // Check that commit contains a number of signatures equal to at least 2/3rd of the |
324 | | // number of authorities. |
325 | | // Duplicate signatures are checked below. |
326 | | // The logic of the check is `actual >= (expected * 2 / 3) + 1`. |
327 | 0 | if decoded_commit.precommits.len() |
328 | 0 | < (usize::try_from(self.num_authorities).unwrap() * 2 / 3) + 1 |
329 | | { |
330 | 0 | return CommitVerify::FinishedUnknown; |
331 | 0 | } |
332 | 0 |
|
333 | 0 | // Actual signatures verification performed here. |
334 | 0 | match self.signatures_batch.verify(&mut self.randomness) { |
335 | 0 | Ok(()) => {} |
336 | 0 | Err(_) => return CommitVerify::Finished(Err(CommitVerifyError::BadSignature)), |
337 | | } |
338 | | |
339 | 0 | return CommitVerify::Finished(Ok(())); |
340 | | } |
341 | | } |
342 | 0 | } Unexecuted instantiation: _RNvMs0_NtNtCsN16ciHI6Qf_7smoldot8finality6verifyINtB5_18CommitVerificationpE6resumeB9_ Unexecuted instantiation: _RNvMs0_NtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB5_18CommitVerificationRShE6resumeCsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNvMs0_NtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB5_18CommitVerificationpE6resumeB9_ Unexecuted instantiation: _RNvMs0_NtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB5_18CommitVerificationRShE6resumeCsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNvMs0_NtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB5_18CommitVerificationRShE6resumeCscDgN54JpMGG_6author Unexecuted instantiation: _RNvMs0_NtNtCseuYC0Zibziv_7smoldot8finality6verifyINtB5_18CommitVerificationRShE6resumeCsibGXYHQB8Ea_25json_rpc_general_requests |
343 | | } |
344 | | |
345 | | /// Error that can happen while verifying a commit. |
346 | 0 | #[derive(Debug, derive_more::Display)] Unexecuted instantiation: _RNvXs3_NtNtCsN16ciHI6Qf_7smoldot8finality6verifyNtB5_17CommitVerifyErrorNtNtCsaYZPK01V26L_4core3fmt7Display3fmt Unexecuted instantiation: _RNvXs3_NtNtCseuYC0Zibziv_7smoldot8finality6verifyNtB5_17CommitVerifyErrorNtNtCsaYZPK01V26L_4core3fmt7Display3fmt |
347 | | pub enum CommitVerifyError { |
348 | | /// Failed to decode the commit message. |
349 | | InvalidFormat, |
350 | | /// The authorities set id of the commit doesn't match the one that is expected. |
351 | | BadSetId, |
352 | | /// One of the public keys is invalid. |
353 | | BadPublicKey, |
354 | | /// One of the signatures can't be verified. |
355 | | BadSignature, |
356 | | /// One authority has produced two signatures. |
357 | | #[display(fmt = "One authority has produced two signatures")] |
358 | | DuplicateSignature([u8; 32]), |
359 | | /// One of the public keys isn't in the list of authorities. |
360 | | #[display(fmt = "One of the public keys isn't in the list of authorities")] |
361 | | NotAuthority([u8; 32]), |
362 | | /// Commit contains a vote for a block that isn't a descendant of the target block. |
363 | | BadAncestry, |
364 | | } |
365 | | |
366 | | // TODO: tests |
367 | | |
368 | | /// Configuration for a justification verification process. |
369 | | #[derive(Debug)] |
370 | | pub struct JustificationVerifyConfig<J, I> { |
371 | | /// Justification to verify. |
372 | | pub justification: J, |
373 | | |
374 | | pub block_number_bytes: usize, |
375 | | |
376 | | // TODO: document |
377 | | pub authorities_set_id: u64, |
378 | | |
379 | | /// List of authorities that are allowed to emit pre-commits for the block referred to by |
380 | | /// the justification. Must implement `Iterator<Item = &[u8]>`, where each item is |
381 | | /// the public key of an authority. |
382 | | pub authorities_list: I, |
383 | | |
384 | | /// Seed for a PRNG used for various purposes during the verification. |
385 | | /// |
386 | | /// > **Note**: The verification is nonetheless deterministic. |
387 | | pub randomness_seed: [u8; 32], |
388 | | } |
389 | | |
390 | | /// Verifies that a justification is valid. |
391 | 0 | pub fn verify_justification<'a>( |
392 | 0 | config: JustificationVerifyConfig<impl AsRef<[u8]>, impl Iterator<Item = &'a [u8]>>, |
393 | 0 | ) -> Result<(), JustificationVerifyError> { |
394 | 0 | let decoded_justification = match decode::decode_grandpa_justification( |
395 | 0 | config.justification.as_ref(), |
396 | 0 | config.block_number_bytes, |
397 | 0 | ) { |
398 | 0 | Ok(c) => c, |
399 | 0 | Err(_) => return Err(JustificationVerifyError::InvalidFormat), |
400 | | }; |
401 | | |
402 | 0 | let num_precommits = decoded_justification.precommits.iter().count(); |
403 | 0 |
|
404 | 0 | let mut randomness = ChaCha20Rng::from_seed(config.randomness_seed); |
405 | | |
406 | | // Collect the authorities in a set in order to be able to determine with a low complexity |
407 | | // whether a public key is an authority. |
408 | | // For each authority, contains a boolean indicating whether the authority has been seen |
409 | | // before in the list of pre-commits. |
410 | 0 | let mut authorities_list = { |
411 | 0 | let mut list = hashbrown::HashMap::<&[u8], _, _>::with_capacity_and_hasher( |
412 | 0 | 0, |
413 | 0 | crate::util::SipHasherBuild::new({ |
414 | 0 | let mut seed = [0; 16]; |
415 | 0 | randomness.fill_bytes(&mut seed); |
416 | 0 | seed |
417 | 0 | }), |
418 | 0 | ); |
419 | 0 | for authority in config.authorities_list { |
420 | 0 | list.insert(authority, false); |
421 | 0 | } |
422 | 0 | list |
423 | 0 | }; |
424 | 0 |
|
425 | 0 | // Check that justification contains a number of signatures equal to at least 2/3rd of the |
426 | 0 | // number of authorities. |
427 | 0 | // Duplicate signatures are checked below. |
428 | 0 | // The logic of the check is `actual >= (expected * 2 / 3) + 1`. |
429 | 0 | if num_precommits < (authorities_list.len() * 2 / 3) + 1 { |
430 | 0 | return Err(JustificationVerifyError::NotEnoughSignatures); |
431 | 0 | } |
432 | 0 |
|
433 | 0 | // Verifying all the signatures together brings better performances than verifying them one |
434 | 0 | // by one. |
435 | 0 | // Note that batched ed25519 verification has some issues. The code below uses a special |
436 | 0 | // flavour of ed25519 where ambiguities are removed. |
437 | 0 | // See https://docs.rs/ed25519-zebra/2.2.0/ed25519_zebra/batch/index.html and |
438 | 0 | // https://github.com/zcash/zips/blob/master/zip-0215.rst |
439 | 0 | let mut batch = ed25519_zebra::batch::Verifier::new(); |
440 | | |
441 | 0 | for precommit in decoded_justification.precommits.iter() { |
442 | 0 | match authorities_list.entry(precommit.authority_public_key) { |
443 | 0 | hashbrown::hash_map::Entry::Occupied(mut entry) => { |
444 | 0 | if entry.insert(true) { |
445 | 0 | return Err(JustificationVerifyError::DuplicateSignature( |
446 | 0 | *precommit.authority_public_key, |
447 | 0 | )); |
448 | 0 | } |
449 | | } |
450 | | hashbrown::hash_map::Entry::Vacant(_) => { |
451 | 0 | return Err(JustificationVerifyError::NotAuthority( |
452 | 0 | *precommit.authority_public_key, |
453 | 0 | )) |
454 | | } |
455 | | } |
456 | | |
457 | | // TODO: must check signed block ancestry using `votes_ancestries` |
458 | | |
459 | 0 | let mut msg = Vec::with_capacity(1 + 32 + 4 + 8 + 8); |
460 | 0 | msg.push(1u8); // This `1` indicates which kind of message is being signed. |
461 | 0 | msg.extend_from_slice(&precommit.target_hash[..]); |
462 | 0 | // The message contains the little endian block number. While simple in concept, |
463 | 0 | // in reality it is more complicated because we don't know the number of bytes of |
464 | 0 | // this block number at compile time. We thus copy as many bytes as appropriate and |
465 | 0 | // pad with 0s if necessary. |
466 | 0 | msg.extend_from_slice( |
467 | 0 | &precommit.target_number.to_le_bytes()[..cmp::min( |
468 | 0 | mem::size_of_val(&precommit.target_number), |
469 | 0 | config.block_number_bytes, |
470 | 0 | )], |
471 | 0 | ); |
472 | 0 | msg.extend( |
473 | 0 | iter::repeat(0).take( |
474 | 0 | config |
475 | 0 | .block_number_bytes |
476 | 0 | .saturating_sub(mem::size_of_val(&precommit.target_number)), |
477 | 0 | ), |
478 | 0 | ); |
479 | 0 | msg.extend_from_slice(&u64::to_le_bytes(decoded_justification.round)[..]); |
480 | 0 | msg.extend_from_slice(&u64::to_le_bytes(config.authorities_set_id)[..]); |
481 | 0 | debug_assert_eq!(msg.len(), msg.capacity()); |
482 | | |
483 | 0 | batch.queue(ed25519_zebra::batch::Item::from(( |
484 | 0 | ed25519_zebra::VerificationKeyBytes::from(*precommit.authority_public_key), |
485 | 0 | ed25519_zebra::Signature::from(*precommit.signature), |
486 | 0 | &msg, |
487 | 0 | ))); |
488 | | } |
489 | | |
490 | | // Actual signatures verification performed here. |
491 | 0 | batch |
492 | 0 | .verify(&mut randomness) |
493 | 0 | .map_err(|_| JustificationVerifyError::BadSignature)?; Unexecuted instantiation: _RNCINvNtNtCsN16ciHI6Qf_7smoldot8finality6verify20verify_justificationppE0B8_ Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot8finality6verify20verify_justificationRINtNtCsdZExvAaxgia_5alloc3vec3VechEINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtB1P_5slice4iter4IterNtNtNtB8_6header7grandpa16GrandpaAuthorityENCNvMs4_NtNtB8_4sync9warp_syncINtB3K_22VerifyWarpSyncFragmentNtNtB3M_3all19WarpSyncSourceExtraNtB4D_20WarpSyncRequestExtraE6verifys0_0EE0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot8finality6verify20verify_justificationRShINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtB1i_5slice4iter4IterNtNtNtB8_6header7grandpa16GrandpaAuthorityENCNvMNtNtNtB8_5chain11blocks_tree8finalityINtB3c_16NonFinalizedTreeINtNtB1i_6option6OptionuEE29verify_grandpa_finality_inners0_0EE0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot8finality6verify20verify_justificationppE0B8_ Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot8finality6verify20verify_justificationRINtNtCsdZExvAaxgia_5alloc3vec3VechEINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtB1P_5slice4iter4IterNtNtNtB8_6header7grandpa16GrandpaAuthorityENCNvMs4_NtNtB8_4sync9warp_syncINtB3K_22VerifyWarpSyncFragmentNtNtB3M_3all19WarpSyncSourceExtraNtB4D_20WarpSyncRequestExtraE6verifys0_0EE0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot8finality6verify20verify_justificationRShINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtB1i_5slice4iter4IterNtNtNtB8_6header7grandpa16GrandpaAuthorityENCNvMNtNtNtB8_5chain11blocks_tree8finalityINtB3c_16NonFinalizedTreeINtNtB1i_6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEE29verify_grandpa_finality_inners0_0EE0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot8finality6verify20verify_justificationRINtNtCsdZExvAaxgia_5alloc3vec3VechEINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtB1P_5slice4iter4IterNtNtNtB8_6header7grandpa16GrandpaAuthorityENCNvMs4_NtNtB8_4sync9warp_syncINtB3K_22VerifyWarpSyncFragmentNtNtB3M_3all19WarpSyncSourceExtraNtB4D_20WarpSyncRequestExtraE6verifys0_0EE0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot8finality6verify20verify_justificationRShINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtB1i_5slice4iter4IterNtNtNtB8_6header7grandpa16GrandpaAuthorityENCNvMNtNtNtB8_5chain11blocks_tree8finalityINtB3c_16NonFinalizedTreeINtNtB1i_6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEE29verify_grandpa_finality_inners0_0EE0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot8finality6verify20verify_justificationRINtNtCsdZExvAaxgia_5alloc3vec3VechEINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtB1P_5slice4iter4IterNtNtNtB8_6header7grandpa16GrandpaAuthorityENCNvMs4_NtNtB8_4sync9warp_syncINtB3K_22VerifyWarpSyncFragmentNtNtB3M_3all19WarpSyncSourceExtraNtB4D_20WarpSyncRequestExtraE6verifys0_0EE0CsibGXYHQB8Ea_25json_rpc_general_requests Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot8finality6verify20verify_justificationRShINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtB1i_5slice4iter4IterNtNtNtB8_6header7grandpa16GrandpaAuthorityENCNvMNtNtNtB8_5chain11blocks_tree8finalityINtB3c_16NonFinalizedTreeINtNtB1i_6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEE29verify_grandpa_finality_inners0_0EE0CsibGXYHQB8Ea_25json_rpc_general_requests |
494 | | |
495 | | // TODO: must check that votes_ancestries doesn't contain any unused entry |
496 | | // TODO: there's also a "ghost" thing? |
497 | | |
498 | 0 | Ok(()) |
499 | 0 | } Unexecuted instantiation: _RINvNtNtCsN16ciHI6Qf_7smoldot8finality6verify20verify_justificationppEB6_ Unexecuted instantiation: _RINvNtNtCseuYC0Zibziv_7smoldot8finality6verify20verify_justificationRINtNtCsdZExvAaxgia_5alloc3vec3VechEINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtB1N_5slice4iter4IterNtNtNtB6_6header7grandpa16GrandpaAuthorityENCNvMs4_NtNtB6_4sync9warp_syncINtB3I_22VerifyWarpSyncFragmentNtNtB3K_3all19WarpSyncSourceExtraNtB4B_20WarpSyncRequestExtraE6verifys0_0EECsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RINvNtNtCseuYC0Zibziv_7smoldot8finality6verify20verify_justificationRShINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtB1g_5slice4iter4IterNtNtNtB6_6header7grandpa16GrandpaAuthorityENCNvMNtNtNtB6_5chain11blocks_tree8finalityINtB3a_16NonFinalizedTreeINtNtB1g_6option6OptionuEE29verify_grandpa_finality_inners0_0EECsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RINvNtNtCseuYC0Zibziv_7smoldot8finality6verify20verify_justificationppEB6_ Unexecuted instantiation: _RINvNtNtCseuYC0Zibziv_7smoldot8finality6verify20verify_justificationRINtNtCsdZExvAaxgia_5alloc3vec3VechEINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtB1N_5slice4iter4IterNtNtNtB6_6header7grandpa16GrandpaAuthorityENCNvMs4_NtNtB6_4sync9warp_syncINtB3I_22VerifyWarpSyncFragmentNtNtB3K_3all19WarpSyncSourceExtraNtB4B_20WarpSyncRequestExtraE6verifys0_0EECsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RINvNtNtCseuYC0Zibziv_7smoldot8finality6verify20verify_justificationRShINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtB1g_5slice4iter4IterNtNtNtB6_6header7grandpa16GrandpaAuthorityENCNvMNtNtNtB6_5chain11blocks_tree8finalityINtB3a_16NonFinalizedTreeINtNtB1g_6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEE29verify_grandpa_finality_inners0_0EECsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RINvNtNtCseuYC0Zibziv_7smoldot8finality6verify20verify_justificationRINtNtCsdZExvAaxgia_5alloc3vec3VechEINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtB1N_5slice4iter4IterNtNtNtB6_6header7grandpa16GrandpaAuthorityENCNvMs4_NtNtB6_4sync9warp_syncINtB3I_22VerifyWarpSyncFragmentNtNtB3K_3all19WarpSyncSourceExtraNtB4B_20WarpSyncRequestExtraE6verifys0_0EECscDgN54JpMGG_6author Unexecuted instantiation: _RINvNtNtCseuYC0Zibziv_7smoldot8finality6verify20verify_justificationRShINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtB1g_5slice4iter4IterNtNtNtB6_6header7grandpa16GrandpaAuthorityENCNvMNtNtNtB6_5chain11blocks_tree8finalityINtB3a_16NonFinalizedTreeINtNtB1g_6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEE29verify_grandpa_finality_inners0_0EECscDgN54JpMGG_6author Unexecuted instantiation: _RINvNtNtCseuYC0Zibziv_7smoldot8finality6verify20verify_justificationRINtNtCsdZExvAaxgia_5alloc3vec3VechEINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtB1N_5slice4iter4IterNtNtNtB6_6header7grandpa16GrandpaAuthorityENCNvMs4_NtNtB6_4sync9warp_syncINtB3I_22VerifyWarpSyncFragmentNtNtB3K_3all19WarpSyncSourceExtraNtB4B_20WarpSyncRequestExtraE6verifys0_0EECsibGXYHQB8Ea_25json_rpc_general_requests Unexecuted instantiation: _RINvNtNtCseuYC0Zibziv_7smoldot8finality6verify20verify_justificationRShINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtB1g_5slice4iter4IterNtNtNtB6_6header7grandpa16GrandpaAuthorityENCNvMNtNtNtB6_5chain11blocks_tree8finalityINtB3a_16NonFinalizedTreeINtNtB1g_6option6OptionNtNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service17NonFinalizedBlockEE29verify_grandpa_finality_inners0_0EECsibGXYHQB8Ea_25json_rpc_general_requests |
500 | | |
501 | | /// Error that can happen while verifying a justification. |
502 | 0 | #[derive(Debug, derive_more::Display)] Unexecuted instantiation: _RNvXs6_NtNtCsN16ciHI6Qf_7smoldot8finality6verifyNtB5_24JustificationVerifyErrorNtNtCsaYZPK01V26L_4core3fmt7Display3fmt Unexecuted instantiation: _RNvXs6_NtNtCseuYC0Zibziv_7smoldot8finality6verifyNtB5_24JustificationVerifyErrorNtNtCsaYZPK01V26L_4core3fmt7Display3fmt |
503 | | pub enum JustificationVerifyError { |
504 | | /// Failed to decode the justification. |
505 | | InvalidFormat, |
506 | | /// One of the public keys is invalid. |
507 | | BadPublicKey, |
508 | | /// One of the signatures can't be verified. |
509 | | BadSignature, |
510 | | /// One authority has produced two signatures. |
511 | | #[display(fmt = "One authority has produced two signatures")] |
512 | | DuplicateSignature([u8; 32]), |
513 | | /// One of the public keys isn't in the list of authorities. |
514 | | #[display(fmt = "One of the public keys isn't in the list of authorities")] |
515 | | NotAuthority([u8; 32]), |
516 | | /// Justification doesn't contain enough authorities signatures to be valid. |
517 | | NotEnoughSignatures, |
518 | | } |