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, FieldChallenger, GrindingChallenger,
12    HashChallenger,
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        // Limiting the number of bits to the field size
165        assert!((1 << bits) <= F::ORDER_U64 as usize);
166        let rand_usize = u32::from_le_bytes(self.inner.sample_array()) as usize;
167        rand_usize & ((1 << bits) - 1)
168    }
169}
170
171impl<F, Inner> GrindingChallenger for SerializingChallenger32<F, Inner>
172where
173    F: PrimeField32,
174    Inner: CanSample<u8> + CanObserve<u8> + Clone + Send + Sync,
175{
176    type Witness = F;
177
178    #[instrument(name = "grind for proof-of-work witness", skip_all)]
179    fn grind(&mut self, bits: usize) -> Self::Witness {
180        assert!(bits < (usize::BITS as usize));
181        assert!((1 << bits) < F::ORDER_U32);
182        let witness = (0..F::ORDER_U32)
183            .into_par_iter()
184            .map(|i| unsafe {
185                // i < F::ORDER_U32 by construction so this is safe.
186                F::from_canonical_unchecked(i)
187            })
188            .find_any(|witness| self.clone().check_witness(bits, *witness))
189            .expect("failed to find witness");
190        assert!(self.check_witness(bits, witness));
191        witness
192    }
193}
194
195impl<F, Inner> FieldChallenger<F> for SerializingChallenger32<F, Inner>
196where
197    F: PrimeField32,
198    Inner: CanSample<u8> + CanObserve<u8> + Clone + Send + Sync,
199{
200}
201
202impl<F: PrimeField64, Inner: CanObserve<u8>> SerializingChallenger64<F, Inner> {
203    pub const fn new(inner: Inner) -> Self {
204        Self {
205            inner,
206            _marker: PhantomData,
207        }
208    }
209}
210
211impl<F, H> SerializingChallenger64<F, HashChallenger<u8, H, 32>>
212where
213    F: PrimeField64,
214    H: CryptographicHasher<u8, [u8; 32]>,
215{
216    pub const fn from_hasher(initial_state: Vec<u8>, hasher: H) -> Self {
217        Self::new(HashChallenger::new(initial_state, hasher))
218    }
219}
220
221impl<F: PrimeField64, Inner: CanObserve<u8>> CanObserve<F> for SerializingChallenger64<F, Inner> {
222    fn observe(&mut self, value: F) {
223        self.inner
224            .observe_slice(&value.to_unique_u64().to_le_bytes());
225    }
226}
227
228impl<F: PrimeField64, const N: usize, Inner: CanObserve<u8>> CanObserve<Hash<F, u8, N>>
229    for SerializingChallenger64<F, Inner>
230{
231    fn observe(&mut self, values: Hash<F, u8, N>) {
232        for value in values {
233            self.inner.observe(value);
234        }
235    }
236}
237
238impl<F: PrimeField64, const N: usize, Inner: CanObserve<u8>> CanObserve<Hash<F, u64, N>>
239    for SerializingChallenger64<F, Inner>
240{
241    fn observe(&mut self, values: Hash<F, u64, N>) {
242        for value in values {
243            self.inner.observe_slice(&value.to_le_bytes());
244        }
245    }
246}
247
248impl<F: PrimeField64, const N: usize, Inner: CanObserve<u8>> CanObserve<&MerkleCap<F, [u8; N]>>
249    for SerializingChallenger64<F, Inner>
250{
251    fn observe(&mut self, cap: &MerkleCap<F, [u8; N]>) {
252        for digest in cap.roots() {
253            for value in digest {
254                self.inner.observe(*value);
255            }
256        }
257    }
258}
259
260impl<F: PrimeField64, const N: usize, Inner: CanObserve<u8>> CanObserve<MerkleCap<F, [u8; N]>>
261    for SerializingChallenger64<F, Inner>
262{
263    fn observe(&mut self, cap: MerkleCap<F, [u8; N]>) {
264        self.observe(&cap);
265    }
266}
267
268impl<F: PrimeField64, const N: usize, Inner: CanObserve<u8>> CanObserve<&MerkleCap<F, [u64; N]>>
269    for SerializingChallenger64<F, Inner>
270{
271    fn observe(&mut self, cap: &MerkleCap<F, [u64; N]>) {
272        for digest in cap.roots() {
273            for value in digest {
274                self.inner.observe_slice(&value.to_le_bytes());
275            }
276        }
277    }
278}
279
280impl<F: PrimeField64, const N: usize, Inner: CanObserve<u8>> CanObserve<MerkleCap<F, [u64; N]>>
281    for SerializingChallenger64<F, Inner>
282{
283    fn observe(&mut self, cap: MerkleCap<F, [u64; N]>) {
284        self.observe(&cap);
285    }
286}
287
288impl<F, EF, Inner> CanSample<EF> for SerializingChallenger64<F, Inner>
289where
290    F: PrimeField64,
291    EF: BasedVectorSpace<F>,
292    Inner: CanSample<u8>,
293{
294    fn sample(&mut self) -> EF {
295        let modulus = F::ORDER_U64;
296        let log_size = log2_ceil_u64(F::ORDER_U64) as u32;
297        // We use u128 to avoid overflow in the case that log_size = 64.
298        let pow_of_two_bound = ((1u128 << log_size) - 1) as u64;
299
300        // Perform rejection sampling over the uniform range (0..log2_ceil(p))
301        let sample_base = |inner: &mut Inner| loop {
302            let value = u64::from_le_bytes(inner.sample_array());
303            let value = value & pow_of_two_bound;
304            if value < modulus {
305                return unsafe {
306                    // This is safe as value < F::ORDER_U64.
307                    F::from_canonical_unchecked(value)
308                };
309            }
310        };
311        EF::from_basis_coefficients_fn(|_| sample_base(&mut self.inner))
312    }
313}
314
315impl<F, Inner> CanSampleBits<usize> for SerializingChallenger64<F, Inner>
316where
317    F: PrimeField64,
318    Inner: CanSample<u8>,
319{
320    fn sample_bits(&mut self, bits: usize) -> usize {
321        assert!(bits < (usize::BITS as usize));
322        assert!((1u64 << bits) <= F::ORDER_U64);
323        let rand_u64 = u64::from_le_bytes(self.inner.sample_array());
324        (rand_u64 & ((1u64 << bits) - 1)) as usize
325    }
326}
327
328impl<F, Inner> GrindingChallenger for SerializingChallenger64<F, Inner>
329where
330    F: PrimeField64,
331    Inner: CanSample<u8> + CanObserve<u8> + Clone + Send + Sync,
332{
333    type Witness = F;
334
335    #[instrument(name = "grind for proof-of-work witness", skip_all)]
336    fn grind(&mut self, bits: usize) -> Self::Witness {
337        assert!(bits < 64);
338        assert!((1u64 << bits) < F::ORDER_U64);
339        let witness = (0..F::ORDER_U64)
340            .into_par_iter()
341            .map(|i| unsafe {
342                // i < F::ORDER_U64 by construction so this is safe.
343                F::from_canonical_unchecked(i)
344            })
345            .find_any(|witness| self.clone().check_witness(bits, *witness))
346            .expect("failed to find witness");
347        assert!(self.check_witness(bits, witness));
348        witness
349    }
350}
351
352impl<F, Inner> FieldChallenger<F> for SerializingChallenger64<F, Inner>
353where
354    F: PrimeField64,
355    Inner: CanSample<u8> + CanObserve<u8> + Clone + Send + Sync,
356{
357}
358
359impl<F, Inner> CanFinalizeDigest for SerializingChallenger32<F, Inner>
360where
361    Inner: CanFinalizeDigest,
362{
363    type Digest = Inner::Digest;
364
365    fn finalize(self) -> Self::Digest {
366        self.inner.finalize()
367    }
368}
369
370impl<F, Inner> CanFinalizeDigest for SerializingChallenger64<F, Inner>
371where
372    Inner: CanFinalizeDigest,
373{
374    type Digest = Inner::Digest;
375
376    fn finalize(self) -> Self::Digest {
377        self.inner.finalize()
378    }
379}
p3_challenger/serializing_challenger.rs

p3_challenger/
serializing_challenger.rs
