From d933fe18e7b3f492a86afac97e058213d353d8d2 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Ole=20Kr=C3=BCger?= Date: Thu, 6 Mar 2025 22:30:27 +0000 Subject: [PATCH 1/4] RISC-V: De-duplicate ProofWrapper natural transformation --- src/riscv/lib/src/pvm/common.rs | 21 +------------------ src/riscv/lib/src/pvm/node_pvm.rs | 21 +------------------ .../lib/src/state_backend/proof_backend.rs | 20 ++++++++++++++++++ 3 files changed, 22 insertions(+), 40 deletions(-) diff --git a/src/riscv/lib/src/pvm/common.rs b/src/riscv/lib/src/pvm/common.rs index 3fcf5b180086..87a7e7fac929 100644 --- a/src/riscv/lib/src/pvm/common.rs +++ b/src/riscv/lib/src/pvm/common.rs @@ -20,9 +20,8 @@ use crate::pvm::sbi; use crate::state_backend; use crate::state_backend::Atom; use crate::state_backend::Cell; -use crate::state_backend::proof_backend::ProofDynRegion; use crate::state_backend::proof_backend::ProofGen; -use crate::state_backend::proof_backend::ProofRegion; +use crate::state_backend::proof_backend::ProofWrapper; use crate::traps::EnvironException; /// PVM configuration @@ -189,24 +188,6 @@ impl< where M: state_backend::ManagerRead, { - enum ProofWrapper {} - - impl state_backend::FnManager for ProofWrapper { - type Output = ProofGen; - - fn map_region( - input: ::Region, - ) -> as state_backend::ManagerBase>::Region { - ProofRegion::bind(input) - } - - fn map_dyn_region( - input: ::DynRegion, - ) -> as state_backend::ManagerBase>::DynRegion { - ProofDynRegion::bind(input) - } - } - let space = self.struct_ref::(); Pvm::bind(space, bcall::InterpretedBlockBuilder) } diff --git a/src/riscv/lib/src/pvm/node_pvm.rs b/src/riscv/lib/src/pvm/node_pvm.rs index 467027aa5d56..e9b64814b094 100644 --- a/src/riscv/lib/src/pvm/node_pvm.rs +++ b/src/riscv/lib/src/pvm/node_pvm.rs @@ -26,9 +26,8 @@ use crate::state_backend::ProofLayout; use crate::state_backend::ProofTree; use crate::state_backend::Ref; use crate::state_backend::owned_backend::Owned; -use crate::state_backend::proof_backend::ProofDynRegion; use crate::state_backend::proof_backend::ProofGen; -use crate::state_backend::proof_backend::ProofRegion; +use crate::state_backend::proof_backend::ProofWrapper; use crate::state_backend::proof_backend::proof::MerkleProof; use crate::state_backend::verify_backend::Verifier; use crate::storage; @@ -84,24 +83,6 @@ impl State { where M: state_backend::ManagerRead, { - enum ProofWrapper {} - - impl state_backend::FnManager for ProofWrapper { - type Output = ProofGen; - - fn map_region( - input: ::Region, - ) -> as state_backend::ManagerBase>::Region { - ProofRegion::bind(input) - } - - fn map_dyn_region( - input: ::DynRegion, - ) -> as state_backend::ManagerBase>::DynRegion { - ProofDynRegion::bind(input) - } - } - State::bind(self.struct_ref::()) } } diff --git a/src/riscv/lib/src/state_backend/proof_backend.rs b/src/riscv/lib/src/state_backend/proof_backend.rs index 26ef6f9bc463..b5096f67cc97 100644 --- a/src/riscv/lib/src/state_backend/proof_backend.rs +++ b/src/riscv/lib/src/state_backend/proof_backend.rs @@ -25,6 +25,7 @@ use serde::ser::SerializeTuple; use super::EnrichedValue; use super::EnrichedValueLinked; +use super::FnManager; use super::ManagerBase; use super::ManagerRead; use super::ManagerReadWrite; @@ -406,6 +407,25 @@ impl DynAccess { } } +/// Natural transformation from a manager `M` to a proof-generating manager `ProofGen` +pub enum ProofWrapper {} + +impl FnManager for ProofWrapper { + type Output = ProofGen; + + fn map_region( + input: ::Region, + ) -> as ManagerBase>::Region { + ProofRegion::bind(input) + } + + fn map_dyn_region( + input: ::DynRegion, + ) -> as ManagerBase>::DynRegion { + ProofDynRegion::bind(input) + } +} + #[cfg(test)] mod tests { use std::collections::VecDeque; -- GitLab From a2c716fefa78d1911d2d87a55099107bbef0620c Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Ole=20Kr=C3=BCger?= Date: Thu, 6 Mar 2025 20:42:30 +0000 Subject: [PATCH 2/4] RISC-V: Use curly braces with struct_layout! macro --- src/riscv/lib/src/machine_state/csregisters/values/mstatus.rs | 4 ++-- src/riscv/lib/src/state_backend/layout.rs | 4 ++-- 2 files changed, 4 insertions(+), 4 deletions(-) diff --git a/src/riscv/lib/src/machine_state/csregisters/values/mstatus.rs b/src/riscv/lib/src/machine_state/csregisters/values/mstatus.rs index 7d0beeabe75b..77c3b8cff9d5 100644 --- a/src/riscv/lib/src/machine_state/csregisters/values/mstatus.rs +++ b/src/riscv/lib/src/machine_state/csregisters/values/mstatus.rs @@ -134,7 +134,7 @@ impl Clone for MStatusValue { } } -struct_layout!( +struct_layout! { pub struct MStatusLayout { pub sie: Atom, pub mie: Atom, @@ -156,7 +156,7 @@ struct_layout!( pub sbe: Atom, pub mbe: Atom, } -); +} #[inline(always)] fn compute_sd(fs: ExtensionValue, xs: ExtensionValue) -> bool { diff --git a/src/riscv/lib/src/state_backend/layout.rs b/src/riscv/lib/src/state_backend/layout.rs index 14642588aa81..a48dca3c3c73 100644 --- a/src/riscv/lib/src/state_backend/layout.rs +++ b/src/riscv/lib/src/state_backend/layout.rs @@ -77,13 +77,13 @@ impl Layout for DynArray { /// use octez_riscv::machine_state::csregisters::CSRRepr; /// use octez_riscv::struct_layout; /// -/// struct_layout!( +/// struct_layout! { /// pub struct ExampleLayout { /// satp_ppn: Atom, /// mode: Atom, /// cached: Atom, /// } -/// ); +/// } /// ``` #[macro_export] macro_rules! struct_layout { -- GitLab From 9abb27452770169f5ebbdbe0a65d3e0f8c361cdd Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Ole=20Kr=C3=BCger?= Date: Thu, 6 Mar 2025 20:42:30 +0000 Subject: [PATCH 3/4] RISC-V: Capture struct_layout! misbehaving using test --- src/riscv/lib/src/state_backend/layout.rs | 76 +++++++++++++++++++++++ 1 file changed, 76 insertions(+) diff --git a/src/riscv/lib/src/state_backend/layout.rs b/src/riscv/lib/src/state_backend/layout.rs index a48dca3c3c73..ad111e1a9d73 100644 --- a/src/riscv/lib/src/state_backend/layout.rs +++ b/src/riscv/lib/src/state_backend/layout.rs @@ -365,6 +365,13 @@ mod tests { use super::*; use crate::backend_test; use crate::default::ConstDefault; + use crate::state_backend::CommitmentLayout; + use crate::state_backend::FnManagerIdent; + use crate::state_backend::ProofLayout; + use crate::state_backend::ProofPart; + use crate::state_backend::owned_backend::Owned; + use crate::state_backend::proof_backend::ProofWrapper; + use crate::state_backend::verify_backend::handle_not_found; #[derive(Clone, Copy, Debug, PartialEq, Eq)] struct MyFoo(u64); @@ -385,4 +392,73 @@ mod tests { [MyFoo::DEFAULT; 1337] ); }); + + #[test] + fn test_struct_layout() { + struct_layout! { + pub struct Foo { + bar: Atom, + qux: Array, + } + } + + fn inner(bar: u64, qux: [u8; 64]) { + let mut foo = Owned::allocate::(); + + foo.bar.write(bar); + foo.qux.write_all(&qux); + + // Obtain the state hash + let refs = FooF { + bar: foo.bar.struct_ref::(), + qux: foo.qux.struct_ref::(), + }; + let hash = Foo::state_hash(refs).unwrap(); + + // Obtain the Merkle tree + let mut proof_foo = FooF { + bar: foo.bar.struct_ref::(), + qux: foo.qux.struct_ref::(), + }; + let proof_foo_refs = FooF { + bar: proof_foo.bar.struct_ref::(), + qux: proof_foo.qux.struct_ref::(), + }; + + let tree = Foo::to_merkle_tree(proof_foo_refs).unwrap(); + let tree_root_hash = tree.root_hash(); + assert_eq!(hash, tree_root_hash); + + // Modify the values so they appear in the proof + proof_foo.bar.write(bar.wrapping_add(1)); + proof_foo.qux.write_all(&qux.map(|x| x.wrapping_add(1))); + + // Obtain the Merkle tree, again, to make sure nothing changed + let proof_foo_refs = FooF { + bar: proof_foo.bar.struct_ref::(), + qux: proof_foo.qux.struct_ref::(), + }; + + let tree = Foo::to_merkle_tree(proof_foo_refs).unwrap(); + let tree_root_hash = tree.root_hash(); + assert_eq!(hash, tree_root_hash); + + // Produce a proof + let proof = tree.to_merkle_proof().unwrap(); + let proof_hash = proof.root_hash().unwrap(); + assert_eq!(hash, proof_hash); + + // Verify the proof + handle_not_found(|| { + let verify_foo = Foo::from_proof(ProofPart::Present(&proof)).unwrap(); + assert_eq!(bar, verify_foo.bar.read()); + assert_eq!(qux, verify_foo.qux.read_all().as_slice()); + }) + .unwrap(); + } + + proptest::proptest!(|(bar: u64, qux: [u8; 64])| { + inner(bar, qux); + }); + } } -- GitLab From 47b952954319fc5a1d7398fb361ec7859e22f707 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Ole=20Kr=C3=BCger?= Date: Thu, 6 Mar 2025 20:42:30 +0000 Subject: [PATCH 4/4] RISC-V: Make struct_layout! macro use Merkle-isation --- src/riscv/lib/src/state_backend/layout.rs | 138 +++++++++++----------- 1 file changed, 66 insertions(+), 72 deletions(-) diff --git a/src/riscv/lib/src/state_backend/layout.rs b/src/riscv/lib/src/state_backend/layout.rs index ad111e1a9d73..bae59646d2f2 100644 --- a/src/riscv/lib/src/state_backend/layout.rs +++ b/src/riscv/lib/src/state_backend/layout.rs @@ -87,59 +87,67 @@ impl Layout for DynArray { /// ``` #[macro_export] macro_rules! struct_layout { - ($vis:vis struct $layout_t:ident { - $($field_vis:vis $field_name:ident: $cell_repr:ty),+ - $( , )? - }) => { + ( + $vis:vis struct $layout_t:ident $(< $($param:ident),+ >)? { + $($field_vis:vis $field_name:ident: $cell_repr:ty),+ + $(,)? + } + ) => { paste::paste! { #[derive(serde::Deserialize, serde::Serialize, Debug, Clone, PartialEq, Eq)] $vis struct [<$layout_t F>]< $( - [<$field_name:upper>] + [<$field_name:camel>] ),+ > { $( - $field_vis $field_name: [<$field_name:upper>] + $field_vis $field_name: [<$field_name:camel>] ),+ } - $vis type $layout_t = [<$layout_t F>]< + $vis type $layout_t $(< $($param),+ >)? = [<$layout_t F>]< $( $cell_repr ),+ >; - impl $crate::state_backend::Layout for $layout_t { + impl < + $( + [<$field_name:camel>]: $crate::state_backend::Layout + ),+ + > $crate::state_backend::Layout for [<$layout_t F>]< + $( + [<$field_name:camel>] + ),+ + > { type Allocated = [<$layout_t F>]< $( - AllocatedOf<$cell_repr, M> + <[<$field_name:camel>] as $crate::state_backend::Layout>::Allocated ),+ >; + #[inline] fn allocate( backend: &mut M, ) -> Self::Allocated { Self::Allocated { - $($field_name: <$cell_repr as $crate::state_backend::Layout>::allocate( + $($field_name: <[<$field_name:camel>] as $crate::state_backend::Layout>::allocate( backend )),+ } } } - use $crate::state_backend::proof_backend::merkle::{ - AccessInfoAggregatable, MerkleTree, - }; - impl < $( - [<$field_name:upper>]: AccessInfoAggregatable + serde::Serialize + [<$field_name:camel>]: $crate::state_backend::proof_backend::merkle::AccessInfoAggregatable + serde::Serialize ),+ - > AccessInfoAggregatable for [<$layout_t F>]< + > $crate::state_backend::proof_backend::merkle::AccessInfoAggregatable for [<$layout_t F>]< $( - [<$field_name:upper>] + [<$field_name:camel>] ),+ > { + #[inline] fn aggregate_access_info(&self) -> bool { let children = [ $( @@ -150,73 +158,59 @@ macro_rules! struct_layout { } } - impl $crate::state_backend::CommitmentLayout for $layout_t { - fn state_hash(state: AllocatedOf + impl < + $( + [<$field_name:camel>]: $crate::state_backend::CommitmentLayout + ),+ + > $crate::state_backend::CommitmentLayout for [<$layout_t F>]< + $( + [<$field_name:camel>] + ),+ + > { + #[inline] + fn state_hash( + state: AllocatedOf ) -> Result<$crate::storage::Hash, $crate::storage::HashError> { - $crate::storage::Hash::blake2b_hash(state) + $crate::storage::Hash::combine(&[ + $( + [<$field_name:camel>]::state_hash(state.$field_name)? + ),+ + ]) } } - impl $crate::state_backend::ProofLayout for $layout_t { + impl < + $( + [<$field_name:camel>]: $crate::state_backend::ProofLayout + ),+ + > $crate::state_backend::ProofLayout for [<$layout_t F>]< + $( + [<$field_name:camel>] + ),+ + > { + #[inline] 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()) + $crate::state_backend::proof_backend::merkle::MerkleTree::make_merkle_node( + vec![ + $( + [<$field_name:camel>]::to_merkle_tree(state.$field_name)? + ),+ + ] + ) } + #[inline] fn from_proof( proof: $crate::state_backend::ProofTree, ) -> Result, $crate::state_backend::FromProofError> { - if let $crate::state_backend::ProofTree::Present(proof) = proof { - match proof { - $crate::state_backend::proof_backend::tree::Tree::Leaf(_) => { - Err($crate::state_backend::FromProofError::UnexpectedLeaf) - } - - $crate::state_backend::proof_backend::tree::Tree::Node(branches) => { - let mut branches = branches.iter(); - - let expected_branches = 0 $( - + { let $field_name = 1; $field_name } - )+; - let successful_branches = 0; - - $( - let $field_name = branches.next().ok_or($crate::state_backend::FromProofError::BadNumberOfBranches { - got: successful_branches, - expected: expected_branches, - })?; - let $field_name = <$cell_repr as $crate::state_backend::ProofLayout>::from_proof($crate::state_backend::ProofTree::Present($field_name))?; - let successful_branches = successful_branches + 1; - )+ - - if branches.last().is_some() { - // There were more branches, this is bad. - return Err($crate::state_backend::FromProofError::BadNumberOfBranches { - got: successful_branches + 1, - expected: expected_branches, - }); - } - - Ok( - Self::Allocated { - $( - $field_name - ),+ - } - ) - } - } - } else { - Ok( - Self::Allocated { - $( - $field_name: <$cell_repr as $crate::state_backend::ProofLayout>::from_proof($crate::state_backend::ProofTree::Absent)? - ),+ - } - ) - } + let [ $($field_name),+ ] = *proof.into_branches()?; + Ok(Self::Allocated { + $( + $field_name: [<$field_name:camel>]::from_proof($field_name)? + ),+ + }) } } } -- GitLab