nilfoundation / crypto3-algebra Goto Github PK

Use const modular params with montgomery form parameters for increasing performance.

• Add type trait for Group
• Add type trait for Group element
• Add type trait for Curve group element
• Add check, that set of methods is correct, to curve policies

UPDATE: Unrelated to field , also fails with double type.

typedef bls12_fq<381>::value_type bls12_base_f;

int main() {
    constexpr auto f1 = bls12_base_f(0x1);
    constexpr auto f2 = bls12_base_f(0x2);

    constexpr matrix<bls12_base_f,2,2> m1 = {{{f1, f2}, {f1, f2}}};
    constexpr matrix<bls12_base_f,2,2> m2 = {{{f2, f1}, {f2, f1}}};

    auto m3 = m1 + m2;
    return 0;
}

The above snippet fails with the below error

/home/hgedia/Development/nil/crypto3-scaffold/src/bls/src/main.cpp:18:18: error: invalid operands to binary expression ('const matrix<bls12_base_f, 2, 2>' (aka 'const matrix<element_fp<params<bls12_base_field<381>>>, 2, 2>') and 'const matrix<bls12_base_f, 2, 2>' (aka 'const matrix<element_fp<params<bls12_base_field<381>>>, 2, 2>'))
    auto m3 = m1 + m2;

http://www.hyperelliptic.org/EFD/g1p/auto-shortw.html

Because the stable version of marshalling is ready, it's time to transfer all the functions we want have in algebra marshalling from algebra to the crypto3::marshalling.

Each new curve implementation right now requires it's own group element implementation. However, most of our curves are of the same representations. There is no need to implement it from scratch every time. If we introduce separate elements for different curves representations, we will be able to add new curves extremely fast.

Bringing a new curve requires to do just two things:

• Add field description (like here);
• Add curve params (like here);
• Add curve group type struct and public policy.

There is a great source of many common curves in a easy-readable form: https://github.com/J08nY/std-curves

This process most probably can be automatized with simple python json parser.

• Edwards Fp3 (and probably other field extensions) sqrt seems to work incorrectly
• BLS12-381 Fp2 (and probably other field extensions) inversed seems to work incorrectly

Implementation of BN-128 currently differs from other curves. It relies now on the double_element structure. Looks like not the best way to implement it.
The current implementation also requires a lot of specific functions inside the element structures.
We need to review and debug it.

We should add some other params to curve group policy to identify it more clearly.

Pallas and Vesta are two curves, introduced by Zcash and widely used by the community. We need to add them to support more algorithms and protocols.
Zcash Protocol Specification
This zcash repository looks like it contains these two curves.

Related to NilFoundation/crypto3-zk#9

Concept introduction along with type traits formalization is required.

Concept introduction along with type traits formalization is required.

Having access to a precomputed quadratic non-residue is useful for circuits.
An example is an 'and' operation, merging two constraints f(x) = 0, g(x) = 0 into a single one
f^2(x) - p * g^2(x) = 0
This can be used to build complex constraints like 'either both f and g are 0, or both q and r are zero'.

Pairings require thorough debug and testing:

• * ALT-BN128
• * BLS12-381
• * BLS12-377
• * BN128
• * Edwards-183
• * MNT-4
• * MNT-6

The following pairings do not compile now:

• ALT-BN128
• BN128

Making pairing for ALT-BN128 compiled is the easiest subtask.

Pairing for BLS12-377 undone at all.

Our current implementation is hardly bound to multiprecision cpp_int modular_adaptor backend.
The problem partially is that we have a lot of constexpr defined things, which are not supported by gmp and tommath backends. Probably we need to add some conversions between backends in the multiprecision.

https://datatracker.ietf.org/doc/html/rfc7748
https://datatracker.ietf.org/doc/html/rfc8032

Multiexp algorithms have no actual tests at the moment.
We need to add some JSON-based tests to be sure of its correctness.

Sqrt implementation seems to be incorrect.
Underlying fields of mentioned curves are affected by this issue. Check correctness after sqrt issue will be fixed.

modulus_type (cpp_int) and number_type (modulus_adaptor) confuse

We need to introduce the first full version of documentation for each crypto3-module.

• Module Description
• Getting Started Guide
• API description:
  • algorithms
  • curves
  • detail
  • fields
  • matrix
  • multiexp (including multiprecision part)
  • pairing
  • scalar
  • vector
• Internal algorithms description
• Examples
• Extension Example / Guide
• Architecture

Arithmetic params usage require #includes being appended in very particular order. This makes things complicated. Should be reviewed.

Right now g1_type and g2_type are a mixture of group element and group policy concepts. This has to be split to comply to the generic architecture.

Static (constexpr) tests for curves and fields arithmetic are required

It makes sense to add an assert to the curve element constructor and check, if the point with given coordinates is in the group.

Constexpr field and curve arithmetic highly required.
Including Frobenius params constexpr eval.

Matrix and vector arithmetic used in run-time has to be optimized.

Field extension params structure can be made way better.

Includes #89