1//!
  2//! ## Overview
  3//!
  4//! This module implements a field gadget for a prime field `Fp` over another prime field `Fq` where `p != q`.
  5//!
  6//! When writing constraint systems for many cryptographic proofs, we are restricted to a native field (e.g., the scalar field of the pairing-friendly curve).
  7//! This can be inconvenient; for example, the recursive composition of proofs via cycles of curves requires the verifier to compute over a non-native field.
  8//!
  9//! The library makes it possible to write computations over a non-native field in the same way one would write computations over the native field. This naturally introduces additional overhead, which we minimize using a variety of optimizations. (Nevertheless, the overhead is still substantial, and native fields should be used where possible.)
 10//!
 11//! ## Usage
 12//!
 13//! Because [`NonNativeFieldVar`] implements the [`FieldVar`] trait in arkworks, we can treat it like a native field variable ([`FpVar`]).
 14//!
 15//! We can do the standard field operations, such as `+`, `-`, and `*`. See the following example:
 16//!
 17//! ```rust
 18//! # fn main() -> Result<(), ark_relations::r1cs::SynthesisError> {
 19//! # use ark_std::UniformRand;
 20//! # use ark_relations::{ns, r1cs::ConstraintSystem};
 21//! # use ark_r1cs_std::prelude::*;
 22//! use ark_r1cs_std::fields::nonnative::NonNativeFieldVar;
 23//! use ark_bls12_377::{Fr, Fq};
 24//!
 25//! # let mut rng = ark_std::test_rng();
 26//! # let a_value = Fr::rand(&mut rng);
 27//! # let b_value = Fr::rand(&mut rng);
 28//! # let cs = ConstraintSystem::<Fq>::new_ref();
 29//!
 30//! let a = NonNativeFieldVar::<Fr, Fq>::new_witness(ns!(cs, "a"), || Ok(a_value))?;
 31//! let b = NonNativeFieldVar::<Fr, Fq>::new_witness(ns!(cs, "b"), || Ok(b_value))?;
 32//!
 33//! // add
 34//! let a_plus_b = &a + &b;
 35//!
 36//! // sub
 37//! let a_minus_b = &a - &b;
 38//!
 39//! // multiply
 40//! let a_times_b = &a * &b;
 41//!
 42//! // enforce equality
 43//! a.enforce_equal(&b)?;
 44//! # Ok(())
 45//! # }
 46//! ```
 47//!
 48//! ## Advanced optimization
 49//!
 50//! After each multiplication, our library internally performs a *reduce* operation,
 51//! which reduces an intermediate type [`NonNativeFieldMulResultVar`] to the normalized type [`NonNativeFieldVar`].
 52//! This enables a user to seamlessly perform a sequence of operations without worrying about the underlying details.
 53//!
 54//! However, this operation is expensive and is sometimes avoidable. We can reduce the number of constraints by using this intermediate type, which only supports additions. To multiply, it must be reduced back to [`NonNativeFieldVar`]. See below for a skeleton example.
 55//!
 56//! ---
 57//!
 58//! To compute `a * b + c * d`, the straightforward (but more expensive) implementation is as follows:
 59//!
 60//! ```ignore
 61//! let a_times_b = &a * &b;
 62//! let c_times_d = &c * &d;
 63//! let res = &a_times_b + &c_times_d;
 64//! ```
 65//!
 66//! This performs two *reduce* operations in total, one for each multiplication.
 67//!
 68//! ---
 69//!
 70//! We can save one reduction by using the [`NonNativeFieldMulResultVar`], as follows:
 71//!
 72//! ```ignore
 73//! let a_times_b = a.mul_without_reduce(&b)?;
 74//! let c_times_d = c.mul_without_reduce(&d)?;
 75//! let res = (&a_times_b + &c_times_d)?.reduce()?;
 76//! ```
 77//!
 78//! It performs only one *reduce* operation and is roughly 2x faster than the first implementation.
 79//!
 80//! ## Inspiration and basic design
 81//!
 82//! This implementation employs the standard idea of using multiple **limbs** to represent an element of the target field. For example, an element in the TargetField may be represented by three BaseField elements (i.e., the limbs).
 83//!
 84//! ```text
 85//! TargetField -> limb 1, limb 2, and limb 3 (each is a BaseField element)
 86//! ```
 87//!
 88//! After some computation, the limbs become saturated and need to be **reduced**, in order to engage in more computation.
 89//!
 90//! We heavily use the optimization techniques in [\[KPS18\]](https://akosba.github.io/papers/xjsnark.pdf) and [\[OWWB20\]](https://eprint.iacr.org/2019/1494).
 91//! Both works have their own open-source libraries:
 92//! [xJsnark](https://github.com/akosba/xjsnark) and
 93//! [bellman-bignat](https://github.com/alex-ozdemir/bellman-bignat).
 94//! Compared with these, this module works with the `arkworks` ecosystem.
 95//! It also provides the option (based on an `optimization_goal` for the constraint system) to optimize
 96//! for constraint density instead of number of constraints, which improves efficiency in
 97//! proof systems like [Marlin](https://github.com/arkworks-rs/marlin).
 98//!
 99//! ## References
100//! \[KPS18\]: A. E. Kosba, C. Papamanthou, and E. Shi. "xJsnark: a framework for efficient verifiable computation," in *Proceedings of the 39th Symposium on Security and Privacy*, ser. S&P ’18, 2018, pp. 944–961.
101//!
102//! \[OWWB20\]: A. Ozdemir, R. S. Wahby, B. Whitehat, and D. Boneh. "Scaling verifiable computation using efficient set accumulators," in *Proceedings of the 29th USENIX Security Symposium*, ser. Security ’20, 2020.
103//!
104//! [`NonNativeFieldVar`]: crate::fields::nonnative::NonNativeFieldVar
105//! [`NonNativeFieldMulResultVar`]: crate::fields::nonnative::NonNativeFieldMulResultVar
106//! [`FpVar`]: crate::fields::fp::FpVar
107
108#![allow(
109    clippy::redundant_closure_call,
110    clippy::enum_glob_use,
111    clippy::missing_errors_doc,
112    clippy::cast_possible_truncation,
113    clippy::unseparated_literal_suffix
114)]
115
116use ark_std::fmt::Debug;
117
118/// Utilities for sampling parameters for non-native field gadgets
119///
120/// - `BaseField`:              the constraint field
121/// - `TargetField`:            the field being simulated
122/// - `num_limbs`:              how many limbs are used
123/// - `bits_per_limb`:          the size of the limbs
124pub mod params;
125/// How are non-native elements reduced?
126pub(crate) mod reduce;
127
128/// a macro for computing ceil(log2(x)) for a field element x
129macro_rules! overhead {
130    ($x:expr) => {{
131        use ark_ff::BigInteger;
132        let num = $x;
133        let num_bits = num.into_repr().to_bits_be();
134        let mut skipped_bits = 0;
135        for b in num_bits.iter() {
136            if *b == false {
137                skipped_bits += 1;
138            } else {
139                break;
140            }
141        }
142
143        let mut is_power_of_2 = true;
144        for b in num_bits.iter().skip(skipped_bits + 1) {
145            if *b == true {
146                is_power_of_2 = false;
147            }
148        }
149
150        if is_power_of_2 {
151            num_bits.len() - skipped_bits
152        } else {
153            num_bits.len() - skipped_bits + 1
154        }
155    }};
156}
157
158pub(crate) use overhead;
159
160/// Parameters for a specific `NonNativeFieldVar` instantiation
161#[derive(Clone, Debug)]
162pub struct NonNativeFieldParams {
163    /// The number of limbs (`BaseField` elements) used to represent a `TargetField` element. Highest limb first.
164    pub num_limbs: usize,
165
166    /// The number of bits of the limb
167    pub bits_per_limb: usize,
168}
169
170mod allocated_field_var;
171pub use allocated_field_var::*;
172
173mod allocated_mul_result;
174pub use allocated_mul_result::*;
175
176mod field_var;
177pub use field_var::*;
178
179mod mul_result;
180pub use mul_result::*;