kimchi/circuits/polynomials/
foreign_field_common.rs

1//! Common parameters and functions for kimchi's foreign field circuits.
2
3use o1_utils::{
4    field_helpers::FieldHelpers,
5    foreign_field::{ForeignElement, ForeignFieldHelpers},
6};
7
8use ark_ff::{Field, One, PrimeField, Zero};
9use core::array;
10use num_bigint::BigUint;
11
12/// Index of low limb (in 3-limb foreign elements)
13pub const LO: usize = 0;
14/// Index of middle limb (in 3-limb foreign elements)
15pub const MI: usize = 1;
16/// Index of high limb (in 3-limb foreign elements)
17pub const HI: usize = 2;
18
19/// Limb length for foreign field elements
20pub const LIMB_BITS: usize = 88;
21
22/// Two to the power of the limb length
23pub const TWO_TO_LIMB: u128 = 2u128.pow(LIMB_BITS as u32);
24
25/// Number of desired limbs for foreign field elements
26pub const LIMB_COUNT: usize = 3;
27
28/// Exponent of binary modulus (i.e. t)
29pub const BINARY_MODULUS_EXP: usize = LIMB_BITS * LIMB_COUNT;
30
31pub type KimchiForeignElement<F> = ForeignElement<F, LIMB_BITS, LIMB_COUNT>;
32
33/// Foreign field helpers
34pub trait BigUintForeignFieldHelpers {
35    /// 2
36    fn two() -> Self;
37
38    /// 2^{LIMB_BITS}
39    fn two_to_limb() -> Self;
40
41    /// 2^{2 * LIMB_BITS}
42    fn two_to_2limb() -> Self;
43
44    /// 2^t
45    fn binary_modulus() -> Self;
46
47    /// 2^259 (see foreign field multiplication RFC)
48    fn max_foreign_field_modulus<F: PrimeField>() -> Self;
49
50    /// Convert to 3 limbs of LIMB_BITS each
51    fn to_limbs(&self) -> [BigUint; 3];
52
53    /// Convert to 2 limbs of 2 * LIMB_BITS each. The compressed term is the bottom part
54    fn to_compact_limbs(&self) -> [BigUint; 2];
55
56    /// Convert to 3 PrimeField limbs of LIMB_BITS each
57    fn to_field_limbs<F: Field>(&self) -> [F; 3];
58
59    /// Convert to 2 PrimeField limbs of 2 * LIMB_BITS each. The compressed term is the bottom part.
60    fn to_compact_field_limbs<F: Field>(&self) -> [F; 2];
61
62    /// Negate: 2^T - self
63    fn negate(&self) -> BigUint;
64}
65
66// @volhovm can we remove this?
67// /// Two to the power of the limb length
68// pub fn two_to_limb() -> BigUint {
69//     BigUint::from(TWO_TO_LIMB)
70// }
71
72impl BigUintForeignFieldHelpers for BigUint {
73    fn two() -> Self {
74        Self::from(2u32)
75    }
76
77    fn two_to_limb() -> Self {
78        BigUint::two().pow(LIMB_BITS as u32)
79    }
80
81    fn two_to_2limb() -> Self {
82        BigUint::two().pow(2 * LIMB_BITS as u32)
83    }
84
85    fn binary_modulus() -> Self {
86        BigUint::two().pow(3 * LIMB_BITS as u32)
87    }
88
89    fn max_foreign_field_modulus<F: PrimeField>() -> Self {
90        // For simplicity and efficiency we use the approximation m = 2^259 - 1
91        BigUint::two().pow(259) - BigUint::one()
92    }
93
94    fn to_limbs(&self) -> [Self; 3] {
95        let mut limbs = biguint_to_limbs(self, LIMB_BITS);
96        assert!(limbs.len() <= 3);
97        limbs.resize(3, BigUint::zero());
98
99        array::from_fn(|i| limbs[i].clone())
100    }
101
102    fn to_compact_limbs(&self) -> [Self; 2] {
103        let mut limbs = biguint_to_limbs(self, 2 * LIMB_BITS);
104        assert!(limbs.len() <= 2);
105        limbs.resize(2, BigUint::zero());
106
107        array::from_fn(|i| limbs[i].clone())
108    }
109
110    fn to_field_limbs<F: Field>(&self) -> [F; 3] {
111        self.to_limbs().to_field_limbs()
112    }
113
114    fn to_compact_field_limbs<F: Field>(&self) -> [F; 2] {
115        self.to_compact_limbs().to_field_limbs()
116    }
117
118    fn negate(&self) -> BigUint {
119        assert!(*self < BigUint::binary_modulus());
120        let neg_self = BigUint::binary_modulus() - self;
121        assert_eq!(neg_self.bits(), BINARY_MODULUS_EXP as u64);
122        neg_self
123    }
124}
125
126/// PrimeField array BigUint helpers
127pub trait FieldArrayBigUintHelpers<F: PrimeField, const N: usize> {
128    /// Convert limbs from field elements to BigUint
129    fn to_limbs(&self) -> [BigUint; N];
130
131    /// Alias for to_limbs
132    fn to_biguints(&self) -> [BigUint; N] {
133        self.to_limbs()
134    }
135}
136
137impl<F: PrimeField, const N: usize> FieldArrayBigUintHelpers<F, N> for [F; N] {
138    fn to_limbs(&self) -> [BigUint; N] {
139        array::from_fn(|i| self[i].to_biguint())
140    }
141}
142
143/// PrimeField array compose BigUint
144pub trait FieldArrayCompose<F: PrimeField, const N: usize> {
145    /// Compose field limbs into BigUint
146    fn compose(&self) -> BigUint;
147}
148
149impl<F: PrimeField> FieldArrayCompose<F, 2> for [F; 2] {
150    fn compose(&self) -> BigUint {
151        fields_compose(self, &BigUint::two_to_2limb())
152    }
153}
154
155impl<F: PrimeField> FieldArrayCompose<F, 3> for [F; 3] {
156    fn compose(&self) -> BigUint {
157        fields_compose(self, &BigUint::two_to_limb())
158    }
159}
160
161/// PrimeField array compact limbs
162pub trait FieldArrayCompact<F: PrimeField> {
163    /// Compose field limbs into BigUint
164    fn to_compact_limbs(&self) -> [F; 2];
165}
166
167impl<F: PrimeField> FieldArrayCompact<F> for [F; 3] {
168    fn to_compact_limbs(&self) -> [F; 2] {
169        [
170            self[0] + KimchiForeignElement::<F>::two_to_limb() * self[1],
171            self[2],
172        ]
173    }
174}
175
176/// BigUint array PrimeField helpers
177pub trait BigUintArrayFieldHelpers<const N: usize> {
178    /// Convert limbs from BigUint to field element
179    fn to_field_limbs<F: Field>(&self) -> [F; N];
180
181    /// Alias for to_field_limbs
182    fn to_fields<F: Field>(&self) -> [F; N] {
183        self.to_field_limbs()
184    }
185}
186
187impl<const N: usize> BigUintArrayFieldHelpers<N> for [BigUint; N] {
188    fn to_field_limbs<F: Field>(&self) -> [F; N] {
189        biguints_to_fields(self)
190    }
191}
192
193/// BigUint array compose helper
194pub trait BigUintArrayCompose<const N: usize> {
195    /// Compose limbs into BigUint
196    fn compose(&self) -> BigUint;
197}
198
199impl BigUintArrayCompose<2> for [BigUint; 2] {
200    fn compose(&self) -> BigUint {
201        bigunits_compose(self, &BigUint::two_to_2limb())
202    }
203}
204
205impl BigUintArrayCompose<3> for [BigUint; 3] {
206    fn compose(&self) -> BigUint {
207        bigunits_compose(self, &BigUint::two_to_limb())
208    }
209}
210
211// Compose field limbs into BigUint value
212fn fields_compose<F: PrimeField, const N: usize>(limbs: &[F; N], base: &BigUint) -> BigUint {
213    limbs
214        .iter()
215        .cloned()
216        .enumerate()
217        .fold(BigUint::zero(), |x, (i, limb)| {
218            x + base.pow(i as u32) * limb.to_biguint()
219        })
220}
221
222// Convert array of BigUint to an array of PrimeField
223fn biguints_to_fields<F: Field, const N: usize>(limbs: &[BigUint; N]) -> [F; N] {
224    array::from_fn(|i| {
225        F::from_random_bytes(&limbs[i].to_bytes_le())
226            .expect("failed to convert BigUint to field element")
227    })
228}
229
230// Compose limbs into BigUint value
231fn bigunits_compose<const N: usize>(limbs: &[BigUint; N], base: &BigUint) -> BigUint {
232    limbs
233        .iter()
234        .cloned()
235        .enumerate()
236        .fold(BigUint::zero(), |x, (i, limb)| {
237            x + base.pow(i as u32) * limb
238        })
239}
240
241// Split a BigUint up into limbs of size limb_size (in little-endian order)
242fn biguint_to_limbs(x: &BigUint, limb_bits: usize) -> Vec<BigUint> {
243    let bytes = x.to_bytes_le();
244    let chunks: Vec<&[u8]> = bytes.chunks(limb_bits / 8).collect();
245    chunks
246        .iter()
247        .map(|chunk| BigUint::from_bytes_le(chunk))
248        .collect()
249}
250
251#[cfg(test)]
252mod tests {
253    use super::*;
254
255    use ark_ec::AffineRepr;
256    use ark_ff::One;
257    use mina_curves::pasta::Pallas as CurvePoint;
258    use num_bigint::RandBigInt;
259
260    /// Base field element type
261    pub type BaseField = <CurvePoint as AffineRepr>::BaseField;
262
263    fn secp256k1_modulus() -> BigUint {
264        BigUint::from_bytes_be(&secp256k1::constants::FIELD_SIZE)
265    }
266
267    #[test]
268    fn test_negate_modulus_safe1() {
269        secp256k1_modulus().negate();
270    }
271
272    #[test]
273    fn test_negate_modulus_safe2() {
274        BigUint::binary_modulus().sqrt().negate();
275    }
276
277    #[test]
278    fn test_negate_modulus_safe3() {
279        (BigUint::binary_modulus() / BigUint::from(2u32)).negate();
280    }
281
282    #[test]
283    #[should_panic]
284    fn test_negate_modulus_unsafe1() {
285        (BigUint::binary_modulus() - BigUint::one()).negate();
286    }
287
288    #[test]
289    #[should_panic]
290    fn test_negate_modulus_unsafe2() {
291        (BigUint::binary_modulus() + BigUint::one()).negate();
292    }
293
294    #[test]
295    #[should_panic]
296    fn test_negate_modulus_unsafe3() {
297        BigUint::binary_modulus().negate();
298    }
299
300    #[test]
301    fn check_negation() {
302        let mut rng = o1_utils::tests::make_test_rng(None);
303        for _ in 0..10 {
304            rng.gen_biguint(256).negate();
305        }
306    }
307
308    #[test]
309    fn check_good_limbs() {
310        let mut rng = o1_utils::tests::make_test_rng(None);
311        for _ in 0..100 {
312            let x = rng.gen_biguint(264);
313            assert_eq!(x.to_limbs().len(), 3);
314            assert_eq!(x.to_limbs().compose(), x);
315            assert_eq!(x.to_compact_limbs().len(), 2);
316            assert_eq!(x.to_compact_limbs().compose(), x);
317            assert_eq!(x.to_compact_limbs().compose(), x.to_limbs().compose());
318
319            assert_eq!(x.to_field_limbs::<BaseField>().len(), 3);
320            assert_eq!(x.to_field_limbs::<BaseField>().compose(), x);
321            assert_eq!(x.to_compact_field_limbs::<BaseField>().len(), 2);
322            assert_eq!(x.to_compact_field_limbs::<BaseField>().compose(), x);
323            assert_eq!(
324                x.to_compact_field_limbs::<BaseField>().compose(),
325                x.to_field_limbs::<BaseField>().compose()
326            );
327
328            assert_eq!(x.to_limbs().to_fields::<BaseField>(), x.to_field_limbs());
329            assert_eq!(x.to_field_limbs::<BaseField>().to_biguints(), x.to_limbs());
330        }
331    }
332
333    #[test]
334    #[should_panic]
335    fn check_bad_limbs_1() {
336        let mut rng = o1_utils::tests::make_test_rng(None);
337        assert_ne!(rng.gen_biguint(265).to_limbs().len(), 3);
338    }
339
340    #[test]
341    #[should_panic]
342    fn check_bad_limbs_2() {
343        let mut rng = o1_utils::tests::make_test_rng(None);
344        assert_ne!(rng.gen_biguint(265).to_compact_limbs().len(), 2);
345    }
346
347    #[test]
348    #[should_panic]
349    fn check_bad_limbs_3() {
350        let mut rng = o1_utils::tests::make_test_rng(None);
351        assert_ne!(rng.gen_biguint(265).to_field_limbs::<BaseField>().len(), 3);
352    }
353
354    #[test]
355    #[should_panic]
356    fn check_bad_limbs_4() {
357        let mut rng = o1_utils::tests::make_test_rng(None);
358        assert_ne!(
359            rng.gen_biguint(265)
360                .to_compact_field_limbs::<BaseField>()
361                .len(),
362            2
363        );
364    }
365}
kimchi/circuits/polynomials/foreign_field_common.rs

kimchi/circuits/polynomials/
foreign_field_common.rs
