verify_execution.rs
1 // Copyright (c) 2025 ADnet Contributors 2 // This file is part of the AlphaVM library. 3 4 // Licensed under the Apache License, Version 2.0 (the "License"); 5 // you may not use this file except in compliance with the License. 6 // You may obtain a copy of the License at: 7 8 // http://www.apache.org/licenses/LICENSE-2.0 9 10 // Unless required by applicable law or agreed to in writing, software 11 // distributed under the License is distributed on an "AS IS" BASIS, 12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 // See the License for the specific language governing permissions and 14 // limitations under the License. 15 16 use super::*; 17 18 impl<N: Network> Process<N> { 19 /// Verifies the given execution is valid. 20 /// Note: This does *not* check that the global state root exists in the ledger. 21 #[inline] 22 pub fn verify_execution( 23 &self, 24 consensus_version: ConsensusVersion, 25 varuna_version: VarunaVersion, 26 inclusion_version: InclusionVersion, 27 execution: &Execution<N>, 28 ) -> Result<()> { 29 let timer = timer!("Process::verify_execution"); 30 31 // Ensure the execution contains transitions. 32 ensure!(!execution.is_empty(), "There are no transitions in the execution"); 33 // Ensure that the execution does not exceed the maximum number of transitions. 34 ensure!( 35 execution.len() < Transaction::<N>::MAX_TRANSITIONS, 36 "The number of transitions in an execution must be less than '{}'", 37 Transaction::<N>::MAX_TRANSITIONS 38 ); 39 40 // Determine the function locator and ensure the number of transitions matches the number of calls. 41 let locator = { 42 // Retrieve the transition (without popping it). 43 let transition = execution.peek()?; 44 // Retrieve the stack. 45 let stack = self.get_stack(transition.program_id())?; 46 // Ensure the number of calls matches the number of transitions. 47 let number_of_calls = stack.get_number_of_calls(transition.function_name())?; 48 ensure!( 49 number_of_calls == execution.len(), 50 "The number of transitions in the execution is incorrect. Expected {number_of_calls}, but found {}", 51 execution.len() 52 ); 53 // Output the locator of the main function. 54 Locator::new(*transition.program_id(), *transition.function_name()).to_string() 55 }; 56 lap!(timer, "Verify the number of transitions"); 57 58 // Construct the call graph of the execution. 59 let call_graph = self.construct_call_graph(execution)?; 60 // Construct the reverse call graph of the execution. 61 // Note: This is a mapping of the child transition ID to the parent transition ID. 62 let reverse_call_graph = Self::reverse_call_graph(&call_graph); 63 64 // Initialize a map of verifying keys to public inputs. 65 let mut verifier_inputs = HashMap::new(); 66 67 // Initialize a map of transition IDs to references of the transition. 68 let mut transition_map = HashMap::new(); 69 70 // Verify each transition. 71 for transition in execution.transitions() { 72 dev_println!("Verifying transition for {}/{}...", transition.program_id(), transition.function_name()); 73 // Debug-mode only, as the `Transition` constructor recomputes the transition ID at initialization. 74 debug_assert_eq!( 75 **transition.id(), 76 N::hash_bhp512(&(transition.to_root()?, *transition.tcm()).to_bits_le())?, 77 "The transition ID is incorrect" 78 ); 79 80 // Ensure the transition is not a fee transition. 81 let is_fee_transition = transition.is_fee_private() || transition.is_fee_public(); 82 ensure!(!is_fee_transition, "Fee transitions are not allowed in executions"); 83 // Ensure the number of inputs is within the allowed range. 84 ensure!(transition.inputs().len() <= N::MAX_INPUTS, "Transition exceeded maximum number of inputs"); 85 // Ensure the number of outputs is within the allowed range. 86 ensure!(transition.outputs().len() <= N::MAX_OUTPUTS, "Transition exceeded maximum number of outputs"); 87 88 // Retrieve the network ID. 89 let network_id = U16::new(N::ID); 90 // Compute the function ID. 91 let function_id = compute_function_id(&network_id, transition.program_id(), transition.function_name())?; 92 93 // Ensure each input is valid. 94 if transition 95 .inputs() 96 .iter() 97 .enumerate() 98 .any(|(index, input)| !input.verify(function_id, transition.tcm(), index)) 99 { 100 bail!("Failed to verify a transition input") 101 } 102 lap!(timer, "Verify the inputs"); 103 104 // Ensure each output is valid. 105 let num_inputs = transition.inputs().len(); 106 let num_outputs = transition.outputs().len(); 107 for (index, output) in transition.outputs().iter().enumerate() { 108 // If the consensus version are before `ConsensusVersion::V8`, ensure the output record is on Version 0. 109 // if the consensus version is on or after `ConsensusVersion::V8`, ensure the output record is on Version 1. 110 if let Some((_, record)) = output.record() { 111 if (ConsensusVersion::V1..=ConsensusVersion::V7).contains(&consensus_version) { 112 #[cfg(not(any(test, feature = "test")))] 113 ensure!(record.version().is_zero(), "Output record must be Version 0 before Consensus V8"); 114 #[cfg(any(test, feature = "test"))] 115 ensure!( 116 record.version().is_one(), 117 "Output record must be Version 1 before Consensus V8 in tests." 118 ); 119 } else { 120 ensure!(record.version().is_one(), "Output record must be Version 1 on or after Consensus V8"); 121 } 122 } 123 // Ensure the output is valid. 124 if !output.verify(function_id, transition.tcm(), num_inputs + index) { 125 bail!("Failed to verify a transition output") 126 } 127 } 128 lap!(timer, "Verify the outputs"); 129 130 // Retrieve the stack. 131 let stack = self.get_stack(transition.program_id())?; 132 // Retrieve the function from the stack. 133 let function = stack.get_function(transition.function_name())?; 134 // Retrieve the program checksum, if the program has a constructor. 135 let program_checksum = match stack.program().contains_constructor() { 136 true => Some(stack.program_checksum_as_field()?), 137 false => None, 138 }; 139 140 // Ensure the number of inputs and outputs match the expected number in the function. 141 ensure!(function.inputs().len() == num_inputs, "The number of transition inputs is incorrect"); 142 ensure!(function.outputs().len() == num_outputs, "The number of transition outputs is incorrect"); 143 144 // Ensure the input and output types are equivalent to the ones defined in the function. 145 // We only need to check that the variant type matches because we already check the hashes in 146 // the `Input::verify` and `Output::verify` functions. 147 let transition_input_variants = transition.inputs().iter().map(Input::variant).collect::<Vec<_>>(); 148 let transition_output_variants = transition.outputs().iter().map(Output::variant).collect::<Vec<_>>(); 149 ensure!(function.input_variants() == transition_input_variants, "The input variants do not match"); 150 ensure!(function.output_variants() == transition_output_variants, "The output variants do not match"); 151 152 // Retrieve the parent program ID. 153 // Note: The last transition in the execution does not have a parent, by definition. 154 let parent = reverse_call_graph.get(transition.id()).and_then(|tid| execution.get_program_id(tid)); 155 156 // Construct the verifier inputs for the transition. 157 let inputs = self.to_transition_verifier_inputs( 158 transition, 159 parent, 160 &call_graph, 161 program_checksum.map(|checksum| *checksum), 162 &mut transition_map, 163 )?; 164 lap!(timer, "Constructed the verifier inputs for a transition of {}", function.name()); 165 166 // Save the verifying key and its inputs. 167 verifier_inputs 168 .entry(Locator::new(*stack.program_id(), *function.name())) 169 // Retrieve the verifying key, if it does not already exist. 170 .or_insert((stack.get_verifying_key(function.name())?, vec![])) 171 .1 172 .push(inputs); 173 lap!(timer, "Stored the verifier inputs for a transition of {}", function.name()); 174 175 // Add the transition to the transition map. 176 transition_map.insert(*transition.id(), transition); 177 } 178 179 // Count the number of verifier instances. 180 let num_instances = verifier_inputs.values().map(|(_, inputs)| inputs.len()).sum::<usize>(); 181 // Ensure the number of instances matches the number of transitions. 182 ensure!(num_instances == execution.transitions().len(), "The number of verifier instances is incorrect"); 183 // Ensure the same signer is used for all transitions. 184 execution.transitions().try_fold(None, |signer, transition| { 185 Ok(match signer { 186 None => Some(transition.scm()), 187 Some(signer) => { 188 ensure!(signer == transition.scm(), "The transitions did not use the same signer"); 189 Some(signer) 190 } 191 }) 192 })?; 193 194 // Construct the list of verifier inputs. 195 let verifier_inputs: Vec<_> = verifier_inputs.values().cloned().collect(); 196 // Verify the execution proof. 197 Trace::verify_execution_proof(&locator, varuna_version, inclusion_version, verifier_inputs, execution)?; 198 199 lap!(timer, "Verify the proof"); 200 201 finish!(timer); 202 Ok(()) 203 } 204 } 205 206 impl<N: Network> Process<N> { 207 /// Returns the public inputs to verify the proof for the given transition. 208 fn to_transition_verifier_inputs( 209 &self, 210 transition: &Transition<N>, 211 parent: Option<&ProgramID<N>>, 212 call_graph: &HashMap<N::TransitionID, Vec<N::TransitionID>>, 213 program_checksum: Option<N::Field>, 214 transition_map: &mut HashMap<N::TransitionID, &Transition<N>>, 215 ) -> Result<Vec<N::Field>> { 216 // Compute the x- and y-coordinate of `tpk`. 217 let (tpk_x, tpk_y) = transition.tpk().to_xy_coordinates(); 218 219 // Determine the value of `is_root` and `parent`. 220 let (is_root, parent) = match parent { 221 // If there is a parent, then `is_root` is `0` and `parent` is the parent program ID. 222 Some(program_id) => (Field::<N>::zero(), *program_id), 223 // If there is no parent, then `is_root` is `1` and `parent` is the root program ID. 224 None => (Field::one(), *transition.program_id()), 225 }; 226 227 // Retrieve the address belonging to the parent. 228 let stack = self.get_stack(parent)?; 229 let parent_address = stack.program_address(); 230 231 // Compute the x- and y-coordinate of `parent`. 232 let (parent_x, parent_y) = parent_address.to_xy_coordinates(); 233 234 // [Inputs] Construct the verifier inputs to verify the proof. 235 let mut inputs = vec![N::Field::one()]; 236 // [Inputs] Extend the verifier inputs with the program checksum if it was provided. 237 if let Some(program_checksum) = program_checksum { 238 inputs.push(program_checksum); 239 } 240 // [Inputs] Extend the verifier inputs with the tpk, transition and signer commitments. 241 inputs.extend([*tpk_x, *tpk_y, **transition.tcm(), **transition.scm()]); 242 // [Inputs] Extend the verifier inputs with the input IDs. 243 inputs.extend(transition.inputs().iter().flat_map(|input| input.verifier_inputs())); 244 // [Inputs] Extend the verifier inputs with the public inputs for 'self.caller'. 245 inputs.extend([*is_root, *parent_x, *parent_y]); 246 247 // If there are function calls, append their inputs and outputs. 248 for transition_id in call_graph.get(transition.id()).unwrap() { 249 // Note: This unwrap is safe, as we are processing transitions in post-order, 250 // which implies that all child transition IDs have been added to `transition_map`. 251 let transition: &&Transition<N> = transition_map.get(transition_id).unwrap(); 252 // [Inputs] Extend the verifier inputs with the transition commitment of the external call. 253 inputs.extend([**transition.tcm()]); 254 // [Inputs] Extend the verifier inputs with the input IDs of the external call. 255 inputs.extend(transition.inputs().iter().flat_map(|input| input.verifier_inputs())); 256 // [Inputs] Extend the verifier inputs with the output IDs of the external call. 257 inputs.extend(transition.output_ids().map(|id| **id)); 258 } 259 260 // [Inputs] Extend the verifier inputs with the output IDs. 261 inputs.extend(transition.outputs().iter().flat_map(|output| output.verifier_inputs())); 262 263 dev_println!("Transition public inputs ({} elements): {:#?}", inputs.len(), inputs); 264 Ok(inputs) 265 } 266 } 267 268 impl<N: Network> Process<N> { 269 // A helper function to construct a call graph from an execution. 270 // 271 // The call graph represents a mapping of parent transition IDs to child transition IDs, 272 // in the order that they were called. 273 // 274 // Suppose we have the following call structure. 275 // The functions are invoked in the following order: 276 // "three.alpha/a" 277 // --> "two.alpha/b" 278 // --> "zero.alpha/c" 279 // --> "zero.alpha/c" 280 // --> "one.alpha/d" 281 // --> "zero.alpha/c" 282 // The order of the transitions in the `Execution` is: 283 // - [c, b, c, c, d, a] 284 // However, the `Execution` only provides `Transition`s and not the call graph. 285 // In other words, we do not know which transitions were invoked by which transitions. 286 // Note that transition names are insufficient to reconstruct the call graph, since the same function can be invoked multiple times, in different ways. 287 // 288 // In order to reconstruct the call graph, we: 289 // - Iterate over the call structure in reverse post-order. The ordering is maintained by the `traversal_stack`. 290 // - Process each transition in the `Execution` in reverse, assigning its transition ID to the corresponding function call. 291 pub fn construct_call_graph( 292 &self, 293 execution: &Execution<N>, 294 ) -> Result<HashMap<N::TransitionID, Vec<N::TransitionID>>> { 295 // Metadata for each transition the execution. 296 struct TransitionMetadata<N: Network> { 297 uid: usize, 298 pid: ProgramID<N>, 299 fname: Identifier<N>, 300 tid: Option<N::TransitionID>, 301 children: Option<Vec<usize>>, 302 } 303 304 impl<N: Network> TransitionMetadata<N> { 305 fn new(counter: &mut usize, pid: ProgramID<N>, fname: Identifier<N>, tid: Option<N::TransitionID>) -> Self { 306 let uid = *counter; 307 *counter += 1; 308 Self { uid, pid, fname, tid, children: None } 309 } 310 311 /// Returns 'true' if the subgraph starting from this transition has been fully-indexed. 312 fn is_complete(&self) -> bool { 313 self.tid.is_some() && self.children.is_some() 314 } 315 } 316 317 // A helper function to update the call graph, given transition metadata. 318 let update_call_graph = |metadata: TransitionMetadata<N>, 319 call_graph: &mut HashMap<N::TransitionID, Vec<N::TransitionID>>, 320 uid_to_tid: &mut HashMap<usize, N::TransitionID>| 321 -> Result<()> { 322 // Check that the transition metadata is complete. 323 ensure!(metadata.is_complete(), "Invalid traversal - transition metadata is incomplete"); 324 // Update the call graph. 325 call_graph.insert( 326 metadata.tid.unwrap(), 327 metadata 328 .children // Safe to unwrap, since the metadata is complete. 329 .unwrap() 330 .into_iter() 331 .map(|uid| match uid_to_tid.get(&uid) { 332 Some(tid) => Ok(*tid), 333 None => bail!("Invalid traversal - missing 'tid' for uid '{uid}'"), 334 }) 335 .collect::<Result<Vec<_>, _>>()?, 336 ); 337 // Update the UID to TID mapping. 338 uid_to_tid.insert(metadata.uid, metadata.tid.unwrap()); 339 Ok(()) 340 }; 341 342 // Initialize a call graph, which is a map of transition IDs to the transition IDs it calls. 343 let mut call_graph = HashMap::new(); 344 // Initialize a mapping from UIDs to transition IDs. 345 let mut uid_to_tid = HashMap::new(); 346 347 // Initialize a stack to track transition metadata, while traversing the call graph. 348 let mut traversal_stack: Vec<TransitionMetadata<N>> = Vec::new(); 349 // Initialize a counter to provide unique IDs for each transition. 350 let mut counter = 0; 351 352 // Iterate over each transition in reverse post-order, and populate the call graph. 353 for transition in execution.transitions().rev() { 354 // Now process the current `transition`. 355 // At this point, the algorithm must maintain the following invariant: 356 // - The stack is either empty, or the top entry is incomplete. 357 match traversal_stack.last_mut() { 358 // If the stack is empty, then push the `transition` to the top of the stack. 359 None => { 360 traversal_stack.push(TransitionMetadata::new( 361 &mut counter, 362 *transition.program_id(), 363 *transition.function_name(), 364 Some(*transition.id()), 365 )); 366 } 367 // If the stack is not empty, then add the current transition ID to the entry. 368 Some(head) => match head.pid == *transition.program_id() && head.fname == *transition.function_name() { 369 true => head.tid = Some(*transition.id()), 370 false => bail!("Invalid traversal - unexpected transition in the execution"), 371 }, 372 } 373 374 // Process the entry at the top of the stack. By the previous step, this entry has a transition ID. 375 // Note this unwrap is safe, since we either pushed an entry to the stack or modified the one at the top of the stack. 376 let top = traversal_stack.last().unwrap(); 377 // If the entry is complete, then add it to the call graph. 378 if top.is_complete() { 379 // Note this unwrap is safe, for the same reason as above. 380 update_call_graph(traversal_stack.pop().unwrap(), &mut call_graph, &mut uid_to_tid)?; 381 } else { 382 // Retrieve the stack. 383 let stack = self.get_stack(top.pid)?; 384 // Retrieve the function from the stack. 385 let function = stack.get_function(&top.fname)?; 386 // Collect the children of the current transition. 387 let mut children = Vec::new(); 388 for instruction in function.instructions() { 389 if let Instruction::Call(call) = instruction { 390 let (pid, fname) = match call.operator() { 391 alphavm_synthesizer_program::CallOperator::Locator(locator) => { 392 (locator.program_id(), locator.resource()) 393 } 394 alphavm_synthesizer_program::CallOperator::Resource(fname) => (&top.pid, fname), 395 }; 396 // Add the child to the traversal stack, only if it is a call to a transition. 397 if self.get_stack(pid)?.get_function(fname).is_ok() { 398 children.push(TransitionMetadata::new(&mut counter, *pid, *fname, None)); 399 } 400 } 401 } 402 403 // Add the children UIDs to the metadata. 404 // Note this unwrap is safe, for the same reason as above. 405 let top = traversal_stack.last_mut().unwrap(); 406 let child_uids = children.iter().map(|child| child.uid).collect::<Vec<_>>(); 407 match top.children { 408 None => top.children = Some(child_uids), 409 Some(_) => bail!("Invalid traversal - children have already been processed"), 410 } 411 // Push the children to the top of the stack. 412 traversal_stack.extend(children); 413 } 414 // If the stack has complete metadata entries, then remove and add them to the call graph. 415 while let Some(metadata) = traversal_stack.last() { 416 if metadata.is_complete() { 417 update_call_graph(traversal_stack.pop().unwrap(), &mut call_graph, &mut uid_to_tid)?; 418 } else { 419 break; 420 } 421 } 422 } 423 // Check that the the traversal completed correctly. 424 ensure!(traversal_stack.is_empty(), "Invalid traversal - traversal stack is not empty"); 425 ensure!( 426 counter == execution.len(), 427 "Invalid traversal - counter does not match the number of transitions in the execution" 428 ); 429 430 Ok(call_graph) 431 } 432 433 /// A helper function to reverse the call graph. 434 /// 435 /// The call graph is a mapping of parent transition IDs to child transition IDs, 436 /// in the order that they were called. 437 /// 438 /// The reverse call graph is a mapping of child transition IDs to parent transition IDs. 439 /// Note: Each child transition only has one parent transition, by definition. 440 fn reverse_call_graph( 441 call_graph: &HashMap<N::TransitionID, Vec<N::TransitionID>>, 442 ) -> HashMap<N::TransitionID, N::TransitionID> { 443 // Initialize a map for the reverse call graph. 444 let mut reverse_call_graph = HashMap::new(); 445 // Iterate over the (forward) call graph. 446 for (parent, children) in call_graph { 447 for child in children { 448 let result = reverse_call_graph.insert(*child, *parent); 449 debug_assert!(result.is_none(), "Found a child with multiple parents"); 450 } 451 } 452 reverse_call_graph 453 } 454 }