snarkvm_ledger_block/transaction/
merkle.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> Transaction<N> {
19    /// The maximum number of transitions allowed in a transaction.
20    pub const MAX_TRANSITIONS: usize = usize::pow(2, TRANSACTION_DEPTH as u32);
21
22    /// Returns the transaction root, by computing the root for a Merkle tree of the transition IDs.
23    pub fn to_root(&self) -> Result<Field<N>> {
24        Ok(*self.to_tree()?.root())
25    }
26
27    /// Returns the Merkle leaf for the given ID of a function or transition in the transaction.
28    pub fn to_leaf(&self, id: &Field<N>) -> Result<TransactionLeaf<N>> {
29        match self {
30            Self::Deploy(_, _, _, deployment, fee) => {
31                // Check if the ID is the transition ID for the fee.
32                if *id == **fee.id() {
33                    // Return the transaction leaf.
34                    return Ok(TransactionLeaf::new_fee(
35                        u16::try_from(deployment.program().functions().len())?, // The last index.
36                        *id,
37                    ));
38                }
39
40                // Iterate through the functions in the deployment.
41                for (index, function) in deployment.program().functions().values().enumerate() {
42                    // Check if the function hash matches the given ID.
43                    if *id == N::hash_bhp1024(&function.to_bytes_le()?.to_bits_le())? {
44                        // Return the transaction leaf.
45                        return Ok(TransactionLeaf::new_deployment(u16::try_from(index)?, *id));
46                    }
47                }
48                // Error if the function hash was not found.
49                bail!("Function hash not found in deployment transaction");
50            }
51            Self::Execute(_, _, execution, fee) => {
52                // Check if the ID is the transition ID for the fee.
53                if let Some(fee) = fee {
54                    if *id == **fee.id() {
55                        // Return the transaction leaf.
56                        return Ok(TransactionLeaf::new_execution(
57                            u16::try_from(execution.len())?, // The last index.
58                            *id,
59                        ));
60                    }
61                }
62
63                // Iterate through the transitions in the execution.
64                for (index, transition) in execution.transitions().enumerate() {
65                    // Check if the transition ID matches the given ID.
66                    if *id == **transition.id() {
67                        // Return the transaction leaf.
68                        return Ok(TransactionLeaf::new_execution(u16::try_from(index)?, *id));
69                    }
70                }
71                // Error if the transition ID was not found.
72                bail!("Transition ID not found in execution transaction");
73            }
74            Self::Fee(_, fee) => {
75                if *id == **fee.id() {
76                    // Return the transaction leaf.
77                    return Ok(TransactionLeaf::new_fee(0, **fee.id()));
78                }
79                // Error if the transition ID was not found.
80                bail!("Transition ID not found in fee transaction");
81            }
82        }
83    }
84
85    /// Returns the Merkle path for the transaction leaf.
86    pub fn to_path(&self, leaf: &TransactionLeaf<N>) -> Result<TransactionPath<N>> {
87        // Compute the Merkle path.
88        self.to_tree()?.prove(leaf.index() as usize, &leaf.to_bits_le())
89    }
90
91    /// The Merkle tree of transition IDs for the transaction.
92    pub fn to_tree(&self) -> Result<TransactionTree<N>> {
93        match self {
94            // Compute the deployment tree.
95            Transaction::Deploy(_, _, _, deployment, fee) => {
96                Self::transaction_tree(Self::deployment_tree(deployment)?, Some(fee))
97            }
98            // Compute the execution tree.
99            Transaction::Execute(_, _, execution, fee) => {
100                Self::transaction_tree(Self::execution_tree(execution)?, fee.as_ref())
101            }
102            // Compute the fee tree.
103            Transaction::Fee(_, fee) => Self::fee_tree(fee),
104        }
105    }
106}
107
108impl<N: Network> Transaction<N> {
109    /// Returns the Merkle tree for the given transaction tree, fee index, and fee.
110    pub fn transaction_tree(
111        mut deployment_or_execution_tree: TransactionTree<N>,
112        fee: Option<&Fee<N>>,
113    ) -> Result<TransactionTree<N>> {
114        // Retrieve the fee index, defined as the last index in the transaction tree.
115        let fee_index = deployment_or_execution_tree.number_of_leaves();
116        // Ensure the fee index is within the Merkle tree size.
117        ensure!(
118            fee_index <= N::MAX_FUNCTIONS,
119            "The fee index ('{fee_index}') in the transaction tree must be at most {}",
120            N::MAX_FUNCTIONS
121        );
122        // Ensure the fee index is within the Merkle tree size.
123        ensure!(
124            fee_index < Self::MAX_TRANSITIONS,
125            "The fee index ('{fee_index}') in the transaction tree must be less than {}",
126            Self::MAX_TRANSITIONS
127        );
128
129        // If a fee is provided, append the fee leaf to the transaction tree.
130        if let Some(fee) = fee {
131            // Construct the transaction leaf.
132            let leaf = TransactionLeaf::new_fee(u16::try_from(fee_index)?, **fee.transition_id()).to_bits_le();
133            // Append the fee leaf to the transaction tree.
134            deployment_or_execution_tree.append(&[leaf])?;
135        }
136        // Return the transaction tree.
137        Ok(deployment_or_execution_tree)
138    }
139
140    /// Returns the Merkle tree for the given deployment.
141    pub fn deployment_tree(deployment: &Deployment<N>) -> Result<DeploymentTree<N>> {
142        // Use the V1 or V2 deployment tree based on implicit deployment version.
143        // Note: `ConsensusVersion::V9` requires the program checksum and program owner to be present, while prior versions require it to be absent.
144        //   `Deployment::version` checks that this is the case.
145        // Note: After `ConsensusVersion::V9`, the program checksum and owner are used in the header of the hash instead of the program ID.
146        match deployment.version() {
147            Ok(DeploymentVersion::V1) => Self::deployment_tree_v1(deployment),
148            Ok(DeploymentVersion::V2) => Self::deployment_tree_v2(deployment),
149            Err(e) => bail!("Malformed deployment - {e}"),
150        }
151    }
152
153    /// Returns the Merkle tree for the given execution.
154    pub fn execution_tree(execution: &Execution<N>) -> Result<ExecutionTree<N>> {
155        Self::transitions_tree(execution.transitions())
156    }
157
158    /// Returns the Merkle tree for the given transitions.
159    pub fn transitions_tree<'a>(
160        transitions: impl ExactSizeIterator<Item = &'a Transition<N>>,
161    ) -> Result<ExecutionTree<N>> {
162        // Retrieve the number of transitions.
163        let num_transitions = transitions.len();
164        // Ensure the number of leaves is within the Merkle tree size.
165        Self::check_execution_size(num_transitions)?;
166        // Prepare the leaves.
167        let leaves = transitions.enumerate().map(|(index, transition)| {
168            // Construct the transaction leaf.
169            Ok::<_, Error>(TransactionLeaf::new_execution(u16::try_from(index)?, **transition.id()).to_bits_le())
170        });
171        // Compute the execution tree.
172        N::merkle_tree_bhp::<TRANSACTION_DEPTH>(&leaves.collect::<Result<Vec<_>, _>>()?)
173    }
174
175    /// Returns the Merkle tree for the given fee.
176    pub fn fee_tree(fee: &Fee<N>) -> Result<TransactionTree<N>> {
177        // Construct the transaction leaf.
178        let leaf = TransactionLeaf::new_fee(0u16, **fee.transition_id()).to_bits_le();
179        // Compute the execution tree.
180        N::merkle_tree_bhp::<TRANSACTION_DEPTH>(&[leaf])
181    }
182
183    /// Returns `true` if the deployment is within the size bounds.
184    pub fn check_deployment_size(deployment: &Deployment<N>) -> Result<()> {
185        // Retrieve the program.
186        let program = deployment.program();
187        // Retrieve the functions.
188        let functions = program.functions();
189        // Retrieve the verifying keys.
190        let verifying_keys = deployment.verifying_keys();
191        // Retrieve the number of functions.
192        let num_functions = functions.len();
193
194        // Ensure the number of functions and verifying keys match.
195        ensure!(
196            num_functions == verifying_keys.len(),
197            "Number of functions ('{num_functions}') and verifying keys ('{}') do not match",
198            verifying_keys.len()
199        );
200        // Ensure there are functions.
201        ensure!(num_functions != 0, "Deployment must contain at least one function");
202        // Ensure the number of functions is within the allowed range.
203        ensure!(
204            num_functions <= N::MAX_FUNCTIONS,
205            "Deployment must contain at most {} functions, found {num_functions}",
206            N::MAX_FUNCTIONS,
207        );
208        // Ensure the number of functions is within the allowed range.
209        ensure!(
210            num_functions < Self::MAX_TRANSITIONS, // Note: Observe we hold back 1 for the fee.
211            "Deployment must contain less than {} functions, found {num_functions}",
212            Self::MAX_TRANSITIONS,
213        );
214        Ok(())
215    }
216
217    /// Returns `true` if the execution is within the size bounds.
218    pub fn check_execution_size(num_transitions: usize) -> Result<()> {
219        // Ensure there are transitions.
220        ensure!(num_transitions > 0, "Execution must contain at least one transition");
221        // Ensure the number of functions is within the allowed range.
222        ensure!(
223            num_transitions < Self::MAX_TRANSITIONS, // Note: Observe we hold back 1 for the fee.
224            "Execution must contain less than {} transitions, found {num_transitions}",
225            Self::MAX_TRANSITIONS,
226        );
227        Ok(())
228    }
229}
230
231impl<N: Network> Transaction<N> {
232    /// Returns the V1 deployment tree.
233    pub fn deployment_tree_v1(deployment: &Deployment<N>) -> Result<DeploymentTree<N>> {
234        // Ensure the number of leaves is within the Merkle tree size.
235        Self::check_deployment_size(deployment)?;
236        // Prepare the header for the hash.
237        let header = deployment.program().id().to_bits_le();
238        // Prepare the leaves.
239        let leaves = deployment.program().functions().values().enumerate().map(|(index, function)| {
240            // Construct the transaction leaf.
241            Ok(TransactionLeaf::new_deployment(
242                u16::try_from(index)?,
243                N::hash_bhp1024(&to_bits_le![header, function.to_bytes_le()?])?,
244            )
245            .to_bits_le())
246        });
247        // Compute the deployment tree.
248        N::merkle_tree_bhp::<TRANSACTION_DEPTH>(&leaves.collect::<Result<Vec<_>>>()?)
249    }
250
251    /// Returns the V2 deployment tree.
252    pub fn deployment_tree_v2(deployment: &Deployment<N>) -> Result<DeploymentTree<N>> {
253        // Ensure the number of leaves is within the Merkle tree size.
254        Self::check_deployment_size(deployment)?;
255        // Compute a hash of the deployment bytes.
256        let deployment_hash = N::hash_sha3_256(&to_bits_le!(deployment.to_bytes_le()?))?;
257        // Prepare the header for the hash.
258        let header = to_bits_le![deployment.version()? as u8, deployment_hash];
259        // Prepare the leaves.
260        let leaves = deployment.program().functions().values().enumerate().map(|(index, function)| {
261            // Construct the transaction leaf.
262            Ok(TransactionLeaf::new_deployment(
263                u16::try_from(index)?,
264                N::hash_bhp1024(&to_bits_le![header, function.to_bytes_le()?])?,
265            )
266            .to_bits_le())
267        });
268        // Compute the deployment tree.
269        N::merkle_tree_bhp::<TRANSACTION_DEPTH>(&leaves.collect::<Result<Vec<_>>>()?)
270    }
271}
272
273#[cfg(test)]
274mod tests {
275    use super::*;
276
277    type CurrentNetwork = console::network::MainnetV0;
278
279    #[test]
280    fn test_transaction_depth_is_correct() {
281        // We ensure 2^TRANSACTION_DEPTH == MAX_FUNCTIONS + 1.
282        // The "1 extra" is for the fee transition.
283        assert_eq!(
284            2u32.checked_pow(TRANSACTION_DEPTH as u32).unwrap() as usize,
285            Transaction::<CurrentNetwork>::MAX_TRANSITIONS
286        );
287        assert_eq!(
288            CurrentNetwork::MAX_FUNCTIONS.checked_add(1).unwrap(),
289            Transaction::<CurrentNetwork>::MAX_TRANSITIONS
290        );
291    }
292}
snarkvm_ledger_block/transaction/merkle.rs

snarkvm_ledger_block/transaction/
merkle.rs
