horizenofficial/ginger-lib

Ginger-lib is a general purpose zk-SNARK library that supports recursive proof composition

ginger-lib's Issues

Restructuring pairings

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),
• and our recent implementations for generic MNT4 curves, 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.).

Precomputations for Ate Miller loop

The present code of the Miller loop for the MNT4/6 Ate pairings uses the pre-computed values

• for $P=(x_P,y_P)$ from $G_1$: $(x_P, y_P*twist^2)$,
• for $Q=(x_Q,y_Q)$ from $G_2$: for each intermediate point R, $(y_R, \gamma, \gamma * x_R)$, where $\gamma$ is the slope in the base field F of the quadratic twist (i.e. F2 for MNT4, F3 for the MNT6).

Later, point evaluation of the Miller line (scaled by twist^2) in the embedding field $F_e = F[Y]/(Y^2-twist)$ is computed as
$$
(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 $\gamma'= \gamma * twist$, $d'= y_R - \gamma * x_R$ are (re-)computed for every single line, although they are independent of $P$.

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 $Q$ as the two elements

• $\gamma' := \gamma * twist$, and
• $d' = y_R - \gamma * x_R$

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.

Placeholder 7

PR: mathematical comments for MNT4/6, and their fields (base+extension)

Placeholder 20

Placeholder 28

Placeholder 21

PR: Readme file edited

PR: Ginger additions and refactoring

Placeholder 19

Resistance against timing attacks

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?

Restructuring of towered extension fields Fp4 and Fp6

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 $X$ therein.
To illustrate the different styles of implementation:

• for Fp4, multiplication by Y^2 = X is done as

    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

• for Fp6, multiplication by $X$ is implemented as

    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.

Placeholder 8

Placeholder 24

Placeholder 10

PR: Comments modification

Placeholder 11

Placeholder 6

Documentation with example

This looks like a promising library, but how do you use it?

• Can it be used as both R1CS frontend (compiling) and backend?
• Or should the library be used from Rust itself based on R1CS primitives? Then,
• How does one perform a simple circuit generation and proving? Some example code like https://github.com/microsoft/Spartan would be helpful

Placeholder 16

Fixes after code review

Placeholder 1

Placeholder 17

Placeholder 15

NEqGadget implementation of extension field gadgets

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.

Modify FieldElement read function to return error in case of value over modulus

See arkworks-rs#181

Clearing sensitive data before exiting the code

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.

Updatable Poseidon Hash

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.

Cached Merkle Trees

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.

Placeholder 5

Placeholder 23

Fixes after code review

Placeholder 12

Add more regression tests

We should add more regression tests (hardcode expected relevant data, recompute it inside the test and compare) on:

• Cryptographic primitives;

• Bit/Byte serialization

Placeholder 13

PR: Docu Schnorr and Poseidon

Security estimate of pairing-friendly curves, TNFS

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.

Optimizing deg-3 extension field gadgets

Some code of the cubic extension field gadgets Fp3Gadget and Fp6Gadget as '3over2' can be optimized:

• the inverse gadget uses Karatsuba multiplication using 6 base field constraints instead of Toom-Cook's 5 constraints
• the square 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.

Complete EC addition circuits

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:

• Which projective representation has the most efficient complete addition formulas?
• Is mixed arithmetics useful for us?
• Are there other practical approaches for avoiding exceptions (such as random shifts, e.g.)?

Placeholder 18

Placeholder 32

Add support for Travis CI

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

Placeholder 2

PR: Docu Miller loops

Group membership test with large cofactors

By now, we test a point P belonging to a prime order subgroup G of an elliptic curve E by checking that

• P is a point on E (by checking the curve equation), and
• P has the order of G.
  However, this enforces group membership only if the prime order r of G is unique in E, i.e. it's multiplicity as a factor of ord(G) is one, or r || ord(G).
  For small cofactor subgroups G (as is always the case for all of our curves, in particular our pairing G1's) this is always satisfied, but for our pairing G2's as a subgroup of a quadratic twist E' of E, this is no longer necessarily true.
  For the sake of generality, it seems that we need to introduce the extra check that the cofactor(G) is coprime to r, i.e.
• gcd(cofactor(G),r) = 1,
  but maybe for our pairing groups this check is redundant, too.

Placeholder 9

Insufficient constraints for fn inverse in Fp2 (and other) extension field gadgets

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, and
• Fp12Gadget.

The affine curve and pairing gadgets of G2 for all BLS, MNT4 and MNT6 curves rely on these.

Placeholder 14

Placeholder 22

Placeholder 26