p3_challenger/
serializing_challenger.rs

Help
1use alloc::vec::Vec;
2use core::marker::PhantomData;
3
4use p3_field::{ExtensionField, 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 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: ExtensionField<F>,
94    Inner: CanSample<u8>,
95{
96    fn sample(&mut self) -> EF {
97        let modulus = F::ORDER_U64 as 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 F::from_canonical_u32(value);
107            }
108        };
109        EF::from_base_fn(|_| sample_base(&mut self.inner))
110    }
111}
112
113impl<F, Inner> CanSampleBits<usize> for SerializingChallenger32<F, Inner>
114where
115    F: PrimeField32,
116    Inner: CanSample<u8>,
117{
118    fn sample_bits(&mut self, bits: usize) -> usize {
119        assert!(bits < (usize::BITS as usize));
120        // Limiting the number of bits to the field size
121        assert!((1 << bits) <= F::ORDER_U64 as usize);
122        let rand_usize = u32::from_le_bytes(self.inner.sample_array()) as usize;
123        rand_usize & ((1 << bits) - 1)
124    }
125}
126
127impl<F, Inner> GrindingChallenger for SerializingChallenger32<F, Inner>
128where
129    F: PrimeField32,
130    Inner: CanSample<u8> + CanObserve<u8> + Clone + Send + Sync,
131{
132    type Witness = F;
133
134    #[instrument(name = "grind for proof-of-work witness", skip_all)]
135    fn grind(&mut self, bits: usize) -> Self::Witness {
136        assert!(bits < (usize::BITS as usize));
137        assert!((1 << bits) < F::ORDER_U64);
138        let witness = (0..F::ORDER_U64)
139            .into_par_iter()
140            .map(|i| F::from_canonical_u64(i))
141            .find_any(|witness| self.clone().check_witness(bits, *witness))
142            .expect("failed to find witness");
143        assert!(self.check_witness(bits, witness));
144        witness
145    }
146}
147
148impl<F, Inner> FieldChallenger<F> for SerializingChallenger32<F, Inner>
149where
150    F: PrimeField32,
151    Inner: CanSample<u8> + CanObserve<u8> + Clone + Send + Sync,
152{
153}
154
155impl<F: PrimeField64, Inner: CanObserve<u8>> SerializingChallenger64<F, Inner> {
156    pub const fn new(inner: Inner) -> Self {
157        Self {
158            inner,
159            _marker: PhantomData,
160        }
161    }
162}
163
164impl<F, H> SerializingChallenger64<F, HashChallenger<u8, H, 32>>
165where
166    F: PrimeField64,
167    H: CryptographicHasher<u8, [u8; 32]>,
168{
169    pub fn from_hasher(initial_state: Vec<u8>, hasher: H) -> Self {
170        Self::new(HashChallenger::new(initial_state, hasher))
171    }
172}
173
174impl<F: PrimeField64, Inner: CanObserve<u8>> CanObserve<F> for SerializingChallenger64<F, Inner> {
175    fn observe(&mut self, value: F) {
176        self.inner
177            .observe_slice(&value.to_unique_u64().to_le_bytes());
178    }
179}
180
181impl<F: PrimeField64, const N: usize, Inner: CanObserve<u8>> CanObserve<Hash<F, u8, N>>
182    for SerializingChallenger64<F, Inner>
183{
184    fn observe(&mut self, values: Hash<F, u8, N>) {
185        for value in values {
186            self.inner.observe(value);
187        }
188    }
189}
190
191impl<F: PrimeField64, const N: usize, Inner: CanObserve<u8>> CanObserve<Hash<F, u64, N>>
192    for SerializingChallenger64<F, Inner>
193{
194    fn observe(&mut self, values: Hash<F, u64, N>) {
195        for value in values {
196            self.inner.observe_slice(&value.to_le_bytes());
197        }
198    }
199}
200
201impl<F, EF, Inner> CanSample<EF> for SerializingChallenger64<F, Inner>
202where
203    F: PrimeField64,
204    EF: ExtensionField<F>,
205    Inner: CanSample<u8>,
206{
207    fn sample(&mut self) -> EF {
208        let modulus = F::ORDER_U64;
209        let log_size = log2_ceil_u64(F::ORDER_U64) as u32;
210        // We use u128 to avoid overflow in the case that log_size = 64.
211        let pow_of_two_bound = ((1u128 << log_size) - 1) as u64;
212
213        // Perform rejection sampling over the uniform range (0..log2_ceil(p))
214        let sample_base = |inner: &mut Inner| loop {
215            let value = u64::from_le_bytes(inner.sample_array());
216            let value = value & pow_of_two_bound;
217            if value < modulus {
218                return F::from_canonical_u64(value);
219            }
220        };
221        EF::from_base_fn(|_| sample_base(&mut self.inner))
222    }
223}
224
225impl<F, Inner> CanSampleBits<usize> for SerializingChallenger64<F, Inner>
226where
227    F: PrimeField64,
228    Inner: CanSample<u8>,
229{
230    fn sample_bits(&mut self, bits: usize) -> usize {
231        assert!(bits < (usize::BITS as usize));
232        // Limiting the number of bits to the field size
233        assert!((1 << bits) <= F::ORDER_U64 as usize);
234        let rand_usize = u64::from_le_bytes(self.inner.sample_array()) as usize;
235        rand_usize & ((1 << bits) - 1)
236    }
237}
238
239impl<F, Inner> GrindingChallenger for SerializingChallenger64<F, Inner>
240where
241    F: PrimeField64,
242    Inner: CanSample<u8> + CanObserve<u8> + Clone + Send + Sync,
243{
244    type Witness = F;
245
246    #[instrument(name = "grind for proof-of-work witness", skip_all)]
247    fn grind(&mut self, bits: usize) -> Self::Witness {
248        assert!(bits < (usize::BITS as usize));
249        assert!((1 << bits) < F::ORDER_U64);
250        let witness = (0..F::ORDER_U64)
251            .into_par_iter()
252            .map(|i| F::from_canonical_u64(i))
253            .find_any(|witness| self.clone().check_witness(bits, *witness))
254            .expect("failed to find witness");
255        assert!(self.check_witness(bits, witness));
256        witness
257    }
258}
259
260impl<F, Inner> FieldChallenger<F> for SerializingChallenger64<F, Inner>
261where
262    F: PrimeField64,
263    Inner: CanSample<u8> + CanObserve<u8> + Clone + Send + Sync,
264{
265}
p3_challenger/serializing_challenger.rs

p3_challenger/
serializing_challenger.rs
