Skip to content

Latest commit

 

History

History
95 lines (63 loc) · 8.01 KB

README.md

File metadata and controls

95 lines (63 loc) · 8.01 KB
Raw

zkSync Era Precompiles

DISCLAIMER: This implementation is still being developed and has not been reviewed or audited. Use at your own risk.

This is a precompile library implemented in Yul to speed up arithmetic operations of elliptic curves. In the next weeks, we will add more optimizations and benchmarks.

Current Status

Precompile MVP Optimized Optional Future Optimizations Audited Comments
ecAdd ✅ ✅ Montgomery SOS Squaring ✅ -
ecMul ✅ ✅ Montgomery SOS Squaring + Mul GLV ✅ -
ecPairing ✅ ✅ - 🏗️ -
modexp ✅ ✅ - 🏗️ -
P256VERIFY ✅ ✅ Montgomery SOS Squaring ✅ -
secp256k1VERIFY ✅ ✅ Montgomery SOS Squaring ✅ -

Summary

  • ecAdd is optimized with finite field arithmetic in Montgomery form and optimized modular inverse with a modification of the binary extended Euclidean algorithm that skips the Montgomery reduction step for inverting. There is not much more room for optimizations, maybe we could think of Montgomery squaring (SOS) to improve the finite field squaring. This precompile has been audited a first time and it is currently being audited a second time (after the fixes).

  • ecMul is optimized with finite field arithmetic in Montgomery form, optimized modular inverse with a modification of the binary extended Euclidean algorithm that skips the Montgomery reduction step for inverting, and the elliptic curve point arithmetic is being done in homogeneous projective coordinates. There are some other possible optimizations to implement, one is the one discussed in the Slack channel (endomorphism: GLV or wGLV), the windowed method, the sliding-window method, wNAF (windowed non-adjacent form) to improve the elliptic curve point arithmetic, and Montgomery squaring (SOS) to improve the finite field squaring, Jacobian projective coordinates (this would have similar performance and gas costs as working with the homogeneous projective coordinates but it would be free to add it since we need this representation for ecPairing). This precompile has been audited a first time and it is currently being audited a second time (after the fixes).

  • modexp has been updated to support Big Int arithmetic. This means it is now fully compatible with EIP-198's specification and all the tests are passing, however the gas costs are really high. As an example, passing a modulus with three limbs (three uint256s) will most certainly make it run out of gas. The big cost is in the finite field div_rem function, which we need to have a modulo operator on big ints, taking around 80/90% of all the gas cost when calling the precompile. The gas cost skyrockets pretty quickly the more limbs numbers have. We are looking into optimization opportunities but gas costs may still remain really high. This precompile has not been audited yet.

  • ecPairing: We have based our algorithm implementation primarily on the guidelines presented in the paper "High-Speed Software Implementation of the Optimal Ate Pairing over Barreto–Naehrig Curves" . This implementation includes the utilization of Tower Extension Field Arithmetic and the Frobenius Operator.

    To enhance the performance of the Miller loop, we have incorporated specific optimizations, we have optimized line evaluation based on the techniques outlined in "The Realm of the Pairings" . Also, instead of using Jacobian coordinates, we have adopted projective coordinates. This choice is particularly advantageous given the large inversion/multiplication ratio in this context.

    In the final exponentiation phase, we have integrated the methods presented in "Memory-saving computation of the pairing final exponentiation on BN curves". This includes the Fuentes et al. method and the addition chain. We have also applied Faster Squaring in the Cyclotomic Subgroup, as described in ”Faster Squaring in the Cyclotomic Subgroup of Sixth Degree Extensions”.

    Remaining Optimizations: While our implementation has achieved notable results, there are still some straightforward optimizations that can be implemented:

    • Optimizing Accumulated Value: We are currently naively multiplying two fp12 elements, which contain many zeros. Modifying this calculation could enhance efficiency. This is in WIP.

    Future Investigations: We need to investigate the reliability of additional optimizations, such as the application of the GLV method for multiplication of rational points of elliptic curves.

  • P256VERIFY is already working and optimized with Shamir’s trick. This precompile has been audited a first time and it is currently being audited a second time (after the fixes).

  • secp256k1VERIFY is already working and optimized with Shamir’s trick. This precompile has been audited a first time and it is currently being audited a second time (after the fixes).

Gas Consumption

Used Algorithms

Precompile
Arithmetic Operation ecAdd ecMul modexp P256VERIFY secp256k1VERIFY
Prime Field Arithmetic Addition Montgomery Modular Addition Montgomery Modular Addition Big Unsigned Integer Addition Montgomery Modular Addition Montgomery Modular Addition
Subtraction Montgomery Modular Subtraction Montgomery Modular Subtraction Big Unsigned Integer Subtraction With Borrow Montgomery Modular Subtraction Montgomery Modular Subtraction
Multiplication Montgomery Modular Multiplication Montgomery multiplication Big Unsigned Integer Multiplication Montgomery multiplication Montgomery multiplication
Exponentiation - - Binary exponentiation - -
Inversion Modified Binary Extended GCD (adapted for Montgomery Form) Modified Binary Extended GCD (adapted for Montgomery Form) - Modified Binary Extended GCD (adapted for Montgomery Form) Modified Binary Extended GCD (adapted for Montgomery Form)
Elliptic Curve Arithmetic Addition Addition in Affine Form Addition in Homogeneous Projective Form - Addition in Homogeneous Projective Form Addition in Homogeneous Projective Form
Double Double in Affine Form Double in Homogeneous Projective Form - Double in Homogeneous Projective Form Double in Homogeneous Projective Form
Scalar Multiplication - Double-and-add - Double-and-add Double-and-add

Resources

You can find a curated list of helpful resources that we've used for guiding our implementations in References

Development

Follow the instructions below to setup the repo and run a development L2 node.

Running an era-test-node

Run one of the following commands to have a working test node.

make run-node
make run-node-light # no call trace, no hash resolving, and no gas details

Run the tests

If you want to run all the tests:

make test

If you want to run a specific test:

make test PRECOMPILE=<precompile_name>

To pull changes zk sync era node LC fork on the precompiles branch

git subtree pull --prefix=.test-node-subtree --squash git@github.com:lambdaclass/era-test-node.git lambdaclasss_precompiles

To push changes from local node to the branch

This should be used if for example a precompile is added or modified, and we want to push the chanes to the fork upstream

git subtree push -P .test-node-subtree git@github.com:lambdaclass/era-test-node.git lambdaclasss_precompiles