cairo_vm/vm/runners/
cairo_pie.rs

1use super::cairo_runner::ExecutionResources;
2use crate::stdlib::prelude::{String, Vec};
3use crate::types::builtin_name::BuiltinName;
4use crate::vm::errors::cairo_pie_errors::CairoPieValidationError;
5use crate::{
6    stdlib::{collections::HashMap, prelude::*},
7    types::relocatable::{MaybeRelocatable, Relocatable},
8    Felt252,
9};
10use num_traits::{One, Zero};
11use serde::{Deserialize, Serialize};
12#[cfg(feature = "std")]
13use {
14    std::{fs::File, io::Write, path::Path},
15    zip::ZipWriter,
16};
17
18const CAIRO_PIE_VERSION: &str = "1.1";
19
20#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
21pub struct SegmentInfo {
22    pub index: isize,
23    pub size: usize,
24}
25
26impl From<(isize, usize)> for SegmentInfo {
27    fn from(value: (isize, usize)) -> Self {
28        SegmentInfo {
29            index: value.0,
30            size: value.1,
31        }
32    }
33}
34
35// A simplified version of Memory, without any additional data besides its elements
36// Contains all addr-value pairs, ordered by index and offset
37// Allows practical serialization + conversion between CairoPieMemory & Memory
38#[derive(Serialize, Deserialize, Clone, Debug, Eq)]
39pub struct CairoPieMemory(
40    #[serde(serialize_with = "serde_impl::serialize_memory")]
41    pub  Vec<((usize, usize), MaybeRelocatable)>,
42);
43
44impl PartialEq for CairoPieMemory {
45    fn eq(&self, other: &Self) -> bool {
46        fn as_hashmap(
47            cairo_pie_memory: &CairoPieMemory,
48        ) -> HashMap<&(usize, usize), &MaybeRelocatable> {
49            cairo_pie_memory
50                .0
51                .iter()
52                .map(|tuple| (&tuple.0, &tuple.1))
53                .collect::<HashMap<&(usize, usize), &MaybeRelocatable>>()
54        }
55        as_hashmap(self) == as_hashmap(other)
56    }
57}
58
59#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
60pub struct PublicMemoryPage {
61    pub start: usize,
62    pub size: usize,
63}
64
65impl From<&Vec<usize>> for PublicMemoryPage {
66    fn from(vec: &Vec<usize>) -> Self {
67        Self {
68            start: vec[0],
69            size: vec[1],
70        }
71    }
72}
73
74// HashMap value based on starknet/core/os/output.cairo usage
75pub type Attributes = HashMap<String, Vec<usize>>;
76pub type Pages = HashMap<usize, PublicMemoryPage>;
77
78#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
79pub struct OutputBuiltinAdditionalData {
80    #[serde(with = "serde_impl::pages")]
81    pub pages: Pages,
82    pub attributes: Attributes,
83}
84
85#[derive(Serialize, Deserialize, Clone, Debug, Eq)]
86#[serde(untagged)]
87pub enum BuiltinAdditionalData {
88    // Catch empty lists under the `Empty` variant.
89    Empty([(); 0]),
90    // Contains verified addresses as contiguous index, value pairs
91    #[serde(with = "serde_impl::hash_additional_data")]
92    Hash(Vec<Relocatable>),
93    Output(OutputBuiltinAdditionalData),
94    // Signatures are composed of (r, s) tuples
95    #[serde(with = "serde_impl::signature_additional_data")]
96    Signature(HashMap<Relocatable, (Felt252, Felt252)>),
97    None,
98}
99
100impl BuiltinAdditionalData {
101    fn is_empty(&self) -> bool {
102        match self {
103            Self::Empty(_) => true,
104            Self::Hash(data) => data.is_empty(),
105            Self::Signature(data) => data.is_empty(),
106            Self::Output(_) => false,
107            Self::None => false,
108        }
109    }
110}
111
112impl PartialEq for BuiltinAdditionalData {
113    fn eq(&self, other: &BuiltinAdditionalData) -> bool {
114        match (self, other) {
115            (Self::Hash(data), Self::Hash(other_data)) => data == other_data,
116            (Self::Signature(data), Self::Signature(other_data)) => data == other_data,
117            (Self::Output(data), Self::Output(other_data)) => data == other_data,
118            (Self::None, Self::None) => true,
119            (Self::Empty(_), x) | (x, Self::Empty(_)) => x.is_empty(),
120            _ => false,
121        }
122    }
123}
124
125#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
126pub struct CairoPieAdditionalData(
127    #[serde(with = "crate::types::builtin_name::serde_generic_map_impl")]
128    pub  HashMap<BuiltinName, BuiltinAdditionalData>,
129);
130
131#[derive(Serialize, Clone, Debug, PartialEq, Eq)]
132pub struct CairoPie {
133    pub metadata: CairoPieMetadata,
134    pub memory: CairoPieMemory,
135    pub execution_resources: ExecutionResources,
136    pub additional_data: CairoPieAdditionalData,
137    pub version: CairoPieVersion,
138}
139
140#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
141pub struct CairoPieMetadata {
142    pub program: StrippedProgram,
143    pub program_segment: SegmentInfo,
144    pub execution_segment: SegmentInfo,
145    pub ret_fp_segment: SegmentInfo,
146    pub ret_pc_segment: SegmentInfo,
147    #[serde(serialize_with = "serde_impl::serialize_builtin_segments")]
148    pub builtin_segments: HashMap<BuiltinName, SegmentInfo>,
149    pub extra_segments: Vec<SegmentInfo>,
150}
151
152#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
153pub struct StrippedProgram {
154    #[serde(with = "serde_impl::program_data")]
155    pub data: Vec<MaybeRelocatable>,
156    pub builtins: Vec<BuiltinName>,
157    pub main: usize,
158    // Dummy field
159    #[serde(with = "serde_impl::prime")]
160    pub prime: (),
161}
162
163#[derive(Serialize, Deserialize, Clone, Debug, PartialEq, Eq)]
164pub struct CairoPieVersion {
165    // Dummy field
166    #[serde(with = "serde_impl::version")]
167    pub cairo_pie: (),
168}
169
170impl CairoPieMetadata {
171    pub(crate) fn run_validity_checks(&self) -> Result<(), CairoPieValidationError> {
172        if self.program.main > self.program.data.len() {
173            return Err(CairoPieValidationError::InvalidMainAddress);
174        }
175        if self.program.data.len() != self.program_segment.size {
176            return Err(CairoPieValidationError::ProgramLenVsSegmentSizeMismatch);
177        }
178        if self.builtin_segments.len() != self.program.builtins.len()
179            || !self
180                .program
181                .builtins
182                .iter()
183                .all(|b| self.builtin_segments.contains_key(b))
184        {
185            return Err(CairoPieValidationError::BuiltinListVsSegmentsMismatch);
186        }
187        if !self.ret_fp_segment.size.is_zero() {
188            return Err(CairoPieValidationError::InvalidRetFpSegmentSize);
189        }
190        if !self.ret_pc_segment.size.is_zero() {
191            return Err(CairoPieValidationError::InvalidRetPcSegmentSize);
192        }
193        self.validate_segment_order()
194    }
195
196    fn validate_segment_order(&self) -> Result<(), CairoPieValidationError> {
197        if !self.program_segment.index.is_zero() {
198            return Err(CairoPieValidationError::InvalidProgramSegmentIndex);
199        }
200        if !self.execution_segment.index.is_one() {
201            return Err(CairoPieValidationError::InvalidExecutionSegmentIndex);
202        }
203        for (i, builtin_name) in self.program.builtins.iter().enumerate() {
204            // We can safely index as run_validity_checks already ensures that the keys match
205            if self.builtin_segments[builtin_name].index != 2 + i as isize {
206                return Err(CairoPieValidationError::InvalidBuiltinSegmentIndex(
207                    *builtin_name,
208                ));
209            }
210        }
211        let n_builtins = self.program.builtins.len() as isize;
212        if self.ret_fp_segment.index != n_builtins + 2 {
213            return Err(CairoPieValidationError::InvalidRetFpSegmentIndex);
214        }
215        if self.ret_pc_segment.index != n_builtins + 3 {
216            return Err(CairoPieValidationError::InvalidRetPcSegmentIndex);
217        }
218        for (i, segment) in self.extra_segments.iter().enumerate() {
219            if segment.index != 4 + n_builtins + i as isize {
220                return Err(CairoPieValidationError::InvalidExtraSegmentIndex);
221            }
222        }
223        Ok(())
224    }
225}
226
227impl CairoPie {
228    /// Check that self is a valid Cairo PIE
229    pub fn run_validity_checks(&self) -> Result<(), CairoPieValidationError> {
230        self.metadata.run_validity_checks()?;
231        self.run_memory_validity_checks()?;
232        if self.execution_resources.builtin_instance_counter.len()
233            != self.metadata.program.builtins.len()
234            || !self.metadata.program.builtins.iter().all(|b| {
235                self.execution_resources
236                    .builtin_instance_counter
237                    .contains_key(b)
238            })
239        {
240            return Err(CairoPieValidationError::BuiltinListVsSegmentsMismatch);
241        }
242        Ok(())
243    }
244
245    fn run_memory_validity_checks(&self) -> Result<(), CairoPieValidationError> {
246        let mut segment_sizes = vec![
247            &self.metadata.program_segment,
248            &self.metadata.execution_segment,
249            &self.metadata.ret_fp_segment,
250            &self.metadata.ret_pc_segment,
251        ];
252        segment_sizes.extend(self.metadata.builtin_segments.values());
253        segment_sizes.extend(self.metadata.extra_segments.iter());
254        let segment_sizes: HashMap<isize, usize> =
255            HashMap::from_iter(segment_sizes.iter().map(|si| (si.index, si.size)));
256
257        let validate_addr = |addr: Relocatable| -> Result<(), CairoPieValidationError> {
258            if segment_sizes
259                .get(&addr.segment_index)
260                .is_none_or(|size| addr.offset > *size)
261            {
262                return Err(CairoPieValidationError::InvalidAddress);
263            }
264            Ok(())
265        };
266
267        for ((si, so), _) in self.memory.0.iter() {
268            validate_addr((*si as isize, *so).into())?;
269        }
270        Ok(())
271    }
272
273    /// Checks that the pie received is identical to self, skipping the fields execution_resources.n_steps, and additional_data[pedersen]
274    /// Stricter runs check more Pedersen addresses leading to different address lists
275    pub fn check_pie_compatibility(&self, pie: &CairoPie) -> Result<(), CairoPieValidationError> {
276        if self.metadata != pie.metadata {
277            return Err(CairoPieValidationError::DiffMetadata);
278        }
279        if self.memory != pie.memory {
280            return Err(CairoPieValidationError::DiffMemory);
281        }
282        if self.execution_resources.n_steps != pie.execution_resources.n_steps
283            || self.execution_resources.builtin_instance_counter
284                != pie.execution_resources.builtin_instance_counter
285        {
286            return Err(CairoPieValidationError::DiffExecutionResources);
287        }
288        if self.additional_data.0.len() != pie.additional_data.0.len() {
289            return Err(CairoPieValidationError::DiffAdditionalData);
290        }
291        for (name, data) in self.additional_data.0.iter() {
292            // As documented above, we skip the pedersen field when comparing.
293            if *name == BuiltinName::pedersen {
294                continue;
295            }
296            if !pie.additional_data.0.get(name).is_some_and(|d| d == data) {
297                return Err(CairoPieValidationError::DiffAdditionalDataForBuiltin(*name));
298            }
299        }
300        Ok(())
301    }
302
303    #[cfg(feature = "std")]
304    pub fn write_zip_file(
305        &self,
306        file_path: &Path,
307        merge_extra_segments: bool,
308    ) -> Result<(), std::io::Error> {
309        let mut metadata = self.metadata.clone();
310
311        let segment_offsets = if merge_extra_segments {
312            if let Some((segment, segment_offsets)) = self.merge_extra_segments() {
313                metadata.extra_segments = vec![segment];
314                Some(segment_offsets)
315            } else {
316                None
317            }
318        } else {
319            None
320        };
321
322        let file = File::create(file_path)?;
323        let mut zip_writer = ZipWriter::new(file);
324        let options =
325            zip::write::FileOptions::default().compression_method(zip::CompressionMethod::Deflated);
326
327        zip_writer.start_file("version.json", options)?;
328        serde_json::to_writer(&mut zip_writer, &self.version)?;
329        zip_writer.start_file("metadata.json", options)?;
330        serde_json::to_writer(&mut zip_writer, &metadata)?;
331        zip_writer.start_file("memory.bin", options)?;
332        zip_writer.write_all(&self.memory.to_bytes(segment_offsets))?;
333        zip_writer.start_file("additional_data.json", options)?;
334        serde_json::to_writer(&mut zip_writer, &self.additional_data)?;
335        zip_writer.start_file("execution_resources.json", options)?;
336        serde_json::to_writer(&mut zip_writer, &self.execution_resources)?;
337        zip_writer.finish()?;
338        Ok(())
339    }
340
341    #[cfg(feature = "std")]
342    pub fn from_zip_archive<R: std::io::Read + std::io::Seek>(
343        mut zip_reader: zip::ZipArchive<R>,
344    ) -> Result<CairoPie, std::io::Error> {
345        use std::io::Read;
346
347        let version = match zip_reader.by_name("version.json") {
348            Ok(version_buffer) => {
349                let reader = std::io::BufReader::new(version_buffer);
350                serde_json::from_reader(reader)?
351            }
352            Err(_) => CairoPieVersion { cairo_pie: () },
353        };
354
355        let reader = std::io::BufReader::new(zip_reader.by_name("metadata.json")?);
356        let metadata: CairoPieMetadata = serde_json::from_reader(reader)?;
357
358        let mut memory = vec![];
359        zip_reader.by_name("memory.bin")?.read_to_end(&mut memory)?;
360        let memory = CairoPieMemory::from_bytes(&memory)
361            .ok_or_else(|| std::io::Error::from(std::io::ErrorKind::InvalidData))?;
362
363        let reader = std::io::BufReader::new(zip_reader.by_name("execution_resources.json")?);
364        let execution_resources: ExecutionResources = serde_json::from_reader(reader)?;
365
366        let reader = std::io::BufReader::new(zip_reader.by_name("additional_data.json")?);
367        let additional_data: CairoPieAdditionalData = serde_json::from_reader(reader)?;
368
369        Ok(CairoPie {
370            metadata,
371            memory,
372            execution_resources,
373            additional_data,
374            version,
375        })
376    }
377
378    #[cfg(feature = "std")]
379    pub fn from_bytes(bytes: &[u8]) -> Result<Self, std::io::Error> {
380        let reader = std::io::Cursor::new(bytes);
381        let zip_archive = zip::ZipArchive::new(reader)?;
382
383        Self::from_zip_archive(zip_archive)
384    }
385
386    #[cfg(feature = "std")]
387    pub fn read_zip_file(path: &Path) -> Result<Self, std::io::Error> {
388        let file = File::open(path)?;
389        let zip = zip::ZipArchive::new(file)?;
390
391        Self::from_zip_archive(zip)
392    }
393
394    // Heavily inspired in:
395    // https://github.com/starkware-libs/cairo-lang/blob/8276ac35830148a397e1143389f23253c8b80e93/src/starkware/cairo/lang/vm/cairo_pie.py#L286-L306
396    /// Merges `extra_segments` to a single segment.
397    ///
398    /// Returns a tuple with the new `extra_segments` (containing just the merged segment)
399    /// and a HashMap with the old segment indices mapped to their new offset in the new segment
400    #[cfg(feature = "std")]
401    fn merge_extra_segments(&self) -> Option<(SegmentInfo, HashMap<usize, Relocatable>)> {
402        if self.metadata.extra_segments.is_empty() {
403            return None;
404        }
405
406        let new_index = self.metadata.extra_segments[0].index;
407        let mut accumulated_size = 0;
408        let offsets: HashMap<usize, Relocatable> = self
409            .metadata
410            .extra_segments
411            .iter()
412            .map(|seg| {
413                let value = (
414                    seg.index as usize,
415                    Relocatable {
416                        segment_index: new_index,
417                        offset: accumulated_size,
418                    },
419                );
420
421                accumulated_size += seg.size;
422
423                value
424            })
425            .collect();
426
427        Some((
428            SegmentInfo {
429                index: new_index,
430                size: accumulated_size,
431            },
432            offsets,
433        ))
434    }
435}
436
437pub(super) mod serde_impl {
438    use crate::stdlib::collections::HashMap;
439    use crate::types::builtin_name::BuiltinName;
440    use num_traits::Num;
441
442    use super::CAIRO_PIE_VERSION;
443    use super::{CairoPieMemory, Pages, PublicMemoryPage, SegmentInfo};
444    #[cfg(any(target_arch = "wasm32", not(feature = "std")))]
445    use crate::alloc::string::ToString;
446    use crate::stdlib::prelude::{String, Vec};
447    use crate::{
448        types::relocatable::{MaybeRelocatable, Relocatable},
449        utils::CAIRO_PRIME,
450        Felt252,
451    };
452    use num_bigint::BigUint;
453    use serde::{
454        de::Error, ser::SerializeMap, ser::SerializeSeq, Deserialize, Deserializer, Serialize,
455        Serializer,
456    };
457    use serde_json::Number;
458
459    pub const ADDR_BYTE_LEN: usize = 8;
460    pub const FIELD_BYTE_LEN: usize = 32;
461    pub const CELL_BYTE_LEN: usize = ADDR_BYTE_LEN + FIELD_BYTE_LEN;
462    pub const ADDR_BASE: u64 = 0x8000000000000000; // 2 ** (8 * ADDR_BYTE_LEN - 1)
463    pub const OFFSET_BASE: u64 = 0x800000000000; // 2 ** OFFSET_BIT_LEN
464    pub const RELOCATE_BASE: &str =
465        "8000000000000000000000000000000000000000000000000000000000000000"; // 2 ** (8 * FIELD_BYTE_LEN - 1)
466
467    pub(crate) struct Felt252Wrapper<'a>(&'a Felt252);
468
469    impl Serialize for Felt252Wrapper<'_> {
470        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
471        where
472            S: Serializer,
473        {
474            // Note: This uses an API intended only for testing.
475            serde_json::Number::from_string_unchecked(self.0.to_string()).serialize(serializer)
476        }
477    }
478
479    pub mod version {
480        use super::*;
481
482        pub fn serialize<S>(_value: &(), serializer: S) -> Result<S::Ok, S::Error>
483        where
484            S: Serializer,
485        {
486            serializer.serialize_str(CAIRO_PIE_VERSION)
487        }
488
489        pub fn deserialize<'de, D>(d: D) -> Result<(), D::Error>
490        where
491            D: Deserializer<'de>,
492        {
493            let version = String::deserialize(d)?;
494
495            if version != CAIRO_PIE_VERSION {
496                Err(D::Error::custom("Invalid cairo_pie version"))
497            } else {
498                Ok(())
499            }
500        }
501    }
502
503    pub mod program_data {
504        use super::*;
505
506        pub fn serialize<S>(values: &[MaybeRelocatable], serializer: S) -> Result<S::Ok, S::Error>
507        where
508            S: Serializer,
509        {
510            use serde::ser::Error;
511            let mut seq_serializer = serializer.serialize_seq(Some(values.len()))?;
512
513            for value in values {
514                match value {
515                    MaybeRelocatable::RelocatableValue(_) => {
516                        return Err(S::Error::custom("Invalid program data"))
517                    }
518                    MaybeRelocatable::Int(x) => {
519                        seq_serializer.serialize_element(&Felt252Wrapper(x))?;
520                    }
521                };
522            }
523
524            seq_serializer.end()
525        }
526
527        pub fn deserialize<'de, D>(d: D) -> Result<Vec<MaybeRelocatable>, D::Error>
528        where
529            D: Deserializer<'de>,
530        {
531            let numbers = Vec::<serde_json::Number>::deserialize(d)?;
532            numbers
533                .into_iter()
534                .map(|n| Felt252::from_dec_str(n.as_str()).map(MaybeRelocatable::from))
535                .collect::<Result<Vec<_>, _>>()
536                .map_err(|_| D::Error::custom("Failed to deserilaize Felt252 value"))
537        }
538    }
539
540    pub mod prime {
541        use super::*;
542
543        use lazy_static::lazy_static;
544        lazy_static! {
545            static ref CAIRO_PRIME_NUMBER: Number =
546                Number::from_string_unchecked(CAIRO_PRIME.to_string());
547        }
548
549        pub fn serialize<S>(_value: &(), serializer: S) -> Result<S::Ok, S::Error>
550        where
551            S: Serializer,
552        {
553            // Note: This uses an API intended only for testing.
554            CAIRO_PRIME_NUMBER.serialize(serializer)
555        }
556
557        pub fn deserialize<'de, D>(d: D) -> Result<(), D::Error>
558        where
559            D: Deserializer<'de>,
560        {
561            let prime = Number::deserialize(d)?;
562
563            if prime != *CAIRO_PRIME_NUMBER {
564                Err(D::Error::custom("Invalid prime"))
565            } else {
566                Ok(())
567            }
568        }
569    }
570
571    pub fn serialize_memory<S>(
572        values: &[((usize, usize), MaybeRelocatable)],
573        serializer: S,
574    ) -> Result<S::Ok, S::Error>
575    where
576        S: Serializer,
577    {
578        // Missing segment and memory holes can be ignored
579        // as they can be inferred by the address on the prover side
580        let mem_cap = values.len() * ADDR_BYTE_LEN + values.len() * FIELD_BYTE_LEN;
581        let mut res = Vec::with_capacity(mem_cap);
582
583        for ((segment, offset), value) in values.iter() {
584            // mem_addr = ADDR_BASE + segment * OFFSET_BASE + offset
585            let mem_addr = (*segment as u64)
586                .checked_mul(OFFSET_BASE)
587                .and_then(|n| n.checked_add(ADDR_BASE))
588                .and_then(|n| n.checked_add(*offset as u64))
589                .ok_or_else(|| {
590                    serde::ser::Error::custom(format!(
591                        "failed to serialize address: {segment}:{offset}"
592                    ))
593                })?;
594
595            res.extend_from_slice(mem_addr.to_le_bytes().as_ref());
596            match value {
597                // Serializes RelocatableValue(little endian):
598                // 1bit |   SEGMENT_BITS |   OFFSET_BITS
599                // 1    |     segment    |   offset
600                MaybeRelocatable::RelocatableValue(rel_val) => {
601                    let reloc_base = BigUint::from_str_radix(RELOCATE_BASE, 16)
602                        .map_err(|_| serde::ser::Error::custom("invalid relocation base str"))?;
603                    let reloc_value = reloc_base
604                        + BigUint::from(rel_val.segment_index as usize)
605                            * BigUint::from(OFFSET_BASE)
606                        + BigUint::from(rel_val.offset);
607                    res.extend_from_slice(reloc_value.to_bytes_le().as_ref());
608                }
609                // Serializes Int(little endian):
610                // 1bit | Num
611                // 0    | num
612                MaybeRelocatable::Int(data_val) => {
613                    res.extend_from_slice(data_val.to_bytes_le().as_ref());
614                }
615            };
616        }
617
618        let string = res
619            .iter()
620            .fold(String::new(), |string, b| string + &format!("{:02x}", b));
621
622        serializer.serialize_str(&string)
623    }
624
625    pub mod pages {
626        use super::*;
627
628        pub fn serialize<S>(pages: &Pages, serializer: S) -> Result<S::Ok, S::Error>
629        where
630            S: Serializer,
631        {
632            let mut map = serializer.serialize_map(Some(pages.len()))?;
633            for (k, v) in pages {
634                map.serialize_entry(&k.to_string(), &vec![v.start, v.size])?;
635            }
636            map.end()
637        }
638
639        pub fn deserialize<'de, D>(deserializer: D) -> Result<Pages, D::Error>
640        where
641            D: Deserializer<'de>,
642        {
643            Ok(HashMap::<String, Vec<usize>>::deserialize(deserializer)?
644                .iter()
645                .map(|(k, v)| {
646                    if v.len() == 2 {
647                        Ok((
648                            k.parse::<usize>().map_err(|_| {
649                                D::Error::custom("Failed to deserialize page index.")
650                            })?,
651                            PublicMemoryPage::from(v),
652                        ))
653                    } else {
654                        Err(D::Error::custom(
655                            "Memory page description must be of length 2.",
656                        ))
657                    }
658                })
659                .collect::<Result<Vec<_>, _>>()
660                .map_err(|_| D::Error::custom("PublicMemoryPage deserialization failed."))?
661                .into_iter()
662                .collect::<Pages>())
663        }
664    }
665
666    impl CairoPieMemory {
667        /// Relocates a `Relocatable` value, which represented by its
668        /// index and offset, according to a given segment offsets
669        fn relocate_value(
670            index: usize,
671            offset: usize,
672            segment_offsets: &Option<HashMap<usize, Relocatable>>,
673        ) -> (usize, usize) {
674            segment_offsets
675                .as_ref()
676                .and_then(|offsets| offsets.get(&index))
677                .map(|relocatable| {
678                    (
679                        relocatable.segment_index as usize,
680                        relocatable.offset + offset,
681                    )
682                })
683                .unwrap_or((index, offset))
684        }
685
686        pub fn to_bytes(&self, seg_offsets: Option<HashMap<usize, Relocatable>>) -> Vec<u8> {
687            // Missing segment and memory holes can be ignored
688            // as they can be inferred by the address on the prover side
689            let values = &self.0;
690            let mem_cap = values.len() * ADDR_BYTE_LEN + values.len() * FIELD_BYTE_LEN;
691            let mut res = Vec::with_capacity(mem_cap);
692
693            for ((segment, offset), value) in values.iter() {
694                let (segment, offset) = Self::relocate_value(*segment, *offset, &seg_offsets);
695                let mem_addr = ADDR_BASE + segment as u64 * OFFSET_BASE + offset as u64;
696                res.extend_from_slice(mem_addr.to_le_bytes().as_ref());
697                match value {
698                    // Serializes RelocatableValue(little endian):
699                    // 1bit |   SEGMENT_BITS |   OFFSET_BITS
700                    // 1    |     segment    |   offset
701                    MaybeRelocatable::RelocatableValue(rel_val) => {
702                        let (segment, offset) = Self::relocate_value(
703                            rel_val.segment_index as usize,
704                            rel_val.offset,
705                            &seg_offsets,
706                        );
707                        let reloc_base = BigUint::from_str_radix(RELOCATE_BASE, 16).unwrap();
708                        let reloc_value = reloc_base
709                            + BigUint::from(segment) * BigUint::from(OFFSET_BASE)
710                            + BigUint::from(offset);
711                        res.extend_from_slice(reloc_value.to_bytes_le().as_ref());
712                    }
713                    // Serializes Int(little endian):
714                    // 1bit | Num
715                    // 0    | num
716                    MaybeRelocatable::Int(data_val) => {
717                        res.extend_from_slice(data_val.to_bytes_le().as_ref());
718                    }
719                };
720            }
721            res
722        }
723
724        pub fn from_bytes(bytes: &[u8]) -> Option<CairoPieMemory> {
725            if !num_integer::Integer::is_multiple_of(&bytes.len(), &CELL_BYTE_LEN) {
726                return None;
727            }
728
729            let relocatable_from_bytes = |bytes: [u8; 8]| -> (usize, usize) {
730                const N_SEGMENT_BITS: usize = 16;
731                const N_OFFSET_BITS: usize = 47;
732                const SEGMENT_MASK: u64 = ((1 << N_SEGMENT_BITS) - 1) << N_OFFSET_BITS;
733                const OFFSET_MASK: u64 = (1 << N_OFFSET_BITS) - 1;
734
735                let addr = u64::from_le_bytes(bytes);
736                let segment = (addr & SEGMENT_MASK) >> N_OFFSET_BITS;
737                let offset = addr & OFFSET_MASK;
738                (segment as usize, offset as usize)
739            };
740
741            let mut res = vec![];
742            for cell_bytes in bytes.chunks(CELL_BYTE_LEN) {
743                let addr = relocatable_from_bytes(cell_bytes[0..ADDR_BYTE_LEN].try_into().ok()?);
744                let field_bytes = &cell_bytes[ADDR_BYTE_LEN..CELL_BYTE_LEN];
745                // Check the last bit to determine if it is a Relocatable or Felt value
746                let value = if (field_bytes[field_bytes.len() - 1] & 0x80) != 0 {
747                    let (segment, offset) =
748                        relocatable_from_bytes(field_bytes[0..ADDR_BYTE_LEN].try_into().ok()?);
749                    MaybeRelocatable::from((segment as isize, offset))
750                } else {
751                    MaybeRelocatable::from(Felt252::from_bytes_le_slice(field_bytes))
752                };
753                res.push((addr, value));
754            }
755
756            Some(CairoPieMemory(res))
757        }
758    }
759
760    pub mod signature_additional_data {
761        use super::*;
762
763        pub fn serialize<S>(
764            values: &HashMap<Relocatable, (Felt252, Felt252)>,
765            serializer: S,
766        ) -> Result<S::Ok, S::Error>
767        where
768            S: Serializer,
769        {
770            let mut seq_serializer = serializer.serialize_seq(Some(values.len()))?;
771
772            for (key, (x, y)) in values {
773                seq_serializer.serialize_element(&[
774                    [
775                        Felt252Wrapper(&Felt252::from(key.segment_index)),
776                        Felt252Wrapper(&Felt252::from(key.offset)),
777                    ],
778                    [Felt252Wrapper(x), Felt252Wrapper(y)],
779                ])?;
780            }
781            seq_serializer.end()
782        }
783
784        pub fn deserialize<'de, D>(
785            d: D,
786        ) -> Result<HashMap<Relocatable, (Felt252, Felt252)>, D::Error>
787        where
788            D: Deserializer<'de>,
789        {
790            let number_map = Vec::<((Number, Number), (Number, Number))>::deserialize(d)?;
791            let mut res = HashMap::with_capacity(number_map.len());
792            for ((index, offset), (r, s)) in number_map.into_iter() {
793                let addr = Relocatable::from((
794                    index
795                        .as_u64()
796                        .ok_or_else(|| D::Error::custom("Invalid address"))?
797                        as isize,
798                    offset
799                        .as_u64()
800                        .ok_or_else(|| D::Error::custom("Invalid address"))?
801                        as usize,
802                ));
803                let r = Felt252::from_dec_str(r.as_str())
804                    .map_err(|_| D::Error::custom("Invalid Felt252 value"))?;
805                let s = Felt252::from_dec_str(s.as_str())
806                    .map_err(|_| D::Error::custom("Invalid Felt252 value"))?;
807                res.insert(addr, (r, s));
808            }
809            Ok(res)
810        }
811    }
812
813    pub mod hash_additional_data {
814        use super::*;
815
816        pub fn serialize<S>(values: &[Relocatable], serializer: S) -> Result<S::Ok, S::Error>
817        where
818            S: Serializer,
819        {
820            let mut seq_serializer: <S as Serializer>::SerializeSeq =
821                serializer.serialize_seq(Some(values.len()))?;
822
823            for value in values {
824                seq_serializer.serialize_element(&[value.segment_index, value.offset as isize])?;
825            }
826
827            seq_serializer.end()
828        }
829
830        pub fn deserialize<'de, D>(d: D) -> Result<Vec<Relocatable>, D::Error>
831        where
832            D: Deserializer<'de>,
833        {
834            let tuples = Vec::<(usize, usize)>::deserialize(d)?;
835            Ok(tuples
836                .into_iter()
837                .map(|(x, y)| Relocatable::from((x as isize, y)))
838                .collect())
839        }
840    }
841
842    pub fn serialize_builtin_segments<S>(
843        values: &HashMap<BuiltinName, SegmentInfo>,
844        serializer: S,
845    ) -> Result<S::Ok, S::Error>
846    where
847        S: Serializer,
848    {
849        let mut map_serializer = serializer.serialize_map(Some(values.len()))?;
850        const BUILTIN_ORDERED_LIST: &[BuiltinName] = &[
851            BuiltinName::output,
852            BuiltinName::pedersen,
853            BuiltinName::range_check,
854            BuiltinName::ecdsa,
855            BuiltinName::bitwise,
856            BuiltinName::ec_op,
857            BuiltinName::keccak,
858            BuiltinName::poseidon,
859            BuiltinName::range_check96,
860            BuiltinName::add_mod,
861            BuiltinName::mul_mod,
862        ];
863
864        for name in BUILTIN_ORDERED_LIST {
865            if let Some(info) = values.get(name) {
866                map_serializer.serialize_entry(name, info)?
867            }
868        }
869        map_serializer.end()
870    }
871}
872
873#[cfg(test)]
874mod test {
875    #[cfg(feature = "std")]
876    use {
877        crate::{
878            cairo_run::CairoRunConfig,
879            hint_processor::builtin_hint_processor::builtin_hint_processor_definition::BuiltinHintProcessor,
880            types::layout_name::LayoutName,
881        },
882        rstest::rstest,
883    };
884
885    use super::*;
886
887    #[test]
888    fn serialize_cairo_pie_memory() {
889        let addrs = [
890            ((1, 0), "0000000000800080"),
891            ((1, 1), "0100000000800080"),
892            ((1, 4), "0400000000800080"),
893            ((1, 8), "0800000000800080"),
894            ((2, 0), "0000000000000180"),
895            ((5, 8), "0800000000800280"),
896        ];
897
898        let memory = CairoPieMemory(vec![
899            (addrs[0].0, MaybeRelocatable::Int(1234.into())),
900            (addrs[1].0, MaybeRelocatable::Int(11.into())),
901            (addrs[2].0, MaybeRelocatable::Int(12.into())),
902            (
903                addrs[3].0,
904                MaybeRelocatable::RelocatableValue((1, 2).into()),
905            ),
906            (
907                addrs[4].0,
908                MaybeRelocatable::RelocatableValue((3, 4).into()),
909            ),
910            (
911                addrs[5].0,
912                MaybeRelocatable::RelocatableValue((5, 6).into()),
913            ),
914        ]);
915
916        let mem = serde_json::to_value(memory).unwrap();
917        let mem_str = mem.as_str().unwrap();
918        let shift_len = (serde_impl::ADDR_BYTE_LEN + serde_impl::FIELD_BYTE_LEN) * 2;
919        let shift_field = serde_impl::FIELD_BYTE_LEN * 2;
920        let shift_addr = serde_impl::ADDR_BYTE_LEN * 2;
921
922        // Serializes Address 8 Byte(little endian):
923        for (i, expected_addr) in addrs.into_iter().enumerate() {
924            let shift = shift_len * i;
925            assert_eq!(
926                &mem_str[shift..shift + shift_addr],
927                expected_addr.1,
928                "addr mismatch({i}): {mem_str:?}",
929            );
930        }
931
932        // Serializes Int(little endian):
933        // 1bit | Num
934        // 0    | num
935        assert_eq!(
936            &mem_str[shift_addr..shift_addr + shift_field],
937            "d204000000000000000000000000000000000000000000000000000000000000",
938            "value mismatch: {mem_str:?}",
939        );
940        // Serializes RelocatableValue(little endian):
941        // 1bit |   SEGMENT_BITS |   OFFSET_BITS
942        // 1    |     segment    |   offset
943        let shift_first_relocatable = shift_len * 3 + shift_addr;
944        assert_eq!(
945            &mem_str[shift_first_relocatable..shift_first_relocatable + shift_field],
946            "0200000000800000000000000000000000000000000000000000000000000080",
947            "value mismatch: {mem_str:?}",
948        );
949    }
950
951    #[test]
952    fn serialize_cairo_pie_memory_with_overflow() {
953        let memory = CairoPieMemory(vec![
954            ((0, 0), MaybeRelocatable::Int(0.into())),
955            ((0, 1), MaybeRelocatable::Int(1.into())),
956            ((usize::MAX, 0), MaybeRelocatable::Int(2.into())),
957        ]);
958
959        serde_json::to_value(memory).unwrap_err();
960    }
961
962    #[rstest]
963    #[cfg(feature = "std")]
964    #[case(include_bytes!("../../../../cairo_programs/fibonacci.json"), "fibonacci")]
965    #[case(include_bytes!("../../../../cairo_programs/integration.json"), "integration")]
966    #[case(include_bytes!("../../../../cairo_programs/common_signature.json"), "signature")]
967    #[case(include_bytes!("../../../../cairo_programs/relocate_segments.json"), "relocate")]
968    #[case(include_bytes!("../../../../cairo_programs/ec_op.json"), "ec_op")]
969    #[case(include_bytes!("../../../../cairo_programs/bitwise_output.json"), "bitwise")]
970    #[case(include_bytes!("../../../../cairo_programs/value_beyond_segment.json"), "relocate_beyond")]
971    fn read_write_pie_zip(#[case] program_content: &[u8], #[case] identifier: &str) {
972        // Run a program to obtain the CairoPie
973        let cairo_pie = {
974            let cairo_run_config = CairoRunConfig {
975                layout: LayoutName::starknet_with_keccak,
976                ..Default::default()
977            };
978            let runner = crate::cairo_run::cairo_run(
979                program_content,
980                &cairo_run_config,
981                &mut BuiltinHintProcessor::new_empty(),
982            )
983            .unwrap();
984            runner.get_cairo_pie().unwrap()
985        };
986        // Serialize the CairoPie into a zip file
987        let filename = format!("temp_file_{}", identifier); // Identifier used to avoid name clashes
988        let file_path = Path::new(&filename);
989        cairo_pie.write_zip_file(file_path, false).unwrap();
990        // Deserialize the zip file
991        let deserialized_pie = CairoPie::read_zip_file(file_path).unwrap();
992        // Check that both pies are equal
993        assert_eq!(cairo_pie, deserialized_pie);
994        // Remove zip file created by the test
995        std::fs::remove_file(file_path).unwrap();
996    }
997
998    #[test]
999    #[cfg(feature = "std")]
1000    fn cairo_pie_with_extra_segments() {
1001        let program_content = include_bytes!("../../../../cairo_programs/fibonacci.json");
1002        let mut cairo_pie = {
1003            let cairo_run_config = CairoRunConfig {
1004                layout: LayoutName::starknet_with_keccak,
1005                ..Default::default()
1006            };
1007            let runner = crate::cairo_run::cairo_run(
1008                program_content,
1009                &cairo_run_config,
1010                &mut BuiltinHintProcessor::new_empty(),
1011            )
1012            .unwrap();
1013            runner.get_cairo_pie().unwrap()
1014        };
1015
1016        cairo_pie.metadata.extra_segments = vec![
1017            SegmentInfo { index: 8, size: 10 },
1018            SegmentInfo { index: 9, size: 20 },
1019        ];
1020        let memory = CairoPieMemory(vec![
1021            (
1022                (3, 4),
1023                MaybeRelocatable::RelocatableValue(Relocatable {
1024                    segment_index: 6,
1025                    offset: 7,
1026                }),
1027            ),
1028            (
1029                (8, 0),
1030                MaybeRelocatable::RelocatableValue(Relocatable {
1031                    segment_index: 8,
1032                    offset: 4,
1033                }),
1034            ),
1035            (
1036                (9, 3),
1037                MaybeRelocatable::RelocatableValue(Relocatable {
1038                    segment_index: 9,
1039                    offset: 7,
1040                }),
1041            ),
1042        ]);
1043
1044        cairo_pie.memory = memory;
1045
1046        let file_path = Path::new("merge_extra_segments_test");
1047
1048        cairo_pie.write_zip_file(file_path, true).unwrap();
1049
1050        let result_cairo_pie = CairoPie::read_zip_file(file_path).unwrap();
1051
1052        std::fs::remove_file(file_path).unwrap();
1053
1054        assert_eq!(
1055            result_cairo_pie.metadata.extra_segments,
1056            vec![SegmentInfo { index: 8, size: 30 }]
1057        );
1058        assert_eq!(
1059            result_cairo_pie.memory,
1060            CairoPieMemory(vec![
1061                (
1062                    (3, 4),
1063                    MaybeRelocatable::RelocatableValue(Relocatable {
1064                        segment_index: 6,
1065                        offset: 7
1066                    })
1067                ),
1068                (
1069                    (8, 0),
1070                    MaybeRelocatable::RelocatableValue(Relocatable {
1071                        segment_index: 8,
1072                        offset: 4
1073                    })
1074                ),
1075                (
1076                    (8, 13),
1077                    MaybeRelocatable::RelocatableValue(Relocatable {
1078                        segment_index: 8,
1079                        offset: 17
1080                    })
1081                ),
1082            ])
1083        )
1084    }
1085
1086    #[test]
1087    #[cfg(feature = "std")]
1088    fn cairo_pie_without_extra_segments() {
1089        let program_content = include_bytes!("../../../../cairo_programs/fibonacci.json");
1090        let mut cairo_pie = {
1091            let cairo_run_config = CairoRunConfig {
1092                layout: LayoutName::starknet_with_keccak,
1093                ..Default::default()
1094            };
1095            let runner = crate::cairo_run::cairo_run(
1096                program_content,
1097                &cairo_run_config,
1098                &mut BuiltinHintProcessor::new_empty(),
1099            )
1100            .unwrap();
1101            runner.get_cairo_pie().unwrap()
1102        };
1103
1104        cairo_pie.metadata.extra_segments = vec![];
1105        let memory = CairoPieMemory(vec![
1106            (
1107                (3, 4),
1108                MaybeRelocatable::RelocatableValue(Relocatable {
1109                    segment_index: 6,
1110                    offset: 7,
1111                }),
1112            ),
1113            (
1114                (8, 0),
1115                MaybeRelocatable::RelocatableValue(Relocatable {
1116                    segment_index: 8,
1117                    offset: 4,
1118                }),
1119            ),
1120            (
1121                (9, 3),
1122                MaybeRelocatable::RelocatableValue(Relocatable {
1123                    segment_index: 9,
1124                    offset: 7,
1125                }),
1126            ),
1127        ]);
1128
1129        cairo_pie.memory = memory.clone();
1130
1131        let file_path = Path::new("merge_without_extra_segments_test");
1132
1133        cairo_pie.write_zip_file(file_path, true).unwrap();
1134
1135        let result_cairo_pie = CairoPie::read_zip_file(file_path).unwrap();
1136
1137        std::fs::remove_file(file_path).unwrap();
1138
1139        assert_eq!(result_cairo_pie.metadata.extra_segments, vec![]);
1140        assert_eq!(result_cairo_pie.memory, memory)
1141    }
1142}
cairo_vm/vm/runners/cairo_pie.rs

cairo_vm/vm/runners/
cairo_pie.rs
