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

snarkvm_synthesizer_process/trace/
mod.rs
