snarkvm_synthesizer_process/trace/
mod.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
16mod call_metrics;
17pub use call_metrics::*;
18
19mod inclusion;
20pub use inclusion::*;
21
22use algorithms::snark::varuna::VarunaVersion;
23use circuit::Assignment;
24use console::{
25    network::prelude::*,
26    program::{InputID, Locator},
27};
28use ledger_block::{Execution, Fee, Transition};
29use ledger_query::QueryTrait;
30use synthesizer_snark::{Proof, ProvingKey, VerifyingKey};
31
32use once_cell::sync::OnceCell;
33use std::collections::HashMap;
34
35#[derive(Clone, Debug, Default)]
36pub struct Trace<N: Network> {
37    /// The list of transitions.
38    transitions: Vec<Transition<N>>,
39    /// A map of locators to (proving key, assignments) pairs.
40    transition_tasks: HashMap<Locator<N>, (ProvingKey<N>, Vec<Assignment<N::Field>>)>,
41    /// A tracker for all inclusion tasks.
42    inclusion_tasks: Inclusion<N>,
43    /// A list of call metrics.
44    call_metrics: Vec<CallMetrics<N>>,
45
46    /// A tracker for the inclusion assignments.
47    inclusion_assignments: OnceCell<Vec<InclusionAssignment<N>>>,
48    /// A tracker for the global state root.
49    global_state_root: OnceCell<N::StateRoot>,
50}
51
52impl<N: Network> Trace<N> {
53    /// Initializes a new trace.
54    pub fn new() -> Self {
55        Self {
56            transitions: Vec::new(),
57            transition_tasks: HashMap::new(),
58            inclusion_tasks: Inclusion::new(),
59            inclusion_assignments: OnceCell::new(),
60            global_state_root: OnceCell::new(),
61            call_metrics: Vec::new(),
62        }
63    }
64
65    /// Returns the list of transitions.
66    pub fn transitions(&self) -> &[Transition<N>] {
67        &self.transitions
68    }
69
70    /// Returns the call metrics.
71    pub fn call_metrics(&self) -> &[CallMetrics<N>] {
72        &self.call_metrics
73    }
74}
75
76impl<N: Network> Trace<N> {
77    /// Inserts the transition into the trace.
78    pub fn insert_transition(
79        &mut self,
80        input_ids: &[InputID<N>],
81        transition: &Transition<N>,
82        (proving_key, assignment): (ProvingKey<N>, Assignment<N::Field>),
83        metrics: CallMetrics<N>,
84    ) -> Result<()> {
85        // Ensure the inclusion assignments and global state root have not been set.
86        ensure!(self.inclusion_assignments.get().is_none());
87        ensure!(self.global_state_root.get().is_none());
88
89        // Insert the transition into the inclusion tasks.
90        self.inclusion_tasks.insert_transition(input_ids, transition)?;
91
92        // Construct the locator.
93        let locator = Locator::new(*transition.program_id(), *transition.function_name());
94        // Insert the assignment (and proving key if the entry does not exist), for the specified locator.
95        self.transition_tasks.entry(locator).or_insert((proving_key, vec![])).1.push(assignment);
96        // Insert the transition into the list.
97        self.transitions.push(transition.clone());
98        // Insert the call metrics into the list.
99        self.call_metrics.push(metrics);
100
101        Ok(())
102    }
103}
104
105impl<N: Network> Trace<N> {
106    /// Returns `true` if the trace is for a fee transition.
107    pub fn is_fee(&self) -> bool {
108        self.is_fee_private() || self.is_fee_public()
109    }
110
111    /// Returns `true` if the trace is for a private fee transition.
112    pub fn is_fee_private(&self) -> bool {
113        // If there is 1 transition, check if the transition is a fee transition.
114        self.transitions.len() == 1 && self.transitions[0].is_fee_private()
115    }
116
117    /// Returns `true` if the trace is for a public fee transition.
118    pub fn is_fee_public(&self) -> bool {
119        // If there is 1 transition, check if the transition is a fee transition.
120        self.transitions.len() == 1 && self.transitions[0].is_fee_public()
121    }
122}
123
124impl<N: Network> Trace<N> {
125    /// Returns the inclusion assignments and global state root for the current transition(s).
126    pub fn prepare(&mut self, query: impl QueryTrait<N>) -> Result<()> {
127        // Compute the inclusion assignments.
128        let (inclusion_assignments, global_state_root) = self.inclusion_tasks.prepare(&self.transitions, query)?;
129        // Store the inclusion assignments and global state root.
130        self.inclusion_assignments
131            .set(inclusion_assignments)
132            .map_err(|_| anyhow!("Failed to set inclusion assignments"))?;
133        self.global_state_root.set(global_state_root).map_err(|_| anyhow!("Failed to set global state root"))?;
134        Ok(())
135    }
136
137    /// Returns the inclusion assignments and global state root for the current transition(s).
138    #[cfg(feature = "async")]
139    pub async fn prepare_async(&mut self, query: impl QueryTrait<N>) -> Result<()> {
140        // Compute the inclusion assignments.
141        let (inclusion_assignments, global_state_root) =
142            self.inclusion_tasks.prepare_async(&self.transitions, query).await?;
143        // Store the inclusion assignments and global state root.
144        self.inclusion_assignments
145            .set(inclusion_assignments)
146            .map_err(|_| anyhow!("Failed to set inclusion assignments"))?;
147        self.global_state_root.set(global_state_root).map_err(|_| anyhow!("Failed to set global state root"))?;
148        Ok(())
149    }
150
151    /// Returns a new execution with a proof, for the current inclusion assignments and global state root.
152    pub fn prove_execution<A: circuit::Aleo<Network = N>, R: Rng + CryptoRng>(
153        &self,
154        locator: &str,
155        varuna_version: VarunaVersion,
156        rng: &mut R,
157    ) -> Result<Execution<N>> {
158        // Ensure this is not a fee.
159        ensure!(!self.is_fee(), "The trace cannot call 'prove_execution' for a fee type");
160        // Ensure there are no fee transitions.
161        ensure!(
162            self.transitions.iter().all(|transition| !(transition.is_fee_private() || transition.is_fee_public())),
163            "The trace cannot prove execution for a fee, call 'prove_fee' instead"
164        );
165        // Retrieve the inclusion assignments.
166        let inclusion_assignments =
167            self.inclusion_assignments.get().ok_or_else(|| anyhow!("Inclusion assignments have not been set"))?;
168        // Retrieve the global state root.
169        let global_state_root =
170            self.global_state_root.get().ok_or_else(|| anyhow!("Global state root has not been set"))?;
171        // Construct the proving tasks.
172        let proving_tasks = self.transition_tasks.values().cloned().collect();
173        // Compute the proof.
174        let (global_state_root, proof) = Self::prove_batch::<A, R>(
175            locator,
176            varuna_version,
177            proving_tasks,
178            inclusion_assignments,
179            *global_state_root,
180            rng,
181        )?;
182        // Return the execution.
183        Execution::from(self.transitions.iter().cloned(), global_state_root, Some(proof))
184    }
185
186    /// Returns a new fee with a proof, for the current inclusion assignment and global state root.
187    pub fn prove_fee<A: circuit::Aleo<Network = N>, R: Rng + CryptoRng>(
188        &self,
189        varuna_version: VarunaVersion,
190        rng: &mut R,
191    ) -> Result<Fee<N>> {
192        // Ensure this is a fee.
193        let is_fee_public = self.is_fee_public();
194        let is_fee_private = self.is_fee_private();
195        ensure!(is_fee_public || is_fee_private, "The trace cannot call 'prove_fee' for an execution type");
196        // Retrieve the inclusion assignments.
197        let inclusion_assignments =
198            self.inclusion_assignments.get().ok_or_else(|| anyhow!("Inclusion assignments have not been set"))?;
199        // Ensure the correct number of inclusion assignments are provided.
200        match is_fee_public {
201            true => ensure!(inclusion_assignments.is_empty(), "Expected 0 inclusion assignments for proving the fee"),
202            false => ensure!(inclusion_assignments.len() == 1, "Expected 1 inclusion assignment for proving the fee"),
203        }
204        // Retrieve the global state root.
205        let global_state_root =
206            self.global_state_root.get().ok_or_else(|| anyhow!("Global state root has not been set"))?;
207        // Retrieve the fee transition.
208        let fee_transition = &self.transitions[0];
209        // Construct the proving tasks.
210        let proving_tasks = self.transition_tasks.values().cloned().collect();
211        // Compute the proof.
212        let (global_state_root, proof) = Self::prove_batch::<A, R>(
213            "credits.aleo/fee (private or public)",
214            varuna_version,
215            proving_tasks,
216            inclusion_assignments,
217            *global_state_root,
218            rng,
219        )?;
220        // Return the fee.
221        Ok(Fee::from_unchecked(fee_transition.clone(), global_state_root, Some(proof)))
222    }
223
224    /// Checks the proof for the execution.
225    /// Note: This does *not* check that the global state root exists in the ledger.
226    pub fn verify_execution_proof(
227        locator: &str,
228        varuna_version: VarunaVersion,
229        verifier_inputs: Vec<(VerifyingKey<N>, Vec<Vec<N::Field>>)>,
230        execution: &Execution<N>,
231    ) -> Result<()> {
232        // Retrieve the global state root.
233        let global_state_root = execution.global_state_root();
234        // Ensure the global state root is not zero.
235        if global_state_root == N::StateRoot::default() {
236            bail!("Inclusion expected the global state root in the execution to *not* be zero")
237        }
238        // Retrieve the proof.
239        let Some(proof) = execution.proof() else { bail!("Expected the execution to contain a proof") };
240        // Verify the execution proof.
241        match Self::verify_batch(
242            locator,
243            varuna_version,
244            verifier_inputs,
245            global_state_root,
246            execution.transitions(),
247            proof,
248        ) {
249            Ok(()) => Ok(()),
250            Err(e) => bail!("Execution is invalid - {e}"),
251        }
252    }
253
254    /// Checks the proof for the fee.
255    /// Note: This does *not* check that the global state root exists in the ledger.
256    pub fn verify_fee_proof(
257        varuna_version: VarunaVersion,
258        verifier_inputs: (VerifyingKey<N>, Vec<Vec<N::Field>>),
259        fee: &Fee<N>,
260    ) -> Result<()> {
261        // Retrieve the global state root.
262        let global_state_root = fee.global_state_root();
263        // Ensure the global state root is not zero.
264        if global_state_root == N::StateRoot::default() {
265            bail!("Inclusion expected the global state root in the fee to *not* be zero")
266        }
267        // Retrieve the proof.
268        let Some(proof) = fee.proof() else { bail!("Expected the fee to contain a proof") };
269        // Verify the fee proof.
270        match Self::verify_batch(
271            "credits.aleo/fee (private or public)",
272            varuna_version,
273            vec![verifier_inputs],
274            global_state_root,
275            [fee.transition()].into_iter(),
276            proof,
277        ) {
278            Ok(()) => Ok(()),
279            Err(e) => bail!("Fee is invalid - {e}"),
280        }
281    }
282}
283
284impl<N: Network> Trace<N> {
285    /// Returns the global state root and proof for the given assignments.
286    fn prove_batch<A: circuit::Aleo<Network = N>, R: Rng + CryptoRng>(
287        locator: &str,
288        varuna_version: VarunaVersion,
289        mut proving_tasks: Vec<(ProvingKey<N>, Vec<Assignment<N::Field>>)>,
290        inclusion_assignments: &[InclusionAssignment<N>],
291        global_state_root: N::StateRoot,
292        rng: &mut R,
293    ) -> Result<(N::StateRoot, Proof<N>)> {
294        // Ensure the global state root is not zero.
295        // Note: To protect user privacy, even when there are *no* inclusion assignments,
296        // the user must provide a real global state root (which is checked in consensus).
297        if global_state_root == N::StateRoot::default() {
298            bail!("Inclusion expected the global state root in the execution to *not* be zero")
299        }
300
301        // Initialize a vector for the batch inclusion assignments.
302        let mut batch_inclusions = Vec::with_capacity(inclusion_assignments.len());
303
304        for assignment in inclusion_assignments.iter() {
305            // Ensure the global state root is the same across iterations.
306            if global_state_root != assignment.state_path.global_state_root() {
307                bail!("Inclusion expected the global state root to be the same across iterations")
308            }
309            // Add the assignment to the assignments.
310            batch_inclusions.push(assignment.to_circuit_assignment::<A>()?);
311        }
312
313        if !batch_inclusions.is_empty() {
314            // Fetch the inclusion proving key.
315            let proving_key = ProvingKey::<N>::new(N::inclusion_proving_key().clone());
316            // Insert the inclusion proving key and assignments.
317            proving_tasks.push((proving_key, batch_inclusions));
318        }
319
320        // Compute the proof.
321        let proof = ProvingKey::prove_batch(locator, varuna_version, &proving_tasks, rng)?;
322        // Return the global state root and proof.
323        Ok((global_state_root, proof))
324    }
325
326    /// Checks the proof for the given inputs.
327    /// Note: This does *not* check that the global state root exists in the ledger.
328    fn verify_batch<'a>(
329        locator: &str,
330        varuna_version: VarunaVersion,
331        mut verifier_inputs: Vec<(VerifyingKey<N>, Vec<Vec<N::Field>>)>,
332        global_state_root: N::StateRoot,
333        transitions: impl ExactSizeIterator<Item = &'a Transition<N>>,
334        proof: &Proof<N>,
335    ) -> Result<()> {
336        // Construct the batch of inclusion verifier inputs.
337        let batch_inclusion_inputs = Inclusion::prepare_verifier_inputs(global_state_root, transitions)?;
338        // Insert the batch of inclusion verifier inputs to the verifier inputs.
339        if !batch_inclusion_inputs.is_empty() {
340            // Retrieve the inclusion verifying key.
341            let verifying_key = N::inclusion_verifying_key().clone();
342            // Retrieve the number of public and private variables.
343            // Note: This number does *NOT* include the number of constants. This is safe because
344            // this program is never deployed, as it is a first-class citizen of the protocol.
345            let num_variables = verifying_key.circuit_info.num_public_and_private_variables as u64;
346            // Insert the inclusion verifier inputs.
347            verifier_inputs.push((VerifyingKey::<N>::new(verifying_key, num_variables), batch_inclusion_inputs));
348        }
349        // Verify the proof.
350        VerifyingKey::verify_batch(locator, varuna_version, verifier_inputs, proof)
351            .map_err(|e| anyhow!("Failed to verify proof - {e}"))
352    }
353}
snarkvm_synthesizer_process/trace/mod.rs

snarkvm_synthesizer_process/trace/
mod.rs
