# A Primer on Secp256r1

The goal of this document is to present an overview of the different approaches to validating the secp256r1 elliptic curve in an EVM setting. The primary goal is to reduce the gas cost of the signature verification, but there are also secondary tradeoffs to consider such as deployment gas costs, pre-computation/proving times, ease of use, and future areas of gas reduction.

## Zero Knowledge via Halo2
**Single Signature gas cost:** 391,331 gas

**High Level Approach:**
Know Nothing Labs uses a zero knowledge proofs to reduce the gas costs of the secp256r1 signature. Specifically, they support ES256 along the P-256 elliptic curve, which is present on Apple's FaceID/Touch ID, Andriod devices, Intel SGX secure enclaves, hardware devices like Yubikeys, and much more.

**End to End Flow:**
1. **Generating the Signature:** The signature is generated asking the passkey to sign the data the user wants signed. In the [demo](https://www.noseedphrases.xyz/), this is a UserOperation and the signature returned from the passkey is a signature over the User Operation.
2. **Generating the Zero Knowledge Proof:** The signature from the passkey is then turned into a zero knowledge proof. They use the Halo2 proof system to generate the proof on the server side. Client side proof generation on a local browser or dApp is also possible, but server side proving is much faster.
3. **Verifying the Zero Knowledge Proof On-chain:** The zero knowledge proof is set as the `UserOperation.signature` field and passed to the P256Account for verification. The P256Account calls a separate snark verifier contract, which verifies the zero knowledge proof against the UserOperation and the public key of the passkey.

**Misc:**
- Proving times range between 3-15 seconds, depending on what level of hardware you are currently using to generate proofs.
- This method is completely decentralized and immutable. There are no trusted parties, no trusted setups, and the prover can be run client side for a truly trustless experience

**Future areas of improvement:**
- **Proving time:** We have been exploring specialized hardware acceleration via providers like Sindri Labs or SuperScalar. Currently, an M1 Mac has proving times between 3-4 seconds. In other applications, GPU acceleration, Sindri, or superscalar have seen 5-20x speedups when compared to baseline proving speeds.
- **Accumulation Schemes:** In 2019, a paper was published by the Electric Coin Co, the makers of Zcash and the halo2 proving system that demonstrated the feasibility of recursive proof composition. This allows a single halo2 proof to attest to the correctness of a practically unlimited amount of other proofs. The two bottlenecks here are 1) the amount of users wanting proofs at the same time and 2) implementing this into the system.
- In a few years, EIP-7212 may be passed on a sizable number of chains, such that it will be the default solution to verifying the secp256r1 curve.

## Solidity - Ledger's Fresh Crypto Lib
**Single Signature Gas Cost:** ~70,000 gas

**High Level Approach:** Ledger's Fresh Crypto Lib(FCL) is currently the most optimized and known piece of software for verifying the secp256r1 curve in pure solidity. It uses a number of optimizations in order to reach the low stated gas cost:
1. Similarly to Obvious Wallet's implementation, FCL uses Shamir's trick and `modexp` for point multiplication and efficient exponentiation.
2. **Reducing the number of negations:** While negation is almost free in Arithmetic Logic Units(ALU, present in most computing devices), it costs half a `mulmod` and can be avoided by inspecting the output and exchanging the intermediate operators.
3. **XYZZ Coordinates:** As an improvement, Jacobian coordinates from the Obvious wallet implementation have been turned into coordinates with the format `(x,y,zz,zzz)` where its affine representation is obtained from computing `X = (x/zz)` and `Y=y/zzz`
4. **Precomputations:** The optimization strategy involves externalizing precomputations, leveraging constant inputs like the base point P and public key Q, and potentially increasing the number of inputs to enhance the efficiency of the elliptic curve cryptography algorithm for signature verification.
5. **SSTORE 2:** The main drawback when using precomputations is the usage of a large array of elliptic curve points which would be very expensive to create in solidity. One workaround is the usage of the [`SStore2`](https://github.com/0xsequence/sstore2) storage pattern, where the array is stored inside a newly deployed contract's bytecode. The drawback is the newly deployed contract requires a heavy deployment cost hiwhc is currently benchmarked at 3.2 million gas. However, this is amortized over the cost of many transactions and tends to zero.

**End to End Flow:**
1. **Generating the Signature:** The user generates the signature using the passkey and creates signature as well as preprocessing the signature. Unfortunately, it is unclear as to how the preprocessing actually works, but it is safe to assume that there is some small overhead to the preprocessing.
2. **Submitting the Signature:** The user submits the signature in the signature field of the UserOperation.signature field. The signature is then verified via the Secp256r1.sol verifier.

**Future Areas of Improvement:**
The optimized solidity approach has already been around for many years and some of the smartest developers and researchers have taken an attempt at optimizing it further. Thus, while there is still likely to be room for optimization, it seems unlikely for there to be a 10x decrease in gas costs.

## Solidity - Obvious Wallet
**Single Signature Gas Cost:** 294,569 gas

**High Level Approach:** Obvious wallet builds on previous work in the pure solidity attempts to verify secp256r1. The library is based off of a [previous attempt](https://github.com/maxrobot/elliptic-solidity/blob/master/contracts/Secp256r1.sol) by Max Robot's Elliptic Solidity library which costs ~1m gas per signature verification. The optimizations are as follows:
1. **Precomputation and Shamir's trick:** The code precomputes a set of 16 Jacobian coordinates representing specific points on the elliptic curve. These precomputed points are then utilized in the Shamir's Trick for efficient point multiplication.
2. **Jacobian coordinates:** The arithmetic operations are performed in Jacobian coordinates rather than affine coordinates. Jacobian coordinates allow for more efficient elliptic curve arithmetic.
3. **Efficient Exponentiation:** The code includes a modular exponentiation function (modexp) that takes advantage of the Ethereum precompile (0x05) for efficient exponentiation modulo a prime.

**End to End Flow:**
1. **Generating the Signature:** The user generates the signature using the passkey and creates signature as well as preprocessing the signature. Unfortunately, it is unclear as to how the preprocessing actually works, but it is safe to assume that there is some small overhead to the preprocessing.
2. **Submitting the Signature:** The user submits the signature in the signature field of the `UserOperation.signature` field. The signature is then verified via the [Secp256r1.sol](https://github.com/itsobvioustech/aa-passkeys-wallet/blob/main/src/Secp256r1.sol) verifier.

**Future Areas of Improvement:**
- Currently, the gold standard for a pure solidity implementation seems to be Ledger's library, so there is room for additional precomputation as well as a more optimized setup.

## Zero Knowledge Via Circom
**Single Signature Gas Cost:**
There are no confirmed gas costs for this library, as it is currently under construction. However, it seems pretty likely that gas costs will be close to 1 million gas per signature verification, as compared with similar circom circuits

**High Level Approach:** A group from the Ethereum Foundations Privacy and Scaling Explorations is attempting to implement the P-256 curve in circom. The main idea is to perform the computations in a zero knowledge circuit and verify the computation on chain via a zero knowledge proof instead of redoing the computations on chain.

**End to End Flow:**
1. **Generating the Signature:** The user generates the signature using the passkey and creates signature.
2. **Generating the Proof:** The signature would be submitted to a client side prover which generates a proof using a zk-snark via circom
3. **Signature Verification:** The signature is then verified and a proof is sent to the smart contract where the transaction is executed

**Future Areas of Improvement:**

## Zero Knowledge Via Risc0
**Single Signature Gas Cost:** 220,000

**High Level Approach:** Risc0 is a zero knowledge coprocessor, where computation from ethereum mainnet can be offloaded to risc0 and the results of the computation can be relayed to Ethereum via bonsai.

**End to End Flow:**
1. **Generating the Signature:** The user generates the signature using the passkey and creates signature.
2. **Generating the Proof:** The signature would be submitted to risc0's bonsai provers which generates a proof using a zk-stark
3. **Signature Verification:** The signature is then verified and a proof is sent to the smart contract where the transaction is executed

**Future Areas of Improvement:** Improvements for this method are up to the development and improvement of the risc0 ecosystem and the bonsai network. If there are breakthroughts, the gas costs can be reduced, but this is a difficult problem to approach.

## EIP-7212
Sourced from the [Clave Team](https://www.getclave.io/)

**Single Signature Gas Cost:** 3450 gas

**High Level Approach:**
EIP-7212 proposes a new precompiled contract for verifying the secp256r1 curve at a cost of just 3,450 gas. While it is still under review, it requires community support to make it to the mainnet. Notably, some Layer 2 solutions are already considering the implementation of EIP-7212 in their EVMs.

**End to End Flow:**
1. **Generating the Signature:** The user generates the signature using the passkey and creates signature.
2. **Submitting the signature:** The user can submit the signature - the signature will be verified by the precompile.

**Future Areas of Improvement:** The biggest problem is the difficulty of getting an EIP adopted. Furthermore, each network will need to adopt the EIP as a precompile.

## Existing Native Support
**High Level Approach:** Many layer two and alternative layer one blockchains natively support the secp-256r1 as a precompile. Here is a list:
- **Aztec Network:** Noir, the domain specific language that Aztec uses, [natively supports](https://github.com/noir-lang/noir/pull/1858) Secp256r1 in its standard library
- **Fuel Network:** The Fuel VM [natively supports](https://specs.fuel.network/master/fuel-vm/instruction-set.html#ecr1-secp256r1-signature-recovery) in its instruction set.
- **Zksync Era:** There has been a [precompile](https://github.com/lambdaclass/zksync_era_precompiles/blob/52be22232a696dca7ccc27decd61576d2584b4f6/precompiles/P256VERIFY.yul) added via EIP-7212 to Zksync Era. However, it is not live yet, though it is coming soon as [confirmed](https://twitter.com/gluk64/status/1731421365469618476) by the founder of zkSync.
- **Starkware:** Cairo does not natively support Secp256r1, but there are [many](https://github.com/cartridge-gg/cairo-webauthn) [libraries](https://github.com/myBraavos/efficient-secp256r1) that try to reduce gas costs.

There are also networks that have planned the upgrade, but have not yet implemented the precompile:
- **Near Protocol:** Near Protocol plans to add the Secp256r1 curve in the next [two years](https://www.pagoda.co/blog/protocol-roadmap-2023-4-the-next-2-years-of-near).

**End to End Flow:**
1. **Generating the Signature:** The user generates the signature using the passkey and creates signature.
2. **Submitting the signature:** The user can submit the signature - the signature will be verified by the precompile.

**Single Signature Gas Cost:** The gas cost is dependent on each chain, but it is likely an order of magnitude less than other verification methods.

**Future Areas of Improvement:** It is likely that more and more networks will adopt EIP-7212, as the risks related to adding a precompile to a single network are not that high. However, it likely won't be for a few years until Ethereum supports this, as the current plan is to wait for layer two networks to adopt it into production before adding it to Ethereum.

# References
This is a list of reference material that gives further context into Secp256r1 in the Ethereum Virtual Machine.

## Research
[**The Current State of Verifying Secp256r1**](https://hackmd.io/@1ofB8klpQky-YoR5pmPXFQ/SJ0nuzD1T) - This gives a good overview of the current state of live verifiers on EVM blockchains

[**Speeding up elliptic computations for Ethereum Account
Abstraction**](https://eprint.iacr.org/2023/939.pdf) - Reducing the cost of Secp256r1 in solidity (ledger implementation)

[**Improving Proving Times with GPUs**](https://medium.com/@SuperScalar_io/quick-overview-of-the-halo2-gpu-acceleration-solution-f68c00652552) - This goes into proving times for the Halo2 proving system with ways to accelerate proving times and associated benchmarks.

[**Recursive Snarks**](https://medium.com/@richardchen_81235/intro-to-recursive-snarks-50d201796109) - A primer on recursive snarks

[**Recursive Schemes for Halo2**](https://eprint.iacr.org/2020/499) - An academic paper defining a general recursive proving scheme

## Application

[**Sindri Labs Docs**](https://sindri-labs.gitbook.io/forge/bc8WIRWQjpisJcyNffoc/forge/introduction) - Sindri Labs' Forge API provides simple access to state-of-the-art hardware acceleration for zero knowledge proof generation.

[**Supporting WebAuthn on Starknet**](https://hackmd.io/@tarrence/Hkjrm8cJj) - A primer with code on the current state of webauthn proving on starknet

[**EthCC Talk on Secp256r1 Optimization**](https://www.youtube.com/watch?v=Rlq21oA_FA8)

## Implemetations
[**Secp256r1 implementation in Huff**](https://github.com/atarpara/LibSecp256r1) - This repo contains a Huff contract of the basic curve operation of the secp256r1 curve.

[**Cryptography Library**](https://paulmillr.com/noble/) - Paul Miller Noble javascript library for its G1 implementation of BN254 and BLS12, and keccak256.

[**Alembic/cometh P256 Library**](https://github.com/alembic-tech/P256-verify-signature/blob/main/contracts/EllipticCurve.sol)
[**Braavos P256 Library**](https://github.com/myBraavos/efficient-secp256r1/blob/develop/src/secp256r1/ec_mulmuladd.cairo)
[**Cartridge P256 Library**](https://github.com/cartridge-gg/cairo-secp256r1/pull/3)
[**Daimo P256 Library**](https://github.com/daimo-eth/p256-verifier/blob/master/src/P256Verifier.sol)
[**ForumDAO P256 Implementation**](https://github.com/forumdaos/forum-contracts/blob/main/src/libraries/FCL_Elliptic_ZZ.sol)
[**MaxRobot P256 Library**](https://github.com/maxrobot/elliptic-solidity)
[**Numerology P256 Library**](https://github.com/nucypher/numerology)
[**Obvious P256 Library**](https://github.com/itsobvioustech/aa-passkeys-wallet)