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