horizenofficial / ginger-lib Goto Github PK
View Code? Open in Web Editor NEWThis project forked from arkworks-rs/snark
Ginger-lib is a general purpose zk-SNARK library that supports recursive proof composition
License: Apache License 2.0
This project forked from arkworks-rs/snark
Ginger-lib is a general purpose zk-SNARK library that supports recursive proof composition
License: Apache License 2.0
By now the pairing engines for different types of pairing-friendly curves are implemented independently, resulting in five pieces of very similar code for the Ate pairing evaluation:
algebra/src/curves/models/bls12/mod.rs
, ZEXE's generic implementation for BLS12 curves in affine coordinates,algebra/src/curves/mnt6/mod.rs
, ZEXE's specific implementation for the MNT6-298,algebra/src/curves/sw6/mod.rs
, another implementation for the Cocks-Pinch curve-782 of embedding degree 6 (ZEXE's outer curve with respect to the BLS12-377),algebra/src/curves/models/mnt4/mod.rs
, and MNT6 curves, algebra/src/curves/models/mnt6/mod.rs
.I propose a different level of abstraction, introducing twist2Ate
and twist6Ate
as pairing types according to the two representations of G2 as found in the above implementations: either as a subgroup of a quadratic twist (as for MNT4/6, mnt6, sw6) or sextic twist (BLS12) of the curve.
Both twist2Ate
and twist6Ate
need to allow the base field for the twist E' to be a general extension field of the same characteristic as the one for E - but the operations for the evaluation of the Ate paring are generic, i.e. independent of the degree of the base field for E'.
Such abstraction makes it possible to reuse these two types of pairing types, and to aggregate pairing evaluation code in an own folder (e.g. algebra/src/pairings/
) separated from algebra/src/curves
, which contain also non-pairing-friendly curves such as the JubJub.
In my opinion such a structure is more clear than the present. Moreover, it makes it is easier to find all the pairing code when extending the lib by further pairing types (which use cubic twists, e.g.).
The present code of the Miller loop for the MNT4/6 Ate pairings uses the pre-computed values
Later, point evaluation of the Miller line (scaled by twist^2) in the embedding field
$$
(y_p - \lambda * x_p - d) * twist^2 = (y_p*twist^2 - (\gamma * twist * x_p - y_R - \gamma * x_R ) * Y),
$$
where the terms
Beside gathering the point evaluation code in a separate function (as done for the ZEXE sw6), I propose to define the pre-computed values for
instead (for each Miller line), and reduce point evaluation to
$$
(y_p - \lambda * x_p - d) * twist^2 = (y_p * twist^2 - (\gamma' * x_p - d' ) * Y),
$$
saving two multiplications and one addition in the base field F of the quadratic twist.
Do we need to make the field arithmetic resistant to timing attacks?
For example, removing the final conditional branch in the Montgomery multiplication or making the computation of the modular inversion constant?
Can an adversary take advantage of these attacks to break the security of the system?
As Coda we take the embedding field of an MTN4 curve as the quadratic extension
Fp4 = Fp2[Y] / (Y^2 - X)
of Fp2 = Fp[X]/(X^2 - alpha), where alpha is the const Fp2Parameters::NONRESIDUE
, and similarly the embedding field of an MNT6 curve as
Fp6 = Fp2[Y]/(Y^2-X)
of Fp3=Fp[X]/(X^3 - alpha), with \alpha as const Fp3Parameters::NONRESIDUE
.
However, the implementations of the two towered extensions differs in style, and both 'open up' the arithmetics of their subfields Fp2, Fp3, respectively, to define multiplications by
To illustrate the different styles of implementation:
pub fn mul_by_nonresidue(value: &Fp2<P::Fp2Params>) -> Fp2<P::Fp2Params> {
let new_c0 = P::Fp2Params::mul_fp_by_nonresidue(&value.c1);
let new_c1 = value.c0;
Fp2::new(new_c0, new_c1)
}
not even referring to Fp2Parameters::NONRESIDUE
, whereas
pub fn mul_by_nonresidue(value: &Fp3<P::Fp3Params>) -> Fp3<P::Fp3Params> {
let mut res = *value;
res.c0 = value.c2;
res.c1 = value.c0;
res.c2 = value.c1;
res.c0
.mul_assign(&<P::Fp3Params as Fp3Parameters>::NONRESIDUE);
res
}
which use Fp3Parameters::NONRESIDUE
, and the generic trait Fp6Parameters
function
fn mul_fp3_by_nonresidue(fe: &Fp3<Self::Fp3Params>) -> Fp3<Self::Fp3Params> {
Self::NONRESIDUE * fe
}
is not used at all.
I propose a restructuring of the towered extension fields, choosing a generic approach which defines quadratic/cubic extensions F2/F3 over any field F (not necessarily prime), and then define F6 with "sextic" non-residue Fp6Params::NONRESIDUE
as quadratic extension F2(F3), using the (quadratic) non-residue
(c_0,c_1)=(0,1) from F3^2
(which corresponds to X), where F3 is the cubic extension of Fp using the sextic non-residue as (cubic) non-residue. Likewise, one defines F4 with "quartic" non-residue Fp4Params::NONRESIDUE
as quadratic extension F2(F2), using the quadratic nonresidue
(0,1) in F2^2,
where F2 is the quadratic extension of Fp using the quartic non-residue as quadratic one.
Such generic implementation is not just for readability - it also makes further towering (if ever needed lateron) more transparent and easy.
This looks like a promising library, but how do you use it?
In all our extension fields gadgets, the 'not-equal' gadget NEqGadget
as implemented enforces inequality of all components (=vector coordinates), and not of at least one.
Besides that this does not describe the 'canoncial' behaviour one would expect, it is necessary to evaluate the impact of using this stricter notion of inequality in other gadgets (e.g., for affine EC arithmetics, which need to compare against the 0 element, etc.).
Update
The impact is surprisingly harmless. The AffineGadgets which use enforce_not_equal
of field elements to implement the inequality gadget of points is only used at a single place of code by now (in the G2PreparedGadget of BLS12 pairings), which has no security impact.
Still to prevent malicious impact I recommend to correct the extension field NEqGadgets to reflect the expected behaviour.
See arkworks-rs#181
Please make sure that sensitive data, such as private keys, that are stored in temporary variables are cleared before exiting the function. It is not safe to just leave it out of scope as it may be exploited with attacks. Also make sure that the function that clears the data is not skipped by optimization of the compiler.
To be able to not have to collect first all the inputs together and then passing them to poseidon, add the possibility to pass just one input at a time and keep the state in a separate structure. The state will be updated each time that the inputs collected so far are multiple of R or if the finalize method was called and something was still in the pending inputs.
In the actual Merkle Tree implementation a minimum number of leaves/nodes is actually generated to create a tree of height MIN_HEIGHT with respect to the one you would expect by setting the HEIGHT parameter in MerkleTreeConfig.
This is obviously done for efficiency reason, but: padding nodes are added only between MIN_HEIGHT and HEIGHT , therefore you won't actually have 2^(HEIGHT - 1) leaves: this means that if you want to create a Merkle Proof starting from a specific padding leaf, or reconstruct the Merkle Root starting from all the leaves, you can't;
Of course if we want to keep this implementation the most immediate solution would be to explicitly pass all the leaves according to the desired HEIGHT and keep everything in memory.
But, if a given subtree has all or some of the leaves all to null, sure there is a smarter way to quickly and efficiently compute the root of that tree via pre-computation and caching:
it is worth to investigate this and implement optimizations in order to efficiently compute and represent a "full" Merkle Tree and not a "virtually full" like the actual one.
We should add more regression tests (hardcode expected relevant data, recompute it inside the test and compare) on:
Cryptographic primitives;
Bit/Byte serialization
It seems that the security estimates of ZEXE's BLS, Cocks-Pinch, MNT6 as well as Coda's full MNT4-MNT6 cycle, which we implemented for ginger, do not consider recent improvements on the special number field sieve for towered extension fields (TNFS). In a 2019 paper , BLS curves targeting a security level of 128 bit are updated accordingly yielding base field sizes of 446 bit (instead of the 377 Bits for the BLS-377).
I did not read the paper in detail, but we should evaluate the impact of STNFS improvements on our MNT4/6 curves as well.
Some code of the cubic extension field gadgets Fp3Gadget
and Fp6Gadget
as '3over2' can be optimized:
inverse
gadget uses Karatsuba multiplication using 6 base field constraints instead of Toom-Cook's 5 constraintssquare
gadget uses Toom-Cook multiplication, but according to Devigili, et al., the Chung-Hasan asymmetric squaring formula (CH-SQR2) replaces 3 multiplications by squares (Zexe replaced this piece of code today).mul_by_constant
uses for no reason Toom-Cook with more than 100 lines, although the naive multiplication yields the same result.Some of these issues are described in more detail in the docu branch of the field gadgets, PR of docu field gadgets.
When it comes to complete addition gadgets, I expect that we can do better than the "naive" approach using the infinity flag of the AffineGadget
. Let us investigate efficient complete arithmetics within circuit:
Would be nice to execute some commands on PR and new commit. I'm thinking about checking that compilation and tests pass.
Something like:
cargo check --examples --all-features
To compile (without generating the binaries) libraries and examples with all features enabled;
cargo test --all-features
To compile and run all the tests (might be necessary here to restrict the number of threads in which the tests are parallely executed to avoid finishing resources with the flag --test-threads);
cargo +nightly check --benches --all-features
To also compile the benchmarks
By now, we test a point P belonging to a prime order subgroup G of an elliptic curve E by checking that
The constraints for fn inverse
in our Fp2Gadget
(as well as many other extension field gadgets, see below) are
(1) v1 = a1* b1,
(2) 1+ (1- beta)* v1 = (a0 + a1) * (b0 + b1),
where a = (a0 + a1 * Y) and b = (b0 + b1 * Y) in Fp2 = Fp[Y]/(Y^2-beta) are meant to be enforced being inverse to each other, i.e. (a0 + a1 * Y) * (b0 + b1 * Y) = 1. These two constraints are derived directly from the equations for "real" and "imaginary" parts using the Karatsuba trick,
1 = a0 * b0 + Y^2 a1*b1,
0 = a0 * b1 + a1 * b0 = (a0 + a1) * (b0 + b1) - v0 - v1,
where v0 = a0*b0.
However, the two constraints (1) and (2) are NOT SUFFICIENT to enforce that a = (a0 + a1 * Y) is the inverse of b = (b0 + b1 * Y): For instance, suppose an adversary chooses a0 = 0, b1= 0, which amounts to assuming a = a1*Y, b = b0, a pair of Fp2 elments that never can be inverse to each other. But in this case the above constraints reduce to
(1) v1 = a1 * b1 = 0 ,
(2) 1+ (1- beta) * v1 = a1 * b0,
which are easily satisfied choosing v1 = 0 and a1 as the inverse of b0 in the base field Fp.
To overcome this problem we need to keep the additional constraint for the "real" part of (a0 + a1 * Y) * (b0 + b1 * Y) = 1, which is
(3) 1 - beta * v1 = a0 * b0.
Note: This issue is critical, as it allows an adversary to cheat on the inverse relation between (extension) Fp2 (and other extension field) gadgets, which is part of affine curve arithmetics and pairing evaluation gadgets relying on these extension fields. In particular, the following extension field gadget have this issue:
Fp2Gadget
,Fp4Gadget
,FP6Gadget
in fp6_2over3.rs, andFp12Gadget
.The affine curve and pairing gadgets of G2 for all BLS, MNT4 and MNT6 curves rely on these.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.