snarkvm_console_program/state_path/verify.rs
1// Copyright (c) 2019-2025 Provable Inc.
2// This file is part of the snarkVM 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
16use super::*;
17
18impl<N: Network> StatePath<N> {
19 /// Checks 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: bool, local_state_root: Field<N>) -> Result<()> {
56 // Ensure the transition leaf variant is 3 (Input::Record).
57 ensure!(self.transition_leaf.variant() == 3, "Transition leaf variant must be 3 (Input::Record)");
58 // Ensure the transition path is valid.
59 ensure!(
60 N::verify_merkle_path_bhp(&self.transition_path, &self.transition_root, &self.transition_leaf.to_bits_le()),
61 "'{}' (an input or output ID) does not belong to '{}' (a function or transition)",
62 self.transition_leaf.id(),
63 self.transaction_leaf.id()
64 );
65
66 // Ensure the transaction leaf is correct.
67 ensure!(
68 *self.transaction_leaf.id() == *N::hash_bhp512(&(*self.transition_root, self.tcm).to_bits_le())?,
69 "Transaction leaf id '{}' is incorrect. Double-check the tcm and transition root.",
70 self.transaction_leaf.id()
71 );
72
73 // Ensure the transaction leaf variant is 1 (Transaction::Execution).
74 ensure!(self.transaction_leaf.variant() == 1, "Transaction leaf variant must be 1 (Transaction::Execution)");
75 // Ensure the transaction path is valid.
76 ensure!(
77 N::verify_merkle_path_bhp(
78 &self.transaction_path,
79 &self.transaction_id,
80 &self.transaction_leaf.to_bits_le()
81 ),
82 "'{}' (a function or transition) does not belong to transaction '{}'",
83 self.transaction_leaf.id(),
84 self.transaction_id
85 );
86
87 if is_global {
88 // Ensure the header leaf index is 1 (Header::transactions_root).
89 ensure!(self.header_leaf.index() == 1, "Header leaf index must be 1 (Header::transactions_root)");
90 // Ensure the transactions path is valid.
91 ensure!(
92 N::verify_merkle_path_bhp(
93 &self.transactions_path,
94 &self.header_leaf.id(),
95 &self.transaction_id.to_bits_le()
96 ),
97 "Transaction '{}' does not belong to '{}' (a header leaf)",
98 self.transaction_id,
99 self.header_leaf
100 );
101 // Ensure the header path is valid.
102 ensure!(
103 N::verify_merkle_path_bhp(&self.header_path, &self.header_root, &self.header_leaf.to_bits_le()),
104 "'{}' (a header leaf) does not belong to '{}' (a block header)",
105 self.header_leaf,
106 self.block_hash
107 );
108 // Ensure the block hash is correct.
109 ensure!(
110 *self.block_hash == N::hash_bhp1024(&to_bits_le![(*self.previous_block_hash), self.header_root])?,
111 "Block hash '{}' is incorrect. Double-check the previous block hash and block header root.",
112 self.block_hash
113 );
114 // Ensure the global state root is correct.
115 ensure!(
116 N::verify_merkle_path_bhp(&self.block_path, &self.global_state_root, &self.block_hash.to_bits_le()),
117 "'{}' (a block hash) does not belong to '{}' (a global state root)",
118 self.block_hash,
119 self.global_state_root
120 );
121 } else {
122 // Ensure the local state root is correct.
123 ensure!(
124 *self.transaction_id == local_state_root,
125 "'{}' (a decoded transaction ID) does not match the '{local_state_root}' (a local state root)",
126 *self.transaction_id
127 );
128 }
129
130 Ok(())
131 }
132}
133
134#[cfg(test)]
135mod tests {
136 use super::*;
137 use snarkvm_console_network::{MainnetV0, prelude::TestRng};
138
139 type CurrentNetwork = MainnetV0;
140
141 const ITERATIONS: usize = 100;
142
143 #[test]
144 fn test_verify_global() {
145 let rng = &mut TestRng::default();
146
147 for _ in 0..ITERATIONS {
148 // Sample the state path.
149 let state_path =
150 crate::state_path::test_helpers::sample_global_state_path::<CurrentNetwork>(None, rng).unwrap();
151 // Sample the local state root.
152 let local_state_root = Field::rand(rng);
153
154 // Ensure the state path is valid.
155 state_path.verify(true, local_state_root).unwrap();
156 // Ensure the state path is *not* valid for a random local state root.
157 state_path.verify(false, local_state_root).unwrap_err();
158 }
159 }
160
161 #[test]
162 fn test_verify_local() {
163 let rng = &mut TestRng::default();
164
165 for _ in 0..ITERATIONS {
166 // Sample the state path.
167 let state_path =
168 crate::state_path::test_helpers::sample_local_state_path::<CurrentNetwork>(None, rng).unwrap();
169 // Retrieve the local state root.
170 let local_state_root = **state_path.transaction_id();
171
172 // Ensure the state path is valid.
173 state_path.verify(false, local_state_root).unwrap();
174 // Ensure the state path does *not* match a random local state root.
175 state_path.verify(false, Field::rand(rng)).unwrap_err();
176 // Ensure the state path does *not* match to the random global state root.
177 state_path.verify(true, local_state_root).unwrap_err();
178 // Ensure the state path does *not* match to the random global state root.
179 state_path.verify(true, Field::rand(rng)).unwrap_err();
180 }
181 }
182
183 #[test]
184 fn test_verify_new_local() {
185 let rng = &mut TestRng::default();
186
187 for _ in 0..ITERATIONS {
188 // Sample the state path.
189 let state_path =
190 crate::state_path::test_helpers::sample_local_state_path::<CurrentNetwork>(None, rng).unwrap();
191
192 // Initialize the state path using `new_local`.
193 let new_local_state_path = StatePath::new_local(
194 state_path.global_state_root(),
195 *state_path.transaction_id(),
196 state_path.transaction_path().clone(),
197 *state_path.transaction_leaf(),
198 *state_path.transition_root(),
199 *state_path.tcm(),
200 state_path.transition_path().clone(),
201 *state_path.transition_leaf(),
202 )
203 .unwrap();
204
205 // Retrieve the local state root.
206 let local_state_root = **new_local_state_path.transaction_id();
207
208 // Ensure the state path is valid.
209 new_local_state_path.verify(false, local_state_root).unwrap();
210 // Ensure the state path does *not* match a random local state root.
211 new_local_state_path.verify(false, Field::rand(rng)).unwrap_err();
212 // Ensure the state path does *not* match to the random global state root.
213 new_local_state_path.verify(true, local_state_root).unwrap_err();
214 // Ensure the state path does *not* match to the random global state root.
215 new_local_state_path.verify(true, Field::rand(rng)).unwrap_err();
216 }
217 }
218}