From b3a50e7b10b423f88fda38a054eea24ccca54503 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Ole=20Kr=C3=BCger?= Date: Tue, 17 Dec 2024 12:17:47 +0000 Subject: [PATCH 1/3] RISC-V: Implement the Verifier backend --- src/riscv/Cargo.lock | 48 ++ src/riscv/Cargo.toml | 1 + src/riscv/lib/Cargo.toml | 1 + .../lib/src/state_backend/proof_layout.rs | 25 +- .../lib/src/state_backend/verify_backend.rs | 731 +++++++++++++++++- src/rust_deps/Cargo.lock | 48 ++ 6 files changed, 834 insertions(+), 20 deletions(-) diff --git a/src/riscv/Cargo.lock b/src/riscv/Cargo.lock index 852752657a08..cde0040c20f7 100644 --- a/src/riscv/Cargo.lock +++ b/src/riscv/Cargo.lock @@ -156,6 +156,12 @@ version = "1.6.0" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "8c3c1a368f70d6cf7302d78f8f7093da241fb8e8807c05cc9e51a125895a6d5b" +[[package]] +name = "binary-merge" +version = "0.1.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "597bb81c80a54b6a4381b23faba8d7774b144c94cbd1d6fe3f1329bd776554ab" + [[package]] name = "bincode" version = "1.3.3" @@ -1320,6 +1326,15 @@ dependencies = [ "hashbrown 0.14.5", ] +[[package]] +name = "inplace-vec-builder" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "cf64c2edc8226891a71f127587a2861b132d2b942310843814d5001d99a1d307" +dependencies = [ + "smallvec", +] + [[package]] name = "is_terminal_polyfill" version = "1.70.0" @@ -1689,6 +1704,7 @@ dependencies = [ "paste", "proptest", "rand 0.8.5", + "range-collections", "rustc_apfloat", "serde", "serde_json", @@ -2011,6 +2027,18 @@ dependencies = [ "rand_core 0.6.4", ] +[[package]] +name = "range-collections" +version = "0.4.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ca9edd21e2db51000ac63eccddabba622f826e631a60be7bade9bd6a76b69537" +dependencies = [ + "binary-merge", + "inplace-vec-builder", + "ref-cast", + "smallvec", +] + [[package]] name = "ratatui" version = "0.26.3" @@ -2069,6 +2097,26 @@ dependencies = [ "thiserror", ] +[[package]] +name = "ref-cast" +version = "1.0.23" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ccf0a6f84d5f1d581da8b41b47ec8600871962f2a528115b542b362d4b744931" +dependencies = [ + "ref-cast-impl", +] + +[[package]] +name = "ref-cast-impl" +version = "1.0.23" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bcc303e793d3734489387d205e9b186fac9c6cfacedd98cbb2e8a5943595f3e6" +dependencies = [ + "proc-macro2", + "quote", + "syn 2.0.65", +] + [[package]] name = "regalloc2" version = "0.9.3" diff --git a/src/riscv/Cargo.toml b/src/riscv/Cargo.toml index 17fb865955a0..6c9d8a92b9aa 100644 --- a/src/riscv/Cargo.toml +++ b/src/riscv/Cargo.toml @@ -43,6 +43,7 @@ vm-fdt = "0.3.0" goldenfile = "1.7.1" arbitrary-int = "1.2.7" rustc-demangle = "0.1" +range-collections = "0.4.5" [workspace.dependencies.tezos-smart-rollup] path = "../kernel_sdk/sdk" diff --git a/src/riscv/lib/Cargo.toml b/src/riscv/lib/Cargo.toml index ef86d252c7c0..6ad9a3cde347 100644 --- a/src/riscv/lib/Cargo.toml +++ b/src/riscv/lib/Cargo.toml @@ -29,6 +29,7 @@ tezos-smart-rollup-utils.workspace = true thiserror.workspace = true vm-fdt.workspace = true itertools.workspace = true +range-collections.workspace = true [dependencies.ocaml] workspace = true diff --git a/src/riscv/lib/src/state_backend/proof_layout.rs b/src/riscv/lib/src/state_backend/proof_layout.rs index 411d8ee8d1f7..3f641e58fb5d 100644 --- a/src/riscv/lib/src/state_backend/proof_layout.rs +++ b/src/riscv/lib/src/state_backend/proof_layout.rs @@ -10,8 +10,8 @@ use super::{ }, verify_backend, Array, Atom, DynArray, Layout, Many, }; -use crate::{default::ConstDefault, storage::binary}; -use std::collections::BTreeMap; +use crate::{default::ConstDefault, state_backend, storage::binary}; +use serde::de::Error; /// Errors that may occur when parsing a Merkle proof #[derive(Debug, thiserror::Error)] @@ -133,7 +133,8 @@ where MerkleProofLeaf::Blind(_) => verify_backend::Region::Absent, MerkleProofLeaf::Read(data) => { let data: [T; LEN] = binary::deserialise(data.as_slice())?; - verify_backend::Region::Present(data) + let data = Box::new(data.map(Some)); + verify_backend::Region::Partial(data) } } } else { @@ -147,7 +148,7 @@ where impl ProofLayout for DynArray { fn from_proof(proof: ProofTree) -> FromProofResult { let mut pipeline = vec![(0usize, LEN, proof)]; - let mut pages = BTreeMap::new(); + let mut pages = Vec::new(); while let Some((start, length, tree)) = pipeline.pop() { if length <= super::MERKLE_LEAF_SIZE.get() { @@ -158,12 +159,20 @@ impl ProofLayout for DynArray { continue; }; - let data: Box<[u8]> = binary::deserialise(data)?; + let data: Box<[u8; state_backend::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(), + err.len() + )) + })? + }; - // TODO: Check data is the right length. - assert_eq!(data.len(), length); + let start = verify_backend::PageId::from_address(start); - pages.insert(start, data); + pages.push((start, data)); } else { // Expecting a branching point. diff --git a/src/riscv/lib/src/state_backend/verify_backend.rs b/src/riscv/lib/src/state_backend/verify_backend.rs index d3b3ea0cd0c9..c7e007752db7 100644 --- a/src/riscv/lib/src/state_backend/verify_backend.rs +++ b/src/riscv/lib/src/state_backend/verify_backend.rs @@ -2,9 +2,45 @@ // // SPDX-License-Identifier: MIT -use super::{Cell, EnrichedValue, ManagerBase}; -use crate::state_backend::owned_backend::Owned; -use std::collections::BTreeMap; +use super::{ + Cell, EnrichedValue, ManagerBase, ManagerClone, ManagerRead, ManagerReadWrite, ManagerWrite, +}; +use crate::state_backend::{owned_backend::Owned, MERKLE_LEAF_SIZE}; +use range_collections::RangeSet2; +use std::{ + array, + collections::BTreeMap, + mem::{self, MaybeUninit}, + ops::Index, + panic::resume_unwind, + slice, +}; + +/// Panic payload that is raised when a value isn't present in a part of the Verifier backend. +#[derive(Copy, Clone, Debug, Eq, PartialEq)] +struct NotFound; + +/// Raise a [`NotFound`] panic. +fn not_found() -> ! { + // TODO: RV-350: Ensure that panics are handled upstream + + // We use [`resume_unwind`] over [`panic_any`] to avoid calling the panic hook. + // XXX: This fails without a message when there is no matching [`handle_not_found`] wrapper. + resume_unwind(Box::new(NotFound)) +} + +/// Catch errors that the verifier backend may raise during the invocation of `f` and return them +/// as [`Err`]. +#[cfg(test)] +fn handle_not_found R + std::panic::UnwindSafe>(f: F) -> Result { + match std::panic::catch_unwind(f) { + Ok(res) => Ok(res), + Err(err) => match err.downcast::() { + Ok(not_found) => Err(*not_found), + Err(other) => resume_unwind(other), + }, + } +} /// Proof verification backend pub struct Verifier; @@ -12,28 +48,410 @@ pub struct Verifier; impl ManagerBase for Verifier { type Region = Region; - type DynRegion = DynRegion; + type DynRegion = DynRegion<{ MERKLE_LEAF_SIZE.get() }, LEN>; type EnrichedCell = EnrichedCell; type ManagerRoot = Self; } +impl ManagerRead for Verifier { + fn region_read(region: &Self::Region, index: usize) -> E { + region[index] + } + + fn region_ref(region: &Self::Region, index: usize) -> &E { + ®ion[index] + } + + fn region_read_all(region: &Self::Region) -> Vec { + (0..LEN).map(|index| region[index]).collect() + } + + fn dyn_region_read( + region: &Self::DynRegion, + address: usize, + ) -> E { + let mut value = MaybeUninit::::uninit(); + + // SAFETY: `raw_data` points to a byte slice which has same size as `E`. + let raw_data = unsafe { + slice::from_raw_parts_mut(value.as_mut_ptr().cast::(), mem::size_of::()) + }; + + region.read_bytes(address, raw_data); + + // SAFETY: `read_bytes` fully populates the contents of `values`. Additionally, `E: Elem` + // lets us know that any byte combination is valid. + let mut value = unsafe { value.assume_init() }; + + value.from_stored_in_place(); + + value + } + + fn dyn_region_read_all( + region: &Self::DynRegion, + address: usize, + values: &mut [E], + ) { + // SAFETY: `E: Elem` tells us that values of that type would be arranged contiguously in + // addition to values of `E` being valid for any raw byte combination. + // Hence, obtain a slice that points to the same underlying memory as `values` and populate + // it with the raw bytes. + let raw_values = unsafe { + let data = values.as_mut_ptr().cast::(); + let len = mem::size_of_val(values); + slice::from_raw_parts_mut(data, len) + }; + + // `read_bytes` fills the entire slice. + region.read_bytes(address, raw_values); + + for value in values { + value.from_stored_in_place(); + } + } + + fn enriched_cell_read_stored(cell: &Self::EnrichedCell) -> V::E + where + V: EnrichedValue, + V::E: Copy, + { + *Self::enriched_cell_ref_stored(cell) + } + + fn enriched_cell_read_derived(cell: &Self::EnrichedCell) -> V::D + where + V: super::EnrichedValueLinked, + V::D: Copy, + { + let stored = Self::enriched_cell_ref_stored(cell); + V::derive(stored) + } + + fn enriched_cell_ref_stored(cell: &Self::EnrichedCell) -> &V::E + where + V: EnrichedValue, + { + match cell { + EnrichedCell::Absent => not_found(), + EnrichedCell::Present(cell) => cell, + } + } +} + +impl ManagerWrite for Verifier { + fn region_write( + region: &mut Self::Region, + index: usize, + value: E, + ) { + match region { + Region::Absent => { + // We can't uses `[None; LEN]` because `E: Copy` is not given. + let mut data = Box::new(array::from_fn(|_| None)); + + data[index] = Some(value); + + *region = Region::Partial(data); + } + + Region::Partial(data) => { + data[index] = Some(value); + } + } + } + + fn region_write_all( + region: &mut Self::Region, + values: &[E], + ) { + for (i, &value) in values.iter().enumerate() { + Self::region_write(region, i, value); + } + } + + fn dyn_region_write( + region: &mut Self::DynRegion, + address: usize, + mut value: E, + ) { + value.to_stored_in_place(); + + let raw_data = unsafe { + let raw_ptr = (&value as *const E).cast::(); + let len = mem::size_of::(); + slice::from_raw_parts(raw_ptr, len) + }; + + region.write_bytes(address, raw_data); + } + + fn dyn_region_write_all( + region: &mut Self::DynRegion, + base_address: usize, + values: &[E], + ) { + for (i, &value) in values.iter().enumerate() { + let address = base_address + i * mem::size_of::(); + Self::dyn_region_write(region, address, value); + } + } + + fn enriched_cell_write(cell: &mut Self::EnrichedCell, value: V::E) + where + V: super::EnrichedValueLinked, + { + match cell { + EnrichedCell::Absent => *cell = EnrichedCell::Present(value), + EnrichedCell::Present(stored) => *stored = value, + } + } +} + +impl ManagerReadWrite for Verifier { + fn region_replace( + region: &mut Self::Region, + index: usize, + value: E, + ) -> E { + let old = Self::region_read(region, index); + Self::region_write(region, index, value); + old + } +} + +impl ManagerClone for Verifier { + fn clone_region( + region: &Self::Region, + ) -> Self::Region { + region.clone() + } + + fn clone_dyn_region(region: &Self::DynRegion) -> Self::DynRegion { + region.clone() + } + + fn clone_enriched_cell(cell: &Self::EnrichedCell) -> Self::EnrichedCell + where + V: EnrichedValue, + V::E: Copy, + V::D: Copy, + { + cell.clone() + } +} + /// Verifier region +#[derive(Clone)] pub enum Region { + // We maintain a separate [`Absent`] variant in order to save space for regions that aren't + // accessed at all. Absent, - Present([E; LEN]), + Partial( + // This needs to be boxed to prevent inflating the size of this type for absent regions. + Box<[Option; LEN]>, + ), +} + +impl Index for Region { + type Output = E; + + fn index(&self, index: usize) -> &Self::Output { + match self { + Region::Absent => not_found(), + Region::Partial(region) => match region.get(index).and_then(Option::as_ref) { + Some(value) => value, + None => not_found(), + }, + } + } +} + +/// Page identifier +#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)] +pub struct PageId(usize); + +impl PageId { + const LEAF_SIZE: usize = { + if LEAF_SIZE.count_ones() != 1 { + panic!("LEAF_SIZE must be a power of 2"); + } + + LEAF_SIZE + }; + + const LEAF_MASK: usize = !(Self::LEAF_SIZE - 1); + + /// Construct a page idetifier from an address. + pub fn from_address(address: usize) -> Self { + PageId(address & Self::LEAF_MASK) + } + + /// Calculate the offset of an address relative to the start of the identified page. + pub fn offset(&self, address: usize) -> Option { + address.checked_sub(self.0) + } +} + +/// Page of a dynamic region where sub-ranges may not be present +#[derive(Clone, Debug)] +pub struct Page { + data: Box<[u8; LEAF_SIZE]>, + available: RangeSet2, +} + +impl Page { + /// Construct a page where the entire data is present. + fn from_full(data: Box<[u8; LEAF_SIZE]>) -> Self { + let available = RangeSet2::from(0..LEAF_SIZE); + Page { data, available } + } + + /// Read a sub-range of the page. Only returns `Some` if the entire range is present. + fn get(&self, start: usize, len: usize) -> Option<&[u8]> { + if len > LEAF_SIZE.saturating_sub(start) { + return None; + } + + let range = start..start.saturating_add(len); + + // Superset means that `self.available` fully covers `range`. In other words, everything in + // `range` is also in `self.available`. + if !self.available.is_superset(&RangeSet2::::from(range)) { + return None; + } + + Some(&self.data[start..][..len]) + } + + /// Write to a range in the page. This makes that range available to subsequent reads. + fn put(&mut self, start: usize, data: &[u8]) -> bool { + if data.len() > LEAF_SIZE.saturating_sub(start) { + return false; + } + + self.available.union_with(&RangeSet2::::from( + start..data.len().saturating_add(start), + )); + + self.data[start..][..data.len()].copy_from_slice(data); + + true + } +} + +impl Default for Page { + fn default() -> Self { + Page { + data: Box::new([0; LEAF_SIZE]), + available: RangeSet2::empty(), + } + } } /// Verifier dynamic region -pub struct DynRegion { - _pages: BTreeMap>, +#[derive(Clone, Debug)] +pub struct DynRegion { + pages: BTreeMap, Page>, } -impl DynRegion { +impl DynRegion { + const SANE: bool = { + if LEN.rem_euclid(LEAF_SIZE) != 0 { + panic!("LEN must be a multiple of LEAF_SIZE") + } + + true + }; + /// Construct a verifier dynamic region using the given known pages. - pub fn from_pages(pages: BTreeMap>) -> Self { - DynRegion { _pages: pages } + pub fn from_pages( + pages: impl IntoIterator, Box<[u8; LEAF_SIZE]>)>, + ) -> Self { + if !Self::SANE { + unreachable!() + } + + let pages = pages + .into_iter() + .map(|(id, data)| (id, Page::from_full(data))) + .collect(); + + DynRegion { pages } + } + + /// Read bytes from the dynamic region. + pub fn read_bytes(&self, mut address: usize, mut buffer: &mut [u8]) { + if buffer.is_empty() { + return; + } + + if buffer.len() > LEN.saturating_sub(address) { + not_found() + } + + while !buffer.is_empty() { + let page_index = PageId::from_address(address); + + let Some(page) = self.pages.get(&page_index) else { + not_found() + }; + + let Some(offset) = page_index.offset(address) else { + not_found() + }; + + let chunk_length = buffer.len().min(LEAF_SIZE.saturating_sub(offset)); + + let dst = &mut buffer[..chunk_length]; + let Some(src) = page.get(offset, chunk_length) else { + not_found() + }; + dst.copy_from_slice(src); + + address = address.saturating_add(chunk_length); + buffer = &mut buffer[chunk_length..]; + } + } + + /// Write bytes to the dynamic region. + pub fn write_bytes(&mut self, mut address: usize, mut buffer: &[u8]) { + if buffer.is_empty() { + return; + } + + if buffer.len() > LEN.saturating_sub(address) { + not_found() + } + + while !buffer.is_empty() { + let page_index = PageId::from_address(address); + let page = self.pages.entry(page_index).or_default(); + + let Some(offset) = page_index.offset(address) else { + not_found() + }; + + let chunk_length = buffer.len().min(LEAF_SIZE.saturating_sub(offset)); + + let src = &buffer[..chunk_length]; + if !page.put(offset, src) { + not_found() + }; + + address = address.saturating_add(chunk_length); + buffer = &buffer[chunk_length..]; + } + } +} + +impl Default for DynRegion { + fn default() -> Self { + DynRegion { + pages: BTreeMap::new(), + } } } @@ -51,8 +469,297 @@ impl Cell { /// Construct a verifier cell with a value. pub fn from_owned(cell: Cell) -> Self { - let values = cell.into_region(); - let region = Region::Present(values); + let values = Box::new(cell.into_region().map(Some)); + let region = Region::Partial(values); Cell::bind(region) } } + +impl Clone for EnrichedCell +where + V::E: Clone, +{ + fn clone(&self) -> Self { + match self { + Self::Absent => Self::Absent, + Self::Present(value) => Self::Present(value.clone()), + } + } +} + +#[cfg(test)] +mod tests { + use super::*; + use crate::state_backend::{self, Cells, DynCells, EnrichedValueLinked}; + + /// Ensures that page indices are properly calculated. + #[test] + fn page_index() { + let page0 = [ + PageId::<4>::from_address(0), + PageId::<4>::from_address(1), + PageId::<4>::from_address(2), + PageId::<4>::from_address(3), + ]; + + let page4 = [ + PageId::<4>::from_address(4), + PageId::<4>::from_address(5), + PageId::<4>::from_address(6), + PageId::<4>::from_address(7), + ]; + + let page8 = [ + PageId::<4>::from_address(8), + PageId::<4>::from_address(9), + PageId::<4>::from_address(10), + PageId::<4>::from_address(11), + ]; + + page0.into_iter().fold((), |_, item| { + assert_eq!(item, page0[0]); + assert!(item < page4[0]); + assert!(item < page8[0]); + }); + + page4.into_iter().fold((), |_, item| { + assert!(item > page0[0]); + assert_eq!(item, page4[0]); + assert!(item < page8[0]); + }); + + page8.into_iter().fold((), |_, item| { + assert!(item > page0[0]); + assert!(item > page4[0]); + assert_eq!(item, page8[0]); + }); + } + + /// Proptest value for a partial region + type PartialRegionArb = Box<[Option; LEN]>; + + /// Proptest value for a region + type RegionArb = Option>; + + /// Construct [`Cells`] from a proptest value. + fn arb_to_cells(region: RegionArb) -> Cells { + let region = match region { + Some(data) => Region::Partial(data), + None => Region::Absent, + }; + + Cells::bind(region) + } + + /// Check functionality of a region that is partially present. + #[test] + fn region_present() { + proptest::proptest!(|(reg: PartialRegionArb)| { + let mut cells: Cells<_, 32, Verifier> = arb_to_cells(Some(reg.clone())); + + for i in 0..32 { + let value = handle_not_found(|| cells.read(i)).ok(); + proptest::prop_assert_eq!(value, reg[i]); + + let new_value = rand::random(); + cells.write(i, new_value); + + let read_value = cells.read(i); + proptest::prop_assert_eq!(read_value, new_value); + } + }); + } + + /// Check functionality of a region that is absent. + #[test] + fn region_absent() { + let cells: Cells = arb_to_cells(None); + + for i in 0..32 { + let value = handle_not_found(|| cells.read(i)).ok(); + assert_eq!(value, None); + } + } + + /// Construct a [`state_backend::EnrichedCell`] from a proptest value. + fn arb_to_enriched_cell( + value: Option, + ) -> state_backend::EnrichedCell { + let cell = match value { + Some(value) => EnrichedCell::Present(value), + None => EnrichedCell::Absent, + }; + state_backend::EnrichedCell::bind(cell) + } + + /// Check the functionality of an enriched cell whose value may or may not be present. + #[test] + fn enriched_cell() { + struct Ident; + + #[derive(Clone, Copy, Debug, Eq, PartialEq)] + struct Derived(u64); + + impl From<&'_ u64> for Derived { + fn from(value: &u64) -> Self { + Derived(*value) + } + } + + impl EnrichedValue for Ident { + type E = u64; + + type D = Derived; + } + + proptest::proptest!(|(initial: Option)| { + let mut cell = arb_to_enriched_cell::(initial); + + let stored = handle_not_found(|| cell.read_stored()).ok(); + proptest::prop_assert_eq!(stored, initial); + + let derived = handle_not_found(|| cell.read_derived()).ok(); + let expected_derived = initial.as_ref().map(>::derive); + proptest::prop_assert_eq!(derived, expected_derived); + + let new_value = rand::random(); + cell.write(new_value); + + let read_value = cell.read_stored(); + proptest::prop_assert_eq!(read_value, new_value); + + let new_derived = >::derive(&new_value); + let read_derived = cell.read_derived(); + proptest::prop_assert_eq!(read_derived, new_derived); + }); + } + + macro_rules! assert_eq_found { + ( $left:expr, $right:expr ) => { + assert_eq!(handle_not_found(|| { $left }), Ok($right)); + }; + } + + macro_rules! assert_not_found { + ( $body:expr ) => { + assert_eq!(handle_not_found(|| { $body }), Err(NotFound)); + }; + } + + /// Check the read functionality of a region that has no gaps between its pages. + #[test] + fn dyn_region_continuous() { + const LEAF_SIZE: usize = MERKLE_LEAF_SIZE.get(); + + let mut dyn_region = DynRegion::default(); + dyn_region.write_bytes( + 0, + [1, 3, 3, 7] + .into_iter() + .cycle() + .take(LEAF_SIZE) + .collect::>() + .as_slice(), + ); + dyn_region.write_bytes( + LEAF_SIZE, + [11, 14, 14, 15] + .into_iter() + .cycle() + .take(LEAF_SIZE) + .collect::>() + .as_slice(), + ); + + let mut dyn_cells: DynCells<{ 3 * LEAF_SIZE }, Verifier> = DynCells::bind(dyn_region); + + // Read things that are contained in the first leaf. + assert_eq_found!(dyn_cells.read::<[u8; 4]>(0), [1, 3, 3, 7]); + assert_eq_found!(dyn_cells.read::<[u8; 4]>(1), [3, 3, 7, 1]); + assert_eq_found!(dyn_cells.read::<[u8; 4]>(LEAF_SIZE - 4), [1, 3, 3, 7]); + + // Read things that span the first and second leaf. + assert_eq_found!(dyn_cells.read::<[u8; 4]>(LEAF_SIZE - 2), [3, 7, 11, 14]); + + // Read things that are contained in the second leaf. + assert_eq_found!(dyn_cells.read::<[u8; 4]>(LEAF_SIZE), [11, 14, 14, 15]); + assert_eq_found!(dyn_cells.read::<[u8; 4]>(LEAF_SIZE + 1), [14, 14, 15, 11]); + + // Read more than is available. + assert_not_found!(dyn_cells.read::<[u8; LEAF_SIZE * 3 + 1]>(0)); + + // Read at an offset that is out of bounds. + assert_not_found!(dyn_cells.read::(LEAF_SIZE * 2)); + + // Write to an index that is out of bounds. + assert_not_found!(dyn_cells.clone().write(LEAF_SIZE * 3, 0u8)); + + // Add more to the third leaf. + let dyn_cells = handle_not_found(move || { + dyn_cells.write(LEAF_SIZE * 2, [255u8, 0]); + dyn_cells + }) + .unwrap(); + assert_eq_found!( + dyn_cells.read::<[u8; 6]>(LEAF_SIZE * 2 - 4), + [11, 14, 14, 15, 255, 0] + ); + assert_eq_found!(dyn_cells.read::<[u8; 2]>(LEAF_SIZE * 2), [255, 0]); + assert_not_found!(dyn_cells.read::<[u8; 4]>(LEAF_SIZE * 2)); + assert_not_found!(dyn_cells.read::<[u8; 2]>(LEAF_SIZE * 2 + 2)); + + // Read at an offset that is out of bounds. + assert_not_found!(dyn_cells.read::(LEAF_SIZE * 3)); + } + + /// Check the functionality of a region that has gaps between its pages. + #[test] + fn dyn_region_gaps() { + const LEAF_SIZE: usize = MERKLE_LEAF_SIZE.get(); + + let mut dyn_region = DynRegion::default(); + dyn_region.write_bytes( + 0, + [7, 3, 3] + .into_iter() + .cycle() + .take(LEAF_SIZE) + .collect::>() + .as_slice(), + ); + dyn_region.write_bytes( + LEAF_SIZE * 2, + [42, 41] + .into_iter() + .cycle() + .take(LEAF_SIZE) + .collect::>() + .as_slice(), + ); + + let mut dyn_cells: DynCells<{ 3 * LEAF_SIZE }, Verifier> = DynCells::bind(dyn_region); + + assert_eq_found!(dyn_cells.read::<[u8; 3]>(0), [7, 3, 3]); + assert_eq_found!(dyn_cells.read::<[u8; 2]>(1), [3, 3]); + assert_eq_found!(dyn_cells.read::<[u8; 1]>(LEAF_SIZE * 2), [42]); + assert_eq_found!(dyn_cells.read::<[u8; 1]>(LEAF_SIZE * 2 + 1), [41]); + + // Read a range that covers a gap. + assert_not_found!(dyn_cells.read::<[u8; LEAF_SIZE + 4]>(LEAF_SIZE - 2)); + assert_not_found!(dyn_cells.read::<[u8; LEAF_SIZE]>(LEAF_SIZE)); + + // Write within the gap. + let dyn_cells = handle_not_found(move || { + dyn_cells.write(LEAF_SIZE - 1, [1u8, 1, 3]); + dyn_cells + }) + .unwrap(); + + assert_eq_found!(dyn_cells.read::<[u8; 3]>(LEAF_SIZE - 1), [1, 1, 3]); + assert_eq_found!(dyn_cells.read::<[u8; 2]>(LEAF_SIZE), [1, 3]); + assert_eq_found!(dyn_cells.read::<[u8; 4]>(LEAF_SIZE - 2), [3, 1, 1, 3]); + + assert_not_found!(dyn_cells.read::<[u8; 6]>(LEAF_SIZE - 1)); + assert_not_found!(dyn_cells.read::<[u8; 4]>(LEAF_SIZE)); + } +} diff --git a/src/rust_deps/Cargo.lock b/src/rust_deps/Cargo.lock index f011ca35b07a..156865dc5f4f 100644 --- a/src/rust_deps/Cargo.lock +++ b/src/rust_deps/Cargo.lock @@ -244,6 +244,12 @@ dependencies = [ "subtle", ] +[[package]] +name = "binary-merge" +version = "0.1.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "597bb81c80a54b6a4381b23faba8d7774b144c94cbd1d6fe3f1329bd776554ab" + [[package]] name = "bincode" version = "1.3.3" @@ -1995,6 +2001,15 @@ dependencies = [ "hashbrown 0.15.2", ] +[[package]] +name = "inplace-vec-builder" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "cf64c2edc8226891a71f127587a2861b132d2b942310843814d5001d99a1d307" +dependencies = [ + "smallvec", +] + [[package]] name = "instant" version = "0.1.13" @@ -2563,6 +2578,7 @@ dependencies = [ "ocaml", "ocaml-build", "paste", + "range-collections", "rustc_apfloat", "serde", "serde_json", @@ -3088,6 +3104,18 @@ dependencies = [ "rand_core 0.5.1", ] +[[package]] +name = "range-collections" +version = "0.4.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ca9edd21e2db51000ac63eccddabba622f826e631a60be7bade9bd6a76b69537" +dependencies = [ + "binary-merge", + "inplace-vec-builder", + "ref-cast", + "smallvec", +] + [[package]] name = "raw-cpuid" version = "10.7.0" @@ -3172,6 +3200,26 @@ dependencies = [ "thiserror", ] +[[package]] +name = "ref-cast" +version = "1.0.23" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ccf0a6f84d5f1d581da8b41b47ec8600871962f2a528115b542b362d4b744931" +dependencies = [ + "ref-cast-impl", +] + +[[package]] +name = "ref-cast-impl" +version = "1.0.23" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bcc303e793d3734489387d205e9b186fac9c6cfacedd98cbb2e8a5943595f3e6" +dependencies = [ + "proc-macro2", + "quote", + "syn 2.0.89", +] + [[package]] name = "regalloc2" version = "0.5.1" -- GitLab From 67fdd5dd979e0d13e7792c4a26da7c5b3d7bfdf1 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Ole=20Kr=C3=BCger?= Date: Tue, 17 Dec 2024 11:56:15 +0000 Subject: [PATCH 2/3] RISC-V: PVM stepper exercises PVM during verification --- src/riscv/lib/src/stepper/pvm.rs | 71 +++++++++++++++++++++----------- 1 file changed, 47 insertions(+), 24 deletions(-) diff --git a/src/riscv/lib/src/stepper/pvm.rs b/src/riscv/lib/src/stepper/pvm.rs index e3cd57e91e34..b31aec08b567 100644 --- a/src/riscv/lib/src/stepper/pvm.rs +++ b/src/riscv/lib/src/stepper/pvm.rs @@ -20,7 +20,7 @@ use crate::{ owned_backend::Owned, proof_backend::{merkle::Merkleisable, proof::Proof, ProofGen}, verify_backend::Verifier, - AllocatedOf, CommitmentLayout, FnManagerIdent, ProofLayout, ProofTree, Ref, RefOwnedAlloc, + AllocatedOf, CommitmentLayout, FnManagerIdent, ProofLayout, ProofTree, Ref, }, storage::binary, }; @@ -52,7 +52,7 @@ pub struct PvmStepper< origination_level: u32, } -impl<'hooks, ML: MainMemoryLayout, CL: CacheLayouts> PvmStepper<'hooks, ML, CL> { +impl<'hooks, ML: MainMemoryLayout, CL: CacheLayouts> PvmStepper<'hooks, ML, CL, Owned> { /// Create a new PVM stepper. pub fn new( program: &[u8], @@ -78,6 +78,16 @@ impl<'hooks, ML: MainMemoryLayout, CL: CacheLayouts> PvmStepper<'hooks, ML, CL> }) } + /// Obtain the root hash for the PVM state. + pub fn hash(&self) -> Hash { + let refs = self.pvm.struct_ref::(); + PvmLayout::::state_hash(refs).unwrap() + } +} + +impl<'hooks, ML: MainMemoryLayout, CL: CacheLayouts, M: ManagerReadWrite> + PvmStepper<'hooks, ML, CL, M> +{ /// Non-continuing variant of [`Stepper::step_max`] fn step_max_once(&mut self, steps: Bound) -> StepperStatus { match self.pvm.status() { @@ -135,33 +145,28 @@ impl<'hooks, ML: MainMemoryLayout, CL: CacheLayouts> PvmStepper<'hooks, ML, CL> } } - /// Obtain the root hash for the PVM state. - pub fn hash(&self) -> Hash { - let refs = self.pvm.struct_ref::(); - PvmLayout::::state_hash(refs).unwrap() - } - /// Create a new stepper in which the existing PVM is managed by /// the proof-generating backend. - pub fn start_proof_mode<'a>(&'a self) -> PvmStepper<'hooks, ML, CL, ProofGen>> { - PvmStepper::<'hooks, ML, CL, ProofGen>> { + pub fn start_proof_mode<'a>(&'a self) -> PvmStepper<'hooks, ML, CL, ProofGen>> { + PvmStepper::<'hooks, ML, CL, ProofGen>> { pvm: self.pvm.start_proof(), - hooks: PvmHooks::none(), - inbox: self.inbox.clone(), rollup_address: self.rollup_address, origination_level: self.origination_level, + + // The inbox needs to be cloned because we should not mutate it through the new stepper + // instance. + inbox: self.inbox.clone(), + + // We don't want to re-use the same hooks to avoid polluting logs with refutation game + // output. Instead we use hooks that don't do anything. + hooks: PvmHooks::none(), } } /// Verify a Merkle proof. The [`PvmStepper`] is used for inbox information. pub fn verify_proof(&self, proof: Proof) -> bool { // Allow some warnings while this method goes through iterations. - #![allow( - dead_code, - unreachable_code, - unused_variables, - clippy::diverging_sub_expression - )] + #![allow(unreachable_code, unused_variables, clippy::diverging_sub_expression)] let proof_tree = ProofTree::Present(proof.tree()); let Some(space) = PvmLayout::::from_proof(proof_tree).ok() else { @@ -169,12 +174,30 @@ impl<'hooks, ML: MainMemoryLayout, CL: CacheLayouts> PvmStepper<'hooks, ML, CL> }; let pvm = Pvm::::bind(space); + let mut stepper = PvmStepper { + pvm, + rollup_address: self.rollup_address, + origination_level: self.origination_level, + + // The inbox needs to be cloned because we should not mutate it through the new stepper + // instance. + inbox: self.inbox.clone(), - // TODO: RV-361: Exercise the PVM - todo!("Can't exercise the PVM during proof verification yet"); + // We don't want to re-use the same hooks to avoid polluting logs with refutation game + // output. Instead we use hooks that don't do anything. + hooks: PvmHooks::none(), + }; + + match stepper.step_max_once(Bound::Included(1)) { + // We don't include errors in this case because errors count as 0 steps. That means if + // we receive a [`StepperStatus::Errored`] with `steps: 1` then it tried to run 2 steps + // but failed at the second. + StepperStatus::Running { steps: 1 } | StepperStatus::Exited { steps: 1, .. } => {} + _ => return false, + } // TODO: RV-362: Check the final state - let refs = pvm.struct_ref::(); + let _refs = stepper.pvm.struct_ref::(); let hash: Hash = todo!("Can't obtain the hash of a verification state yet"); &hash == proof.final_state_hash() @@ -182,7 +205,7 @@ impl<'hooks, ML: MainMemoryLayout, CL: CacheLayouts> PvmStepper<'hooks, ML, CL> /// 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(&self) -> RefOwnedAlloc> { + pub fn struct_ref(&self) -> AllocatedOf, Ref<'_, M>> { self.pvm.struct_ref::() } @@ -190,8 +213,8 @@ impl<'hooks, ML: MainMemoryLayout, CL: CacheLayouts> PvmStepper<'hooks, ML, CL> /// ephemeral state that doesn't make it into the serialised output. pub fn rebind_via_serde(&mut self) where - for<'a> RefOwnedAlloc<'a, PvmLayout>: Serialize, - AllocatedOf, Owned>: DeserializeOwned, + for<'a> AllocatedOf, Ref<'a, M>>: Serialize, + AllocatedOf, M>: DeserializeOwned, { let space = { let refs = self.pvm.struct_ref::(); -- GitLab From 6c548784e2f283aeae8dae43307511a9c69b9f90 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Ole=20Kr=C3=BCger?= Date: Tue, 17 Dec 2024 11:56:15 +0000 Subject: [PATCH 3/3] RISC-V: Node PVM is exercised during verification --- src/riscv/lib/src/ocaml_api.rs | 28 ++++++++++++++++++++++------ 1 file changed, 22 insertions(+), 6 deletions(-) diff --git a/src/riscv/lib/src/ocaml_api.rs b/src/riscv/lib/src/ocaml_api.rs index 29293aa15a4f..32f576871c55 100644 --- a/src/riscv/lib/src/ocaml_api.rs +++ b/src/riscv/lib/src/ocaml_api.rs @@ -11,7 +11,9 @@ use crate::{ node_pvm::{NodePvm, PvmStorage, PvmStorageError}, PvmHooks, PvmStatus, }, - state_backend::{owned_backend::Owned, proof_backend::proof::serialise_proof}, + state_backend::{ + hash::Hash, owned_backend::Owned, proof_backend::proof::serialise_proof, ManagerReadWrite, + }, }; use crate::{ state_backend::proof_backend::proof, @@ -393,7 +395,7 @@ pub fn octez_riscv_mut_state_hash(state: Pointer) -> [u8; 32] { state.apply_ro(NodePvm::hash).into() } -fn apply_set_input(pvm: &mut NodePvm, input: Input) { +fn apply_set_input(pvm: &mut NodePvm, input: Input) { match input { Input::InboxMessage(level, message_counter, payload) => { pvm.set_input_message(level, message_counter, payload.to_vec()) @@ -467,14 +469,28 @@ pub fn octez_riscv_proof_stop_state(_proof: Pointer) -> [u8; 32] { #[ocaml::func] #[ocaml::sig("input option -> proof -> input_request option")] +// Allow some warnings while this method goes through iterations. +#[allow(unreachable_code, unused_variables, clippy::diverging_sub_expression)] pub unsafe fn octez_riscv_verify_proof( proof: Pointer, - _input: Option, + input: Option, ) -> Option> { - let _state = NodePvm::from_proof(proof.as_ref().tree())?; + let mut state = NodePvm::from_proof(proof.as_ref().tree())?; + + match input { + Some(input) => apply_set_input(&mut state, input), + None => state.compute_step(&mut PvmHooks::none()), + } + + // TODO: RV-362: Check the final state + let hash: Hash = todo!("Can't obtain the final state hash just yet"); + + if &hash != proof.as_ref().final_state_hash() { + return None; + } - // TODO: RV-369: Run a step over the PVM state - todo!("Can't verify proof just yet") + // TODO: RV-336: Need to construct InputRequest + Some(Pointer::from(InputRequest)) } #[ocaml::func] -- GitLab