halo2_ecc/bigint/
mod.rs

Help
1use halo2_base::{
2    gates::flex_gate::GateInstructions,
3    utils::{biguint_to_fe, decompose_biguint, fe_to_biguint, BigPrimeField, ScalarField},
4    AssignedValue, Context,
5    QuantumCell::Constant,
6};
7use num_bigint::{BigInt, BigUint};
8use num_traits::Zero;
9
10pub mod add_no_carry;
11pub mod big_is_equal;
12pub mod big_is_zero;
13pub mod big_less_than;
14pub mod carry_mod;
15pub mod check_carry_mod_to_zero;
16pub mod check_carry_to_zero;
17pub mod mul_no_carry;
18pub mod negative;
19pub mod scalar_mul_and_add_no_carry;
20pub mod scalar_mul_no_carry;
21pub mod select;
22pub mod select_by_indicator;
23pub mod sub;
24pub mod sub_no_carry;
25
26#[derive(Clone, Debug, PartialEq, Default)]
27pub enum BigIntStrategy {
28    // use existing gates
29    #[default]
30    Simple,
31    // vertical custom gates of length 4 for dot product between an unknown vector and a constant vector, both of length 3
32    // we restrict to gate of length 4 since this uses the same set of evaluation points Rotation(0..=3) as our simple gate
33    // CustomVerticalShort,
34}
35
36#[derive(Clone, Debug)]
37pub struct OverflowInteger<F: ScalarField> {
38    pub limbs: Vec<AssignedValue<F>>,
39    // max bits of a limb, ignoring sign
40    pub max_limb_bits: usize,
41    // the standard limb bit that we use for pow of two limb base - to reduce overhead we just assume this is inferred from context (e.g., the chip stores it), so we stop storing it here
42    // pub limb_bits: usize,
43}
44
45impl<F: ScalarField> OverflowInteger<F> {
46    pub fn new(limbs: Vec<AssignedValue<F>>, max_limb_bits: usize) -> Self {
47        Self { limbs, max_limb_bits }
48    }
49
50    // convenience function for testing
51    #[cfg(test)]
52    pub fn to_bigint(&self, limb_bits: usize) -> BigInt
53    where
54        F: BigPrimeField,
55    {
56        use halo2_base::utils::fe_to_bigint;
57
58        self.limbs
59            .iter()
60            .rev()
61            .fold(BigInt::zero(), |acc, acell| (acc << limb_bits) + fe_to_bigint(acell.value()))
62    }
63
64    /// Computes `sum_i limbs[i] * limb_bases[i]` in native field `F`.
65    /// In practice assumes `limb_bases[i] = 2^{limb_bits * i}`.
66    pub fn evaluate_native(
67        ctx: &mut Context<F>,
68        gate: &impl GateInstructions<F>,
69        limbs: impl IntoIterator<Item = AssignedValue<F>>,
70        limb_bases: &[F],
71    ) -> AssignedValue<F> {
72        // Constrain `out_native = sum_i out_assigned[i] * 2^{n*i}` in `F`
73        gate.inner_product(ctx, limbs, limb_bases.iter().map(|c| Constant(*c)))
74    }
75}
76
77/// Safe wrapper around a BigUint represented as a vector of limbs in **little endian**.
78/// The underlying BigUint is represented by
79/// sum<sub>i</sub> limbs\[i\] * 2<sup>limb_bits * i</sup>
80///
81/// To save memory we do not store the `limb_bits` and it must be inferred from context.
82#[repr(transparent)]
83#[derive(Clone, Debug)]
84pub struct ProperUint<F: ScalarField>(pub(crate) Vec<AssignedValue<F>>);
85
86impl<F: ScalarField> ProperUint<F> {
87    pub fn limbs(&self) -> &[AssignedValue<F>] {
88        self.0.as_slice()
89    }
90
91    pub fn into_overflow(self, limb_bits: usize) -> OverflowInteger<F> {
92        OverflowInteger::new(self.0, limb_bits)
93    }
94
95    /// Computes `sum_i limbs[i] * limb_bases[i]` in native field `F`.
96    /// In practice assumes `limb_bases[i] = 2^{limb_bits * i}`.
97    ///
98    /// Assumes that `value` is the underlying BigUint value represented by `self`.
99    pub fn into_crt(
100        self,
101        ctx: &mut Context<F>,
102        gate: &impl GateInstructions<F>,
103        value: BigUint,
104        limb_bases: &[F],
105        limb_bits: usize,
106    ) -> ProperCrtUint<F> {
107        // Constrain `out_native = sum_i out_assigned[i] * 2^{n*i}` in `F`
108        let native =
109            OverflowInteger::evaluate_native(ctx, gate, self.0.iter().copied(), limb_bases);
110        ProperCrtUint(CRTInteger::new(self.into_overflow(limb_bits), native, value.into()))
111    }
112}
113
114#[repr(transparent)]
115#[derive(Clone, Debug)]
116pub struct FixedOverflowInteger<F: ScalarField> {
117    pub limbs: Vec<F>,
118}
119
120impl<F: BigPrimeField> FixedOverflowInteger<F> {
121    pub fn construct(limbs: Vec<F>) -> Self {
122        Self { limbs }
123    }
124
125    /// Input: a BigInteger `value`, Output: the `FixedOverflowInteger` that represents the same value
126    /// Can handle signs
127    /// Note the representation of the integer will be in proper (no overflow) format, if signs are interpretted correctly
128    pub fn from_native(value: &BigUint, num_limbs: usize, limb_bits: usize) -> Self {
129        let limbs = decompose_biguint(value, num_limbs, limb_bits);
130        Self { limbs }
131    }
132
133    pub fn to_bigint(&self, limb_bits: usize) -> BigUint {
134        self.limbs
135            .iter()
136            .rev()
137            .fold(BigUint::zero(), |acc, x| (acc << limb_bits) + fe_to_biguint(x))
138    }
139
140    pub fn assign(self, ctx: &mut Context<F>) -> ProperUint<F> {
141        let assigned_limbs = self.limbs.into_iter().map(|limb| ctx.load_constant(limb)).collect();
142        ProperUint(assigned_limbs)
143    }
144
145    /// only use case is when coeffs has only a single 1, rest are 0
146    pub fn select_by_indicator(
147        gate: &impl GateInstructions<F>,
148        ctx: &mut Context<F>,
149        a: &[Self],
150        coeffs: &[AssignedValue<F>],
151        limb_bits: usize,
152    ) -> OverflowInteger<F> {
153        let k = a[0].limbs.len();
154
155        let out_limbs = (0..k)
156            .map(|idx| {
157                let int_limbs = a.iter().map(|a| Constant(a.limbs[idx]));
158                gate.select_by_indicator(ctx, int_limbs, coeffs.iter().copied())
159            })
160            .collect();
161
162        OverflowInteger::new(out_limbs, limb_bits)
163    }
164}
165
166#[derive(Clone, Debug)]
167pub struct CRTInteger<F: ScalarField> {
168    // keep track of an integer `a` using CRT as `a mod 2^t` and `a mod n`
169    // where `t = truncation.limbs.len() * truncation.limb_bits`
170    //       `n = modulus::<F>`
171    // `value` is the actual integer value we want to keep track of
172
173    // we allow `value` to be a signed BigInt
174    // however `value` is really an element of Z/(2^t * n), so signs are only meaningful if:
175    // ASSUME `abs(value) < 2^t * n / 2`
176
177    // the IMPLICIT ASSUMPTION: `value (mod 2^t) = truncation` && `value (mod n) = native`
178    // this struct should only be used if the implicit assumption above is satisfied
179    pub truncation: OverflowInteger<F>,
180    pub native: AssignedValue<F>,
181    pub value: BigInt,
182}
183
184impl<F: ScalarField> AsRef<CRTInteger<F>> for CRTInteger<F> {
185    fn as_ref(&self) -> &CRTInteger<F> {
186        self
187    }
188}
189
190// Cloning all the time impacts readability so we'll just implement From<&T> for T
191impl<'a, F: ScalarField> From<&'a CRTInteger<F>> for CRTInteger<F> {
192    fn from(x: &'a CRTInteger<F>) -> Self {
193        x.clone()
194    }
195}
196
197impl<F: ScalarField> CRTInteger<F> {
198    pub fn new(truncation: OverflowInteger<F>, native: AssignedValue<F>, value: BigInt) -> Self {
199        Self { truncation, native, value }
200    }
201
202    pub fn native(&self) -> &AssignedValue<F> {
203        &self.native
204    }
205
206    pub fn limbs(&self) -> &[AssignedValue<F>] {
207        self.truncation.limbs.as_slice()
208    }
209}
210
211/// Safe wrapper for representing a BigUint as a [`CRTInteger`] whose underlying BigUint value is in `[0, 2^t)`
212/// where `t = truncation.limbs.len() * limb_bits`. This struct guarantees that
213/// * each `truncation.limbs[i]` is ranged checked to be in `[0, 2^limb_bits)`,
214/// * `native` is the evaluation of `sum_i truncation.limbs[i] * 2^{limb_bits * i} (mod modulus::<F>)` in the native field `F`
215/// * `value` is equal to `sum_i truncation.limbs[i] * 2^{limb_bits * i}` as integers
216///
217/// Note this means `native` and `value` are completely determined by `truncation`. However, we still store them explicitly for convenience.
218#[repr(transparent)]
219#[derive(Clone, Debug)]
220pub struct ProperCrtUint<F: ScalarField>(pub(crate) CRTInteger<F>);
221
222impl<F: ScalarField> AsRef<CRTInteger<F>> for ProperCrtUint<F> {
223    fn as_ref(&self) -> &CRTInteger<F> {
224        &self.0
225    }
226}
227
228impl<'a, F: ScalarField> From<&'a ProperCrtUint<F>> for ProperCrtUint<F> {
229    fn from(x: &'a ProperCrtUint<F>) -> Self {
230        x.clone()
231    }
232}
233
234// cannot blanket implement From<Proper<T>> for T because of Rust
235impl<F: ScalarField> From<ProperCrtUint<F>> for CRTInteger<F> {
236    fn from(x: ProperCrtUint<F>) -> Self {
237        x.0
238    }
239}
240
241impl<'a, F: ScalarField> From<&'a ProperCrtUint<F>> for CRTInteger<F> {
242    fn from(x: &'a ProperCrtUint<F>) -> Self {
243        x.0.clone()
244    }
245}
246
247impl<F: ScalarField> From<ProperCrtUint<F>> for ProperUint<F> {
248    fn from(x: ProperCrtUint<F>) -> Self {
249        ProperUint(x.0.truncation.limbs)
250    }
251}
252
253impl<F: ScalarField> ProperCrtUint<F> {
254    pub fn limbs(&self) -> &[AssignedValue<F>] {
255        self.0.limbs()
256    }
257
258    pub fn native(&self) -> &AssignedValue<F> {
259        self.0.native()
260    }
261
262    pub fn value(&self) -> BigUint {
263        self.0.value.to_biguint().expect("Value of proper uint should not be negative")
264    }
265}
266
267#[derive(Clone, Debug)]
268pub struct FixedCRTInteger<F: ScalarField> {
269    // keep track of an integer `a` using CRT as `a mod 2^t` and `a mod n`
270    // where `t = truncation.limbs.len() * truncation.limb_bits`
271    //       `n = modulus::<Fn>`
272    // `value` is the actual integer value we want to keep track of
273
274    // we allow `value` to be a signed BigInt
275    // however `value` is really an element of Z/(2^t * n), so signs are only meaningful if:
276    // ASSUME `abs(value) < 2^t * n / 2`
277
278    // the IMPLICIT ASSUMPTION: `value (mod 2^t) = truncation` && `value (mod n) = native`
279    // this struct should only be used if the implicit assumption above is satisfied
280    pub truncation: FixedOverflowInteger<F>,
281    pub value: BigUint,
282}
283
284impl<F: BigPrimeField> FixedCRTInteger<F> {
285    pub fn new(truncation: FixedOverflowInteger<F>, value: BigUint) -> Self {
286        Self { truncation, value }
287    }
288
289    /// Input: a BigInteger `value`, Output: the `FixedCRTInteger` that represents the same value
290    /// Can handle signs
291    pub fn from_native(value: BigUint, num_limbs: usize, limb_bits: usize) -> Self {
292        let truncation = FixedOverflowInteger::from_native(&value, num_limbs, limb_bits);
293        Self { truncation, value }
294    }
295
296    pub fn assign(
297        self,
298        ctx: &mut Context<F>,
299        limb_bits: usize,
300        native_modulus: &BigUint,
301    ) -> ProperCrtUint<F> {
302        let assigned_truncation = self.truncation.assign(ctx).into_overflow(limb_bits);
303        let assigned_native = ctx.load_constant(biguint_to_fe(&(&self.value % native_modulus)));
304        ProperCrtUint(CRTInteger::new(assigned_truncation, assigned_native, self.value.into()))
305    }
306}
halo2_ecc/bigint/mod.rs

halo2_ecc/bigint/
mod.rs
