verify.rs
1 // Copyright (c) 2019-2025 Alpha-Delta Network Inc. 2 // This file is part of the deltavm 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<A: Alpha> StatePath<A> { 19 /// Returns `true` if the state path is valid. 20 /// 21 /// # Parameters 22 /// - `local_state_root` is the local transaction root for the current execution. 23 /// - `is_global` is a boolean indicating whether this is a global or local state root. 24 /// 25 /// # Diagram 26 /// The `[[ ]]` notation is used to denote public inputs. 27 /// ```ignore 28 /// 29 /// [[ global_state_root ]] 30 /// | 31 /// block_path 32 /// | 33 /// block_hash := Hash( previous_block_hash || header_root ) 34 /// | 35 /// header_path 36 /// | 37 /// header_leaf 38 /// | 39 /// transactions_path [[ local_state_root ]] 40 /// | | 41 /// (true) ------ is_global ------ (false) 42 /// | 43 /// transaction_id 44 /// | 45 /// transaction_path 46 /// | 47 /// transaction_leaf 48 /// | 49 /// transition_id := Hash( transition_root || tcm ) 50 /// | 51 /// transition_path 52 /// | 53 /// transition_leaf 54 /// ``` 55 pub fn verify(&self, is_global: &Boolean<A>, local_state_root: &Field<A>) -> Boolean<A> { 56 // Ensure the transition path is valid. 57 let check_transition_path = 58 A::verify_merkle_path_bhp(&self.transition_path, &self.transition_root, &self.transition_leaf.to_bits_le()) 59 & self.transition_leaf.variant().is_equal(&U8::constant(console::U8::new(3))); // Variant = 3 (Input::Record) 60 61 // Ensure the transaction leaf is valid. 62 let check_transaction_leaf = 63 A::hash_bhp512(&(&self.transition_root, &self.tcm).to_bits_le()).is_equal(self.transaction_leaf.id()); 64 65 // Ensure the transaction path is valid. 66 let check_transaction_path = A::verify_merkle_path_bhp( 67 &self.transaction_path, 68 &self.transaction_id, 69 &self.transaction_leaf.to_bits_le(), 70 ) & self.transaction_leaf.variant().is_equal(&U8::one()); // Variant = 1 (Transaction::Execution) 71 72 // Ensure the transactions path is valid. 73 let check_transactions_path = A::verify_merkle_path_bhp( 74 &self.transactions_path, 75 self.header_leaf.id(), 76 &self.transaction_id.to_bits_le(), 77 ); 78 79 // Ensure the header path is valid. 80 let check_header_path = 81 A::verify_merkle_path_bhp(&self.header_path, &self.header_root, &self.header_leaf.to_bits_le()) 82 & self.header_leaf.index().is_equal(&U8::one()); // Index = 1 (Header::transactions_root) 83 84 // Construct the block hash preimage. 85 let mut block_hash_preimage = self.previous_block_hash.to_bits_le(); 86 self.header_root.write_bits_le(&mut block_hash_preimage); 87 88 // Ensure the block path is valid. 89 let check_block_hash = A::hash_bhp1024(&block_hash_preimage).is_equal(&self.block_hash); 90 91 // Ensure the global state root is correct. 92 let check_state_root = 93 A::verify_merkle_path_bhp(&self.block_path, &self.global_state_root, &self.block_hash.to_bits_le()); 94 95 // Combine the transition and transaction path checks. 96 let check_transition_and_transaction_path = 97 check_transition_path & check_transaction_path & check_transaction_leaf; 98 99 // Check the state path. 100 let check_local = &check_transition_and_transaction_path & local_state_root.is_equal(&self.transaction_id); 101 let check_global = check_transition_and_transaction_path 102 & check_transactions_path 103 & check_header_path 104 & check_block_hash 105 & check_state_root; 106 107 // If the state path is for a global root, return 'check_global'. Else, return 'check_local'. 108 Boolean::ternary(is_global, &check_global, &check_local) 109 } 110 } 111 112 #[cfg(test)] 113 mod tests { 114 use super::*; 115 use crate::Circuit; 116 use deltavm_utilities::rand::{TestRng, Uniform}; 117 118 type CurrentNetwork = <Circuit as Environment>::Network; 119 120 const ITERATIONS: usize = 20; 121 122 fn check_verify_global( 123 mode: Mode, 124 is_global: bool, 125 num_constants: u64, 126 num_public: u64, 127 num_private: u64, 128 num_constraints: u64, 129 ) -> Result<()> { 130 let rng = &mut TestRng::default(); 131 132 for i in 0..ITERATIONS { 133 // Sample the console state path. 134 let console_state_path = 135 console::state_path::test_helpers::sample_global_state_path::<CurrentNetwork>(None, rng).unwrap(); 136 // Sample the local state root. 137 let local_state_root = console::Field::rand(rng); 138 139 // Ensure the console state path is valid. 140 console_state_path.verify(true, local_state_root).unwrap(); 141 142 Circuit::scope(format!("Verify global state path {mode} (is_global: {is_global})"), || { 143 // Inject the is_global boolean. 144 let circuit_is_global = Boolean::new(mode, is_global); 145 // Inject the local state root. 146 let circuit_local_state_root = Field::new(mode, local_state_root); 147 // Inject the state path. 148 let circuit_state_path = StatePath::<Circuit>::new(mode, console_state_path.clone()); 149 150 // Ensure the state path is valid. 151 let is_valid = circuit_state_path.verify(&circuit_is_global, &circuit_local_state_root); 152 match is_global { 153 true => assert!(is_valid.eject_value()), 154 false => assert!(!is_valid.eject_value()), 155 } 156 157 assert!(Circuit::is_satisfied()); 158 // TODO (howardwu): Resolve skipping the cost count checks for the burn-in round. 159 if i > 0 { 160 assert_scope!(num_constants, num_public, num_private, num_constraints); 161 } 162 }); 163 164 Circuit::reset(); 165 } 166 Ok(()) 167 } 168 169 fn check_verify_local( 170 mode: Mode, 171 is_global: bool, 172 is_valid_local_root: bool, 173 num_constants: u64, 174 num_public: u64, 175 num_private: u64, 176 num_constraints: u64, 177 ) -> Result<()> { 178 let rng = &mut TestRng::default(); 179 180 for i in 0..ITERATIONS { 181 // Sample the console state path. 182 let console_state_path = 183 console::state_path::test_helpers::sample_local_state_path::<CurrentNetwork>(None, rng).unwrap(); 184 // Sample the local state root. 185 let local_state_root = **console_state_path.transaction_id(); 186 187 // Ensure the console state path is valid. 188 console_state_path.verify(false, local_state_root).unwrap(); 189 190 Circuit::scope( 191 format!( 192 "Verify local state path {mode} (is_global: {is_global}, is_valid_local_root: {is_valid_local_root})" 193 ), 194 || { 195 // Inject the is_global boolean. 196 let circuit_is_global = Boolean::new(mode, is_global); 197 // Inject the local state root. 198 let circuit_local_state_root = if is_valid_local_root { 199 Field::new(mode, local_state_root) 200 } else { 201 Field::new(mode, console::Field::rand(rng)) 202 }; 203 204 // Inject the state path. 205 let circuit_state_path = StatePath::<Circuit>::new(mode, console_state_path.clone()); 206 207 // Ensure the state path is valid. 208 let is_valid = circuit_state_path.verify(&circuit_is_global, &circuit_local_state_root); 209 match (is_global, is_valid_local_root) { 210 (false, true) => assert!(is_valid.eject_value()), 211 _ => assert!(!is_valid.eject_value()), 212 } 213 214 assert!(Circuit::is_satisfied()); 215 // TODO (howardwu): Resolve skipping the cost count checks for the burn-in round. 216 if i > 0 { 217 assert_scope!(num_constants, num_public, num_private, num_constraints); 218 } 219 }, 220 ); 221 222 Circuit::reset(); 223 } 224 Ok(()) 225 } 226 227 #[test] 228 fn test_state_path_verify_global_constant() -> Result<()> { 229 check_verify_global(Mode::Constant, true, 112709, 1, 2, 2)?; 230 check_verify_global(Mode::Constant, false, 112709, 1, 2, 2) 231 } 232 233 #[test] 234 fn test_state_path_verify_global_public() -> Result<()> { 235 check_verify_global(Mode::Public, true, 29450, 453, 130867, 131522)?; 236 check_verify_global(Mode::Public, false, 29450, 453, 130867, 131522) 237 } 238 239 #[test] 240 fn test_state_path_verify_global_private() -> Result<()> { 241 check_verify_global(Mode::Private, true, 29450, 1, 131319, 131522)?; 242 check_verify_global(Mode::Private, false, 29450, 1, 131319, 131522) 243 } 244 245 #[test] 246 fn test_state_path_verify_local_constant() -> Result<()> { 247 check_verify_local(Mode::Constant, false, true, 112709, 1, 2, 2)?; 248 check_verify_local(Mode::Constant, false, false, 112709, 1, 2, 2)?; 249 check_verify_local(Mode::Constant, true, true, 112709, 1, 2, 2)?; 250 check_verify_local(Mode::Constant, true, false, 112709, 1, 2, 2) 251 } 252 253 #[test] 254 fn test_state_path_verify_local_public() -> Result<()> { 255 check_verify_local(Mode::Public, false, true, 29450, 453, 130867, 131522)?; 256 check_verify_local(Mode::Public, false, false, 29450, 453, 130867, 131522)?; 257 check_verify_local(Mode::Public, true, true, 29450, 453, 130867, 131522)?; 258 check_verify_local(Mode::Public, true, false, 29450, 453, 130867, 131522) 259 } 260 261 #[test] 262 fn test_state_path_verify_local_private() -> Result<()> { 263 check_verify_local(Mode::Private, false, true, 29450, 1, 131319, 131522)?; 264 check_verify_local(Mode::Private, false, false, 29450, 1, 131319, 131522)?; 265 check_verify_local(Mode::Private, true, true, 29450, 1, 131319, 131522)?; 266 check_verify_local(Mode::Private, true, false, 29450, 1, 131319, 131522) 267 } 268 }