# Secp256R1 Signature Verification using groth16 & PLONK

## Project Abstract
#### Status Quo
Webauthn enables secure passkey authentication via face ID, touch ID, and passwords, perfect for onboarding new crypto users.
#### Problem:
However, the current signature scheme for webauthn(secp256R1 elliptical curve) in solidity is highly gas-intensive around 1.2million gas. On even L2s this amount of gas will turn into huge overhead charge.
#### Solution
Our off-chain approach using groth16 and PLONK in a ZK circuit for signature verification significantly reduces gas usage to around 300k, making it more efficient and cost-effective.

## Objectives

- The main objective of this grant is to research and implement an efficient signature verification scheme using the secp256R1 curve through a ZK circuit using groth16 and PLONK while also exploring newer implementations like Halo2.
- The success of the project will be measured by around 75% reduction in gas costs, enabling widespread adoption of webauthn for smart contract wallets. Batching of multiple signatures and verifying proofs for multiple transactions in single go on-chain will further help in optimizing gas usage.
- Success can also be measured by the speed of proof generation, verification and stability of the solution, ensuring that it can be used in a production environment.

Overall, the objective is to make signature verification more efficient and cost-effective, promoting wider accessibility and adoption of crypto.

## Outcomes
The benefits of this project for the Ethereum ecosystem are significant.

**Benefits for Users:**

- Making it easier for users to access and use Ethereum blockchain as it is one of the most web2 friendly auth mechanism.
- More efficient verification process with the use of webauthn.
- More flexibility and efficiency in terms of gas costs with the use of zero-knowledge proofs for signature verification of new improved schemes

**Benefits for Developers and Researchers:**
- Reduced effort and challenges for integrating new signature schemes into Ethereum ecosystem
- Open-source nature of this project will enable other developers to contribute and build faster circuits with better proving time and memory-efficient proving keys.

Hence, it offers significant benefits to both users and developers in the Ethereum ecosystem.

## Grant Scope

#### Grant research scope:
- Conduct research into existing signature verification schemes like BLS, ECDSA, EDDSA, and RSA.
- Explore implementation of elliptical curve operations like point addition, scalar multiplication, adding two unequal points in elliptical curve and point doubling in Circom, with a focus on the secp256R1 curve.
- Understand the underlying mathematics and cryptographic principles involved.
- Reading and implementing various recent developements like Turbo Plonk, Plonkup, Halo2 and Plonky2.
- Design multiple experiments for improving the speed of verification of proofs and decrease the size of proving key in user machines.

#### Expected Output:
- Identify potential improvements to existing ZK based signature verification schemes and elliptical curve operations by Persona Labs, 0xParc, and zkAsset. These will be mainly help in improving the verification time(current time 439s) and proving key size.
- Sharing our findings and insights with the wider community by publishing research articles weekly, potentially leading to new avenues of research or applications of your work.
- Develop new circuits for verification with optimized gates and fewer constraints based on the insights and findings obtained from the research.
- Comprehensive report or publication that benchmarks the results of different methods used like PLONK, groth16 and halo2.
- Aggressive testing of the circuits and aiming to get them audited for security and efficiency. This will be a top priorities to ensure that the resulting code is robust and secure.

## Project Team
How many people are working on this project?

Please list their names and roles for the project as well as how many hours per month will each person work on this project?
The team will initally consist of two members:
- Rishabh Gupta, ZKP developer: 80 hours/week
- Nitanshu Lokhande, Solidity and full stack developer: 80 hours/week

## Background

#### Rishabh Gupta: [Github](https://github.com/rishotics) [LinkedIn](https://www.linkedin.com/in/rishotics/) [Twitter](https://twitter.com/rishotics)
- Working with zero-knowledge proofs for more than 1.5 years now
- Have won prizes in [ETH Online 2022](https://ethglobal.com/showcase/zkauth-zgdq7), [Polygon Buidl It '22](https://devpost.com/software/pecunia-qatynj) and ETH India '22 in ZK projects
- Gwei **Ethereum India Research Fellow** 3.0 where I was working on webauth based wallet deployment and transaction signing
- Co-founder Rize Labs(Banana Wallet SDK)
- Ex-blockchain engineer at Biconomy
- Ex-freelance worker at Instadapp
- Ex-analyst at Goldman sachs

#### Nitanshu Lokhande: [Github](https://github.com/nlok5923) [LinkedIn](https://www.linkedin.com/in/nitanshu-lokhande/) [Twitter](https://twitter.com/NitanshuL)
- Fullstack + Solidity dev
- Founding Dev at Rize Labs(Banana Wallet SDK)
- Gwei **Ethereum India Research Fellow** 3.0 (Worked on Banana Wallet SDK)
- **Polygon Research Fellow 2022**
- Past Dev at Zus Network
- Contributed to Oppia, anitaborg, fossasia
- **[Push and Tableland Grand prize winner + filecoin grantee.](https://github.com/filecoin-project/devgrants/issues/1052)**

Also
- Our team presented [Banana Wallet SDK](https://github.com/nlok5923/hacking-at-ethindia) at [ETH India 2022](https://devfolio.co/projects/banana-smart-wallet-efca). Banana Wallet received lots of love from developers at ETH India and has won

- Among **top 3 projects** among around 500 submitted projects
- 🥇 First prize from Ethereum Foundation in Account Abstraction
- 🥇 First prize from Safe
- 🥇 First prize from Gnosis chain
- 🥉 Third prize from Coin DCX
- 🏊🏼‍♂️ Pool prizes from Push protocol and IPFS
- 🏆 [Filecoin Micro grant](https://github.com/filecoin-project/devgrants/issues/1238)

We have been working on this project from 3 months now and gained quite a lot of expierence and developed a deep understanding of EIP 4337 and account abstraction.

We both are [ETH India Fellows](https://devfolio.co/projects/banana-wallet-sdk-fd24) and have been working from past 7 weeks to build [Banana SDK](https://github.com/Banana-Wallet/banana-contracts) with webauthn capability. We have developed an in-house SDK which Dapps can integrate for allowing users to create a wallet in less than 1 min using their face ID or touch ID. Our package is also live on [npmjs](https://www.npmjs.com/package/@rize-labs/banana-wallet-sdk). We have been working closely with Tom Teman who is our mentor from Ethereum Foundation at Ethereum India research fellowship 3.0 to refine our idea and build the product.

We will be happy to provide any additional proofs, documents or code needed for verification.

## Methodology
How do you plan to achieve your research objectives?

I have already started the backgroud work needed for building the circuits. We encountered a major hurdle in our preliminary investigation: current zkSNARK proving systems are limited to specific elliptic curves that only allow operations on numbers represented as residues modulo a specific prime. This restricts the maximum "register size" for numbers used in zkSNARK proofs to $254$ bits, which is insufficient for handling operations on the secp256R1 elliptic curve. This curve is widely used standard in Hardware Security Modules like secure enclaves, but is not "SNARK-friendly," as it requires arithmetic on $256$ bit numbers that overflow the $254$ bit registers allowed in current SNARK systems.

To address this challenge, we plan to use non-native field arithmetic circuits for Big Int arithmetic and secp256R1 operations using $254$ bit registers. This will enable us to implement ECDSA algorithm for signature verification and aggregation within the constraints of zkSNARK proving systems.

We will represent large numbers such as private keys, public key coordinates, and other $256$ bit numbers in a little-endian form that is adapted to zkSNARKs. For instance, we use arrays of four signals constrained to $64$ bits each to represent $256$ bit numbers, with an array interpreted as the number.
$$arr[0]+ (2 ^{**} 64) * arr[1] + (2 ^{**} 64 * 2) * arr[2] + (2 ^{**} 64 * 3) * arr[3]$$

**Scalar multiplication** is an important operation in ECDSA, during verification we calculate

$$ Private Key: P_v $$

$$ q = u_1 . G + u_2 . (P_v .G) $$

where $$ u_1 = Hash(message). inv(s) $$

$$ u_2 = r . inv(s) $$

and

$$ signature = (r,s) $$

For the calculation of $u_1.G$ we need scalar multiplication. As $G$ is the generator point of secp256R1 curve.
$$ G_x=0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
$$ $$ G_y=0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
$$

To achieve this in a non-native field of $254$ bits we need to store the pre-computed multiplications of generator value. The idea boils down to the basic of number theory, asking how a number is represented in its respective base.

$$ 356 = 3 * 10^2 + 5 * 10^1 + 6 * 10^0 $$ where $$ base=10 $$
$$ 11 = 1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0 $$ where $$ base=2 $$
So the idea is to present a number in following format:

$$ number = \sum_{l=0}^{ceil(log_{base}(number))} b_l * base^l $$
$$ b_i \in [0,base-1] $$

- Here we will change the representation of scalar(256 bits) value by breaking it into smaller chunks. We need to break the scalar value in $k$ registers of $n$ bits each.

- Because the base point $G$ is known and fixed in our setting, we can reduce the number of point operations by precomputing and caching multiples of $G$ by powers of two.We need to store the pre-computed values of $b_l * base^l * G$ in a 2D array $powers(i,j)$. $w$ is the window length, which represents how many bits are selected for iteration.
Where

$$[0 \le i < \frac{n}{w}*k] $$
$$\&$$
$$ 0\le j<2^k $$
$$ arr[i,j] = j * (2^w)^i * G $$

This element will be containing $2k$ values($k$ values for $x,y$ co-ordinate each).

- Then we will use a window approach where we will first pick up $w$ bytes from first register and find its corresponding value in the first row of $powers$ array. After we have all $\frac{n}{w}*k$ values of broken scalar value. We will group binary digits of the private key into groups of size $w$, cache multiples of $G$ corresponding to numbers with non-zero binary digits only in a single group, and represent $G$ as a sum of the cached elliptic curve points. For every $n$ bits of the scalar value at position $[w*i, w*i + w]$ we will find the corresponding $i$ th row in $powers$ array and then the $j$ th column where Bits2Number(bits $\in[w*i, w*i + w]$) which is non-zero, and add it to the result.

**For BigInt number** multiplications normally, with $k$ registers, a naive multiplication implementation uses two for-loops to compute intermediate products, for $O(k^2)$ constraints, followed by a bunch of carries that takes $O(nk)$ constraints
- When implementing big Int multiplication in zkSNARKs with $k$ registers, a naive approach will involve using two for-loops to compute intermediate products, resulting in $O(k^2)$ constraints. After this carry operations that take $O(nk)$ constraints will be performed, where the primary cost is a set of range checks that ensure that each of the $2k$ registers is no more than n bits in size. What we can do is represent each number in an a proper number format with base value equal to $2^{**}64$. $$ a = a[0] * (2 ^{**} 64 * 0) + a[1] * (2 ^{**} 64 * 1) + ... + a[k-1] * (2 ^{**} 64 * k-1)$$
We will write this number such that each coffecient is following the m-overflow representation i.e each coeffient in above equation is less than $(m * x)$. In our case each coefficient should be less that $(2 ^{**} 64 )$.

- If we take $2$ such numbers, lets call them a and b in the above format and take a multiplication. The resulting number will be having $(2^{**} 64 -1)$ coefficients. We also need to take care of the carry term for each coefficient. As it may happen that each term might cross the $(2^{**} 64 - 1)$ mark and we need to make sure if that happens carries are handled properly. We can also convert this $O(k ^{**} 2)$ multiplication process into $O(k)$ steps by comparing the coefficients of same power terms in $a * b = c$ equation.

In **point addition,** we will perform elliptic curve point addition with 2 distinct points P and Q giving R.

$$ P + Q = R $$
$$ (x_p,y_p) + (x_q,y_q) = (x_r,y_r) $$
So the result is
$$ x_r=\lambda ^2 - x_p-x_q $$
$$ y_r=\lambda . (x_p-x_r) - y_p $$

where,
$$ \lambda = \frac{y_q-y_p}{x_q-x_p} $$

Similar approach will be used for point doubling where
$$ \lambda = \frac{3x_p^2 + a}{2y_p} $$

We will not be converting it to Jacobian form for addition as it was mentioned in the 0xParcs blog that inside Zk circuits the difference in number of constraints of modulo inverse and module multiplications operation is almost same. So it does not improve the performance.

Finally all this will come together in a final circuit where we will calculate
$$ q = u_1 . G + u_2 . (Pub_k .G) $$

In the result we will output public key with $k$ registers each for $(x,y)$ co-ordinates.

In conclusion, we will conduct an extensive literature review and investigate existing research in this area, in order to build upon previous work and identify the most effective approaches for our specific use case. This work is inspired from 0xParc's work on ZK ECDSA for secp256k1 curve. We will also collaborate with our mentor from the Ethereum Foundation to refine our methodology and ensure that our research is aligned with current industry standards and best practices.

Our Github project [link](https://github.com/nlok5923/zk-ecdsa-secp256r1).

Handwritten solved examples for reference [here](https://drive.google.com/file/d/1xmn7ylF2zu-85W2ETZcQJrvM8v2Tirmz/view?usp=share_link).

## Timeline

A rough timeline would look like:
- 10th April to 30th April: RnD over existing work on ZK based ECDSA schemes implemented using groth16, plonk, Halo2 for secp256K1, BLS signature and pairing friendly curve schemes
- There are several resources by [Personae Labs](https://github.com/personaelabs/efficient-zk-ecdsa), [0xParc](https://0xparc.org/blog/zk-ecdsa-1), and [zkAttest](https://github.com/cloudflare/zkp-ecdsa) for secp256k1 curve.
- Some popular libraries are already built for handling [BigInt operations in circom](https://github.com/nlok5923/zk-ecdsa-secp256r1/tree/feat/basic-circuit/circuits), we are also going through them for proper understanding
- We already have a deep understanding of groth16 and PLONK, so we are exploring newer advancements like Turbo Plonk, Hyper Plonk and Halo2.
- 1st May to 30th May: Implementing the Proof Of Concept of the circom circuit
- First step will be to modify the existing circuits of elliptical curve operations and prepare the powers array containing the cached values multiplied with Generator points for secp256R1 curve.
- Then we will move towards adding the ECC operations required for scalar and BigInt multiplications.
- Verification circuit will be designed by putting everything in place.
- 1st June to 30th June:
- This time will be devoted to writing the test cases for checking constraints of groth16 circuits.
- While going through existing approaches we found that the time taken for these proof systems is not compatible with webauthn as it will be a big friction to the UX thats why we need to use more advanced SNARK systems apart from groth16. These might include [Halo2](https://www.youtube.com/watch?v=vRiUeDPomkQ&t=2s) for ECC operations and PLOOKUP for optimizing ciruits with smaller size of register.
- 1st July to 30th July:
- Period for circuits auditing.
- For V2, we will start with Halo2 implementation of ECC functions

## Budget

We are requesting an amount 20,000$ from the grant committee. These funds will be used to support our reseach and developement for 4 months. Apart from supporting the team it will also be used for various tasks.
- Team's salary: 1000\$/month * 2 people * 4 months = 8000$
- Hardware costs: This will include getting a machine with high CPU cores and RAM for circuit processing with large number of constraints: 4000$
- Auditing: around 5000$
- Outsourcing costs: These might include if we need to hire a ZK developer to speed up the things: 3000$