binius_core/challenger/
isomorphic_challenger.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
// Copyright 2024 Ulvetanna Inc.

use binius_field::{packed::iter_packed_slice, BinaryField, ExtensionField, Field, PackedField};
use p3_challenger::{CanObserve, CanSample, CanSampleBits};
use std::{iter::repeat_with, marker::PhantomData, slice};

/// A wrapper over a challenger that isomorphically converts field elements sampled and observed.
///
/// This implements [`CanSample`] and [`CanObserve`] over the [`Field`] `F2` where the internal
/// challenger needs to sample and observe over the BinaryField `F1` which must be isomorphic to
/// `F2`.
#[derive(Debug)]
pub struct IsomorphicChallenger<F1, Challenger, F2> {
	challenger: Challenger,
	_marker: PhantomData<(F1, F2)>,
}

impl<F1, Challenger, F2> Clone for IsomorphicChallenger<F1, Challenger, F2>
where
	F1: Field,
	Challenger: Clone,
	F2: Field,
{
	fn clone(&self) -> Self {
		Self {
			challenger: self.challenger.clone(),
			_marker: PhantomData,
		}
	}
}

impl<F1, Challenger, F2> IsomorphicChallenger<F1, Challenger, F2>
where
	F1: Field + From<F2> + Into<F2>,
	F2: Field,
{
	pub fn new(challenger: Challenger) -> Self {
		Self {
			challenger,
			_marker: PhantomData,
		}
	}
}

impl<F1, Challenger, F2, PF2> CanObserve<PF2> for IsomorphicChallenger<F1, Challenger, F2>
where
	F1: Field + From<F2> + Into<F2>,
	F2: Field,
	PF2: PackedField<Scalar: ExtensionField<F2>>,
	Challenger: CanObserve<F1>,
{
	fn observe(&mut self, value: PF2) {
		self.observe_slice(slice::from_ref(&value));
	}

	fn observe_slice(&mut self, values: &[PF2]) {
		for packed in iter_packed_slice(values) {
			for base in packed.iter_bases() {
				self.challenger.observe(base.into());
			}
		}
	}
}

impl<F1, Challenger, F2, F2E> CanSample<F2E> for IsomorphicChallenger<F1, Challenger, F2>
where
	F1: Field + From<F2> + Into<F2>,
	F2: Field,
	F2E: ExtensionField<F2>,
	Challenger: CanSample<F1>,
{
	fn sample(&mut self) -> F2E {
		let bases = repeat_with(|| self.challenger.sample().into())
			.take(F2E::DEGREE)
			.collect::<Vec<F2>>();

		F2E::from_bases(&bases).expect("the size of bases is F2E::DEGREE")
	}
}

impl<F1, Challenger, F2> CanSampleBits<usize> for IsomorphicChallenger<F1, Challenger, F2>
where
	F1: BinaryField,
	F2: BinaryField,
	Challenger: CanSampleBits<usize>,
{
	fn sample_bits(&mut self, bits: usize) -> usize {
		self.challenger.sample_bits(bits)
	}
}

#[cfg(test)]
mod test {
	use super::*;
	use crate::challenger::{new_duplex_challenger, new_hasher_challenger};
	use binius_field::{
		AESTowerField32b, AESTowerField8b, BinaryField128b, BinaryField128bPolyval, BinaryField32b,
		BinaryField8b,
	};
	use binius_hash::{Groestl256, GroestlHasher, Vision32bPermutation};
	use rand::thread_rng;
	use std::array;

	#[test]
	fn test_isomorphic_hasher_challenger_sampling() {
		let challenger_over_aes =
			new_hasher_challenger::<AESTowerField8b, Groestl256<AESTowerField8b, _>>();
		let mut challenger_over_bin =
			new_hasher_challenger::<BinaryField8b, GroestlHasher<BinaryField8b>>();
		let mut isomorphic_challenger_over_bin: IsomorphicChallenger<
			AESTowerField32b,
			_,
			BinaryField32b,
		> = IsomorphicChallenger::new(challenger_over_aes);

		for _ in 0..20 {
			let as_b32_1: BinaryField32b = isomorphic_challenger_over_bin.sample();
			let as_b32_2: BinaryField32b = challenger_over_bin.sample();
			assert_eq!(as_b32_1, as_b32_2);
		}

		let mut challenger_over_bin =
			new_hasher_challenger::<BinaryField8b, GroestlHasher<BinaryField8b>>();
		let mut isomorphic_challenger_over_bin: IsomorphicChallenger<
			BinaryField128b,
			_,
			BinaryField128bPolyval,
		> = IsomorphicChallenger::new(challenger_over_bin.clone());

		for _ in 0..20 {
			let as_b128: BinaryField128b = challenger_over_bin.sample();
			let as_polyval128: BinaryField128bPolyval = isomorphic_challenger_over_bin.sample();

			assert_eq!(as_b128, as_polyval128.into());
		}
	}

	#[test]
	fn test_isomorphic_duplex_challenger_sampling_and_observing() {
		let mut challenger_over_bin =
			new_duplex_challenger::<BinaryField32b, Vision32bPermutation, 20, 24>();
		let mut isomorphic_challenger_over_aes: IsomorphicChallenger<
			BinaryField32b,
			_,
			AESTowerField32b,
		> = IsomorphicChallenger::new(challenger_over_bin.clone());

		const N: usize = 20;
		let mut rng = thread_rng();
		let bin32_observations: [BinaryField32b; N] =
			array::from_fn(|_| <BinaryField32b as Field>::random(&mut rng));
		let aes32_observations: [AESTowerField32b; N] =
			array::from_fn(|i| bin32_observations[i].into());

		for i in 0..N {
			isomorphic_challenger_over_aes.observe(aes32_observations[i]);
			challenger_over_bin.observe(bin32_observations[i]);
			let as_b32: BinaryField32b = challenger_over_bin.sample();
			let as_aes32: AESTowerField32b = isomorphic_challenger_over_aes.sample();
			assert_eq!(as_b32, as_aes32.into());
		}
	}

	#[test]
	fn test_isomorphic_hasher_challenger_sampling_and_observing() {
		let mut challenger_over_bin =
			new_hasher_challenger::<BinaryField8b, GroestlHasher<BinaryField8b>>();
		let mut isomorphic_challenger_over_bin: IsomorphicChallenger<
			BinaryField128b,
			_,
			BinaryField128bPolyval,
		> = IsomorphicChallenger::new(challenger_over_bin.clone());

		const N: usize = 20;
		let mut rng = thread_rng();
		let observable: [BinaryField128b; N] =
			array::from_fn(|_| <BinaryField128b as Field>::random(&mut rng));
		let observable_polyval: [BinaryField128bPolyval; N] =
			array::from_fn(|i| observable[i].into());

		for i in 0..20 {
			challenger_over_bin.observe(observable[i]);
			isomorphic_challenger_over_bin.observe(observable_polyval[i]);
			let as_b128: BinaryField128b = challenger_over_bin.sample();
			let as_polyval128: BinaryField128bPolyval = isomorphic_challenger_over_bin.sample();

			assert_eq!(as_b128, as_polyval128.into());
		}

		challenger_over_bin.observe_slice(&observable);
		isomorphic_challenger_over_bin.observe_slice(&observable_polyval);
		let as_b128: BinaryField128b = challenger_over_bin.sample();
		let as_polyval128: BinaryField128bPolyval = isomorphic_challenger_over_bin.sample();
		assert_eq!(as_b128, as_polyval128.into());
	}
}