From 3055a7d7e35aa206fe4b30a6ee390a56fa293de6 Mon Sep 17 00:00:00 2001 From: Victor Dumitrescu Date: Thu, 23 Jan 2025 17:25:32 +0100 Subject: [PATCH] RISC-V: Remove Merkleisable trait --- src/riscv/lib/src/cache_utils.rs | 4 +- .../lib/src/machine_state/block_cache.rs | 6 +- .../src/machine_state/csregisters/values.rs | 16 +- .../lib/src/machine_state/main_memory.rs | 28 +-- src/riscv/lib/src/state_backend/layout.rs | 20 +- .../lib/src/state_backend/proof_backend.rs | 173 +++++++++--------- .../src/state_backend/proof_backend/merkle.rs | 165 +++++------------ .../lib/src/state_backend/proof_layout.rs | 64 +++---- src/riscv/lib/src/state_backend/region.rs | 57 +----- src/riscv/lib/src/stepper/pvm.rs | 2 +- 10 files changed, 180 insertions(+), 355 deletions(-) diff --git a/src/riscv/lib/src/cache_utils.rs b/src/riscv/lib/src/cache_utils.rs index 5facfd7d0c99..a8acd17aa1dd 100644 --- a/src/riscv/lib/src/cache_utils.rs +++ b/src/riscv/lib/src/cache_utils.rs @@ -101,10 +101,10 @@ impl Commi impl ProofLayout for Sizes { - fn to_proof( + fn to_merkle_tree( state: crate::state_backend::RefProofGenOwnedAlloc, ) -> Result { - Many::::to_proof(state) + Many::::to_merkle_tree(state) } fn from_proof(proof: ProofTree) -> FromProofResult { diff --git a/src/riscv/lib/src/machine_state/block_cache.rs b/src/riscv/lib/src/machine_state/block_cache.rs index d9ba93354ff0..af9086d631c1 100644 --- a/src/riscv/lib/src/machine_state/block_cache.rs +++ b/src/riscv/lib/src/machine_state/block_cache.rs @@ -127,7 +127,7 @@ impl state_backend::CommitmentLayout for ICallLayout { } impl state_backend::ProofLayout for ICallLayout { - fn to_proof( + fn to_merkle_tree( state: state_backend::RefProofGenOwnedAlloc, ) -> Result { let cell = state.cell_ref(); @@ -218,10 +218,10 @@ impl state_backend::CommitmentLayout for AddressCellLayout { } impl state_backend::ProofLayout for AddressCellLayout { - fn to_proof( + fn to_merkle_tree( state: state_backend::RefProofGenOwnedAlloc, ) -> Result { - as state_backend::ProofLayout>::to_proof(state) + as state_backend::ProofLayout>::to_merkle_tree(state) } fn from_proof(proof: state_backend::ProofTree) -> state_backend::FromProofResult { diff --git a/src/riscv/lib/src/machine_state/csregisters/values.rs b/src/riscv/lib/src/machine_state/csregisters/values.rs index ae249544af52..049625d1e252 100644 --- a/src/riscv/lib/src/machine_state/csregisters/values.rs +++ b/src/riscv/lib/src/machine_state/csregisters/values.rs @@ -17,7 +17,7 @@ use crate::{ state_backend::{ hash::{Hash, HashError}, owned_backend::Owned, - proof_backend::merkle::{MerkleTree, Merkleisable}, + proof_backend::merkle::MerkleTree, verify_backend, AllocatedOf, Cell, CommitmentLayout, EffectCell, EffectCellLayout, FnManager, FromProofResult, Layout, ManagerAlloc, ManagerBase, ManagerRead, ManagerReadWrite, ManagerWrite, ProofLayout, ProofPart, ProofTree, Ref, RefOwnedAlloc, @@ -164,7 +164,7 @@ impl CommitmentLayout for CSRValuesLayout { } impl ProofLayout for CSRValuesLayout { - fn to_proof(state: RefProofGenOwnedAlloc) -> Result { + fn to_merkle_tree(state: RefProofGenOwnedAlloc) -> Result { let serialised = binary::serialise(&state)?; MerkleTree::make_merkle_leaf(serialised, state.aggregate_access_info()) } @@ -1467,18 +1467,6 @@ impl CSRValuesF { } } -impl Merkleisable for CSRValuesF -where - Raw: AccessInfoAggregatable + serde::Serialize, - MStatus: AccessInfoAggregatable + serde::Serialize, - MIP: AccessInfoAggregatable + serde::Serialize, -{ - fn to_merkle_tree(&self) -> Result { - let serialised = binary::serialise(&self)?; - MerkleTree::make_merkle_leaf(serialised, self.aggregate_access_info()) - } -} - impl AccessInfoAggregatable for CSRValuesF where Raw: AccessInfoAggregatable + serde::Serialize, diff --git a/src/riscv/lib/src/machine_state/main_memory.rs b/src/riscv/lib/src/machine_state/main_memory.rs index c5db4281d071..82108e4dd9ef 100644 --- a/src/riscv/lib/src/machine_state/main_memory.rs +++ b/src/riscv/lib/src/machine_state/main_memory.rs @@ -5,15 +5,7 @@ use crate::{ machine_state::registers::XValue, - state_backend::{ - self as backend, - hash::HashError, - proof_backend::{ - merkle::{MerkleTree, Merkleisable}, - ProofGen, - }, - ManagerDeserialise, ManagerSerialise, Ref, - }, + state_backend::{self as backend, ManagerDeserialise, ManagerSerialise}, }; use serde::{Deserialize, Serialize}; use std::mem; @@ -115,10 +107,6 @@ pub trait MainMemoryLayout: backend::ProofLayout + backend::CommitmentLayout + ' /// Clone the dynamic region. fn clone_data(data: &Self::Allocated) -> Self::Allocated; - - fn to_merkle_tree( - data: &Self::Allocated>>, - ) -> Result; } impl MainMemoryLayout for backend::DynArray { @@ -177,12 +165,6 @@ impl MainMemoryLayout for backend::DynArray { fn clone_data(data: &Self::Allocated) -> Self::Allocated { data.clone() } - - fn to_merkle_tree( - data: &Self::Allocated>>, - ) -> Result { - data.to_merkle_tree() - } } /// Main memory state for the given layout @@ -307,14 +289,6 @@ where } } -impl Merkleisable - for MainMemory>> -{ - fn to_merkle_tree(&self) -> Result { - L::to_merkle_tree(&self.data) - } -} - impl Clone for MainMemory { fn clone(&self) -> Self { Self { diff --git a/src/riscv/lib/src/state_backend/layout.rs b/src/riscv/lib/src/state_backend/layout.rs index 37fb65c5b5a2..c0233f3c6722 100644 --- a/src/riscv/lib/src/state_backend/layout.rs +++ b/src/riscv/lib/src/state_backend/layout.rs @@ -127,25 +127,9 @@ macro_rules! struct_layout { } use $crate::state_backend::proof_backend::merkle::{ - AccessInfo, AccessInfoAggregatable, MerkleTree, Merkleisable, + AccessInfo, AccessInfoAggregatable, MerkleTree, }; - impl < - $( - [<$field_name:upper>]: AccessInfoAggregatable + serde::Serialize - ),+ - > Merkleisable for [<$layout_t F>]< - $( - [<$field_name:upper>] - ),+ - > { - fn to_merkle_tree(&self) -> Result - { - let serialised = $crate::storage::binary::serialise(&self)?; - MerkleTree::make_merkle_leaf(serialised, self.aggregate_access_info()) - } - } - impl < $( [<$field_name:upper>]: AccessInfoAggregatable + serde::Serialize @@ -173,7 +157,7 @@ macro_rules! struct_layout { } impl $crate::state_backend::ProofLayout for $layout_t { - fn to_proof(state: $crate::state_backend::RefProofGenOwnedAlloc) -> + fn to_merkle_tree(state: $crate::state_backend::RefProofGenOwnedAlloc) -> Result<$crate::state_backend::proof_backend::merkle::MerkleTree, $crate::storage::HashError> { let serialised = $crate::storage::binary::serialise(&state)?; MerkleTree::make_merkle_leaf(serialised, state.aggregate_access_info()) diff --git a/src/riscv/lib/src/state_backend/proof_backend.rs b/src/riscv/lib/src/state_backend/proof_backend.rs index d286e9435276..5c17c5f72cbe 100644 --- a/src/riscv/lib/src/state_backend/proof_backend.rs +++ b/src/riscv/lib/src/state_backend/proof_backend.rs @@ -1,4 +1,4 @@ -// SPDX-FileCopyrightText: 2024 Nomadic Labs +// SPDX-FileCopyrightText: 2024-2025 Nomadic Labs // // SPDX-License-Identifier: MIT @@ -421,93 +421,95 @@ impl DynAccess { mod tests { use super::*; use crate::state_backend::{ - hash::RootHashable, - owned_backend::Owned, - proof_backend::merkle::Merkleisable, - region::{DynCells, MERKLE_LEAF_SIZE}, - Cells, EnrichedCell, FnManagerIdent, + layout::Array, owned_backend::Owned, region::MERKLE_LEAF_SIZE, Cells, CommitmentLayout, + DynArray, DynCells, ProofLayout, Ref, }; use proptest::{array, prop_assert_eq, proptest}; use std::collections::VecDeque; use tests::merkle::MerkleTree; - const CELLS_SIZE: usize = 255; + const CELLS_SIZE: usize = 32; #[test] fn test_proof_gen_region() { proptest!(|(value_before: u64, value_after: u64, i in 0..CELLS_SIZE)| { // A read followed by a write let cells = [value_before; CELLS_SIZE]; - let mut region: ProofRegion = - ProofRegion::bind(cells); - prop_assert_eq!(region.get_access_info(), AccessInfo::NoAccess); - let value = ProofGen::::region_read(®ion, i); + let region: ProofRegion> = ProofRegion::bind(&cells); + let mut region: Cells>> = Cells::bind(region); + + prop_assert_eq!(region.region_ref().get_access_info(), AccessInfo::NoAccess); + let value = region.read(i); prop_assert_eq!(value, value_before); - prop_assert_eq!(region.get_access_info(), AccessInfo::Read); - ProofGen::::region_write(&mut region, i, value_after); - prop_assert_eq!(region.get_access_info(), AccessInfo::ReadWrite); + prop_assert_eq!(region.region_ref().get_access_info(), AccessInfo::Read); + region.write(i, value_after); + prop_assert_eq!(region.region_ref().get_access_info(), AccessInfo::ReadWrite); // A write followed by a read let cells = [value_before; CELLS_SIZE]; - let mut region: ProofRegion = - ProofRegion::bind(cells); - prop_assert_eq!(region.get_access_info(), AccessInfo::NoAccess); - ProofGen::::region_write(&mut region, i, value_after); - prop_assert_eq!(region.get_access_info(), AccessInfo::Write); - let value = ProofGen::::region_read(®ion, i); + let region: ProofRegion> = ProofRegion::bind(&cells); + let mut region: Cells>> = Cells::bind(region); + prop_assert_eq!(region.region_ref().get_access_info(), AccessInfo::NoAccess); + region.write(i, value_after); + prop_assert_eq!(region.region_ref().get_access_info(), AccessInfo::Write); + let value = region.read(i); prop_assert_eq!(value, value_after); - prop_assert_eq!(region.get_access_info(), AccessInfo::ReadWrite); + prop_assert_eq!(region.region_ref().get_access_info(), AccessInfo::ReadWrite); // Replace let cells = [value_before; CELLS_SIZE]; - let mut region: ProofRegion = - ProofRegion::bind(cells); - prop_assert_eq!(region.get_access_info(), AccessInfo::NoAccess); - let value = ProofGen::::region_replace(&mut region, i, value_after); + let region: ProofRegion> = ProofRegion::bind(&cells); + let mut region: Cells>> = Cells::bind(region); + prop_assert_eq!(region.region_ref().get_access_info(), AccessInfo::NoAccess); + let value = region.replace(i, value_after); prop_assert_eq!(value, value_before); - prop_assert_eq!(region.get_access_info(), AccessInfo::ReadWrite); + prop_assert_eq!(region.region_ref().get_access_info(), AccessInfo::ReadWrite); let data_before = [value_before; CELLS_SIZE]; let data_after = [value_after; CELLS_SIZE]; // A read_all followed by a write_all let cells = data_before; - let mut region: ProofRegion = - ProofRegion::bind(cells); - prop_assert_eq!(region.get_access_info(), AccessInfo::NoAccess); - let values = ProofGen::::region_read_all(®ion); + let region: ProofRegion> = ProofRegion::bind(&cells); + let mut region: Cells>> = Cells::bind(region); + prop_assert_eq!(region.region_ref().get_access_info(), AccessInfo::NoAccess); + let values = region.read_all(); prop_assert_eq!(values.as_slice(), data_before); - prop_assert_eq!(region.get_access_info(), AccessInfo::Read); - ProofGen::::region_write_all(&mut region, &data_after); - prop_assert_eq!(region.get_access_info(), AccessInfo::ReadWrite); + prop_assert_eq!(region.region_ref().get_access_info(), AccessInfo::Read); + region.write_all(&data_after); + prop_assert_eq!(region.region_ref().get_access_info(), AccessInfo::ReadWrite); // A write_all followed by a read_all let cells = data_before; - let mut region: ProofRegion = - ProofRegion::bind(cells); - prop_assert_eq!(region.get_access_info(), AccessInfo::NoAccess); - ProofGen::::region_write_all(&mut region, &data_after); - prop_assert_eq!(region.get_access_info(), AccessInfo::Write); - let values = ProofGen::::region_read_all(®ion); + let region: ProofRegion> = ProofRegion::bind(&cells); + let mut region: Cells>> = Cells::bind(region); + prop_assert_eq!(region.region_ref().get_access_info(), AccessInfo::NoAccess); + region.write_all(&data_after); + prop_assert_eq!(region.region_ref().get_access_info(), AccessInfo::Write); + let values = region.read_all(); prop_assert_eq!(values.as_slice(), data_after); - prop_assert_eq!(region.get_access_info(), AccessInfo::ReadWrite); + prop_assert_eq!(region.region_ref().get_access_info(), AccessInfo::ReadWrite); // Check correct Merkleisation let cells = [value_before; CELLS_SIZE]; - let region: ProofRegion = ProofRegion::bind(cells); - let mut cells: Cells> = Cells::bind(region); - let initial_root_hash = cells.hash().unwrap(); - cells.write(i, value_after); - prop_assert_eq!(cells.hash().unwrap(), initial_root_hash); - let merkle_tree = cells.struct_ref::() - .to_merkle_tree() - .unwrap(); - + let cells_owned: Cells> = Cells::bind(&cells); + let initial_root_hash = + as CommitmentLayout>::state_hash(cells_owned).unwrap(); + + let mut proof_region: ProofRegion> = + ProofRegion::bind(&cells); + ProofGen::>::region_write(&mut proof_region, i, value_after); + let proof_cells: Cells>>> = + Cells::bind(&proof_region); + + let merkle_tree = + as ProofLayout>::to_merkle_tree(proof_cells).unwrap(); + merkle_tree.check_root_hash(); match merkle_tree { MerkleTree::Leaf(hash, access_info, _) => { prop_assert_eq!(hash, initial_root_hash); prop_assert_eq!(access_info, AccessInfo::Write); - }, + } _ => panic!("Expected Merkle tree to contain a single written leaf"), } }); @@ -588,31 +590,38 @@ mod tests { bytes_after: [u8; ELEM_SIZE], reads in array::uniform2(&address_range), writes in array::uniform2(&address_range))| { - let region = Box::new([byte_before; DYN_REGION_SIZE]); - let dyn_region: ProofDynRegion = - ProofDynRegion::bind(region.clone()); - let mut dyn_cells: DynCells> = - DynCells::bind(dyn_region); + let dyn_array = Box::new([byte_before; DYN_REGION_SIZE]); + let owned_dyn_cells: DynCells> = + DynCells::bind(&dyn_array); + let initial_root_hash = + as CommitmentLayout>::state_hash(owned_dyn_cells) + .unwrap(); + + let mut proof_dyn_region: ProofDynRegion> = + ProofDynRegion::bind(&dyn_array); // Perform memory accesses let value_before = [byte_before; ELEM_SIZE]; reads.iter().for_each(|i| { let mut value = [0u8; ELEM_SIZE]; - dyn_cells.read_all(*i, &mut value); + ProofGen::>::dyn_region_read_all(&proof_dyn_region, *i, &mut value); assert_eq!(value, value_before) }); writes.iter().for_each(|i| { - dyn_cells.write_all(*i, &bytes_after); + ProofGen::>::dyn_region_write_all( + &mut proof_dyn_region, + *i, + &bytes_after, + ); }); // Build the Merkle tree and check that it has the root hash of the // initial wrapped region. - let merkle_tree = dyn_cells - .struct_ref::() - .to_merkle_tree() - .unwrap(); - let cells: DynCells = DynCells::bind(region); - let initial_root_hash = cells.hash().unwrap(); + let proof_dyn_cells: DynCells>>> = + DynCells::bind(&proof_dyn_region); + let merkle_tree = + as ProofLayout>::to_merkle_tree(proof_dyn_cells).unwrap(); + merkle_tree.check_root_hash(); prop_assert_eq!(merkle_tree.root_hash(), initial_root_hash); // Compute expected access info for each leaf, assuming that an access @@ -671,47 +680,29 @@ mod tests { proptest!(|(value_before: u64, value_after: u64)| { // A read followed by a write let cell = (value_before, T::from(&value_before)); - let mut proof_cell: ProofEnrichedCell = ProofEnrichedCell::bind(cell); + let mut proof_cell: ProofEnrichedCell> = + ProofEnrichedCell::bind(&cell); prop_assert_eq!(proof_cell.get_access_info(), AccessInfo::NoAccess); - let value = ProofGen::::enriched_cell_read_stored(&proof_cell); + let value = ProofGen::>::enriched_cell_read_stored(&proof_cell); prop_assert_eq!(value, value_before); - let derived = ProofGen::::enriched_cell_read_derived(&proof_cell); + let derived = ProofGen::>::enriched_cell_read_derived(&proof_cell); prop_assert_eq!(derived, T::from(&value_before)); prop_assert_eq!(proof_cell.get_access_info(), AccessInfo::Read); - ProofGen::::enriched_cell_write(&mut proof_cell, value_after); + ProofGen::>::enriched_cell_write(&mut proof_cell, value_after); prop_assert_eq!(proof_cell.get_access_info(), AccessInfo::ReadWrite); // A write followed by a read let cell = (value_before, T::from(&value_before)); - let mut proof_cell: ProofEnrichedCell = ProofEnrichedCell::bind(cell); + let mut proof_cell: ProofEnrichedCell> = + ProofEnrichedCell::bind(&cell); prop_assert_eq!(proof_cell.get_access_info(), AccessInfo::NoAccess); - ProofGen::::enriched_cell_write(&mut proof_cell, value_after); + ProofGen::>::enriched_cell_write(&mut proof_cell, value_after); prop_assert_eq!(proof_cell.get_access_info(), AccessInfo::Write); - let value = ProofGen::::enriched_cell_read_stored(&proof_cell); + let value = ProofGen::>::enriched_cell_read_stored(&proof_cell); prop_assert_eq!(value, value_after); - let derived = ProofGen::::enriched_cell_read_derived(&proof_cell); + let derived = ProofGen::>::enriched_cell_read_derived(&proof_cell); prop_assert_eq!(derived, T::from(&value_after)); prop_assert_eq!(proof_cell.get_access_info(), AccessInfo::ReadWrite); - - // Check correct Merkleisation - let cell = (value_before, T::from(&value_before)); - let proof_cell: ProofEnrichedCell = ProofEnrichedCell::bind(cell); - let mut proof_cell: EnrichedCell> = - EnrichedCell::bind(proof_cell); - let initial_root_hash = proof_cell.hash().unwrap(); - proof_cell.write(value_after); - prop_assert_eq!(proof_cell.hash().unwrap(), initial_root_hash); - let merkle_tree = proof_cell - .struct_ref::() - .to_merkle_tree() - .unwrap(); - match merkle_tree { - MerkleTree::Leaf(hash, access_info, _) => { - prop_assert_eq!(hash, initial_root_hash); - prop_assert_eq!(access_info, AccessInfo::Write); - } - _ => panic!("Expected Merkle tree to contain a single written leaf"), - } }); } } diff --git a/src/riscv/lib/src/state_backend/proof_backend/merkle.rs b/src/riscv/lib/src/state_backend/proof_backend/merkle.rs index e948c2efee1f..7ec801326b82 100644 --- a/src/riscv/lib/src/state_backend/proof_backend/merkle.rs +++ b/src/riscv/lib/src/state_backend/proof_backend/merkle.rs @@ -8,12 +8,9 @@ use super::{ proof::{MerkleProof, MerkleProofLeaf}, DynAccess, }; -use crate::{ - state_backend::{ - hash::{Hash, HashError, RootHashable}, - proof_backend::tree::{impl_modify_map_collect, ModifyResult}, - }, - storage::binary, +use crate::state_backend::{ + hash::{Hash, HashError, RootHashable}, + proof_backend::tree::{impl_modify_map_collect, ModifyResult}, }; use std::convert::Infallible; @@ -237,12 +234,6 @@ enum CompressedAccessInfo { ReadWrite(Vec), } -// TODO: RV-414: Remove `Merkleisable` trait -pub trait Merkleisable { - /// Build the Merkle tree described by the layouat of the data. - fn to_merkle_tree(&self) -> Result; -} - pub trait AccessInfoAggregatable { /// Aggregate the access information of the Merkle tree described by /// the layout of the given data, without constructing the tree. @@ -252,17 +243,6 @@ pub trait AccessInfoAggregatable { fn aggregate_access_info(&self) -> AccessInfo; } -impl Merkleisable for [T] { - fn to_merkle_tree(&self) -> Result { - let children = self - .iter() - .map(|e| e.to_merkle_tree()) - .collect::, _>>()?; - - Ok(MerkleTree::Node(children.hash()?, children)) - } -} - impl AccessInfoAggregatable for [T] { fn aggregate_access_info(&self) -> AccessInfo { let mut acc = AccessInfo::NoAccess; @@ -276,55 +256,26 @@ impl AccessInfoAggregatable for [T] { } } -impl Merkleisable for Vec { - fn to_merkle_tree(&self) -> Result { - self.as_slice().to_merkle_tree() - } -} - impl AccessInfoAggregatable for Vec { fn aggregate_access_info(&self) -> AccessInfo { self.as_slice().aggregate_access_info() } } -impl Merkleisable for [T; N] { - fn to_merkle_tree(&self) -> Result { - self.as_slice().to_merkle_tree() - } -} - impl AccessInfoAggregatable for [T; N] { fn aggregate_access_info(&self) -> AccessInfo { self.as_slice().aggregate_access_info() } } -impl Merkleisable for () { - fn to_merkle_tree(&self) -> Result { - let serialised = binary::serialise(self)?; - MerkleTree::make_merkle_leaf(serialised, AccessInfo::NoAccess) - } -} - impl AccessInfoAggregatable for () { fn aggregate_access_info(&self) -> AccessInfo { AccessInfo::NoAccess } } -macro_rules! impl_merkleisable_for_tuple { +macro_rules! impl_aggregatable_for_tuple { ($($name:ident),*) => { - impl<$($name: Merkleisable),*> Merkleisable for ($($name,)*) { - fn to_merkle_tree(&self) -> Result { - #[allow(non_snake_case)] - let ($($name,)*) = self; - let children: Result, HashError> = [$($name.to_merkle_tree(),)*].into_iter().collect(); - let children = children?; - Ok(MerkleTree::Node(children.hash()?, children)) - } - } - impl<$($name: AccessInfoAggregatable),*> AccessInfoAggregatable for ($($name,)*) { fn aggregate_access_info(&self) -> AccessInfo { #[allow(non_snake_case)] @@ -336,11 +287,11 @@ macro_rules! impl_merkleisable_for_tuple { } } -impl_merkleisable_for_tuple!(A, B); -impl_merkleisable_for_tuple!(A, B, C); -impl_merkleisable_for_tuple!(A, B, C, D); -impl_merkleisable_for_tuple!(A, B, C, D, E); -impl_merkleisable_for_tuple!(A, B, C, D, E, F); +impl_aggregatable_for_tuple!(A, B); +impl_aggregatable_for_tuple!(A, B, C); +impl_aggregatable_for_tuple!(A, B, C, D); +impl_aggregatable_for_tuple!(A, B, C, D, E); +impl_aggregatable_for_tuple!(A, B, C, D, E, F); /// Writer which splits data in fixed-sized chunks and produces a [`MerkleTree`] /// with a given arity in which each leaf represents a chunk. @@ -452,48 +403,51 @@ impl std::io::Write for MerkleWriter { } } +impl MerkleTree { + /// Check the validity of the Merkle root by recomputing all hashes + #[cfg(test)] + pub fn check_root_hash(&self) -> bool { + let mut deque = std::collections::VecDeque::new(); + deque.push_back(self); + + while let Some(node) = deque.pop_front() { + let is_valid_hash = match node { + Self::Leaf(hash, _, data) => { + Hash::blake2b_hash_bytes(data).is_ok_and(|h| h == *hash) + } + Self::Node(hash, children) => { + // TODO RV-250: Instead of building the whole input and + // hashing it, we should use incremental hashing, which + // isn't currently supported in `tezos_crypto_rs`. + // + // Check the hash of this node and push children to deque to be checked + let mut hashes: Vec = Vec::with_capacity( + crate::state_backend::hash::DIGEST_SIZE * children.len(), + ); + children.iter().for_each(|child| { + deque.push_back(child); + hashes.extend_from_slice(child.root_hash().as_ref()) + }); + Hash::blake2b_hash_bytes(&hashes).is_ok_and(|h| h == *hash) + } + }; + if !is_valid_hash { + return false; + } + } + true + } +} + #[cfg(test)] mod tests { - use super::{AccessInfo, CompressedAccessInfo, CompressedMerkleTree, MerkleTree, Merkleisable}; + use super::{AccessInfo, CompressedAccessInfo, CompressedMerkleTree, MerkleTree}; use crate::state_backend::{ hash::{Hash, HashError, RootHashable, DIGEST_SIZE}, proof_backend::proof::{MerkleProof, MerkleProofLeaf}, }; use proptest::prelude::*; - impl MerkleTree { - /// Check the validity of the Merkle root by recomputing all hashes - fn check_root_hash(&self) -> bool { - let mut deque = std::collections::VecDeque::new(); - deque.push_back(self); - - while let Some(node) = deque.pop_front() { - let is_valid_hash = match node { - Self::Leaf(hash, _, data) => { - Hash::blake2b_hash_bytes(data).is_ok_and(|h| h == *hash) - } - Self::Node(hash, children) => { - // TODO RV-250: Instead of building the whole input and - // hashing it, we should use incremental hashing, which - // isn't currently supported in `tezos_crypto_rs`. - // - // Check the hash of this node and push children to deque to be checked - let mut hashes: Vec = Vec::with_capacity(DIGEST_SIZE * children.len()); - children.iter().for_each(|child| { - deque.push_back(child); - hashes.extend_from_slice(child.root_hash().as_ref()) - }); - Hash::blake2b_hash_bytes(&hashes).is_ok_and(|h| h == *hash) - } - }; - if !is_valid_hash { - return false; - } - } - true - } - } - impl CompressedMerkleTree { /// Get the root hash of a compreessed Merkle tree fn root_hash(&self) -> Hash { @@ -539,17 +493,6 @@ mod tests { } } - impl Merkleisable for &Vec { - fn to_merkle_tree(&self) -> Result { - let hash = Hash::blake2b_hash_bytes(self)?; - Ok(MerkleTree::Leaf( - hash, - AccessInfo::NoAccess, - (*self).clone(), - )) - } - } - impl RootHashable for Vec { fn hash(&self) -> Result { Hash::blake2b_hash_bytes(self) @@ -566,22 +509,6 @@ mod tests { Ok(MerkleTree::Node(hash, vec![left, right])) } - #[test] - fn test_merkle_tree() { - proptest!(| - (leaves in prop::collection::vec( - prop::collection::vec(0u8..255, 0..100), - 6) - )| { - let state = ((&leaves[0], (&leaves[1], &leaves[2])), ((&leaves[3], &leaves[4]), &leaves[5])); - let tree = state - .to_merkle_tree() - .expect("Error building Merkle tree"); - assert!(tree.check_root_hash()); - assert!(tree.root_hash() == state.hash()?); - }); - } - #[test] fn test_compression() { let test = |l: Vec>| -> Result<_, HashError> { diff --git a/src/riscv/lib/src/state_backend/proof_layout.rs b/src/riscv/lib/src/state_backend/proof_layout.rs index e30f8752011f..08fdb1a8944c 100644 --- a/src/riscv/lib/src/state_backend/proof_layout.rs +++ b/src/riscv/lib/src/state_backend/proof_layout.rs @@ -114,7 +114,7 @@ impl<'a> ProofTree<'a> { pub trait ProofLayout: Layout { /// Obtain the complete Merkle tree which captures an execution trace /// using the proof-generating backend. - fn to_proof(state: RefProofGenOwnedAlloc) -> Result; + fn to_merkle_tree(state: RefProofGenOwnedAlloc) -> Result; /// Parse a Merkle proof into the allocated form of this layout. fn from_proof(proof: ProofTree) -> FromProofResult; @@ -123,7 +123,7 @@ pub trait ProofLayout: Layout { impl ProofLayout for Atom { - fn to_proof(state: RefProofGenOwnedAlloc) -> Result { + fn to_merkle_tree(state: RefProofGenOwnedAlloc) -> Result { let serialised = binary::serialise(&state)?; MerkleTree::make_merkle_leaf(serialised, state.into_region().get_access_info()) } @@ -137,7 +137,7 @@ impl ProofLayout for Array) -> Result { + fn to_merkle_tree(state: RefProofGenOwnedAlloc) -> Result { // RV-282: Break down into multiple leaves if the size of the `Cells` // is too large for a proof. let serialised = binary::serialise(&state)?; @@ -168,7 +168,7 @@ where } impl ProofLayout for DynArray { - fn to_proof(state: RefProofGenOwnedAlloc) -> Result { + fn to_merkle_tree(state: RefProofGenOwnedAlloc) -> Result { let region = state.region_ref(); let mut writer = MerkleWriter::new( MERKLE_LEAF_SIZE, @@ -242,8 +242,8 @@ where A: ProofLayout, B: ProofLayout, { - fn to_proof(state: RefProofGenOwnedAlloc) -> Result { - let children = vec![A::to_proof(state.0)?, B::to_proof(state.1)?]; + fn to_merkle_tree(state: RefProofGenOwnedAlloc) -> Result { + let children = vec![A::to_merkle_tree(state.0)?, B::to_merkle_tree(state.1)?]; Ok(MerkleTree::Node(children.hash()?, children)) } @@ -259,11 +259,11 @@ where B: ProofLayout, C: ProofLayout, { - fn to_proof(state: RefProofGenOwnedAlloc) -> Result { + fn to_merkle_tree(state: RefProofGenOwnedAlloc) -> Result { let children = vec![ - A::to_proof(state.0)?, - B::to_proof(state.1)?, - C::to_proof(state.2)?, + A::to_merkle_tree(state.0)?, + B::to_merkle_tree(state.1)?, + C::to_merkle_tree(state.2)?, ]; Ok(MerkleTree::Node(children.hash()?, children)) } @@ -281,12 +281,12 @@ where C: ProofLayout, D: ProofLayout, { - fn to_proof(state: RefProofGenOwnedAlloc) -> Result { + fn to_merkle_tree(state: RefProofGenOwnedAlloc) -> Result { let children = vec![ - A::to_proof(state.0)?, - B::to_proof(state.1)?, - C::to_proof(state.2)?, - D::to_proof(state.3)?, + A::to_merkle_tree(state.0)?, + B::to_merkle_tree(state.1)?, + C::to_merkle_tree(state.2)?, + D::to_merkle_tree(state.3)?, ]; Ok(MerkleTree::Node(children.hash()?, children)) } @@ -310,13 +310,13 @@ where D: ProofLayout, E: ProofLayout, { - fn to_proof(state: RefProofGenOwnedAlloc) -> Result { + fn to_merkle_tree(state: RefProofGenOwnedAlloc) -> Result { let children = vec![ - A::to_proof(state.0)?, - B::to_proof(state.1)?, - C::to_proof(state.2)?, - D::to_proof(state.3)?, - E::to_proof(state.4)?, + A::to_merkle_tree(state.0)?, + B::to_merkle_tree(state.1)?, + C::to_merkle_tree(state.2)?, + D::to_merkle_tree(state.3)?, + E::to_merkle_tree(state.4)?, ]; Ok(MerkleTree::Node(children.hash()?, children)) } @@ -342,14 +342,14 @@ where E: ProofLayout, F: ProofLayout, { - fn to_proof(state: RefProofGenOwnedAlloc) -> Result { + fn to_merkle_tree(state: RefProofGenOwnedAlloc) -> Result { let children = vec![ - A::to_proof(state.0)?, - B::to_proof(state.1)?, - C::to_proof(state.2)?, - D::to_proof(state.3)?, - E::to_proof(state.4)?, - F::to_proof(state.5)?, + A::to_merkle_tree(state.0)?, + B::to_merkle_tree(state.1)?, + C::to_merkle_tree(state.2)?, + D::to_merkle_tree(state.3)?, + E::to_merkle_tree(state.4)?, + F::to_merkle_tree(state.5)?, ]; Ok(MerkleTree::Node(children.hash()?, children)) } @@ -371,7 +371,7 @@ impl ProofLayout for [T; LEN] where T: ProofLayout, { - fn to_proof(state: RefProofGenOwnedAlloc) -> Result { + fn to_merkle_tree(state: RefProofGenOwnedAlloc) -> Result { iter_to_proof::<_, T>(state) } @@ -393,7 +393,7 @@ impl ProofLayout for Many where T: ProofLayout, { - fn to_proof(state: RefProofGenOwnedAlloc) -> Result { + fn to_merkle_tree(state: RefProofGenOwnedAlloc) -> Result { iter_to_proof::<_, T>(state) } @@ -401,7 +401,7 @@ where proof .into_branches::()? .into_iter() - .map(|branch| T::from_proof(branch)) + .map(T::from_proof) .collect::, _>>() } } @@ -414,7 +414,7 @@ where { let children = iter .into_iter() - .map(|e| T::to_proof(e)) + .map(T::to_merkle_tree) .collect::, _>>()?; Ok(MerkleTree::Node(children.hash()?, children)) diff --git a/src/riscv/lib/src/state_backend/region.rs b/src/riscv/lib/src/state_backend/region.rs index 440d972bf7a6..5a7b341c5b4f 100644 --- a/src/riscv/lib/src/state_backend/region.rs +++ b/src/riscv/lib/src/state_backend/region.rs @@ -6,13 +6,12 @@ use super::{ hash::{self, Hash, HashError, HashWriter, RootHashable}, proof_backend::{ - merkle::{AccessInfo, AccessInfoAggregatable, MerkleTree, MerkleWriter, Merkleisable}, - ProofDynRegion, ProofEnrichedCell, ProofGen, + merkle::{AccessInfo, AccessInfoAggregatable}, + ProofGen, }, Elem, EnrichedValue, EnrichedValueLinked, FnManager, ManagerBase, ManagerClone, ManagerDeserialise, ManagerRead, ManagerReadWrite, ManagerSerialise, ManagerWrite, Ref, }; -use crate::storage::binary; use std::borrow::Borrow; use std::num::NonZeroUsize; @@ -203,12 +202,6 @@ impl + Copy, B: Copy, M: ManagerRead, N: ManagerRead> PartialEq< } } -impl Merkleisable for Cell>> { - fn to_merkle_tree(&self) -> Result { - self.region.to_merkle_tree() - } -} - impl AccessInfoAggregatable for Cell>> { @@ -338,6 +331,11 @@ impl Cells { } } + /// Obtain a reference to the underlying region. + pub fn region_ref(&self) -> &M::Region { + &self.region + } + /// Obtain the underlying region. pub fn into_region(self) -> M::Region { self.region @@ -423,16 +421,6 @@ where } } -impl Merkleisable for EnrichedCell>> -where - V::E: serde::Serialize, -{ - fn to_merkle_tree(&self) -> Result { - let serialised = ProofEnrichedCell::serialise_inner_enriched_cell(self.cell)?; - MerkleTree::make_merkle_leaf(serialised, self.cell.get_access_info()) - } -} - impl AccessInfoAggregatable for EnrichedCell>> where @@ -483,17 +471,6 @@ impl + Copy, B: Copy, const LEN: usize, M: ManagerRead, N: Manag } } -impl Merkleisable - for Cells>> -{ - fn to_merkle_tree(&self) -> Result { - // RV-282: Break down into multiple leaves if the size of the `Cells` - // is too large for a proof. - let serialised = binary::serialise(&self)?; - MerkleTree::make_merkle_leaf(serialised, self.region.get_access_info()) - } -} - impl AccessInfoAggregatable for Cells>> { @@ -615,9 +592,10 @@ pub const MERKLE_LEAF_SIZE: NonZeroUsize = /// Arity of the Merkle tree used for Merkleising [`DynCells`]. pub const MERKLE_ARITY: usize = 3; +// TODO RV-398: Move to `merkle` once `RootHashable` is removed /// Helper function which allows iterating over chunks of a dynamic region /// and writing them to a writer. The last chunk may be smaller than the -/// Merkle leaf size. The implementations of `RootHashable` and `Merkleisable` +/// Merkle leaf size. The implementations of `CommitmentLayout` and `ProofLayout` /// for dynamic regions both use it, ensuring consistency between the two. pub(crate) fn chunks_to_writer< const LEN: usize, @@ -660,23 +638,6 @@ impl RootHashable for DynCells { } } -impl Merkleisable for DynCells>> { - fn to_merkle_tree(&self) -> Result { - let mut writer = MerkleWriter::new( - MERKLE_LEAF_SIZE, - MERKLE_ARITY, - self.region.get_read(), - self.region.get_write(), - LEN.div_ceil(MERKLE_ARITY), - ); - let read = |address| -> [u8; MERKLE_LEAF_SIZE.get()] { - ProofDynRegion::inner_dyn_region_read(self.region, address) - }; - chunks_to_writer::(&mut writer, read)?; - writer.finalise() - } -} - impl Clone for DynCells { fn clone(&self) -> Self { Self { diff --git a/src/riscv/lib/src/stepper/pvm.rs b/src/riscv/lib/src/stepper/pvm.rs index a845f6ae8783..c1aeea3d86aa 100644 --- a/src/riscv/lib/src/stepper/pvm.rs +++ b/src/riscv/lib/src/stepper/pvm.rs @@ -93,7 +93,7 @@ impl<'hooks, ML: MainMemoryLayout, CL: CacheLayouts> PvmStepper<'hooks, ML, CL, let refs = proof_stepper .pvm .struct_ref::(); - let merkle_proof = PvmLayout::::to_proof(refs) + let merkle_proof = PvmLayout::::to_merkle_tree(refs) .expect("Obtaining the Merkle tree of a proof-gen state should not fail") .to_merkle_proof() .expect("Converting a Merkle tree to a compressed Merkle proof should not fail"); -- GitLab