snarkvm_ledger_block/header/
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> Header<N> {
19    /// Returns the block header root.
20    pub fn to_root(&self) -> Result<Field<N>> {
21        Ok(*self.to_tree()?.root())
22    }
23
24    /// Returns the Merkle path for the Merkle tree of the block header.
25    pub fn to_path(&self, leaf: &HeaderLeaf<N>) -> Result<HeaderPath<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 ID in the header.
31    pub fn to_leaf(&self, id: &Field<N>) -> Result<HeaderLeaf<N>> {
32        // If the ID is the previous state root, return the 0th leaf.
33        if id == &*self.previous_state_root {
34            Ok(HeaderLeaf::<N>::new(0, *self.previous_state_root))
35        }
36        // If the ID is the transactions root, return the 1st leaf.
37        else if id == &self.transactions_root {
38            Ok(HeaderLeaf::<N>::new(1, self.transactions_root))
39        }
40        // If the ID is the finalize root, return the 2nd leaf.
41        else if id == &self.finalize_root {
42            Ok(HeaderLeaf::<N>::new(2, self.finalize_root))
43        }
44        // If the ID is the ratifications root, return the 3rd leaf.
45        else if id == &self.ratifications_root {
46            Ok(HeaderLeaf::<N>::new(3, self.ratifications_root))
47        }
48        // If the ID is the solutions root, return the 4th leaf.
49        else if id == &self.solutions_root {
50            Ok(HeaderLeaf::<N>::new(4, self.solutions_root))
51        }
52        // If the ID is the subdag root, return the 5th leaf
53        else if id == &self.subdag_root {
54            Ok(HeaderLeaf::<N>::new(5, self.subdag_root))
55        }
56        // If the ID is the metadata hash, then return the 7th leaf.
57        else if id == &self.metadata.to_hash()? {
58            Ok(HeaderLeaf::<N>::new(7, *id))
59        }
60        // Otherwise, bail.
61        else {
62            bail!("Non-existent block header leaf ID: {id}")
63        }
64    }
65
66    /// Returns an instance of the Merkle tree for the block header.
67    pub fn to_tree(&self) -> Result<HeaderTree<N>> {
68        // Determine the number of leaves.
69        let num_leaves = usize::pow(2, HEADER_DEPTH as u32);
70
71        // Construct the Merkle leaves.
72        let mut leaves: Vec<Vec<bool>> = Vec::with_capacity(num_leaves);
73        leaves.push(HeaderLeaf::<N>::new(0, *self.previous_state_root).to_bits_le());
74        leaves.push(HeaderLeaf::<N>::new(1, self.transactions_root).to_bits_le());
75        leaves.push(HeaderLeaf::<N>::new(2, self.finalize_root).to_bits_le());
76        leaves.push(HeaderLeaf::<N>::new(3, self.ratifications_root).to_bits_le());
77        leaves.push(HeaderLeaf::<N>::new(4, self.solutions_root).to_bits_le());
78        leaves.push(HeaderLeaf::<N>::new(5, self.subdag_root).to_bits_le());
79        leaves.push(HeaderLeaf::<N>::new(6, Field::zero()).to_bits_le());
80        leaves.push(HeaderLeaf::<N>::new(7, self.metadata.to_hash()?).to_bits_le());
81
82        // Ensure the correct number of leaves are allocated.
83        ensure!(num_leaves == leaves.len(), "Incorrect number of leaves in the Merkle tree for the block header");
84
85        // Compute the Merkle tree.
86        N::merkle_tree_bhp::<HEADER_DEPTH>(&leaves)
87    }
88}
89
90#[cfg(test)]
91mod tests {
92    use super::*;
93    use console::network::MainnetV0;
94
95    type CurrentNetwork = MainnetV0;
96
97    const ITERATIONS: u64 = 1_000;
98
99    fn check_path<N: Network>(header_path: HeaderPath<N>, root: Field<N>, leaf: &HeaderLeaf<N>) -> Result<()> {
100        // Ensure that the path is valid for the corresponding root and leaf.
101        assert!(N::verify_merkle_path_bhp(&header_path, &root, &leaf.to_bits_le()));
102
103        // Check serialization.
104        let expected_bytes = header_path.to_bytes_le()?;
105        assert_eq!(header_path, HeaderPath::<N>::read_le(&expected_bytes[..])?);
106        assert!(HeaderPath::<N>::read_le(&expected_bytes[1..]).is_err());
107        Ok(())
108    }
109
110    #[test]
111    fn test_merkle() -> Result<()> {
112        let rng = &mut TestRng::default();
113
114        for _ in 0..ITERATIONS {
115            let coinbase_target = u64::rand(rng);
116            let proof_target = rng.gen_range(0..coinbase_target);
117
118            let header = Header::<CurrentNetwork>::from(
119                Into::<<CurrentNetwork as Network>::StateRoot>::into(Field::rand(rng)),
120                Field::rand(rng),
121                Field::rand(rng),
122                Field::rand(rng),
123                Field::rand(rng),
124                Field::rand(rng),
125                Metadata::new(
126                    CurrentNetwork::ID,
127                    u64::rand(rng),
128                    u32::rand(rng),
129                    u128::rand(rng),
130                    u128::rand(rng),
131                    coinbase_target,
132                    proof_target,
133                    u64::rand(rng),
134                    rng.gen_range(0..i64::MAX),
135                    rng.gen_range(0..i64::MAX),
136                )?,
137            )?;
138
139            // Compute the header root.
140            let root = header.to_root()?;
141
142            // Check the 0th leaf.
143            let leaf = header.to_leaf(&*header.previous_state_root())?;
144            assert_eq!(leaf.index(), 0);
145            check_path(header.to_path(&leaf)?, root, &leaf)?;
146
147            // Check the 1st leaf.
148            let leaf = header.to_leaf(&header.transactions_root())?;
149            assert_eq!(leaf.index(), 1);
150            check_path(header.to_path(&leaf)?, root, &leaf)?;
151
152            // Check the 2nd leaf.
153            let leaf = header.to_leaf(&header.finalize_root())?;
154            assert_eq!(leaf.index(), 2);
155            check_path(header.to_path(&leaf)?, root, &leaf)?;
156
157            // Check the 3rd leaf.
158            let leaf = header.to_leaf(&header.ratifications_root())?;
159            assert_eq!(leaf.index(), 3);
160            check_path(header.to_path(&leaf)?, root, &leaf)?;
161
162            // Check the 4th leaf.
163            let leaf = header.to_leaf(&header.solutions_root())?;
164            assert_eq!(leaf.index(), 4);
165            check_path(header.to_path(&leaf)?, root, &leaf)?;
166
167            // Check the 5th leaf.
168            let leaf = header.to_leaf(&header.subdag_root())?;
169            assert_eq!(leaf.index(), 5);
170            check_path(header.to_path(&leaf)?, root, &leaf)?;
171
172            // Check the 7th leaf.
173            let leaf = header.to_leaf(&CurrentNetwork::hash_bhp1024(&header.metadata().to_bits_le())?)?;
174            assert_eq!(leaf.index(), 7);
175            check_path(header.to_path(&leaf)?, root, &leaf)?;
176        }
177
178        Ok(())
179    }
180}
snarkvm_ledger_block/header/merkle.rs

snarkvm_ledger_block/header/
merkle.rs
