miden_lifted_stark/pcs/
proof.rs

1//! PCS transcript data structures.
2
3use alloc::vec::Vec;
4
5use miden_stark_transcript::{TranscriptError, VerifierChannel};
6use p3_field::{ExtensionField, Field, TwoAdicField};
7
8use crate::{
9    lmcs::{Lmcs, tree_indices::TreeIndices},
10    pcs::{deep::proof::DeepTranscript, fri::proof::FriTranscript, params::PcsParams},
11};
12
13/// Structured transcript view for the full PCS interaction.
14///
15/// Captures observed transcript data plus parsed LMCS batch openings for inspection.
16pub struct PcsTranscript<EF, L>
17where
18    L: Lmcs,
19    L::F: Field,
20    EF: ExtensionField<L::F>,
21{
22    /// DEEP transcript data (evals, PoW witness, challenges).
23    pub deep_transcript: DeepTranscript<L::F, EF>,
24    /// FRI transcript data (round commitments/challenges, final polynomial).
25    pub fri_transcript: FriTranscript<L::F, EF, L::Commitment>,
26    /// Proof-of-work witness for query sampling.
27    pub query_pow_witness: L::F,
28    /// Query indices in sampling order (domain indices, may contain duplicates).
29    pub query_indices: Vec<usize>,
30    /// Batch witness per trace tree (leaf data + Merkle witness).
31    pub deep_witnesses: Vec<L::BatchProof>,
32    /// Batch witness per FRI round (leaf data + Merkle witness).
33    pub fri_witnesses: Vec<L::BatchProof>,
34}
35
36impl<EF, L> PcsTranscript<EF, L>
37where
38    L: Lmcs,
39    L::F: TwoAdicField,
40    EF: ExtensionField<L::F>,
41{
42    /// Parse a PCS transcript from a verifier channel without validation.
43    ///
44    /// Composes [`DeepTranscript`], [`FriTranscript`], and per-query LMCS batch proofs.
45    /// Does not verify any claims; validation happens in
46    /// [`verify_multi`](crate::verify_multi).
47    /// Commitment widths must match the committed rows (including any alignment padding),
48    /// and all commitments are expected to be lifted to the same `log_lde_height`.
49    ///
50    /// `log_lde_height` is the log₂ of the LDE evaluation domain height (i.e. the height of
51    /// the committed LDE matrices). When a trace degree is known, it is typically
52    /// `log_trace_height + params.fri.log_blowup` (plus any extension used by the caller).
53    pub fn from_verifier_channel<Ch, const N: usize>(
54        params: &PcsParams,
55        lmcs: &L,
56        commitments: &[(L::Commitment, Vec<usize>)],
57        log_lde_height: u8,
58        eval_points: [EF; N],
59        channel: &mut Ch,
60    ) -> Result<Self, TranscriptError>
61    where
62        Ch: VerifierChannel<F = L::F, Commitment = L::Commitment>,
63    {
64        if commitments.is_empty() {
65            return Err(TranscriptError::NoMoreFields);
66        }
67
68        let deep_transcript = DeepTranscript::from_verifier_channel::<Ch>(
69            &params.deep,
70            commitments,
71            eval_points.len(),
72            channel,
73        )?;
74
75        let fri_transcript =
76            FriTranscript::from_verifier_channel(&params.fri, log_lde_height, channel)?;
77
78        let query_pow_witness = channel.grind(params.query_pow_bits())?;
79
80        // Sample query indices (domain indices), matching the prover/verifier convention.
81        let query_indices: Vec<usize> = (0..params.num_queries())
82            .map(|_| channel.sample_bits(log_lde_height as usize))
83            .collect();
84        let tree_indices = TreeIndices::new(query_indices.iter().copied(), log_lde_height)
85            .expect("sampled indices are in range");
86
87        let deep_witnesses: Vec<_> = commitments
88            .iter()
89            .map(|(_commitment, widths)| {
90                lmcs.read_batch_proof(widths, &tree_indices, channel).map_err(|e| match e {
91                    crate::lmcs::LmcsError::TranscriptError(te) => te,
92                    _ => TranscriptError::NoMoreFields,
93                })
94            })
95            .collect::<Result<Vec<_>, _>>()?;
96
97        let log_arity = params.fri.fold.log_arity();
98        let arity = params.fri.fold.arity();
99        let num_rounds = params.fri.num_rounds(log_lde_height);
100
101        let mut fri_witnesses = Vec::with_capacity(num_rounds);
102        let mut round_indices = tree_indices;
103        for _round in 0..num_rounds {
104            round_indices.shrink_depth(log_arity);
105            let base_width = arity * EF::DIMENSION;
106            // FRI round openings are unaligned, so use the base width directly.
107            let round_widths = [base_width];
108            let batch = lmcs.read_batch_proof(&round_widths, &round_indices, channel).map_err(
109                |e| match e {
110                    crate::lmcs::LmcsError::TranscriptError(te) => te,
111                    _ => TranscriptError::NoMoreFields,
112                },
113            )?;
114            fri_witnesses.push(batch);
115        }
116
117        Ok(Self {
118            deep_transcript,
119            fri_transcript,
120            query_pow_witness,
121            query_indices,
122            deep_witnesses,
123            fri_witnesses,
124        })
125    }
126}
miden_lifted_stark/pcs/proof.rs

miden_lifted_stark/pcs/
proof.rs
