openvm_sdk/
codec.rs

1use std::io::{self, Cursor, Read, Result, Write};
2
3use openvm_circuit::{
4    arch::ContinuationVmProof, system::memory::merkle::public_values::UserPublicValuesProof,
5};
6use openvm_continuations::verifier::{
7    internal::types::VmStarkProof, root::types::RootVmVerifierInput,
8};
9use openvm_native_compiler::ir::DIGEST_SIZE;
10use openvm_native_recursion::hints::{InnerBatchOpening, InnerFriProof, InnerQueryProof};
11use openvm_stark_backend::{
12    config::{Com, PcsProof},
13    interaction::{fri_log_up::FriLogUpPartialProof, RapPhaseSeqKind},
14    p3_field::{
15        extension::BinomialExtensionField, FieldAlgebra, FieldExtensionAlgebra, PrimeField32,
16    },
17    proof::{AdjacentOpenedValues, AirProofData, Commitments, OpenedValues, OpeningProof, Proof},
18};
19use p3_fri::CommitPhaseProofStep;
20
21use super::{F, SC};
22
23type Challenge = BinomialExtensionField<F, 4>;
24
25/// Codec version should change only when proof system or proof format changes.
26/// It does correspond to the main openvm version (which may change more frequently).
27const CODEC_VERSION: u32 = 1;
28
29/// Hardware and language independent encoding.
30/// Uses the Writer pattern for more efficient encoding without intermediate buffers.
31// @dev Trait just for implementation sanity
32pub trait Encode {
33    /// Writes the encoded representation of `self` to the given writer.
34    fn encode<W: Write>(&self, writer: &mut W) -> Result<()>;
35
36    /// Convenience method to encode into a `Vec<u8>`
37    fn encode_to_vec(&self) -> Result<Vec<u8>> {
38        let mut buffer = Vec::new();
39        self.encode(&mut buffer)?;
40        Ok(buffer)
41    }
42}
43
44/// Hardware and language independent decoding.
45/// Uses the Reader pattern for efficient decoding.
46pub trait Decode: Sized {
47    /// Reads and decodes a value from the given reader.
48    fn decode<R: Read>(reader: &mut R) -> Result<Self>;
49    fn decode_from_bytes(bytes: &[u8]) -> Result<Self> {
50        let mut reader = Cursor::new(bytes);
51        Self::decode(&mut reader)
52    }
53}
54
55// ==================== Encode implementation ====================
56
57impl Encode for ContinuationVmProof<SC> {
58    fn encode<W: Write>(&self, writer: &mut W) -> Result<()> {
59        encode_slice(&self.per_segment, writer)?;
60        self.user_public_values.encode(writer)
61    }
62}
63
64impl Encode for VmStarkProof<SC> {
65    fn encode<W: Write>(&self, writer: &mut W) -> Result<()> {
66        self.inner.encode(writer)?;
67        encode_slice(&self.user_public_values, writer)
68    }
69}
70
71impl Encode for UserPublicValuesProof<DIGEST_SIZE, F> {
72    fn encode<W: Write>(&self, writer: &mut W) -> Result<()> {
73        encode_slice(&self.proof, writer)?;
74        encode_slice(&self.public_values, writer)?;
75        self.public_values_commit.encode(writer)
76    }
77}
78
79impl Encode for RootVmVerifierInput<SC> {
80    fn encode<W: Write>(&self, writer: &mut W) -> Result<()> {
81        encode_slice(&self.proofs, writer)?;
82        encode_slice(&self.public_values, writer)
83    }
84}
85
86impl Encode for Proof<SC> {
87    // We need to know:
88    // - Pcs is TwoAdicFriPcs
89    // - Com<SC>: Into<[F; 8]>
90    // For simplicity, we only implement for fixed `BabyBearPoseidon2Config`
91    //
92    /// Encode a proof using FRI as the PCS with `BabyBearPoseidon2Config`.
93    /// The Merkle tree hashes have digest `[F; 8]`.
94    /// ```
95    /// pub struct Proof<SC: StarkGenericConfig> {
96    ///     pub commitments: Commitments<Com<SC>>,
97    ///     pub opening: OpeningProof<PcsProof<SC>, SC::Challenge>,
98    ///     pub per_air: Vec<AirProofData<Val<SC>, SC::Challenge>>,
99    ///     pub rap_phase_seq_proof: Option<RapPhaseSeqPartialProof<SC>>,
100    /// }
101    /// ```
102    fn encode<W: Write>(&self, writer: &mut W) -> Result<()> {
103        writer.write_all(&CODEC_VERSION.to_le_bytes())?;
104        // Encode commitments
105        encode_commitments(&self.commitments.main_trace, writer)?;
106        encode_commitments(&self.commitments.after_challenge, writer)?;
107        let quotient_commit: [F; DIGEST_SIZE] = self.commitments.quotient.into();
108        quotient_commit.encode(writer)?;
109
110        // Encode OpeningProof
111        encode_opening_proof(&self.opening, writer)?;
112
113        // Encode per_air data
114        encode_slice(&self.per_air, writer)?;
115
116        writer.write_all(&[RapPhaseSeqKind::FriLogUp as u8])?;
117        // Encode logup witness
118        self.rap_phase_seq_proof.encode(writer)?;
119
120        Ok(())
121    }
122}
123
124// Helper function to encode OpeningProof
125// ```
126// pub struct OpeningProof<PcsProof, Challenge> {
127//     pub proof: PcsProof,
128//     pub values: OpenedValues<Challenge>,
129// }
130// ```
131fn encode_opening_proof<W: Write>(
132    opening: &OpeningProof<PcsProof<SC>, Challenge>,
133    writer: &mut W,
134) -> Result<()> {
135    // Encode FRI proof
136    opening.proof.encode(writer)?;
137    encode_opened_values(&opening.values, writer)?;
138    Ok(())
139}
140
141/// [OpenedValues] is a typedef for `Vec<Vec<Vec<Vec<F>>>>` for
142/// - each round
143///   - each matrix
144///     - each point to open at
145///       - evaluations for each column of matrix at that point
146fn encode_opened_values<W: Write>(
147    opened_values: &OpenedValues<Challenge>,
148    writer: &mut W,
149) -> Result<()> {
150    encode_slice(&opened_values.preprocessed, writer)?;
151    opened_values.main.len().encode(writer)?;
152    for part in &opened_values.main {
153        encode_slice(part, writer)?;
154    }
155    opened_values.after_challenge.len().encode(writer)?;
156    for phase in &opened_values.after_challenge {
157        encode_slice(phase, writer)?;
158    }
159    opened_values.quotient.len().encode(writer)?;
160    for per_air in &opened_values.quotient {
161        per_air.len().encode(writer)?;
162        for chunk in per_air {
163            encode_slice(chunk, writer)?;
164        }
165    }
166
167    Ok(())
168}
169
170impl Encode for AdjacentOpenedValues<Challenge> {
171    fn encode<W: Write>(&self, writer: &mut W) -> Result<()> {
172        encode_slice(&self.local, writer)?;
173        encode_slice(&self.next, writer)?;
174        Ok(())
175    }
176}
177
178impl Encode for AirProofData<F, Challenge> {
179    /// Encodes the struct
180    /// ```
181    /// pub struct OpenedValues<Challenge> {
182    ///     pub preprocessed: Vec<AdjacentOpenedValues<Challenge>>,
183    ///     pub main: Vec<Vec<AdjacentOpenedValues<Challenge>>>,
184    ///     pub after_challenge: Vec<Vec<AdjacentOpenedValues<Challenge>>>,
185    ///     pub quotient: Vec<Vec<Vec<Challenge>>>,
186    /// }
187    /// ```
188    fn encode<W: Write>(&self, writer: &mut W) -> Result<()> {
189        self.air_id.encode(writer)?;
190        self.degree.encode(writer)?;
191        self.exposed_values_after_challenge.len().encode(writer)?;
192        for exposed_vals in &self.exposed_values_after_challenge {
193            encode_slice(exposed_vals, writer)?;
194        }
195        encode_slice(&self.public_values, writer)?;
196        Ok(())
197    }
198}
199
200// PcsProof<SC> = InnerFriProof where Pcs = TwoAdicFriPcs
201impl Encode for InnerFriProof {
202    /// Encodes the struct
203    /// ```
204    /// pub struct FriProof<Challenge, M: Mmcs<Challenge>> {
205    ///     pub commit_phase_commits: Vec<M::Commitment>,
206    ///     pub query_proofs: Vec<QueryProof<Challenge, M, Vec<BatchOpening<F>>>>,
207    ///     pub final_poly: Vec<Challenge>,
208    ///     pub pow_witness: F,
209    /// }
210    /// ```
211    fn encode<W: Write>(&self, writer: &mut W) -> Result<()> {
212        encode_commitments(&self.commit_phase_commits, writer)?;
213        encode_slice(&self.query_proofs, writer)?;
214        encode_slice(&self.final_poly, writer)?;
215        self.pow_witness.encode(writer)?;
216        Ok(())
217    }
218}
219
220impl Encode for InnerQueryProof {
221    /// Encodes the struct
222    /// ```
223    /// pub struct QueryProof<Challenge, M: Mmcs<Challenge>> {
224    ///     pub input_proof: Vec<BatchOpening<F>>,
225    ///     pub commit_phase_openings: Vec<CommitPhaseProofStep<Challenge, M>>,
226    /// }
227    ///
228    /// pub struct BatchOpening<F> {
229    ///     pub opened_values: Vec<Vec<F>>,
230    ///     pub opening_proof: Vec<[F; DIGEST_SIZE]>,
231    /// }
232    ///
233    /// pub struct CommitPhaseProofStep<Challenge, M: Mmcs<Challenge>> {
234    ///     pub sibling_value: Challenge,
235    ///     pub opening_proof: Vec<[F; DIGEST_SIZE]>,
236    /// }
237    /// ```
238    // @dev [jpw]: We prefer to keep the implementation all in one function
239    // without `impl Encode` on subtypes because it obfuscates what the overall
240    // struct consists of.
241    fn encode<W: Write>(&self, writer: &mut W) -> Result<()> {
242        // Input proof is Vec<BatchOpening<F>>
243        self.input_proof.len().encode(writer)?;
244        for batch_opening in &self.input_proof {
245            batch_opening.opened_values.len().encode(writer)?;
246            for vals in &batch_opening.opened_values {
247                encode_slice(vals, writer)?;
248            }
249            // Opening proof is just a vector of siblings
250            encode_slice(&batch_opening.opening_proof, writer)?;
251        }
252        self.commit_phase_openings.len().encode(writer)?;
253        for step in &self.commit_phase_openings {
254            step.sibling_value.encode(writer)?;
255            encode_slice(&step.opening_proof, writer)?;
256        }
257        Ok(())
258    }
259}
260
261impl Encode for Option<FriLogUpPartialProof<F>> {
262    fn encode<W: Write>(&self, writer: &mut W) -> Result<()> {
263        match self {
264            // If exists, `F` will be < MODULUS < 2^31 so it will
265            // never collide with u32::MAX
266            Some(FriLogUpPartialProof { logup_pow_witness }) => logup_pow_witness.encode(writer),
267            None => writer.write_all(&u32::MAX.to_le_bytes()),
268        }
269    }
270}
271
272impl Encode for Challenge {
273    fn encode<W: Write>(&self, writer: &mut W) -> Result<()> {
274        let base_slice: &[F] = self.as_base_slice();
275        // Fixed length slice, so don't encode length
276        for val in base_slice {
277            val.encode(writer)?;
278        }
279        Ok(())
280    }
281}
282
283/// Encodes length of slice and then each commitment
284fn encode_commitments<W: Write>(commitments: &[Com<SC>], writer: &mut W) -> Result<()> {
285    let coms: Vec<[F; DIGEST_SIZE]> = commitments.iter().copied().map(Into::into).collect();
286    encode_slice(&coms, writer)
287}
288
289// Can't implement Encode on Com<SC> because Rust complains about associated trait types when you
290// don't own the trait (in this case SC)
291impl Encode for [F; DIGEST_SIZE] {
292    fn encode<W: Write>(&self, writer: &mut W) -> Result<()> {
293        for val in self {
294            val.encode(writer)?;
295        }
296        Ok(())
297    }
298}
299
300/// Encodes length of slice and then each element
301pub fn encode_slice<T: Encode, W: Write>(slice: &[T], writer: &mut W) -> Result<()> {
302    slice.len().encode(writer)?;
303    for elt in slice {
304        elt.encode(writer)?;
305    }
306    Ok(())
307}
308
309impl Encode for F {
310    fn encode<W: Write>(&self, writer: &mut W) -> Result<()> {
311        writer.write_all(&self.as_canonical_u32().to_le_bytes())
312    }
313}
314
315impl Encode for usize {
316    fn encode<W: Write>(&self, writer: &mut W) -> Result<()> {
317        let x: u32 = (*self).try_into().map_err(io::Error::other)?;
318        writer.write_all(&x.to_le_bytes())
319    }
320}
321
322// ============ Decode implementation =============
323
324impl Decode for ContinuationVmProof<SC> {
325    fn decode<R: Read>(reader: &mut R) -> Result<Self> {
326        let per_segment = decode_vec(reader)?;
327        let user_public_values = UserPublicValuesProof::decode(reader)?;
328        Ok(Self {
329            per_segment,
330            user_public_values,
331        })
332    }
333}
334
335impl Decode for VmStarkProof<SC> {
336    fn decode<R: Read>(reader: &mut R) -> Result<Self> {
337        let inner = Proof::decode(reader)?;
338        let user_public_values = decode_vec(reader)?;
339        Ok(Self {
340            inner,
341            user_public_values,
342        })
343    }
344}
345
346impl Decode for UserPublicValuesProof<DIGEST_SIZE, F> {
347    fn decode<R: Read>(reader: &mut R) -> Result<Self> {
348        let proof = decode_vec(reader)?;
349        let public_values = decode_vec(reader)?;
350        let public_values_commit = <[F; DIGEST_SIZE]>::decode(reader)?;
351        Ok(Self {
352            proof,
353            public_values,
354            public_values_commit,
355        })
356    }
357}
358
359impl Decode for RootVmVerifierInput<SC> {
360    fn decode<R: Read>(reader: &mut R) -> Result<Self> {
361        let proofs = decode_vec(reader)?;
362        let public_values = decode_vec(reader)?;
363        Ok(Self {
364            proofs,
365            public_values,
366        })
367    }
368}
369
370impl Decode for Proof<SC> {
371    /// Decode a proof using FRI as the PCS with `BabyBearPoseidon2Config`.
372    fn decode<R: Read>(reader: &mut R) -> Result<Self> {
373        let mut version_bytes = [0u8; 4];
374        reader.read_exact(&mut version_bytes)?;
375        let version = u32::from_le_bytes(version_bytes);
376
377        if version != CODEC_VERSION {
378            return Err(io::Error::new(
379                io::ErrorKind::InvalidData,
380                format!("Invalid codec version. Expected {CODEC_VERSION}, got {version}"),
381            ));
382        }
383
384        // Decode commitments
385        let main_trace = decode_commitments(reader)?;
386        let after_challenge = decode_commitments(reader)?;
387        let quotient = decode_commitment(reader)?;
388
389        let commitments = Commitments {
390            main_trace,
391            after_challenge,
392            quotient,
393        };
394
395        // Decode OpeningProof
396        let opening = decode_opening_proof(reader)?;
397
398        // Decode per_air data
399        let per_air = decode_vec(reader)?;
400
401        // Decode RAP phase sequence kind
402        let mut kind_byte = [0u8; 1];
403        reader.read_exact(&mut kind_byte)?;
404        if kind_byte[0] != RapPhaseSeqKind::FriLogUp as u8 {
405            return Err(io::Error::new(
406                io::ErrorKind::InvalidData,
407                format!("Unknown RapPhaseSeqKind: {}", kind_byte[0]),
408            ));
409        }
410
411        // Decode logup witness
412        let rap_phase_seq_proof = Option::<FriLogUpPartialProof<F>>::decode(reader)?;
413
414        Ok(Proof {
415            commitments,
416            opening,
417            per_air,
418            rap_phase_seq_proof,
419        })
420    }
421}
422
423fn decode_commitment<R: Read>(reader: &mut R) -> Result<Com<SC>> {
424    let digest = <[F; DIGEST_SIZE]>::decode(reader)?;
425    // Convert [F; DIGEST_SIZE] to Com<SC>
426    Ok(digest.into())
427}
428
429fn decode_commitments<R: Read>(reader: &mut R) -> Result<Vec<Com<SC>>> {
430    let coms_count = usize::decode(reader)?;
431    let mut coms = Vec::with_capacity(coms_count);
432
433    for _ in 0..coms_count {
434        coms.push(decode_commitment(reader)?);
435    }
436
437    Ok(coms)
438}
439
440fn decode_opening_proof<R: Read>(reader: &mut R) -> Result<OpeningProof<PcsProof<SC>, Challenge>> {
441    // Decode FRI proof
442    let proof = InnerFriProof::decode(reader)?;
443    let values = decode_opened_values(reader)?;
444
445    Ok(OpeningProof { proof, values })
446}
447
448fn decode_opened_values<R: Read>(reader: &mut R) -> Result<OpenedValues<Challenge>> {
449    let preprocessed = decode_vec(reader)?;
450
451    let main_count = usize::decode(reader)?;
452    let mut main = Vec::with_capacity(main_count);
453    for _ in 0..main_count {
454        main.push(decode_vec(reader)?);
455    }
456
457    let after_challenge_count = usize::decode(reader)?;
458    let mut after_challenge = Vec::with_capacity(after_challenge_count);
459    for _ in 0..after_challenge_count {
460        after_challenge.push(decode_vec(reader)?);
461    }
462
463    let quotient_count = usize::decode(reader)?;
464    let mut quotient = Vec::with_capacity(quotient_count);
465    for _ in 0..quotient_count {
466        let per_air_count = usize::decode(reader)?;
467        let mut per_air = Vec::with_capacity(per_air_count);
468        for _ in 0..per_air_count {
469            per_air.push(decode_vec(reader)?);
470        }
471        quotient.push(per_air);
472    }
473
474    Ok(OpenedValues {
475        preprocessed,
476        main,
477        after_challenge,
478        quotient,
479    })
480}
481
482impl Decode for AdjacentOpenedValues<Challenge> {
483    fn decode<R: Read>(reader: &mut R) -> Result<Self> {
484        let local = decode_vec(reader)?;
485        let next = decode_vec(reader)?;
486
487        Ok(AdjacentOpenedValues { local, next })
488    }
489}
490
491impl Decode for AirProofData<F, Challenge> {
492    fn decode<R: Read>(reader: &mut R) -> Result<Self> {
493        let air_id = usize::decode(reader)?;
494        let degree = usize::decode(reader)?;
495
496        let exposed_values_count = usize::decode(reader)?;
497        let mut exposed_values_after_challenge = Vec::with_capacity(exposed_values_count);
498        for _ in 0..exposed_values_count {
499            exposed_values_after_challenge.push(decode_vec(reader)?);
500        }
501
502        let public_values = decode_vec(reader)?;
503
504        Ok(AirProofData {
505            air_id,
506            degree,
507            exposed_values_after_challenge,
508            public_values,
509        })
510    }
511}
512
513impl Decode for InnerFriProof {
514    fn decode<R: Read>(reader: &mut R) -> Result<Self> {
515        let commit_phase_commits = decode_commitments(reader)?;
516        let query_proofs = decode_vec(reader)?;
517        let final_poly = decode_vec(reader)?;
518        let pow_witness = F::decode(reader)?;
519
520        Ok(InnerFriProof {
521            commit_phase_commits,
522            query_proofs,
523            final_poly,
524            pow_witness,
525        })
526    }
527}
528
529impl Decode for InnerQueryProof {
530    /// See [InnerQueryProof::encode].
531    fn decode<R: Read>(reader: &mut R) -> Result<Self> {
532        let batch_opening_count = usize::decode(reader)?;
533        let mut input_proof = Vec::with_capacity(batch_opening_count);
534        for _ in 0..batch_opening_count {
535            let opened_values_len = usize::decode(reader)?;
536            let mut opened_values = Vec::with_capacity(opened_values_len);
537            for _ in 0..opened_values_len {
538                opened_values.push(decode_vec(reader)?);
539            }
540            let opening_proof = decode_vec(reader)?;
541
542            let batch_opening = InnerBatchOpening {
543                opened_values,
544                opening_proof,
545            };
546            input_proof.push(batch_opening);
547        }
548
549        let commit_phase_openings_count = usize::decode(reader)?;
550        let mut commit_phase_openings = Vec::with_capacity(commit_phase_openings_count);
551
552        for _ in 0..commit_phase_openings_count {
553            let sibling_value = Challenge::decode(reader)?;
554            let opening_proof = decode_vec(reader)?;
555
556            commit_phase_openings.push(CommitPhaseProofStep {
557                sibling_value,
558                opening_proof,
559            });
560        }
561
562        Ok(InnerQueryProof {
563            input_proof,
564            commit_phase_openings,
565        })
566    }
567}
568
569impl Decode for Option<FriLogUpPartialProof<F>> {
570    fn decode<R: Read>(reader: &mut R) -> Result<Self> {
571        let mut bytes = [0u8; 4];
572        reader.read_exact(&mut bytes)?;
573
574        let value = u32::from_le_bytes(bytes);
575        // When `Option<FriLogUpPartialProof<F>>` is None, it's encoded as `u32::max`.
576        if value == u32::MAX {
577            return Ok(None);
578        }
579
580        // Reconstruct the field element from the u32 value
581        let logup_pow_witness = F::from_canonical_u32(value);
582        Ok(Some(FriLogUpPartialProof { logup_pow_witness }))
583    }
584}
585
586impl Decode for Challenge {
587    fn decode<R: Read>(reader: &mut R) -> Result<Self> {
588        // For a BinomialExtensionField<F, 4>, we need to read 4 F elements
589        let mut base_elements = [F::ZERO; 4];
590        for base_element in &mut base_elements {
591            *base_element = F::decode(reader)?;
592        }
593
594        // Construct the extension field from base elements
595        Ok(Challenge::from_base_slice(&base_elements))
596    }
597}
598
599impl Decode for [F; DIGEST_SIZE] {
600    fn decode<R: Read>(reader: &mut R) -> Result<Self> {
601        let mut result = [F::ZERO; DIGEST_SIZE];
602        for elt in &mut result {
603            *elt = F::decode(reader)?;
604        }
605        Ok(result)
606    }
607}
608
609/// Decodes a vector of elements
610pub(crate) fn decode_vec<T: Decode, R: Read>(reader: &mut R) -> Result<Vec<T>> {
611    let len = usize::decode(reader)?;
612    let mut vec = Vec::with_capacity(len);
613
614    for _ in 0..len {
615        vec.push(T::decode(reader)?);
616    }
617
618    Ok(vec)
619}
620
621impl Decode for F {
622    fn decode<R: Read>(reader: &mut R) -> Result<Self> {
623        let mut bytes = [0u8; 4];
624        reader.read_exact(&mut bytes)?;
625
626        let value = u32::from_le_bytes(bytes);
627        Ok(F::from_canonical_u32(value))
628    }
629}
630
631impl Decode for usize {
632    fn decode<R: Read>(reader: &mut R) -> Result<Self> {
633        let mut bytes = [0u8; 4];
634        reader.read_exact(&mut bytes)?;
635
636        let value = u32::from_le_bytes(bytes);
637        Ok(value as usize)
638    }
639}
openvm_sdk/codec.rs

openvm_sdk/
codec.rs
