midnight_circuits/biguint/
types.rs

1// This file is part of MIDNIGHT-ZK.
2// Copyright (C) Midnight Foundation
3// SPDX-License-Identifier: Apache-2.0
4// Licensed under the Apache License, Version 2.0 (the "License");
5// You may not use this file except in compliance with the License.
6// You may obtain a copy of the License at
7// http://www.apache.org/licenses/LICENSE-2.0
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14use std::cmp::max;
15
16use midnight_proofs::circuit::Value;
17use num_bigint::BigUint;
18use num_traits::{One, Zero};
19
20#[cfg(any(test, feature = "testing"))]
21use crate::testing_utils::Sampleable;
22use crate::{
23    field::foreign::util::{big_from_limbs, big_to_limbs},
24    types::{AssignedNative, InnerConstants, InnerValue},
25    utils::util::big_to_fe,
26    CircuitField,
27};
28
29/// The logarithm of the base of representation `BASE := 2^LOG2_BASE`.
30// This number should be lower than `F::NUM_BITS / 2` over native field `F`.
31// Indeed, it must be lower than that amount with some extra room for
32// "computing". For example, with a 256-bits field, this number is not
33// recommended to exceed 120.
34//
35// In general, a good choice for the value of LOG2_BASE is a multiple of
36// `MAX_BIT_LEN * ZkStdLibArch::nr_pow2range_cols` where the former is the
37// table size of the native_gadget range-checks and the latter the number of
38// columns dedicated to such lookup. Here, we pick a multiple of 8 * 4 = 32.
39pub(crate) const LOG2_BASE: u32 = 96;
40
41/// Type for assigned big unsigned integers, emulated over native field `F`.
42///  - `limbs` is a little-endian vector of assigned native values representing
43///    the big unsigned integer in base `BASE`.
44///
45///    We allow the limbs to be non-normalized, i.e., they do not necessarily
46///    need to be in the range `[0, BASE)`. However, we keep track of an
47///    upper-bound on their size.
48///
49///  - `limb_size_bounds` is a vector (of the same length as `limbs`) containing
50///    an upper-bound on the size the respective limb. That is, `limbs[i]` is
51///    guaranteed to be in `[0, 1 << limb_size_bounds[i])`, for every `i`.
52///
53/// NOTE: Do not implement `AssignmentInstructions` for this type.
54/// `AssignedBigUint`s should be constructed with a known bound on their size.
55/// We provided dedicated methods `assign_biguint` and `assign_fixed_biguint`
56/// for this.
57///
58/// Similarly, do not implement `PublicInputInstructions` for this type.
59/// Use `constrain_as_public_input` instead.
60#[derive(Clone, Debug)]
61#[must_use]
62pub struct AssignedBigUint<F: CircuitField> {
63    pub(crate) limbs: Vec<AssignedNative<F>>,
64    pub(crate) limb_size_bounds: Vec<u32>,
65}
66
67impl<F: CircuitField> InnerValue for AssignedBigUint<F> {
68    type Element = BigUint;
69
70    fn value(&self) -> Value<BigUint> {
71        let base = BigUint::one() << LOG2_BASE;
72        let limbs_as_big = self.limbs.iter().map(|l| l.value().copied().map(|v| v.to_biguint()));
73        let value: Value<Vec<BigUint>> = Value::from_iter(limbs_as_big);
74        value.map(|limbs| big_from_limbs(&base, &limbs))
75    }
76}
77
78impl<F: CircuitField> InnerConstants for AssignedBigUint<F> {
79    fn inner_zero() -> BigUint {
80        BigUint::zero()
81    }
82
83    fn inner_one() -> Self::Element {
84        BigUint::one()
85    }
86}
87
88impl<F: CircuitField> AssignedBigUint<F> {
89    /// This function is the off-circuit analog of
90    /// [crate::biguint::biguint_gadget::BigUintGadget::constrain_as_public_input].
91    pub fn as_public_input(element: &BigUint, nb_bits: u32) -> Vec<F> {
92        biguint_to_limbs(element, Some(nb_bits.div_ceil(LOG2_BASE)))
93    }
94}
95
96impl<F: CircuitField> PartialEq for AssignedBigUint<F> {
97    fn eq(&self, other: &Self) -> bool {
98        // Cell address comparison
99        self.limbs.iter().zip(other.limbs.iter()).all(|(s, o)| s == o)
100    }
101}
102
103#[cfg(any(test, feature = "testing"))]
104pub(crate) const TEST_NB_BITS: u32 = 1024;
105
106#[cfg(any(test, feature = "testing"))]
107impl<F: CircuitField> Sampleable for AssignedBigUint<F> {
108    fn sample_inner(mut rng: impl rand::RngCore) -> BigUint {
109        num_bigint::RandBigInt::gen_biguint(&mut rng, TEST_NB_BITS as u64)
110    }
111}
112
113impl<F: CircuitField> AssignedBigUint<F> {
114    /// Returns an upper-bound on the number of bits necessary to represent the
115    /// given big unsigned integer. Such bound is computed based on the
116    /// `AssignedBigUint` limb size bounds.
117    ///
118    /// This function does not simply return `nb_limbs * LOG2_BASE` because it
119    /// can also deal with big unsigned integers that are not normalized i.e.
120    /// whose bounds are allowed to exceed LOG2_BASE.
121    pub fn nb_bits(&self) -> u32 {
122        self.limb_size_bounds
123            .iter()
124            .rev()
125            .fold(BigUint::zero(), |acc, bound| {
126                (acc << LOG2_BASE) + (BigUint::one() << bound) - BigUint::one()
127            })
128            .bits() as u32
129    }
130
131    /// Returns `true` iff all the limb bounds of this `AssignedBigUint` are
132    /// lower than or equal to LOG2_BASE.
133    pub fn is_normalized(&self) -> bool {
134        self.limb_size_bounds.iter().all(|bound| *bound <= LOG2_BASE)
135    }
136}
137
138/// Given bounds which limit the size of two integers, returns a bound on the
139/// size of their sum. Concretely, it returns the smallest integer `bound` such
140/// that the sum of an integer in the range `[0, 2^bound1)` with an integer in
141/// the range `[0, 2^bound2)` is guaranteed to be in the range `[0, 2^bound)`.
142pub(crate) fn bound_of_addition(bound1: u32, bound2: u32) -> u32 {
143    if bound1 == 0 {
144        return bound2;
145    }
146
147    if bound2 == 0 {
148        return bound1;
149    }
150
151    1 + max(bound1, bound2)
152}
153
154/// Breaks the given BigUint into `nb_limbs` limbs (over the underlying prime
155/// field) representing the value in base 2^LOG2_BASE (in little-endian).
156///
157/// If not provided, `nb_limbs` will default to the minimum number of limbs
158/// necessary to represent the given integer.
159///
160/// If `nb_limbs` is provided, this function will panic if the conversion is not
161/// possible.
162pub(crate) fn biguint_to_limbs<F: CircuitField>(value: &BigUint, nb_limbs: Option<u32>) -> Vec<F> {
163    let nb_limbs = nb_limbs.unwrap_or(value.bits().div_ceil(LOG2_BASE as u64) as u32);
164    big_to_limbs(nb_limbs, &(BigUint::from(1u8) << LOG2_BASE), value)
165        .into_iter()
166        .map(big_to_fe::<F>)
167        .collect()
168}
midnight_circuits/biguint/types.rs

midnight_circuits/biguint/
types.rs
