snarkvm_ledger_block/transition/
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> Transition<N> {
19    /// Returns the transition root, by computing the root for a Merkle tree of the input and output IDs.
20    pub fn to_root(&self) -> Result<Field<N>> {
21        Ok(*self.to_tree()?.root())
22    }
23
24    /// Returns the Merkle path for the transition leaf.
25    pub fn to_path(&self, leaf: &TransitionLeaf<N>) -> Result<TransitionPath<N>> {
26        // Compute the Merkle path.
27        self.to_tree()?.prove(leaf.index() as usize, &leaf.to_bits_le())
28    }
29
30    /// Returns the Merkle leaf for the given input or output ID in the transition.
31    pub fn to_leaf(&self, id: &Field<N>, is_input: bool) -> Result<TransitionLeaf<N>> {
32        // Match on the input or output ID.
33        match is_input {
34            true => {
35                // Iterate through the transition inputs.
36                for (index, input) in self.inputs.iter().enumerate() {
37                    // Check if the input ID matches the given ID.
38                    if id == input.id() {
39                        // Return the transition leaf.
40                        return Ok(input.to_transition_leaf(u8::try_from(index)?));
41                    }
42                }
43                // Error if the input ID was not found.
44                bail!("Input ID not found in transition")
45            }
46            false => {
47                // Iterate through the transition outputs.
48                for (index, output) in self.outputs.iter().enumerate() {
49                    // Check if the output ID matches the given ID.
50                    if id == output.id() {
51                        // Return the transition leaf.
52                        return Ok(output.to_transition_leaf(u8::try_from(self.inputs.len() + index)?));
53                    }
54                }
55                // Error if the output ID was not found.
56                bail!("Output ID not found in transition")
57            }
58        }
59    }
60
61    /// The Merkle tree of input and output IDs for the transition.
62    pub fn to_tree(&self) -> Result<TransitionTree<N>> {
63        Self::function_tree(&self.inputs, &self.outputs)
64    }
65
66    /// Returns the Merkle tree for the given inputs and outputs.
67    pub(super) fn function_tree(inputs: &[Input<N>], outputs: &[Output<N>]) -> Result<TransitionTree<N>> {
68        // Ensure the number of inputs is within the allowed range.
69        ensure!(
70            inputs.len() <= N::MAX_INPUTS,
71            "Transition cannot exceed {} inputs, found {} inputs",
72            N::MAX_INPUTS,
73            inputs.len()
74        );
75        // Ensure the number of outputs is within the allowed range.
76        ensure!(
77            outputs.len() <= N::MAX_OUTPUTS,
78            "Transition cannot exceed {} outputs, found {} outputs",
79            N::MAX_OUTPUTS,
80            outputs.len()
81        );
82
83        // Prepare the input leaves.
84        let input_leaves = inputs
85            .iter()
86            .enumerate()
87            .map(|(index, input)| Ok::<_, Error>(input.to_transition_leaf(u8::try_from(index)?).to_bits_le()));
88        // Prepare the output leaves.
89        let output_leaves = outputs
90            .iter()
91            .enumerate()
92            .map(|(index, output)| Ok(output.to_transition_leaf(u8::try_from(inputs.len() + index)?).to_bits_le()));
93        // Compute the function tree.
94        N::merkle_tree_bhp::<TRANSITION_DEPTH>(&input_leaves.chain(output_leaves).collect::<Result<Vec<_>, _>>()?)
95    }
96}
97
98#[cfg(test)]
99mod tests {
100    use super::*;
101    use console::network::MainnetV0;
102
103    type CurrentNetwork = MainnetV0;
104
105    #[test]
106    fn test_transition_depth() {
107        // Ensure the log2 relationship between depth and the maximum number of transition inputs & outputs.
108        assert_eq!(2usize.pow(TRANSITION_DEPTH as u32), CurrentNetwork::MAX_INPUTS + CurrentNetwork::MAX_OUTPUTS);
109    }
110}
snarkvm_ledger_block/transition/merkle.rs

snarkvm_ledger_block/transition/
merkle.rs
