This issue involves:

• Adding as_conversions lint as a warning at a workspace level.
• Fixing the clippy warnings because of the above.

For more context see as_conversions.

There is currently a naming convention on traits that they are supposed to start with something like Is or Has. We should get rid of it

The idea is to have a structure like this (for both math and crypto crates):

benches
|_benchmarks
|  |_mod.rs
|  |_field.rs
|  |_...
|_benchmarks.rs
|_benchmarks_field.rs
|_...

• The benchmarks.rs file will run all the benchmarks and the benchmarks_<module> will run the module's benchmarks.
• The benchmarks will be written in the benchmarks module in the corresponding files.

The goal with this is for us to be able to run all the benchmarks at once or just some of them individually.

We'll also need to have two targets in the Makefile:

// Run all the benchmarks at once
benches:
    cargo criterion --bench benchmarks

// Run a specific benchmark
benchmark:
    cargo criterion --bench ${BENCHMARK}

Building from the ground up with fuzzing in mind is always beneficial to libraries, especially ones that define their own types.

Meaning the Arbitrary trait should be implemented for all types, maybe even on the features themselves. This way, setting up libFuzzer, cargo fuzz, or AFL is easy.

The standard approach is to add a feature gate arbitrary that reveals the Arbitrary trait implementations when enabled.

Add support for Goldilocks elliptic curve.

See https://eprint.iacr.org/2015/625.pdf for reference.

Fast Karatsuba multiplication has to be implemented for Goldilocks to be highly efficient

Add to_hex(&self) -> String function to FieldElement and implement it where needed

This function should create an hexstring representing the number in FieldElement. It should abstract the user from the internal representation, so if the number is in Montgomery form, it should convert it back to the original form before returning the element.

Add from_hex(hex_string: &str) -> Self function to FieldElement and implement it where needed

This function should create FieldElement from an hex string. It should support arbitrary sizes of strings, and be easily shared between FieldElement implementations.

It needs to take in account the internal representation may not be the same number. For example, if "1" is the input, and the MontgomeryBackend is used, the number stored will be 1 * R mod MODULUS, but the user should never know about the internal representation.

Additionally, it may be useful to make it a const fn

Hey, you folks planning on writing any tutorials or more comprehensive for Readme.md for newbies? Would love to help with that so more learners could start with this

Obtain the domain evaluation points by taking an element in the coset and the generator of the trace domain.

I think that for the Field trait, rather than defining methods like add, sub, mult, inv, etc., they should leverage the core::ops::Add and others.

If a trait for a method does not exist, it should be defined in a similar style to one from core::ops.

NOTE:
The use of core instead of std here, and I would recommend using core for all things where possible as it would make supporting no_std easier.
They point to the same implementations, but core is specifically for no_std environments.

Michael Scott, one of the creators of BLS curves, has a paper out which should describe a more efficient group membership check for G1, G2 and GT.

https://eprint.iacr.org/2021/1130.pdf

• Interpolate trace values where there are boundary constraintsto obtain polynomial
• Subtract this new polynomial to the trace polynomial
• Divide by zerofier

Hi guys, the link to the telegram chat at the README.md seams to be expired, can someone update it?

We need operations over finite fields defined in the Metal Shading Language for implementing FFT (#116) and possibly other future algorithms in the GPU. So it's required to make implementations that mimic the ones we already have in Rust.

Some requirements:

• Basic operations like sum, sub, mul, div.
• Watch out for integer overflow, special care is needed to implement the mul operation for example.
• Ideally we could build a field with a custom module (represented as an uint64_t or whichever type is needed)
• MSL only supports up to 64-bit integers, so it would be needed to also implement classes for bigger ints (specifically see which fields with big integers there are implemented on Rust right now)
• The work directory will be math/src/fft/metal/

Relevant resources:

• MSL Specification (MSL is based on C++)
• The Metal documentation and also see our metal_playground repo for examples on how to use the metal crate in Rust, useful for testing.
• risc0 and ministark have some examples of prime fields implemented in C or MSL.
• Us
• General information about finite fields and modular arithmetic can be easily found on the web.

The ByteConversion trait should define:

• to_bytes_be: Big-Endian representation.
• to_bytes_le: Little-Endian representation.
• from_bytes_be: Big-Endian representation.
• from_bytes_le: Little-Endian representation.

Fiat Shamir is currently hardcoded for both the prover and verifier, they should both use the Transcript API instead to sample values.

The idea is to have something like this but for 256 bits.

For inspiration, check implementations of

• Winterfell: https://github.com/facebook/winterfell/tree/main/air/src/air
• Giza: https://github.com/maxgillett/giza/tree/master/air/src

Some functions should return a Resultinstead of using an assert because doing the latter would panic in runtime.

In general, if you don't have any choice but to panic it is better to describe the cases in which that function would panic and why in the documentation.

For this issue, we just want to replace these assertions with debug assertions. We'll address the Result in another issue.

An example would be this.

Implement Fast Fourier transform

Example implementation: https://github.com/facebook/winterfell/blob/main/math/src/fft/mod.rs

Depends on #30

The API should be something like this:
interpolate_poly()
evaluate_poly()

Implement the rand traits for FieldElement<F> where F: IsFIeld.

Implement the rand traits for ProjectivePoint<E> where E: IsEllipticCurve.

Learn the basics of how CUDA works by implementing some examples.

Initial resource: https://www.notamonadtutorial.com/cuda-from-scratch/

The FriDecommitment struct currently provides the last layer evaluation point, but the verifier does not check it. Fix this

Acceptance criteria:

• It should be customisable to to use sequential or the parallelizable implementation.
• Parallelizable version should pass all the tests that the sequencial version passes.

Implement sparse polynomial representation. We should support operations between sparse and dense polynomials, and conversions between them.

The first task is to be investigate how it's done in other libraries, and update the issue with an explanation of how it's done in them.

"Inside the FFT black box" by E. Chu & A. George seems like a great resource.

Tasks

• #125
• #167
• #123
• #147
• #190
• #193
• Add benchmarks and tests

PR Template is not being detected, it needs to be fixed

The canonical signed digit, or Non-Adjacent Form (NAF) is a unique way to represent a binary number with a lower absolute hamming weight, using digit € {0,1,-1} as coefficients instead of just digit € {0,1}.

See https://en.wikipedia.org/wiki/Non-adjacent_form

It should improve performance in exponentiation by squaring algorithms and similar as you just need a sub or negate function for -1 cases.
The overall hamming weight W = sum([abs(digit) for digit in bin(int)]) is in average 1/3 instead of 1/2.
Using this representation should lead to improvements in the range of 10-25% for the average case.

An example of this technique can be found in the gnark repo :

definition : https://github.com/ConsenSys/gnark-crypto/blob/8f7ca09273c24ed9465043566906cbecf5dcee91/ecc/bn254/bn254.go#L141-L143
usage (miller loop) : https://github.com/ConsenSys/gnark-crypto/blob/8f7ca09273c24ed9465043566906cbecf5dcee91/ecc/bn254/pairing.go#L161

For example From<&F::BaseType> for FieldElement<F> is already implemented for FieldElement but const_from (its constant version) it's not.

Currently the inv implementations for U64PrimeField and U384PrimeField both panic when dividing by zero. We should return an error instead. For this, we should use thiserror.

The current composition polynomials we commit to do not divide by the appropriate zerofiers. When this is done, change the proving to evaluate on a root of unity coset instead of an actual set of roots of unity.

The task is to implement this trait for FieldElement.

In order to solve #95 without repeat code i tried to generalize IsMontgomeryConfiguration trait and MontgomeryBackendPrimeField struct to allow usage with any UnsignedInteger.

Tried something like this:

If i use a generic U: IsUnsignedInteger :

Any idea to define a generic to generalize any type UnsignedInteger<_> struct like?