From 623ce99abe1f19d14efd2ee01a2471f6bef68e99 Mon Sep 17 00:00:00 2001 From: Victor Dumitrescu Date: Mon, 21 Oct 2024 21:06:01 +0200 Subject: [PATCH] RISC-V: Proof-generating state backend --- src/riscv/lib/src/state_backend/hash.rs | 6 - .../lib/src/state_backend/proof_backend.rs | 508 ++++++++++++++++++ .../src/state_backend/proof_backend/merkle.rs | 178 +++--- src/riscv/lib/src/state_backend/region.rs | 10 +- 4 files changed, 630 insertions(+), 72 deletions(-) diff --git a/src/riscv/lib/src/state_backend/hash.rs b/src/riscv/lib/src/state_backend/hash.rs index 574570b63017..f466fe0bc471 100644 --- a/src/riscv/lib/src/state_backend/hash.rs +++ b/src/riscv/lib/src/state_backend/hash.rs @@ -170,9 +170,6 @@ pub struct HashWriter { impl HashWriter { /// Initialise a new writer with the given `size`. - /// - /// # Panics - /// Panics if `size == 0`. pub fn new(size: NonZeroUsize) -> Self { let size = size.get(); Self { @@ -193,9 +190,6 @@ impl HashWriter { /// Hash the contents of the buffer. fn flush_buffer(&mut self) -> Result<(), HashError> { - // 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`. let hash = Hash::blake2b_hash_bytes(&self.buffer)?; self.hashes.push(hash); self.buffer.clear(); diff --git a/src/riscv/lib/src/state_backend/proof_backend.rs b/src/riscv/lib/src/state_backend/proof_backend.rs index fc3dfd8e2983..4ddfad5f1e04 100644 --- a/src/riscv/lib/src/state_backend/proof_backend.rs +++ b/src/riscv/lib/src/state_backend/proof_backend.rs @@ -2,6 +2,514 @@ // // SPDX-License-Identifier: MIT +//! Proof-generating backend +//! +//! Generic backend used for PVM proof generation, which wraps a manager and +//! records all state accesses performed during an evaluation step. +//! After evaluation, a [`MerkleTree`] over the PVM state can be obtained, +//! which can be partially blinded to produce a proof as a partial Merkle tree. +//! The structure of the Merkle tree is informed by the layout of the state, by +//! implementing [`Merkleisable`] for each of its components. +//! +//! [`MerkleTree`]: merkle::MerkleTree +//! [`Merkleisable`]: merkle::Merkleisable + +use super::{ + EnrichedValue, EnrichedValueLinked, ManagerBase, ManagerRead, ManagerReadWrite, + ManagerSerialise, ManagerWrite, +}; +use merkle::AccessInfo; +use std::{ + cell::{Cell, RefCell}, + collections::{BTreeMap, BTreeSet}, + mem, slice, +}; + pub mod merkle; pub mod proof; mod tree; + +/// Proof-generating backend +pub struct ProofGen<'a, M: ManagerBase> { + _pd: std::marker::PhantomData<&'a M>, +} + +impl<'a, M: ManagerBase> ManagerBase for ProofGen<'a, M> { + type Region = ProofRegion; + + type DynRegion = ProofDynRegion; + + type EnrichedCell = ProofEnrichedCell; + + type ManagerRoot = Self; +} + +/// Implementation of [`ManagerRead`] which wraps another manager and +/// additionally records read locations. +impl<'a, M: ManagerRead> ManagerRead for ProofGen<'a, M> { + fn region_read(region: &Self::Region, index: usize) -> E { + region.set_read(); + match region.writes.get(&index) { + Some(elem) => *elem, + None => M::region_read(®ion.source, index), + } + } + + fn region_ref(region: &Self::Region, index: usize) -> &E { + region.set_read(); + region + .writes + .get(&index) + .unwrap_or_else(|| M::region_ref(®ion.source, index)) + } + + fn region_read_all(region: &Self::Region) -> Vec { + region.set_read(); + let mut elems = M::region_read_all(®ion.source); + for (index, elem) in region.writes.iter() { + elems[*index] = *elem; + } + elems + } + + fn dyn_region_read( + region: &Self::DynRegion, + address: usize, + ) -> E { + let elem_size = mem::size_of::(); + region.reads.borrow_mut().insert::(address); + + // Read a value from the wrapped region and convert it to the stored representation. + let mut value: E = M::dyn_region_read(®ion.source, address); + value.to_stored_in_place(); + + // Get a mutable slice of bytes over the value and overwrite any byte that has been written + // during the proof step. + let value_bytes: &mut [u8] = unsafe { + // SAFETY: Obtaining a mutable slice of `mem::size_of::()` bytes from a mutable reference + // to one value of type `E` should be safe, assuming `value` is not the result of + // multiple allocations. + // Cannot use `mem::transmute` because `E` does not have a constant size. + slice::from_raw_parts_mut((&mut value as *mut E) as *mut u8, elem_size) + }; + for (i, byte) in region.writes.range(address..address + elem_size) { + value_bytes[*i - address] = *byte; + } + + // Convert back from the stored representation and return. + value.from_stored_in_place(); + value + } + + fn dyn_region_read_all( + region: &Self::DynRegion, + address: usize, + values: &mut [E], + ) { + assert!(address + mem::size_of_val(values) <= LEN); + + for (offset, value) in values.iter_mut().enumerate() { + *value = Self::dyn_region_read(region, address + offset * mem::size_of::()); + } + } + + fn enriched_cell_read(_cell: &Self::EnrichedCell) -> (V::E, V::D) + where + V: EnrichedValueLinked, + V::E: Copy, + V::D: Copy, + { + // TODO: RV-325 Support for `EnrichedCell` in the proof-generating backend + todo!() + } + + fn enriched_cell_ref(_cell: &Self::EnrichedCell) -> (&V::E, &V::D) + where + V: EnrichedValueLinked, + { + // TODO: RV-325 Support for `EnrichedCell` in the proof-generating backend + todo!() + } + + fn enriched_cell_read_stored(_cell: &Self::EnrichedCell) -> V::E + where + V: EnrichedValue, + V::E: Copy, + { + // TODO: RV-325 Support for `EnrichedCell` in the proof-generating backend + todo!() + } +} + +/// Implementation of [`ManagerWrite`] which wraps another manager and +/// records written locations but does not write to the wrapped region directly. +impl<'a, M: ManagerWrite> ManagerWrite for ProofGen<'a, M> { + fn region_write( + region: &mut Self::Region, + index: usize, + value: E, + ) { + region.set_write(); + region.writes.insert(index, value); + } + + fn region_write_all(region: &mut Self::Region, value: &[E]) { + region.set_write(); + for (index, elem) in value.iter().enumerate() { + region.writes.insert(index, *elem); + } + } + + fn dyn_region_write( + region: &mut Self::DynRegion, + address: usize, + mut value: E, + ) { + assert!(address + mem::size_of_val(&value) <= LEN); + + value.to_stored_in_place(); + + // Get a mutable slice of bytes over the value to be written and iterate over it + // in order to record every byte to the write log. The wrapped region is not modified. + let value_bytes = unsafe { + // SAFETY: Obtaining a slice of `mem::size_of::()` bytes from a reference + // to one value of type `E` should be safe, assuming `value` is not the result of + // multiple allocations. + // Cannot use `mem::transmute` because `E` does not have a constant size. + slice::from_raw_parts((&value as *const E) as *const u8, mem::size_of::()) + }; + for (offset, byte) in value_bytes.iter().enumerate() { + region.writes.insert(address + offset, *byte); + } + } + + fn dyn_region_write_all( + region: &mut Self::DynRegion, + address: usize, + values: &[E], + ) { + assert!(address + mem::size_of_val(values) <= LEN); + + for (offset, value) in values.iter().enumerate() { + Self::dyn_region_write(region, address + offset * mem::size_of::(), *value) + } + } + + fn enriched_cell_write(_cell: &mut Self::EnrichedCell, _value: V::E) + where + V: EnrichedValueLinked, + { + // TODO: RV-325 Support for `EnrichedCell` in the proof-generating backend + todo!() + } +} + +/// Implementation of [`ManagerReadWrite`] which wraps another manager and +/// additionally records read and written locations. +impl<'a, M: ManagerReadWrite> ManagerReadWrite for ProofGen<'a, M> { + fn region_replace( + region: &mut Self::Region, + index: usize, + value: E, + ) -> E { + region.set_read_write(); + let elem = M::region_read(®ion.source, index); + region.writes.insert(index, value); + elem + } +} + +impl<'a, M: ManagerSerialise> ManagerSerialise for ProofGen<'a, M> { + fn serialise_region( + region: &Self::Region, + serializer: S, + ) -> Result { + M::serialise_region(®ion.source, serializer) + } + + fn serialise_dyn_region( + region: &Self::DynRegion, + serializer: S, + ) -> Result { + M::serialise_dyn_region(®ion.source, serializer) + } + + fn serialise_enriched_cell( + _cell: &Self::EnrichedCell, + _serializer: S, + ) -> Result + where + V: EnrichedValue, + V::E: serde::Serialize, + S: serde::Serializer, + { + // TODO: RV-325 Support for `EnrichedCell` in the proof-generating backend + todo!() + } +} + +/// Proof region which wraps a region managed by another manager. +/// +/// A [`ManagerBase::Region`] is never split across multiple leaves when Merkleised. +/// An access to any part of the region is thus recorded as an access to the region as a whole. +/// The underlying region is never mutated, but all written values are recorded +/// in order to preserve the integrity of subsequent reads. +pub struct ProofRegion { + source: M::Region, + writes: BTreeMap, + access: Cell, +} + +impl ProofRegion { + /// Get a copy of the access log. + pub fn get_access_info(&self) -> AccessInfo { + self.access.get() + } + + /// Set the access log to `Read` or, if previously `Write`, to `ReadWrite`. + pub fn set_read(&self) { + match self.access.get() { + AccessInfo::NoAccess => self.access.set(AccessInfo::Read), + AccessInfo::Write => self.access.set(AccessInfo::ReadWrite), + _ => (), + } + } + + /// Set the access log to `Write` or, if previously `Read`, to `ReadWrite`. + pub fn set_write(&self) { + match self.access.get() { + AccessInfo::NoAccess => self.access.set(AccessInfo::Write), + AccessInfo::Read => self.access.set(AccessInfo::ReadWrite), + _ => (), + } + } + + /// Set the access log to `ReadWrite`. + pub fn set_read_write(&self) { + self.access.set(AccessInfo::ReadWrite) + } +} + +/// Proof dynamic region which wraps a dynamic region managed by another manager. +/// +/// When Merkleising a [`ManagerBase::DynRegion`], its data can be split into multiple leaves. +/// Accesses are thus recorded for each address. +/// The underlying dynamic region is never mutated, but all written bytes are +/// recorded in order to preserve the integrity of subsequent reads. +pub struct ProofDynRegion { + source: M::DynRegion, + reads: RefCell, + writes: BTreeMap, +} + +impl ProofDynRegion { + /// Get the set of addresses of the region that were read from. + /// This function is meant to be called once when Merkleising the region. + pub fn get_read(&self) -> DynAccess { + self.reads.take() + } + + /// Get the set of addresses of the region that were written to. + /// This function is meant to be called once when Merkleising the region. + pub fn get_write(&self) -> DynAccess { + let writes: BTreeSet<_> = self.writes.keys().copied().collect(); + DynAccess(writes) + } +} + +impl ProofDynRegion { + /// Read from the wrapped dynamic region. + pub fn inner_dyn_region_read(&self, address: usize) -> E { + M::dyn_region_read(&self.source, address) + } +} + +// TODO: RV-325 Support for `EnrichedCell` in the proof-generating backend +#[allow(dead_code)] +pub struct ProofEnrichedCell { + source: M::EnrichedCell, +} + +/// A record of accessed addresses in a dynamic region +#[derive(Default)] +pub struct DynAccess(BTreeSet); + +impl DynAccess { + /// Insert all addresses touched while accessing an element of a given size. + pub fn insert(&mut self, address: usize) { + self.0.extend(address..address + mem::size_of::()) + } + + /// Check whether any address within a given range of addresses + /// has been accessed. + pub fn includes_range(&self, r: std::ops::Range) -> bool { + self.0.range(r).next().is_some() + } +} + +#[cfg(test)] +mod tests { + use super::*; + use crate::state_backend::{ + owned_backend::Owned, + region::{DynCells, MERKLE_LEAF_SIZE}, + }; + use proptest::{prop_assert_eq, proptest}; + + impl ProofRegion { + pub fn from_source_region(source: M::Region) -> Self { + Self { + source, + writes: BTreeMap::new(), + access: Cell::new(AccessInfo::NoAccess), + } + } + } + + const CELLS_SIZE: usize = 255; + + #[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::from_source_region(cells); + prop_assert_eq!(region.get_access_info(), AccessInfo::NoAccess); + let value = ProofGen::<'_, Owned>::region_read(®ion, i); + prop_assert_eq!(value, value_before); + prop_assert_eq!(region.get_access_info(), AccessInfo::Read); + ProofGen::<'_, Owned>::region_write(&mut region, i, value_after); + prop_assert_eq!(region.get_access_info(), AccessInfo::ReadWrite); + + // A write followed by a read + let cells = [value_before; CELLS_SIZE]; + let mut region: ProofRegion = + ProofRegion::from_source_region(cells); + prop_assert_eq!(region.get_access_info(), AccessInfo::NoAccess); + ProofGen::<'_, Owned>::region_write(&mut region, i, value_after); + prop_assert_eq!(region.get_access_info(), AccessInfo::Write); + let value = ProofGen::<'_, Owned>::region_read(®ion, i); + prop_assert_eq!(value, value_after); + prop_assert_eq!(region.get_access_info(), AccessInfo::ReadWrite); + + // Replace + let cells = [value_before; CELLS_SIZE]; + let mut region: ProofRegion = + ProofRegion::from_source_region(cells); + prop_assert_eq!(region.get_access_info(), AccessInfo::NoAccess); + let value = ProofGen::<'_, Owned>::region_replace(&mut region, i, value_after); + prop_assert_eq!(value, value_before); + prop_assert_eq!(region.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::from_source_region(cells); + prop_assert_eq!(region.get_access_info(), AccessInfo::NoAccess); + let values = ProofGen::<'_, Owned>::region_read_all(®ion); + prop_assert_eq!(values.as_slice(), data_before); + prop_assert_eq!(region.get_access_info(), AccessInfo::Read); + ProofGen::<'_, Owned>::region_write_all(&mut region, &data_after); + prop_assert_eq!(region.get_access_info(), AccessInfo::ReadWrite); + + // A write_all followed by a read_all + let cells = data_before; + let mut region: ProofRegion = + ProofRegion::from_source_region(cells); + prop_assert_eq!(region.get_access_info(), AccessInfo::NoAccess); + ProofGen::<'_, Owned>::region_write_all(&mut region, &data_after); + prop_assert_eq!(region.get_access_info(), AccessInfo::Write); + let values = ProofGen::<'_, Owned>::region_read_all(®ion); + prop_assert_eq!(values.as_slice(), data_after); + prop_assert_eq!(region.get_access_info(), AccessInfo::ReadWrite); + }); + } + + impl ProofDynRegion { + pub fn from_source_region(source: M::DynRegion) -> Self { + Self { + source, + reads: RefCell::default(), + writes: BTreeMap::new(), + } + } + } + + const LEAVES: usize = 8; + const DYN_REGION_SIZE: usize = MERKLE_LEAF_SIZE.get() * LEAVES; + const ELEM_SIZE: usize = mem::size_of::(); + + #[test] + fn test_proof_gen_dyn_region() { + if ELEM_SIZE > MERKLE_LEAF_SIZE.get() { + unreachable!( + "This test assumes that a single element does not span more than 2 leaves" + ); + } + let address_range = 0..DYN_REGION_SIZE - ELEM_SIZE; + + // Check that writing to an address in the proof region makes subsequent reads return + // the overwritten value. + proptest!(|(byte_before: u8, + bytes_after: [u8; ELEM_SIZE], + write_address in &address_range)| { + let cells = Box::new([byte_before; DYN_REGION_SIZE]); + let dyn_region: ProofDynRegion = + ProofDynRegion::from_source_region(cells); + let mut dyn_cells: DynCells> = + DynCells::bind(dyn_region); + + // Perform static memory accesses + let value_before = u64::from_le_bytes([byte_before; ELEM_SIZE]); + let value_after = u64::from_le_bytes(bytes_after); + + let value: u64 = dyn_cells.read(write_address); + assert_eq!(value, value_before); + dyn_cells.write(write_address, value_after); + let value: u64 = dyn_cells.read(write_address); + assert_eq!(value, value_after); + + let cells = Box::new([byte_before; DYN_REGION_SIZE]); + let dyn_region: ProofDynRegion = + ProofDynRegion::from_source_region(cells); + let mut dyn_cells: DynCells> = + DynCells::bind(dyn_region); + + // Perform dynamic memory accesses as `u16` + let value_before = [u16::from_le_bytes([byte_before; 2]); ELEM_SIZE / 2]; + let value_after = [ + u16::from_le_bytes([bytes_after[0], bytes_after[1]]), + u16::from_le_bytes([bytes_after[2], bytes_after[3]]), + u16::from_le_bytes([bytes_after[4], bytes_after[5]]), + u16::from_le_bytes([bytes_after[6], bytes_after[7]]), + ]; + + let mut value = [0u16; ELEM_SIZE / 2]; + dyn_cells.read_all(write_address, &mut value); + assert_eq!(value, value_before); + dyn_cells.write_all(write_address, &value_after); + dyn_cells.read_all(write_address, &mut value); + assert_eq!(value, value_after); + + let cells = Box::new([byte_before; DYN_REGION_SIZE]); + let dyn_region: ProofDynRegion = + ProofDynRegion::from_source_region(cells); + let mut dyn_cells: DynCells> = + DynCells::bind(dyn_region); + + // Perform dynamic memory accesses as bytes + let value_before = [byte_before; ELEM_SIZE]; + + let mut value = [0u8; ELEM_SIZE]; + dyn_cells.read_all(write_address, &mut value); + assert_eq!(value, value_before); + dyn_cells.write_all(write_address, &bytes_after); + dyn_cells.read_all(write_address, &mut value); + assert_eq!(value, bytes_after); + }); + } +} 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 126dc0784d6c..767561075cf7 100644 --- a/src/riscv/lib/src/state_backend/proof_backend/merkle.rs +++ b/src/riscv/lib/src/state_backend/proof_backend/merkle.rs @@ -11,6 +11,7 @@ use crate::state_backend::hash::{Hash, HashError, RootHashable, DIGEST_SIZE}; use itertools::Itertools; /// A variable-width Merkle tree with [`AccessInfo`] metadata for leaves. +/// /// Values of this type are produced by the proof-generating backend to capture /// a snapshot of the machine state along with access information for leaves /// which hold data that was used in a particular evaluation step. @@ -20,49 +21,6 @@ pub enum MerkleTree { Node(Hash, Vec), } -/// Type of access associated with leaves in a [`MerkleTree`]. -#[derive(Debug, Clone, PartialEq)] -pub enum AccessInfo { - NoAccess, - Write, - Read, - ReadWrite, -} - -/// Intermediary representation obtained when compressing a [`MerkleTree`]. -/// -/// For the compressed tree, we only care about the data in the non-blinded leaves. -#[derive(Debug, Clone, PartialEq)] -pub(super) enum CompressedMerkleTree { - Leaf(Hash, CompressedAccessInfo), - Node(Hash, Vec), -} - -/// Type of access associated with leaves in a [`CompressedMerkleTree`]. -/// -/// If a subtree is made up of only [`AccessInfo::NoAccess`] or of only [`AccessInfo::Read`] -/// then the subtree can be compressed to a leaf of the corresponding access type. -/// For the non-blinded variants, it holds the byte data associated with the access. -#[derive(Debug, Clone, PartialEq)] -pub(super) enum CompressedAccessInfo { - NoAccess, - Write, - Read(Vec), - ReadWrite(Vec), -} - -impl AccessInfo { - /// Convert an access info to a compressed access info, potentially with additional data. - pub(super) fn to_compressed(&self, data: Vec) -> CompressedAccessInfo { - match self { - Self::NoAccess => CompressedAccessInfo::NoAccess, - Self::Write => CompressedAccessInfo::Write, - Self::Read => CompressedAccessInfo::Read(data), - Self::ReadWrite => CompressedAccessInfo::ReadWrite(data), - } - } -} - impl MerkleTree { /// Get the root hash of a Merkle tree fn root_hash(&self) -> Hash { @@ -159,6 +117,42 @@ impl MerkleTree { } } +impl RootHashable for MerkleTree { + fn hash(&self) -> Result { + Ok(self.root_hash()) + } +} + +/// Type of access associated with leaves in a [`MerkleTree`]. +#[derive(Debug, Clone, Copy, PartialEq)] +pub enum AccessInfo { + NoAccess, + Write, + Read, + ReadWrite, +} + +impl AccessInfo { + /// Convert an access info to a compressed access info, potentially with additional data. + pub(super) fn to_compressed(self, data: Vec) -> CompressedAccessInfo { + match self { + Self::NoAccess => CompressedAccessInfo::NoAccess, + Self::Write => CompressedAccessInfo::Write, + Self::Read => CompressedAccessInfo::Read(data), + Self::ReadWrite => CompressedAccessInfo::ReadWrite(data), + } + } +} + +/// Intermediary representation obtained when compressing a [`MerkleTree`]. +/// +/// For the compressed tree, we only care about the data in the non-blinded leaves. +#[derive(Debug, Clone, PartialEq)] +pub(super) enum CompressedMerkleTree { + Leaf(Hash, CompressedAccessInfo), + Node(Hash, Vec), +} + impl CompressedMerkleTree { /// Get the root hash of a compreessed Merkle tree fn root_hash(&self) -> Hash { @@ -203,6 +197,19 @@ impl CompressedMerkleTree { } } +/// Type of access associated with leaves in a [`CompressedMerkleTree`]. +/// +/// If a subtree is made up of only [`AccessInfo::NoAccess`] or of only [`AccessInfo::Read`] +/// then the subtree can be compressed to a leaf of the corresponding access type. +/// For the non-blinded variants, it holds the byte data associated with the access. +#[derive(Debug, Clone, PartialEq)] +pub(super) enum CompressedAccessInfo { + NoAccess, + Write, + Read(Vec), + ReadWrite(Vec), +} + // TODO: RV-237 Ensure consistency between `RootHashable` and `Merkleisable` // implementations pub trait Merkleisable { @@ -210,6 +217,50 @@ pub trait Merkleisable { fn to_merkle_tree(&self) -> Result; } +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 Merkleisable for Vec { + fn to_merkle_tree(&self) -> Result { + self.as_slice().to_merkle_tree() + } +} + +impl Merkleisable for [T; N] { + fn to_merkle_tree(&self) -> Result { + self.as_ref().to_merkle_tree() + } +} + +macro_rules! impl_merkleisable_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_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); + #[cfg(test)] mod tests { use super::{AccessInfo, MerkleTree, Merkleisable}; @@ -230,18 +281,15 @@ mod tests { } } - impl Merkleisable for (A, B) { - fn to_merkle_tree(&self) -> Result { - let left = self.0.to_merkle_tree()?; - let right = self.1.to_merkle_tree()?; - let hash = RootHashable::hash(&(left.root_hash(), right.root_hash()))?; - Ok(MerkleTree::Node(hash, vec![left, right])) + impl RootHashable for Vec { + fn hash(&self) -> Result { + Hash::blake2b_hash_bytes(self) } } fn m_l(data: &[u8], access: AccessInfo) -> Result { let hash = Hash::blake2b_hash_bytes(data)?; - Ok(MerkleTree::Leaf(hash, access.clone(), data.to_vec())) + Ok(MerkleTree::Leaf(hash, access, data.to_vec())) } fn m_t(left: MerkleTree, right: MerkleTree) -> Result { @@ -256,10 +304,12 @@ mod tests { prop::collection::vec(0u8..255, 0..100), 6) )| { - let tree = ((&leaves[0], (&leaves[1], &leaves[2])), ((&leaves[3], &leaves[4]), &leaves[5])) + 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.check_root_hash()); + assert!(tree.root_hash() == state.hash()?); }); } @@ -273,7 +323,7 @@ mod tests { m_t(m_l(&l[2], Read)?, m_l(&l[3], ReadWrite)?)?, )?; let no_access_t = m_t( - m_l(&l[4], NoAccess.clone())?, + m_l(&l[4], NoAccess)?, m_t(m_l(&l[5], NoAccess)?, m_l(&l[6], NoAccess)?)?, )?; let write_t = m_t( @@ -368,21 +418,21 @@ mod tests { let proof_read = MerkleProof::Node(vec![ MerkleProof::Node(vec![ - merkle_proof_leaf(&l[11], Read.clone())?, - merkle_proof_leaf(&l[12], Read.clone())?, + merkle_proof_leaf(&l[11], Read)?, + merkle_proof_leaf(&l[12], Read)?, ]), MerkleProof::Node(vec![ - merkle_proof_leaf(&l[13], Read.clone())?, - merkle_proof_leaf(&l[14], Read.clone())?, + merkle_proof_leaf(&l[13], Read)?, + merkle_proof_leaf(&l[14], Read)?, ]), ]); let proof_read_write = MerkleProof::Node(vec![ MerkleProof::Node(vec![ - merkle_proof_leaf(&l[15], ReadWrite.clone())?, - merkle_proof_leaf(&l[16], ReadWrite.clone())?, + merkle_proof_leaf(&l[15], ReadWrite)?, + merkle_proof_leaf(&l[16], ReadWrite)?, ]), - merkle_proof_leaf(&l[17], ReadWrite.clone())?, + merkle_proof_leaf(&l[17], ReadWrite)?, ]); let proof_combine_isolated = MerkleProof::Node(vec![ @@ -392,9 +442,9 @@ mod tests { let proof_mix = MerkleProof::Node(vec![ MerkleProof::Node(vec![ - merkle_proof_leaf(&l[18], NoAccess.clone())?, + merkle_proof_leaf(&l[18], NoAccess)?, MerkleProof::Node(vec![ - merkle_proof_leaf(&l[19], NoAccess.clone())?, + merkle_proof_leaf(&l[19], NoAccess)?, MerkleProof::Leaf(MerkleProofLeaf::Blind( [ Hash::blake2b_hash_bytes(&l[20])?, @@ -406,7 +456,7 @@ mod tests { ]), MerkleProof::Node(vec![ MerkleProof::Node(vec![ - merkle_proof_leaf(&l[22], ReadWrite.clone())?, + merkle_proof_leaf(&l[22], ReadWrite)?, MerkleProof::Leaf(MerkleProofLeaf::Blind( [ Hash::blake2b_hash_bytes(&l[23])?, @@ -415,7 +465,7 @@ mod tests { .hash()?, )), ]), - merkle_proof_leaf(&l[25], Read.clone())?, + merkle_proof_leaf(&l[25], Read)?, ]), ]); diff --git a/src/riscv/lib/src/state_backend/region.rs b/src/riscv/lib/src/state_backend/region.rs index b7bc015dd29b..bd13af065515 100644 --- a/src/riscv/lib/src/state_backend/region.rs +++ b/src/riscv/lib/src/state_backend/region.rs @@ -502,8 +502,14 @@ impl<'de, const LEN: usize, M: ManagerDeserialise> serde::Deserialize<'de> for D } } -// SAFETY: This constant is non-zero. -const MERKLE_LEAF_SIZE: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(4096) }; +// TODO RV-322: Choose optimal Merkleisation parameters for main memory. +/// Size of the Merkle leaf used for Merkleising [`DynCells`]. +pub const MERKLE_LEAF_SIZE: NonZeroUsize = + // SAFETY: This constant is non-zero. + unsafe { NonZeroUsize::new_unchecked(4096) }; + +// TODO RV-322: Choose optimal Merkleisation parameters for main memory. +/// Arity of the Merkle tree used for Merkleising [`DynCells`]. const MERKLE_ARITY: usize = 3; impl RootHashable for DynCells { -- GitLab