feltroidprime

@feltroidprime

Joined on Dec 14, 2022

  • In this article we showcase a new way to greatly enhance the cost of the Miller loop and final exponentiation of pairings in circuit by extensively using hints and moving away from the traditional towered extension approach. It uses a combination of the Fiat-Shamir Heurisitic, the Schwartz-Zippel lemma, and a polynomial commitment scheme. The work has been done in CairoZero inside the Garaga library^1 for the bn254 curve. Equivalent optimisations to BLS12-381 will be applied in the near future. 1. Coming back to direct extensions Usually in almost all efficient pairings implementations, a tower of field extension is used to obtain fast formulas for $\mathbb F_{p^{12}}$ arithmetics. For example, the following tower is used for the Bn254 curve in Gnark^3 : $$ \begin{aligned}
     Like 7 Bookmark
  • I. An Introduction to Garaga Garaga^1 is a modern cryptographic library written in Cairo0 that emerged in December 2022. It is built upon the foundational efforts of Tekkac and Nethermind^2. Licensed under MIT, the project is housed within the "Keep Starknet Strange"^4 organization. It's worth acknowledging the invaluable trust and support extended by @abdelhamidbakta in bringing this endeavor to life. The integration of SNARKs into Starknet to enhance privacy has long been a sought-after goal. However, the inherent cost of performing cryptographic operations for SNARK verification in Cairo has made it a costly endeavor. To this day, finding a cost-effective method to verify SNARKs, as well as other pairing-based cryptographic methods like BLS-Signatures or KZG Commitments continues to be a challenge. However change is on the horizon. The library has undergone significant enhancements, drawing a wealth of inspiration from the work of Youssef El Housny and Ivo Kubjas at Consensys ^5. By harmonizing these advancements with specific optimizations for Cairo, Garaga now promises a resource-efficient and accessible experience. II. Operational Workflow: Making It Happen. Consider the Groth16 SNARK over the BN254 Curve.
     Like 1 Bookmark
  • How to use the power of Cairo hints by being two developers at the same time. ;) Hints in Cairo can be very powerful when utilized properly, and very dangerous if malicious actions are not prevented. In this post, we'll review through two examples how to defeat malicious provers by forcing them to comply to provide you what you want. 1. An important recap about Cairo, provers, verifiers and hints. Cairo is a Turing-complete programming language that you first prove then verify. It is not like your traditional programming language when you run the code on your machine or a cloud server and that's it. Here, there is two people and two steps involved: The prover who runs the full .cairo code and outputs a proof a computation. The verifier who validates the proof related to the .cairo file, without running the .cairo file.
     Like  Bookmark