kimchi/circuits/polynomials/
foreign_field_common.rs

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

kimchi/circuits/polynomials/
foreign_field_common.rs
