From b4cd96a6943fbae0b46288d31b98f53dbafd5f28 Mon Sep 17 00:00:00 2001 From: Victor Dumitrescu Date: Mon, 20 Jan 2025 11:31:24 +0100 Subject: [PATCH 1/2] RISC-V: Remove RootHashable trait --- .../lib/src/machine_state/block_cache.rs | 18 ++- .../src/state_backend/commitment_layout.rs | 27 ++-- src/riscv/lib/src/state_backend/hash.rs | 86 +++-------- .../lib/src/state_backend/owned_backend.rs | 3 - .../src/state_backend/proof_backend/merkle.rs | 146 +++++++----------- .../src/state_backend/proof_backend/proof.rs | 13 +- .../lib/src/state_backend/proof_layout.rs | 14 +- src/riscv/lib/src/state_backend/region.rs | 33 ---- 8 files changed, 120 insertions(+), 220 deletions(-) diff --git a/src/riscv/lib/src/machine_state/block_cache.rs b/src/riscv/lib/src/machine_state/block_cache.rs index af9086d631c1..3387a2258c73 100644 --- a/src/riscv/lib/src/machine_state/block_cache.rs +++ b/src/riscv/lib/src/machine_state/block_cache.rs @@ -945,7 +945,7 @@ mod tests { MachineCoreState, MachineCoreStateLayout, MachineState, MachineStateLayout, TestCacheLayouts, }, - state_backend::owned_backend::Owned, + state_backend::{owned_backend::Owned, CommitmentLayout}, }; pub type TestLayout = Layout; @@ -1243,6 +1243,22 @@ mod tests { ); }); + /// Tests that a layout which contains an [`EnrichedCell`] is hashed identically as + /// a layout which contains a [`Cell`] of the same value. + #[test] + fn test_enriched_cell_hashing() { + let instr = Instruction::DEFAULT; + + let ec_value = (instr, ICall::::from(&instr)); + let ec: EnrichedCell, Ref<'_, Owned>> = EnrichedCell::bind(&ec_value); + let ec_hash = as CommitmentLayout>::state_hash(ec).unwrap(); + + let c_value = [instr; 1]; + let c: Cell> = Cell::bind(&c_value); + let c_hash = as CommitmentLayout>::state_hash(c).unwrap(); + assert_eq!(ec_hash, c_hash); + } + /// The initialised block cache must not return any blocks. This is especially important for /// blocks at address 0 which at one point were accidentally valid but empty which caused loops. #[test] diff --git a/src/riscv/lib/src/state_backend/commitment_layout.rs b/src/riscv/lib/src/state_backend/commitment_layout.rs index 29767671b727..cae53fc5366b 100644 --- a/src/riscv/lib/src/state_backend/commitment_layout.rs +++ b/src/riscv/lib/src/state_backend/commitment_layout.rs @@ -4,7 +4,7 @@ use super::{ chunks_to_writer, - hash::{self, Hash, HashError, HashWriter, RootHashable, DIGEST_SIZE}, + hash::{self, Hash, HashError, HashWriter, DIGEST_SIZE}, Array, Atom, DynArray, Layout, Many, RefOwnedAlloc, MERKLE_ARITY, MERKLE_LEAF_SIZE, }; use crate::default::ConstDefault; @@ -50,7 +50,7 @@ where { fn state_hash(state: RefOwnedAlloc) -> Result { let hashes = [A::state_hash(state.0)?, B::state_hash(state.1)?]; - hashes.hash() + Hash::combine(&hashes) } } @@ -66,7 +66,7 @@ where B::state_hash(state.1)?, C::state_hash(state.2)?, ]; - hashes.hash() + Hash::combine(&hashes) } } @@ -84,7 +84,7 @@ where C::state_hash(state.2)?, D::state_hash(state.3)?, ]; - hashes.hash() + Hash::combine(&hashes) } } @@ -104,7 +104,7 @@ where D::state_hash(state.3)?, E::state_hash(state.4)?, ]; - hashes.hash() + Hash::combine(&hashes) } } @@ -126,7 +126,7 @@ where E::state_hash(state.4)?, F::state_hash(state.5)?, ]; - hashes.hash() + Hash::combine(&hashes) } } @@ -153,15 +153,10 @@ where I: IntoIterator>, T: CommitmentLayout, { - let mut hashes: Vec = Vec::with_capacity(DIGEST_SIZE * LEN); + let hashes: Vec = iter + .into_iter() + .map(T::state_hash) + .collect::, _>>()?; - iter.into_iter().try_for_each(|e| { - hashes.extend_from_slice(T::state_hash(e)?.as_ref()); - Ok::<(), 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`. - Hash::blake2b_hash_bytes(&hashes) + Hash::combine(&hashes) } diff --git a/src/riscv/lib/src/state_backend/hash.rs b/src/riscv/lib/src/state_backend/hash.rs index ba3f9b8aad6d..70c66514694f 100644 --- a/src/riscv/lib/src/state_backend/hash.rs +++ b/src/riscv/lib/src/state_backend/hash.rs @@ -48,6 +48,24 @@ impl Hash { pub fn blake2b_hash(data: T) -> Result { Self::blake2b_hash_bytes(&bincode::serialize(&data)?) } + + /// Combine multiple [`Hash`] values into a single one. + /// + /// The hashes are combined by concatenating them, then hashing the result. + /// Pre-image resistance is not compromised because the concatenation is not + /// ambiguous, with hashes having a fixed size ([`DIGEST_SIZE`]). + pub fn combine(hashes: &[Hash]) -> Result { + let mut input: Vec = Vec::with_capacity(DIGEST_SIZE * hashes.len()); + + hashes + .iter() + .for_each(|h| input.extend_from_slice(h.as_ref())); + + // 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`. + Hash::blake2b_hash_bytes(&input) + } } impl std::fmt::Display for Hash { @@ -92,72 +110,6 @@ impl AsRef<[u8]> for Hash { } } -// TODO RV-398: Remove `RootHashable` trait -pub trait RootHashable { - /// Build the root hash corresponding to the Merkle tree described by the - /// layout of the data. - fn hash(&self) -> Result; -} - -impl RootHashable for &T { - fn hash(&self) -> Result { - T::hash(self) - } -} - -impl RootHashable for Hash { - fn hash(&self) -> Result { - Ok(*self) - } -} - -impl RootHashable for [T] { - fn hash(&self) -> Result { - let mut hashes: Vec = Vec::with_capacity(DIGEST_SIZE * self.len()); - - self.iter().try_for_each(|e| { - hashes.extend_from_slice(e.hash()?.as_ref()); - Ok::<(), 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`. - Hash::blake2b_hash_bytes(&hashes) - } -} - -impl RootHashable for Vec { - fn hash(&self) -> Result { - self.as_slice().hash() - } -} - -impl RootHashable for [T; N] { - fn hash(&self) -> Result { - self.as_slice().hash() - } -} - -macro_rules! impl_roothash_for_tuple { - ($($name:ident),*) => { - impl<$($name: RootHashable),*> RootHashable for ($($name,)*) { - fn hash(&self) -> Result { - #[allow(non_snake_case)] - let ($($name,)*) = self; - let hashes: Result, HashError> = [$($name.hash(),)*].into_iter().collect(); - hashes?.hash() - } - } - } -} - -impl_roothash_for_tuple!(A, B); -impl_roothash_for_tuple!(A, B, C); -impl_roothash_for_tuple!(A, B, C, D); -impl_roothash_for_tuple!(A, B, C, D, E); -impl_roothash_for_tuple!(A, B, C, D, E, F); - /// Writer which hashes fixed-sized chunks of data and produces the digests. pub struct HashWriter { size: usize, @@ -240,7 +192,7 @@ pub(crate) fn build_custom_merkle_hash( while nodes.len() > 1 { // Group the nodes into chunks of size `arity` and hash each chunk. for chunk in nodes.chunks(arity) { - next_level.push(chunk.hash()?) + next_level.push(Hash::combine(chunk)?) } std::mem::swap(&mut nodes, &mut next_level); diff --git a/src/riscv/lib/src/state_backend/owned_backend.rs b/src/riscv/lib/src/state_backend/owned_backend.rs index a4aa78e6a191..95c39720cc72 100644 --- a/src/riscv/lib/src/state_backend/owned_backend.rs +++ b/src/riscv/lib/src/state_backend/owned_backend.rs @@ -468,8 +468,6 @@ pub mod test_helpers { /// Ensure [`EnrichedCell`] is serialized identically to [`Cell`]. #[test] fn enriched_cell_serialise_match_cell() { - use crate::state_backend::hash::RootHashable; - pub struct Enriching; pub struct Fun; @@ -497,7 +495,6 @@ pub mod test_helpers { let cbytes = bincode::serialize(&cell).unwrap(); assert_eq!(ebytes, cbytes, "Serializing EnrichedCell and Cell should match"); - assert_eq!(ecell.hash().unwrap(), cell.hash().unwrap(), "RootHashable for EnrichedCell and Cell should match"); }); } 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 7ec801326b82..601c0ff043e0 100644 --- a/src/riscv/lib/src/state_backend/proof_backend/merkle.rs +++ b/src/riscv/lib/src/state_backend/proof_backend/merkle.rs @@ -9,7 +9,7 @@ use super::{ DynAccess, }; use crate::state_backend::{ - hash::{Hash, HashError, RootHashable}, + hash::{Hash, HashError}, proof_backend::tree::{impl_modify_map_collect, ModifyResult}, }; use std::convert::Infallible; @@ -41,6 +41,14 @@ impl MerkleTree { Ok(MerkleTree::Leaf(hash, access_info, data)) } + /// Make a Merkle tree consisting of a node which combines the given + /// child trees. + pub fn make_merkle_node(children: Vec) -> Result { + let children_hashes: Vec = children.iter().map(|t| t.root_hash()).collect(); + let node_hash = Hash::combine(children_hashes.as_slice())?; + Ok(MerkleTree::Node(node_hash, children)) + } + /// Compress all fully blindable subtrees to a single leaf node, obtaining a [`CompressedMerkleTree`]. /// /// To fit a proof in a manager operation, the Merkle tree it contains needs to be compressed. @@ -76,7 +84,7 @@ impl MerkleTree { CompresedNode(hash, _) => (hash, None), } }) - .unzip::<_, _, Vec<&Hash>, Vec<_>>(); + .unzip::<_, _, Vec, Vec<_>>(); // Obtain the compression type of all children // if all children have been compressed successfully to the same type of leaf. @@ -86,7 +94,7 @@ impl MerkleTree { .flatten(); let compressed_tree = match compression { - Some(access) => CompresedLeaf(RootHashable::hash(&hashes)?, access), + Some(access) => CompresedLeaf(Hash::combine(hashes.as_slice())?, access), None => CompresedNode(hash, compact_children), }; @@ -102,12 +110,6 @@ 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 { @@ -367,7 +369,7 @@ impl MerkleWriter { while self.leaves.len() > 1 { for chunk in self.leaves.chunks(self.arity) { - next_level.push(MerkleTree::Node(chunk.hash()?, chunk.to_vec())); + next_level.push(MerkleTree::make_merkle_node(chunk.to_vec())?) } std::mem::swap(&mut self.leaves, &mut next_level); @@ -416,19 +418,15 @@ impl MerkleTree { 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) + let children_hashes: Vec = children + .iter() + .map(|child| { + deque.push_back(child); + child.root_hash() + }) + .collect(); + + Hash::combine(&children_hashes).is_ok_and(|h| h == *hash) } }; if !is_valid_hash { @@ -443,13 +441,13 @@ impl MerkleTree { mod tests { use super::{AccessInfo, CompressedAccessInfo, CompressedMerkleTree, MerkleTree}; use crate::state_backend::{ - hash::{Hash, HashError, RootHashable, DIGEST_SIZE}, + hash::{Hash, HashError}, proof_backend::proof::{MerkleProof, MerkleProofLeaf}, }; use proptest::prelude::*; impl CompressedMerkleTree { - /// Get the root hash of a compreessed Merkle tree + /// Get the root hash of a compressed Merkle tree fn root_hash(&self) -> Hash { match self { Self::Node(hash, _) => *hash, @@ -472,17 +470,15 @@ mod tests { } }, 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) + let children_hashes: Vec = children + .iter() + .map(|child| { + deque.push_back(child); + child.root_hash() + }) + .collect(); + + Hash::combine(&children_hashes).is_ok_and(|h| h == *hash) } }; if !is_valid_hash { @@ -493,20 +489,13 @@ mod tests { } } - 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, data.to_vec())) } fn m_t(left: MerkleTree, right: MerkleTree) -> Result { - let hash = RootHashable::hash(&(left.root_hash(), right.root_hash()))?; - Ok(MerkleTree::Node(hash, vec![left, right])) + MerkleTree::make_merkle_node(vec![left, right]) } #[test] @@ -584,33 +573,24 @@ mod tests { // Not even though structurally the code has the same arborescent shape, // the proof shape is changed, some nodes becoming leaves now. (subtrees being compressed) - let proof_no_access = MerkleProof::Leaf(MerkleProofLeaf::Blind( - [ - Hash::blake2b_hash_bytes(&l[4])?, - [ - Hash::blake2b_hash_bytes(&l[5])?, - Hash::blake2b_hash_bytes(&l[6])?, - ] - .hash()?, - ] - .hash()?, - )); - - let proof_write = MerkleProof::Leaf(MerkleProofLeaf::Blind( - [ - [ - Hash::blake2b_hash_bytes(&l[7])?, - Hash::blake2b_hash_bytes(&l[8])?, - ] - .hash()?, - [ - Hash::blake2b_hash_bytes(&l[9])?, - Hash::blake2b_hash_bytes(&l[10])?, - ] - .hash()?, - ] - .hash()?, - )); + let proof_no_access = MerkleProof::Leaf(MerkleProofLeaf::Blind(Hash::combine(&[ + Hash::blake2b_hash_bytes(&l[4])?, + Hash::combine(&[ + Hash::blake2b_hash_bytes(&l[5])?, + Hash::blake2b_hash_bytes(&l[6])?, + ])?, + ])?)); + + let proof_write = MerkleProof::Leaf(MerkleProofLeaf::Blind(Hash::combine(&[ + Hash::combine(&[ + Hash::blake2b_hash_bytes(&l[7])?, + Hash::blake2b_hash_bytes(&l[8])?, + ])?, + Hash::combine(&[ + Hash::blake2b_hash_bytes(&l[9])?, + Hash::blake2b_hash_bytes(&l[10])?, + ])?, + ])?)); let proof_read = MerkleProof::Node(vec![ MerkleProof::Node(vec![ @@ -641,25 +621,19 @@ mod tests { merkle_proof_leaf(&l[18], NoAccess)?, MerkleProof::Node(vec![ merkle_proof_leaf(&l[19], NoAccess)?, - MerkleProof::Leaf(MerkleProofLeaf::Blind( - [ - Hash::blake2b_hash_bytes(&l[20])?, - Hash::blake2b_hash_bytes(&l[21])?, - ] - .hash()?, - )), + MerkleProof::Leaf(MerkleProofLeaf::Blind(Hash::combine(&[ + Hash::blake2b_hash_bytes(&l[20])?, + Hash::blake2b_hash_bytes(&l[21])?, + ])?)), ]), ]), MerkleProof::Node(vec![ MerkleProof::Node(vec![ merkle_proof_leaf(&l[22], ReadWrite)?, - MerkleProof::Leaf(MerkleProofLeaf::Blind( - [ - Hash::blake2b_hash_bytes(&l[23])?, - Hash::blake2b_hash_bytes(&l[24])?, - ] - .hash()?, - )), + MerkleProof::Leaf(MerkleProofLeaf::Blind(Hash::combine(&[ + Hash::blake2b_hash_bytes(&l[23])?, + Hash::blake2b_hash_bytes(&l[24])?, + ])?)), ]), merkle_proof_leaf(&l[25], Read)?, ]), @@ -681,7 +655,7 @@ mod tests { assert_eq!(merkle_tree.to_merkle_proof().unwrap(), proof); assert_eq!( - compressed_merkle_proof.hash().unwrap(), + compressed_merkle_proof.root_hash().unwrap(), merkle_tree_root_hash ); diff --git a/src/riscv/lib/src/state_backend/proof_backend/proof.rs b/src/riscv/lib/src/state_backend/proof_backend/proof.rs index 46699db9d54e..e7edf43784f5 100644 --- a/src/riscv/lib/src/state_backend/proof_backend/proof.rs +++ b/src/riscv/lib/src/state_backend/proof_backend/proof.rs @@ -1,5 +1,5 @@ // SPDX-FileCopyrightText: 2024 TriliTech -// SPDX-FileCopyrightText: 2024 Nomadic Labs +// SPDX-FileCopyrightText: 2024-2025 Nomadic Labs // // SPDX-License-Identifier: MIT @@ -16,7 +16,7 @@ use super::tree::{impl_modify_map_collect, ModifyResult, Tree}; use crate::{ - state_backend::hash::{Hash, RootHashable}, + state_backend::hash::Hash, storage::{HashError, DIGEST_SIZE}, }; use itertools::Itertools; @@ -52,7 +52,7 @@ impl Proof { /// Get the initial state hash of the proof. pub fn initial_state_hash(&self) -> Hash { self.partial_tree - .hash() + .root_hash() .expect("Computing the root hash of the Merkle proof should not fail") } @@ -108,10 +108,9 @@ impl MerkleProof { MerkleProof::Leaf(MerkleProofLeaf::Read(_)) => Tag::Leaf(LeafTag::Read), } } -} -impl RootHashable for MerkleProof { - fn hash(&self) -> Result { + /// Compute the root hash of the Merkle proof. + pub fn root_hash(&self) -> Result { impl_modify_map_collect( self, |subtree| { @@ -124,7 +123,7 @@ impl RootHashable for MerkleProof { MerkleProofLeaf::Blind(hash) => Ok(*hash), MerkleProofLeaf::Read(data) => Hash::blake2b_hash_bytes(data.as_slice()), }, - |(), leaves| leaves.hash(), + |(), leaves| Hash::combine(&leaves), ) } } diff --git a/src/riscv/lib/src/state_backend/proof_layout.rs b/src/riscv/lib/src/state_backend/proof_layout.rs index 08fdb1a8944c..f9a27b153a66 100644 --- a/src/riscv/lib/src/state_backend/proof_layout.rs +++ b/src/riscv/lib/src/state_backend/proof_layout.rs @@ -5,7 +5,7 @@ use super::{ chunks_to_writer, hash, - hash::{HashError, RootHashable}, + hash::HashError, proof_backend::{ merkle::{MerkleTree, MerkleWriter}, proof::{MerkleProof, MerkleProofLeaf}, @@ -244,7 +244,7 @@ where { 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)) + MerkleTree::make_merkle_node(children) } fn from_proof(proof: ProofTree) -> FromProofResult { @@ -265,7 +265,7 @@ where B::to_merkle_tree(state.1)?, C::to_merkle_tree(state.2)?, ]; - Ok(MerkleTree::Node(children.hash()?, children)) + MerkleTree::make_merkle_node(children) } fn from_proof(proof: ProofTree) -> FromProofResult { @@ -288,7 +288,7 @@ where C::to_merkle_tree(state.2)?, D::to_merkle_tree(state.3)?, ]; - Ok(MerkleTree::Node(children.hash()?, children)) + MerkleTree::make_merkle_node(children) } fn from_proof(proof: ProofTree) -> FromProofResult { @@ -318,7 +318,7 @@ where D::to_merkle_tree(state.3)?, E::to_merkle_tree(state.4)?, ]; - Ok(MerkleTree::Node(children.hash()?, children)) + MerkleTree::make_merkle_node(children) } fn from_proof(proof: ProofTree) -> FromProofResult { @@ -351,7 +351,7 @@ where E::to_merkle_tree(state.4)?, F::to_merkle_tree(state.5)?, ]; - Ok(MerkleTree::Node(children.hash()?, children)) + MerkleTree::make_merkle_node(children) } fn from_proof(proof: ProofTree) -> FromProofResult { @@ -417,5 +417,5 @@ where .map(T::to_merkle_tree) .collect::, _>>()?; - Ok(MerkleTree::Node(children.hash()?, children)) + MerkleTree::make_merkle_node(children) } diff --git a/src/riscv/lib/src/state_backend/region.rs b/src/riscv/lib/src/state_backend/region.rs index 5a7b341c5b4f..b71f747333b8 100644 --- a/src/riscv/lib/src/state_backend/region.rs +++ b/src/riscv/lib/src/state_backend/region.rs @@ -4,7 +4,6 @@ // SPDX-License-Identifier: MIT use super::{ - hash::{self, Hash, HashError, HashWriter, RootHashable}, proof_backend::{ merkle::{AccessInfo, AccessInfoAggregatable}, ProofGen, @@ -188,12 +187,6 @@ impl<'de, E: serde::Deserialize<'de>, M: ManagerDeserialise> serde::Deserialize< } } -impl RootHashable for Cell { - fn hash(&self) -> Result { - Hash::blake2b_hash(self) - } -} - impl + Copy, B: Copy, M: ManagerRead, N: ManagerRead> PartialEq> for Cell { @@ -412,15 +405,6 @@ where } } -impl RootHashable for EnrichedCell -where - V::E: serde::Serialize, -{ - fn hash(&self) -> Result { - Hash::blake2b_hash(self) - } -} - impl AccessInfoAggregatable for EnrichedCell>> where @@ -457,12 +441,6 @@ where } } -impl RootHashable for Cells { - fn hash(&self) -> Result { - Hash::blake2b_hash(self) - } -} - impl + Copy, B: Copy, const LEN: usize, M: ManagerRead, N: ManagerRead> PartialEq> for Cells { @@ -627,17 +605,6 @@ pub(crate) fn chunks_to_writer< Ok(()) } -impl RootHashable for DynCells { - fn hash(&self) -> Result { - let mut writer = HashWriter::new(MERKLE_LEAF_SIZE); - let read = - |address| -> [u8; MERKLE_LEAF_SIZE.get()] { M::dyn_region_read(&self.region, address) }; - chunks_to_writer::(&mut writer, read)?; - let hashes = writer.finalise()?; - hash::build_custom_merkle_hash(MERKLE_ARITY, hashes) - } -} - impl Clone for DynCells { fn clone(&self) -> Self { Self { -- GitLab From d62abb29da0516bbf0d70443f186663611dfcd54 Mon Sep 17 00:00:00 2001 From: Victor Dumitrescu Date: Fri, 24 Jan 2025 16:22:53 +0100 Subject: [PATCH 2/2] RISC-V: Move Merkleisation-related definitions in `merkle` module --- .../src/state_backend/commitment_layout.rs | 6 +- .../lib/src/state_backend/proof_backend.rs | 5 +- .../src/state_backend/proof_backend/merkle.rs | 96 ++++++++++++++++++- .../lib/src/state_backend/proof_layout.rs | 19 ++-- src/riscv/lib/src/state_backend/region.rs | 88 ----------------- .../lib/src/state_backend/verify_backend.rs | 2 +- 6 files changed, 110 insertions(+), 106 deletions(-) diff --git a/src/riscv/lib/src/state_backend/commitment_layout.rs b/src/riscv/lib/src/state_backend/commitment_layout.rs index cae53fc5366b..117e432e0df6 100644 --- a/src/riscv/lib/src/state_backend/commitment_layout.rs +++ b/src/riscv/lib/src/state_backend/commitment_layout.rs @@ -3,9 +3,9 @@ // SPDX-License-Identifier: MIT use super::{ - chunks_to_writer, - hash::{self, Hash, HashError, HashWriter, DIGEST_SIZE}, - Array, Atom, DynArray, Layout, Many, RefOwnedAlloc, MERKLE_ARITY, MERKLE_LEAF_SIZE, + hash::{self, Hash, HashError, HashWriter}, + proof_backend::merkle::{chunks_to_writer, MERKLE_ARITY, MERKLE_LEAF_SIZE}, + Array, Atom, DynArray, Layout, Many, RefOwnedAlloc, }; use crate::default::ConstDefault; diff --git a/src/riscv/lib/src/state_backend/proof_backend.rs b/src/riscv/lib/src/state_backend/proof_backend.rs index 5c17c5f72cbe..f52ccc429fee 100644 --- a/src/riscv/lib/src/state_backend/proof_backend.rs +++ b/src/riscv/lib/src/state_backend/proof_backend.rs @@ -419,10 +419,11 @@ impl DynAccess { #[cfg(test)] mod tests { + use super::merkle::MERKLE_LEAF_SIZE; use super::*; use crate::state_backend::{ - layout::Array, owned_backend::Owned, region::MERKLE_LEAF_SIZE, Cells, CommitmentLayout, - DynArray, DynCells, ProofLayout, Ref, + layout::Array, owned_backend::Owned, Cells, CommitmentLayout, DynArray, DynCells, + ProofLayout, Ref, }; use proptest::{array, prop_assert_eq, proptest}; use std::collections::VecDeque; 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 601c0ff043e0..1876ec660cf4 100644 --- a/src/riscv/lib/src/state_backend/proof_backend/merkle.rs +++ b/src/riscv/lib/src/state_backend/proof_backend/merkle.rs @@ -12,7 +12,21 @@ use crate::state_backend::{ hash::{Hash, HashError}, proof_backend::tree::{impl_modify_map_collect, ModifyResult}, }; -use std::convert::Infallible; +use std::{convert::Infallible, num::NonZeroUsize}; + +// TODO RV-322: Choose optimal Merkleisation parameters for main memory. +/// Size of the Merkle leaf used for Merkleising [`DynArrays`]. +/// +/// [`DynArrays`]: [`crate::state_backend::layout::DynArray`] +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 [`DynArrays`]. +/// +/// [`DynArrays`]: [`crate::state_backend::layout::DynArray`] +pub const MERKLE_ARITY: usize = 3; /// A variable-width Merkle tree with [`AccessInfo`] metadata for leaves. /// @@ -295,6 +309,43 @@ 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); +/// Helper function which allows iterating over chunks of a dynamic array +/// and writing them to a writer. The last chunk may be smaller than the +/// Merkle leaf size. The implementations of [`CommitmentLayout`] and +/// [`ProofLayout`] for both use it, ensuring consistency between the two. +/// +/// [`CommitmentLayout`]: crate::state_backend::commitment_layout::CommitmentLayout +/// [`ProofLayout`]: crate::state_backend::proof_layout::ProofLayout +pub(crate) fn chunks_to_writer< + const LEN: usize, + T: std::io::Write, + F: Fn(usize) -> [u8; MERKLE_LEAF_SIZE.get()], +>( + writer: &mut T, + read: F, +) -> Result<(), std::io::Error> { + let merkle_leaf_size = MERKLE_LEAF_SIZE.get(); + assert!(LEN >= merkle_leaf_size); + + let mut address = 0; + + while address + merkle_leaf_size <= LEN { + writer.write_all(read(address).as_slice())?; + address += merkle_leaf_size; + } + + // When the last chunk is smaller than `MERKLE_LEAF_SIZE`, + // read the last `MERKLE_LEAF_SIZE` bytes and pass a subslice containing + // only the bytes not previously read to the writer. + if address != LEN { + address += merkle_leaf_size; + let buffer = read(LEN.saturating_sub(merkle_leaf_size)); + writer.write_all(&buffer[address.saturating_sub(LEN)..])?; + }; + + Ok(()) +} + /// Writer which splits data in fixed-sized chunks and produces a [`MerkleTree`] /// with a given arity in which each leaf represents a chunk. pub struct MerkleWriter { @@ -439,12 +490,16 @@ impl MerkleTree { #[cfg(test)] mod tests { - use super::{AccessInfo, CompressedAccessInfo, CompressedMerkleTree, MerkleTree}; + use super::{ + chunks_to_writer, AccessInfo, CompressedAccessInfo, CompressedMerkleTree, MerkleTree, + MERKLE_LEAF_SIZE, + }; use crate::state_backend::{ hash::{Hash, HashError}, proof_backend::proof::{MerkleProof, MerkleProofLeaf}, }; use proptest::prelude::*; + use std::io::Cursor; impl CompressedMerkleTree { /// Get the root hash of a compressed Merkle tree @@ -732,4 +787,41 @@ mod tests { check(t_root, root); } + + const LENS: [usize; 4] = [0, 1, 535, 4095]; + const _: () = { + if MERKLE_LEAF_SIZE.get() != 4096 { + panic!( + "Test values in `LENS` assume a specific MERKLE_LEAF_SIZE, change them accordingly" + ); + } + }; + + // Test `chunks_to_writer` with a variety of lengths + macro_rules! generate_test_chunks_to_writer { + ( $name:ident, $i:expr ) => { + proptest! { + #[test] + fn $name( + data in proptest::collection::vec(any::(), 4 * MERKLE_LEAF_SIZE.get() + LENS[$i]) + ) { + const LEN: usize = 4 * MERKLE_LEAF_SIZE.get() + LENS[$i]; + + let read = |pos: usize| { + assert!(pos + MERKLE_LEAF_SIZE.get() <= LEN); + data[pos..pos + MERKLE_LEAF_SIZE.get()].try_into().unwrap() + }; + + let mut writer = Cursor::new(Vec::new()); + chunks_to_writer::(&mut writer, read).unwrap(); + assert_eq!(writer.into_inner(), data); + } + } + } + } + + generate_test_chunks_to_writer!(test_chunks_to_writer_0, 0); + generate_test_chunks_to_writer!(test_chunks_to_writer_1, 1); + generate_test_chunks_to_writer!(test_chunks_to_writer_2, 2); + generate_test_chunks_to_writer!(test_chunks_to_writer_3, 3); } diff --git a/src/riscv/lib/src/state_backend/proof_layout.rs b/src/riscv/lib/src/state_backend/proof_layout.rs index f9a27b153a66..cc2f6072c190 100644 --- a/src/riscv/lib/src/state_backend/proof_layout.rs +++ b/src/riscv/lib/src/state_backend/proof_layout.rs @@ -4,17 +4,16 @@ // SPDX-License-Identifier: MIT use super::{ - chunks_to_writer, hash, + hash, hash::HashError, proof_backend::{ - merkle::{MerkleTree, MerkleWriter}, + merkle::{chunks_to_writer, MerkleTree, MerkleWriter, MERKLE_ARITY, MERKLE_LEAF_SIZE}, proof::{MerkleProof, MerkleProofLeaf}, tree::Tree, }, - verify_backend, Array, Atom, DynArray, Layout, Many, RefProofGenOwnedAlloc, MERKLE_ARITY, - MERKLE_LEAF_SIZE, + verify_backend, Array, Atom, DynArray, Layout, Many, RefProofGenOwnedAlloc, }; -use crate::{default::ConstDefault, state_backend, storage::binary}; +use crate::{default::ConstDefault, storage::binary}; use serde::de::Error; /// Errors that may occur when parsing a Merkle proof @@ -188,7 +187,7 @@ impl ProofLayout for DynArray { let mut pages = Vec::new(); while let Some((start, length, tree)) = pipeline.pop() { - if length <= super::MERKLE_LEAF_SIZE.get() { + if length <= MERKLE_LEAF_SIZE.get() { // Must be a leaf. let super::ProofPart::Present(data) = tree.into_leaf()? else { @@ -196,12 +195,12 @@ impl ProofLayout for DynArray { continue; }; - let data: Box<[u8; state_backend::MERKLE_LEAF_SIZE.get()]> = { + let data: Box<[u8; MERKLE_LEAF_SIZE.get()]> = { let data: Box<[u8]> = binary::deserialise(data)?; data.try_into().map_err(|err: Box<[u8]>| { bincode::Error::custom(format!( "Invalid Merkle leaf: expected {} bytes, got {}", - state_backend::MERKLE_LEAF_SIZE.get(), + MERKLE_LEAF_SIZE.get(), err.len() )) })? @@ -213,8 +212,8 @@ impl ProofLayout for DynArray { } else { // Expecting a branching point. - let branches = tree.into_branches::<{ super::MERKLE_ARITY }>()?; - let branch_max_length = length.div_ceil(super::MERKLE_ARITY); + let branches = tree.into_branches::<{ MERKLE_ARITY }>()?; + let branch_max_length = length.div_ceil(MERKLE_ARITY); let mut branch_start = start; let mut length_left = length; diff --git a/src/riscv/lib/src/state_backend/region.rs b/src/riscv/lib/src/state_backend/region.rs index b71f747333b8..54355963d643 100644 --- a/src/riscv/lib/src/state_backend/region.rs +++ b/src/riscv/lib/src/state_backend/region.rs @@ -12,7 +12,6 @@ use super::{ ManagerDeserialise, ManagerRead, ManagerReadWrite, ManagerSerialise, ManagerWrite, Ref, }; use std::borrow::Borrow; -use std::num::NonZeroUsize; /// Link a stored value directly with a derived value - /// that would either be expensive to compute each time, or cannot @@ -560,51 +559,6 @@ impl PartialEq Eq for DynCells {} -// 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`]. -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 `CommitmentLayout` and `ProofLayout` -/// for dynamic regions both use it, ensuring consistency between the two. -pub(crate) fn chunks_to_writer< - const LEN: usize, - T: std::io::Write, - F: Fn(usize) -> [u8; MERKLE_LEAF_SIZE.get()], ->( - writer: &mut T, - read: F, -) -> Result<(), std::io::Error> { - let merkle_leaf_size = MERKLE_LEAF_SIZE.get(); - assert!(LEN >= merkle_leaf_size); - - let mut address = 0; - - while address + merkle_leaf_size <= LEN { - writer.write_all(read(address).as_slice())?; - address += merkle_leaf_size; - } - - // When the last chunk is smaller than `MERKLE_LEAF_SIZE`, - // read the last `MERKLE_LEAF_SIZE` bytes and pass a subslice containing - // only the bytes not previously read to the writer. - if address != LEN { - address += merkle_leaf_size; - let buffer = read(LEN.saturating_sub(merkle_leaf_size)); - writer.write_all(&buffer[address.saturating_sub(LEN)..])?; - }; - - Ok(()) -} - impl Clone for DynCells { fn clone(&self) -> Self { Self { @@ -615,7 +569,6 @@ impl Clone for DynCells { #[cfg(test)] pub(crate) mod tests { - use super::{chunks_to_writer, MERKLE_LEAF_SIZE}; use crate::{ backend_test, default::ConstDefault, @@ -624,9 +577,7 @@ pub(crate) mod tests { Array, DynCells, Elem, FnManagerIdent, ManagerAlloc, ManagerBase, }, }; - use proptest::prelude::*; use serde::ser::SerializeTuple; - use std::io::Cursor; /// Dummy type that helps us implement custom normalisation via [Elem] #[repr(packed)] @@ -857,43 +808,4 @@ pub(crate) mod tests { let buffer = bincode::serialize(®ion.struct_ref::()).unwrap(); assert_eq!(buffer[..8], [22, 11, 24, 13, 26, 15, 28, 17]); }); - - const LENS: [usize; 4] = [0, 1, 535, 4095]; - const _: () = { - if MERKLE_LEAF_SIZE.get() != 4096 { - panic!( - "Test values in `LENS` assume a specific MERKLE_LEAF_SIZE, change them accordingly" - ); - } - }; - - // Test `chunks_to_writer` with a variety of lengths - macro_rules! generate_test_chunks_to_writer { - ( $( $name:ident, $i:expr ),* ) => { - $( - proptest! { - #[test] - fn $name( - data in proptest::collection::vec(any::(), 4 * MERKLE_LEAF_SIZE.get() + LENS[$i]) - ) { - const LEN: usize = 4 * MERKLE_LEAF_SIZE.get() + LENS[$i]; - - let read = |pos: usize| { - assert!(pos + MERKLE_LEAF_SIZE.get() <= LEN); - data[pos..pos + MERKLE_LEAF_SIZE.get()].try_into().unwrap() - }; - - let mut writer = Cursor::new(Vec::new()); - chunks_to_writer::(&mut writer, read).unwrap(); - assert_eq!(writer.into_inner(), data); - } - } - )* - } - } - - generate_test_chunks_to_writer!(test_chunks_to_writer_0, 0); - generate_test_chunks_to_writer!(test_chunks_to_writer_1, 1); - generate_test_chunks_to_writer!(test_chunks_to_writer_2, 2); - generate_test_chunks_to_writer!(test_chunks_to_writer_3, 3); } diff --git a/src/riscv/lib/src/state_backend/verify_backend.rs b/src/riscv/lib/src/state_backend/verify_backend.rs index c7e007752db7..9cecc920b2ed 100644 --- a/src/riscv/lib/src/state_backend/verify_backend.rs +++ b/src/riscv/lib/src/state_backend/verify_backend.rs @@ -5,7 +5,7 @@ use super::{ Cell, EnrichedValue, ManagerBase, ManagerClone, ManagerRead, ManagerReadWrite, ManagerWrite, }; -use crate::state_backend::{owned_backend::Owned, MERKLE_LEAF_SIZE}; +use crate::state_backend::{owned_backend::Owned, proof_backend::merkle::MERKLE_LEAF_SIZE}; use range_collections::RangeSet2; use std::{ array, -- GitLab