Expand description
This module contains a generic implementation of “emulated” prime field
variables. It emulates Fp
arithmetic using Fq
operations, where p != q
.
§Overview
This module implements a field gadget for a prime field Fp
over another
prime field Fq
where p != q
.
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). 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.
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.)
§Usage
Because EmulatedFpVar
implements the FieldVar
trait in arkworks,
we can treat it like a native prime field variable (FpVar
).
We can do the standard field operations, such as +
, -
, and *
. See the
following example:
use ark_r1cs_std::fields::emulated_fp::EmulatedFpVar;
use ark_bls12_377::{Fr, Fq};
let a = EmulatedFpVar::<Fr, Fq>::new_witness(ns!(cs, "a"), || Ok(a_value))?;
let b = EmulatedFpVar::<Fr, Fq>::new_witness(ns!(cs, "b"), || Ok(b_value))?;
// add
let a_plus_b = &a + &b;
// sub
let a_minus_b = &a - &b;
// multiply
let a_times_b = &a * &b;
// enforce equality
a.enforce_equal(&b)?;
§Advanced optimization
After each multiplication, our library internally performs a reduce
operation, which reduces an intermediate type MulResultVar
to the normalized type EmulatedFpVar
. This enables a user to
seamlessly perform a sequence of operations without worrying about the
underlying details.
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
EmulatedFpVar
. See below for a skeleton example.
To compute a * b + c * d
, the straightforward (but more expensive)
implementation is as follows:
let a_times_b = &a * &b;
let c_times_d = &c * &d;
let res = &a_times_b + &c_times_d;
This performs two reduce operations in total, one for each multiplication.
We can save one reduction by using MulResultVar
, as
follows:
let a_times_b = a.mul_without_reduce(&b)?;
let c_times_d = c.mul_without_reduce(&d)?;
let res = (&a_times_b + &c_times_d)?.reduce()?;
It performs only one reduce operation and is roughly 2x faster than the first implementation.
§Inspiration and basic design
This implementation employs the standard idea of using multiple limbs to represent an element of the target field. For example, an element in the TargetF may be represented by three BaseF elements (i.e., the limbs).
TargetF -> limb 1, limb 2, and limb 3 (each is a BaseF element)
After some computation, the limbs become saturated and need to be reduced, in order to engage in more computation.
We heavily use the optimization techniques in [KPS18] and [OWWB20].
Both works have their own open-source libraries:
xJsnark and
bellman-bignat.
Compared with these, this module works with the arkworks
ecosystem.
It also provides the option (based on an optimization_goal
for the
constraint system) to optimize for constraint density instead of number of
constraints, which improves efficiency in proof systems like Marlin.
§References
[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.
[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.
Modules§
- Utilities for sampling parameters for non-native field gadgets
Structs§
- The allocated version of
EmulatedFpVar
(introduced below) - The allocated form of
MulResultVar
(introduced below) - Parameters for a specific
EmulatedFpVar
instantiation
Enums§
- A gadget for representing non-native (
TargetF
) field elements over the constraint field (BaseF
). - An intermediate representation especially for the result of a multiplication, containing more limbs. It is intended for advanced usage to improve the efficiency.