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};
7use p3_util::log2_ceil_u64;
8use tracing::instrument;
9
10use crate::{
11    CanObserve, CanSample, CanSampleBits, FieldChallenger, GrindingChallenger, HashChallenger,
12};
13
14/// Given a challenger that can observe and sample bytes, produces a challenger that is able to
15/// sample and observe field elements of a `PrimeField32`.
16///
17/// **Observing**:
18/// -  Takes a field element will serialize it into a byte array and observe each byte.
19///
20/// **Sampling**:
21/// -  Samples a field element in a prime field of size `p` by sampling uniformly an element in the
22///    range (0..1 << log_2(p)). This avoids modulo bias.
23#[derive(Clone, Debug)]
24pub struct SerializingChallenger32<F, Inner> {
25    inner: Inner,
26    _marker: PhantomData<F>,
27}
28
29/// Given a challenger that can observe and sample bytes, produces a challenger that is able to
30/// sample and observe field elements of a `PrimeField64` field.
31///
32/// **Observing**:
33/// -  Takes a field element will serialize it into a byte array and observe each byte.
34///
35/// **Sampling**:
36/// -  Samples a field element in a prime field of size `p` by sampling uniformly an element in the
37///    range (0..1 << log_2(p)). This avoids modulo bias.
38#[derive(Clone, Debug)]
39pub struct SerializingChallenger64<F, Inner> {
40    inner: Inner,
41    _marker: PhantomData<F>,
42}
43
44impl<F: PrimeField32, Inner: CanObserve<u8>> SerializingChallenger32<F, Inner> {
45    pub const fn new(inner: Inner) -> Self {
46        Self {
47            inner,
48            _marker: PhantomData,
49        }
50    }
51}
52
53impl<F, H> SerializingChallenger32<F, HashChallenger<u8, H, 32>>
54where
55    F: PrimeField32,
56    H: CryptographicHasher<u8, [u8; 32]>,
57{
58    pub const fn from_hasher(initial_state: Vec<u8>, hasher: H) -> Self {
59        Self::new(HashChallenger::new(initial_state, hasher))
60    }
61}
62
63impl<F: PrimeField32, Inner: CanObserve<u8>> CanObserve<F> for SerializingChallenger32<F, Inner> {
64    fn observe(&mut self, value: F) {
65        self.inner
66            .observe_slice(&value.to_unique_u32().to_le_bytes());
67    }
68}
69
70impl<F: PrimeField32, const N: usize, Inner: CanObserve<u8>> CanObserve<Hash<F, u8, N>>
71    for SerializingChallenger32<F, Inner>
72{
73    fn observe(&mut self, values: Hash<F, u8, N>) {
74        for value in values {
75            self.inner.observe(value);
76        }
77    }
78}
79
80impl<F: PrimeField32, const N: usize, Inner: CanObserve<u8>> CanObserve<Hash<F, u64, N>>
81    for SerializingChallenger32<F, Inner>
82{
83    fn observe(&mut self, values: Hash<F, u64, N>) {
84        for value in values {
85            self.inner.observe_slice(&value.to_le_bytes());
86        }
87    }
88}
89
90impl<F, EF, Inner> CanSample<EF> for SerializingChallenger32<F, Inner>
91where
92    F: PrimeField32,
93    EF: BasedVectorSpace<F>,
94    Inner: CanSample<u8>,
95{
96    fn sample(&mut self) -> EF {
97        let modulus = F::ORDER_U32;
98        let log_size = log2_ceil_u64(F::ORDER_U64);
99        // We use u64 to avoid overflow in the case that log_size = 32.
100        let pow_of_two_bound = ((1u64 << log_size) - 1) as u32;
101        // Perform rejection sampling over the uniform range (0..log2_ceil(p))
102        let sample_base = |inner: &mut Inner| loop {
103            let value = u32::from_le_bytes(inner.sample_array());
104            let value = value & pow_of_two_bound;
105            if value < modulus {
106                return unsafe {
107                    // This is safe as value < F::ORDER_U32.
108                    F::from_canonical_unchecked(value)
109                };
110            }
111        };
112        EF::from_basis_coefficients_fn(|_| sample_base(&mut self.inner))
113    }
114}
115
116impl<F, Inner> CanSampleBits<usize> for SerializingChallenger32<F, Inner>
117where
118    F: PrimeField32,
119    Inner: CanSample<u8>,
120{
121    fn sample_bits(&mut self, bits: usize) -> usize {
122        assert!(bits < (usize::BITS as usize));
123        // Limiting the number of bits to the field size
124        assert!((1 << bits) <= F::ORDER_U64 as usize);
125        let rand_usize = u32::from_le_bytes(self.inner.sample_array()) as usize;
126        rand_usize & ((1 << bits) - 1)
127    }
128}
129
130impl<F, Inner> GrindingChallenger for SerializingChallenger32<F, Inner>
131where
132    F: PrimeField32,
133    Inner: CanSample<u8> + CanObserve<u8> + Clone + Send + Sync,
134{
135    type Witness = F;
136
137    #[instrument(name = "grind for proof-of-work witness", skip_all)]
138    fn grind(&mut self, bits: usize) -> Self::Witness {
139        assert!(bits < (usize::BITS as usize));
140        assert!((1 << bits) < F::ORDER_U32);
141        let witness = (0..F::ORDER_U32)
142            .into_par_iter()
143            .map(|i| unsafe {
144                // i < F::ORDER_U32 by construction so this is safe.
145                F::from_canonical_unchecked(i)
146            })
147            .find_any(|witness| self.clone().check_witness(bits, *witness))
148            .expect("failed to find witness");
149        assert!(self.check_witness(bits, witness));
150        witness
151    }
152}
153
154impl<F, Inner> FieldChallenger<F> for SerializingChallenger32<F, Inner>
155where
156    F: PrimeField32,
157    Inner: CanSample<u8> + CanObserve<u8> + Clone + Send + Sync,
158{
159}
160
161impl<F: PrimeField64, Inner: CanObserve<u8>> SerializingChallenger64<F, Inner> {
162    pub const fn new(inner: Inner) -> Self {
163        Self {
164            inner,
165            _marker: PhantomData,
166        }
167    }
168}
169
170impl<F, H> SerializingChallenger64<F, HashChallenger<u8, H, 32>>
171where
172    F: PrimeField64,
173    H: CryptographicHasher<u8, [u8; 32]>,
174{
175    pub const fn from_hasher(initial_state: Vec<u8>, hasher: H) -> Self {
176        Self::new(HashChallenger::new(initial_state, hasher))
177    }
178}
179
180impl<F: PrimeField64, Inner: CanObserve<u8>> CanObserve<F> for SerializingChallenger64<F, Inner> {
181    fn observe(&mut self, value: F) {
182        self.inner
183            .observe_slice(&value.to_unique_u64().to_le_bytes());
184    }
185}
186
187impl<F: PrimeField64, const N: usize, Inner: CanObserve<u8>> CanObserve<Hash<F, u8, N>>
188    for SerializingChallenger64<F, Inner>
189{
190    fn observe(&mut self, values: Hash<F, u8, N>) {
191        for value in values {
192            self.inner.observe(value);
193        }
194    }
195}
196
197impl<F: PrimeField64, const N: usize, Inner: CanObserve<u8>> CanObserve<Hash<F, u64, N>>
198    for SerializingChallenger64<F, Inner>
199{
200    fn observe(&mut self, values: Hash<F, u64, N>) {
201        for value in values {
202            self.inner.observe_slice(&value.to_le_bytes());
203        }
204    }
205}
206
207impl<F, EF, Inner> CanSample<EF> for SerializingChallenger64<F, Inner>
208where
209    F: PrimeField64,
210    EF: BasedVectorSpace<F>,
211    Inner: CanSample<u8>,
212{
213    fn sample(&mut self) -> EF {
214        let modulus = F::ORDER_U64;
215        let log_size = log2_ceil_u64(F::ORDER_U64) as u32;
216        // We use u128 to avoid overflow in the case that log_size = 64.
217        let pow_of_two_bound = ((1u128 << log_size) - 1) as u64;
218
219        // Perform rejection sampling over the uniform range (0..log2_ceil(p))
220        let sample_base = |inner: &mut Inner| loop {
221            let value = u64::from_le_bytes(inner.sample_array());
222            let value = value & pow_of_two_bound;
223            if value < modulus {
224                return unsafe {
225                    // This is safe as value < F::ORDER_U64.
226                    F::from_canonical_unchecked(value)
227                };
228            }
229        };
230        EF::from_basis_coefficients_fn(|_| sample_base(&mut self.inner))
231    }
232}
233
234impl<F, Inner> CanSampleBits<usize> for SerializingChallenger64<F, Inner>
235where
236    F: PrimeField64,
237    Inner: CanSample<u8>,
238{
239    fn sample_bits(&mut self, bits: usize) -> usize {
240        assert!(bits < (usize::BITS as usize));
241        // Limiting the number of bits to the field size
242        assert!((1 << bits) <= F::ORDER_U64 as usize);
243        let rand_usize = u64::from_le_bytes(self.inner.sample_array()) as usize;
244        rand_usize & ((1 << bits) - 1)
245    }
246}
247
248impl<F, Inner> GrindingChallenger for SerializingChallenger64<F, Inner>
249where
250    F: PrimeField64,
251    Inner: CanSample<u8> + CanObserve<u8> + Clone + Send + Sync,
252{
253    type Witness = F;
254
255    #[instrument(name = "grind for proof-of-work witness", skip_all)]
256    fn grind(&mut self, bits: usize) -> Self::Witness {
257        assert!(bits < (usize::BITS as usize));
258        assert!((1 << bits) < F::ORDER_U64);
259        let witness = (0..F::ORDER_U64)
260            .into_par_iter()
261            .map(|i| unsafe {
262                // i < F::ORDER_U64 by construction so this is safe.
263                F::from_canonical_unchecked(i)
264            })
265            .find_any(|witness| self.clone().check_witness(bits, *witness))
266            .expect("failed to find witness");
267        assert!(self.check_witness(bits, witness));
268        witness
269    }
270}
271
272impl<F, Inner> FieldChallenger<F> for SerializingChallenger64<F, Inner>
273where
274    F: PrimeField64,
275    Inner: CanSample<u8> + CanObserve<u8> + Clone + Send + Sync,
276{
277}
p3_challenger/serializing_challenger.rs

p3_challenger/
serializing_challenger.rs
