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_some_and(|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_integer::Integer;
441    use num_traits::Num;
442
443    use super::CAIRO_PIE_VERSION;
444    use super::{CairoPieMemory, Pages, PublicMemoryPage, SegmentInfo};
445    #[cfg(any(target_arch = "wasm32", not(feature = "std")))]
446    use crate::alloc::string::ToString;
447    use crate::stdlib::prelude::{String, Vec};
448    use crate::{
449        types::relocatable::{MaybeRelocatable, Relocatable},
450        utils::CAIRO_PRIME,
451        Felt252,
452    };
453    use num_bigint::BigUint;
454    use serde::{
455        de::Error, ser::SerializeMap, ser::SerializeSeq, Deserialize, Deserializer, Serialize,
456        Serializer,
457    };
458    use serde_json::Number;
459
460    pub const ADDR_BYTE_LEN: usize = 8;
461    pub const FIELD_BYTE_LEN: usize = 32;
462    pub const CELL_BYTE_LEN: usize = ADDR_BYTE_LEN + FIELD_BYTE_LEN;
463    pub const ADDR_BASE: u64 = 0x8000000000000000; // 2 ** (8 * ADDR_BYTE_LEN - 1)
464    pub const OFFSET_BASE: u64 = 0x800000000000; // 2 ** OFFSET_BIT_LEN
465    pub const RELOCATE_BASE: &str =
466        "8000000000000000000000000000000000000000000000000000000000000000"; // 2 ** (8 * FIELD_BYTE_LEN - 1)
467
468    pub(crate) struct Felt252Wrapper<'a>(&'a Felt252);
469
470    impl<'a> Serialize for Felt252Wrapper<'a> {
471        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
472        where
473            S: Serializer,
474        {
475            // Note: This uses an API intended only for testing.
476            serde_json::Number::from_string_unchecked(self.0.to_string()).serialize(serializer)
477        }
478    }
479
480    pub mod version {
481        use super::*;
482
483        pub fn serialize<S>(_value: &(), serializer: S) -> Result<S::Ok, S::Error>
484        where
485            S: Serializer,
486        {
487            serializer.serialize_str(CAIRO_PIE_VERSION)
488        }
489
490        pub fn deserialize<'de, D>(d: D) -> Result<(), D::Error>
491        where
492            D: Deserializer<'de>,
493        {
494            let version = String::deserialize(d)?;
495
496            if version != CAIRO_PIE_VERSION {
497                Err(D::Error::custom("Invalid cairo_pie version"))
498            } else {
499                Ok(())
500            }
501        }
502    }
503
504    pub mod program_data {
505        use super::*;
506
507        pub fn serialize<S>(values: &[MaybeRelocatable], serializer: S) -> Result<S::Ok, S::Error>
508        where
509            S: Serializer,
510        {
511            use serde::ser::Error;
512            let mut seq_serializer = serializer.serialize_seq(Some(values.len()))?;
513
514            for value in values {
515                match value {
516                    MaybeRelocatable::RelocatableValue(_) => {
517                        return Err(S::Error::custom("Invalid program data"))
518                    }
519                    MaybeRelocatable::Int(x) => {
520                        seq_serializer.serialize_element(&Felt252Wrapper(x))?;
521                    }
522                };
523            }
524
525            seq_serializer.end()
526        }
527
528        pub fn deserialize<'de, D>(d: D) -> Result<Vec<MaybeRelocatable>, D::Error>
529        where
530            D: Deserializer<'de>,
531        {
532            let numbers = Vec::<serde_json::Number>::deserialize(d)?;
533            numbers
534                .into_iter()
535                .map(|n| Felt252::from_dec_str(n.as_str()).map(MaybeRelocatable::from))
536                .collect::<Result<Vec<_>, _>>()
537                .map_err(|_| D::Error::custom("Failed to deserilaize Felt252 value"))
538        }
539    }
540
541    pub mod prime {
542        use super::*;
543
544        use lazy_static::lazy_static;
545        lazy_static! {
546            static ref CAIRO_PRIME_NUMBER: Number =
547                Number::from_string_unchecked(CAIRO_PRIME.to_string());
548        }
549
550        pub fn serialize<S>(_value: &(), serializer: S) -> Result<S::Ok, S::Error>
551        where
552            S: Serializer,
553        {
554            // Note: This uses an API intended only for testing.
555            CAIRO_PRIME_NUMBER.serialize(serializer)
556        }
557
558        pub fn deserialize<'de, D>(d: D) -> Result<(), D::Error>
559        where
560            D: Deserializer<'de>,
561        {
562            let prime = Number::deserialize(d)?;
563
564            if prime != *CAIRO_PRIME_NUMBER {
565                Err(D::Error::custom("Invalid prime"))
566            } else {
567                Ok(())
568            }
569        }
570    }
571
572    pub fn serialize_memory<S>(
573        values: &[((usize, usize), MaybeRelocatable)],
574        serializer: S,
575    ) -> Result<S::Ok, S::Error>
576    where
577        S: Serializer,
578    {
579        // Missing segment and memory holes can be ignored
580        // as they can be inferred by the address on the prover side
581        let mem_cap = values.len() * ADDR_BYTE_LEN + values.len() * FIELD_BYTE_LEN;
582        let mut res = Vec::with_capacity(mem_cap);
583
584        for ((segment, offset), value) in values.iter() {
585            // mem_addr = ADDR_BASE + segment * OFFSET_BASE + offset
586            let mem_addr = (*segment as u64)
587                .checked_mul(OFFSET_BASE)
588                .and_then(|n| n.checked_add(ADDR_BASE))
589                .and_then(|n| n.checked_add(*offset as u64))
590                .ok_or_else(|| {
591                    serde::ser::Error::custom(format!(
592                        "failed to serialize address: {segment}:{offset}"
593                    ))
594                })?;
595
596            res.extend_from_slice(mem_addr.to_le_bytes().as_ref());
597            match value {
598                // Serializes RelocatableValue(little endian):
599                // 1bit |   SEGMENT_BITS |   OFFSET_BITS
600                // 1    |     segment    |   offset
601                MaybeRelocatable::RelocatableValue(rel_val) => {
602                    let reloc_base = BigUint::from_str_radix(RELOCATE_BASE, 16)
603                        .map_err(|_| serde::ser::Error::custom("invalid relocation base str"))?;
604                    let reloc_value = reloc_base
605                        + BigUint::from(rel_val.segment_index as usize)
606                            * BigUint::from(OFFSET_BASE)
607                        + BigUint::from(rel_val.offset);
608                    res.extend_from_slice(reloc_value.to_bytes_le().as_ref());
609                }
610                // Serializes Int(little endian):
611                // 1bit | Num
612                // 0    | num
613                MaybeRelocatable::Int(data_val) => {
614                    res.extend_from_slice(data_val.to_bytes_le().as_ref());
615                }
616            };
617        }
618
619        let string = res
620            .iter()
621            .fold(String::new(), |string, b| string + &format!("{:02x}", b));
622
623        serializer.serialize_str(&string)
624    }
625
626    pub mod pages {
627        use super::*;
628
629        pub fn serialize<S>(pages: &Pages, serializer: S) -> Result<S::Ok, S::Error>
630        where
631            S: Serializer,
632        {
633            let mut map = serializer.serialize_map(Some(pages.len()))?;
634            for (k, v) in pages {
635                map.serialize_entry(&k.to_string(), &vec![v.start, v.size])?;
636            }
637            map.end()
638        }
639
640        pub fn deserialize<'de, D>(deserializer: D) -> Result<Pages, D::Error>
641        where
642            D: Deserializer<'de>,
643        {
644            Ok(HashMap::<String, Vec<usize>>::deserialize(deserializer)?
645                .iter()
646                .map(|(k, v)| {
647                    if v.len() == 2 {
648                        Ok((
649                            k.parse::<usize>().map_err(|_| {
650                                D::Error::custom("Failed to deserialize page index.")
651                            })?,
652                            PublicMemoryPage::from(v),
653                        ))
654                    } else {
655                        Err(D::Error::custom(
656                            "Memory page description must be of length 2.",
657                        ))
658                    }
659                })
660                .collect::<Result<Vec<_>, _>>()
661                .map_err(|_| D::Error::custom("PublicMemoryPage deserialization failed."))?
662                .into_iter()
663                .collect::<Pages>())
664        }
665    }
666
667    impl CairoPieMemory {
668        /// Relocates a `Relocatable` value, which represented by its
669        /// index and offset, according to a given segment offsets
670        fn relocate_value(
671            index: usize,
672            offset: usize,
673            segment_offsets: &Option<HashMap<usize, Relocatable>>,
674        ) -> (usize, usize) {
675            segment_offsets
676                .as_ref()
677                .and_then(|offsets| offsets.get(&index))
678                .map(|relocatable| {
679                    (
680                        relocatable.segment_index as usize,
681                        relocatable.offset + offset,
682                    )
683                })
684                .unwrap_or((index, offset))
685        }
686
687        pub fn to_bytes(&self, seg_offsets: Option<HashMap<usize, Relocatable>>) -> Vec<u8> {
688            // Missing segment and memory holes can be ignored
689            // as they can be inferred by the address on the prover side
690            let values = &self.0;
691            let mem_cap = values.len() * ADDR_BYTE_LEN + values.len() * FIELD_BYTE_LEN;
692            let mut res = Vec::with_capacity(mem_cap);
693
694            for ((segment, offset), value) in values.iter() {
695                let (segment, offset) = Self::relocate_value(*segment, *offset, &seg_offsets);
696                let mem_addr = ADDR_BASE + segment as u64 * OFFSET_BASE + offset as u64;
697                res.extend_from_slice(mem_addr.to_le_bytes().as_ref());
698                match value {
699                    // Serializes RelocatableValue(little endian):
700                    // 1bit |   SEGMENT_BITS |   OFFSET_BITS
701                    // 1    |     segment    |   offset
702                    MaybeRelocatable::RelocatableValue(rel_val) => {
703                        let (segment, offset) = Self::relocate_value(
704                            rel_val.segment_index as usize,
705                            rel_val.offset,
706                            &seg_offsets,
707                        );
708                        let reloc_base = BigUint::from_str_radix(RELOCATE_BASE, 16).unwrap();
709                        let reloc_value = reloc_base
710                            + BigUint::from(segment) * BigUint::from(OFFSET_BASE)
711                            + BigUint::from(offset);
712                        res.extend_from_slice(reloc_value.to_bytes_le().as_ref());
713                    }
714                    // Serializes Int(little endian):
715                    // 1bit | Num
716                    // 0    | num
717                    MaybeRelocatable::Int(data_val) => {
718                        res.extend_from_slice(data_val.to_bytes_le().as_ref());
719                    }
720                };
721            }
722            res
723        }
724
725        pub fn from_bytes(bytes: &[u8]) -> Option<CairoPieMemory> {
726            if !bytes.len().is_multiple_of(&CELL_BYTE_LEN) {
727                return None;
728            }
729
730            let relocatable_from_bytes = |bytes: [u8; 8]| -> (usize, usize) {
731                const N_SEGMENT_BITS: usize = 16;
732                const N_OFFSET_BITS: usize = 47;
733                const SEGMENT_MASK: u64 = ((1 << N_SEGMENT_BITS) - 1) << N_OFFSET_BITS;
734                const OFFSET_MASK: u64 = (1 << N_OFFSET_BITS) - 1;
735
736                let addr = u64::from_le_bytes(bytes);
737                let segment = (addr & SEGMENT_MASK) >> N_OFFSET_BITS;
738                let offset = addr & OFFSET_MASK;
739                (segment as usize, offset as usize)
740            };
741
742            let mut res = vec![];
743            for cell_bytes in bytes.chunks(CELL_BYTE_LEN) {
744                let addr = relocatable_from_bytes(cell_bytes[0..ADDR_BYTE_LEN].try_into().ok()?);
745                let field_bytes = &cell_bytes[ADDR_BYTE_LEN..CELL_BYTE_LEN];
746                // Check the last bit to determine if it is a Relocatable or Felt value
747                let value = if (field_bytes[field_bytes.len() - 1] & 0x80) != 0 {
748                    let (segment, offset) =
749                        relocatable_from_bytes(field_bytes[0..ADDR_BYTE_LEN].try_into().ok()?);
750                    MaybeRelocatable::from((segment as isize, offset))
751                } else {
752                    MaybeRelocatable::from(Felt252::from_bytes_le_slice(field_bytes))
753                };
754                res.push((addr, value));
755            }
756
757            Some(CairoPieMemory(res))
758        }
759    }
760
761    pub mod signature_additional_data {
762        use super::*;
763
764        pub fn serialize<S>(
765            values: &HashMap<Relocatable, (Felt252, Felt252)>,
766            serializer: S,
767        ) -> Result<S::Ok, S::Error>
768        where
769            S: Serializer,
770        {
771            let mut seq_serializer = serializer.serialize_seq(Some(values.len()))?;
772
773            for (key, (x, y)) in values {
774                seq_serializer.serialize_element(&[
775                    [
776                        Felt252Wrapper(&Felt252::from(key.segment_index)),
777                        Felt252Wrapper(&Felt252::from(key.offset)),
778                    ],
779                    [Felt252Wrapper(x), Felt252Wrapper(y)],
780                ])?;
781            }
782            seq_serializer.end()
783        }
784
785        pub fn deserialize<'de, D>(
786            d: D,
787        ) -> Result<HashMap<Relocatable, (Felt252, Felt252)>, D::Error>
788        where
789            D: Deserializer<'de>,
790        {
791            let number_map = Vec::<((Number, Number), (Number, Number))>::deserialize(d)?;
792            let mut res = HashMap::with_capacity(number_map.len());
793            for ((index, offset), (r, s)) in number_map.into_iter() {
794                let addr = Relocatable::from((
795                    index
796                        .as_u64()
797                        .ok_or_else(|| D::Error::custom("Invalid address"))?
798                        as isize,
799                    offset
800                        .as_u64()
801                        .ok_or_else(|| D::Error::custom("Invalid address"))?
802                        as usize,
803                ));
804                let r = Felt252::from_dec_str(r.as_str())
805                    .map_err(|_| D::Error::custom("Invalid Felt252 value"))?;
806                let s = Felt252::from_dec_str(s.as_str())
807                    .map_err(|_| D::Error::custom("Invalid Felt252 value"))?;
808                res.insert(addr, (r, s));
809            }
810            Ok(res)
811        }
812    }
813
814    pub mod hash_additional_data {
815        use super::*;
816
817        pub fn serialize<S>(values: &[Relocatable], serializer: S) -> Result<S::Ok, S::Error>
818        where
819            S: Serializer,
820        {
821            let mut seq_serializer: <S as Serializer>::SerializeSeq =
822                serializer.serialize_seq(Some(values.len()))?;
823
824            for value in values {
825                seq_serializer.serialize_element(&[value.segment_index, value.offset as isize])?;
826            }
827
828            seq_serializer.end()
829        }
830
831        pub fn deserialize<'de, D>(d: D) -> Result<Vec<Relocatable>, D::Error>
832        where
833            D: Deserializer<'de>,
834        {
835            let tuples = Vec::<(usize, usize)>::deserialize(d)?;
836            Ok(tuples
837                .into_iter()
838                .map(|(x, y)| Relocatable::from((x as isize, y)))
839                .collect())
840        }
841    }
842
843    pub fn serialize_builtin_segments<S>(
844        values: &HashMap<BuiltinName, SegmentInfo>,
845        serializer: S,
846    ) -> Result<S::Ok, S::Error>
847    where
848        S: Serializer,
849    {
850        let mut map_serializer = serializer.serialize_map(Some(values.len()))?;
851        const BUILTIN_ORDERED_LIST: &[BuiltinName] = &[
852            BuiltinName::output,
853            BuiltinName::pedersen,
854            BuiltinName::range_check,
855            BuiltinName::ecdsa,
856            BuiltinName::bitwise,
857            BuiltinName::ec_op,
858            BuiltinName::keccak,
859            BuiltinName::poseidon,
860            BuiltinName::range_check96,
861            BuiltinName::add_mod,
862            BuiltinName::mul_mod,
863        ];
864
865        for name in BUILTIN_ORDERED_LIST {
866            if let Some(info) = values.get(name) {
867                map_serializer.serialize_entry(name, info)?
868            }
869        }
870        map_serializer.end()
871    }
872}
873
874#[cfg(test)]
875mod test {
876    #[cfg(feature = "std")]
877    use {
878        crate::{
879            cairo_run::CairoRunConfig,
880            hint_processor::builtin_hint_processor::builtin_hint_processor_definition::BuiltinHintProcessor,
881            types::layout_name::LayoutName,
882        },
883        rstest::rstest,
884    };
885
886    use super::*;
887
888    #[test]
889    fn serialize_cairo_pie_memory() {
890        let addrs = [
891            ((1, 0), "0000000000800080"),
892            ((1, 1), "0100000000800080"),
893            ((1, 4), "0400000000800080"),
894            ((1, 8), "0800000000800080"),
895            ((2, 0), "0000000000000180"),
896            ((5, 8), "0800000000800280"),
897        ];
898
899        let memory = CairoPieMemory(vec![
900            (addrs[0].0, MaybeRelocatable::Int(1234.into())),
901            (addrs[1].0, MaybeRelocatable::Int(11.into())),
902            (addrs[2].0, MaybeRelocatable::Int(12.into())),
903            (
904                addrs[3].0,
905                MaybeRelocatable::RelocatableValue((1, 2).into()),
906            ),
907            (
908                addrs[4].0,
909                MaybeRelocatable::RelocatableValue((3, 4).into()),
910            ),
911            (
912                addrs[5].0,
913                MaybeRelocatable::RelocatableValue((5, 6).into()),
914            ),
915        ]);
916
917        let mem = serde_json::to_value(memory).unwrap();
918        let mem_str = mem.as_str().unwrap();
919        let shift_len = (serde_impl::ADDR_BYTE_LEN + serde_impl::FIELD_BYTE_LEN) * 2;
920        let shift_field = serde_impl::FIELD_BYTE_LEN * 2;
921        let shift_addr = serde_impl::ADDR_BYTE_LEN * 2;
922
923        // Serializes Address 8 Byte(little endian):
924        for (i, expected_addr) in addrs.into_iter().enumerate() {
925            let shift = shift_len * i;
926            assert_eq!(
927                &mem_str[shift..shift + shift_addr],
928                expected_addr.1,
929                "addr mismatch({i}): {mem_str:?}",
930            );
931        }
932
933        // Serializes Int(little endian):
934        // 1bit | Num
935        // 0    | num
936        assert_eq!(
937            &mem_str[shift_addr..shift_addr + shift_field],
938            "d204000000000000000000000000000000000000000000000000000000000000",
939            "value mismatch: {mem_str:?}",
940        );
941        // Serializes RelocatableValue(little endian):
942        // 1bit |   SEGMENT_BITS |   OFFSET_BITS
943        // 1    |     segment    |   offset
944        let shift_first_relocatable = shift_len * 3 + shift_addr;
945        assert_eq!(
946            &mem_str[shift_first_relocatable..shift_first_relocatable + shift_field],
947            "0200000000800000000000000000000000000000000000000000000000000080",
948            "value mismatch: {mem_str:?}",
949        );
950    }
951
952    #[test]
953    fn serialize_cairo_pie_memory_with_overflow() {
954        let memory = CairoPieMemory(vec![
955            ((0, 0), MaybeRelocatable::Int(0.into())),
956            ((0, 1), MaybeRelocatable::Int(1.into())),
957            ((usize::MAX, 0), MaybeRelocatable::Int(2.into())),
958        ]);
959
960        serde_json::to_value(memory).unwrap_err();
961    }
962
963    #[rstest]
964    #[cfg(feature = "std")]
965    #[case(include_bytes!("../../../../cairo_programs/fibonacci.json"), "fibonacci")]
966    #[case(include_bytes!("../../../../cairo_programs/integration.json"), "integration")]
967    #[case(include_bytes!("../../../../cairo_programs/common_signature.json"), "signature")]
968    #[case(include_bytes!("../../../../cairo_programs/relocate_segments.json"), "relocate")]
969    #[case(include_bytes!("../../../../cairo_programs/ec_op.json"), "ec_op")]
970    #[case(include_bytes!("../../../../cairo_programs/bitwise_output.json"), "bitwise")]
971    #[case(include_bytes!("../../../../cairo_programs/value_beyond_segment.json"), "relocate_beyond")]
972    fn read_write_pie_zip(#[case] program_content: &[u8], #[case] identifier: &str) {
973        // Run a program to obtain the CairoPie
974        let cairo_pie = {
975            let cairo_run_config = CairoRunConfig {
976                layout: LayoutName::starknet_with_keccak,
977                ..Default::default()
978            };
979            let runner = crate::cairo_run::cairo_run(
980                program_content,
981                &cairo_run_config,
982                &mut BuiltinHintProcessor::new_empty(),
983            )
984            .unwrap();
985            runner.get_cairo_pie().unwrap()
986        };
987        // Serialize the CairoPie into a zip file
988        let filename = format!("temp_file_{}", identifier); // Identifier used to avoid name clashes
989        let file_path = Path::new(&filename);
990        cairo_pie.write_zip_file(file_path, false).unwrap();
991        // Deserialize the zip file
992        let deserialized_pie = CairoPie::read_zip_file(file_path).unwrap();
993        // Check that both pies are equal
994        assert_eq!(cairo_pie, deserialized_pie);
995        // Remove zip file created by the test
996        std::fs::remove_file(file_path).unwrap();
997    }
998
999    #[test]
1000    #[cfg(feature = "std")]
1001    fn cairo_pie_with_extra_segments() {
1002        let program_content = include_bytes!("../../../../cairo_programs/fibonacci.json");
1003        let mut cairo_pie = {
1004            let cairo_run_config = CairoRunConfig {
1005                layout: LayoutName::starknet_with_keccak,
1006                ..Default::default()
1007            };
1008            let runner = crate::cairo_run::cairo_run(
1009                program_content,
1010                &cairo_run_config,
1011                &mut BuiltinHintProcessor::new_empty(),
1012            )
1013            .unwrap();
1014            runner.get_cairo_pie().unwrap()
1015        };
1016
1017        cairo_pie.metadata.extra_segments = vec![
1018            SegmentInfo { index: 8, size: 10 },
1019            SegmentInfo { index: 9, size: 20 },
1020        ];
1021        let memory = CairoPieMemory(vec![
1022            (
1023                (3, 4),
1024                MaybeRelocatable::RelocatableValue(Relocatable {
1025                    segment_index: 6,
1026                    offset: 7,
1027                }),
1028            ),
1029            (
1030                (8, 0),
1031                MaybeRelocatable::RelocatableValue(Relocatable {
1032                    segment_index: 8,
1033                    offset: 4,
1034                }),
1035            ),
1036            (
1037                (9, 3),
1038                MaybeRelocatable::RelocatableValue(Relocatable {
1039                    segment_index: 9,
1040                    offset: 7,
1041                }),
1042            ),
1043        ]);
1044
1045        cairo_pie.memory = memory;
1046
1047        let file_path = Path::new("merge_extra_segments_test");
1048
1049        cairo_pie.write_zip_file(file_path, true).unwrap();
1050
1051        let result_cairo_pie = CairoPie::read_zip_file(file_path).unwrap();
1052
1053        std::fs::remove_file(file_path).unwrap();
1054
1055        assert_eq!(
1056            result_cairo_pie.metadata.extra_segments,
1057            vec![SegmentInfo { index: 8, size: 30 }]
1058        );
1059        assert_eq!(
1060            result_cairo_pie.memory,
1061            CairoPieMemory(vec![
1062                (
1063                    (3, 4),
1064                    MaybeRelocatable::RelocatableValue(Relocatable {
1065                        segment_index: 6,
1066                        offset: 7
1067                    })
1068                ),
1069                (
1070                    (8, 0),
1071                    MaybeRelocatable::RelocatableValue(Relocatable {
1072                        segment_index: 8,
1073                        offset: 4
1074                    })
1075                ),
1076                (
1077                    (8, 13),
1078                    MaybeRelocatable::RelocatableValue(Relocatable {
1079                        segment_index: 8,
1080                        offset: 17
1081                    })
1082                ),
1083            ])
1084        )
1085    }
1086
1087    #[test]
1088    #[cfg(feature = "std")]
1089    fn cairo_pie_without_extra_segments() {
1090        let program_content = include_bytes!("../../../../cairo_programs/fibonacci.json");
1091        let mut cairo_pie = {
1092            let cairo_run_config = CairoRunConfig {
1093                layout: LayoutName::starknet_with_keccak,
1094                ..Default::default()
1095            };
1096            let runner = crate::cairo_run::cairo_run(
1097                program_content,
1098                &cairo_run_config,
1099                &mut BuiltinHintProcessor::new_empty(),
1100            )
1101            .unwrap();
1102            runner.get_cairo_pie().unwrap()
1103        };
1104
1105        cairo_pie.metadata.extra_segments = vec![];
1106        let memory = CairoPieMemory(vec![
1107            (
1108                (3, 4),
1109                MaybeRelocatable::RelocatableValue(Relocatable {
1110                    segment_index: 6,
1111                    offset: 7,
1112                }),
1113            ),
1114            (
1115                (8, 0),
1116                MaybeRelocatable::RelocatableValue(Relocatable {
1117                    segment_index: 8,
1118                    offset: 4,
1119                }),
1120            ),
1121            (
1122                (9, 3),
1123                MaybeRelocatable::RelocatableValue(Relocatable {
1124                    segment_index: 9,
1125                    offset: 7,
1126                }),
1127            ),
1128        ]);
1129
1130        cairo_pie.memory = memory.clone();
1131
1132        let file_path = Path::new("merge_without_extra_segments_test");
1133
1134        cairo_pie.write_zip_file(file_path, true).unwrap();
1135
1136        let result_cairo_pie = CairoPie::read_zip_file(file_path).unwrap();
1137
1138        std::fs::remove_file(file_path).unwrap();
1139
1140        assert_eq!(result_cairo_pie.metadata.extra_segments, vec![]);
1141        assert_eq!(result_cairo_pie.memory, memory)
1142    }
1143}
cairo_vm/vm/runners/cairo_pie.rs

cairo_vm/vm/runners/
cairo_pie.rs
