snarkvm_circuit_program/state_path/
verify.rs

1// Copyright 2024-2025 Aleo Network Foundation
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<A: Aleo> 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)]
113mod tests {
114    use super::*;
115    use crate::Circuit;
116    use snarkvm_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}
snarkvm_circuit_program/state_path/verify.rs

snarkvm_circuit_program/state_path/
verify.rs
