From 28eb48e612c72e4fcb1fa4b2e8c7ea514cf9aaa5 Mon Sep 17 00:00:00 2001 From: Victor Dumitrescu Date: Thu, 23 Jan 2025 14:07:10 +0100 Subject: [PATCH] RISC-V: Move proof generation functionality to `ProofLayout` trait --- src/riscv/lib/src/cache_utils.rs | 6 + .../lib/src/machine_state/block_cache.rs | 32 +++-- .../src/machine_state/csregisters/values.rs | 6 + src/riscv/lib/src/state_backend.rs | 8 +- src/riscv/lib/src/state_backend/layout.rs | 10 +- .../lib/src/state_backend/proof_backend.rs | 6 +- .../src/state_backend/proof_backend/merkle.rs | 3 +- .../lib/src/state_backend/proof_layout.rs | 114 +++++++++++++++++- src/riscv/lib/src/state_backend/region.rs | 10 ++ src/riscv/lib/src/stepper/pvm.rs | 47 ++++---- 10 files changed, 193 insertions(+), 49 deletions(-) diff --git a/src/riscv/lib/src/cache_utils.rs b/src/riscv/lib/src/cache_utils.rs index 4409360ec34d..5facfd7d0c99 100644 --- a/src/riscv/lib/src/cache_utils.rs +++ b/src/riscv/lib/src/cache_utils.rs @@ -101,6 +101,12 @@ impl Commi impl ProofLayout for Sizes { + fn to_proof( + state: crate::state_backend::RefProofGenOwnedAlloc, + ) -> Result { + Many::::to_proof(state) + } + fn from_proof(proof: ProofTree) -> FromProofResult { Many::::from_proof(proof) } diff --git a/src/riscv/lib/src/machine_state/block_cache.rs b/src/riscv/lib/src/machine_state/block_cache.rs index 0289b453529e..d9ba93354ff0 100644 --- a/src/riscv/lib/src/machine_state/block_cache.rs +++ b/src/riscv/lib/src/machine_state/block_cache.rs @@ -86,8 +86,8 @@ use super::{main_memory::Address, ProgramCounterUpdate}; use crate::machine_state::address_translation::PAGE_SIZE; use crate::parser::instruction::InstrWidth; use crate::state_backend::{ - self, AllocatedOf, Atom, Cell, EnrichedCell, EnrichedValue, ManagerBase, ManagerClone, - ManagerRead, ManagerReadWrite, ManagerWrite, Ref, + self, proof_backend, AllocatedOf, Atom, Cell, EnrichedCell, EnrichedValue, ManagerBase, + ManagerClone, ManagerRead, ManagerReadWrite, ManagerWrite, Ref, }; use crate::traps::{EnvironException, Exception}; use crate::{cache_utils::FenceCounter, state_backend::FnManager}; @@ -111,7 +111,7 @@ pub struct ICallLayout { _pd: PhantomData, } -impl crate::state_backend::Layout for ICallLayout { +impl state_backend::Layout for ICallLayout { type Allocated = EnrichedCell, M>; fn allocate(backend: &mut M) -> Self::Allocated { @@ -120,15 +120,21 @@ impl crate::state_backend::Layout for ICallLayout { } } -impl crate::state_backend::CommitmentLayout for ICallLayout { - fn state_hash( - state: AllocatedOf>, - ) -> Result { +impl state_backend::CommitmentLayout for ICallLayout { + fn state_hash(state: state_backend::RefOwnedAlloc) -> Result { Hash::blake2b_hash(state) } } -impl crate::state_backend::ProofLayout for ICallLayout { +impl state_backend::ProofLayout for ICallLayout { + fn to_proof( + state: state_backend::RefProofGenOwnedAlloc, + ) -> Result { + let cell = state.cell_ref(); + let serialised = proof_backend::ProofEnrichedCell::serialise_inner_enriched_cell(cell)?; + proof_backend::merkle::MerkleTree::make_merkle_leaf(serialised, cell.get_access_info()) + } + fn from_proof(proof: state_backend::ProofTree) -> state_backend::FromProofResult { let leaf = proof.into_leaf()?; @@ -206,14 +212,18 @@ impl state_backend::Layout for AddressCellLayout { } impl state_backend::CommitmentLayout for AddressCellLayout { - fn state_hash( - state: AllocatedOf>, - ) -> Result { + fn state_hash(state: state_backend::RefOwnedAlloc) -> Result { Hash::blake2b_hash(state) } } impl state_backend::ProofLayout for AddressCellLayout { + fn to_proof( + state: state_backend::RefProofGenOwnedAlloc, + ) -> Result { + as state_backend::ProofLayout>::to_proof(state) + } + fn from_proof(proof: state_backend::ProofTree) -> state_backend::FromProofResult { as state_backend::ProofLayout>::from_proof(proof) } diff --git a/src/riscv/lib/src/machine_state/csregisters/values.rs b/src/riscv/lib/src/machine_state/csregisters/values.rs index 8533c343ff54..ae249544af52 100644 --- a/src/riscv/lib/src/machine_state/csregisters/values.rs +++ b/src/riscv/lib/src/machine_state/csregisters/values.rs @@ -21,6 +21,7 @@ use crate::{ verify_backend, AllocatedOf, Cell, CommitmentLayout, EffectCell, EffectCellLayout, FnManager, FromProofResult, Layout, ManagerAlloc, ManagerBase, ManagerRead, ManagerReadWrite, ManagerWrite, ProofLayout, ProofPart, ProofTree, Ref, RefOwnedAlloc, + RefProofGenOwnedAlloc, }, storage::binary, }; @@ -163,6 +164,11 @@ impl CommitmentLayout for CSRValuesLayout { } impl ProofLayout for CSRValuesLayout { + fn to_proof(state: RefProofGenOwnedAlloc) -> Result { + let serialised = binary::serialise(&state)?; + MerkleTree::make_merkle_leaf(serialised, state.aggregate_access_info()) + } + fn from_proof(proof: ProofTree) -> FromProofResult { fn make_absent() -> AllocatedOf { CSRValuesF::new( diff --git a/src/riscv/lib/src/state_backend.rs b/src/riscv/lib/src/state_backend.rs index 2f463bc48fd8..f57c4d6263a3 100644 --- a/src/riscv/lib/src/state_backend.rs +++ b/src/riscv/lib/src/state_backend.rs @@ -1,5 +1,5 @@ // SPDX-FileCopyrightText: 2023-2025 TriliTech -// SPDX-FileCopyrightText: 2024 Nomadic Labs +// SPDX-FileCopyrightText: 2024-2025 Nomadic Labs // // SPDX-License-Identifier: MIT @@ -393,8 +393,14 @@ impl ManagerRead for Ref<'_, M> { } } +/// Alias for the allocated structure with references to regions of +/// the [`owned_backend::Owned`] backend pub type RefOwnedAlloc<'a, L> = AllocatedOf>; +/// Alias for the allocated structure with references to a proof-generating backend +pub type RefProofGenOwnedAlloc<'a, 'b, L> = + AllocatedOf>>>; + #[cfg(test)] pub(crate) mod test_helpers { use super::{ diff --git a/src/riscv/lib/src/state_backend/layout.rs b/src/riscv/lib/src/state_backend/layout.rs index f7c4a13f9a31..37fb65c5b5a2 100644 --- a/src/riscv/lib/src/state_backend/layout.rs +++ b/src/riscv/lib/src/state_backend/layout.rs @@ -1,5 +1,5 @@ // SPDX-FileCopyrightText: 2023 TriliTech -// SPDX-FileCopyrightText: 2024 Nomadic Labs +// SPDX-FileCopyrightText: 2024-2025 Nomadic Labs // // SPDX-License-Identifier: MIT @@ -166,13 +166,19 @@ macro_rules! struct_layout { } impl $crate::state_backend::CommitmentLayout for $layout_t { - fn state_hash(state: $crate::state_backend::AllocatedOf>) -> + fn state_hash(state: $crate::state_backend::RefOwnedAlloc) -> Result<$crate::storage::Hash, $crate::storage::HashError> { $crate::storage::Hash::blake2b_hash(state) } } impl $crate::state_backend::ProofLayout for $layout_t { + fn to_proof(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()) + } + fn from_proof(proof: $crate::state_backend::ProofTree) -> Result, $crate::state_backend::FromProofError> { if let $crate::state_backend::ProofTree::Present(proof) = proof { match proof { diff --git a/src/riscv/lib/src/state_backend/proof_backend.rs b/src/riscv/lib/src/state_backend/proof_backend.rs index 03d9e8bc620d..d286e9435276 100644 --- a/src/riscv/lib/src/state_backend/proof_backend.rs +++ b/src/riscv/lib/src/state_backend/proof_backend.rs @@ -8,11 +8,11 @@ //! 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. +//! The structure of the Merkle tree is informed by the layout of the state, +//! which needs to implement [`ProofLayout`]. //! //! [`MerkleTree`]: merkle::MerkleTree -//! [`Merkleisable`]: merkle::Merkleisable +//! [`ProofLayout`]: super::ProofLayout use super::{ EnrichedCell, EnrichedValue, EnrichedValueLinked, ManagerBase, ManagerRead, ManagerReadWrite, 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 88abae1465b7..e948c2efee1f 100644 --- a/src/riscv/lib/src/state_backend/proof_backend/merkle.rs +++ b/src/riscv/lib/src/state_backend/proof_backend/merkle.rs @@ -237,8 +237,7 @@ enum CompressedAccessInfo { ReadWrite(Vec), } -// TODO: RV-237 Ensure consistency between `RootHashable` and `Merkleisable` -// implementations +// 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; diff --git a/src/riscv/lib/src/state_backend/proof_layout.rs b/src/riscv/lib/src/state_backend/proof_layout.rs index 3f641e58fb5d..e30f8752011f 100644 --- a/src/riscv/lib/src/state_backend/proof_layout.rs +++ b/src/riscv/lib/src/state_backend/proof_layout.rs @@ -1,14 +1,18 @@ // SPDX-FileCopyrightText: 2024 TriliTech +// SPDX-FileCopyrightText: 2025 Nomadic Labs // // SPDX-License-Identifier: MIT use super::{ - hash, + chunks_to_writer, hash, + hash::{HashError, RootHashable}, proof_backend::{ + merkle::{MerkleTree, MerkleWriter}, proof::{MerkleProof, MerkleProofLeaf}, tree::Tree, }, - verify_backend, Array, Atom, DynArray, Layout, Many, + verify_backend, Array, Atom, DynArray, Layout, Many, RefProofGenOwnedAlloc, MERKLE_ARITY, + MERKLE_LEAF_SIZE, }; use crate::{default::ConstDefault, state_backend, storage::binary}; use serde::de::Error; @@ -108,20 +112,38 @@ impl<'a> ProofTree<'a> { /// /// [`Layouts`]: crate::state_backend::Layout 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; + /// Parse a Merkle proof into the allocated form of this layout. fn from_proof(proof: ProofTree) -> FromProofResult; } -impl ProofLayout for Atom { +impl ProofLayout + for Atom +{ + fn to_proof(state: RefProofGenOwnedAlloc) -> Result { + let serialised = binary::serialise(&state)?; + MerkleTree::make_merkle_leaf(serialised, state.into_region().get_access_info()) + } + fn from_proof(proof: ProofTree) -> FromProofResult { >::from_proof(proof).map(super::Cell::from) } } -impl ProofLayout for Array +impl ProofLayout for Array where [T; LEN]: ConstDefault + serde::de::DeserializeOwned, { + fn to_proof(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)?; + MerkleTree::make_merkle_leaf(serialised, state.into_region().get_access_info()) + } + fn from_proof(proof: ProofTree) -> FromProofResult { let region = if let ProofTree::Present(proof) = proof { let leaf = match proof { @@ -146,6 +168,21 @@ where } impl ProofLayout for DynArray { + fn to_proof(state: RefProofGenOwnedAlloc) -> Result { + let region = state.region_ref(); + let mut writer = MerkleWriter::new( + MERKLE_LEAF_SIZE, + MERKLE_ARITY, + region.get_read(), + region.get_write(), + LEN.div_ceil(MERKLE_ARITY), + ); + let read = + |address| -> [u8; MERKLE_LEAF_SIZE.get()] { region.inner_dyn_region_read(address) }; + chunks_to_writer::(&mut writer, read)?; + writer.finalise() + } + fn from_proof(proof: ProofTree) -> FromProofResult { let mut pipeline = vec![(0usize, LEN, proof)]; let mut pages = Vec::new(); @@ -205,6 +242,11 @@ where A: ProofLayout, B: ProofLayout, { + fn to_proof(state: RefProofGenOwnedAlloc) -> Result { + let children = vec![A::to_proof(state.0)?, B::to_proof(state.1)?]; + Ok(MerkleTree::Node(children.hash()?, children)) + } + fn from_proof(proof: ProofTree) -> FromProofResult { let [left, right] = proof.into_branches()?; Ok((A::from_proof(left)?, B::from_proof(right)?)) @@ -217,6 +259,15 @@ where B: ProofLayout, C: ProofLayout, { + fn to_proof(state: RefProofGenOwnedAlloc) -> Result { + let children = vec![ + A::to_proof(state.0)?, + B::to_proof(state.1)?, + C::to_proof(state.2)?, + ]; + Ok(MerkleTree::Node(children.hash()?, children)) + } + fn from_proof(proof: ProofTree) -> FromProofResult { let [a, b, c] = proof.into_branches()?; Ok((A::from_proof(a)?, B::from_proof(b)?, C::from_proof(c)?)) @@ -230,6 +281,16 @@ where C: ProofLayout, D: ProofLayout, { + fn to_proof(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)?, + ]; + Ok(MerkleTree::Node(children.hash()?, children)) + } + fn from_proof(proof: ProofTree) -> FromProofResult { let [a, b, c, d] = proof.into_branches()?; Ok(( @@ -249,6 +310,17 @@ where D: ProofLayout, E: ProofLayout, { + fn to_proof(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)?, + ]; + Ok(MerkleTree::Node(children.hash()?, children)) + } + fn from_proof(proof: ProofTree) -> FromProofResult { let [a, b, c, d, e] = proof.into_branches()?; Ok(( @@ -270,6 +342,18 @@ where E: ProofLayout, F: ProofLayout, { + fn to_proof(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)?, + ]; + Ok(MerkleTree::Node(children.hash()?, children)) + } + fn from_proof(proof: ProofTree) -> FromProofResult { let [a, b, c, d, e, f] = proof.into_branches()?; Ok(( @@ -287,6 +371,10 @@ impl ProofLayout for [T; LEN] where T: ProofLayout, { + fn to_proof(state: RefProofGenOwnedAlloc) -> Result { + iter_to_proof::<_, T>(state) + } + fn from_proof(proof: ProofTree) -> FromProofResult { proof .into_branches::()? @@ -305,6 +393,10 @@ impl ProofLayout for Many where T: ProofLayout, { + fn to_proof(state: RefProofGenOwnedAlloc) -> Result { + iter_to_proof::<_, T>(state) + } + fn from_proof(proof: ProofTree) -> FromProofResult { proof .into_branches::()? @@ -313,3 +405,17 @@ where .collect::, _>>() } } + +fn iter_to_proof<'a, 'b, I, T>(iter: I) -> Result +where + I: IntoIterator>, + T: ProofLayout, + 'b: 'a, +{ + let children = iter + .into_iter() + .map(|e| T::to_proof(e)) + .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 68c4dd33f404..440d972bf7a6 100644 --- a/src/riscv/lib/src/state_backend/region.rs +++ b/src/riscv/lib/src/state_backend/region.rs @@ -31,6 +31,11 @@ impl EnrichedCell { Self { cell } } + /// Obtain a reference to the underlying cell. + pub fn cell_ref(&self) -> &M::EnrichedCell { + &self.cell + } + /// Given a manager morphism `f : &M -> N`, return the layout's allocated structure containing /// the constituents of `N` that were produced from the constituents of `&M`. pub fn struct_ref<'a, F: FnManager>>(&'a self) -> EnrichedCell { @@ -516,6 +521,11 @@ impl DynCells { Self { region } } + /// Obtain a reference to the underlying dynamic region. + pub fn region_ref(&self) -> &M::DynRegion { + &self.region + } + /// Given a manager morphism `f : &M -> N`, return the layout's allocated structure containing /// the constituents of `N` that were produced from the constituents of `&M`. pub fn struct_ref<'a, F: FnManager>>(&'a self) -> DynCells { diff --git a/src/riscv/lib/src/stepper/pvm.rs b/src/riscv/lib/src/stepper/pvm.rs index b31aec08b567..a845f6ae8783 100644 --- a/src/riscv/lib/src/stepper/pvm.rs +++ b/src/riscv/lib/src/stepper/pvm.rs @@ -18,7 +18,7 @@ use crate::{ state_backend::{ hash::Hash, owned_backend::Owned, - proof_backend::{merkle::Merkleisable, proof::Proof, ProofGen}, + proof_backend::{proof::Proof, ProofGen}, verify_backend::Verifier, AllocatedOf, CommitmentLayout, FnManagerIdent, ProofLayout, ProofTree, Ref, }, @@ -83,6 +83,26 @@ impl<'hooks, ML: MainMemoryLayout, CL: CacheLayouts> PvmStepper<'hooks, ML, CL, let refs = self.pvm.struct_ref::(); PvmLayout::::state_hash(refs).unwrap() } + + /// Produce the Merkle proof for evaluating one step on the given PVM state. + /// The given stepper takes one step. + pub fn produce_proof(&mut self) -> Option { + // Step using the proof mode stepper in order to obtain the proof + let mut proof_stepper = self.start_proof_mode(); + proof_stepper.eval_one(); + let refs = proof_stepper + .pvm + .struct_ref::(); + let merkle_proof = PvmLayout::::to_proof(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"); + + // TODO RV-373 : Proof-generating backend should also compute final state hash + // Currently, the proof and the initial state hash are valid, + // but the final state hash is not. + Some(Proof::new(merkle_proof, self.hash())) + } } impl<'hooks, ML: MainMemoryLayout, CL: CacheLayouts, M: ManagerReadWrite> @@ -235,31 +255,6 @@ impl<'hooks, ML: MainMemoryLayout, CL: CacheLayouts, M: ManagerReadWrite> } } -impl<'hooks, ML: MainMemoryLayout, CL: CacheLayouts> PvmStepper<'hooks, ML, CL> -where - for<'a, 'b> AllocatedOf, Ref<'a, ProofGen>>>: Merkleisable, -{ - /// Produce the Merkle proof for evaluating one step on the given PVM state. - /// The given stepper takes one step. - pub fn produce_proof(&mut self) -> Option { - // Step using the proof mode stepper in order to obtain the proof - let mut proof_stepper = self.start_proof_mode(); - proof_stepper.eval_one(); - let merkle_proof = proof_stepper - .pvm - .struct_ref::() - .to_merkle_tree() - .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"); - - // TODO RV-373 : Proof-generating backend should also compute final state hash - // Currently, the proof and the initial state hash are valid, - // but the final state hash is not. - Some(Proof::new(merkle_proof, self.hash())) - } -} - impl<'hooks, ML: MainMemoryLayout, CL: CacheLayouts> Stepper for PvmStepper<'hooks, ML, CL> { type MainMemoryLayout = ML; -- GitLab