feat: Versionable Merkle metadata (FuelLabs#1639)

Related issues: - FuelLabs#1552 --------- Co-authored-by: Matt <54373384 [email protected]>
cryptoxyz1 · Jan 31, 2024 · bc8780c · bc8780c
1 parent e128814
commit bc8780c
Show file tree

Hide file tree

Showing 4 changed files with 98 additions and 20 deletions.
diff --git a/CHANGELOG.md b/CHANGELOG.md
@@ -25,6  25,7 @@ Description of the upcoming release here.
 - [#1601](https://github.com/FuelLabs/fuel-core/pull/1601): Fix formatting in docs and check that `cargo doc` passes in the CI.
 
 #### Breaking
 - [#1639](https://github.com/FuelLabs/fuel-core/pull/1639): Make Merkle metadata, i.e. `SparseMerkleMetadata` and `DenseMerkleMetadata` type version-able enums
 - [#16232](https://github.com/FuelLabs/fuel-core/pull/1632): Make `Message` type a version-able enum
 - [#1628](https://github.com/FuelLabs/fuel-core/pull/1628): Make `CompressedCoin` type a version-able enum
 - [#1616](https://github.com/FuelLabs/fuel-core/pull/1616): Make `BlockHeader` type a version-able enum

diff --git a/crates/fuel-core/src/database/block.rs b/crates/fuel-core/src/database/block.rs
@@ -119,14  119,14 @@ impl StorageMutate<FuelBlocks> for Database {
 
         let storage = self.borrow_mut();
         let mut tree: MerkleTree<FuelBlockMerkleData, _> =
-            MerkleTree::load(storage, prev_metadata.version)
             MerkleTree::load(storage, prev_metadata.version())
                 .map_err(|err| StorageError::Other(anyhow::anyhow!(err)))?;
         tree.push(block_id.as_slice())?;
 
         // Generate new metadata for the updated tree
-        let version = tree.leaves_count();
         let root = tree.root();
-        let metadata = DenseMerkleMetadata { version, root };
         let version = tree.leaves_count();
         let metadata = DenseMerkleMetadata::new(root, version);
         self.storage::<FuelBlockMerkleMetadata>()
             .insert(height, &metadata)?;
 
@@ -222,7  222,7 @@ impl MerkleRootStorage<BlockHeight, FuelBlocks> for Database {
             .storage::<FuelBlockMerkleMetadata>()
             .get(key)?
             .ok_or(not_found!(FuelBlocks))?;
-        Ok(metadata.root)
         Ok(*metadata.root())
     }
 }
 
@@ -250,11  250,11 @@ impl Database {
 
         let storage = self;
         let tree: MerkleTree<FuelBlockMerkleData, _> =
-            MerkleTree::load(storage, commit_merkle_metadata.version)
             MerkleTree::load(storage, commit_merkle_metadata.version())
                 .map_err(|err| StorageError::Other(anyhow::anyhow!(err)))?;
 
         let proof_index = message_merkle_metadata
-            .version
             .version()
             .checked_sub(1)
             .ok_or(anyhow::anyhow!("The count of leafs - messages is zero"))?;
         let (_, proof_set) = tree

diff --git a/crates/storage/src/blueprint/sparse.rs b/crates/storage/src/blueprint/sparse.rs
@@ -104,7  104,7 @@ where
             .get(primary_key)?
             .unwrap_or_default();
 
-        let root = prev_metadata.root;
         let root = *prev_metadata.root();
         let mut tree: MerkleTree<Nodes, _> = MerkleTree::load(&mut storage, &root)
             .map_err(|err| StorageError::Other(anyhow::anyhow!("{err:?}")))?;
 
@@ -113,7  113,7 @@ where
 
         // Generate new metadata for the updated tree
         let root = tree.root();
-        let metadata = SparseMerkleMetadata { root };
         let metadata = SparseMerkleMetadata::new(root);
         storage
             .storage::<Metadata>()
             .insert(primary_key, &metadata)?;
@@ -138,7  138,7 @@ where
             storage.storage::<Metadata>().get(primary_key)?;
 
         if let Some(prev_metadata) = prev_metadata {
-            let root = prev_metadata.root;
             let root = *prev_metadata.root();
 
             let mut tree: MerkleTree<Nodes, _> = MerkleTree::load(&mut storage, &root)
                 .map_err(|err| StorageError::Other(anyhow::anyhow!("{err:?}")))?;
@@ -152,7  152,7 @@ where
                 storage.storage::<Metadata>().remove(primary_key)?;
             } else {
                 // Generate new metadata for the updated tree
-                let metadata = SparseMerkleMetadata { root };
                 let metadata = SparseMerkleMetadata::new(root);
                 storage
                     .storage::<Metadata>()
                     .insert(primary_key, &metadata)?;
@@ -259,7  259,7 @@ where
         let metadata: Option<Cow<SparseMerkleMetadata>> =
             self.storage_as_ref::<Metadata>().get(key)?;
         let root = metadata
-            .map(|metadata| metadata.root)
             .map(|metadata| *metadata.root())
             .unwrap_or_else(|| in_memory::MerkleTree::new().root());
         Ok(root)
     }
@@ -346,7  346,7 @@ where
         });
         storage.as_mut().batch_write(&mut nodes)?;
 
-        let metadata = SparseMerkleMetadata { root };
         let metadata = SparseMerkleMetadata::new(root);
         storage
             .storage::<Metadata>()
             .insert(primary_key, &metadata)?;
@@ -379,7  379,7 @@ where
             .get(primary_key)?
             .unwrap_or_default();
 
-        let root = prev_metadata.root;
         let root = *prev_metadata.root();
         let mut tree: MerkleTree<Nodes, _> = MerkleTree::load(&mut storage, &root)
             .map_err(|err| StorageError::Other(anyhow::anyhow!("{err:?}")))?;
 
@@ -404,7  404,7 @@ where
         )?;
 
         // Generate new metadata for the updated tree
-        let metadata = SparseMerkleMetadata { root };
         let metadata = SparseMerkleMetadata::new(root);
         storage
             .storage::<Metadata>()
             .insert(primary_key, &metadata)?;
@@ -436,7  436,7 @@ where
             .get(primary_key)?
             .unwrap_or_default();
 
-        let root = prev_metadata.root;
         let root = *prev_metadata.root();
         let mut tree: MerkleTree<Nodes, _> = MerkleTree::load(&mut storage, &root)
             .map_err(|err| StorageError::Other(anyhow::anyhow!("{err:?}")))?;
 
@@ -461,7  461,7 @@ where
             storage.storage::<Metadata>().remove(primary_key)?;
         } else {
             // Generate new metadata for the updated tree
-            let metadata = SparseMerkleMetadata { root };
             let metadata = SparseMerkleMetadata::new(root);
             storage
                 .storage::<Metadata>()
                 .insert(primary_key, &metadata)?;

diff --git a/crates/storage/src/tables.rs b/crates/storage/src/tables.rs
@@ -148,7  148,43 @@ pub mod merkle {
 
     /// Metadata for dense Merkle trees
     #[derive(Debug, Clone, serde::Serialize, serde::Deserialize, PartialEq, Eq)]
-    pub struct DenseMerkleMetadata {
     pub enum DenseMerkleMetadata {
         /// V1 Dense Merkle Metadata
         V1(DenseMerkleMetadataV1),
     }
 
     impl Default for DenseMerkleMetadata {
         fn default() -> Self {
             Self::V1(Default::default())
         }
     }
 
     impl DenseMerkleMetadata {
         /// Create a new dense Merkle metadata object from the given Merkle
         /// root and version
         pub fn new(root: MerkleRoot, version: u64) -> Self {
             let metadata = DenseMerkleMetadataV1 { root, version };
             Self::V1(metadata)
         }
 
         /// Get the Merkle root of the dense Metadata
         pub fn root(&self) -> &MerkleRoot {
             match self {
                 DenseMerkleMetadata::V1(metadata) => &metadata.root,
             }
         }
 
         /// Get the version of the dense Metadata
         pub fn version(&self) -> u64 {
             match self {
                 DenseMerkleMetadata::V1(metadata) => metadata.version,
             }
         }
     }
 
     /// Metadata for dense Merkle trees
     #[derive(Debug, Clone, serde::Serialize, serde::Deserialize, PartialEq, Eq)]
     pub struct DenseMerkleMetadataV1 {
         /// The root hash of the dense Merkle tree structure
         pub root: MerkleRoot,
         /// The version of the dense Merkle tree structure is equal to the number of
@@ -157,7  193,7 @@ pub mod merkle {
         pub version: u64,
     }
 
-    impl Default for DenseMerkleMetadata {
     impl Default for DenseMerkleMetadataV1 {
         fn default() -> Self {
             let empty_merkle_tree = binary::root_calculator::MerkleRootCalculator::new();
             Self {
@@ -167,14  203,49 @@ pub mod merkle {
         }
     }
 
     impl From<DenseMerkleMetadataV1> for DenseMerkleMetadata {
         fn from(value: DenseMerkleMetadataV1) -> Self {
             Self::V1(value)
         }
     }
 
     /// Metadata for sparse Merkle trees
     #[derive(Debug, Clone, serde::Serialize, serde::Deserialize, PartialEq, Eq)]
-    pub struct SparseMerkleMetadata {
     pub enum SparseMerkleMetadata {
         /// V1 Sparse Merkle Metadata
         V1(SparseMerkleMetadataV1),
     }
 
     impl Default for SparseMerkleMetadata {
         fn default() -> Self {
             Self::V1(Default::default())
         }
     }
 
     impl SparseMerkleMetadata {
         /// Create a new sparse Merkle metadata object from the given Merkle
         /// root
         pub fn new(root: MerkleRoot) -> Self {
             let metadata = SparseMerkleMetadataV1 { root };
             Self::V1(metadata)
         }
 
         /// Get the Merkle root stored in the metadata
         pub fn root(&self) -> &MerkleRoot {
             match self {
                 SparseMerkleMetadata::V1(metadata) => &metadata.root,
             }
         }
     }
 
     /// Metadata V1 for sparse Merkle trees
     #[derive(Debug, Clone, serde::Serialize, serde::Deserialize, PartialEq, Eq)]
     pub struct SparseMerkleMetadataV1 {
         /// The root hash of the sparse Merkle tree structure
         pub root: MerkleRoot,
     }
 
-    impl Default for SparseMerkleMetadata {
     impl Default for SparseMerkleMetadataV1 {
         fn default() -> Self {
             let empty_merkle_tree = sparse::in_memory::MerkleTree::new();
             Self {
@@ -183,6  254,12 @@ pub mod merkle {
         }
     }
 
     impl From<SparseMerkleMetadataV1> for SparseMerkleMetadata {
         fn from(value: SparseMerkleMetadataV1) -> Self {
             Self::V1(value)
         }
     }
 
     /// The table of BMT data for Fuel blocks.
     pub struct FuelBlockMerkleData;