Description

Phase 3 as defined in Algorithm 6 of document B is not working currently. Indeed, the returned polynomial is not congruent to a*b mod P.

Fp arithmetics using polynomial representation of field elements not only require modular polynomial multiplication, which should be completed (see #6) before starting this task, but also modular polynomial addition.

Based on the work on modular polynomial multiplication in mul_mod.py , implement a modular polynomial addition algorithm for BN curves.
Given a,b € Fp, A and B their respective polynomial representation, and p=F(t), t fixed for a BN prime, compute C=A+B and and find out how to reduce the coefficients so that C(t) == a+b mod p.

Currently, inverse functions in e2 and e12 are using hints for efficient computations.
The inverse is computed using the gnark library.

They should be computed in pure python to allow whitelisting of the hints on Starknet.
Some possible working code for pure python inversion is available in tests/cairo_programs/libs/

Update the inverse hints in src/bn254/towers/e2.cairo and e12.cairo
All protostar tests should pass.
Try to make the python hints as clean/succint as possible. It must be self-contained, ie: no imports. Define the function inside the hint.

Implement Rust bindings for the file algebra.py while maintaining same methods and properties.

Demonstrate performance improvements when running benchmarks.py

Use https://pyo3.rs/ and PR to rewrite branch.

Some bench using py-spy top -- python src/benchmarks.py (see py-spy ) :

make setup script should be updated and integrated easily.

https://github.com/Consensys/gnark/blob/bd4a39719a964f0305ee9ec36b6226e4c266584c/std/algebra/emulated/sw_bls12381/pairing.go#L318

create a new folder in tests/cairo_snark/plonk

Update tests/protostar_tests/bn254/test_precompiles.cairo and precompiles contract to reflect the changes in the pairing.cairo library for bn254. (Multi pairing now available)
the command protostar test-cairo0 tests/protostar_tests/bn254/test_precompiles.cairo --max-steps 5000000 should pass

Feature Request

Describe the Feature Request

Add Ethereum's bn254 precompiles Starknet contract

Describe Preferred Solution

A tested contract that exposes ecAdd, ecMul and ecPairing and takes the same arguments as Ethereum's related precompiles.

Additional Context

• https://www.evm.codes/precompiled#0x06?fork=merge

Counting the positive and negative multiplicities of the base (-3) decomposition of a u128 is needed for efficient elliptic curve scalar multiplication.

Implement the Cairo1 version of

Annotations were added on the python function to help you on the expected types.

FYI, the CairoZero version of it is here

Since it is not possible in Cairo1, you must also implement the following function

However, the CairoZero version may still contains important information or clarifications.

• Be sure to implement this function for u128 in input.
• Use constant array of felt252 for powers of (-3) % STARK where STARK = 2^251+ 17*2^192 + 1. , similarly to the Cairo0 version.
• Write the utils functions in the contracts branch of the repo, under src/cairo/src/utils.cairo. Generate some test vectors with the python functions and test it. Try to automatize the creation of a test function to simplify its generation.
• Be as performant as possible. Benchmark your implementation.

Relevant references and explanations are present in section 7.3 of Document A.
Direct formulas can be found in appendix of Document C.
Use (already or naïvely) implemented Cairo functions for modular addition and multiplication in Fp to construct the tower of Fields for Fp12.

Implement Torus Final exponentiation as in
https://github.com/Consensys/gnark/blob/bd4a39719a964f0305ee9ec36b6226e4c266584c/std/algebra/emulated/sw_bn254/pairing.go#L136

Document D is used as reference.
Use the Adapted Modular Number System (AMNS) for polynomial representation of field elements and use it to construct arithmetics over Fp12 for any p.

For better security of linear combination in the polynomial commitment, BN254 base should be increased to 96 bits.
Change it in curve.cairo and update constants and relevant hints

Following the working implementation of pairing and arithmetics for bn254, create a folder in src/bls12-381 and implement everything similarly to bn254.
Create a subfolder in tests/protostar_tests for bls12-381.
Update the parsing tool from gnark for this curve.

Implement Rust bindings for the file poseidon_transcript.py while maintaining same methods and properties.

Demonstrate performance improvements when running benchmarks.py

Use https://pyo3.rs/ and PR to rewrite branch.

For this part, modular polynomial addition and multiplication in Fp should be implemented and correct.

Use Document E as reference for theory and algorithms.
Use Python bindings of Armadillo for matrix arithmetic : https://pyarma.sourceforge.io/docs.html

This work should start with the understanding and representation of the mathematical objects described in Document E in python.

Feature Request

Describe the Feature Request

Update the go CLI implementation with the needed e12 and e6 operations

Describe Preferred Solution

• Add an argument to the command to be able to pick the field to do the operations from (e2, e6 and e12).
  Currently, only e2 is available.
• Modify main.go CLI to be able to call operation using a specific command and parse the specific input.

Describe Alternatives

Related Code
old:
./main op 1 2 3 4
needed
./main field op [x as a list of fp limbs] [y as a list of fp limbs]̀

Additional Context

If the feature request is approved, would you be willing to submit a PR?
(Help can be provided if you need assistance submitting a PR)

• Yes
• No

Write a verifier in python for Honk proofs based on this repo : https://github.com/Maddiaa0/honk-verifier/tree/master

how to :
- use garaga's python classes : [PyFelt](https://github.com/keep-starknet-strange/garaga/blob/ 07ad865/src/algebra.py#L5) for modular arithmetic operations.
- use / add (if needed) Elliptic curves information and constants from definitions.py
- write the verifier in a single python file under src/precompiled_circuits/honk.py.
- Do not write a ModuloCircuit class (this will be done later), only the verifier inside a function.
- You can copy paste and re-use the code here for EC scalar multiplication https://github.com/feltroidprime/zk-ecip-py/blob/main/src/curve.py when the solidity is using the ECMul/EcADD precompile
- You can use the gnark CLI backend when the solidity is using the EcPairing precompile
- add some python functions to parse and map the honk proof into a proper python dataclass inside honk.py
- write a similar test than in the honk-verifier repo inside the if __name__ == "__main__": part of the honk.py file.
- write clear code with type hints

Done.

Next task : Write a cairo implementation.
Requires #112

https://github.com/Consensys/gnark/blob/bd4a39719a964f0305ee9ec36b6226e4c266584c/std/algebra/emulated/sw_bn254/pairing.go#L324

We want to test Garaga against functions from https://github.com/ConsenSys/gnark-crypto/tree/master/ in our protostar tests. Gnark is an audited and trustworthy library which can be used for reference.

For example, this function that has 4 ints as input https://github.com/ConsenSys/gnark-crypto/blob/1a7a29904a7c29ba3e1c644d9752765b6ae9775e/ecc/bn254/internal/fptower/e2.go#L114

The scenario would be to use a hint to run a bash command which executes go code from inside python with the arguments parsed from Cairo, and parse stdout in python, write them to cairo, and then assert the correct in Cairo to test the functions.

Provide an example on the add function of two E2 elements in Gnark, that translates to a Fq2.add() function in cairo.
Write a protostar test with the correct hint to parse and run the go functions, and test the resulting value.

Make the tool as reusable and reproducible as possible for other functions from the Gnark library.

The checks are done for the BigInt3 not for the BigInt4, x.d3 == 0 needs to be added to both functions

Implement Torus Final exponentiation for BLS as in https://github.com/Consensys/gnark/blob/bd4a39719a964f0305ee9ec36b6226e4c266584c/std/algebra/emulated/sw_bls12381/pairing.go#L136

Work on https://github.com/feltroidprime/cairo-vm

• Implement bn254 hints, with unit cairo programs tests for all of them
• Integrate the CairoVM into the garaga repo, modify make-run scripts to run the program with CairoVM
• Handle input.json with a specific hint that loops through all the variable in the .json and fill them to the corresponding variable names in the Cairo memory.

@bacharif

Tower arithmetics can be made faster by using unreduced addition before modular multiplication is used.

An example of it is inside the e2.mul() function in src/towers/e2.cairo.

Implement (or draft) similar improvements wherever possible in e6 and e12. Make due diligence about the safety of such changes. (optional)

2022/596.pdf

Implement computing L = s0P0 + s1P1 + s2P2 + s3P3 for bn254 G1 points
using https://stackoverflow.com/questions/50993471/ec-scalar-multiplication-with-strauss-shamir-method

This should save an additional ~ 400 k steps on the Groth16 verifier with 4 inputs

Describe how https://eprint.iacr.org/2021/1029.pdf could be implemented assuming Starknet will be the weak client having access to a source of randomness, and locally-proven Cairo program being the strong server.
This should consist of a smart contract having two functions for pre-computing and verifying values on-chain and a local Cairo program. Local cairo might not even be needed in fact, the results may be passed as call data. It that's the case, it is a big win.

add a file in /tests/cairo_snarks/groth16/sample_groth16.cairo

input a groth16 proof and use the pairing and e12 arithmetics functions to verify it.
Example of usage of the library can be found in tests/protostar_tests/test_pair.cairo

reference https://www.zeroknowledgeblog.com/index.php/groth16

help is welcomed to create the proof for a simple groth16 circuit

Hashing to the curve is needed to verify bls signatures.
An example of implementation can be found here https://github.com/ConsenSys/gnark-crypto/blob/f93a56c714c4e6266429cac111a004e9eec7daa0/ecc/bls12-381/hash_to_g1.go#L313