p3_binary_pcs/whir/
boolean.rs

1//! A bit witness committed narrow, and opened through WHIR over the additive binary domain.
2//!
3//! ```text
4//!     packing    bits  ->  the elements a commitment holds, by reinterpretation
5//!     switch     a claim about the bits  ->  a claim about the packing
6//!     opening    that claim  ->  discharged by WHIR
7//! ```
8//!
9//! The packing is a bijection between bit strings and elements of the alphabet.
10//!
11//! One committed byte therefore holds eight trace bits, whatever the alphabet's width.
12//!
13//! No step of the commit path widens a bit into an element of its own.
14//!
15//! # Soundness
16//!
17//! Three errors compose by a union bound.
18//!
19//! ```text
20//!     commitment       the proximity argument's own budget, at one opened point
21//!     reduction        one bit ring switch for every claim, its rounds run once
22//!     claim batching   the claims folded under powers of lambda
23//! ```
24//!
25//! All come back labelled, so a report says which one is short.
26//!
27//! The batch runs before the proximity argument names one codeword.
28//!
29//! So it is charged over every candidate the commitment still leaves open.
30
31use alloc::vec;
32use alloc::vec::Vec;
33
34use p3_binary_field::{PackedGf2, TowerLevel, Underlier};
35use p3_challenger::fs::TranscriptField;
36use p3_challenger::{CanObserve, CanSampleUniformBits, FieldChallenger, GrindingChallenger};
37use p3_commit::Mmcs;
38use p3_field::Field;
39use p3_multilinear_util::point::Point;
40use p3_security::multilinear::{bit_ring_switch_claim_batching_term, bit_ring_switch_tensors_term};
41use p3_sumcheck::layout::{Layout, SuffixProver};
42use p3_sumcheck::ring_switch::bits::{
43    BitPacking, BitPackingView, BitRingSwitch, BitRingSwitchClaims,
44};
45use p3_sumcheck::{
46    OpeningBatch, OpeningProtocol, PrescribedOpeningSecurity, PrescribedPointPcs, TableShape,
47    TableSpec,
48};
49use p3_whir::{WhirDomain, WhirProver, WhirProverData};
50
51use crate::boolean::{BitOpening, BitReadings, BooleanBackend, BooleanMultilinearPcs};
52use crate::boolean_trace::BooleanTraceCommitment;
53use crate::fold::ChallengeField;
54use crate::packing::{Coordinates, PackedStack};
55use crate::whir::error::BooleanWhirError;
56use crate::whir::proof::BooleanWhirProof;
57use crate::whir::shape::ProofShape;
58
59/// The binding mode the committed layout uses.
60///
61/// One mode is fixed rather than chosen, so a commitment and its replay never disagree.
62type Binding<EF> = SuffixProver<EF, EF>;
63
64/// The proximity argument every packed claim is discharged against.
65pub type BooleanWhirProver<EF, Dft, MT, Challenger> =
66    WhirProver<EF, EF, Dft, MT, Challenger, Binding<EF>>;
67
68/// Prover-side data retained between committing and opening.
69pub type BooleanWhirData<EF, MT> = WhirProverData<EF, EF, MT, SuffixProver<EF, EF>>;
70
71/// A batched trace of Boolean columns, discharged through the additive-domain proximity argument.
72pub type BooleanWhirTracePcs<EF, Dft, MT, Challenger> =
73    BooleanTraceCommitment<EF, BooleanWhirPcs<EF, Dft, MT, Challenger>>;
74
75/// A commitment to a function from the hypercube to `{0, 1}`, opened through WHIR.
76///
77/// The committed object is a bit witness.
78///
79/// An opening answers for its multilinear extension at a point of the challenge field.
80pub struct BooleanWhirPcs<EF: Field, Dft, MT, Challenger> {
81    /// The proximity argument the packed multilinear is discharged against.
82    inner: BooleanWhirProver<EF, Dft, MT, Challenger>,
83    /// Variables the bit witness has, which is the packing's plus the absorbed ones.
84    num_variables: usize,
85}
86
87impl<EF, Dft, MT, Challenger> BooleanWhirPcs<EF, Dft, MT, Challenger>
88where
89    EF: Field + TranscriptField + TowerLevel + Coordinates + Ord,
90    Dft: WhirDomain<EF, EF>,
91    MT: Mmcs<EF>,
92{
93    /// Wrap a proximity argument as a commitment to a bit witness of this many variables.
94    ///
95    /// # Errors
96    ///
97    /// Returns an error unless one element can absorb the witness's low coordinates.
98    ///
99    /// Returns an error unless the schedule commits exactly the elements the packing holds.
100    pub fn new(
101        inner: BooleanWhirProver<EF, Dft, MT, Challenger>,
102        num_variables: usize,
103    ) -> Result<Self, BooleanWhirError> {
104        let packed = Self::packed_variables(num_variables)?;
105        if inner.num_variables() != packed {
106            return Err(BooleanWhirError::ConfigArity {
107                expected: packed,
108                actual: inner.num_variables(),
109            });
110        }
111        Ok(Self {
112            inner,
113            num_variables,
114        })
115    }
116
117    /// Variables the committed bit witness has, so `2^n` bits in all.
118    #[must_use]
119    pub const fn num_variables(&self) -> usize {
120        self.num_variables
121    }
122
123    /// Bytes the commitment holds, which is one per eight bits of the witness.
124    #[must_use]
125    pub const fn committed_bytes(&self) -> usize {
126        1 << (self.num_variables - 3)
127    }
128
129    /// Variables the packing keeps, the witness's less the ones one element absorbs.
130    fn packed_variables(num_variables: usize) -> Result<usize, BooleanWhirError> {
131        let absorbed = BitRingSwitch::<EF>::ABSORBED;
132        num_variables
133            .checked_sub(absorbed)
134            .ok_or(BooleanWhirError::WitnessTooNarrow {
135                needed: absorbed,
136                actual: num_variables,
137            })
138    }
139
140    /// The opening schedule this many surviving claims are discharged through.
141    ///
142    /// One table of one column, opened directly at one point per claim.
143    /// A batch of claims leaves one surviving claim, whatever its size.
144    fn protocol(&self, num_claims: usize) -> OpeningProtocol {
145        OpeningProtocol::new(vec![TableSpec::new(
146            TableShape::new(self.inner.num_variables(), 1),
147            (0..num_claims)
148                .map(|_| OpeningBatch::new(vec![0], Vec::new()))
149                .collect(),
150        )])
151    }
152
153    /// Every opening's reduction, gathered into the one batch that reduces them all.
154    fn claims(openings: &[BitOpening<EF>]) -> Result<BitRingSwitchClaims<EF>, BooleanWhirError> {
155        let reductions = openings
156            .iter()
157            .map(Self::reduction)
158            .collect::<Result<Vec<_>, _>>()?;
159        BitRingSwitchClaims::new(reductions).map_err(BooleanWhirError::Reduction)
160    }
161
162    /// The reduction answering every reading one opening asks for.
163    fn reduction(opening: &BitOpening<EF>) -> Result<BitRingSwitch<EF>, BooleanWhirError> {
164        if opening.next {
165            BitRingSwitch::with_successor(&opening.point, opening.row_variables)
166        } else {
167            BitRingSwitch::new(&opening.point)
168        }
169        .map_err(BooleanWhirError::Reduction)
170    }
171
172    /// Each point as an opening asking for the current reading alone.
173    fn current_openings(points: &[Point<EF>]) -> Vec<BitOpening<EF>> {
174        points
175            .iter()
176            .map(|point| BitOpening {
177                point: point.clone(),
178                row_variables: point.num_variables(),
179                current: true,
180                next: false,
181            })
182            .collect()
183    }
184
185    /// Check that every opening names the witness's variables and asks for a reading it has.
186    fn check_openings(&self, openings: &[BitOpening<EF>]) -> Result<(), BooleanWhirError> {
187        if openings.is_empty() {
188            return Err(BooleanWhirError::NoPoints);
189        }
190        for (index, opening) in openings.iter().enumerate() {
191            if opening.point.num_variables() != self.num_variables {
192                return Err(BooleanWhirError::PointArity {
193                    expected: self.num_variables,
194                    actual: opening.point.num_variables(),
195                });
196            }
197            if !opening.current && !opening.next {
198                return Err(BooleanWhirError::NoReading { index });
199            }
200            if opening.row_variables > self.num_variables {
201                return Err(BooleanWhirError::RowVariables {
202                    index,
203                    row_variables: opening.row_variables,
204                    num_variables: self.num_variables,
205                });
206            }
207        }
208        Ok(())
209    }
210
211    /// The packed multilinear the commitment holds, borrowed from the retained table.
212    ///
213    /// # Panics
214    ///
215    /// Never for a table this scheme committed.
216    ///
217    /// Its alphabet is byte aligned and its height is a power of two.
218    fn packing(prover_data: &BooleanWhirData<EF, MT>) -> BitPackingView<'_, EF> {
219        BitPacking::from_packed(prover_data.table(0).poly(0))
220            .expect("a committed table is a hypercube over a byte-aligned level")
221    }
222}
223
224impl<EF, Dft, MT, Challenger> BooleanWhirPcs<EF, Dft, MT, Challenger>
225where
226    EF: Field + TranscriptField + TowerLevel + Coordinates + Ord + Send + Sync + ChallengeField<EF>,
227    Dft: WhirDomain<EF, EF>,
228    MT: Mmcs<EF>,
229    Challenger: FieldChallenger<EF>
230        + GrindingChallenger<Witness = EF>
231        + CanSampleUniformBits<EF>
232        + CanObserve<MT::Commitment>,
233{
234    /// Every labelled algebraic error one opening of this many claims charges.
235    ///
236    /// ```text
237    ///     commitment       the proximity argument's own budget, at the one surviving point
238    ///     reduction        one batched bit ring switch, batching its elements under one draw
239    ///     claim batching   the claims folded under powers of lambda
240    /// ```
241    ///
242    /// The terms are independent draws, so they compose by a union bound.
243    ///
244    /// The reduction is charged over every candidate the commitment leaves open.
245    ///
246    /// Its challenges are drawn before the proximity argument names one of them.
247    ///
248    /// The count itself is forwarded untouched, because this is a link and not the end.
249    ///
250    /// A caller stacking its own draw faces the same list the proximity argument left.
251    ///
252    /// So it charges that draw over the same count.
253    ///
254    /// Nothing here covers hash or transcript collisions, which the caller supplies.
255    ///
256    /// # Returns
257    ///
258    /// Nothing when the proximity argument declines to price the schedule.
259    #[must_use]
260    pub fn readings_security(
261        &self,
262        num_claims: usize,
263        successor_tensors: bool,
264    ) -> Option<PrescribedOpeningSecurity> {
265        // Every claim of a batch survives as one claim, at one point.
266        let protocol = self.protocol(num_claims.min(1));
267        let mut security = self.inner.prescribed_security(&protocol)?;
268        // The tensor alone, or the tensor with carry and last.
269        let num_tensors = if successor_tensors { 3 } else { 1 };
270        // The batch runs before one candidate is named, so it pays for all of them.
271        //
272        // The charge leaves the count alone, so the caller above still sees the same list.
273        //
274        // It then charges its own draws over that list.
275        security.charge_reduction(bit_ring_switch_tensors_term(
276            num_claims.min(1),
277            num_tensors,
278            BitRingSwitch::<EF>::ABSORBED,
279            self.inner.num_variables(),
280            EF::bits(),
281        ));
282        // A single claim draws no lambda, so its report carries no batching term.
283        if num_claims > 1 {
284            security.charge_reduction(bit_ring_switch_claim_batching_term(num_claims, EF::bits()));
285        }
286        Some(security)
287    }
288
289    /// The shape of every proof an opening of this many claims can produce.
290    ///
291    /// It covers the reductions as well as the opening, so a ceiling graded against it binds both.
292    #[must_use]
293    pub fn proof_shape(&self, num_claims: usize, successor_tensors: bool) -> ProofShape {
294        ProofShape::of_bit_readings(&self.inner, num_claims, successor_tensors)
295    }
296
297    /// Open the bit witness with the readings every opening asks for, in one proof.
298    ///
299    /// No point needs prior transcript binding: each reduction binds its own.
300    ///
301    /// # Returns
302    ///
303    /// One set of readings per opening, in the order the openings were supplied.
304    ///
305    /// # Errors
306    ///
307    /// Before the transcript moves, an opening that names the wrong variables.
308    ///
309    /// An opening asking for no reading, or stepping within more rows than the witness has.
310    #[allow(clippy::type_complexity)]
311    pub fn open_readings(
312        &self,
313        prover_data: BooleanWhirData<EF, MT>,
314        openings: &[BitOpening<EF>],
315        challenger: &mut Challenger,
316    ) -> Result<(Vec<BitReadings<EF>>, BooleanWhirProof<EF, MT>), BooleanWhirError> {
317        self.check_openings(openings)?;
318        // Every reduction is set up before any runs, so a refused one leaves the transcript alone.
319        let claims = Self::claims(openings)?;
320        let packing = Self::packing(&prover_data);
321
322        // One batch for every opening, leaving one claim about the packing.
323        let (reduction, surviving_point, _) =
324            tracing::info_span!("bit ring switch").in_scope(|| {
325                claims.prove::<<EF as ChallengeField<EF>>::SumcheckRepr, _, _>(&packing, challenger)
326            });
327
328        // The elements each claim sends already hold its readings.
329        let readings = openings
330            .iter()
331            .zip(claims.reductions())
332            .zip(&reduction.claims)
333            .map(|((opening, switch), elements)| {
334                let current = opening
335                    .current
336                    .then(|| switch.incoming_claim(&elements.tensor));
337                let next = opening
338                    .next
339                    .then(|| switch.successor_claim(&elements.tensor, elements.successor.as_ref()))
340                    .transpose()
341                    .map_err(BooleanWhirError::Reduction)?;
342                Ok(BitReadings { current, next })
343            })
344            .collect::<Result<Vec<_>, BooleanWhirError>>()?;
345
346        // The surviving value crosses the wire twice, and the closing check is that the two agree.
347        // The surviving point came out of the batch's rounds, so it is bound already.
348        let opening = self
349            .inner
350            .open_at(
351                prover_data,
352                &self.protocol(1),
353                &[surviving_point],
354                challenger,
355            )
356            .map_err(BooleanWhirError::Commit)?;
357
358        Ok((readings, BooleanWhirProof { reduction, opening }))
359    }
360
361    /// Check one proof against the readings it claims at every opening.
362    ///
363    /// The commitment's binding is the caller's, replayed before this is reached.
364    ///
365    /// # Errors
366    ///
367    /// Before the transcript moves, a refused opening or a reading count that disagrees.
368    ///
369    /// After it, a false reading, a failed reduction, the commitment, or an unclosed claim.
370    pub fn verify_readings(
371        &self,
372        commitment: &MT::Commitment,
373        openings: &[BitOpening<EF>],
374        readings: &[BitReadings<EF>],
375        proof: &BooleanWhirProof<EF, MT>,
376        challenger: &mut Challenger,
377    ) -> Result<(), BooleanWhirError> {
378        self.check_openings(openings)?;
379        if readings.len() != openings.len() || proof.reduction.claims.len() != openings.len() {
380            return Err(BooleanWhirError::ClaimCount {
381                expected: openings.len(),
382                values: readings.len(),
383                reductions: proof.reduction.claims.len(),
384            });
385        }
386        // The openings fix which readings are checked, so a missing one is never skipped.
387        if let Some(index) = openings
388            .iter()
389            .zip(readings)
390            .position(|(opening, reading)| {
391                reading.current.is_some() != opening.current
392                    || reading.next.is_some() != opening.next
393            })
394        {
395            return Err(BooleanWhirError::ReadingShape { index });
396        }
397        let claims = Self::claims(openings)?;
398
399        // The batch turns every reading about the bits into one claim about the packing.
400        let readings = readings
401            .iter()
402            .map(|reading| (reading.current, reading.next))
403            .collect::<Vec<_>>();
404        let (surviving_point, surviving_value) = claims
405            .verify_readings(&proof.reduction, &readings, challenger)
406            .map_err(BooleanWhirError::ReductionProof)?;
407
408        // One proximity opening pins the one surviving point to the committed polynomial.
409        let evals = self
410            .inner
411            .verify_at(
412                commitment,
413                &proof.opening,
414                &self.protocol(1),
415                &[surviving_point],
416                challenger,
417            )
418            .map_err(BooleanWhirError::Opening)?;
419
420        // The batch closes against the value opened at its surviving point.
421        match evals.as_slice() {
422            [batch] if batch.current().first() == Some(&surviving_value) => Ok(()),
423            _ => Err(BooleanWhirError::SurvivingClaim),
424        }
425    }
426}
427
428impl<EF, Dft, MT, Challenger> BooleanMultilinearPcs<EF, Challenger>
429    for BooleanWhirPcs<EF, Dft, MT, Challenger>
430where
431    EF: Field + TranscriptField + TowerLevel + Coordinates + Ord + Send + Sync + ChallengeField<EF>,
432    Dft: WhirDomain<EF, EF>,
433    MT: Mmcs<EF>,
434    Challenger: FieldChallenger<EF>
435        + GrindingChallenger<Witness = EF>
436        + CanSampleUniformBits<EF>
437        + CanObserve<MT::Commitment>,
438{
439    fn observe_commitment(&self, commitment: &Self::Commitment, challenger: &mut Challenger) {
440        p3_commit::MultilinearPcs::<EF, Challenger>::observe_commitment(
441            &self.inner,
442            commitment,
443            challenger,
444        );
445    }
446
447    fn commit_bits<U: Underlier>(
448        &self,
449        bits: &[PackedGf2<U>],
450        challenger: &mut Challenger,
451    ) -> Result<(Self::Commitment, Self::ProverData), Self::Error> {
452        // The packing is one copy of the bits, so the witness is never swept for arithmetic.
453        let stack = PackedStack::<PackedGf2<U>, EF>::from_columns(&[bits])
454            .map_err(BooleanWhirError::Packing)?;
455        if stack.column_num_variables() != self.inner.num_variables() {
456            return Err(BooleanWhirError::WitnessArity {
457                expected: self.inner.num_variables(),
458                actual: stack.column_num_variables(),
459            });
460        }
461
462        let folding = self.inner.round_folding_factor(0);
463        let witness = Binding::<EF>::new_witness(vec![stack.into_table()], folding);
464        p3_commit::MultilinearPcs::<EF, Challenger>::commit(&self.inner, witness, challenger)
465            .map_err(BooleanWhirError::Commit)
466    }
467
468    fn open_readings(
469        &self,
470        prover_data: Self::ProverData,
471        openings: &[BitOpening<EF>],
472        challenger: &mut Challenger,
473    ) -> Result<(Vec<BitReadings<EF>>, Self::Proof), Self::Error> {
474        Self::open_readings(self, prover_data, openings, challenger)
475    }
476
477    fn verify_readings(
478        &self,
479        commitment: &Self::Commitment,
480        openings: &[BitOpening<EF>],
481        readings: &[BitReadings<EF>],
482        proof: &Self::Proof,
483        challenger: &mut Challenger,
484    ) -> Result<(), Self::Error> {
485        Self::verify_readings(self, commitment, openings, readings, proof, challenger)
486    }
487
488    fn readings_security(
489        &self,
490        num_claims: usize,
491        successor_tensors: bool,
492    ) -> Option<PrescribedOpeningSecurity> {
493        Self::readings_security(self, num_claims, successor_tensors)
494    }
495
496    fn open_at_points(
497        &self,
498        prover_data: Self::ProverData,
499        points: &[Point<EF>],
500        challenger: &mut Challenger,
501    ) -> Result<(Vec<EF>, Self::Proof), Self::Error> {
502        let (readings, proof) =
503            self.open_readings(prover_data, &Self::current_openings(points), challenger)?;
504        let values = readings
505            .into_iter()
506            .map(|reading| {
507                reading
508                    .current
509                    .expect("an opening asking for the current reading carries it")
510            })
511            .collect();
512        Ok((values, proof))
513    }
514
515    fn verify_at_points(
516        &self,
517        commitment: &Self::Commitment,
518        points: &[Point<EF>],
519        values: &[EF],
520        proof: &Self::Proof,
521        challenger: &mut Challenger,
522    ) -> Result<(), Self::Error> {
523        let readings: Vec<BitReadings<EF>> = values
524            .iter()
525            .map(|&value| BitReadings {
526                current: Some(value),
527                next: None,
528            })
529            .collect();
530        self.verify_readings(
531            commitment,
532            &Self::current_openings(points),
533            &readings,
534            proof,
535            challenger,
536        )
537    }
538}
539
540impl<EF, Dft, MT, Challenger> BooleanBackend<EF> for BooleanWhirPcs<EF, Dft, MT, Challenger>
541where
542    EF: Field + TranscriptField + TowerLevel + Coordinates + Ord + Send + Sync,
543    Dft: WhirDomain<EF, EF>,
544    MT: Mmcs<EF>,
545{
546    type Commitment = MT::Commitment;
547    type ProverData = BooleanWhirData<EF, MT>;
548    type Proof = BooleanWhirProof<EF, MT>;
549    type Error = BooleanWhirError;
550
551    fn num_variables(&self) -> usize {
552        self.num_variables
553    }
554}
p3_binary_pcs/whir/boolean.rs

p3_binary_pcs/whir/
boolean.rs
