p3_challenger/
serializing_challenger.rs

1use alloc::vec::Vec;
2use core::marker::PhantomData;
3
4use p3_field::{BasedVectorSpace, PrimeField32, PrimeField64};
5use p3_maybe_rayon::prelude::*;
6use p3_symmetric::{CryptographicHasher, Hash, MerkleCap};
7use p3_util::log2_ceil_u64;
8use tracing::instrument;
9
10use crate::{
11    CanFinalizeDigest, CanObserve, CanSample, CanSampleBits, CanSampleUniformBits, FieldChallenger,
12    GrindingChallenger, HashChallenger, ResamplingError,
13};
14
15/// Given a challenger that can observe and sample bytes, produces a challenger that is able to
16/// sample and observe field elements of a `PrimeField32`.
17///
18/// **Observing**:
19/// -  Takes a field element will serialize it into a byte array and observe each byte.
20///
21/// **Sampling**:
22/// -  Samples a field element in a prime field of size `p` by sampling uniformly an element in the
23///    range (0..1 << log_2(p)). This avoids modulo bias.
24#[derive(Clone, Debug)]
25pub struct SerializingChallenger32<F, Inner> {
26    inner: Inner,
27    _marker: PhantomData<F>,
28}
29
30/// Given a challenger that can observe and sample bytes, produces a challenger that is able to
31/// sample and observe field elements of a `PrimeField64` field.
32///
33/// **Observing**:
34/// -  Takes a field element will serialize it into a byte array and observe each byte.
35///
36/// **Sampling**:
37/// -  Samples a field element in a prime field of size `p` by sampling uniformly an element in the
38///    range (0..1 << log_2(p)). This avoids modulo bias.
39#[derive(Clone, Debug)]
40pub struct SerializingChallenger64<F, Inner> {
41    inner: Inner,
42    _marker: PhantomData<F>,
43}
44
45impl<F: PrimeField32, Inner: CanObserve<u8>> SerializingChallenger32<F, Inner> {
46    pub const fn new(inner: Inner) -> Self {
47        Self {
48            inner,
49            _marker: PhantomData,
50        }
51    }
52}
53
54impl<F, H> SerializingChallenger32<F, HashChallenger<u8, H, 32>>
55where
56    F: PrimeField32,
57    H: CryptographicHasher<u8, [u8; 32]>,
58{
59    pub const fn from_hasher(initial_state: Vec<u8>, hasher: H) -> Self {
60        Self::new(HashChallenger::new(initial_state, hasher))
61    }
62}
63
64impl<F: PrimeField32, Inner: CanObserve<u8>> CanObserve<F> for SerializingChallenger32<F, Inner> {
65    fn observe(&mut self, value: F) {
66        self.inner
67            .observe_slice(&value.to_unique_u32().to_le_bytes());
68    }
69}
70
71impl<F: PrimeField32, const N: usize, Inner: CanObserve<u8>> CanObserve<Hash<F, u8, N>>
72    for SerializingChallenger32<F, Inner>
73{
74    fn observe(&mut self, values: Hash<F, u8, N>) {
75        for value in values {
76            self.inner.observe(value);
77        }
78    }
79}
80
81impl<F: PrimeField32, const N: usize, Inner: CanObserve<u8>> CanObserve<Hash<F, u64, N>>
82    for SerializingChallenger32<F, Inner>
83{
84    fn observe(&mut self, values: Hash<F, u64, N>) {
85        for value in values {
86            self.inner.observe_slice(&value.to_le_bytes());
87        }
88    }
89}
90
91impl<F: PrimeField32, const N: usize, Inner: CanObserve<u8>> CanObserve<&MerkleCap<F, [u8; N]>>
92    for SerializingChallenger32<F, Inner>
93{
94    fn observe(&mut self, cap: &MerkleCap<F, [u8; N]>) {
95        for digest in cap.roots() {
96            for value in digest {
97                self.inner.observe(*value);
98            }
99        }
100    }
101}
102
103impl<F: PrimeField32, const N: usize, Inner: CanObserve<u8>> CanObserve<MerkleCap<F, [u8; N]>>
104    for SerializingChallenger32<F, Inner>
105{
106    fn observe(&mut self, cap: MerkleCap<F, [u8; N]>) {
107        self.observe(&cap);
108    }
109}
110
111impl<F: PrimeField32, const N: usize, Inner: CanObserve<u8>> CanObserve<&MerkleCap<F, [u64; N]>>
112    for SerializingChallenger32<F, Inner>
113{
114    fn observe(&mut self, cap: &MerkleCap<F, [u64; N]>) {
115        for digest in cap.roots() {
116            for value in digest {
117                self.inner.observe_slice(&value.to_le_bytes());
118            }
119        }
120    }
121}
122
123impl<F: PrimeField32, const N: usize, Inner: CanObserve<u8>> CanObserve<MerkleCap<F, [u64; N]>>
124    for SerializingChallenger32<F, Inner>
125{
126    fn observe(&mut self, cap: MerkleCap<F, [u64; N]>) {
127        self.observe(&cap);
128    }
129}
130
131impl<F, EF, Inner> CanSample<EF> for SerializingChallenger32<F, Inner>
132where
133    F: PrimeField32,
134    EF: BasedVectorSpace<F>,
135    Inner: CanSample<u8>,
136{
137    fn sample(&mut self) -> EF {
138        let modulus = F::ORDER_U32;
139        let log_size = log2_ceil_u64(F::ORDER_U64);
140        // We use u64 to avoid overflow in the case that log_size = 32.
141        let pow_of_two_bound = ((1u64 << log_size) - 1) as u32;
142        // Perform rejection sampling over the uniform range (0..log2_ceil(p))
143        let sample_base = |inner: &mut Inner| loop {
144            let value = u32::from_le_bytes(inner.sample_array());
145            let value = value & pow_of_two_bound;
146            if value < modulus {
147                return unsafe {
148                    // This is safe as value < F::ORDER_U32.
149                    F::from_canonical_unchecked(value)
150                };
151            }
152        };
153        EF::from_basis_coefficients_fn(|_| sample_base(&mut self.inner))
154    }
155}
156
157impl<F, Inner> CanSampleBits<usize> for SerializingChallenger32<F, Inner>
158where
159    F: PrimeField32,
160    Inner: CanSample<u8>,
161{
162    fn sample_bits(&mut self, bits: usize) -> usize {
163        assert!(bits < (usize::BITS as usize));
164        // Evaluate the bound in `u64` to keep the shift within its type width.
165        // A `usize` shift by `bits >= 32` overflows on 32-bit targets and would zero the mask.
166        assert!(
167            (1u64 << bits) < F::ORDER_U64,
168            "requested bit count must fit within the field order"
169        );
170        let rand_usize = u32::from_le_bytes(self.inner.sample_array()) as usize;
171        rand_usize & ((1 << bits) - 1)
172    }
173}
174
175impl<F, Inner> CanSampleUniformBits<F> for SerializingChallenger32<F, Inner>
176where
177    F: PrimeField32,
178    Inner: CanSample<u8>,
179{
180    /// Sample uniform bits by masking bytes from the inner stream.
181    ///
182    /// # Overview
183    ///
184    /// The inner stream emits cryptographic-hash bytes uniform on `[0, 2^8)`.
185    ///
186    /// Reading 4 bytes as a 32-bit integer and masking the low `bits` is
187    /// exactly uniform on `[0, 2^bits)`.
188    ///
189    /// No field-element decomposition occurs, so no rejection band exists.
190    /// The const generic is therefore inert: this function never errors
191    /// and never resamples.
192    fn sample_uniform_bits<const RESAMPLE: bool>(
193        &mut self,
194        bits: usize,
195    ) -> Result<usize, ResamplingError> {
196        // Byte-sourced sampling is uniform without rejection, so the
197        // result is always valid and the error arm is unreachable.
198        Ok(self.sample_bits(bits))
199    }
200}
201
202impl<F, Inner> GrindingChallenger for SerializingChallenger32<F, Inner>
203where
204    F: PrimeField32,
205    Inner: CanSample<u8> + CanObserve<u8> + Clone + Send + Sync,
206{
207    type Witness = F;
208
209    #[instrument(name = "grind for proof-of-work witness", skip_all)]
210    fn grind(&mut self, bits: usize) -> Self::Witness {
211        assert!(bits < (usize::BITS as usize));
212        // Evaluate the bound in `u64` to keep the shift within its type width.
213        // A `u32` shift by `bits >= 32` would wrap and accept a trivial proof-of-work.
214        assert!(
215            (1u64 << bits) < F::ORDER_U64,
216            "requested bit count must fit within the field order"
217        );
218
219        // Trivial case: 0 bits mean no PoW is required and any witness is valid.
220        if bits == 0 {
221            return F::ZERO;
222        }
223
224        let witness = (0..F::ORDER_U32)
225            .into_par_iter()
226            .map(|i| unsafe {
227                // i < F::ORDER_U32 by construction so this is safe.
228                F::from_canonical_unchecked(i)
229            })
230            .find_any(|witness| self.clone().check_witness(bits, *witness))
231            .expect("failed to find witness");
232        assert!(self.check_witness(bits, witness));
233        witness
234    }
235}
236
237impl<F, Inner> FieldChallenger<F> for SerializingChallenger32<F, Inner>
238where
239    F: PrimeField32,
240    Inner: CanSample<u8> + CanObserve<u8> + Clone + Send + Sync,
241{
242}
243
244impl<F: PrimeField64, Inner: CanObserve<u8>> SerializingChallenger64<F, Inner> {
245    pub const fn new(inner: Inner) -> Self {
246        Self {
247            inner,
248            _marker: PhantomData,
249        }
250    }
251}
252
253impl<F, H> SerializingChallenger64<F, HashChallenger<u8, H, 32>>
254where
255    F: PrimeField64,
256    H: CryptographicHasher<u8, [u8; 32]>,
257{
258    pub const fn from_hasher(initial_state: Vec<u8>, hasher: H) -> Self {
259        Self::new(HashChallenger::new(initial_state, hasher))
260    }
261}
262
263impl<F: PrimeField64, Inner: CanObserve<u8>> CanObserve<F> for SerializingChallenger64<F, Inner> {
264    fn observe(&mut self, value: F) {
265        self.inner
266            .observe_slice(&value.to_unique_u64().to_le_bytes());
267    }
268}
269
270impl<F: PrimeField64, const N: usize, Inner: CanObserve<u8>> CanObserve<Hash<F, u8, N>>
271    for SerializingChallenger64<F, Inner>
272{
273    fn observe(&mut self, values: Hash<F, u8, N>) {
274        for value in values {
275            self.inner.observe(value);
276        }
277    }
278}
279
280impl<F: PrimeField64, const N: usize, Inner: CanObserve<u8>> CanObserve<Hash<F, u64, N>>
281    for SerializingChallenger64<F, Inner>
282{
283    fn observe(&mut self, values: Hash<F, u64, N>) {
284        for value in values {
285            self.inner.observe_slice(&value.to_le_bytes());
286        }
287    }
288}
289
290impl<F: PrimeField64, const N: usize, Inner: CanObserve<u8>> CanObserve<&MerkleCap<F, [u8; N]>>
291    for SerializingChallenger64<F, Inner>
292{
293    fn observe(&mut self, cap: &MerkleCap<F, [u8; N]>) {
294        for digest in cap.roots() {
295            for value in digest {
296                self.inner.observe(*value);
297            }
298        }
299    }
300}
301
302impl<F: PrimeField64, const N: usize, Inner: CanObserve<u8>> CanObserve<MerkleCap<F, [u8; N]>>
303    for SerializingChallenger64<F, Inner>
304{
305    fn observe(&mut self, cap: MerkleCap<F, [u8; N]>) {
306        self.observe(&cap);
307    }
308}
309
310impl<F: PrimeField64, const N: usize, Inner: CanObserve<u8>> CanObserve<&MerkleCap<F, [u64; N]>>
311    for SerializingChallenger64<F, Inner>
312{
313    fn observe(&mut self, cap: &MerkleCap<F, [u64; N]>) {
314        for digest in cap.roots() {
315            for value in digest {
316                self.inner.observe_slice(&value.to_le_bytes());
317            }
318        }
319    }
320}
321
322impl<F: PrimeField64, const N: usize, Inner: CanObserve<u8>> CanObserve<MerkleCap<F, [u64; N]>>
323    for SerializingChallenger64<F, Inner>
324{
325    fn observe(&mut self, cap: MerkleCap<F, [u64; N]>) {
326        self.observe(&cap);
327    }
328}
329
330impl<F, EF, Inner> CanSample<EF> for SerializingChallenger64<F, Inner>
331where
332    F: PrimeField64,
333    EF: BasedVectorSpace<F>,
334    Inner: CanSample<u8>,
335{
336    fn sample(&mut self) -> EF {
337        let modulus = F::ORDER_U64;
338        let log_size = log2_ceil_u64(F::ORDER_U64) as u32;
339        // We use u128 to avoid overflow in the case that log_size = 64.
340        let pow_of_two_bound = ((1u128 << log_size) - 1) as u64;
341
342        // Perform rejection sampling over the uniform range (0..log2_ceil(p))
343        let sample_base = |inner: &mut Inner| loop {
344            let value = u64::from_le_bytes(inner.sample_array());
345            let value = value & pow_of_two_bound;
346            if value < modulus {
347                return unsafe {
348                    // This is safe as value < F::ORDER_U64.
349                    F::from_canonical_unchecked(value)
350                };
351            }
352        };
353        EF::from_basis_coefficients_fn(|_| sample_base(&mut self.inner))
354    }
355}
356
357impl<F, Inner> CanSampleBits<usize> for SerializingChallenger64<F, Inner>
358where
359    F: PrimeField64,
360    Inner: CanSample<u8>,
361{
362    fn sample_bits(&mut self, bits: usize) -> usize {
363        assert!(bits < (usize::BITS as usize));
364        assert!((1u64 << bits) <= F::ORDER_U64);
365        let rand_u64 = u64::from_le_bytes(self.inner.sample_array());
366        (rand_u64 & ((1u64 << bits) - 1)) as usize
367    }
368}
369
370impl<F, Inner> CanSampleUniformBits<F> for SerializingChallenger64<F, Inner>
371where
372    F: PrimeField64,
373    Inner: CanSample<u8>,
374{
375    /// Sample uniform bits by masking bytes from the inner stream.
376    ///
377    /// # Overview
378    ///
379    /// The inner stream emits cryptographic-hash bytes uniform on `[0, 2^8)`.
380    ///
381    /// Reading 8 bytes as a 64-bit integer and masking the low `bits` is
382    /// exactly uniform on `[0, 2^bits)`.
383    ///
384    /// No field-element decomposition occurs, so no rejection band exists.
385    /// The const generic is therefore inert: this function never errors
386    /// and never resamples.
387    fn sample_uniform_bits<const RESAMPLE: bool>(
388        &mut self,
389        bits: usize,
390    ) -> Result<usize, ResamplingError> {
391        // Byte-sourced sampling is uniform without rejection, so the
392        // result is always valid and the error arm is unreachable.
393        Ok(self.sample_bits(bits))
394    }
395}
396
397impl<F, Inner> GrindingChallenger for SerializingChallenger64<F, Inner>
398where
399    F: PrimeField64,
400    Inner: CanSample<u8> + CanObserve<u8> + Clone + Send + Sync,
401{
402    type Witness = F;
403
404    #[instrument(name = "grind for proof-of-work witness", skip_all)]
405    fn grind(&mut self, bits: usize) -> Self::Witness {
406        assert!(bits < 64);
407        assert!((1u64 << bits) < F::ORDER_U64);
408
409        // Trivial case: 0 bits mean no PoW is required and any witness is valid.
410        if bits == 0 {
411            return F::ZERO;
412        }
413
414        let witness = (0..F::ORDER_U64)
415            .into_par_iter()
416            .map(|i| unsafe {
417                // i < F::ORDER_U64 by construction so this is safe.
418                F::from_canonical_unchecked(i)
419            })
420            .find_any(|witness| self.clone().check_witness(bits, *witness))
421            .expect("failed to find witness");
422        assert!(self.check_witness(bits, witness));
423        witness
424    }
425}
426
427impl<F, Inner> FieldChallenger<F> for SerializingChallenger64<F, Inner>
428where
429    F: PrimeField64,
430    Inner: CanSample<u8> + CanObserve<u8> + Clone + Send + Sync,
431{
432}
433
434impl<F, Inner> CanFinalizeDigest for SerializingChallenger32<F, Inner>
435where
436    Inner: CanFinalizeDigest,
437{
438    type Digest = Inner::Digest;
439
440    fn finalize(self) -> Self::Digest {
441        self.inner.finalize()
442    }
443}
444
445impl<F, Inner> CanFinalizeDigest for SerializingChallenger64<F, Inner>
446where
447    Inner: CanFinalizeDigest,
448{
449    type Digest = Inner::Digest;
450
451    fn finalize(self) -> Self::Digest {
452        self.inner.finalize()
453    }
454}
455
456#[cfg(test)]
457mod tests {
458    use alloc::vec;
459
460    use p3_baby_bear::BabyBear;
461    use p3_field::PrimeCharacteristicRing;
462    use p3_goldilocks::Goldilocks;
463    use p3_symmetric::CryptographicHasher;
464
465    use super::*;
466    use crate::HashChallenger;
467
468    /// Toy byte hasher: deterministic length-only fingerprint.
469    ///
470    /// Enough to drive the challenger plumbing without pulling in a real hash crate.
471    #[derive(Clone)]
472    struct ByteCountHasher;
473
474    impl CryptographicHasher<u8, [u8; 32]> for ByteCountHasher {
475        fn hash_iter<I>(&self, input: I) -> [u8; 32]
476        where
477            I: IntoIterator<Item = u8>,
478        {
479            let len = input.into_iter().count() as u8;
480            core::array::from_fn(|i| len.wrapping_add(i as u8))
481        }
482
483        fn hash_iter_slices<'a, I>(&self, input: I) -> [u8; 32]
484        where
485            I: IntoIterator<Item = &'a [u8]>,
486        {
487            let len = input.into_iter().map(<[u8]>::len).sum::<usize>() as u8;
488            core::array::from_fn(|i| len.wrapping_add(i as u8))
489        }
490    }
491
492    type Inner = HashChallenger<u8, ByteCountHasher, 32>;
493
494    #[test]
495    fn test_serializing_challenger32_grind_zero_bits_returns_zero() {
496        // bits == 0: must short-circuit to ZERO without consuming bytes.
497        type F = BabyBear;
498        let inner = Inner::new(vec![0, 1, 2, 3], ByteCountHasher);
499        let mut challenger = SerializingChallenger32::<F, Inner>::new(inner);
500
501        // Pristine shadow: equal next-byte proves no inner mutation.
502        let mut shadow = challenger.clone();
503
504        let witness = challenger.grind(0);
505
506        assert_eq!(witness, F::ZERO);
507        let after_grind: u8 = challenger.inner.sample();
508        let no_grind: u8 = shadow.inner.sample();
509        assert_eq!(after_grind, no_grind);
510    }
511
512    #[test]
513    fn test_serializing_challenger64_grind_zero_bits_returns_zero() {
514        // bits == 0: must short-circuit to ZERO without consuming bytes.
515        type F = Goldilocks;
516        let inner = Inner::new(vec![0, 1, 2, 3], ByteCountHasher);
517        let mut challenger = SerializingChallenger64::<F, Inner>::new(inner);
518
519        // Pristine shadow: equal next-byte proves no inner mutation.
520        let mut shadow = challenger.clone();
521
522        let witness = challenger.grind(0);
523
524        assert_eq!(witness, F::ZERO);
525        let after_grind: u8 = challenger.inner.sample();
526        let no_grind: u8 = shadow.inner.sample();
527        assert_eq!(after_grind, no_grind);
528    }
529
530    #[test]
531    #[should_panic = "requested bit count must fit within the field order"]
532    fn test_serializing_challenger32_sample_bits_rejects_oversized_request() {
533        // BabyBear order is ~2^30.9, so a 32-bit request must be rejected.
534        // The bound is evaluated in u64, so the guard fires in every build profile.
535        type F = BabyBear;
536        let inner = Inner::new(vec![0, 1, 2, 3], ByteCountHasher);
537        let mut challenger = SerializingChallenger32::<F, Inner>::new(inner);
538        let _ = challenger.sample_bits(32);
539    }
540
541    #[test]
542    #[should_panic = "requested bit count must fit within the field order"]
543    fn test_serializing_challenger32_grind_rejects_oversized_request() {
544        // Same guard, reached through the proof-of-work entry point.
545        type F = BabyBear;
546        let inner = Inner::new(vec![0, 1, 2, 3], ByteCountHasher);
547        let mut challenger = SerializingChallenger32::<F, Inner>::new(inner);
548        let _ = challenger.grind(32);
549    }
550}
p3_challenger/serializing_challenger.rs

p3_challenger/
serializing_challenger.rs
